# Solution in distinct elements for a system of $n$ equations over finite fields

The following problem is motivated by pure curiosity; it is not a part of any research project and I do not have any applications.

Problem:

Let $\{y_1 , y_2 , \dots, y_n \}$ be arbitrary (distinct) elements of $\mathbb Z_p−\{0\}$, where $p \equiv 3 \pmod 4$. Now, for a given $p ≡ 3 \pmod 4$, what is the maximum $n$, so that the following system of $n$ equations over $\mathbb Z_p$ has at least one solution with the added restriction that $x_i \neq 0$ and $x_i \neq x_j$.

\begin{align*} x_{1}^2-x_{m}^2&\equiv y_{1}\pmod p,\\\\ x_{2}^2-x_{m}^2&\equiv y_{2}\pmod p,\\\\ \dots\\\\ x_{n}^2-x_{m}^2&\equiv y_{n}\pmod p\\\\ \end{align*}

Clarification: In a comment posted to the (initial) answer by Barry Cipra, the OP has rephrased the question as follows:

For a given a prime $p\equiv3 \pmod 4$, what is the largest $n$ such that for any choice of distinct elements $y_1,y_2,\dots,y_n$ of $\mathbb Z_p−\{0\}$, there exist at least one (fixed) nonzero quadratic residue, say $r$ such that $y_i+r$ is again a nonzero quadratic residue for all $1≤i≤n$. I have verified that for $p=7$ and $p=11$, the maximum $n$ is 1. Also, I verified that for $p=19$, the maximum $n$ is 2. The question is how to generalize this for a given $p$.

-
What is $m$?${}$ – Gerry Myerson Mar 12 '13 at 10:06
Dear Prof. Gerry Myerson, essentially, $x_m^2$ is a fixed quadratic residue and since $y_i′$s are distinct $x_i^2 \neq x_m^2$ for all $1 \leq i \leq n$. – Shivaraj Mar 12 '13 at 16:20
Your equations specialize to $x_m^2-x_m^2=y_m$ mod $p$, but you want $y_m$ nonzero mod $p$. So there are never any solutions. – John Pardon Mar 12 '13 at 17:16
No! I already mentioned that $x_i^2 \neq x_m^2$ for all $1 \leq i \leq n$. – Shivaraj Mar 13 '13 at 4:27
Given that there's no research project or applications involved, I think the problem could be posed for all primes, and not just primes congruent to 3 mod 4. – Barry Cipra Mar 13 '13 at 13:37

Are you sure you've posed the question correctly?

You see, sometimes you can't even solve for $x_1$. In particular, this happens if $y_1$ is such that $y_1 + {x_m}^2$ is a quadratic nonresidue. So there is no such maximum $n$; even when $n=1$ there exist situations where there is no solution. That can't be what you meant.

In an attempt to discover a version of the question with a more interesting answer, let's further suppose that the $y_i$ are chosen in such a way that $y_i + {x_m}^2$ are all quadratic residues. But this is boring for the opposite reason: you can always solve the system. Since you've forced all the $y_i$ to be distinct, then there is no obstruction to finding solutions until you run out of values of $y_i + {x_m}^2$ which are quadratic residues. The maximum $n$ where there's a solution is when you take $n$ to be the number of distinct nonzero quadratic residues mod $p$... I am still left with the sense that I haven't told you anything you didn't already know.

-

Added 3/13/13: The OP has confirmed, in comments, that my interpretation (beginning with the next paragraph) is basically correct, aside from relaxing the condition that the $x_i$s be nonzero. I've added some additional remarks at the bottom here (and corrected one minor mistake in the original answer).

I agree with Benjamin Young (and Gerry Myerson), the question does not seem to be correctly posed. Here is a possible interpretation, albeit one that drops, at least initially, the condition $x_i\ne0$.

Given a prime $p$ congruent to 3 mod 4, one can ask for the largest $n$ such that for any choice of distinct $y_1,y_2,\ldots,y_n$ with $y_1y_2\cdots y_n\ne0\mod p$, there is a square number $r$ (including the possibility $r=0$) such that $y_i+r$ is a square (mod $p$) for $1\le i\le n$.

The sought-for $n$ depends on $p$. It's immediately clear that $0\le n \le p-1$ for any prime $p$; for $p\equiv3\mod4$, it's easy to see that $1\le n$. That's because any $y_1\ne0$ is either a quadratic residue mod $p$, in which case you can let $r=0$, or it's a non-residue, in which case you can let $r=-y_1$, which is a quadratic residue (hence square).

For $p=3$, it's easy to see that $n=1$: The only pair at stake is $(y_1,y_2)=(1,2)$, for which adding $r=1$ gives $(2,0)$, which includes the non-square number 2. (Obviously, adding $r=0$ also leaves the non-square 2.)

For $p=7$, the result is also $n=1$, but it takes a bit more checking to see that $(y_1,y_2)=(2,3)$ is an obstruction: The quadratic residues mod 7 are 1, 2, and 4, but $(2,3)+1=(3,4)$, $(2,3)+2=(4,5)$, and $(2,3)+4 = (6,0)$, each of which contains a non-residue. (I hope the notation here is clear.) As it happens, $(y_1,y_2)=(1,5)$ and $(4,6)$ are also obstructions (for all other pairs, there is a square $r$ that makes each number square), but it only takes one.

For $p=11$, though, we do find that $n$ is at least 2. The squares mod 11 are 0, 1, 3, 4, 5, and 9, and one can check the completeness and correctness of the following list (which covers all pairs with at least one non-square entry):

\begin{align}(1,2)+3&=(4,5)\cr (1,6)+3&=(4,9)\cr (1,7)+2&=(3,9)\cr (1,8)+3&=(4,0)\cr (1,10)+2&=(3,1)\cr (2,3)+1&=(3,4)\cr (2,4)+1&=(3,5)\cr (2,5)+9&=(0,3)\cr (2,6)+3&=(5,9)\cr (2,7)+2&=(4,9)\cr (2,8)+1&=(3,9)\cr (2,9)+2&=(4,0)\cr (2,10)+2&=(4,1)\cr (3,6)+9&=(1,4)\cr (3,7)+9&=(1,5)\cr (3,8)+1&=(4,9)\cr (3,10)+1&=(4,0)\cr (4,6)+5&=(9,0)\cr (4,7)+5&=(9,1)\cr (4,8)+1&=(5,9)\cr (4,10)+5&=(9,4)\cr (5,6)+9&=(3,4)\cr (5,7)+9&=(3,5)\cr (5,8)+4&=(9,1)\cr (5,10)+4&=(9,3)\cr (6,7)+9&=(4,5)\cr (6,8)+3&=(9,0)\cr (6,9)+3&=(9,1)\cr (6,10)+5&=(0,4)\cr (7,8)+4&=(0,1)\cr (7,9)+5&=(1,3)\cr (7,10)+5&=(1,4)\cr (8,9)+3&=(0,1)\cr (8,10)+1&=(9,0)\cr (9,10)+5&=(3,4)\cr \end{align}

(Note: Several pairs allow more than one choice of $r$. In general I've used the smallest $r$ among 0, 1, 3, 4, 5, and 9, except that I've tried to avoid producing a 0 in the sum pair whenever possible. If there's a more sensible way to summarize all the checking, I'm all ears.)

Luckily, it's easy to show that $(1,2,7)$ is an obstruction to $n=3$ for $p=11$, so we can conclude that $n=2$ is the maximum in this case. What one gets for the largest $n$ when $p=19$, I'll leave for someone else to work on. I'll merely note that one might go ahead and reinstate the prohibition on using the square 0, but if you do, you get $n=0$ for $p=3$ and $n=1$ for $p=7$ and $11$. Whether you ever get anything larger is unclear.

Added 3/13/13: The "immediately clear" upper bound $n\le p-1$ came from the mindless observation that the $y_i$s are distinct and nonzero. The somewhat more thoughtful observation that the $(y_i+r)$s must all be distinct squares not equal to the square $r$ shows that $n\le (p-1)/2$. But we can do a lot better than that by working backwards: Start with distinct squares $r,s_1,s_2,\ldots,s_n$ and let $y_i=s_i-r$ for $1\le i\le n$. We have $(p+1)/2\choose n$ choices for the $s_i$s, leaving ${p+1\over2}-n$ choices for $r$, whereas there are $p-1\choose n$ choices for the $y_i$s, so the maximum $n$ must satisfy

$$({p+1\over2}-n){(p+1)/2\choose n} \ge {p-1\choose n}$$

For $p=7$, this is $(4-n){4\choose n} \ge {6\choose n}$, from which we see that $n=1$ is OK (as we already know) but $n=2$ is not, since $12 < 15$. (In fact this is how I caught an error in my original answer. I initially thought there were only two "obstructions" to $n=2$ for $p=7$, but this comparisons shows there must be at least three. I went back and realized that I had decided that adding 4 to the pair $(1,5)$ would produce a pair of squares, but of course $4+1=5$ is not a square mod 7. Note that for every other pair, there is exactly one value for $r$ that turns it into a pair of squares, since $15-12=3$.)

For $p=11$, the upper bound inequality is

$$(6-n){6\choose n}\ge {10\choose 2}$$

Doublechecking $n=2$, we have $60\ge 45$, but for $n=3$ we have

$$(6-3){6\choose 3} = 3\cdot20 = 60 < {10\choose3} = 120,$$

so we could have concluded that $n=2$ is the maximum for $p=11$ without bothering to look for the obstruction $(1,2,7)$.

For $p=19$, it's easy to check that $n=3$ satisfies the upper bound inequality but $n=4$ does not, so we can conclude that the maximum $n$ is between 1 and 3, but that's about all we can say without exhaustive checking.

A quicker, cruder upper bound comes from letting $s_1,s_2,\ldots,s_n,r$ range over all squares, including repetitions, and noting that this should account for all possible $y_i$s, including repetitions and 0s. One needs $({p+1\over2})^{n+1} \ge p^n$, or

$$n \le \log({p+1\over2})/\log({2p\over p+1})$$.

Finally, the OP really wants all the squares to be (non-zero) quadratic residues. This simply changes the upper bound inequality to

$$({p-1\over2}-n){(p-1)/2\choose n} \ge {p-1\choose n}.$$

This rules out $n=2$ for $p=11$ (since $(5-2){5\choose2} = 3\cdot10 = 30 < {10\choose2}=45$), but allows it for $p=19$, since $(9-2){9\choose2}=7\cdot36 = 252 > {18\choose2}=153$. It's easy to see that $n=3$ is ruled out for $p=19$. The OP claims (in comments) to have checked that $n=2$ actually is the maximum in this case.

-
Gerry, sorry, I'll bet you get tired of making that correction! – Barry Cipra Mar 12 '13 at 22:32
Thank you Prof. Gerry.\\ Now let me put the problem in the simple way: \\ For a given a prime $p\equiv3(mod\ 4)$, what is the largest $n$ such that for any choice of distinct elements $y_1,y_2,...,y_n$ of $Z_p−0$, there exist at least one (fixed) nonzero quadratic residue, say $r$ such that $y_i+r$ is again a nonzero quadratic residue for all $1≤i≤n$.\\ I have been verified that for $p=7$ and $p=11$, the maximum $n$ is 1. Also, I verified that for $p=19$, the maximum n is 2.\\ The question is how to generalize this for a given $p$. – Shivaraj Mar 13 '13 at 5:57
@Shivaraj, not that I want to hog the credit, but Gerry's contribution here was to correct the spelling of his name. ;-) – Barry Cipra Mar 13 '13 at 11:56
Barry, no worries, I never get tired of calling attention to myself. – Gerry Myerson Mar 13 '13 at 12:02
Gerry, as a journalist, I consider it very important to spell people's names correctly, so I'm always chagrinned on occasions when I don't. – Barry Cipra Mar 13 '13 at 12:43