The longest wait for a prime

The prime number theorem says that near a large number $x$ about one number in $\log x$ is prime, so the average distance from one prime to the next is about $\log x$. Near a million that is about fourteen; near thirty million, about seventeen. Averages hide the extremes, and the extremes are the question here: below $x$, how long is the longest run of consecutive numbers containing no prime at all?

Two elementary facts bracket the answer. Bertrand’s postulate says there is always a prime between $n$ and $2n$, so no gap below $x$ is longer than about $x$ itself. And the numbers $n! + 2, n! + 3, \ldots, n! + n$ are divisible by $2, 3, \ldots, n$ in turn, so gaps of every length exist somewhere. Both facts are hopelessly far from the truth. The longest gaps actually found are about the square of the logarithm — tiny compared to $x$, and appearing enormously earlier than $n!$.

Every record below thirty million #

A record gap, or maximal gap, is a gap between consecutive primes that is longer than every gap before it. The first few are easy: 1 between 2 and 3, 2 between 3 and 5, 4 between 7 and 11, 6 between 23 and 29, 8 after 89, 14 after 113. Finding them all below thirty million needs a sieve of that size and a single pass along it.

There are twenty-four records below thirty million. The sieve finds 1,857,859 primes, and the scan along them reproduces the two records that every published table lists as checks: a gap of 72 first appearing after 31,397, and a gap of 210 first appearing after 20,831,323. Plotted against $\log p$, the records climb in a curve that bends upward, and the curve they follow is roughly the shape of $(\log p)^2$ — but all of them lie below it.

The picture is sparse because records are rare. Between a gap of 154 after 4,652,353 and a gap of 180 after 17,051,707 there is no record at all; the primes spend more than twelve million numbers without beating their previous longest gap. Records arrive in jumps, and each jump sets a mark that can stand for a long time.

Records are not the same as first appearances, and the difference shows how irregular the small scale is. A gap of exactly 14 first appears after 113, before any gap of 10 or 12, which wait until 139 and 199. A gap of exactly 16 does not appear until after 1,831, long after the gap of 18 after 523 and the gap of 34 after 1,327. A record is a first appearance that also beats everything before it, so the record list skips 10, 12 and 16 entirely: by the time those lengths occur, longer gaps already have. The first appearance of each even length wanders up and down, while the records, which only ever increase, trace the envelope that the square of the logarithm describes.

Why the square of the logarithm #

The curve in the figure is a prediction, and it comes from treating the primes as random. Harald Cramér proposed in 1936 a model in which each number $n$ is “prime” with probability $1/\log n$, independently of every other. The model gets the density right by construction, so it reproduces the counting theorem, and it can be asked questions the real primes cannot answer directly.

In the model, the chance that a particular run of $g$ numbers near $x$ contains no prime is about $(1 - 1/\log x)^g \approx e^{-g/\log x}$. There are about $x$ places a run could start, so the longest run below $x$ is the $g$ at which $x\,e^{-g/\log x}$ drops to about one — that is, $g \approx (\log x)^2$. Cramér conjectured that the real primes do the same: that the largest gap below $x$, divided by $(\log x)^2$, tends to one along the records.

Below thirty million the ratio never passes $0.74$. That is not evidence against the conjecture, which is about the limit, and the ratio rises only very slowly. Computations of maximal gaps have been carried much further — Tomás Oliveira e Silva, Siegfried Herzog and Silvio Pardi found every record below $4 \times 10^{18}$ — and the largest ratio ever observed is about $0.92$, for a gap of 1,132 after 1,693,182,318,746,371, found by Bertil Nyman in 1999. No gap anyone has found reaches $(\log p)^2$.

What the random model gets wrong #

A model that treats every number alike cannot know that the primes after 2 are all odd. That sounds like a technicality and is not.

On the left, the gaps between primes from ten to thirty million, measured in units of $\log p$, follow the exponential law the random model predicts: many short gaps, fewer long ones, with the proportion longer than $t$ units about $e^{-t}$. Patrick Gallagher showed in 1976 that this law follows from the Hardy–Littlewood conjectures on prime patterns. The very shortest gaps are rarer than the curve says, because a gap of 2 is the smallest possible and gaps of one are impossible after 2.

The exponential law and the records are the same fact seen from two ends. If a proportion $e^{-t}$ of gaps near $x$ are longer than $t \log x$, and there are about $x / \log x$ gaps below $x$, then the number of gaps longer than $t \log x$ is about $(x/\log x)\,e^{-t}$. That drops to one when $t$ is about $\log x - \log\log x$, so the longest gap is about $(\log x)^2$, less a correction of order $\log x \cdot \log\log x$. The histogram’s tail and the record curve are one prediction, and the records test the tail at the point where it has almost run out of gaps to describe. That correction is also part of why the ratios in the earlier figure sit well below one: at thirty million, $\log\log x$ is almost three, a sizeable fraction of $\log x$.

On the right is what the smooth law hides. A gap of 6 is commoner than a gap of 2 or 4, a gap of 30 commoner than 28 or 32. The reason is divisibility by small primes. Two primes six apart must both avoid multiples of 3, and $n$ and $n + 6$ always have the same remainder on division by 3, so if one avoids it so does the other; for a gap of 2 or 4, avoiding 3 at one end makes it likelier to hit 3 at the other. Every gap divisible by a small prime gets a boost from that prime, and the boosts multiply.

Andrew Granville showed in 1995 that this local structure changes the answer for the largest gaps too. Building on a 1985 theorem of Helmut Maier — that the primes in short intervals do not always have the density the model predicts — he argued that the longest gaps should be at least $2e^{-\gamma} \approx 1.12$ times $(\log x)^2$ infinitely often, where $\gamma$ is Euler’s constant. The reason is that intervals near multiples of a product of small primes are more thoroughly sieved than random intervals of the same length, and the longest gaps live exactly there. So the random model, which gets the average spacing and the exponential law right, is expected to underestimate the extremes.

Three random imitations #

The model can be run. Declare each number prime with chance $1/\log n$, using a fixed seed so the run can be repeated, and record its gaps exactly as for the real primes.

The three runs produce staircases with the same overall shape as the real one, so the model gets the scale of the largest gaps right. In this range every run reaches a longer gap than the primes do: the model’s “primes” can be even, can be multiples of three, can cluster and spread in ways the real primes cannot, and at thirty million those freedoms make its longest gaps longer. Granville’s argument is about much larger numbers, where the sieving by small primes has had room to produce the long, thoroughly sieved intervals his correction counts on. At thirty million the real gaps are still shorter than the model’s, and whether they eventually overtake it — as Granville’s argument says they must — is beyond any computation so far.

That is an uncomfortable position for a model. It is the best available description of the primes’ large-scale randomness, and it is known to be wrong in its details. Its predictions for averages are confirmed, its predictions for the extremes are corrected by a theory that computation cannot yet reach, and its failures come from the same place that makes the patterns primes are allowed to make uneven.

A long gap, number by number #

A gap of 72 is a stretch of 71 consecutive composites. The factorial construction produces such a stretch after $72!$, a number of 104 digits. The primes produce the first one after 31,397.

Every even number in the stretch is divisible by 2, and the odd ones are covered by a scattering of small and not-so-small primes: 3 takes every third odd number, 5 and 7 take a few more, and the remainder are divisible by 11, 13, 17, 23, 31 and so on up to 163. A long gap is a stretch in which the sieve happens to cover every number, by primes all well below the square root of the numbers involved. The factorial construction forces that covering by brute force, dividing every number in the stretch by a different small factor; the primes achieve it by accident, far earlier, because there are so many places the accident can happen.

Twelve average gaps at once #

The records are easiest to feel as multiples of the average. Near twenty million the average gap is about seventeen, so the record gap of 210 is about twelve average gaps with no prime in any of them. By the exponential law, a single stretch that long has a chance of about $e^{-12}$, one in 160,000, of containing no prime — and there are over a million gaps below thirty million to try, so a handful of such stretches is exactly what the law predicts.

That arithmetic matters wherever primes are searched for rather than listed. Cryptographic keys are built from primes of hundreds of digits, found by picking a random number and testing its successors until one is prime. Near a number of 300 digits, $\log x$ is about 690, so the search takes about 690 tests on average, halved by skipping even numbers. The worst case is governed by the largest gap, which Cramér’s model puts near $690^2$, nearly half a million, and which nobody can prove is below $x^{0.525}$ — a number of about 160 digits. In practice the average is what matters, and the average is well understood; the worst case is exactly the part of the theory that remains conjecture.

The same distance separates how often long gaps happen from how long they can be. The exponential law says long gaps are rare in a precise way, and the records confirm it. What is missing is a proof that the tail does not have a few exceptions far out — a stretch of $(\log x)^3$ composites somewhere below $x$ — and the upper bounds below cannot exclude them.

What is proved #

Almost nothing near the conjectured size is proved, in either direction.

Upward, the best unconditional bound says every gap after $x$ is less than about $x^{0.525}$, a result of Roger Baker, Glyn Harman and János Pintz from 2001. Even the Riemann hypothesis would only give $\sqrt{x}\,\log x$, still enormously larger than $(\log x)^2$. The distance between the proved bound and the expected truth is a power of $x$ against a power of $\log x$.

Downward, the question is whether gaps can be much longer than the average $\log x$. Erik Westzynthius proved in 1931 that they can: the ratio of gap to $\log p$ is unbounded. Robert Rankin found in 1938 gaps of size $\log x \cdot \log\log x \cdot \log\log\log\log x / (\log\log\log x)^2$ infinitely often, and for seventy-six years nobody improved it by more than a constant factor; Paul Erdős offered a prize for doing so. In 2014, Kevin Ford, Ben Green, Sergei Konyagin and Terence Tao, and independently James Maynard, removed the constant barrier, and together they later improved the bound further. The best lower bound is still far below $(\log x)^2$: it grows only a little faster than $\log x$ itself.

So the true size of the largest gaps, which computation suggests is close to $(\log x)^2$, lies between a lower bound barely above $\log x$ and an upper bound that is a power of $x$. Every record in the figures is consistent with Cramér’s conjecture, and none of them is anywhere near either proved bound.

What the sieve cannot show #

The figures are exact to thirty million: every prime is sieved, every gap measured, every record found. What they cannot show is the limit, and the question is entirely about the limit. A ratio of $0.74$ at thirty million, rising to $0.92$ in searches billions of times larger, is compatible with a limit of one, of $1.12$, or of something else entirely.

The computation is also the smallest possible version of the searches cited above. Thirty million numbers fit in a sieve held in memory at once; the searches to $4 \times 10^{18}$ sieve in segments, one window at a time, and spend most of their effort confirming that no gap in each window beats the current record. The method is the same, and so is its limit: it reports what happens up to the bound, and nothing at all about what happens after it.

The model runs are three samples of a random process, and a different seed would give different staircases; they are drawn to show the scale and the variability, not to estimate anything precisely. And the histogram of normalised gaps pools gaps from ten to thirty million, over which $\log p$ changes by about seven per cent — small enough for the shape, too large for any fine comparison with the exponential law.

Still open: the true size of the largest gaps #

Cramér’s conjecture that the largest gap below $x$ is asymptotically $(\log x)^2$ is open, and so is Granville’s refinement, which contradicts it. Neither side can be tested by computation: the separation between $1$ and $1.12$ appears only at scales where exhaustive search is impossible, and the records found so far do not even reach $1$.

Weaker statements are open too. Whether every gap after $x$ is less than $\sqrt{x}$ — which would imply Legendre’s conjecture of a prime between consecutive squares — is not known, and not even implied by the Riemann hypothesis. The questions about small gaps have moved faster: Yitang Zhang’s 2013 theorem and the work that followed prove that gaps of at most 246 occur infinitely often. The largest gaps have seen no comparable breakthrough on the upper side, and the reason is structural: to show a gap is short, it is enough to find primes; to show every gap is short, one needs control over every interval at once.

What the records say #

The primes are dense enough that the longest wait for one below thirty million is 210 numbers, and regular enough that the records climb along a recognisable curve. They are also structured enough — by divisibility, the property the whole theory of the primes grows from — that the best random model of them misjudges the extremes in a way that can be predicted but not yet checked.

The records are the one statistic of the primes where computation, heuristics and proof sit furthest apart. The data fit a square of a logarithm, the heuristic says a little more than that, and the theorems cannot rule out anything between a little more than a logarithm and a power of the number itself.