10

Let $\mathbb{F}$ be a finite field. Let $a_1,\dots,a_n \in \mathbb{F}$ be given. I want to know whether there exists $x_1,\dots,x_n \in \mathbb{F}$ such that

$$a_1 x_1^2 + a_2 x_2^2 + \dots + a_n x_n^2 = 1.$$

My question: Can we characterize when this equation has a solution, i.e., by some criterion on $a_1,\dots,a_n$? Is there a clean characterization, in terms of $a_1,\dots,a_n$ and the properties of $\mathbb{F}$?

Here's what I can see immediately. First, if $n=1$, there is an easy answer (the equation has a solution iff $a_1$ is a square in $\mathbb{F}$). Second, if any $a_i$ is a square in $\mathbb{F}$, the equation has a solution (set all other $x_j$'s to $0$), so we can assume that all the $a_i$'s are non-squares and that $n \ge 2$. Third, if $-1$ is a square in $\mathbb{F}$, then the equation has a solution: we can take $x_2 = \sqrt{-a_1/a_2} \cdot x_1$. But what about the case where $-1$ is a non-square in $\mathbb{F}$? Is it always guaranteed to have a solution in this case?

D.W.
  • 4,540
  • 6
    If $n=2$, how many values does $a_1x_1^2$ take on? How about $1-a_2x_2^2$? What does that tell you? – Gerry Myerson Nov 19 '13 at 08:55
  • 1
    @GerryMyerson, ah-hah! Perfect. Hey, that's beautiful! Thank you! I will try to write up a detailed answer tomorrow for others, based upon this insight, in case it is helpful to others. Thank you again. (If you are curious, I ran across this in an application here: http://cstheory.stackexchange.com/q/19832/5038) – D.W. Nov 19 '13 at 08:57

1 Answers1

8

For $n\ge 2$, this equation always has a solution, assuming there exist at least two $a_i$'s that are non-zero. Consider the equation

$$a_1 x_1^2 + a_2 x_2^2 = 1.$$

This equation always has a solution for $x_1,x_2$. In particular, the set $S=\{a_1 x_1^2 : x_1 \in \mathbb{F}\}$ has size $|S|=(|\mathbb{F}|+1)/2$, since there are $(|\mathbb{F}|-1)/2$ non-zero squares in $\mathbb{F}$, plus one for zero. Similarly, letting $T=\{1-a_2 x_2^2 : x_2 \in \mathbb{F}\}$, we see that $|T|=(|\mathbb{F}|+1)/2$. Since $|S|+|T| > |\mathbb{F}|$, by the pigeonhole principle there must exist some common element in the intersection of $S \cap T$. This shows that there is guaranteed to exist a solution to the equation.

For $n>2$, we can simply set $x_3=x_4=\cdots=x_n=0$ and reduce it to the case considered above.

Many thanks to Gerry Myerson for the key insight.

D.W.
  • 4,540
  • 3
    Actually $|S| = \frac{|{\mathbb F}|+1}{2}$ only if the characteristic of ${\mathbb F}$ is not 2. When ${\mathbb F}$ has characteristic two, then $b^2 - a^2 = (b-a)^2$ (note that $-a=a$) and so $a^2 = b^2$ if and only if $a=b$. Thus $|S| = |{\mathbb F}|$ in this case. – Pablo Rotondo Nov 20 '13 at 00:27