# at least $a\sqrt{n}$ solutions

Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed.

Consider a number $0<a<2\pi$. How can we show that there is an infinite amount of integers $n$ such that

$x^2 + y^2 + z^2=n$

has at least $a\sqrt{n}$ integer solutions?

I apologize for not editing in the boldened bit earlier.

-
I note the elliptic-curves tag. Do you know for a fact that this has something to do with elliptic curves? – Gerry Myerson Oct 7 '12 at 22:57
Hah, no. That was an accident. Fixed. – Ali Oct 8 '12 at 1:39
Why do you believe this to be true? – marty cohen Oct 8 '12 at 3:06
A teacher of mine mentioned this as a joking challenge some weeks ago, and I don't think anyone gave it second thought. I looked at it and tried to liken the problem to a sphere, but it did not yield a good result. And then I asked the teacher in question, and he said he'd forgotten the proof! Thought I'd try my luck here. – Ali Oct 8 '12 at 15:05
This is part of the high school research program MIT PRIMES's application: See mit.edu/primes/materials/2013/entpro13.pdf, problem M2. It states, "You are allowed to use any resources to solve these problems, except other people's help." – only Oct 27 '12 at 17:23

Assuming that $a$ and $b$ are fixed and that $x^2+y^2+z^2 = n$ has $\le a \sqrt{n}+b$ integer solutions for all $n$, we get that the number of integer solutions of $x^2+y^2+z^2 < n$ is bounded above by $$\sum_{k=0}^{n-1} (a \sqrt{k}+b) = bn+ an^{3/2}\sum_{k=0}^{n-1} \sqrt{\frac{k}n} \frac1n \le bn+ a n^{3/2} \int_0^1 \sqrt{x} \, dx = bn+\frac{2an^{3/2}}{3},$$ since the second sum is a lower Riemann sum for the integral of $\sqrt{x}$ over $[0,1]$.

Now since the volume of the ball with radius $\sqrt{n}$ is $\frac{4\pi n^{3/2}}3$, and the number of integer solutions of $x^2+y^2+z^2 <n$ has the same asymptotic growth, we get that $\frac{2a}3 \ge \frac{4\pi}3$, i.e., $a \ge 2\pi$.

Lastly, if there are only finitely many $n$ such that $x^2+y^2+z^2 = n$ has $\ge a\sqrt{n}$ integer solutions, it is straightforward that there exists $b$ such that $x^2+y^2+z^2 = n$ has $\le a\sqrt{n}+b$ integer solutions for all $n$.

-
I am a little confused, how exactly does the solution not fit the edited version? What kind of edits would you like? – Lukas Geyer Oct 11 '12 at 4:57
Seems I did not read it properly last night. Thank you. – Ali Oct 11 '12 at 12:44

The number of triples $(x,y,z)$ with $x^2+y^2+z^2\le n$ is roughly the volume of a sphere of radius $\sqrt n$, which is $(4/3)\pi n^{3/2}$. So there must exist $n$ with at least $(4/3)\pi\sqrt n$ solutions to $x^2+y^2+z^2=n$. That's not what you want, but it's a start, and maybe a refinement of this argument gets you where you want to go.

EDIT: Let's try to refine the argument. Given a positive integer $m$, consider the triples with $m/2\le x^2+y^2+z^2\lt m$. The number of such triples is the volume of the region between the spheres of radius $\sqrt{m/2}$ and $\sqrt m$ (plus terms of lower order), and that's $${4\over3}\pi\Bigl(1-{\sqrt2\over4}\Bigr)m^{3/2}$$ Since we're talking about $m/2$ different integer values, (at least) one of those values must occur (at least) $(8/3)\pi(1-(\sqrt2/4))\sqrt m$ times. That's about $1.72\pi\sqrt m$, still not quite the $2\pi$ you want. Might be worth looking at a thinner shell.

-
If you replace $m/2$ by $cm$, where $c$ is less than $1$, the equivalent bound becomes $$\frac{ \frac{4}{3} \pi (1-c^{3/2}) m^{3/2}}{(1-c) m} = \frac{4(1-c^{3/2})}{3(1-c)} \pi \sqrt{m}.$$ As $c$ approaches $1$, the fraction approaches $2$. So it seems like the "thinner shell" would work. – Kevin Costello Oct 11 '12 at 19:26
@Kevin, with 2 squares, we know where to look for numbers with many representations: they are products of many 1-mod-4 primes. It would be nice to be able to answer this question by pointing to numbers that have unusually many representations as sums of three squares. The record-holders are listed at oeis.org/A071609 but I don't see any patterns. – Gerry Myerson Oct 11 '12 at 23:04