Large Gaps Between Primes

The primes thin out: near a large number x they arrive with density about 1/\ln x, so the average gap between one prime and the next is roughly \ln x (the distribution of primes). But an average hides its outliers. This page asks the opposite of the twin-prime question: not how small can a gap be, but how large? After a prime, how long a desert of composite numbers can you be forced to cross before the next prime appears — and where does the truth sit between what we can prove and what we believe?

It is a story with a punchline in 2014, an Erdős cheque for \$10{,}000, and a still-yawning gap of its own: between the best proven lower bound and the conjectured answer lies almost the entire distance from \ln x to (\ln x)^2.

The quantity we care about: the maximal gap

Write the primes in order p_1 = 2, p_2 = 3, p_3 = 5, \dots The maximal prime gap up to x collects the largest jump anywhere below x:

G(x) \;=\; \max_{p_{n+1}\le x}\bigl(p_{n+1}-p_n\bigr).

It is the length of the longest run of consecutive composite numbers you will meet on the way up to x, plus one. As x grows, G(x) can only stay the same or step up.

A cheap first fact: G(x) can never be smaller than the average gap. If every gap below x were short, there would be too many primes — contradicting the prime number theorem. Making that precise gives the easy lower bound

G(x) \;\ge\; \bigl(1+o(1)\bigr)\ln x,

so the maximal gap is at least a typical gap. The whole subject is the struggle to push this lower bound far above \ln x — and to guess how far up the truth really lives.

The easy construction: factorials manufacture a gap on demand

Here is a trick that produces a prime-free stretch of any length you name, with zero primality testing. Fix n and look at the n-1 consecutive numbers

n!+2,\;\; n!+3,\;\; n!+4,\;\; \dots,\;\; n!+n.

The number n!+k (for 2\le k\le n) is divisible by k, because k divides both n! and k. Every one of them is composite — a guaranteed run of n-1 non-primes, so a prime gap of length at least n straddles them.

Worked example — a gap of length at least 100. Take n = 101. The 100 consecutive integers

101!+2,\;\; 101!+3,\;\; \dots,\;\; 101!+101

are all composite (101!+k is divisible by k), so somewhere around 101! there is a prime gap of length at least 101. That settles existence: gaps of every size occur.

But now weigh it honestly. The numbers involved are around 101! \approx 9.4\times10^{159} — a 160-digit monster — with

\ln(101!) \;\approx\; 367.

The average gap out there is \ln x \approx 367. Our hard-won gap of 101 is not just unimpressive — it is below average! The factorial trick proves large gaps exist, but the gap it delivers, measured against the local scale \ln x, is a feeble 101/367 \approx 0.28 of a typical gap. To beat the average by a wide margin takes real work — and that work is the rest of this page.

Two traps hide in the factorial trick. First, it exhibits a gap of length \ge 100 near 101!, but that is not the first place a gap of 100 appears. The earliest gap of at least 100 actually shows up after the prime 396{,}733 (a 6-digit number, not a 160-digit one). The construction locates a big gap; it says nothing about the smallest number where such a gap first occurs.

Second, and more sobering: even the deepest theorems we can prove only push G(x) a little way above the average \ln x — by a factor built from iterated logarithms, which crawl towards infinity so slowly they are practically constant. Meanwhile everyone believes the true answer is about (\ln x)^2. So the proven lower bound sits just barely over \ln x, while the conjecture floats an entire factor of \ln x higher. That chasm is the open problem.

The classical lower bound: Westzynthius, Erdős, Rankin

To beat the average badly, you stop using factorials and start using a sieve. The idea, born with Westzynthius in 1931 and sharpened by Erdős in 1935, is to knock out an interval of integers by choosing, for each small prime q, a clever residue class to forbid — covering a long stretch far more efficiently than n! ever could. Rankin, in 1938, tuned the choice optimally and produced the bound that stood, essentially untouched in shape, for 76 years.

There is a constant c > 0 such that, for large x,

G(x) \;\gg\; \ln x \cdot \frac{\ln\ln x \,\cdot\, \ln\ln\ln\ln x}{(\ln\ln\ln x)^2}.

Rankin could get the shape right, but the constant c he could prove was small. Improving that constant became a celebrated sport — and Erdős put money on it.

Paul Erdős famously offered cash bounties for problems he loved, from \$25 up to hundreds. For pushing the constant in Rankin's bound to infinity — showing the surplus over the average could be made arbitrarily large — he offered \$10{,}000, the biggest Erdős prize on record. He suspected it might be very hard. He was right: the cheque went unclaimed for decades, right up to his death in 1996 and beyond.

It was finally won in 2014 — nearly 80 years after he posed it. Terence Tao, part of one of the two winning teams, has said settling an Erdős prize problem carries a particular thrill: you are, in a small way, still working with Erdős.

The 2014 breakthrough — and the 2018 sequel

In 2014, two groups cracked the constant independently and simultaneously: Ford, Green, Konyagin and Tao on one side, and James Maynard on the other. Both showed that the constant c in Rankin's bound can be taken as large as you please — the surplus over the average is unbounded — collecting Erdős's \$10{,}000. The new ingredient was the same flexible sieve machinery Maynard had just used to crack small gaps: the two extremes of the prime-gap world fell to one toolkit.

Then the four-plus-one authors joined forces. In 2018, Ford, Green, Konyagin, Maynard and Tao improved the shape itself for the first time since Rankin, shaving off a logarithm from the denominator:

For infinitely many x,

G(x) \;\gg\; \ln x \cdot \frac{\ln\ln x \,\cdot\, \ln\ln\ln\ln x}{\ln\ln\ln x}.

It is a triumph — and yet look at what it buys. The whole improvement over the average is a product of triple and quadruple logarithms. Multiply \ln x by that and you are still, for any number you could ever write down, only a modest multiple of the average. The conjectured answer is a full power of \ln x larger.

What we believe: Cramér's conjecture

In 1936 Harald Cramér modelled the primes as if each integer m were "prime" independently with probability 1/\ln m — a probabilistic model of the primes. In that random world the longest gap up to x behaves like (\ln x)^2. Transported back to the real primes, this is

\limsup_{n\to\infty}\frac{p_{n+1}-p_n}{(\ln p_n)^2} \;=\; 1, \qquad\text{i.e.}\qquad G(x)\sim(\ln x)^2.

Note the leap: the proven lower bound is barely a whisker above \ln x, while Cramér's guess is (\ln x)^2 — squared. The entire research programme lives inside that gap between \ln x and (\ln x)^2.

Cramér's model is a beautiful heuristic but not gospel. Andrew Granville noticed the real primes avoid small factors in a correlated way the naïve coin-flip model ignores, and argued the true \limsup should be larger — at least 2e^{-\gamma}\approx 1.1229, where \gamma is the Euler–Mascheroni constant. So the refined belief is

\limsup_{n\to\infty}\frac{p_{n+1}-p_n}{(\ln p_n)^2} \;\ge\; 2e^{-\gamma} \approx 1.1229\ldots

Either way, the shape is (\ln x)^2. And either way, nobody can prove even that G(x)/(\ln x)^2 stays bounded, let alone tends to a limit.

Seeing it: records against the average and the conjecture

Sieve the primes up to 100{,}000 and track the running record G(x) — the largest gap seen so far. Below it sits the average gap \ln x; above it, Cramér's conjectured ceiling (\ln x)^2. The record staircase climbs well above the average, exactly as Rankin promised — yet stays comfortably beneath (\ln x)^2, exactly as Cramér's upper guess predicts.

This modest range only hints at the asymptotics — the iterated logarithms of Rankin's bound are far too sluggish to see here — but the sandwich is already visible: the true record lives between the average and its square, and the enormous white space between the middle and top curves is precisely the territory no proof has yet reached.

We can compute record gaps up to x around 10^{18}, and they do hug (\ln x)^2 handsomely — strong numerical support for Cramér. But computation checks finitely many cases; a \limsup is a statement about all the infinitely many primes still to come. Proving G(x)\gg(\ln x)^2 would need a construction that forces a genuinely enormous gap, and every known method (sieves included) leaks efficiency the moment it tries to reach the (\ln x)^2 scale. The upper direction is even worse: proving G(x)\ll(\ln x)^2 would say the primes are never too clumped, and that is far beyond the Riemann Hypothesis — RH alone only gives G(x)\ll\sqrt{x}\,\ln x, hopelessly weak. The records are easy to see and murderously hard to explain.