Sum of many squares modulo $n$

Question

Let $n$ be a positive integer and $0 \leq i < n$. Define $$ N(i) = \# \left\{ (x_1,\dots, x_s) \in [1, n]^s: x_1^2 +\dots + x_s^2 \equiv i \mod n \right\}. $$ I am looking for a reference for the following result: if $s$ is large enough, $$ n^{s-1} \ll N(i) \ll n^{s-1} $$ is true for all $i$ and $n$. Could anyone provide a reference for this result? Thank you! Any input also appreciated.

Answer 1

The estimate is false for $s\leq 4$, but it is true for $s\geq 5$. For example, if $s=3$ and $8\mid n$ and $i=7$, then $N(i)=0$. Or if $s=4$ and $n=4^k$ and $i=0$, then $N(i)\leq n^2$. For $s\geq 5$ the result follows easily from the fact that the number of ways to write a positive integer $m$ as a sum of $s$ squares is $\asymp_s m^{s/2-1}$. For more details, see Vaughan's book "The Hardy-Littlewood method".

Added. Here are some additional details. From the mentioned bound $$r_s(m):=\#\{ x_1,\ldots,x_s \in \mathbb{Z}: x_1^2+\ldots + x_s^2 = m\} \asymp_s m^{s/2 - 1},$$ it follows that \begin{align*} N(i)&\leq\sum_{k=1}^{sn+1} r_s(kn-n+i)\ll_s \sum_{k=1}^{sn+1}(kn)^{s/2-1}\ll_s n^{s-1},\\ N(i)&\geq\sum_{k=1}^{n} r_s(kn-n+i)\gg_s \sum_{k=1}^{n}(kn)^{s/2-1}\gg_s n^{s-1}. \end{align*}

Answer 2

For simplicity, I will focus on odd $n$ only. I will prove the following estimate:

Claim: Uniformly for $s \ge 5$ and odd $n$ we have $N(i) = n^{s-1} (1+O(p^{1-\frac{s}{2}}))$ where $p$ is the smallest prime dividing $n$, and this is optimal if $i=0$ and $4\mid s$. We also have $N(i) \gg n^{s-1}$, uniformly in the same range. All implied constants are absolute.

But first, I want to elaborate on GH from MO's answer and Emil Jeřábek's proof in the comments.

1. Circle method: If one wants to count integer solutions to $x_1^2+ \ldots+x_s^2 = n$ (a special case of Waring's problem) then one can use the circle method, which for large enough $s$ relates this problem to the local problem of counting solutions to $x_1^2+\ldots+x_n^2 \equiv i \bmod n$ where $x_i$ are variables modulo $n$. So people have studied your $N(i)$ in this context (among other contexts). As GH from MO, in this case one can recover information about the local problem (estimating $N(i)$) from the global one.

2. Quadratic forms: You are counting solutions to $Q(x_1,\ldots,x_s)=i \bmod n$ for a (diagonal) quadratic form $Q$ defined over $\mathbb{Z}/n\mathbb{Z}$. Again, this is a well-studied problem, even for non-diagonal quadratic forms. (See e.g. Lidl-Niederreiter's "Finite Fields", Chapter 6.) By the Chinese remainder theorem, it is enough to consider $n$ a prime power (and I'll focus, as I said, only on odd prime powers), in the sense that if your function $N(i)$ will be denoted $N(i,n)$ to emphasize the dependence on $n$, then $N(i,n) = \prod_{p^k \mid \mid n} N(i,p^k)$. For odd primes, we have an easy method to lift points modulo $p^{k-1}$ to points modulo $p^k$, namely Hensel's lifting, so that $N(i,p^k) = N(i,p^{k-1})p^{s-1}$ (a modification of this relation is available also for $p=2$). The problem of computing $N(i,p)$ is classical. In this prime case, we in fact have close to square-root cancellation: $|N(i,p) - p^{s-1}| \le p^{\lceil (s-1)/2 \rceil}$ (precise formulas are available, but this inequality is essentially optimal). See Theorems 6.26 and 6.27 in the aforementioned book. This already solves your problem and proves my claim (it even has a slightly better exponent for $p$, compared to the claim, if $s$ is odd)! An application of the CRT shows $$\prod_{p^k \mid \mid n} \left(1 -p^{-\lfloor \frac{s-1}{2}\rfloor} \right) \le \frac{N(i)}{n^{s-1}} \le \prod_{p^k \mid \mid n} \left( 1 + p^{-\lfloor \frac{s-1}{2}\rfloor}\right)$$ and this is essentially optimal. If $s \ge 5$ then the upper bound is bounded by the absolute constant $\prod_{p}( 1 + 1/p^2)<\infty$ and the lower bounded is bounded from below by $\prod_{p}(1-1/p^2)>0$. If $s \le 4$ this still gives information but, as pointed out by GH, your required estimate is simple false for small $s$. Specifically, it is violated if you take $n$ to be a primorial $\prod_{p \le m}p$ and let $m \to \infty$. It does hold for certain choices of $n$, such as primes, as long as $s \ge 2$. More generally, you can restrict to $n$ with $\sum_{p \mid n}1/p = O(1)$ and then your claim will be true even for $2 \le s \le 4$.

3. I'll explain how to obtain the claimed estimate without using Lidl-Niederreiter. A standard way to compute $N(i)$ exactly is to use Fourier analysis on $\mathbb{Z}/n\mathbb{Z}$. (This is related to the random walk interpretation of Emil Jeřábek, and the group structure is useful because it gives simple expressions for the eigenvalues associated with the walk.) Let $e(x):=e^{2\pi i x}$. Then $$N(i) = \frac{1}{n} \sum_{a \bmod n} e\left(-\frac{ai}{n}\right) G(a,n)^s$$ where $G$ is the (generalized) quadratic Gauss sum $$G(a,n):=\sum_{x \bmod n} e\left( \frac{ax^2}{n}\right).$$ The main term comes from $a=0$ and is equal to $n^{s-1}$. It remains to bound the other terms. The absolute value of $G(a,n)$ is well understood. If $n$ is odd, we have $$\left|G(a,n)\right| = \sqrt{n \gcd(a,n)}.$$ Hence, by the triangle inequality, $$\left| N(i) - n^{s-1} \right| \le \frac{n^{\frac{s}{2}}}{n}\sum_{0 \not\equiv a \bmod n} \gcd(a,n)^s = \frac{n^{\frac{s}{2}}}{n} \sum_{\substack{d \mid n\\ d \neq n}} d^{\frac{s}{2}} \phi(n/d)$$ where $d$ stands for $\gcd(a,n)$ and $\phi(n/d)$ counts $a \bmod n$ that have $\gcd(a,n)=d$. If we sum over $e:=n/d$ instead of over $d$, we find that $$\left| N(i) - n^{s-1} \right| \le n^{s-1} f_{s}(n)$$ where $$f_{s}(n):= \sum_{\substack{e \mid n \\ e \neq 1}} \phi(e)e^{-\frac{s}{2}}.$$ (This inequality is an equality if $i=0$ and $s$ is divisible by $4$, because the only possible loss is when we applied the triangle inequality, but $G(a,n)/\sqrt{n \gcd(a,n)}$ is a power of $\sqrt{-1}$.) Once $s\ge 5$, we have the upper bound $$f_s(n) \le \sum_{e \ge p} e^{1-\frac{s}{2}} \ll p^{1-\frac{s}{2}}$$ where $p$ is the smallest prime divisor of $n$. This establishes the first part of the claim. To see that $N(i) \gg n^{s-1}$ for $s \ge 5$, observe that $f_{s}(n)$ is monotonic decreasing and $f_5(n) \le \zeta(3/2)/\zeta(5/2)-1\approx 0.94 < 1$.