The comet Goldbach left behind

In June 1742 Christian Goldbach wrote to Leonhard Euler that every number seems to be a sum of three primes, counting 1 as a prime as was then common. Euler replied with what is now the usual form: every even number above 2 is a sum of two primes. Nearly three hundred years later, it has by now been checked for every even number up to $4 \times 10^{18}$, and it has not been proved. Euler thought it a certain theorem that he could not prove, and said as much. It might be the best known open question in mathematics after the Riemann hypothesis, and it has a feature that makes it particularly frustrating. Everybody has a good reason to believe it, and the reason is exact enough to predict the number of ways, to within a percent or so.

The reason can be seen from a picture. Plot, for each even $n$, how many ways it can be written as $p + q$ with $p \le q$ both prime, and what comes out is known as Goldbach’s comet. It is not one smear. It is a set of clearly separated bands, and those bands contain the whole heuristic.

Why neighbours differ so much #

12,000 can be written as a sum of two primes in 302 ways, and 12,002 in only 115. These are adjacent even numbers, of the same size, and one has nearly three times as many ways. The colours in the figure give the answer. The multiples of 3 form a band well above the others, and the multiples of both 3 and 5 are higher still.

The explanation is an observation on remainders. Apart from 3 itself, a prime leaves remainder 1 or 2 on division by 3, in equal shares.

If 3 divides $n$, then when $p \equiv 1$, the partner $n - p \equiv 2$, and when $p \equiv 2$, it is $\equiv 1$. Neither is a multiple of 3. If 3 does not divide $n$, say $n \equiv 1$, then $p \equiv 1$ gives a partner that is a multiple of 3 and so is not prime. Half of the candidate pairs are gone before any further question is asked. So a multiple of 3 has about twice as many chances.

The same count applies to each odd prime $\ell$. Of the $\ell - 1$ non-zero remainders available to a prime, a number $n$ not divisible by $\ell$ loses one, leaving $\ell - 2$ for which the partner can be prime, while a number divisible by $\ell$ loses none. So $\ell$ dividing $n$ multiplies the count by $(\ell - 1)/(\ell - 2)$. That is 2 at 3, $4/3$ at 5, $6/5$ at 7. So 12,000, which is divisible by 3 and 5, has a factor of $2 \times 4/3 = 2.67$, while $12{,}002 = 2 \cdot 17 \cdot 353$ has a factor of $16/15 \times 352/351 = 1.07$. The ratio of these is 2.49, and the true ratio is $302/115 = 2.63$. The bands are that factor, nothing more. The step about equal shares is not an assumption, since Dirichlet’s theorem proves that primes divide evenly among the permitted remainders, and in this sense the first half of the argument is solid. It is the second half, treating the primality of $p$ and of $n - p$ as otherwise unrelated events, that nobody can justify. Those are two statements about the same number and they might conspire. Primes have no known reason to conspire and every measured reason not to, but that absence of a reason is not a proof, and a proof would need to show that it can never happen at any scale. It is as simple an argument as the residues that forbid some patterns of primes, of which it is a two-term case.

Hardy and Littlewood’s product #

Treating primes as independent apart from those congruence conditions gives the heuristic of G. H. Hardy and J. E. Littlewood in 1923:

$$r(n) \approx C_2 \prod_{\substack{\ell \mid n \\ \ell > 2}} \frac{\ell - 1}{\ell - 2} \int_2^{n-2} \frac{dt}{\ln t \ln(n - t)},$$

where $C_2 = 0.66016\ldots$ is the twin-prime constant. That is the same constant that governs how often primes come in pairs, and this is not a coincidence, since $p$ and $n - p$ both being prime is the same kind of event as $p$ and $p + 2$ both being prime. The integral expresses the chance that a pair of numbers of those sizes are both prime, by the prime number theorem. So the count should grow like $n/\ln^2 n$, multiplied by the product above.

Dividing each exact count by this prediction gives the next figure.

All bands collapse onto a single line. The mean ratio from 2,000 to 200,000 is 0.989. Above 100,000 the mean absolute error is about 1.28%, and the largest error found in that range is 8.2%, at one isolated value. The narrowing is about what one would expect if the count were subject to something like square-root fluctuations. So a formula derived with one line of reasoning about remainders predicts all the structure in the comet. If some value of $r(n)$ were near nought at a large $n$, it would be a stupendous exception to a pattern this exact: at $n$ near $4 \times 10^{18}$, the prediction is more than $10^{15}$.

That is why almost no one doubts Goldbach’s conjecture. There is a subtlety though. The heuristic is about typical behaviour, and the conjecture is about all even numbers with no exceptions. To turn this into a proof, the formula would have to be established with an error smaller than the main term for every single $n$.

Reading the bands one at a time #

The formula can be tested band by band. Take the 5,000 even numbers between 190,000 and 200,000 and sort them by which of 3, 5 and 7 divide them. The 2,285 divisible by none of the three have a mean of 1,076 ways. The 1,144 divisible only by 3 have a mean of 2,153, a ratio of 2.00, and the mean factors of the two groups have a ratio of 2.00 as well. The 573 divisible only by 5 have 1,436, a ratio of 1.334, against a predicted 1.334. The 381 divisible only by 7 have 1,292, a ratio of 1.200, predicted 1.200. Combining them behaves as multiplication should: 285 numbers divisible by 3 and 5 have 2,870, 190 divisible by 3 and 7 have 2,584, and the 48 divisible by all three have 3,439, a ratio of 3.20 against a predicted 3.20.

These agreements hold to three figures, in a sample of a few thousand, and that is better than the formula’s reputation might suggest. The independence that is assumed really does seem to be there at this level of detail. The richest even number in the whole table is 196,350, or $2 \cdot 3 \cdot 5^2 \cdot 7 \cdot 11 \cdot 17$, with 3,931 ways, and its product is 3.79, the largest of those near it. It is exactly what the formula would choose. The poorest even number in the final decade is 191,024, with 979 ways, and its product is 1.0001, since it has only large odd prime factors. Numbers of this kind, twice a prime or a power of two times a large prime, form the bottom edge of the comet, and any counterexample ought to live there. The largest error above 100,000 is at 144,128, which is $2^8 \cdot 563$, with 751 ways, 8.2% below its prediction. So the bottom edge is not a particularly clean line. It carries the scatter too, and nobody can show that the scatter never gets as large as the prediction itself.

How few ways there can be #

The numbers with very few ways are all small. 12 is the last even number with only one way, $5 + 7$. 68 is the last with exactly two or fewer. Then 128 is the last with three, 152 with four, 188 with five. The curve runs steadily, as $n$ increases, in a way that is almost a straight line on the logarithmic scales, and the last few values are limited only by the range of the table. Each of these is a small theorem that is been verified by computation up to the limit of the table, with an extra assumption. That 12 is the last with one way is only established up to where searches have gone, because a very large even number with only one way has not been ruled out. It would be far below the prediction. That is the uncomfortable gap. The evidence is overwhelming and the logic is empty.

The smaller prime #

To verify the conjecture at a given even number, the whole of $r(n)$ is not needed. One representation is enough, and because the count is so large, a small prime usually works.

For every even $n$ up to 20 million, testing primes in order finds one quickly. Prime 3 is the smallest that works for 12.7% of numbers, and 5 for 11.6%. The largest value needed over this entire range is 829, at $n = 10{,}759{,}922$. That is what makes verification cheap. Tomás Oliveira e Silva, Siegfried Herzog and Silvio Pardi did this up to $4 \times 10^{18}$ in 2014, where the smaller prime never had to be larger than 9,781. The records grow roughly like a power of $\ln n$, in the same manner as the longest wait for a prime, with which the records are closely connected. If $n - p$ is to be composite for many small primes $p$, then a set of numbers just below $n$ must be composite in a particular pattern, and the likelihood of this falls in the same way that gaps of a given length do.

What can be proved #

The partial results are impressive, and each stops at a clear barrier. Three primes are easier. In 1937, Ivan Vinogradov proved that every sufficiently large odd number is a sum of three primes, using the circle method. In 2013 Harald Helfgott closed the remaining range and proved that every odd number greater than 5 is a sum of three primes, a result known as the ternary Goldbach theorem. The method cannot reach two primes, and the reason is intrinsic. With three primes a triple exponential sum has a square-root saving to spare. With two primes there is no slack to absorb the error from the minor arcs.

“Almost all” is also possible. In the 1930s, Nikolai Chudakov, Johannes van der Corput and Theodor Estermann proved that almost every even number is a sum of two primes. Hugh Montgomery and Robert Vaughan sharpened this in 1975: the exceptions up to $x$ number at most $x^{1-\delta}$ for some $\delta > 0$. So a counterexample would have to be very rare, and it is known that the exceptions have density nought. Yet none of that excludes even one exception.

Sieve methods approach from another side. Chen Jingrun proved in 1973 that every large even number is a sum of a prime and a number with at most two prime factors. That is as close as it gets. It cannot be improved by sieves alone, as the parity problem stands in the way: a sieve, as Atle Selberg saw, cannot distinguish numbers with an odd number of prime factors from those with an even number, and so it cannot separate a prime from a product of two primes. That is why Chen’s theorem and its analogue for twin primes stop at exactly the same spot, one prime factor short.

Other relatives are more tractable and they show where the difficulty lies. Replacing primes by numbers with a dense enough structure makes the same statement easy, as the practical numbers show, even for sets that thin out in a similar way. Sets with similar density, but with no multiplicative structure, can be built that have the same result, so there is no probabilistic barrier. Probabilistic models have a role in explaining what is going on: a random set of the primes’ density has the property with probability one, except finitely many cases. It is exactly the question of whether primes behave like such a random set, one that was also the subject of the sieve that cannot finish.

What the comet cannot show #

Nothing in these figures bears on the conjecture itself. The counts are exact up to 200,000 and the least primes up to 20 million, while the literature reaches $4 \times 10^{18}$, and the statement is about all even numbers. A good fit is evidence of the correctness of the heuristic on this range. It does not contain evidence about any particular number outside it. The largest error of 8% in the last range is at one number, 144,128, and it is likely to be part of the normal scatter, but no analysis of that scatter was made. And the fit’s mean of 0.989 slightly below one is presumably a lower-order effect, since the integral replaces a discrete sum over primes with one over densities, and it was not studied further.

The figure on remainders is a heuristic argument and not a proof. The independence used in it is not known, and it is precisely what cannot be established.

What was computed and what was quoted #

All counts are exact, computed by adding all pairs of primes up to 200,000, with checks at small values and a full check that no even number in that range has $r(n) = 0$. The prediction was computed from the exact factorisation of $n$, with the integral done numerically, and the ratio was computed for every even $n$ from 2,000 upward. The least primes come from a direct search for every even number up to 20 million.

Quoted: the statement of Goldbach’s letter, the Hardy–Littlewood formula, the theorems of Vinogradov, Helfgott, Chudakov, van der Corput, Estermann, Montgomery and Vaughan, Chen, and the verification to $4 \times 10^{18}$. The remark about the parity barrier is an outline, as the essay on that subject explains.

Still open: every even number #

Is every even number above 2 a sum of two primes? Nobody knows, and the best current statement falls short at every point. Since Helfgott’s theorem, the ternary case is closed, so it is only the binary case that is left. Heuristically, $r(n) \to \infty$, as the formula requires, and a stronger version states that every even $n$ is a sum of two primes in about the predicted number of ways. Whether an effective proof of the asymptotic formula for almost all $n$ could be extended by a new idea is exactly the difficulty. Each known method loses at a particular place. The circle method cannot control the minor arcs for two primes, and the sieve has the parity barrier. It is generally believed that a new way of detecting primes will be needed.

Small relatives of the same statement are open as well. Does every even number occur as a difference of two primes, the Polignac form? James Maynard and Terence Tao’s work shows that some gaps recur infinitely often, and it has not reached every gap. Is the smallest prime needed in a Goldbach partition always less than a power of $\ln n$? The records suggest about $(\ln n)^2$ or so, and nothing near that has been proved.

The bands are the argument #

The comet’s bands are the factor $\prod (\ell - 1)/(\ell - 2)$ over the odd primes dividing $n$, and one line of reasoning about remainders predicts all of them, with the twin-prime constant in front. The ratio of exact counts to this prediction averages 0.989, and the bands disappear, leaving a single line.

So anyone who plots the count sees the conjecture’s strength and its weakness together. The count is not near nought at any point, it is growing, it is predicted to within a percent, and a number with no representation would be an absurdity. And yet the prediction assumes independence that nobody can establish, and the conjecture requires all even numbers without exception. The picture supplies the reason to believe and it offers no help at all in proving it.