Secret Sequences

Introduction

Ria has a secret sequence $\mathbf{s}=(s_1,s_2,s_3,s_4)\in\mathbb{N}^4$ that Nate wants to know. Nate is allowed to ask questions in the form of sequences $\mathbf{q}=(q_1,q_2,q_3,q_4)\in\mathbb{N}^4$, to which Ria will reply $$s_1q_1+s_2q_2+s_3q_3+s_4q_4.$$

We can treat the sequences in $\mathbb{N}^4$ as vectors, so Ria's response can also be written as $\mathbf{s}\cdot\mathbf{q}$, where $\cdot$ is the dot product.

We would like to prove the following statement false:

Note: all sequences are in $\mathbb{N}^4$.

Interpretations

What we mean by "decode" is that given $\mathbf{q}$ and $\mathbf{s}\cdot\mathbf{q}$, Nate should be able to uniquely determine $\mathbf{s}$; that is, for all $\mathbf{t}$, with $\mathbf{s}\neq\mathbf{t}$, we have $\mathbf{q}\cdot\mathbf{s}\neq\mathbf{q}\cdot\mathbf{t}$. In shorter notation, $$\forall\mathbf{t}\neq\mathbf{s}\implies\mathbf{s}\cdot\mathbf{q}\neq\mathbf{t}\cdot\mathbf{q}$$

Let $D(\mathbf{q},\mathbf{s})$ denote the predicate that $\mathbf{q}$ can "decode" $\mathbf{s}$.

Now we have two interpretations of the above statement:

1. (The "magic question" interpretation) There is some fixed question $\mathbf{q}$ that can decode any secret $\mathbf{s}$. The quantifier chain is $$\exists\mathbf{q},\forall\mathbf{s}\, D(\mathbf{q},\mathbf{s}).$$

2. (The "luck" interpretation) For any secret $\mathbf{s}$, there is some question $\mathbf{q}$ that can decode $\mathbf{s}$. The quantifier chain is $$\forall\mathbf{s},\exists\mathbf{q}, D(\mathbf{q},\mathbf{s}).$$

Combinations of Quantifiers

The two interpretations suggest that similar quantifier chains will be interesting.

1. $\exists\mathbf{q},\exists\mathbf{s},D(\mathbf{q},\mathbf{s})$ is True.

"There is some question that can decode some secret."

Proof: The question $\mathbf{q}=(1,1,1,1)$ decodes the secret sequence $\mathbf{s}=(1,1,1,1)$.

$\square$

2. $\forall\mathbf{q},\forall\mathbf{s},D(\mathbf{q},\mathbf{s})$ is False.

"Every question decodes every secret." is False.

Proof: We must show that $$\exists\mathbf{q}, \exists\mathbf{s}, \exists \mathbf{t}\neq\mathbf{s},\mathbf{q}\cdot\mathbf{s}=\mathbf{q}\cdot\mathbf{t}.$$ Take $\mathbf{q}=(1,1,1,1)$, $\mathbf{s}=(2,1,1,1)$, and $\mathbf{t}=(1,2,1,1)$. Then $$\mathbf{q}\cdot\mathbf{s} = 2+1+1+1=\mathbf{q}\cdot \mathbf{t}.$$

$\square$

3. $\forall\mathbf{q},\exists\mathbf{s},D(\mathbf{q},\mathbf{s})$ is True.

"It is possible to ask any question and sometimes decode the secret," is True.

Proof: Given any question $\mathbf{q}=(q_1,q_2,q_3,q_4)$, let $\mathbf{s}=(1,1,1,1),$ and suppose indirectly that there is some $\mathbf{t}=(t_1,t_2,t_3,t_4)\neq\mathbf{s}$ for which $$q_1+q_2+q_3+q_4=\mathbf{q}\cdot\mathbf{s}=\mathbf{q}\cdot\mathbf{t}=q_1t_1+q_2t_2+q_3t_3+q_4t_4.$$ If any $t_i>1$, then $\mathbf{q}\cdot\mathbf{t}>\mathbf{q}\cdot\mathbf{s}$, so $t_1=t_2=t_3=t_4=1$, contradicting that $\mathbf{s}\neq\mathbf{t}$.

$\square$

4. $\exists\mathbf{s},\forall\mathbf{q},D(\mathbf{q},\mathbf{s})$ is True.

"There is some secret that can be decoded by any question," is True.

Proof: Let $\mathbf{s}=(1,1,1,1),$ and similarly to (3), for all $\mathbf{q}=(q_1,q_2,q_3,q_4)$, there is no $\mathbf{t}\neq\mathbf{s}$ for which $$q_1+q_2+q_3+q_4=\mathbf{q}\cdot\mathbf{s}=\mathbf{q}\cdot\mathbf{t}=t_1q_1+t_2q_2+t_3q_3+t_4q_4.$$

$\square$

5. $\exists\mathbf{q},\forall\mathbf{s},D(\mathbf{q},\mathbf{s})$ is False.

"There is some fixed question that can decode any secret," is False.

Proof: We must show that $$\forall\mathbf{q}, \exists\mathbf{s}, \exists \mathbf{t}\neq\mathbf{s},\mathbf{q}\cdot\mathbf{s}=\mathbf{q}\cdot\mathbf{t}.$$

Well, given any $\mathbf{q} = (q_1,q_2,q_3,q_4)$, let $\mathbf{s}=(1+q_2,1,1,1)$ and $\mathbf{t}=(1,1+q_1,1,1)$. Then $$\mathbf{q}\cdot\mathbf{s} = q_1(1+q_2)+q_2+q_3+q_4 = q_1+q_2(1+q_1)+q_3+q_4=\mathbf{q}\cdot\mathbf{t}.$$

$\square$

6. $\forall\mathbf{s},\exists\mathbf{q},D(\mathbf{q},\mathbf{s})$

``For any secret, we can pick a question to decode it''

Proof: Let $\mathbf{s}=(s_1,s_2,s_3,s_4)$. Pick $a_1,a_2,a_3,a_4\in\N$, pairwise relatively prime, and $a_i>s_j$. Let $$q_1=a_2a_3a_4$$ $$q_2=a_1a_3a_4$$ $$q_3=a_1a_2a_4$$ $$q_4=a_1a_2a_3.$$ Then assume indirectly that there is some $\mathbf{t}\in\N^4$ for which $$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, $a_1$ must divide $q_1(s_1-t_1)$. Since $a_1$ does not divide $a_1$, divides $s_1-t_1$. Since $s_1$ and $t_1$ are positive integers, $s_1-t_1< s_1$; since $a_1>s_1$ and $a_1|s_1-t_1$, we must have that $t_1\geq s_1$. Similarly, $t_2\geq s_2$, $t_3\geq s_3$, and $t_4\geq s_4$. Then we have that $$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.

$\square$