Erdős–Rankin construction (covering-congruences translation for large prime gaps)

Statement

The translation. To prove a large gap between consecutive primes — i.e. to find $y$ as large as possible such that some interval $(n, n+y]$ (equivalently $(0,y]$ after shifting) contains no prime — it suffices to exhibit, for a set of primes $p\le x$ ($x$ roughly matched to the target scale of $y$), a choice of residues $a_p\bmod p$ such that every integer $m\in(0,y]$ satisfies $m\equiv a_p\pmod p$ for *at least one* such $p$. A family $\{a_p\bmod p\}_{p\le x}$ with this covering property is called a covering system of congruences for $(0,y]$. If one exists, every $m$ in the interval is divisible by some prime $p\le x<y$ (specifically $m-a_p$, chosen so $a_p$ itself is a multiple of $p$, e.g. $a_p=0$), hence composite, so $(n,n+y]$ is prime-free and $$p_{n+1}-p_n \;>\; y.$$ The construction problem "how large a prime gap can you force" is thereby translated exactly into the combinatorial/sieve-theoretic problem "how large an interval can a covering system built from primes up to $x$ cover" — this is the Erdős–Rankin method.

Classical quantitative form (Rankin 1938, restated in modern notation, e.g. via en.wikipedia.org/wiki/Prime_gap and arxiv.org/abs/2402.07176): there is a constant $c>0$ such that for infinitely many $n$, $$ g_n \;=\; p_{n+1}-p_n \;>\; c\,\frac{\log n\,\log\log n\,\log\log\log\log n}{(\log\log\log n)^2}. $$ Westzynthius (1931) first showed only that $g_n/\log p_n\to\infty$ (i.e. gaps beat any constant multiple of $\log n$, super-logarithmic but with no explicit rate); Erdős (1935) obtained the shape $g_n\gg \log n\log_2 n/(\log_3 n)^2$; Rankin (1938) added the extra $\log_4 n$ factor in the numerator and pinned down $c$ explicitly (later shown to admit any $c<e^\gamma$ by Rankin himself, improved to any $c<2e^\gamma$ by 1997 through several hands — Wikipedia "Prime gap", cross-checked). This $(\log\log\log n)^2$-denominator shape was the world record for 76 years (1938–2014).

Modern record (Ford–Green–Konyagin–Maynard–Tao, "Long gaps between primes," arXiv:1412.5029, J. Amer. Math. Soc. 31(1) (2018) 65–105 — cited in Erdős #4 — unbounded large gaps between primes (Rankin's constant removed)): $$ g_n \;\gg\; \frac{\log n\,\log\log n\,\log\log\log\log n}{\log\log\log n} $$ — one full power of $\log\log\log n$ better in the denominator, obtained by rebuilding the *same* covering-congruence skeleton with modern sieve/random/hypergraph-covering machinery (see Technique below). This resolved Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) (the question of whether Rankin's constant $c$ could be taken arbitrarily large — yes) but the *exponent structure* itself (whether the true growth rate is instead $g_n\gg(\log n)^2$, per the Cramér/Shanks heuristic) remains open.

Facts

- Named after: Erdős, P., "On the difference of consecutive primes," Quart. J. Math. Oxford 6 (1935), 124–128; Rankin, R. A., "The difference between consecutive prime numbers," J. London Math. Soc. 13 (1938), 242–247. Predecessor: Westzynthius, E. (1931), who first broke the "gaps are $O(\log n)$"-type barrier qualitatively without an explicit rate. - All results on large prime gaps since Erdős and Rankin are modifications of this one method — this is stated explicitly by the modern literature (Rassias survey, arxiv.org/abs/2402.07176; also the framing of erdosproblems.com/4 and erdosproblems.com/687, both already in this wiki). No structurally different approach to large gaps has superseded it as of 2026. - Three-range prime partition is the standard skeleton (per arxiv.org/abs/2402.07176's presentation of the modern refinements, structurally tracing back to Rankin): primes $p\le x$ used in the covering system are split by size and given *different jobs*: 1. Small primes ($1<p\le \log^{20}x$, in the modern parametrization): assigned the trivial residue $a_p\equiv 0\pmod p$, sieving out all multiples of $p$ directly — cheap coverage of a fixed proportion of the interval. 2. Medium primes (up to $z=x^{\log_3 x/(4\log_2 x)}$): their combined sieving leaves a residual set that consists almost entirely of $z$-smooth integers (integers with no prime factor $>z$) plus the primes themselves — because smooth-integer counts in the relevant range are asymptotically negligible (de Bruijn/Dickman-function bounds), this residual set is small enough to be finished off cheaply. 3. Large primes ($x<q\le y$): assigned residues via a genuine covering / near-perfect-matching argument (Hall's-theorem-flavored: match residual survivors to available large primes) on what's left after steps 1–2 — this is the step where all post-1938 improvements (Rankin's own refinement, Maynard's sieve-weight import, FGKT's randomization, the final Rödl-nibble unification) actually intervene. - The reusable pipeline is exactly "sieve out a target set via covering congruences, matched to a Dickman/smooth-number density bound on what escapes." This generalizes past prime gaps: any problem of the shape "find a long run of integers all satisfying some divisibility-detectable composite-type property" is a candidate for the same translation. The Jacobsthal function problem Erdős #687 — estimate the Jacobsthal covering function Y(x) (largest $y$ such that residues $a_p\bmod p$, $p\le x$, cover $[1,y]$) is the *pure* combinatorial core of the method with the prime-density sieve step stripped away — it is literally "how good can an Erdős–Rankin covering system be," open, still governed by the same [FGKMT18] bound. - The 2014–2018 breakthroughs did not change the translation, only the covering-system construction. Maynard's arXiv:1408.5110 imports GPY/Maynard-Tao *small*-gap sieve weights to choose residues non-greedily (Selberg-optimized rather than density-greedy); Ford–Green–Konyagin–Tao's arXiv:1408.4505 instead randomizes the residue choice and controls variance via long arithmetic progressions of primes; the unifying arXiv:1412.5029 recasts residue selection as covering the edges of an auxiliary hypergraph (vertices = target-interval integers, edges = arithmetic progressions killed by each prime) and applies a Rödl-nibble / semi-random hypergraph-covering theorem (Pippenger–Spencer-style, adapted with per-round reweighting for non-uniform edge sizes) to squeeze out the extra $\log\log\log n$ factor. See Erdős #4 — unbounded large gaps between primes (Rankin's constant removed)'s Solution section for the full derivation chain (already in this wiki).

Technique

WHY it works (the mechanism). Primality is a "positive" property (hard to force directly), but compositeness is a "union of arithmetic-progression" property — an integer $m$ is composite as soon as it lands in *any* fixed nonzero residue class mod some prime $\le\sqrt m$ (or, cheaper, mod any prime dividing it at all). Covering the *entire* target interval by residue classes mod primes $\le x$ is therefore a purely combinatorial condition (a covering system) that is *sufficient* to certify "every integer here is composite," sidestepping any need to reason about primality directly. The size $y$ of interval coverable is controlled by a resource-accounting tension: more primes $p\le x$ give more "covering power" (each residue class mod $p$ kills a $1/p$-density slice), but $\sum_{p\le x}1/p\sim\log\log x$ grows only doubly-logarithmically (Mertens), so covering an interval of length $y\gg x$ requires *reusing* primes cleverly (assigning big primes $q$ close to $y$ to cover small residual leftover sets one-for-one, à la a matching argument) rather than naive union-bound coverage — this is exactly why the bound has the layered $\log\log\log\log n/(\log\log\log n)^2$-type shape rather than something simpler: it's the outcome of an explicit optimization balancing the density loss at each of the three prime ranges (small/medium/large) against each other.

HOW to use it to prove things (recombination steps)

1. Fix target scale. Decide the interval length $y$ you want to certify prime-free, and pick $x$ (the largest prime modulus you'll use) at the matched analytic scale — classically $x\approx y$ up to log factors; the precise relation is itself the thing being optimized. 2. Partition primes $p\le x$ into ranges by role: small primes get trivial residue $0\bmod p$ (cheap bulk coverage); medium primes' leftover is bounded by a smooth-number density estimate (Dickman $\rho$-function / de Bruijn asymptotics — the escaping residual set is asymptotically negligible); large primes $q\in(x,y]$ are matched one-to-one (or via a nibble/random process) against the *specific* surviving elements from steps 1–2. 3. Certify the covering — either combinatorially exactly (classical Rankin: explicit residue choice + counting), by a Selberg-sieve-weighted non-greedy optimization (Maynard's route, importing the small-gap GPY/Maynard-Tao sieve machinery), by randomization with variance control via long APs of primes (Ford–Green–Konyagin–Tao's route), or by casting it as a hypergraph-covering problem and invoking a Rödl-nibble/Pippenger–Spencer-style theorem (the state-of-the-art unification, arXiv:1412.5029). 4. Read off the gap bound: the largest $y$ your covering system provably covers is a valid *lower bound* on $\limsup g_n/(\text{scale term})$ — the translation from "covering system exists" to "prime gap $>y$ exists" is immediate and lossless (step 1's definition), so all the technical work is in maximizing coverable $y$, not in the number-theoretic transport itself. 5. **When it does *not* directly apply**: (a) it only produces *lower* bounds on maximal gaps (existence of *some* long prime-free interval); it says nothing about *upper* bounds on gaps (that's sieve-theoretic zero-density / Baker–Harman–Pintz-type territory, a different toolkit, [BHP01] $g_n\ll n^{0.525+o(1)}$); (b) it is intrinsically a *worst-case/extremal* construction — it does not control the *typical* gap or gap *distribution*, only that arbitrarily large gaps recur infinitely often; (c) the method's ceiling (absent further sieve-theoretic input) is set by how efficiently the covering system can be built at each of the three prime ranges — every post-1938 improvement is a strictly better construction at the "large primes" (matching/covering) stage, not a different translation.

WHEN it applies: any problem of the form "show a long run/interval/structure exists that avoids a divisibility-detectable positive property (primality, being $B_h$-set-compatible, etc.) by exhibiting a covering system of residue classes mod small primes/moduli, with the escaping residual controlled by a density (smooth-number, sieve, or entropy) bound." Prime gaps are the canonical and originating instance; the same skeleton (small-modulus trivial coverage + medium-modulus density bound + large-modulus matching/nibble) is the reusable "engine" whenever a problem reduces to a covering-system existence question, e.g. Erdős #687 — estimate the Jacobsthal covering function Y(x) (Jacobsthal function, the pure covering-system core with no sieve wrapper needed).

Related

- Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) — "unbounded large gaps between primes (Rankin's constant removed)": SOLVED; the direct target application of this technique, and the source of the fullest write-up (already in this wiki) of how modern sieve/random/hypergraph-covering machinery is grafted onto the classical Erdős–Rankin skeleton to remove the bound on Rankin's constant $c$ and then improve the exponent. - Erdős #687 — estimate the Jacobsthal covering function Y(x) — Jacobsthal function $Y(x)$ (largest $y$ covered by a covering system on primes $\le x$): OPEN; the pure combinatorial core of this technique stripped of the prime-density sieve wrapper, sharing the exact same [FGKMT18] state-of-the-art bound. - Concept referenced but not yet its own page: "covering systems of congruences" (the general combinatorial object — residues $a_p\bmod p$ covering $\mathbb Z$ or an interval — underlying both Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) and Erdős #687 — estimate the Jacobsthal covering function Y(x), also central to unrelated territory like Erdős's covering-system conjectures on odd covering systems, resolved by Balister–Bollobás–Morris–Sahasrabudhe, arXiv:2211.01417) and "sieve theory" / "Rödl nibble" (the GPY/Maynard-Tao small-gap sieve and the Pippenger–Spencer semi-random hypergraph-covering theorem, both imported wholesale into this construction by the 2014–2018 improvements) — flagged here as natural next concept pages, both already forward-linked from problems/4.md and problems/687.md in this wiki. - Finite-field / projective-plane constructions for extremal additive sets — a structurally different "explicit algebraic construction beats probabilistic method" technique family in extremal additive combinatorics; contrasts instructively with Erdős–Rankin, which is instead a *density/covering* argument whose modern improvements come from importing sieve-theoretic and semi-random (not algebraic) machinery.