What is the smallest sphere whose surface includes 100 integer points?

Question

Let $S(r)$ be the surface of the origin-centered sphere in $\mathbb{R}^3$. A point is an integer point if all its coordinates are integers.

What is the smallest radius $r_n$ such that $S(r_n)$ includes $\ge n$ integer points?

What is the growth rate of $r_n$ with respect to $n$? Is there an algorithm that could compute $r_n$ for a specific given $n$?

It is known that rational points (all coordinates rational) are dense on $S(1)$: see, e.g., the MO question Rational points on a sphere in $\mathbb{R}^d$.

One possible approach is via rational points of bounded height. The height of a rational $a/b$ in lowest terms is max$(|a|,|b|)$, and the height of a rational point is the max of the heights of its coordinates.

---

         
          ^{Rationals of height $\le 2048$ on sphere. Image due to Stefan Kohl in this answer.}

---

Choose an appropriate $h_\max$, perhaps using an estimate of the number of rational points of height at most $h_\max$ on $S(1)$. Then scale all coordinates by the LCM of the points' denominators. For example, for $h_\max=10$, scaling by $2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$ would suffice to clear all denominators, so that $S(2520)$ includes all those points at integer coordinates.

But this would not necessarily result in the minimum $r_n$ for a given $n$. It would likely be better to use rational points that result in a small LCM.

Exact calculations on a sphere (for example, computing Voronoi diagrams on a sphere) often need integer points of bounded size.

---

Update. The exact answer to the question in the title, due to Dap and Gerhard Paseman, is that a sphere of radius $\sqrt{74} \approx 8.6$ includes $120$ integer points on its surface, and smaller spheres include fewer than $100$ points.

Answer 1

Here are a few facts about this problem, quoting mostly from Local statistics of lattice points on the sphere by Jean Bourgain, Peter Sarnak, Zeév Rudnick:

''A celebrated result of Legendre/Gauss asserts that $n$ is a sum of three squares if and only if $n\ne 4^a(8k+7)$. Let $$ N(n) = \bigl\{ (x,y,z)\in\mathbb Z^3 : x^2+y^2+z^2=n \bigr\}. $$ The behaviour of $N(n)$ is very subtle, and it was a fine achievement in the 1930’s when it was shown that $N(n)\to\infty$ as $n\to\infty$ through square-free values of $n$. It is known that $N(n)\ll n^{1/2+o(1)}$, and if there are primitive solutions, i.e., with $\gcd(x,y,z)=1$, which happens if and only if $n\not\equiv 0,4,7\pmod8$, then there is a lower bound $N(n)\gg n^{1/2-o(1)}$. This lower bound is ineffective and indicates that the behaviour of $N(n)$ is still far from being understood.''

Answer 2

Indeed I was thinking too linearly. If we change standard notation slightly, and call $r_3(n)$ the number of (unordered) representations of $n$ as a sum of three increasing and distinct squares, then a sphere with squared radius of $n$ and centered at the origin has at least $48r_3(n)$ integer lattice points on it. One also has contributions when two of the three squares are equal, or one or more of the squares is zero. We have $r_3(74)\geq 2$, as well as $74=49+25$, so this gives at least (and exactly) $120$ points on this sphere of radius less than 9. Thanks to Dap for finding a relevant OEIS sequence. I leave the growth rate of $r_3$ buried in the literature, but similar quantities such as (ordered) tuples counted by $r_4$ are well documented under sums of squares.

Gerhard "Then There Are Off-Origin Spheres" Paseman, 2018.01.30.

Answer 3

The sphere centred on $(1,1,1)/2$ and radius $\sqrt{131}/2\approx 5.723$ contains $24+48+48=120$ points with integer coordinates, thanks to $$2\{\pm x,\pm y,\pm z\}-(1,1,1)=\{9,5,5\},\{9,7,1\},\{11,3,1\}.$$

Successive best $a,n$ where the sphere centred on $(1,1,1)/2$ and radius $\sqrt{a}/2$ contains $n$ points with integer coordinates:

(3,8),(11,24),(27,32),(35,48),(59,72),(131,120),(251,168),(299,192),(419,216),(611,240),(659,264),(731,288),(899, 336),(971,360),(1091,408),(1691,432),(1739,480),(1811,552),(2219,576),(2651,624),(2939,696),(3251,744),(4091,792),( 4259,840),(4619,864),(5099,936),(5771,1056),(6971,1080),(7619,1104),(8291,1128),(8531,1200),(9539,1320),(11051,1488),( 12011,1560),(13859,1608),(14339,1680),(15539,1728),(18851,1776),(19211,1800),(19379,1944),(20459,1968),(22571,2088),( 25091,2112),(25451,2160),(26171,2184),(26771,2352),(28019,2376),(31379,2472),(31979,2496),(33491,2592),(36539,2736),( 38099,2784),(38939,2832),(39731,3024),(42059,3120),(49139,3144),(51939,3168),(53819,3192),(55571,3360),(58211,3432),( 59219,3672),(65771,3696),(66491,3960),(74051,4200),(87779,4416)

GAP code:

a:=[];R:=89999;for i in [1..R] do a[i]:=0;od;
for x in [1,3..299] do
 for y in [1,3..x] do
  for z in [1,3..y] do
r:=x*x+y*y+z*z; if r<=R then
if x>y and y>z and z>0 then n:=48;
 else if (x>z and z>0) or (x>y and z=0) then n:=24;
 else if x=z then n:=8;
 else if y=0 then n:=6;fi;fi;fi;fi;
a[r]:=a[r]+n;fi;od;od;od;
b:=0;for i in [1..R] do if a[i]>b then b:=a[i];Print("(",i,",",b,"),");fi;od;

Answer 4

I will just reference this link Many representations as a sum of three squares that shows that this is a really hard questions and seems open at the moment to estimate the growth of the sequence.