What's the number of solutions of the quadratic equation $x_1^2+\dots+x_m^2=0$ over finite ring $\mathbb{Z}/p^n$?

Question

I want to calculate the number of solutions to the quadratic equation $$x_1^2+\dots+x_m^2=0$$ where $m$ is odd (a given number) and $x_i\in\mathbb{Z}/p^n$ for a given prime number $p$ and a given positive integer $n$.

I guess one can consider the projective variety over the $p$-adic field $\mathbb{Q}_p$ and count the point of some kind of projection but I didn't make it.

Answer 1

$\newcommand\Z{\mathbf{Z}}$Here's a solution for odd $p$ ($p=2$ seems to have specific complications), granted the case $n=1$.

Lemma 1: ($p$ odd) Let $u_n$ be the number of solutions of $\sum_{i=1}^mx_i^2=0$ in $\Z/p^n\Z$ such that $(x_1,\dots,x_m)$ is not $(0,\dots,0)$ mod $p$. Then, for $n\ge 1$, $u_n=p^{(n-1)(m-1)}u_1$.

Proof: it is enough to prove that $u_n=p^{m-1}u_{n-1}$ whenever $n\ge 2$, namely showing that every such solution mod $p^{n-1}$ has exactly $p^{m-1}$ lifts that are solutions mod $p^n$.

Let $(x_1,\dots,x_m)$ be a solution mod $p^{n-1}$, that is nonzero mod $p$. Lift it mod $p^n$, so we get $a_1,\dots,a_n$ in $\Z/p^n\Z$ such that $M:=\sum_{i=1}^ma_i^2$ belongs to $p^{n-1}\Z/p^n\Z$. The set of possible lifts of this solution mod $p^{n-1}$ is given by the $(a_1+p^{n-1}x_1,\dots,a_n+p^{n-1}x_n)$, for $x_i\in \Z/p\Z$ such that $\sum_{i=1}^m(a_i+p^{n-1}x_i)^2=0$ (in $\Z/p^n\Z$). This rewrites $M+2p^{n-1}\sum_{i=1}^m a_i x_i=0$. Write $-M/2=p^{n-1}M'$ (since $2$ is invertible mod $p^n$), with $M'\in\Z/p\Z$. Then this rewrites $\sum_{i=1}^{m} x_i a_i=M'$. This affine hyperplane in $(\Z/p\Z)^m$ has $p^{m-1}$ elements. Thus the given solution mod $p^{n-1}$ has exactly $p^{m-1}$ lifts that are solutions.$\Box$

Lemma 2: ($p$ odd). Let $v_n$ be the number of solutions of $\sum_{i=1}^mx_i^2=0$ in $\Z/p^n\Z$. Then $v_n=\sum_{0\le 2k<n}p^ku_{n-2k}+p^{m\lfloor n/2\rfloor}$.

Proof: first, for $k\ge n/2$, every $m$-tuple in $p^k\Z/p^n\Z$ is a solution. This yields the last term. Now consider another solution: for some unique $k<n/2$, it belongs to $(p^k\Z/p^n\Z)^m\smallsetminus (p^{k+1}\Z/p^n\Z)^m$. Write it $(p^kx_1,\dots,p^kx_m)$ with $(x_1,\dots,x_m)\in (\Z/p^{n-k}\Z)^m$ nonzero mod $p$. Then it is a solution if and only if $\sum_{i=1}^mx_i^2=0$ modulo $p^{n-2k}$. The number of such solutions mod $p^{n-2k}$, is thus, by Lemma 1, equal to $u_{n-2k}$, and all their lifts mod $p^{n-k}$ are the solutions, so there are $p^ku_{n-2k}$.$\Box$

Thus, writing $q=p^{m-1}$, $$v_{2n}=u_{2n}+pu_{2n-2}+\dots+p^{n-1}u_2+p^{nm}$$ $$=(q^{2n-1}+\dots +p^{n-2}q^3+p^{n-1}q)u_1+p^{nm}=q\frac{q^{2n}-p^n}{q^2-p}u_1+p^{nm},$$ $$v_{2n-1}=(q^{2n-2}+\dots +p^{n-2}q^2+p^{n-1})u_1+p^{m(n-1}=\frac{q^{2n}-p^n}{q^2-p}u_1+p^{m(n-1)}.$$

---

For $p=2$ it's a bit different. Let $w_n$ be the number of solutions (it also depends on $m$).

$n=1$ is obvious: the equation reduces to $\sum_{i=1}^m x_i=0$, which has $2^{m-1}$ solutions.

$n=2$: the number of solutions is $2^ma(m)$, where $a(m)=\sum_{0\le 4i\le m}\binom{m}{4i}$ counts the number of subsets of $\{1,\dots,m\}$ of cardinal in $4\Z$. This is an OEIS sequence: A038503.

In general, for $n\ge 2$ the set of solutions is invariant by addition by $2^{n-1}\Z/2^n\Z$, so we have $w_n=2^mw'_n$: here we can view $(x_1,\dots,x_m)\mapsto \sum_{i=1}^mx_i^2$ as a map $\Phi:(\Z/2^{n-1}\Z)^m\to\Z/2^n\Z$, and $w'_n$ is the cardinal of $\Phi^{-1}(\{0\})$. So $w'_2=a(m)$.

$n=3$: start from a solution in $(\Z/2\Z)^m$ of $\Phi=0_{\Z/4\Z}$, and lift it to $(a_1,\dots,a_m)\in (\Z/4\Z)^m$. We have to count the solutions of the form $(a_1+2x_1,\dots,a_m+2x_m)$, satisfying $\Phi=0$ mod 8. Writing $\sum a_i^2=4M$, this means the equality $\sum_i a_ix_i+x_i^2=M$ (this being mod 2). This yields a discussion. If some $a_i$ is zero mod 2, the set of solutions is a coset of a subgroup of index 2, so there are $2^{m-1}$ solutions.

If all $a_i$ are 1 mod 2, the value does not depend on the lift, and modulo 8, $\sum a_i^2$ is then equal to $m$. Hence this yields no solution if $m\notin 8\Z$, and $2^m$ solutions (in $\Z/4\Z$) if $m\in 8\Z$. Thus $w'_3=2^{m-1}w'_2$ if $m\notin 8\Z$, and $w'_3=2^{m-1}(w'_2-1)+2^m$ if $m\in 8\Z$.

$n=4$: start from a solution in $(\Z/4\Z)^m$ of $\Phi=0_{\Z/8\Z}$, and lift it to $(a_1,\dots,a_m)\in (\Z/8\Z)^m$. We have to count the solutions of the form $(a_1+4x_1,\dots,a_m+4x_m)$, satisfying $\Phi=0$ mod 16. Writing $\sum a_i^2=8M$, this means the equality $\sum_i a_ix_i=M$ (this being mod 2). This yields a discussion. If some $a_i$ is 1 mod 2, the set of solutions is a coset of a subgroup of index 2, so there are $2^{m-1}$ solutions.

If all $a_i$ are 0 mod 2, the value does not depend on the lift and we need another argument. We count the solutions $(2x_1,\dots,2x_m)$ with $x_i\in\Z/4\Z$. The equation is $4\sum_{i=1}^mx_i^2=0$ mod 16, that is, $\sum_{i=1}^mx_i^2=0$ mod 4. So there are $w_2$ such solutions.

We thus need to single out the remaining solutions in the $n=3$ case: those $0$ mod $2$ are the $(2x_1,\dots,2x_m)$, $x_i\in\Z/2\Z$ with $4\sum_{i=1}^mx_i^2=0$ mod $8$, that is, $\sum x_i=0$ mod $2$. There are $2^{m-1}$ such solutions, hence $w'_3-2^{m-1}$ other solutions.

Hence $w'_4=w_2+2^{m-1}(w'_3-2^{m-1})$.

$n\ge 4$: start from a solution in $(\Z/2^{n-2}\Z)^m$ of $\Phi=0_{\Z/2^{n-1}\Z}$, and lift it to $(a_1,\dots,a_m)\in (\Z/2^{n-1}\Z)^m$. We have to count the solutions of the form $(a_1+4x_1,\dots,a_m+4x_m)$, satisfying $\Phi=0$ mod 16. Writing $\sum a_i^2=8M$, this means the equality $\sum_i a_ix_i=M$ (this being mod 2). This yields a discussion. If some $a_i$ is 1 mod 2, the set of solutions is a coset of a subgroup of index 2, so there are $2^{m-1}$ solutions.

If all $a_i$ are 0 mod 2, the value does not depend on the lift and we need another argument. We count the solutions $(2x_1,\dots,2x_m)$ with $x_i\in\Z/4\Z$. The equation is $4\sum_{i=1}^mx_i^2=0$ mod 16, that is, $\sum_{i=1}^mx_i^2=0$ mod 4. So there are $w_2$ such solutions.

We thus need to single out the remaining solutions in the $n=3$ case: those $0$ mod $2$ are the $(2x_1,\dots,2x_m)$, $x_i\in\Z/2\Z$ with $4\sum_{i=1}^mx_i^2=0$ mod $8$, that is, $\sum x_i=0$ mod $2$. There are $2^{m-1}$ such solutions, hence $w'_3-2^{m-1}$ other solutions.

Hence $w'_4=w_2+2^{m-1}(w'_3-2^{m-1})$.

---

Edit: let me do $p=2$ in general. For the induction to work I need to consider $u_n$ as in odd $p$ case: those solutions that are not identically $0$ modulo $2$. Recall that $a(m)$ is the number of subsets of $[m]$ of cardinal in $4\Z$.

Then following the above argument, for $m\ge 1$,

• $u_1=2^{m-1}-1$;

• $u_2=2^m(a(m)-1)$;

• $u_3=2^{2m-1}(a(m)-1)$ if $m\notin 8\Z$, and $u_3=2^{2m-1}a(m)$ if $m\in 8\Z$;

• $u_n=2^{m-1}u_{n-1}$ for $n\ge 4$. Thus, for $n\ge 3$, $u_n=2^{(n-1)(m-1)+1}(a(m)-1)$ if $m\notin 8\Z$ or $n=2$, and $u_n=2^{(n-1)(m-1)+1}a(m)$ if $m\in 8\Z$.

Then, discussing the largest $k$ such that the solution is divisible by $2^k$, we get (if I computed correctly):

$$w_{n}=\sum_{0\le 2k<n}2^ku_{n-2k}+2^{m\lfloor n/2\rfloor}.$$ So for $m\notin 8\Z$, $$w_{2n}=2^m(a(m)-1)\frac{2^{(2m-2)n}-2^n}{2^{2m-2}-2}+2^{mn};$$ $$w_{2n+1}=(a(m)-1)2^{2m-1}\frac{2^{2(m-1)n}-2^n}{2^{2(m-1)}-2}+3.2^{n(m-1)}-2^n.$$

Answer 2

For what it's worth, if you want to investigate this more generally, let $f(x_1,\ldots,x_m)\in\mathbb Z[x_1,\ldots,x_m]$ be a homogeneous form of degree $d$, and let $$ N_n(f) = \Bigl(\text{# of solutions of } f(x_1,\ldots,x_m)\equiv0\pmod{p^n}\Bigr). $$ Then the Igusa zeta function of $f$ is (more-or-less) the generating function $$ Z(f,t) = \sum_{n=1}^\infty N_n(f) (t/p^m)^n . $$ A deep theorem of Igusa, with a subsequent alternative proof by Denef, say that $Z(f,t)$ is a rational function, but exact formulas are known in only a small number of cases. However, one case where a lot is known is "Fermat-type equations," i.e., diagonal equations, of which yours is the first interesting example.

Answer 3

Let $G$ be a cyclic group of order $N=p^n$, $g$ its generator. You ask for the constant term in the expression $(\sum_{k=0}^{N-1} g^{k^2})^m$ in the group ring, say, $\mathbb{C}[G]$. By roots of unity filter it equals $$ \frac1N\sum_{w^N=1} \left(\sum_{k=0}^{N-1} w^{k^2}\right)^m. $$ This reduces the question to quadratic Gauss sums which were computed by Gauss.

Let me concentrate on $N=2^n$ case which is more difficult and not covered by YCor's answer (UPDATE: already covered). Denote $w=\exp(a2^s\frac{2\pi i}{2^n})$ for $s=0,1,\ldots,n$ odd $a\in \{1,3,\ldots,2^{n-s}-1\}$. For $f(w):=\sum_{k=0}^{N-1} w^{k^2}$ we get $f(1)=N$ (this contributes to $s=n$ case, $f(-1)=0$ (this contributes to $s=n-1$ case), for $s\leqslant n-2$ we get $f(w)=2^sG(a,0,2^{n-s})$ in Wiki notation, and the formula gives $$G(a,0,2^{n-s})=(1+i)\varepsilon_a^{-1}\sqrt{2^{n-s}}\left(\frac{2^{n-s}}a\right).$$

It is not hard to sum up $m$-th powers of such guys for each fixed $s$. There are several similar cases in dependence on parity of $m$ and $n-s$.

1. $m=4k+2$. The sum over $a$ does vanish as $\varepsilon_a^2$ alternate.

2. $m=4k$. The sum over $a$ equals $(-4)^k2^{2k(n-s)}$.

3. $m$ is odd and $n-s$ is odd. The sum over $a$ does vanish as $\varepsilon_a^{-1}(\frac{2}a)$ takes teh values $\pm 1$, $\pm i$ equally often.

4. $m$ is odd and $n-s$ is even. The sum over $a$ equals $$ 2^{ms}(1+i)^m2^{n-s-2}(1+i^{-m})2^{(n-s)m/2}. $$

It remains to sum up over $s=0,1,\ldots,n-2$, the sum is a geometric progression in both non-trivial cases.