first.tex

\documentclass[10pt, a4paper, twocolumn]{article}

\input{structure.tex} % Specifies the document structure and loads requires packages


% \usepackage{draftwatermark}



%----------------------------------------------------------------------------------------
%  ARTICLE INFORMATION
%----------------------------------------------------------------------------------------
\title{Decoding Secret Sequences and Mixing Up Quantifiers} % The article title


\author{
  \authorstyle{B\'ela Bajnok and Peter Francis} % Authors
  \newline\newline % Space before institutions
  \institution{Gettysburg College}
}
% \textsuperscript{1,2,3}

% % Example of a one line author/institution relationship
% \author{\newauthor{John Marston} \newinstitution{Universidad Nacional Autónoma de México, Mexico City, Mexico}}

\date{} % Add a date here if you would like one to appear underneath the title block, use \today for the current date, leave empty for no date

%----------------------------------------------------------------------------------------

\begin{document}


\maketitle % Print the title

\thispagestyle{firstpage} % Apply the page style for the first page (no headers and footers)

%----------------------------------------------------------------------------------------
%  ARTICLE CONTENTS
%----------------------------------------------------------------------------------------


\newcommand{\s}{\mathbf{s}}
\newcommand{\q}{\mathbf{q}}
\renewcommand{\t}{\mathbf{t}}




\lettrine{A}merican writer, teacher, and comedian, Sam Levenson, gives us the following warning:

\vspace{.15in}

\begin{center}
  \begin{Large}
    Somewhere on this globe, every ten seconds, there is a woman giving birth to a child. She must be found and stopped.
  \end{Large}
\end{center}

\vspace{.15in}

The joke comes from the fact that the statements ``for any given time, there is a place, at which there is a woman giving birth'' and ``there is a place, for which there is a woman, that is always giving birth'' are not equivalent. The first is believable while the second, if true, would be ridiculously disastrous.

As this example shows, there is a discrepancy between the sometimes deceiving and confusing use of quantifiers (words or phrases used to describe the quantity of objects that have a certain property) in the English language and the rigidly fundamental role that quantification plays in mathematical writing. So the question is: how do we translate? Moreover, how do we teach new Mathematical thinkers the importance of the delicate care that quantifiers need? The answer is a game of course!

$\forall$ people, $\exists$ an understanding and $\nexists$ a want for review, skip the next section. If you're confused by that last sentence, that's OK, just keep on reading!

\section*{The Notation of Quantifiers}

When discussing quantifiers at length, it is useful to have a simple notation to save time and brain power, so before we get to our game, let's review some standard logical symbols.

We will write $P(x)$ to denote a statement whose truth depends on $x$ in a set $A$. For example, if $P(x)$ denotes the predicate
$$x<57\text{ or } x \text{ is odd},$$
for a positive integer $x$, then $P(4)$, $P(57)$, and $P(101)$ are all true, while $P(100)$ and $P(134)$ are false.

Here are the shorthand symbols we most often use:

\begin{itemize}
  \item $\forall$ is the universal quantifier and can be pronounced ``for all''.
  \item $\exists$ is the existential quantifier and can be pronounced ``there exists''.
  \item $\nexists$ is the non-existential quantifier and can be pronounced ``there does not exist''.
\end{itemize}

The sentence $$\forall x\in A, P(x)$$ means that \textit{for all $x$ in the set $A$, $P(x)$ is true}.
The sentence $$\exists x\in A, P(x)$$ means that \textit{there is some (at least one) $x$ in the set $A$ for which $P(x)$ is true}.
The sentence $$\nexists x\in A, P(x)$$ means that there is no $x$ in the set $A$ for which $P(x)$ is true. Equivalently, we can write
$$\forall x\in A, \lnot P(x),$$
meaning that \textit{for all $x\in A$, $P(x)$ is false}.

% There are other symbols used for quantification, but these are the only ones we will be using.

The order of nested quantifiers can change the meaning of the statement drastically. Returning to Sam Levenson's joke, we are now comfortable distinguishing between the statements
$$\forall\text{ time}, \exists\text{ place},\exists\text{ woman giving birth}$$
and
$$\exists\text{ place}, \exists\text{ woman},\forall\text{ time giving birth}.$$

\section*{The Game}

Here is the game. Imagine I have a secret sequence of four positive integers that you would like to know. You are allowed to ask questions also in the form of sequences of positive integers, to which my response will be the sum of the coordinate-wise product of the two sequences, denoted by $(\ \cdot\ )$.
For example, if the secret sequence is $\s=(1,2,3,4)$, the response to the question $\q=(2,3,10,8)$ is
$$\q\cdot\s  = 2(3)+3(2)+10(3)+8(4)=74.$$
The goal of the game is to discover my sequence in as few questions as possible. Let's play!

I have a sequence $(s_1,s_2,s_3,s_4)$ in mind. You first ask the question
$$(1,1,1,1),$$
to which my response is
$$s_1+s_2 + s_3+ s_4=42.$$
Now you know that every term in the sequence is less than 42, so has at most two digits. You cleverly ask the question
$$(10^6,10^4,10^2,1),$$
and I respond with
$$10^6\cdot s_1+10^4\cdot s_2 + 10^2 \cdot s_3+ 1 \cdot s_4=20031405.$$
Looking at the digits of my response, you can deduce that my secret sequence was $(20,3,14,5)$.

It is not hard to see that this two-question method will always work! Any sequence can be discovered by asking the questions $(1,1,1,1)$ and $(10^{3d},10^{2d},10^{d},1)$, where $d$ is the number of digits in the response to the first question.

Well I suppose that it is not that exciting of a game after all. However, you might be wondering if there is a more efficient method, a winning strategy with only one question.

Clearly, if the first question $(1,1,1,1)$ were to have a response of $4$, then we know that the secret sequence was also $(1,1,1,1)$, so we know that winning the game with one question is possible. However, to go any further, we will need to get a little more technical about what we mean by `winning the game.'


\section*{Decoding Sequences}

Let $D(\q,\s)$ denote the predicate that the question $\q$ decodes the secret $\s$. In order to decode the secret with one question, you must be sure that no other secret sequence will return the same response for your question.

That is, $D(\q,\s)$ is true exactly when there is no sequence $\t\neq\s$ for which $$\q\cdot\s=\q\cdot\t.$$
In quantifier notation,
$$D(\s,\t)\iff\nexists\t\neq\s, \q\cdot\t=\q\cdot\s,$$
or equivalently,
$$D(\s,\t)\iff\forall\t\neq\s, \q\cdot\t\neq\q\cdot\s.$$

So now we can ask our question more carefully. Is there a question sequence that can decode any secret sequence: is
$$\exists\q,\forall\s,D(\q,\s)$$
true?

Now you might see why this game is so interesting. We can ask quite a few similar sounding questions that are really quite different, just by changing the order and type of the quantifiers.

\section*{Mixing Up Quantifiers}
Here is a list of different modifications we can make to the quantifier chain above. (5 is the same as above.)

\begin{enumerate}
  %1
  \item ``There is some question that can decode some secret.''
        $$\exists\q,\exists\s,D(\q,\s).$$

        %4 --> 2
  \item ``Every question decodes every secret.''
        $$\forall\q,\forall\s,D(\q,\s).$$


        %3
  \item ``It is possible to ask any question and sometimes decode the secret.''
        $$\forall\q,\exists\s,D(\q,\s).$$


        %5 --> 4
  \item ``There is some secret that can be decoded by any question.''
        $$\exists\s,\forall\q,D(\q,\s).$$



        %2 --> 5
  \item ``There is some fixed question that can decode any secret.''
        $$\exists\q,\forall\s,D(\q,\s).$$



        %6
  \item ``For any secret, we can pick a question to decode it.''
        $$\forall\s,\exists\q,D(\q,\s).$$


\end{enumerate}

Before moving on, attempt to determine the truth of each of these claims. Do not get discouraged; while some of these require simple counterexamples or short proofs, others are a bit more involved to prove. I have arranged them from (what I believe to be) simplest to prove to most challenging.

Remember that a neat artifact of this notation is that in order to negate a statement quantified with only $\exists$s and $\forall$s, we can just switch the $\forall$s and $\exists$s and negate the last predicate. For example, the negation of the sentence
$$\exists a\in A, \forall b\in B, P(a,b)$$
is the sentence
$$\forall a\in A, \exists b\in B, \lnot P(a,b).$$

Each of these six statements is either proven or disproven below.



\newpage
\begin{enumerate}
  \item $\exists\q,\exists\s,D(\q,\s)$ is true.
        \begin{proof} The question $\mathbf{q}=(1,1,1,1)$ decodes the secret sequence $\mathbf{s}=(1,1,1,1)$.
        \end{proof}

  \item $\forall\q,\forall\s,D(\q,\s)$ is false.
        \begin{proof} We must show that
          $$\exists\q, \exists\s, \exists \t\neq\s,\q\cdot\s=\q\cdot\t.$$
          Take $\q=(1,1,1,1)$, $\s=(2,1,1,1)$, and $\t=(1,2,1,1)$. Then
          $$\mathbf{q}\cdot\mathbf{s} = 2+1+1+1=\mathbf{q}\cdot \mathbf{t}.$$
        \end{proof}



  \item $\forall\q,\exists\s,D(\q,\s)$ is true.
        \begin{proof} Given any question $\q=(q_1,q_2,q_3,q_4)$, let $\s=(1,1,1,1),$ and suppose indirectly that there is some $\t=(t_1,t_2,t_3,t_4)\neq\s$ for which
          \begin{align*}
            q_1+q_2+q_3+q_4 & = \q\cdot\s                   \\
                            & =\q\cdot\t                    \\
                            & =q_1t_1+q_2t_2+q_3t_3+q_4t_4.
          \end{align*}
          If any $t_i>1$, then $\q\cdot\t>\q\cdot\s$, so $$t_1=t_2=t_3=t_4=1,$$
          contradicting that $\s\neq\t$.
        \end{proof}



  \item $\exists\s,\forall\q,D(\q,\s)$ is true.

        \begin{proof} Let $\s=(1,1,1,1),$ and similarly to (3), for all $\q=(q_1,q_2,q_3,q_4)$, there is no $\t\neq\s$ for which
          \begin{align*}
            q_1+q_2+q_3+q_4 & = \q\cdot\s                   \\
                            & =\q\cdot\t                    \\
                            & =q_1t_1+q_2t_2+q_3t_3+q_4t_4.
          \end{align*}
        \end{proof}


  \item $\exists\q,\forall\s,D(\q,\s)$ is false.
        \begin{proof} We must show that
          $$\forall\q, \exists\s, \exists \t\neq\s,\q\cdot\s=\q\cdot\t.$$
          Well, given any $\q = (q_1,q_2,q_3,q_4)$, let
          $$\s=(1+q_2,1,1,1)$$ and $$\t=(1,1+q_1,1,1).$$ Then
          \begin{align*}
            \q\cdot\s & = q_1(1+q_2)+q_2+q_3+q_4 \\
                      & = q_1+q_2(1+q_1)+q_3+q_4 \\
                      & = \q\cdot\t.
          \end{align*}
        \end{proof}

  \item $\forall\s,\exists\q,D(\q,\s)$ is true.

        \begin{proof}
          Let $\s=(s_1,s_2,s_3,s_4)$. Pick pairwise relatively prime positive integers $a_1$, $a_2$, $a_3$, and $a_4$, each greater than $\max\{s_1,s_2,s_3,s_4\}$. Let
          \begin{align*}
            q_1 & =a_2a_3a_4, \\
            q_2 & =a_1a_3a_4, \\
            q_3 & =a_1a_2a_4, \\
            q_4 & =a_1a_2a_3,
          \end{align*}
          and $\q = (q_1,q_2,q_3,q_4)$. Then assume indirectly that there is some $\t=(t_1,t_2,t_3,t_4)\neq\s$ for which
          $$\q\cdot\s=\q\cdot\t,$$
          or equivalently,
          $$0=q_1(s_1-t_1)+q_2(s_2-t_2)+q_3(s_3-t_3)+q_4(s_4-t_4).$$
          Since $a_1$ divides the last three terms and 0, $a_1$ must also divide $q_1(s_1-t_1)$; $a_1$ does not divide $q_1$, so $a_1$ divides $s_1-t_1$. Because $s_1$ and $t_1$ are positive integers, $$s_1-t_1< s_1.$$ Since $a_1>s_1$ in order to have that $a_1|s_1-t_1$, it must be that $t_1\geq s_1$. Similarly, $t_2\geq s_2$, $t_3\geq s_3$, and $t_4\geq s_4$. Then since $\s\neq\t$ we know that one of these inequalities is strict. Thus,
          $$q_1(s_1-t_1)+q_2(s_2-t_2)+q_3(s_3-t_3)+q_4(s_4-t_4)<0,$$
          a contradiction.
        \end{proof}

\end{enumerate}

\section*{Conclusion}
Perhaps you are surprised with the results in the previous section (6 was most surprising to me), but hopefully you can see the large differences that quantification make in the truth of a statement, as well as the change in caliber of proof needed to keep up with the variation. Clearly, this is a difficult topic to teach budding mathematicians.

Now, are we sure we aren't missing any combinations of quantifier chains in our lineup?







%----------------------------------------------------------------------------------------
%  BIBLIOGRAPHY
%----------------------------------------------------------------------------------------

% \printbibliography[title={Bibliography}] % Print the bibliography, section title in curly brackets

%----------------------------------------------------------------------------------------

\end{document}