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.



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$?
$\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](https://oeis.org/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.$$


