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?

  • 4
    $\begingroup$ 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? $\endgroup$ – Gerry Myerson Nov 19 '13 at 8:55
  • 1
    $\begingroup$ @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: cstheory.stackexchange.com/q/19832/5038) $\endgroup$ – D.W. Nov 19 '13 at 8:57

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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Pablo Rotondo Nov 20 '13 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.