11
$\begingroup$

So I recently stumbled upon this beautiful problem:

Show that the number $r_2(n)$ of representations of $n$ as a sum of two squares (of not neccesarily positive integers) has $\pi$ as its arithmetic mean, that is $$ \lim_{n\rightarrow \infty }\frac{1}{n}\sum_{i=0}^n r_2(i) = \pi$$

Now the proof remarks that every point of the unit two dimensional integer lattice $(x, y)$ is the solution to the equation $x^2+y^2=n$ for some $n$, and then if we look at all the lattice point satisfyting $x^2+y^2 \leq n$ we can bound this quantity by the area of a circle (with radius about $\sqrt{n}$), and thus gain the result. (This is a rough idea of the proof, it is by no means precise)

Now we can extend this to the function $r_k(n)$ that counts the number of ways to express $n$ as the sum of $k$ squares. Now we simply take the $k$ dimensional lattice and bound it by $k$-spheres, and gain the average as the $k$-volume of the unit $k$-sphere. This quantity is given by: $$\frac{\pi^{\frac{k}{2}}}{\Gamma(1+\frac{k}{2})}$$ where $\Gamma(n)$ is the gamma function.

Now what is interesting about this is that the average tends to zero as the dimension grows to infinity. On the other hand, it is well known that any natural number can be expressed as the sum of four squares.

Now since our definition of $r_k(n)$ counts all the ways to gain $n$, including those that allow $0^2$ as one of the summands (I assume this is true since in our lattice-counting proof we include all latice points, including those that have one or more coordinates zero), then it would be the case that solutions obtained for smaller dimension be valid in higher dimension as well (simply by setting on of the coordinates to zero). So we would expect that every number can be expressed in atleast one way for all $k\geq4$, meaning $r_k(n)\geq1$ for all $n$.

However, this would mean that the average should be atleast one for all higher dimensions, but this contradicts that the volume goes to zero. Why is this? Is there some intuitive explanation?

I have a sense that the infinite nature of the average is probably in some way misleading and my usual intuition that can be applied to finite averages. I have tried thinking of the limit also as an asymptotic bound of $\sum r_k(n)$ in terms of $c\cdot n$, but that doesnt help either. There is also a possibility that there is some flaw in my proof (well, idea of proof as it is presented here). Maybe it is not the volume that I should be looking at?

$\endgroup$
  • 1
    $\begingroup$ Hmm. Do you mean to say $$\frac{1}{n}\sum_{i=1}^{n} r_2(i)$$? $\endgroup$ – Frpzzd Jul 13 '17 at 21:43
  • 2
    $\begingroup$ Note in the $k$ case you divide by $n^{k/2}$ to reduce the problem to a unit sphere, not just $n$. For $k>2$, this makes a large difference to the asymptotics! (Think about the problem in one dimension: how many ways are there of representing the numbers smaller than $n$ in terms of one square? The number of squares less than $n$, which is about $\sqrt{n}$.) $\endgroup$ – Chappers Jul 13 '17 at 22:34
  • $\begingroup$ @Nilknarf Yes, correct. (Note that $i=0$ and $i=1$ doesnt make much of a difference in the average since there is always exactly one way to represent 0) $\endgroup$ – cirpis Jul 14 '17 at 0:53
  • $\begingroup$ @Chappers I guess I see what you mean, but I dont think it epxplains why for large $k$ we have on average almost no ways of expressing a number as a sum of squares, if there is always atleast one way of doing so $\endgroup$ – cirpis Jul 14 '17 at 0:54
  • 1
    $\begingroup$ @Chappers I think that's an answer to the question - for an 'average' you should just be dividing by $n$ rather than by a power of it; making that change makes the asymptotics line up much more with what OP would expect. $\endgroup$ – Steven Stadnicki Jul 14 '17 at 0:55
6
$\begingroup$

Let's call $c_{n,k}$ the number of lattice points contained 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}$$

But then, then calling $r_k(i)$ the of ways of writing the number $i$ as a sum of $k$ squares, 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? There can be indeed an paradox here, that we can state in simpler terms - refering just to the count of enclosed lattice points.

If we trust the formula $(1)$ above, we get $$\lim_{k \to \infty} c_{n,k}= 0 \tag{3}$$

On the other hand, $c_{n,k}$ should increase with $k$, because the $k+1$ dimensional lattice points include those of dimension $k$. That is, you 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, $(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$.

enter image description here

$\endgroup$
  • $\begingroup$ Thank you for the nice answer, both illuminating the error in my argument for higher dimensions AND at the same time explaining why the approximation breaks down and gives a contradiction if we look at fixed $n$. The article in the linked mathoverflow page also brings some insight. $\endgroup$ – cirpis Jul 14 '17 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.