Sieve theory: Eratosthenes–Legendre, Brun, Selberg, Turán, and the large sieve

Statement

Sieve theory is a family of techniques in analytic number theory for estimating the size of a "sifted" set — a sequence of integers with elements satisfying a prescribed divisibility/congruence condition removed at each of a set of primes $P$ up to a bound $z$ (en.wikipedia.org/wiki/Sieve_theory). The prototype is the Sieve of Eratosthenes: start from $\mathcal A \subseteq \{1,\dots,x\}$, remove multiples of each prime $p \le z$, and estimate the sifting function $$S(\mathcal A, P, z) = \bigl|\{a \in \mathcal A : \gcd(a, P(z)) = 1\}\bigr|,\qquad P(z) = \prod_{p \in P,\, p\le z} p.$$ Legendre's identity rewrites this exactly via Möbius inversion, $S(\mathcal A,P,z) = \sum_{d\mid P(z)} \mu(d)\,|\mathcal A_d|$, but this exact inclusion–exclusion has $2^{\pi(z)}$ terms and its error accumulates catastrophically once $z$ is not tiny compared to $x$ — the entire theory is about *truncating* this identity while controlling the resulting error. Viggo Brun coined the term "sieve" in 1915 and introduced the key innovation: replace the Möbius-function coefficients by a restricted weight sequence (upper- and lower-bound weights) so the truncated sum still sandwiches the true count (en.wikipedia.org/wiki/Sieve_theory).

Turán's sieve (Turán, 1934) is the *combinatorial/second-moment* branch: for $\mathcal A\subseteq\{1,\dots,x\}$, primes $P$, threshold $z$, and a multiplicative density function $f$ with $0\le f(d)\le 1$ such that $|\mathcal A_p| = \tfrac1{f(p)}X + R_p$ (with $X=|\mathcal A|$) and $|\mathcal A_{pq}| = \tfrac1{f(p)f(q)}X + R_{p,q}$ for distinct primes $p,q \mid P(z)$, set $U(z) = \sum_{p\mid P(z)} f(p)$. Then (en.wikipedia.org/wiki/Turán_sieve, exact statement): $$S(\mathcal A, P, z) \;\le\; \frac{X}{U(z)} \;+\; \frac{2}{U(z)}\sum_{p\mid P(z)} |R_p| \;+\; \frac{1}{U(z)^2}\sum_{p,q\mid P(z)} |R_{p,q}|.$$ This is derived from a Chebyshev/Cauchy–Schwarz-style second-moment bound on the number of prime divisors of $a\in\mathcal A$ below $z$, not from the finer Möbius/Legendre inclusion–exclusion — it is structurally the *same move* as the Paley–Zygmund/Chebyshev second-moment method (see Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs), applied to $\omega(n)$-type counting functions rather than to a general random variable; Turán's original 1934 paper is in fact the founding instance cross-listed in that page's provenance.

The large sieve (Linnik 1941; Rényi; Roth and Bombieri independently, early 1960s; simplified by Gallagher) is a *different* (harmonic-analytic/duality) branch, so named because it can remove *many* (up to a positive proportion of) residue classes mod each prime, unlike the classical small sieves which only remove $O(1)$ classes per prime (en.wikipedia.org/wiki/Large_sieve). Its two clean forms:

- Analytic form. If $\alpha_1,\dots,\alpha_R \in \mathbb R/\mathbb Z$ are $\delta$-separated ($\|\alpha_j-\alpha_k\|\ge\delta$ for $j\ne k$) and $a_n\in\mathbb C$ for $1\le n\le N$, then $$\sum_{j=1}^{R} \Bigl|\sum_{n=1}^{N} a_n\, e(\alpha_j n)\Bigr|^2 \;\le\; (N+\delta^{-1}) \sum_{n=1}^N |a_n|^2.$$ - Arithmetic form (Farey fractions $a/q$, $q\le Q$, $\gcd(a,q)=1$): $$\sum_{q\le Q} \sum_{\substack{a=1\\ \gcd(a,q)=1}}^{q} \Bigl|\sum_{n\le N} a_n\, e(an/q)\Bigr|^2 \;\ll\; (N+Q^2) \sum_{n\le N} |a_n|^2.$$ The constant $N+Q^2$ (resp. $N+\delta^{-1}$) is essentially optimal, proved independently by Selberg and by Montgomery–Vaughan (1973), refining an earlier Davenport–Halberstam bound (people.math.ethz.ch/~kowalski/remarks-large-sieve.pdf). Proofs go via either an *approximate Plancherel inequality* (poor equidistribution mod $p$ forces large Fourier coefficients, contradicting Plancherel unless $|\mathcal A|$ is small) or the *duality principle* (operator norm = adjoint norm) (en.wikipedia.org/wiki/Large_sieve).

Landmark corollaries of the large sieve

- Brun–Titchmarsh theorem: $\pi(x;q,a) \le \dfrac{2x}{\varphi(q)\log(x/q)}$ for all $q<x$ — an unconditional, GRH-free upper bound on primes in an arithmetic progression, proved via the large sieve by Montgomery–Vaughan (1973), sharpening Brun's and Titchmarsh's earlier weaker (extra-constant-factor) versions (en.wikipedia.org/wiki/Brun–Titchmarsh_theorem). - Bombieri–Vinogradov theorem (mid-1960s): for $x^{1/2}\log^{-A}x \le Q \le x^{1/2}$, $$\sum_{q\le Q} \max_{\gcd(a,q)=1} \Bigl|\pi(x;q,a) - \frac{\operatorname{li}(x)}{\varphi(q)}\Bigr| \;\ll_A\; \frac{x^{1/2}\,Q\,(\log x)^5}{1}$$ i.e. the error term, *averaged over moduli $q\le x^{1/2-\varepsilon}$*, is as small as under the Generalized Riemann Hypothesis, even though no individual modulus is controlled that well unconditionally (en.wikipedia.org/wiki/Bombieri–Vinogradov_theorem). This "GRH on average" phenomenon, built on the large sieve, is the single most-used black box feeding sieve-theoretic prime-gap and Goldbach-type results (Chen's theorem, Zhang's/Maynard–Tao's bounded-gaps theorems).

The parity problem is the fundamental *limitation* shared by all sieve methods (Brun, Selberg, large sieve alike, en.wikipedia.org/wiki/Sieve_theory): a sieve upper bound for $S(\mathcal A,P,z)$ that is asymptotically tight cannot, by itself, distinguish between integers with an even number of prime factors and integers with an odd number — so pure sieve methods can never *unconditionally* prove a set contains primes (odd $\Omega(n)=1$) when they can equally "explain" the count via numbers with two prime factors. This is why Chen's theorem (1966) proves "$p$, $p+2$ prime-or-semiprime" rather than the twin-prime conjecture itself, and it is the named obstruction in this wiki's problems/687.md and problems/970.md discussions of Iwaniec's 1978 Jacobsthal-function bound.

Facts

- Taxonomy (en.wikipedia.org/wiki/Sieve_theory): Brun sieve (bounded-degree truncated inclusion–exclusion, alternating upper/lower weight sequences) → Selberg sieve (optimal *upper*-bound sieve via a positive-semidefinite quadratic form in Möbius-type weights $\lambda_d$, minimized subject to $\lambda_1=1$) → large sieve (harmonic-analytic, controls many residues per modulus at once) → Goldston–Pintz–Yıldırım / Maynard–Tao multidimensional sieve (2005–2013, small-gaps-between-primes machinery). - Brun's theorem: the sum of reciprocals of twin primes converges (Brun's constant) — the founding application of Brun's own sieve, and historically the first proof that a sieve upper bound can extract genuine arithmetic information even without resolving the underlying conjecture. - Selberg's sieve underlies Chen's theorem (1966: infinitely many primes $p$ with $p+2$ having at most 2 prime factors) and, in combinatorially extended (Maynard–Tao "multidimensional sieve") form, the 2013–2014 bounded-gaps-between-primes breakthroughs (Zhang; Maynard; Polymath8) — see Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) for Maynard's *repurposing* of this same multidimensional-sieve machinery in the opposite (large-gaps) direction. - Turán's own headline application: a new, simple proof (1934) of the Hardy–Ramanujan theorem (1917) that the normal order of $\omega(n)$ (number of distinct prime factors of $n$) is $\log\log n$ — historically credited as the starting point of *probabilistic number theory*, a direct ancestor of the Erdős–Kac theorem (Gaussian fluctuation of $\omega(n)$ around $\log\log n$). - Turán sieve, second application: almost all integer polynomials, ordered by height, are irreducible (en.wikipedia.org/wiki/Turán_sieve) — a "typical structure" (normal-order-flavored) statement, the Turán sieve's other recurring use case alongside normal-order theorems. - Motohashi's 1973 refinement of Brun–Titchmarsh for small moduli $q \le x^{9/20}$ exploits *bilinear structure* in the Selberg-sieve error term — the same bilinear/Type-I–Type-II decomposition idea that later became central to Iwaniec's and then Zhang's/Maynard's sieve-with-equidistribution-input machinery (en.wikipedia.org/wiki/Brun–Titchmarsh_theorem). - The large sieve's name is a slight misnomer for its modern use: despite being introduced for problems where a large proportion of residues are removed (Linnik's original quadratic-non-residue application), it is now the standard tool even in classical small-sieve situations, whenever "on-average-over-moduli" control (rather than a single-modulus bound) suffices — this is precisely the Bombieri–Vinogradov mechanism (en.wikipedia.org/wiki/Large_sieve). - In this wiki's own problem corpus, Erdős #687 — estimate the Jacobsthal covering function Y(x) and Jacobsthal's function h(k) — finiteness and near-matching two-sided bounds (Jacobsthal's function $h(k)$/$Y(x)$) both hinge on whether Iwaniec's 1978 elementary/sieve-counting upper bound $Y(x)\ll x^2$ can be tightened by modern large-sieve or Turán-sieve inequalities (as used in Hough's distortion method, arXiv:1307.0874) — an explicitly *open* transfer target flagged in problems/687.md's own provenance. Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) documents Maynard's transplant of GPY/Maynard-Tao small-gap sieve weights into the large-gap Erdős–Rankin construction (arXiv:1408.5110). Erdős #689 — double covering by prime residues: all-moduli case SOLVED (erdos/1205, F(x)~log x); primes-only case OPEN with two 2026 proof claims unverified contrasts classical sieve-theoretic covering-multiplicity bottlenecks against the modern hypergraph-nibble replacement. Erdős #2 — minimum modulus of a covering system cannot be arbitrarily large and Erdős #688 — the ε_n covering variant: how few large primes can cover [1,n]? both invoke classical sieve/density bounds as the (insufficient, pre-modern) tool for covering-system minimum-modulus and Jacobsthal-type questions.

HOW each branch is used to prove things (recombination steps)

1. Pick the sifting set and the sieve dimension. Frame the target ("integers free of small prime factors," "primes in an AP," "$n$ with $\omega(n)$ near $\log\log n$," "polynomials with a rational root") as $S(\mathcal A, P, z)$ for an explicit $\mathcal A$, prime set $P$, and threshold $z$. 2. Choose the branch by what you need: - Need a convergence/finiteness result (e.g. $\sum 1/p_{\text{twin}} < \infty$) with modest loss ⇒ Brun's sieve (truncated alternating inclusion–exclusion, controllable error via bounded-length Möbius truncation). - Need the best possible upper bound on a sifted count (near-primes, Chen's theorem, small-gap sieve weights) ⇒ Selberg's sieve (optimize a quadratic form in weights $\lambda_d$ subject to $\lambda_1=1$, $\lambda_d=0$ for $d>z$; the resulting $S(\mathcal A,P,z) \le X/\text{(local densities)} + \text{error}$ is provably best-possible among diagonal quadratic-form sieves). - Need an "almost all" / normal-order / typical-structure statement (Hardy–Ramanujan, polynomial irreducibility) where a variance/Chebyshev-type bound suffices and simplicity matters more than sharp constants ⇒ Turán's sieve (second-moment inequality on $S(\mathcal A,P,z)$ directly, no Möbius optimization needed — see Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs for the shared mechanism). - Need control averaged over many moduli $q\le Q$ simultaneously, at a strength unconditionally matching GRH-averaged behavior (primes-in-AP error terms feeding bounded-gap or Goldbach-type theorems) ⇒ the large sieve (Fourier/duality inequality, feeds Bombieri–Vinogradov, Brun–Titchmarsh). 3. Extract the arithmetic content via the branch's central inequality (Legendre/Möbius truncation for Brun; the $\lambda_d$ quadratic form for Selberg; the $S(\mathcal A,P,z)\le X/U(z)+\text{error}$ bound above for Turán; the $(N+Q^2)$-type $L^2$ bound for the large sieve), then transport back to the original counting problem by unwinding the density function $f$ or the exponential-sum encoding. 4. Know the ceiling before starting: if the target statement is equivalent to "a specific sifted set is *nonempty*" purely from an asymptotically-tight upper bound with no complementary lower bound (the parity problem), no combination of these four branches alone will close it unconditionally — a genuinely different input is required (Rödl-nibble/hypergraph-covering machinery, as in Erdős #689 — double covering by prime residues: all-moduli case SOLVED (erdos/1205, F(x)~log x); primes-only case OPEN with two 2026 proof claims unverified; algebraic equidistribution/Type-I–Type-II inputs, as in the GPY/Maynard bounded-gaps route; or assuming GRH/Elliott–Halberstam to remove the averaging in Bombieri–Vinogradov).

WHEN it applies: any problem reducible to counting (or bounding) integers, primes, or arithmetic objects satisfying a *local* (per-prime or per-modulus) avoidance/congruence condition, over a *global* range — prime gaps, primes in progressions, almost-prime/near-prime constructions, distribution/normal-order of arithmetic functions ($\omega(n)$, $\Omega(n)$), covering systems and Jacobsthal-type functions, irreducibility of "random" polynomials, and (via the large sieve's duality form) any $L^2$-bounded exponential-sum problem at well-separated frequencies.

WHY it works (the mechanism): every branch replaces an intractable *exact* count (Legendre's $2^{\pi(z)}$-term inclusion–exclusion, whose error swamps the main term once $z$ isn't tiny) with a *provably controllable surrogate* — a bounded-length alternating sum (Brun), an optimized quadratic form with a diagonalizable error (Selberg), a second-moment/Chebyshev bound (Turán), or an $L^2$/Fourier duality inequality (large sieve) — each surrogate sacrificing some sharpness (small sieves: constant-factor losses; large sieve: only "on average over moduli," not per-modulus) in exchange for an error term that is *provably* smaller than the main term across the whole sifting range. The common enemy defeated is error accumulation from naive inclusion–exclusion; the common blind spot is the parity problem, since none of the surrogate bounds can see the *sign* of $(-1)^{\Omega(n)}$.

Related

- Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the Turán sieve's underlying mechanism is a Chebyshev/Paley–Zygmund-type second-moment bound; that page independently documents Turán's 1934 Hardy–Ramanujan proof as its founding number-theoretic instance. - Erdős–Rankin construction (covering-congruences translation for large prime gaps) — the classical 1938 covering-system-plus-sieve skeleton that Erdős #4 — unbounded large gaps between primes (Rankin's constant removed)'s resolution upgrades by importing GPY/Maynard-Tao sieve weights. - Pippenger–Spencer hypergraph covering theorem (and the FGKMT generalization) — the modern Rödl-nibble/hypergraph-matching replacement for classical sieve-theoretic covering-multiplicity bounds, invoked in Erdős #689 — double covering by prime residues: all-moduli case SOLVED (erdos/1205, F(x)~log x); primes-only case OPEN with two 2026 proof claims unverified and Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) precisely where pure sieve methods stall (parity-problem-adjacent obstructions). - Erdős #687 — estimate the Jacobsthal covering function Y(x) — Jacobsthal covering function $Y(x)$; Iwaniec's 1978 sieve-counting bound $Y(x)\ll x^2$ is unimproved, and whether modern large-sieve/Turán-sieve inequalities (Hough's distortion method, arXiv:1307.0874) can tighten it is an open transfer target. - Jacobsthal's function h(k) — finiteness and near-matching two-sided bounds — Jacobsthal's function $h(k)$; same Iwaniec Buchstab/linear-sieve upper-bound technique as the bottleneck. - Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) — unbounded large gaps between primes; Maynard's arXiv:1408.5110 repurposes GPY/Maynard-Tao's small-gap multidimensional sieve to select covering residues non-greedily. - Erdős #689 — double covering by prime residues: all-moduli case SOLVED (erdos/1205, F(x)~log x); primes-only case OPEN with two 2026 proof claims unverified — double covering by prime residues; contrasts the classical sieve-theoretic covering-multiplicity ceiling against the Rödl-nibble/hypergraph-matching resolution route. - Erdős #688 — the ε_n covering variant: how few large primes can cover [1,n]? — the $\varepsilon_n$ covering variant; sieve-theoretic + Mertens-estimate bottleneck on how few large primes can cover $[1,n]$. - Erdős #2 — minimum modulus of a covering system cannot be arbitrarily large — minimum modulus of a covering system; pre-2015 evidence came from static density/character-sum/sieve bounds that could not prove the (now-resolved, via distortion method) unboundedness result unconditionally.