main.tex

\documentclass[10.5pt]{article}

\usepackage[letter, top=.75in, bottom=.75in, left=.75in, right=.75in, marginparwidth=.5 in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
% \usepackage[document]{ragged2e}

\usepackage{hyperref, amsmath, amsthm, latexsym, amsfonts, enumerate, csquotes, multicol, fix-cm, color, soul, amssymb, graphicx}

\usepackage{mathpazo}

% \renewcommand{\baselinestretch}{.95}

% \usepackage{etoolbox}
% \newcommand{\zerodisplayskips}{%
%   \setlength{\abovedisplayskip}{3pt}%
%   \setlength{\belowdisplayskip}{3pt}%
%   \setlength{\abovedisplayshortskip}{3pt}%
%   \setlength{\belowdisplayshortskip}{3pt}}
% \appto{\normalsize}{\zerodisplayskips}
% \appto{\small}{\zerodisplayskips}
% \appto{\footnotesize}{\zerodisplayskips}

\setlength{\columnsep}{1cm}

\tolerance=1
\emergencystretch=\maxdimen
\hyphenpenalty=10000
\hbadness=10000

\newcommand{\s}{\mathbf{s}}
\newcommand{\q}{\mathbf{q}}
\renewcommand{\t}{\mathbf{t}}
\newcommand{\heading}[1]{\vspace{1em}\noindent\textbf{#1}\\\noindent}

\pagenumbering{gobble}



\begin{document}

\begin{center}
  \fontsize{42pt}{0pt}\selectfont
  Secrets and Quantifiers
\end{center}

\vspace{.25cm}

\begin{multicols}{2}

  \noindent\textsc{Peter E. Francis and B\'ela Bajnok}\\\\\noindent
  American writer, teacher, and comedian, Sam Levenson, gives us the following warning:

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

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

\heading{Some Notations}
  We will write $P(x)$ to denote a \textit{predicate}, 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 both false.

  The symbol $\forall$ represents the universal quantifier (pronounced ``for all''). Thus, the sentence $$\forall x\in A, P(x)$$ means ``for all $x$ in the set $A$, $P(x)$ is true.'' The symbol $\exists$ is the existential quantifier (pronounced ``there exists''). The sentence $$\exists x\in A, P(x)$$ means ``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. Sam Levenson's joke plays off the differences between the following two statements:
  $$\begin{cases}\forall\text{ time}, \exists\text{ place},\exists\text{ woman giving birth}, \text{ and}\\
  \exists\text{ place}, \exists\text{ woman},\forall\text{ time giving birth}.\end{cases}$$

\columnbreak

  \heading{A Secret Game}
  Imagine Suzy has a secret sequence of four positive integers that Quentin would like to know. He asks questions in the form of sequences of positive integers, to which Suzy's response will be the scalar product (the sum of the coordinate-wise product) of the two sequences: 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.
Quentin has an idea of how to ``brute force'' the secret sequence: Suzy has a sequence $(s_1,s_2,s_3,s_4)$ in mind and Quentin asks the four questions $(2, 1, 1, 1)$, $(1, 2, 1, 1)$, $(1, 1, 2, 1)$, and $(1, 1, 1, 2)$. Suzy responds with $w$, $x$, $y$, and $z$, respectively.
  These answers determine four equations, a linear system on the variables $s_1$, $s_2$, $s_3$, and $s_4$:
$$\begin{cases}
      w = 2s_1+s_2+s_3+s_4\\
      x = s_1+2s_2+s_3+s_4\\
      y = s_1+s_2+2s_3+s_4\\
      z = s_1+s_2+s_3+2s_4\\
    \end{cases}$$

Maybe Quentin has studied some Linear Algebra or maybe he was lucky, because it turns out that these four questions are \textit{linearly independent} and so will always determine a system of four equations with a unique solution:
$$\begin{cases}
    s_1 = \frac{4w-x-y-z}{5}\\
    s_2 = \frac{4x-w-y-z}{5}\\
    s_3 = \frac{4y-w-x-z}{5}\\
    s_4 = \frac{4z-w-x-y}{5}\\
  \end{cases}$$
This relies on the fact that any sequence of four \textit{real} numbers can be written as a linear combination of Quentin's four questions.
%   Since we are working with sequences of four integers, four questions are necessary for this brute-force method.

  It is exciting (at least for Quentin) that with four questions, he can always discover the secret. However, you might be wondering: can Quentin do better? Are fewer questions sufficient? This possibility takes a bit more to unpack.

  We can think of some secrets where single questions decode them. For example, if Quentin asks the question $(1,5,10,20)$ and Suzy answers 36, the secret must be $(1,1,1,1)$: there is only one way to use \$1, \$5, \$10, and \$20 bills to pay \$36 so that each currency is used at least once. The situation is the same if Suzy answers 37, 38, 39, or 40; however, if Suzy answers 41, her secret could be $(6,1,1,1)$ or $(1,2,1,1)$. So, we see that we may have a `happy accident' in asking our question. To go further, we will need to be more technical with what we mean by `decoding the secret with one question.’


  \heading{Decoding Sequences}
  Let $D(\q,\s)$ denote the predicate ``the question $\q$ decodes the secret $\s$''. In order to decode the secret with one question, you must ensure that no other secret sequence returns the same response for the 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.$$
  Equivalently in quantifier notation,
  $$\underbrace{\forall\t,}_\text{for all $\t$}\ \underbrace{\t\neq\s,}_\text{different from $\s$}\  \q\cdot\t\neq\q\cdot\s.$$
But is a single question \textit{always} enough?  The answer depends largely on the interpretation of this question. There are two ways to make our question precise:
  \begin{enumerate}[1.]
    \itemsep-0.05em
    \item Is ``$\exists\q,\forall\s,D(\q,\s)$'' true?
    \item Is ``$\forall\s,\exists\q,D(\q,\s)$'' true?
  \end{enumerate}

  We will decipher the meaning of these two questions and determine their truth. Our examination will expose that the order of the quantifiers results in two rather different outcomes.


  \heading{The Master Key}
  The first quantifier chain ``$\exists\q,\forall\s,D(\q,\s)$'' means ``there is some fixed question that can decode any secret.'' We can understand this situation by thinking of questions as keys and secrets as locks; the predicate $D(\q,\s)$ can be interpreted as ``key $\q$ opens lock $\s$.''

  Continuing the metaphor, the statement above means ``there is some key that can open any lock.'' In the context of the game, if this were true, Quentin would always win by asking the same one question; the game would be quite boring. Is this true?
  Let $\q = (q_1,q_2,q_3,q_4)$ be an arbitrary question. Define $\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(1+q_3)\\
              & = \q\cdot\t.
  \end{align*}
Thus, given a question, we can build at least two sequences between which the question cannot distinguish. In other words, if we thought we had a `master key' (one that could open any lock), we would be wrong because we showed how to build at least two locks that the key cannot open.

  \columnbreak

  \heading{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'': there is no secret safe from being decoded in one question. At first glance, this sentence sounds quite 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. Let's see why.

  Suppose that $\s=(s_1,s_2,s_3,s_4)$ is an arbitrary sequence.
Pick four pairwise relatively prime positive integers $a_1$, $a_2$, $a_3$, and $a_4$ (that is, four integers with no common prime factors) greater than $s_1$, $s_2$, $s_3$, and $s_4$, respectively. Then 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 claim $\q$ decodes $\s$. To show this, assume there is some sequence $\t=(t_1,t_2,t_3,t_4)$ with $\q\cdot\s=\q\cdot\t$. Then we have
    $$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 summands and 0, $a_1$ must also divide $q_1(s_1-t_1)$. As $a_1$ is relatively prime to $q_1$ (by design), $a_1$ must divide $s_1-t_1$. Because $s_1$ and $t_1$ are positive integers, we conclude $s_1-t_1 < s_1$. We chose $a_1>s_1$, so $a_1$ dividing $s_1-t_1$ implies $t_1\geq s_1$. Similarly, $t_2\geq s_2$, $t_3\geq s_3$, and $t_4\geq s_4$. As the above equation shows four nonpositive integers sum to 0, we conclude that each summand must be 0, so $s_i=t_i$ for each $i$. Thus, $\s=\t$. There is no `unbreakable secret’!


  \heading{The Solution}
  These two examples classify major differences that quantification makes in the truth of a statement, as well as the change in caliber of proof needed to keep up with seemingly small variations to sentence structure.

  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!


As we have seen, Quentin can always find the secret with four questions, but not necessarily with one. However, it turns out that two questions are always sufficient. Can you prove it?

  \vfill
  \hrule
  \vfill

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

  \vfill

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


\end{multicols}





\end{document}










%   Perhaps you are surprised with the results in the previous two sections; clearly, budding mathematicians must be careful when thinking about quantifiers.







%   Suppose . 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.