Sieve Methods

Sieve methods systematically count integers that survive the removal of those divisible by a set of primes, giving the sharpest available bounds on primes, twin primes, and almost-primes.

Definition

A sieve method is an analytic-combinatorial technique that estimates the size of a set of integers remaining after deleting those divisible by primes from a chosen set, yielding upper and lower bounds for counts of primes and almost-primes.

Scope

This topic covers the inclusion-exclusion sieve of Eratosthenes and Legendre and its limitations, Brun's combinatorial sieve, Selberg's quadratic upper-bound sieve, the large sieve inequality, the parity problem that obstructs sieves from isolating primes alone, and applications such as Brun's theorem, Chen's theorem, and modern results on bounded gaps between primes.

Core questions

• How does inclusion-exclusion sieve out multiples, and why does the naive Eratosthenes-Legendre sieve lose control over many sifting primes?
• How do Brun's and Selberg's sieves tame the error terms to give usable bounds?
• What is the parity problem, and why does it prevent classical sieves from counting primes exactly?
• How have sieve methods produced results such as Brun's constant, Chen's theorem, and bounded prime gaps?

Key theories

Brun's sieve and Brun's theorem

By truncating inclusion-exclusion at an even or odd level, Brun obtained usable upper bounds and proved that the sum of reciprocals of twin primes converges, the first major sieve result.

Selberg's sieve and the large sieve

Selberg replaced combinatorial truncation by optimizing a quadratic form for sharp upper bounds, while the large sieve provides strong mean-value estimates over residue classes and characters.

Parity problem and modern advances

Sieves cannot by themselves distinguish numbers with an even versus odd number of prime factors; combining sieves with other inputs yields Chen's theorem and, more recently, infinitely many bounded gaps between primes.

Clinical relevance

Sieve bounds quantify how many almost-primes and primes lie in given ranges and progressions, supporting heuristics used in factorization algorithms and in modelling the supply of cryptographically suitable primes.

History

Sieve theory began with Brun's modification of the Eratosthenes sieve around 1915, which proved the twin-prime reciprocal sum converges. Selberg introduced his optimized sieve in the 1940s; Chen proved in 1973 that every large even number is a prime plus an almost-prime; and Zhang's 2013 work, refined by Maynard and the Polymath project, established bounded gaps between primes.

Key figures

• Viggo Brun
• Atle Selberg
• Chen Jingrun
• Yitang Zhang

Seminal works

• iwaniecKowalski2004

Frequently asked questions

What is the parity problem in sieve theory?

Classical sieves cannot tell apart integers with an even number of prime factors from those with an odd number, so they cannot by themselves prove a sifted set consists of primes; extra arithmetic input is needed.

Did sieve methods prove the twin prime conjecture?

Not the full conjecture. Sieves combined with new ideas proved there are infinitely many pairs of primes within a bounded gap, but showing that gap can be two (twin primes) remains open.