The dots a ball catches

Pick’s theorem gives a lattice polygon’s area exactly, by counting the dots inside it and on its edge. A circle’s dots are counted only approximately: a disc of radius $R$ holds about $\pi R^2$ lattice points, and the error is believed to be about $\sqrt R$ in size and is proved only to be below $R^{0.63}$. That essay ended with an observation it did not draw. In four dimensions and above the same question is essentially settled; in three it is open. The problem is hardest where the geometry is simplest, and this essay measures why.

The count in three dimensions can be built from the count in two. A ball of radius $R$ is a stack of discs, one at each whole-number height, and the lattice points in the ball are the lattice points in all those discs added up.

The ball of radius 7.5 holds 1,791 points against a volume of 1,767.1. The error, 23.9, is a sum of fifteen errors of the circle problem — one per slice — each about the square root of its own radius in size, with signs that may partly cancel. How well they cancel is the whole three-dimensional problem, and the slices alone cannot say: they turn one hard problem into fifteen hard problems and a question about signs.

One ball, taken apart #

The ball of radius 7.5 shows what the slicing does with the error. Each of the fifteen slices has its own circle-problem error, and they are −1.8, 5.4, −1.2, 2.6, −3.4, 4.9, 3.4 and 0.3 from the top slice to the middle one, then the same in reverse. Their sizes add up to 45.5, but with their signs they add up to only 19.9: more than half of the slices’ errors cancel. The remaining 3.9 of the ball’s error comes from a second source — the fifteen slices’ areas add up to 1,771.1, not to the ball’s volume of 1,767.1, because summing areas at whole-number heights is itself only an approximation to the integral that gives the volume.

So the three-dimensional error has two parts: a sum of two-dimensional errors with partly random signs, and a smooth correction from replacing an integral by a sum. The smooth part is easy and small. The random part is the problem. If the fifteen slice errors were independent random numbers of size about $\sqrt{r}$, their sum would be about $\sqrt{15} \times \sqrt{r}$, which for a ball of radius $R$ comes to about $R$ — the conjectured order of the three-dimensional error. Proving that the slice errors behave that independently is beyond present methods, and the conjecture is exactly the statement that they do.

Writing a number as a sum of squares #

The better route goes through arithmetic. A lattice point $(x_1, \ldots, x_d)$ lies on the sphere of radius $\sqrt n$ exactly when $x_1^2 + \cdots + x_d^2 = n$, so the number of lattice points on that sphere is $r_d(n)$, the number of ways of writing $n$ as a sum of $d$ squares, counting order and signs. The number in the ball of radius $R$ is $r_d(0) + r_d(1) + \cdots + r_d(\lfloor R^2 \rfloor)$. Everything about lattice points in balls is a question about the sequence $r_d(n)$ — how large it is on average, and how erratically it departs from its average.

The three sequences behave very differently. Sums of five squares are steady: every number is one, in a number of ways within about a factor of three of the typical count $n^{3/2}$ times a constant. Sums of four squares obey an exact formula that Carl Jacobi proved in 1834 — $r_4(n)$ is eight times the sum of the divisors of $n$ that are not multiples of four — and the formula’s dips are visible at the powers of two, where there are few such divisors; the figure checks it for every $n$ up to five thousand. Every number is a sum of four squares, and Jacobi’s formula says in how many ways.

Sums of three squares are wild. A sixth of all numbers are not sums of three squares at all — exactly the numbers of the form $4^a(8b + 7)$, as Adrien-Marie Legendre found in 1798 and Gauss proved — and the numbers that are have counts scattered over a wide range. The same erratic arithmetic made three triangular numbers suffice for every number a theorem of real depth, and it is the source of the difficulty in three dimensions.

The sequences are computed by building sums of squares one square at a time. The number of ways of writing $n$ as one square is 1 for $n = 0$, 2 for a positive square and 0 otherwise. The number of ways as $d$ squares is the number of ways as $d - 1$ squares, summed over the possible values of the last square: $r_d(n) = \sum_x r_{d-1}(n - x^2)$. Four such passes over the numbers up to 200,000 produce $r_2$ to $r_5$ in a fraction of a second, and the slices of the ball are a check on the result, since the slices and the sums of three squares must give the same count. They do.

Three squares counted by a class number #

Gauss found in 1801 what $r_3(n)$ actually is, and the answer explains the scatter.

For a square-free $n$ greater than 3, the count is $12\,h(-4n)$ when $n$ leaves remainder 1 or 2 on division by 4, and $24\,h(-n)$ when it leaves remainder 3 on division by 8, where $h(D)$ is the class number of the discriminant $D$ — the number of essentially different quadratic forms $ax^2 + bxy + cy^2$ with $b^2 - 4ac = D$. The figure computes each class number by listing the reduced forms, and the formula holds for all 1,515 numbers tested.

Class numbers are notoriously irregular. They measure how badly unique factorisation fails in a quadratic field, they grow roughly like $\sqrt{|D|}$ on average, and they fluctuate around that by factors that are themselves hard to control — the question of how small they can be was one of the long sagas of twentieth-century number theory. A ball in three dimensions inherits all of that. The circle problem has a similar problem in a different form: $r_2(n)$ depends on how $n$ factors into primes of the form $4k + 1$, which is the arithmetic of sums of two squares, and it too can be zero or large in unpredictable ways.

The error on each dimension’s scale #

With $r_d(n)$ computed for every $n$ up to 200,000, the count and its error can be followed for every radius up to about 447 in dimensions two to five. The radii used are $\sqrt{n + \tfrac12}$, halfway between the integer values of $R^2$, so that no lattice point lies on a boundary and no convention about boundary points affects the count.

Each normalised error fluctuates around nought without drifting — over all 200,000 radii its average is within a few thousandths of zero in every dimension, which says that the volume is the right first approximation and that the errors are genuinely fluctuations rather than a missing term. The difference between dimensions is in the width of the band. In five dimensions it settles almost at once. In four it settles more slowly. In three and two it keeps widening, slowly, which is what an exponent with an unknown “+ ε”, or a logarithmic factor, looks like over a finite range.

How fast the error can grow #

The width of the band can be turned into an exponent. Follow the largest error seen so far as the radius grows; on logarithmic scales its record curve rises with a slope that estimates how fast the error can grow.

In five dimensions the slope is 3.05, close to the proved order $R^3$. In four it is 2.11, the order $R^2$ up to a logarithm. In three it is 1.27, between the conjectured $1 + \varepsilon$ and the best proved bound, $21/16 = 1.3125$, due to Roger Heath-Brown in 1999. For the disc it is 0.64, above the conjectured $\tfrac12$ — record curves over a finite range are pushed up by rare large deviations, and overestimate. No finite computation can distinguish an exponent from a slightly larger one, and that is why these computations, and much larger ones, have never settled the low-dimensional problems.

The four-dimensional case deserves its exact status. The error there is proved to be at most $R^2$ times a power of $\log R$ — Arnold Walfisz brought the power down to two-thirds in 1960 — and it is proved to exceed $R^2 \log\log R$ infinitely often. The truth lies between, and in that narrow sense even four dimensions is not quite closed. But the gap is between two logarithmic factors, not between two exponents, and the difference is invisible in any computation.

Where the logarithm in four dimensions comes from #

Jacobi’s formula turns the four-dimensional count into a sum of divisors. The number of lattice points in the ball with $R^2 = x$ is one plus eight times the sum, over $n \le x$, of the divisors of $n$ not divisible by four. Reorganised by divisor rather than by $n$, that is a sum over $d$ of $d$ times the number of multiples of $d$ up to $x$ — about $d \cdot x/d$, but really $d \cdot \lfloor x/d \rfloor$, and the rounding loses up to $d$ for each $d$.

Adding the main terms gives the volume, $\pi^2 x^2/2$. Adding the rounding losses naively gives an error up to $\sum_{d \le x} d$, far too much; the losses cancel on average because $x/d$ falls in every position between two integers about equally often. They do not cancel perfectly for the small divisors, and each scale of divisor — those near 1, near 2, near 4, and so on up to $x$ — contributes a bounded multiple of $x$. There are about $\log x$ scales, and that is the logarithm: an error of order $x \log x = R^2 \log R$, from the many sizes of divisor each making its own small contribution. Walfisz’s refinement shows the contributions cancel a little between scales; the lower bound shows they do not cancel entirely.

The same divisor sum, with all divisors counted, is the divisor problem under a hyperbola in a different guise, and in five dimensions and above no such sum appears, because $r_d(n)$ is no longer a simple sum over divisors and is instead dominated by its smooth main term.

In five dimensions the error is one shell #

From five dimensions up the problem is closed, and the reason can be drawn. The points on a single sphere — the lattice points with $x_1^2 + \cdots + x_5^2 = n$ — number about $n^{3/2} = R^3$ times a constant. The error in the count inside the ball is of the same order.

On average the error is about a sixth of one shell’s points. That is the whole story in five dimensions: the volume approximates the count to within a fraction of the points on a single sphere, and the number of points on a sphere is regular — bounded above and below by fixed multiples of $R^3$ — because $r_5(n)$ is regular. A sum over many shells with regular populations has an error no worse than a typical shell.

In two and three dimensions the same reasoning fails, because a single shell’s population is not regular. In two dimensions a circle of radius $\sqrt n$ carries no lattice points for most $n$ and many for a few; in three, a sphere carries none when $n$ is of Legendre’s form and a class number’s worth otherwise. The error is a sum of irregular terms, and bounding it means controlling how their irregularities cancel — which is a question about the arithmetic of class numbers and of primes, not about geometry.

Why the high dimensions are easier #

There is a general principle behind the reversal. In $d$ dimensions, the number of lattice points on the sphere of radius $\sqrt n$ is, for $d \ge 5$, very close to a smooth main term — Hardy and Littlewood’s singular series times $n^{d/2 - 1}$ — with an error that is much smaller than the main term. The singular series is a product over primes of local factors that say how often a sum of $d$ squares hits $n$ modulo powers of each prime, and with five or more squares the local factors are bounded above and below, so the singular series never strays far from its typical size. With four squares the local factor at 2 can be small, which is Jacobi’s dip at powers of two and the source of the logarithm. With three squares the local factors can vanish, which is Legendre’s theorem, and the main term is not smooth at all.

So adding squares averages away the arithmetic. Each extra square spreads the representations of $n$ more evenly, in the same way that adding independent random variables smooths a distribution, and in high dimensions almost everything is regular. The geometry of a ball gets more complicated as the dimension rises, and the arithmetic of its lattice points gets simpler, and it is the arithmetic that decides.

What the counts cannot show #

Every figure here stops at a radius of about 450 in every dimension, and the claims that matter are about all radii. The slopes of the record curves are estimates over one decade and a half; the proved orders in four and five dimensions are theorems, and the conjectured orders in two and three are beliefs that these figures are consistent with but cannot support any further. In the disc problem the conjecture has been tested on radii far beyond these, and the exponent still cannot be read off: the error’s growth by a logarithm or by a tiny power is beyond the reach of any finite range.

The figures also use one shape. A ball’s lattice points are special because the ball is round and the lattice is the integer lattice; for an ellipsoid whose axes are generic irrational numbers, the arithmetic coincidences that make $r_d(n)$ irregular disappear, and in high dimensions the error is provably smaller than a shell. The roundness of the ball, which makes its geometry simplest, is exactly what lets the arithmetic in.

Still open: the circle and the ball #

For the disc, is the error at most $R^{1/2 + \varepsilon}$ for every $\varepsilon > 0$? Hardy proved in 1915 that it is sometimes larger than $R^{1/2}$ times a small power of $\log R$, and the best upper bound, Martin Huxley’s exponent $131/208 \approx 0.630$ from 2003, has since been edged down only slightly. For the three-dimensional ball, is the error at most $R^{1+\varepsilon}$? The best upper bound is Heath-Brown’s $21/16$; the error is known to reach the size $R$ times a small logarithmic factor infinitely often. Both problems are tied to some of the deepest open questions about exponential sums, and neither is expected to be settled by computation. The progress that has been made has come from bounding sums like $\sum e^{2\pi i f(n)}$ over short ranges, the same exponential sums that control the zeta function on its critical line, and each improvement in the exponent has needed a new idea about them rather than more computing power.

The pattern is the same as in the size of a number with no formula and the error in counting primes: a main term that everyone can write down, an error believed to be about the square root of the main term’s natural scale, and a proof that falls short by a power that nobody knows how to remove.

Arithmetic decides the hard cases #

The lattice points in a ball of radius $R$ number about its volume, and the error depends on dimension in reverse: from five dimensions up it is of the order of one spherical shell, $R^{d-2}$, and that is proved; in four it is $R^2$ up to a logarithm; in three and two its exact size is unknown. The reason is in the representation numbers. Sums of five squares are regular, sums of four follow Jacobi’s divisor formula, and sums of three are zero on Legendre’s numbers and a class number otherwise — and a count that sums irregular shells inherits their irregularity. The ball’s geometry is never the difficulty; the arithmetic of squares is.