Sieve Methods — Mathematics Knowledge System

Overview

Sieve methods are combinatorial techniques for counting or estimating integers in a set that are not divisible by primes in a prescribed list. The sieve of Eratosthenes is the simplest; modern sieves (Brun, Selberg, large sieve) yield sharp estimates for prime-related problems such as twin primes and Goldbach-type results.

Intuition

Start with integers $1, 2, \ldots, N$. Cross out multiples of 2, then of 3, then of 5, etc. Each step is inclusion–exclusion: you add back what you over-subtracted. The Selberg sieve sharpens this by choosing optimal weights to minimise the error in the estimate.

Formal Definition

Definition

Let $\mathcal{A} = \{a_n\}$ be a sequence and $\mathcal{P}$ a set of primes. Define

S(\mathcal{A}, \mathcal{P}, z) = \#\{ a \in \mathcal{A} : \gcd(a, P(z)) = 1 \}, \quad P(z) = \prod_{p \in \mathcal{P},\, p < z} p

Sifted count: elements of A coprime to all primes in P below z

sieve-count

S(\mathcal{A}, \mathcal{P}, z) = \sum_{d | P(z)} \mu(d) |\mathcal{A}_d|

Inclusion-exclusion form via Mobius function

inclusion-exclusion

S(\mathcal{A}, \mathcal{P}, z) \leq X \prod_{p < z, p \in \mathcal{P}} \left(1 - \frac{1}{p}\right) + \text{error}

Selberg upper bound sieve estimate

selberg-upper

Notation

Notation	Meaning
$S(\mathcal{A}, \mathcal{P}, z)$	Number of elements of A not divisible by primes in P below z
$\mu(d)$	Mobius function
$P(z)$	Product of primes in P below z

Theorems

Theorem 1: Brun's Theorem

The sum \sum_{p,\, p+2 \text{ prime}} \left(\frac{1}{p} + \frac{1}{p+2}\right) converges to Brun's constant B \approx 1.902.

Theorem 2: Selberg's Upper Bound

For the sequence \mathcal{A} = \{n \leq N\} and primes \mathcal{P}, the sifted count satisfies S(\mathcal{A}, \mathcal{P}, z) \leq \frac{N}{\sum_{d | P(z)} \lambda_d^2 / d} + O(z^2), where (\lambda_d) are optimally chosen Selberg weights.

Theorem 3: Mertens' Third Theorem

\prod_{p \leq x} \left(1 - \frac{1}{p}\right) \sim \frac{e^{-\gamma}}{\ln x} \text{ as } x \to \infty, where \gamma is the Euler–Mascheroni constant.

Worked Examples

List 2 through 30. Mark 2 as prime; cross out all even numbers: 4, 6, 8, ..., 30.
Mark 3 as prime; cross out 9, 15, 21, 27 (multiples of 3 not already crossed).
Mark 5 as prime; cross out 25 (5² = 25, the first unmarked multiple). Since $\sqrt{30} < 6$, stop. Remaining: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Answer: Primes up to 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Practice Problems

Difficulty 6/10

How many integers in $[1, 100]$ are not divisible by 2, 3, or 5? Use inclusion–exclusion.

Difficulty 7/10

Explain why Mertens' third theorem $\prod_{p \leq x}(1 - 1/p) \sim e^{-\gamma}/\ln x$ implies that the proportion of integers coprime to all primes up to $x$ vanishes as $x \to \infty$.

Difficulty 8/10

State and prove that the number of primes in $[1, N]$ satisfies $\pi(N) \geq c \ln\ln N$ for some constant $c > 0$, using Mertens-style estimates.

Historical Background

Eratosthenes described the first sieve around 240 BCE. Brun introduced his combinatorial sieve in 1919, proving the sum of reciprocals of twin primes converges (Brun's constant). Selberg's sieve (1947) gave elementary proofs of the prime number theorem in arithmetic progressions and has been the workhorse ever since. Zhang's 2013 breakthrough on bounded prime gaps used a variant of the Selberg–GPY sieve.

c. 240 BCE
Eratosthenes describes sieve for generating primes
Eratosthenes
1919
Brun's sieve and proof that sum of twin prime reciprocals converges
Viggo Brun
1947
Selberg introduces his upper bound sieve
Atle Selberg
2013
Zhang proves bounded gaps between primes using sieve methods
Yitang Zhang

Summary

Sieve methods estimate $S(\mathcal{A}, \mathcal{P}, z)$: elements of $\mathcal{A}$ not divisible by primes below $z$.
Inclusion–exclusion via the Möbius function is the foundation.
Brun's sieve proves the sum of twin prime reciprocals converges.
Selberg's sieve provides sharp upper bounds via optimised linear weights.
Modern sieves (GPY, Maynard) established bounded gaps between primes.

References

BookCojocaru, A. & Murty, M. An Introduction to Sieve Methods and Their Applications. Cambridge, 2006.
BookHalberstam, H. & Richert, H. Sieve Methods. Academic Press, 1974.