Average number of ways to express number as a sum of $n$ squares goes to zero, why?

Solution 1:

Let $c_{n,k}$ bee the number of lattice points inside an hypersphere of radius $n$ and dimension $k$. Then, using the volume of the sphere, we get the approximation:

$$ c_{n,k} \approx n^{k/2} \frac{\pi^{\frac{k}{2}}}{\Gamma(1+\frac{k}{2})} \tag{1}$$

Let $r_k(i)$ be the number of ways of writing the number $i$ as a sum of $k$ squares. Then, your average is:

$$ \frac{1}{n}\sum_{i=0}^n r_k(i) =\frac1n c_{n,k} \approx \ n^{k/2-1} \frac{\pi^{\frac{k}{2}}}{\Gamma(1+\frac{k}{2})} \tag{2}$$

For $k=2$ this gives a constant ($\pi$). But for any other fixed $k>2$ it grows towards infinity as $n\to \infty$. Hence there is no paradox here.

But, you might ask: what if we fix some (large) $n$, and make $k$ grow? Indeed, there is some kind of paradox here, that we can state in simpler terms, considering just the number of enclosed lattice points:

Looking at the formula $(1)$ above, we could deduce $$\lim_{k \to \infty} c_{n,k}= 0 \tag{3}$$

But this does not make sense. $c_{n,k}$ should increase with $k$, because the $k+1$ dimensional lattice points include those of dimension $k$. That is, we must have

$$c_{n,k+1} > c_{n,k} \tag{4} $$

But $(3)$ and $(4)$ cannot be both true.

The problem is that formula $(1)$ is an approximation, which is valid only for large $n$ ... where "large" depends on $k$. If we keep $n$ fixed and increase $k$ indefinitely, then most of the points of the grid fall near the border of the sphere (curse of dimensionality), and the approximation turns useless (some details here).

Hence, the limit $(3)$ is definitely wrong.

Indeed, we can check that the RHS of $(1)$ starts decreasing (and hence is being grossly inaccurate) around $k=2\pi n$. Here's a chart of the exact and approximate values (both sides of eq. $(1)$, logarithmic scale) for $n=10$.