The wait for the next sum of two squares

Almost no number is a sum of two squares. Among the numbers up to $x$ the share that are falls off like $1/\sqrt{\log x}$, so it tends to nothing — slowly, but to nothing. A share tending to nothing usually means the members spread further and further apart. The primes behave that way: they thin out like $1/\log x$, and the gaps between consecutive primes grow without bound, with a run of a million composite numbers in a row starting at $(10^6 + 1)! + 2$.

Sums of two squares thin out more slowly than primes do, and their gaps are also forced to stay much shorter than anything the density alone would allow. The next sum of two squares after $n$ is never more than about $2\sqrt 2\, n^{1/4}$ away. The proof is two lines of arithmetic, and it has not been improved in eighty years.

Where they sit on the number line #

It helps to look before arguing.

Two things are visible at once. The sums of two squares get rarer — twelve in the first row of twenty, seven in the last. And they never leave a long hole. The widest stretch without one below two hundred is 186 to 192, seven numbers, after which 193 = 144 + 49 arrives.

Some of the structure in the picture is the rule about primes: a number is a sum of two squares exactly when every prime that is 3 more than a multiple of 4 divides it to an even power. That rule makes every number of the form $4k + 3$ unfilled — a whole column-pattern of holes — and makes 21, 22, 24, 27, 28, 30, 31 all fail for their own reasons. It does not by itself say anything about how long a run of failures can last. For that the argument has to find a sum of two squares near any given number, and the rule about primes is no help in finding one: it decides a number presented to it, but it cannot say where the next success lies without factoring every candidate in turn. What is needed is a construction — a way of writing down, from $n$ alone, a nearby number that is visibly a sum of two squares because it has been built as one.

The largest square, and then the smallest #

Take any $n$. Let $a^2$ be the largest square not exceeding it, so $a = \lfloor \sqrt n \rfloor$, and write the remainder as $r = n - a^2$. Because $(a+1)^2 = a^2 + 2a + 1$ is already bigger than $n$, the remainder is at most $2a$. That is the first squaring: the distance from $n$ down to a square is at most about $2\sqrt n$.

Now do the same thing to $r$, upward. Let $b^2$ be the smallest square at least $r$. The distance from $r$ up to $b^2$ is less than $2b$, and $b$ is about $\sqrt r \le \sqrt{2\sqrt n}$. That is the second squaring.

Put them together: $a^2 + b^2$ is a sum of two squares, it is at least $a^2 + r = n$, and it exceeds $n$ by $b^2 - r < 2b$. So

$$\text{the next sum of two squares after } n \ \le\ n + 2\sqrt{2}\, n^{1/4} + 1.$$

The picture says the same thing geometrically. A sum of two squares is a lattice point, and $x^2 + y^2 = n$ is a circle of radius $\sqrt n$. The argument walks out along the $x$-axis to the last lattice column inside the circle, $x = a$, and climbs that column until it leaves the circle. The circle crosses the column at height $\sqrt r$, and the first lattice point above is less than one unit further on. How far outside the circle can that lattice point be? Its squared distance from the origin exceeds $n$ by less than $2\sqrt r + 1$, and since $r$ is small compared with $n$ — the column is near the edge — the excess is small too.

The argument is due to R. P. Bambah and S. Chowla, in 1947, and it is the kind of proof that looks as though a little more care would sharpen it. The next section shows that it has room to spare. Nobody has found the care.

Record gaps against the bound #

The bound is easy to test, since sums of two squares are easy to sieve for.

Below a million the longest wait is 35 numbers, where the bound allows about 90. More telling than any single gap is the shape of the records: on logarithmic axes a power law would be a straight line, and the dots bend away beneath the bound’s straight line as $n$ grows. What they look like is a quantity growing like a power of $\log n$ rather than a power of $n$.

That is also what heuristics predict. If sums of two squares behaved like random numbers of density $c/\sqrt{\log n}$, gaps would be typically about $\sqrt{\log n}$ long and the longest in a range would be of order $\log n \cdot \sqrt{\log n}$ — a slowly growing function nowhere near $n^{1/4}$. And the true numbers are not random: the rule about primes makes them avoid residue classes, which lengthens some gaps and shortens others in ways the heuristic ignores.

The gap between the proved bound and the observed behaviour is enormous, and it is open. No argument is known that gives a gap of $n^{1/4 - \varepsilon}$ for any $\varepsilon > 0$. In the other direction, Ian Richards proved in 1982 that gaps as long as about $\tfrac14 \log n$ occur infinitely often, so the gaps are genuinely unbounded; between $\log n$ and $n^{1/4}$ is a range nobody has been able to narrow.

Why the easy argument is stuck #

The two-squarings argument uses only the fact that squares are dense near the scale $\sqrt r$: the gap between consecutive squares near $r$ is about $2\sqrt r$. To do better one would want to choose the first square more cleverly — not the largest square below $n$, but some square $a^2$ for which the remainder $n - a^2$ happens to be a square itself, or close to one.

There are about $\sqrt n$ choices of $a$, and each remainder $n - a^2$ is a number of size up to $n$; the chance that a random such number is within $k$ of a square is about $k/\sqrt n$. So with $\sqrt n$ tries and a success probability of $k/\sqrt n$ each, one expects to succeed with $k$ of order 1 — a bounded gap, if the remainders behaved like random numbers. They do not behave like random numbers, and proving that enough of them come close to squares is exactly the kind of statement about the distribution of $n - a^2$ modulo squares that current methods cannot reach. The easy argument takes one try and accepts whatever remainder it gets; every improvement would need to control many tries at once.

A second route would be to use the rule about primes directly — to show that among the numbers just after $n$ one of them has all its $4k + 3$ primes to even powers. That is a sieve problem, and sieves are good at counting how many numbers in a long interval survive and bad at guaranteeing that a short interval contains one. The interval here has length $n^{1/4}$, which is short by the standards of sieve theory. Sieve methods do show that almost every interval of length a power of $\log n$ contains a sum of two squares — the exceptions are rare — but a statement about every interval, with no exceptions allowed, is out of their reach at any length below the fourth root.

The same obstruction, in a different costume, is what separates the count of lattice points in a disc from its expected value. There the question is how far the number of lattice points in a circle of radius $\sqrt n$ can stray from $\pi n$; the easy bound is of order $\sqrt n$, the truth is conjectured to be about $n^{1/4}$, and eighty years of work have moved the proved exponent only a little. Lattice points near a circle are hard to control, and a gap between sums of two squares is precisely a thin ring round a circle containing no lattice point at all.

Three in a row, and never four #

The strip showed 8, 9, 10 filled side by side, and 16, 17, 18, and 72, 73, 74. Runs of consecutive sums of two squares are worth counting, because one length never occurs.

A run of four consecutive numbers always contains one that is 3 more than a multiple of 4. A square leaves remainder 0 or 1 when divided by 4 — an even number squared is a multiple of 4, an odd one is one more than a multiple of 8 — so a sum of two squares leaves 0, 1 or 2, and never 3. So four in a row is impossible, and the reason is arithmetic on a clock with four hours.

Three in a row is not forbidden by any remainder, and it happens, hundreds of times below a hundred thousand. That runs of three recur without end is a theorem, and it can be seen from a family: $n^2 - 1$, $n^2$, $n^2 + 1$ are three consecutive numbers of which the last two are sums of two squares trivially, and for infinitely many $n$ the first is too. Take $n = 2k^2 + 1$: then $n - 1 = k^2 + k^2$ and $n + 1 = (k+1)^2 + (k-1)^2$, and a product of two sums of two squares is again one, so $n^2 - 1 = (n-1)(n+1)$ is a sum of two squares. With $k = 2$ that gives 80, 81, 82. How often runs of three occur in general — how their count up to $x$ compares with what an independence model of the three conditions would predict — has conjectural answers and only partial theorems.

Further out, the same shape #

A strip at the start of the number line can mislead, because small numbers are special. So look again ten thousand numbers on.

Two hundred numbers past ten thousand contain fifty sums of two squares, where the first two hundred contained seventy-nine; the thinning is visible, and it is the slow $1/\sqrt{\log x}$ thinning of the density rather than anything faster. The longest hole has grown from seven to thirteen. And the holes are still scattered rather than clustered: most rows have three or four filled cells, and none is empty. That is the qualitative content of the bound — the density falls but the spacing stays even — seen at a scale where the fourth root of $n$ is ten rather than four.

The hole from 10,101 to 10,113 is also worth reading closely, because it shows what a gap is made of. Among its thirteen numbers, three are $4k + 3$ and fail automatically; the rest fail because each has some prime $4k + 3$ to an odd power — 10,101 is $3 \times 7 \times 13 \times 37$, 10,102 is $2 \times 5051$ with $5051 \equiv 3 \pmod 4$ — each for its own reason. A long gap is a coincidence of many independent failures, which is why long gaps are rare and why their length grows so slowly.

The same bound for other shapes #

The argument used nothing specific to squares beyond the gaps between them. Replace $x^2 + y^2$ by $x^2 + y^3$, or by any sum of two powers, and the same two-step argument gives a gap bound — the largest $k$th power below $n$, then the nearest power above the remainder — with an exponent that depends on the powers. For sums of three squares the question disappears: every number not of the form $4^a(8b + 7)$ is one, so the gaps are bounded outright — never more than two numbers in a row are missed, and 111 and 112 are the first such pair. For four squares there are no gaps at all, since every number is a sum of four.

So two squares is the interesting case for a structural reason. With three or more squares the representable numbers have positive density and the gaps are bounded; with two they have density zero, and the question becomes how that zero density is distributed. It is thin but evenly spread, and the easy argument sees only a crude version of the evenness.

There is a version of the question for primes that shows how much the answer depends on the set. The primes are also of density zero, thinning like $1/\log x$, and the best proved bound for the gap after $n$ is about $n^{0.525}$ — a much weaker statement than $n^{1/4}$, for a set that is only a little thinner. The difference is that sums of two squares can be constructed near any number, by the two squarings, while nobody knows how to construct a prime near a given number at all.

What the pictures cannot establish #

A million is not large. The record gaps are plotted up to $10^6$, where $\log n$ is about 14 and $n^{1/4}$ is about 32. The two scales are not yet far apart, and the eye can be misled about which curve the dots follow. The claim that the records grow like a power of $\log n$ is a heuristic and an extrapolation, not something the figure proves; the only proved statements are the bound above them and Richards’s bound below.

The first figure’s gap of seven is special. Short ranges have their own record gaps, and a strip of two hundred numbers shows a structure — rows thinning, holes at every $4k + 3$ — that is qualitatively right and quantitatively nothing like the asymptotic regime.

The run counts are a census, not a density. The bar chart counts runs below a hundred thousand; it establishes that four in a row never occurs there, which the remainder argument proves everywhere, and it shows three in a row occurring often, which the infinite family above guarantees. It does not say how the proportions change as the range grows.

Still open: the true size of the gaps #

Two questions are open, and they are the natural next steps.

What is the right exponent? It is conjectured that for every $\varepsilon > 0$ the gap after $n$ is eventually less than $n^{\varepsilon}$ — that is, smaller than any power — and most likely of order $\log n$ at most. The proved exponent is $1/4$, from the argument drawn above. Any improvement, to $1/4 - 0.001$, would be a new result.

How long are the longest gaps, really? Richards’s lower bound of about $\tfrac14\log n$ shows the gaps are unbounded; the heuristics suggest the longest gap up to $x$ is of order $\log x$ times a small power of $\log\log x$ at most. Closing the distance between $\tfrac14 \log n$ from below and $n^{1/4}$ from above is a problem about the fine distribution of lattice points near circles, and it is not expected to be easy.

Both questions would follow from strong enough information about lattice points in thin annuli — rings between radius $\sqrt n$ and $\sqrt{n + h}$ — and that information is exactly what the circle problem lacks. So the two open problems, the gaps and the circle, are one problem seen at two scales: the number of lattice points in a whole disc, and whether a thin ring of it contains any at all.

A thin set that is evenly spread #

Sums of two squares are rare in the long run and never far apart. Both statements are true at once because the rarity is so slow — a factor of $\sqrt{\log x}$ — and because squares are so dense near any small number that a remainder can always be topped up to one. The argument that shows it takes two squarings and fits on a line, and the fact that nobody has improved it is a measure of how little is known about where lattice points lie near a circle.

It is also a small lesson about the difference between counting and constructing. Landau’s count says how many sums of two squares there are, to a precision the gap bound cannot approach; the gap bound says where one of them is, near any number, which the count cannot say. Each kind of statement is blind to what the other sees, and the best results in this subject are the ones that manage both. Here the count is sharp and the placement is crude, and the eighty-year-old crude one is still the best there is.