Erdős #4 — unbounded large gaps between primes (Rankin's constant removed)

Statement

Is it true that for every $C>0$ there are infinitely many $n$ such that $$p_{n+1}-p_n \;>\; C\,\frac{\log\log n\,\log\log\log\log n}{(\log\log\log n)^2}\,\log n\ ?$$

Equivalently: is the constant in Rankin's 1938 lower bound for the largest prime gap unbounded, i.e. can the implied constant in $$\max_{p_{n+1}\le X}(p_{n+1}-p_n) \;\gg\; \frac{\log X\log\log X\log\log\log\log X}{(\log\log\log X)^2}$$ be taken arbitrarily large? (erdosproblems.com/4, fetched 2026-07-02.)

Facts

- Status: PROVED (erdosproblems.com/4 marks it "solved in the affirmative"). Answer: yes, the constant is unbounded. - Origin: R. A. Rankin, "The difference between consecutive prime numbers," J. London Math. Soc. 13 (1938) [Ra38], first proved the shape of the bound above held for *some* fixed constant $C>0$. Erdős then asked whether $C$ could be taken arbitrarily large, restating the question across [Er55c] [Er57] [Er61] [Er65b] [Er81k] [Er82e] [Er90] [Er97c] [Er97f] [Va99] (erdosproblems.com/4). - Prize: originally \$10000 — "one of Erdős's largest ever" per erdosproblems.com's Prizes page. In [Er97c] Erdős revised the value of *this* question to \$5000, and reserved the full \$10000 for the much stronger claim of a lower bound $p_{n+1}-p_n>(\log n)^{1+c}$ for some $c>0$ — a separate, still-open target (erdosproblems.com/4). - Solved independently, same month, by two groups (August 2014): James Maynard, "Large gaps between primes," arXiv:1408.5110, Ann. of Math. 183 (2016); and Kevin Ford, Ben Green, Sergei Konyagin, Terence Tao, "Large gaps between consecutive prime numbers," arXiv:1408.4505 (erdosproblems.com/4 cites both as [Ma16] and [FGKT16]). - Best bound (current record), obtained when all five authors combined forces: Ford, Green, Konyagin, Maynard, Tao, "Long gaps between primes," arXiv:1412.5029, J. Amer. Math. Soc. 31(1) (2018) 65-105 — there are infinitely many $n$ with $$p_{n+1}-p_n \;\gg\; \frac{\log\log n\,\log\log\log\log n}{\log\log\log n}\,\log n,$$ i.e. one power of $\log\log\log n$ better than the original Erdős-question exponent (denominator $\log\log\log n$ instead of $(\log\log\log n)^2$) — erdosproblems.com/4, arxiv.org/abs/1412.5029. - Matching upper bound (how large gaps *can't* be, the other side of the question): Baker, Harman, Pintz, [BHP01] — $p_{n+1}-p_n \ll n^{0.525+o(1)}$ — leaves a huge gap to the truth; the *believed* truth per erdosproblems.com/4 is a much stronger lower bound $\gg(\log n)^2$ (the Cramér/Shanks-type heuristic), which remains open and is exactly the target of the still-unclaimed \$10000 half of the prize. - Directly related sibling problem: Erdős #687 — estimate the Jacobsthal covering function Y(x) — the Jacobsthal-function question ($Y(x)$: largest $y$ such that congruence classes $a_p\bmod p$ for $p\le x$ cover all of $[1,y]$) is still open, and the *same* [FGKMT18] paper gives its best-known lower bound $Y(x)\gg x\log x\log\log\log x/\log\log x$, also improving Rankin — the two problems share essentially one covering-system construction (erdosproblems.com/687). - Discussed as problem A8 of Guy's collection [Gu04] (erdosproblems.com/4).

Solution

Answer: YES — Rankin's constant is unbounded; in fact the exponent of $\log\log\log n$ in the denominator can be improved from 2 to 1.

**The transferable technique — upgrade the classical Erdős–Rankin covering-system sieve with modern *small*-gap sieve weights, then push further with a Rödl-nibble/semi-random hypergraph-covering construction:**

1. Classical Erdős–Rankin skeleton (Erdős–Rankin construction (covering-congruences translation for large prime gaps), Rankin 1938): to force a long prime-free interval around $n$, choose, for each small prime $p$ up to some bound, a residue class $a_p\bmod p$ such that "most" of an interval $[n,n+y]$ gets hit (is composite) via $n+k\equiv a_p\pmod p$ for *some* $p$. This is a covering system of congruences (Covering systems of congruences): the surviving, uncovered integers in the interval are exactly the candidates that could still be prime, and one needs to also control how many of those survivors are *actually* prime via a sieve/Buchstab-function estimate on the density of numbers free of small prime factors. Rankin's specific choice of primes/residues fixed one constant $C$; the whole 1930s–1990s literature (Rankin, Schönhage, Ricci, Jacobsthal-type refinements) only ever improved lower-order terms, never the exponent structure, because the *density loss* from picking residues greedily was believed unavoidable. 2. Maynard's move (arXiv:1408.5110): import the sieve weights developed for the *opposite* extreme — GPY/Maynard-Tao's multidimensional sieve for small gaps between primes (the machinery behind bounded gaps, Sieve theory: Eratosthenes–Legendre, Brun, Selberg, Turán, and the large sieve) — and repurpose them to choose the covering residues $a_p$ *non-greedily*, weighting which residue class to pick per prime by a Selberg-type sieve optimization rather than a naive density argument. This squeezes strictly more of the interval into "covered," breaking through the constant $C$ that had capped every prior Erdős–Rankin-style construction, and shows $C$ can be taken arbitrarily large. 3. Ford–Green–Konyagin–Tao's independent move (arXiv:1408.4505): attacks the same barrier from a different angle — a random (rather than greedy or sieve-weighted) choice of covering residues combined with input on long arithmetic progressions of primes, also removing the bound on $C$; the two Aug-2014 papers arrived at essentially the same headline result by genuinely different routes in the same month. 4. **The Dec-2014 unification and record (Pippenger–Spencer hypergraph covering theorem (and the FGKMT generalization), Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings, arXiv:1412.5029): all five authors combine forces and reformulate the residue-selection problem as covering the edges of an auxiliary hypergraph (vertices = integers in the target window, edges = arithmetic progressions killed by each prime's residue choice). They generalize a hypergraph covering theorem of Pippenger–Spencer (proved via the Rödl nibble** / semi-random method Semi-random method (Rödl nibble) — alias page; canonical content at concept/rodl-nibble): repeatedly select small random sub-collections of edges ("nibbles") to cover the hypergraph efficiently, iteratively reweighting the probability distribution on edges after each nibble to compensate for bias introduced by the (crucially, *non-uniform-size*) edges — the key technical innovation, since the classical Pippenger–Spencer theorem assumes uniform edge sizes and prime-covering edges are not uniform. This buys the extra $\log\log\log n$ factor, taking the exponent in the denominator from $2$ down to $1$ (terrytao.wordpress.com/2014/12/16/long-gaps-between-primes). 5. Portable takeaway. Whenever a problem is "find a long interval avoiding a property defined by residues/small-prime-divisibility," the reusable pipeline is: (a) cast residue selection as a hypergraph covering problem; (b) if greedy/deterministic covering saturates at some constant, try (i) importing an *unrelated* sieve's optimized weights (Maynard's route) or (ii) randomizing the choice and controlling variance via long-AP or covering-system inputs (FGKT's route); (c) if edges are non-uniform in size, adapt Rödl-nibble hypergraph-covering (Pippenger–Spencer) with per-round reweighting rather than assuming uniformity — this is exactly the move that also gives the current-best bound on the sibling Jacobsthal-function problem Erdős #687 — estimate the Jacobsthal covering function Y(x), since both reduce to the same covering-system core.

Related

- Erdős #687 — estimate the Jacobsthal covering function Y(x) — Jacobsthal-function problem (still open): "largest $y$ such that congruence classes $a_p\bmod p$, $p\le x$, cover $[1,y]$." Same covering-system core; [FGKMT18]'s hypergraph-covering/Rödl-nibble machinery gives its current best lower bound too, directly transplanted from this problem's solution. - Erdős–Rankin construction (covering-congruences translation for large prime gaps) — the classical 1938 covering-system-plus-sieve skeleton every subsequent improvement (including the full resolution here) is built on top of. - Covering systems of congruences — the combinatorial object (residues $a_p\bmod p$ covering an interval) that both problem #4 and #687 reduce to. - Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings / Semi-random method (Rödl nibble) — alias page; canonical content at concept/rodl-nibble — the Pippenger–Spencer-style semi-random hypergraph-covering technique, generalized with per-round reweighting to handle non-uniform edges, giving the final record bound (arXiv:1412.5029). - Pippenger–Spencer hypergraph covering theorem (and the FGKMT generalization) — the abstract combinatorial engine (residue selection = covering a hypergraph) that unifies the Aug-2014 Maynard and FGKT proofs into the stronger Dec-2014 result. - Sieve theory: Eratosthenes–Legendre, Brun, Selberg, Turán, and the large sieve — the GPY/Maynard-Tao multidimensional sieve for *small* gaps, repurposed by Maynard in the opposite direction (large gaps) as the key new ingredient in arXiv:1408.5110.