Number of solutions of $x^2_1+\dots+x^2_n=0,$ $x_i\in \Bbb{F}_q.$

Question

Let $\mathbb F$ be field with $q$ element and $\operatorname{char}(\mathbb F)\neq2$. I want to know about the number of solutions of this equation:

$$x^2_1+x^2_2+\dots+x^2_n=0 \text{ where } x_i\in \mathbb F.$$

Any suggestion?

Answer 1

Partial answer that works, when $q\equiv1\pmod4$. This is a minor simplification to the use of recurrences as described in the first sentence of Gerry Myerson's answer (that I somehow missed as my gaze was drawn to the character sums :/). For the cases $q\equiv-1\pmod4$ I recommend doing it his way.

---

When $q\equiv1\pmod4$ we know that the field contains a primitive fourth root of unity, call it $i$. Let $A(n)$ be the number of solutions for the equation in $n$ variables. We know (see also comment's by Gerry Myerson) that $A(1)=1$ and $A(2)=2q-1$.

We can write $$x_1^2+x_2^2=(x_1+ix_2)(x_1-ix_2)=z_1z_2,$$ where $z_1=x_1+ix_2$ and $z_2=x_1-ix_2$. The mapping $(x_1,x_2)\mapsto(z_1,z_2)$ is clearly a bijection, so $A(n)$ is equal to the number of solutions of $$ z_1z_2=-(x_3^2+x_4^2+\cdots+x_n^2). $$ Here the r.h.s. is equal to zero for exactly $A(n-2)$ vectors $(x_3,x_4,\ldots,x_n)$, so that gives us $(2q-1)A(n-2)$ solutions. OTOH, if the r.h.s. is non-zero, we can let $z_2$ be any non-zero element ($(q-1)$ choices), and can then uniquely solve for $z_1$. This gives us $(q-1)(q^{n-2}-A(n-2))$ solutions. Altogether we get a recurrence relation $$ A(n)=(2q-1)A(n-2)+(q-1)\left(q^{n-2}-A(n-2)\right)=(q-1)q^{n-2}+qA(n-2). $$

It is easy to prove by induction on $n$ that this has the solution $$ A(2k+1)=q^{2k} $$ for odd values of $n=2k+1$, and $$ A(2k)=q^{2k-1}+q^k-q^{k-1} $$ for even values of $n=2k$.

Answer 2

Let $A_n$ be an abbreviation for $x_1^2+x_2^2+\cdots+x_n^2$. Let $a_n$ be the number of solutions of $A_n=0$, let $b_n$ be the number of solutions of $A_n=-1$, and let $c_n$ be the number of solutions of $A_n=c$, where $-c$ is some fixed nonsquare in the field. Find a system of recurrences involving $a_n$, $b_n$, and $c_n$, and solve.

Alternatively, use exponential sums. This is easiest to do when $q$ is prime. $$\sum_{x_1}\sum_{x_2}\cdots\sum_{x_n}\sum_te^{2\pi it(x_1^2+x_2^2+\cdots+x_n^2)/p}$$ gives $p$ times the number of solutions, where the sums are over all $x_1,x_2,\dots,x_n,t$ in the field. Bring the sum on $t$ to the front, separate out the term with $t=0$ to get $$p^n+\sum_{t=1}^{p-1}\sum_{x_1}\sum_{x_2}\cdots\sum_{x_n}e^{2\pi it(x_1^2+x_2^2+\cdots+x_n^2)/p}=p^n+\sum_{t=1}^{p-1}\left(\sum_xe^{2\pi itx^2/p}\right)^n$$ The sum on the inside is a quadratic Gauss sum whose value is recorded in many texts and on many websites.

Similar methods apply when $q=p^r$, $r\gt1$, but I disremember the trick.

Note the problem $x_1^2+x_2^2+\cdots+x_n^2=1$ (over the field of $p$ elements) is done in detail in Ireland and Rosen, A Classical Introduction to Modern Number Theory, Chapter 8, Section 6, pages 101-102. $x_1^2+x_2^2+\cdots+x_n^2=0$ is left as Exercise 19 in that chapter. The tools for extending the results to finite fields more generally are developed in Chapter 10.

Answer 3

Another way to get a recursion is by first noting that, whether or not $\sqrt{-1}$ lies in the ground field $\mathbb F_q$, every element of $\mathbb F_q$ is representable as $x^2+y^2$: when there is a $\sqrt{-1}$, this factors, and, when there is no $\sqrt{-1}$, this is the norm from the quadratic extension $\mathbb F_{q^2}$, which is surjective.

To hit $0$, there is a unique solution of $x^2+y^2=0$ without $\sqrt{-1}$, while there are $2q-1$ solutions with $\sqrt{-1}$. For non-zero values $z$, there are $q-1$ solutions of $x^2+y^2=z$ with $\sqrt{-1}$, and $q+1$ without.

Thus, there are two families of cases, depending on presence or absence of $\sqrt{-1}$, and incorporating whether one is hitting $0$ or not. That is, looking at $x^2+y^2=1-(x_3^2+\ldots+x_n^2)$, treat the cases that the right-hand side is $0$, or not, etc.

Answer 4

I'll try to answer this in a self-contained manner - I will repeat ideas by Paul and Gerry but it will be more detailed. I'll restrict myself to $q = p$ (a prime), but the same arguments are valid in the general case.

We'll generalize, because the problem calls for it: you want to count solutions to $\sum_{i=1}^{n} x_i^2 = 0$ - why not understand the distribution of $f(x_1,\cdots,x_n) = \sum_{i=1}^{n} x_i^2$, i.e. how many times each value in $\mathbb{F}_{p}$ appears in the multiset $\{ f(\vec{x}) | \vec{x} \in \mathbb{F}_{p}^{n} \}$.

This problem is a convolution problem - let $v$ be the vector that counts solutions to $x^2 = i$ - its i'th coordinate is the number of square roots of $i$ in $\mathbb{F}_{p}$. If we convolve $v$ with itself $n$ times, you'll get the distribution of our function $f$, and you need the 0'th coordinate: $\underbrace{v * \cdots * v}_\textrm{n times}$.

You can approach this via Fourier Transform (so-called "Gauss sums"), since Fourier turns convolution into pointwise multiplication which is easier, but we can avoid that.

The key step is noting that $v*v$ is almost constant - it has a certain value on 0, and another value on all $\mathbb{F}_{p}^{\times}$. Why is that?

1. If $p \equiv 1 (4)$, there's a square root of -1 in $\mathbb{F}_{p}$, call it $i$. Then the equation $x^2 + y^2 = j$ is equivalent to $(x+iy)(x-iy) = j$. We can make the substitution $x+iy=t, x-iy=s$ (since $char(F) \neq 2$) and this turns to $st = j$. If $j=0$ there are $2p-1$ solution, else - there are $p-1$ solutions ($(s,js^{-1})$).

2. If $p \equiv 3 (4)$, there's no square root of -1 living in our field, but we can construct a quadratic extension of our field, which will contain it - $i \in \mathbb{F}_{p}[x]/(x^2+1) \cong \mathbb{F}_{p^2}$ (as there's a unique quadratic extension of any finite field). The equation $x^2 + y^2 = j$ becomes : $$x^2 + y^2 = (x+iy)(x-iy) = (x+iy)^{p+1} = j$$ because $x-iy$ is the conjugate of $x+iy$, and Frobenius Automorphism $t \to t^p$ takes elements to their conjugates. (Since it's linear, you can just verify $1^p = 1, i^p = -i$). We can write this equation as $t^{p+1} = j$ where $j \in \mathbb{F}_{p}, t \in \mathbb{F}_{p^2}$. Note that $\mathbb{F}_{p} = (\mathbb{F}_{p^2})^{p+1}$ (one inclusion follows since for $t \neq 0$, $(t^{p+1})^{p-1} = t^{p^2 - 1} = 1$, so $t^{p+1} \in \mathbb{F}_{p}$). Since $(\mathbb{F}_{p^2})^{\times}$ is cyclic, for $j \neq 0$ this reduces to the equation $$(p+1)x \equiv (p+1)a (\mod p^2-1)$$ which has $p+1$ solutions in $\mathbb{Z}/(p^2-1)\mathbb{Z}$. For $j=0$, this clearly has one solution - $t=0$, i.e. $x=y=0$.

So $v*v$ is nice - as a function of $i$, it depends only on whether $i =0$ or not.

Now, a nice exercise: Let $u = (a,\underbrace{b, \cdots , b}_\textrm{p-1 times})$. $v = (c,\underbrace{d, \cdots , d}_\textrm{p-1 times})$. Then $u*v = (e,\underbrace{f, \cdots , f}_\textrm{p-1 times})$, where $(e-f) = (a-b)(c-d)$ and $e + (p-1)f = (a + (p-1)b)(c + (p-1)d)$. If $a=c, b=d$, we get: $(e-f)=(a-b)^2, e+(p-1)f = (a+(p-1)b)^2$. This is where the Fourier aspect is hidden - convolution of vectors multiplies the frequencies.

We're really close.

1. If $n$ is even, then $\underbrace{v * \cdots * v}_\textrm{n times} = \underbrace{(v * v) * \cdots * (v*v)}_\textrm{n/2 times}$, and this is easy by the exercise - if we apply the exercise $\frac{n}{2}$ times, our final vector $w$ will be of the form $(a,\underbrace{b, \cdots , b}_\textrm{p-1 times})$, where $a-b = \begin{cases} \ ((2p-1) - (p-1))^{n/2} &\text{if } p \equiv 1 \pmod{4}\\ ((p+1) - (1))^{n/2} & \text{if } p\equiv 3 \pmod{4} \end{cases} $ and $a+b(p-1) = (p^2)^{n/2}=p^n$. Solving these 2 equation gives $a$, which is the number you're seeking.

2. If $n$ is odd, we first calculate $\underbrace{v * \cdots * v}_\textrm{n-1 times}$ similarly to the first case. Then we need to convolve $(a,\underbrace{b, \cdots , b}_\textrm{p-1 times})$ with $v$, which turns out to be a relatively easy problem: the i'th coordinate will be $(a-b)v_i + pb$ (do it yourself). For $i=0$, $v_i = 1$ and the answer is $a-b+pb = (p-1)b+a$.

So there are 4 cases, depending on whether $i \in \mathbb{F}_{p}$ ($p \equiv 1(4)$) and on the parity of $n$.

Answer 5

Let $F$ be a field of characteristic $\operatorname{char}F \ne 2$. Let's denote by $S_n(a)$ the set $\{(x_1, \ldots, x_n) \in F^n \ | \ \sum_{i=1}^n x_i^2 = a\}$. We have the stereographic parametrization of the sphere $S_n(1)$ by he map
$$F^{n-1} \ni x \mapsto \left(\frac{x}{1+|x|^2}, \frac{1-|x|^2}{1+|x|^2}\right)\in S_n(1)$$ with inverse $$S_n(1) \ni (x', x_n) \mapsto \frac{x'}{1+x_n}\in F^{n-1}$$ We get in this way a bijection between $S_n(1) \backslash S_{n-1}(0)$ and $F^{n-1} \backslash S_{n-1}(-1)$. Assume now $F$ finite, $|F|=q$. If we write $s_n(a) = \# S_n(a)$ we get $$s_n(1) - s_{n-1}(0) = q^{n-1} - s_{n-1}(-1)$$

Note that we also have $$s_n(-1)= \frac{ s_{n+1}(0) - s_n(0)}{q-1}$$

Case 1. $-1$ is a square in $F$, that is $q\equiv 1 \pmod 4$. We conclude $s_n(1) = s_n(-1)$, and from above we get $$\frac{s_{n+1}-s_n(0)}{q-1} = q^{n-1}+ s_{n-1}(0) - \frac{s_{n}(0)-s_{n-1}(0)}{q-1}$$ or $$s_{n+1} (0)-q^n = q \,(s_{n-1}(0)-q^{n-2})$$

Case 2. $-1$ is not a square, that is $q\equiv -1 \pmod 4$.

Looking at the fibres of the map $F^n \ni (x_1, \ldots, x_n) \mapsto \sum_{i=1}^n x_i^2 \in F$, we get $$q^n = s_(0) + \frac{q-1}{2} s_n(1) + \frac{q-1}{2} s_n(-1)$$

With some calculations we get $$(s_{n+1}(0) - q^n) = -q \,( s_{n-1}(0) - q^{n-2})$$

So for arbitrary odd $q$ we have

$$\bbox[5px,border:2px solid red]{ s_{n+1}(0)- q^n = (-1)^{\frac{q-1}{2}} q\,(s_{n-1}(0)-q^{n-2}) }$$

Some conclusions:

if $n$ is odd then $s_n(0) = q^{n-1}$. This follows easily by induction, noting that $s_1(0) = 1$.

To get all of $s_n(0)$ from the recurrence above we also need $s_2(0)$. If $-1$ is not a square we get $s_2(0) = 1$. If $-1$ Is a square, then the equation $x_1^2 + x_2^2= 0$ can be transformed into $y_1^2 - y_2^2 = 0$, which has $2q-1$ solutions. So, in general we have

$$s_2(0)-q = (-1)^{\frac{q-1}{2}}(q-1)$$

the formulas $s_3(0)$ and $s_4(0)$ do not depend on the parity of $\frac{q-1}{2}$. This can be seen from the formulas, or by noting that the projective variety $x^2 + y^2 - z^2 = 0$ is isomorphic to $\mathbb{P}_1$, while $x^2 + y^2 - z^2 - t^2=0$ is isomorphic to $\mathbb{P}_1\times \mathbb{P}_1$.

Answer 6

Let $A$ be a finite abelian group, $A^{\star}$ the group of characters of $A$. We have $$\sum_{\lambda \in A^{\star}} \lambda(x) = \begin{cases} |A| &\textrm{ if } x = 0 \\ 0 &\textrm{ if } x \ne 0 \end{cases}$$

Let $X$ be a finite set, $f\colon X\to A$ a function. Then we have the counting formula $$\#\{ x \in X \ | \ f(x) = 0\} = \frac{1}{|A|}\sum_{ \lambda \in A^{\star},{x \in X}}\lambda(f(x))$$

A particular case is $X= X_1 \times \cdots \times X_n$, $f\colon X\to A$, $f(x_1, \ldots, x_n) = \sum_{i=1}^n f_i(x_i)$. We have $$\#\{ x \in X \ | \ \sum_{i=1}^n f_i(x_i) = 0\} = \frac{1}{|A|}\sum_{ \lambda \in A^{\star},x \in X}\lambda(\sum_{i=1}^n f_i(x_i))= \\ =\frac{1}{|A|} \sum_{\lambda \in A^{\star} } \prod_{i=1}^n \sum_{x_i \in X_i} \lambda(f_i(x_i))$$

Now consider $A=F$ a finite field of odd order $q$, $X= F^n$, and $f(x_1, \ldots, x_n) = \sum_{i=1}^n d_i x_i^2$, where $d_i \in F^{\times}$.

Now from the above we have to understand sums of form $$\sum_{x\in F} \lambda( a x^2) $$ where $\lambda$ is a character of $F$, $a \in F^{\star}$. If $\lambda$ is the trivial character the sum equals $q$. Assume now $\lambda$ nontrivial.

Lemma: Let $\phi\colon F \to B$, where $B$ is an abelian group, and $\sum_{x\in F} \phi(x)=0$. Then $$\sum_{x\in F} \phi(x^2)= \sum \mu(x) \phi(x)$$ where $\mu$ is the quadratic character $\mu\colon F \to \{-1,0,1\}\subset \mathbb{C}$. The proof is immediate. We conclude: $$\sum_{x\in F} \lambda( a x^2)= \sum_{x\in F} \mu(x) \lambda( a x) = \mu(a)\cdot \sum_{x\in F} \mu(x) \lambda(x)$$

We are now ready to calculate with the formula above. Fix $\lambda$ a nontrivial character of $F$.Then all of the characters of $F$ are $\lambda_a(x) = \lambda(a x)$, for $a \in F$. The term corresponding to $\lambda_a$, with $a=0$ ( the trivial character) equals $q^n$. The term corresponding to $\lambda_a$, $a \in F^{\star}$ equals

$$\prod_{i=1}^n \sum_{x\in X} \lambda( a d_i x^2) = \mu(a)^n \mu(d_1 \cdots d_n) (\sum_{x\in X} \mu(x) \lambda(x))^n$$

We get

$$\#\{(x_1, \ldots, x_n)\in F^n \ | \sum_{i=1}^n d_i x_i^2 = 0\} = q^{n-1} +\\ + \frac{1}{q}(\sum_{a \in F^{\times} }\mu^n(a)) \mu(d_1 \cdots d_n) (\sum_{x\in F} \mu(x) \lambda(x) )^n$$

If $n$ is odd, we have $\mu^n = \mu$, a nontrivial character of $F^{\times}$, so $\sum_{a \in F^{\times}} \mu^n(a) = 0$. We conclude that the number of solutions of $\sum d_i x_i^2 = 0$ equals $q^{n-1}$.

Assume now $n$ is even. We get

$$\# \{ x, Q(x) = 0\} = q^{n-1} + \frac{q-1}{q} \mu(\det Q) S^{n}$$ where $$S = \sum_{x\in F} \mu(x) \lambda(x)$$ is a quadratic Gauss sum. Note that if $\lambda$ is changed to $\lambda_a$, the sum gets multiplied by $\mu(a)$, so $S$ is not determined, but $S^2$ is.

Now, we'll get $S^2$ by estimating $$\# \{ x_1^2 + x_2^2 = 0\}$$

If $-1$ is not a quadratic residue there is only one solution $(0,0)$. We get

$$1 = q + \frac{q-1}{q} S^2$$ so $S^2 = - q$

If $-1$ is a quadratic residue, we have $2q-1$ solutions ( of form $(x, \pm \sqrt{-1} x)$) so $$2q-1 = q + \frac{q-1}{q} S^2$$ and we conclude $S^2 = q$.

Therefore, we have $S^2 = \mu(-1) q$. We can plug this value in the formula for nondegenerate quadratic forms in an even number of variables.

The value $\mu(\det Q)$ is the only invariant of a nondegenerated quadratic form in a given number of variables. This can be seen by noticing that the forms $\epsilon (x_1^2 + x_2^2)$ and $x_1^2 + x_2^2$ are isomorphic.

We ignored the case of quadratic forms over fields of characteristic $2$.

$\bf{Added:}$

The general formula : let $Q$ a non-degenerate quadratic form over the field $F= \mathbb{F}_q$ in $n$ variables. Then we have

1. $$\bbox[5px,border:2px solid green]{ \# \{ x\in \mathbb{F}_q^n \ | \ Q(x) = 0\} = q^{n-1} }$$ if $n$ is odd

2. $$\bbox[5px,border:2px solid green]{\# \{ x\in \mathbb{F}_q^n \ | \ Q(x) = 0\} = q^{n-1} + \frac{q-1}{q}\cdot \mu(\det Q) \cdot (\mu(-1) q)^{\frac{n}{2}} }$$ if $n$ is even

where $\mu(\cdot)$ is the quadratic multiplicative character of the field, $1$ on squares and $-1$ on non-squares.

---

Suppose we want to calculate the number of solutions of the equation

$$Q(x_1, \ldots, x_n) + a_{n+1} = 0$$ where $Q$ is non-degenerate, and $a_{n+1} \ne 0$. This can be done using the previous results. Indeed, calculate the number of solutions for $Q(x) + a_{n+1} x_{n+1}^2 = 0$, substract from this the number of solutions for which we have $x_{n+1} = 0$, and get the number of solutions where $x_{n+1} \ne 0$. This equals $(q-1) \times$ number of solutions for which $x_{n+1} = 1$, which is the desired number.