second.tex

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

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


\usepackage{draftwatermark}
\usepackage{tcolorbox}

\usepackage{todonotes}


\usepackage{enumerate}

%----------------------------------------------------------------------------------------
%  ARTICLE INFORMATION
%----------------------------------------------------------------------------------------
\title{Secrets and Quantifiers} % The article title


\author{
  \authorstyle{B\'ela Bajnok and Peter E. 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




\renewcommand\thesubsubsection{\arabic{subsubsection}}





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

\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}}

\begin{picture}(0,0)
  \put(280,88){\hbox{\missingfigure[figwidth=2.7in, figheight=3in]{}}}
\end{picture}



\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!

Let's start with the basics.

% $\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*{Some Notations}

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 and type 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}.$$

% It is a neat artifact of this notation 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).$$


\section*{The Game}

Here is the game. Imagine someone has a secret sequence of four positive integers that we would like to know. We are allowed to ask questions also in the form of sequences of positive integers, to which their response will be the scalar product (the sum of the coordinate-wise product) of the two sequences, denoted by $(\ \cdot\ )$.
If their secret sequence is $\s=(s_1,s_2,s_3,s_4)$, the response to the question $\q=(q_1,q_2,q_3,q_4)$ is
$$\q\cdot\s  = q_1s_1+q_2s_2 + q_3s_3+ q_4s_4.$$
Our goal is to discover their sequence in as few questions as possible. Let's play!

Suppose they have a sequence $(s_1,s_2,s_3,s_4)$ in mind. We ask the question
$$\q=(1,2,3,4),$$
to which their response is
$$\q\cdot\s=1\cdot s_1+2\cdot s_2 + 3 \cdot s_3+ 4 \cdot s_4=70.$$
Is there any information at all that we can get out of the answer?

Yes! We know that none of $s_1$, $s_2$, $s_3$, or $s_4$ can be bigger than $70$, so each integer has at most two digits. We then cleverly ask the question
$$(10^6,10^4,10^2,1),$$
and they respond with
$$10^6\cdot s_1+10^4\cdot s_2 + 10^2 \cdot s_3+ 1 \cdot s_4=20301008.$$
Looking at the digits of the response, you can deduce that my secret sequence was $(2,3,10,8)$.

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

It is exciting that with two questions, we can always discover the secret. However, you might be wondering if there is a more efficient method, a winning strategy with only one question.

This is clearly the case, for example, if we ask the question $(1,5,10,20)$, and the answer is 36: the secret had to be $(1,1,1,1)$. We can see this is true because if \$1, \$5, \$10, and \$20 bills are used to pay \$36, there is just one way to do it so at least each currency is used at least once. The situation is the same if the answer is 37, 38, 39 or 40; however the answer 41 may come from the secret $(6,1,1,1)$ or $(1,2,1,1)$. So, we see that for any question we may have a ``happy accident'' and decode the unique secret, but it is unclear whether for any secret sequence there exits a question that can decode it.


% Clearly, if we first ask the question $(1,1,1,1)$ and receive a response of $4$, then we know that the secret sequence is also $(1,1,1,1)$, so we know that winning the game with one question is possible. There are plenty of other examples of these ``happy accidents,'' or in other words, \textit{there exist some secrets for which there exists a single question that can reveal them}.

% One way to visualize these examples is with combinations of currency: a response to the question $(1,5,10,20)$ can be seen as a linear combination of \$1, \$5, \$10, and \$20 bills. Therefore, if we get a response of $36$, we know that the secret sequence is $(1,1,1,1)$, since there is only one way to make \$36 with \$1, \$5, \$10, and \$20 bills (one of each). Similarly, a response of 37 would imply that the secret sequence is $(2,1,1,1)$.

This seems more tangible, but 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$ different from $\s$ for which $$\q\cdot\s=\q\cdot\t,$$
or equivalently, for all $\t$ different from $\s$,
$$\q\cdot\t\neq\q\cdot\s.$$
In quantifier notation,
$$\forall\t, \t\neq\s \implies \q\cdot\t\neq\q\cdot\s.$$
% Equivalently,
% $$\q\cdot\t=\q\cdot\s\implies \t=\s.$$

For example, our earlier sentence, \textit{there exist some secrets for which there exists a single question that can reveal them}, can be written
$$\exists\s,\exists\q,D(\q,\s).$$
So now we can talk about a one-question method more carefully: is there a question sequence that can decode any secret sequence? In quantifier notation, is
$$\exists\q,\forall\s,D(\q,\s)$$
true?

\section*{Mixing Up Quantifiers}

Now you might see why this game is so interesting. We can make quite a few similar sounding statements that are really quite different, just by changing the order and type of the quantifiers. We explore three of these variations below with some `real world' scenarios, and attempt to determine their truth. Namely,

\begin{itemize}
  \item[$($1$)$] $\exists\q,\forall\s,D(\q,\s)$
  \item[$($2$)$] $\exists\s,\forall\q,D(\q,\s)$
  \item[$($3$)$] $\forall\s,\exists\q,D(\q,\s)$
\end{itemize}

Before doing so, attempt to determine the truth of each of these claims but do not get discouraged; two require only relatively simple explanations while one is more involved to prove.

\begin{figure}[h!]
  \centering
  \missingfigure[figwidth=3.2in, figheight=3in]{Picture of a key}
\end{figure}

\subsubsection{The Master Key}
The first quantifier chain
$$\exists\q,\forall\s,D(\q,\s)$$
can be read ``There is some fixed question that can decode any secret.''

We can understand this situation if we think of question sequences as keys and secret sequences as locks; $D(\q,\s)$ can be interpreted as key $\q$ opening lock $\s$. The metaphor continues: the statement above is interpreted as that there is some key that can open any lock. Is this true?

No it is not. Let's prove it!
We must show that no matter what question we ask, there are two secret sequences that would return the same response:
$$\forall\q, \exists\s, \exists \t, \t\neq\s,\q\cdot\s=\q\cdot\t.$$

\begin{tcolorbox}
  \begin{proof} Given any $\q = (q_1,q_2,q_3,q_4)$, let\\
    $\s=(1,1,1+q_4,1)$ \ \ and\ \ $\t=(1,1,1,1+q_3)$. Then
    \begin{align*}
      \q\cdot\s & = q_1+q_2+q_3(1+q_4)+q_4        \\
                & = q_1 + q_2 + q_3 + q_4 +q_3q_4 \\
                & = q_1+q_2+q_3+q_4(1+q_3)        \\
                & = \q\cdot\t.
    \end{align*}
  \end{proof}
\end{tcolorbox}

So, any question $(q_1,q_2,q_3,q_4)$ will not be able to distinguish between the secret sequences $(1+q_2,1,1,1)$ and $(1,1+q_1,1,1)$. In other words, if we thought we had a `master key' (a key that could open any lock), we would be wrong because there are always at least two locks that it cannot open.



\subsubsection{The Inn on the Mountain}
The second quantifier chain
$$\exists\s,\forall\q,D(\q,\s)$$
can be read ``There is some secret that can be decoded by any question.''

Continue the lock analogy from the previous section and imagine an inn up on a cold mountain. Wanting to save on heat, the owner keeps the door closed, but chooses a lock so that anyone who makes it up the mountain is allowed to come in; any key the traveler brings will open the door. So is it possible to model this story with our sequences?

Yes! If the owner's lock were the sequence
$$(1,1,1,1),$$
any key sequence would unlock the inn: the response to any question is simply the sum of the terms in the question and the only secret sequence that would produce such a response is $(1,1,1,1)$.

Here is a more formal proof.

\begin{tcolorbox}
  \begin{proof}
    Let $\s=(1,1,1,1)$ and suppose that
    $$\t=(t_1,t_2,t_3,t_4)\neq\s.$$
    Then for all $\q=(q_1,q_2,q_3,q_4)$,
    $$\t\cdot\q>q_1+q_2+q_3+q_4=\q\cdot\s.$$
  \end{proof}
\end{tcolorbox}



\begin{figure}[h!]
  \centering
  \missingfigure[figwidth=3.2in, figheight=4in]{Picture of an inn}
\end{figure}






\subsubsection{The Unbreakable Secret}
The third quantifier chain
$$\forall\s,\exists\q,D(\q,\s)$$
can be read ``For any secret, we can pick a question to decode it.''

Notice how at first glance, this sentence sounds very similar to the `master key' sentence. Here is evidence that a small change in quantifiers can make a big difference in meaning. While (1) is false, (3) happens to be true.

As we will soon see, there does not exist a fixed secret that can not be decoded by a lucky guess. There is no `unbreakable secret'!

This fact is not trivial to prove and strays furthest from the original game in concept. For that reason, it is important to ground ourselves in the definitions that we have agreed upon. Below we prove that $\forall\s,\exists\q,D(\q,\s)$.

\begin{tcolorbox}
  \begin{proof}
    Let $\s=(s_1,s_2,s_3,s_4)$ be an arbitrary sequence and 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)$. We will show that $\q$ decodes $\s$. Then assume  that there is some $\t=(t_1,t_2,t_3,t_4)$ 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$ is relatively prime to $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 by our choice that $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 in the above equation, four nonnegative terms sum to zero, so each is equal to zero, but that means $\s=\t$.
    %           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{tcolorbox}


\begin{figure}[h!]
  \centering
  \missingfigure[figwidth=3.2in, figheight=4in]{Picture of an unbreakable secret}
\end{figure}



\section*{Conclusion}
Perhaps you are surprised with the results in the previous section (3 was most surprising to us), 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 there any missing combinations of quantifier chains in our lineup?


\vspace{1em}

\hrule

% \subsubsection*{B\'ela Bajnok}

% B\'ela Bajnok earned his first PhD from Eotvos University (in Budapest, Hungary) in 1984, and his second from Ohio State University in 1989. B\'ela has taught at Gettysburg College since 1993 and has publications in a wide range of areas, including additive combinatorics, spherical geometry, lattice theory, extremal graph theory, approximation theory, and statistics. He is on the Board of the Budapest Semesters in Mathematics, a member of the Mathematical Association of America Textbook Series Committee, a former associate editor of Math Horizons, and a former director of the International Mathematical Talent Search.
% B\'ela is the 2013 winner of Gettysburg College’s Excellence in Teaching Award, and the 2012 winner of the Distinguished College or University Teaching Award of the EPaDel Section of the Mathematical Association of America.









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

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

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

\end{document}