third.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}}




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

Let's start with the basics.

\section*{Some Notations}

When discussing quantifiers at length it is useful to have a simple notation to save time and brain power. 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.''
\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 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}.$$


\section*{Quentin and Suzy}

Imagine Suzy has a secret sequence of four positive integers that Quentin would like to know. He is allowed to ask questions in the form of sequences of positive integers, to which her response will be the scalar product (the sum of the coordinate-wise product) of the two sequences, denoted by $(\ \cdot\ )$.
If Suzy's 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.$$
Quentin's goal is to discover the sequence in as few questions as possible. Here is how an interaction might play out:

Suppose Suzy has a sequence $(s_1,s_2,s_3,s_4)$ in mind. Quentin asks the question
$$\q=(1,2,3,4),$$
and Suzy responds with
$$\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 Quentin can get out of this answer?

Yes! He knows that none of $s_1$, $s_2$, $s_3$, or $s_4$ can be bigger than $70$, so each has at most two digits. He then cleverly asks the question
$$(10^6,10^4,10^2,1),$$
and Suzy responds with
$$10^6\cdot s_1+10^4\cdot s_2 + 10^2 \cdot s_3+ 1 \cdot s_4=2031008.$$
Looking at the digits of the response, he can correctly deduce that the secret sequence is $(2,3,10,8)$.

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

It is exciting (at least for Quentin) that with two questions, he can always discover the secret. However, you might be wondering: can Quentin do better? Is one question enough?

This possibility will take a little more work to unpack and understand. You might be able to think of some secrets and single questions that can decode them. For example, if Quentin asks the question $(1,5,10,20)$ and Suzy answers 36, the secret has to be $(1,1,1,1)$. We can see this is true because there is just one way to use \$1, \$5, \$10, and \$20 bills to pay \$36 so 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 we may have a ``happy accident,'' but to go any further, we will need to get a little more technical about what we mean by `decoding the secret with one question.’


\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.$$


% 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?


We can then use quantifiers to express the fact that, {\em sometimes}, a single question reveals the secret as

$$ \exists \s, \exists \q, D(q,s). $$

But is a single question {\em always} enough?  As we next discuss, the answer depends largely on how we interpret this question. Indeed, depending on what we mean, there are two ways to make our question precise:

\begin{itemize}
  \item[$($1$)$] $\exists\q,\forall\s,D(\q,\s)$
  \item[$($2$)$] $\forall\s,\exists\q,D(\q,\s)$
\end{itemize}
Below we will decipher what these two questions mean and determine if they are true or not. As we will see, just by changing the order of our quantifiers, we get two rather different outcomes.


% \section*{Mixing Up Quantifiers}

% Now you might see why our previous question is interesting: it shows the importance of quantifiers when making a statement. Just by changing the order and type of the quantifiers, we can make quite a few similar sounding phrases that are really quite different.

% So, how can we interpret the question? Here are two possible ways that sound deceptively similar when read aloud:

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

% Below, we will explore the truth of these two statements as well as attempt to distinguish them.



\section*{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.'' If this were true, it would be in Quentin's favor.

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 ``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 given question $(q_1,q_2,q_3,q_4)$ will not be able to distinguish between the secret sequences $ (1, 1, 1+q_4, 1) $ and $(1,1,1,1+q_3)$. 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.

Thus, statement (1) actually falls in favor of Suzy.


\section*{The Unbreakable Secret}
The second quantifier chain
$$\forall\s,\exists\q,D(\q,\s)$$
can be read ``For any secret, we can pick a question to decode it,'' meaning that there is no secret safe from being decoded in one question.

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

% As we will soon prove, 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.

\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$.
  \end{proof}
\end{tcolorbox}

As we just proved, there is no `unbreakable secret’!


\section*{Conclusion}
We see that Quentin and Suzy would, at least, have difficulty agreeing on an interpretation, for Quentin would prefer (2) and Suzy, (1).

Perhaps you are surprised with the results in the previous section; clearly, this is a difficult topic to teach budding mathematicians. We hope that we have classified the large difference that quantification makes in the truth of a statement, as well as the change in caliber of proof needed to keep up with the variation. At the very least, now if anyone tells you that they have a shirt for every day of the week, you can rightfully ask them how they manage to wash it!

\vfill
\vfill

\noindent\textbf{B\'ela Bajnok}\\
B\'ela Bajnok is a Professor of Mathematics at Gettysburg College and is the Director of the American Mathematics Competitions of the MAA.
\vfill

\noindent\textbf{Peter E. Francis}\\
Peter is an undergraduate Mathematics student at Gettysburg College.







\end{document}