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

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.

• The answer to the second question is obviously "yes". Just compute coefficients of $\theta^3$ and double precision each time. – WhatsUp Jan 30 '18 at 14:39
• For the first question, it is known since Gauss that coefficients of $\theta^3$ are essentially class numbers of quadratic imaginary fields. But you are asking for "$\geq n$ integral points", so maybe the growth in the class number part is insignificant. – WhatsUp Jan 30 '18 at 14:44
• Find an integer Z such that there are four distinct Pythagorean triples with x less than y less than Z (so x^2 + y^2 = Z^2). Then Z will be an upper bound on your search, and likely not far from the minimum. Gerhard "Look For Obvious Points First" Paseman, 2018.01.30. – Gerhard Paseman Jan 30 '18 at 14:54
• Indeed, Z=65 seems to fit the bill, looking at a table. Then there are (excluding the axes) 32 lattice points on the equator, and 102 points on three great circles. My guess is that the minimum will be not much below 40, if 65 is not already the minimum. Gerhard "Maybe Find A Bigger Table?" Paseman, 2018.01.30. – Gerhard Paseman Jan 30 '18 at 15:01
• I think this is oeis.org/A005875/list, but that would give (the square root of) 74 not 65 – Dap Jan 30 '18 at 15:08

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.''

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.

• There is also mathoverflow.net/q/3596, of which this could be considered a duplicate, unless you also talk about spheres not centered at the origin. Gerhard "Hasn't Found Off-Origin Question Origin" Paseman, 2018.01.30. – Gerhard Paseman Jan 30 '18 at 16:27
• In the spirit of this answer mathoverflow.net/a/3601 , I ask how well can one find k squares adding up to N with a simple strategy? Using a greedy algorithm I get something like k is log log N plus either a constant or plus log log log N. Can one do better using mod 4 considerations? The less advanced number theory used, the better the answer. Gerhard "May Need To Make Copies" Paseman, 2018.01.30. – Gerhard Paseman Jan 30 '18 at 16:41

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;


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.