A grid of the integers from 1 to 4545 in rows of 101, each composite shaded by its smallest prime factor and each prime drawn as a pale square
Unit 15 · Advanced + Analytic Number Theory · 65 min

Sieve Methods

From Eratosthenes to Brun, Selberg, and Chen: counting what has no small prime factor
Image: Own rendering

A sieve counts the members of a set that have no small prime factor, and the twentieth century turned the sieve of Eratosthenes into one of the two great tools for questions about primes. This unit derives Legendre's exact formula and shows why it is useless, follows Brun to his theorem that the reciprocals of the twin primes have a finite sum, derives Selberg's optimal weights and the bounds they give, states the Bombieri-Vinogradov theorem that feeds every modern sieve, and explains the parity problem, the barrier at which Chen's theorem stops and which Friedlander and Iwaniec crossed in 1998.

Preview: the beginning of the unit

The sieve of Eratosthenes of Unit 3 lists the primes up to \(N\) by crossing out multiples, and Unit 8 mentioned that the theorems of Brun, Chen, Zhang, and Maynard grew out of it. This unit shows how. A sieve in the modern sense is a way of counting the members of a set that have no small prime factor, and its history in the twentieth century is the story of three ideas: Legendre’s exact formula and why it is useless, Brun’s decision to accept inequalities instead of identities, and Selberg’s choice of the best possible weights. The unit then explains the parity problem, the one obstacle that no sieve of this kind can pass, how Chen got as close to Goldbach’s conjecture as a sieve allows, and how Friedlander and Iwaniec went past the obstacle in 1998.

1 The sieve problem

A sieve problem has three ingredients: a finite set \(\mathcal{A}\) of positive integers, a bound \(z \ge 2\), and the question how many members of \(\mathcal{A}\) have no prime factor below \(z\). The members that survive are called the sifted set, and the standard notation for their number is \[ S(\mathcal{A}, z) = \bigl|\{\, a \in \mathcal{A} : \gcd(a, P(z)) = 1 \,\}\bigr| , \qquad P(z) = \prod_{p < z} p , \] where \(P(z)\) is the product of the primes below \(z\), so that \(\gcd(a, P(z)) = 1\) says exactly that no prime below \(z\) divides \(a\). For a squarefree \(d\) the set of members of \(\mathcal{A}\) divisible by \(d\) is written \(\mathcal{A}_d\), and the whole method rests on the fact that \(|\mathcal{A}_d|\) is usually easy to estimate, while \(S(\mathcal{A}, z)\) is what one wants.

Two uses of this setting cover most of the unit. In the first, \(\mathcal{A}\) is the set of integers from \(1\) to \(x\) and \(z = \sqrt{x}\). A number up to \(x\) with no prime factor below \(\sqrt{x}\) is either \(1\) or a prime (Unit 3), so \(S(\mathcal{A}, \sqrt{x}) = \pi(x) - \pi(\sqrt{x}) + 1\) (the primes below \(\sqrt{x}\) are crossed out, since each of them divides itself, and the number \(1\) survives), and a sieve that could evaluate \(S\) would count the primes. In the second use, \(\mathcal{A}\) is built for a question about primes of a special kind: for twin primes one takes \(\mathcal{A} = \{\, n(n + 2) : n \le x \,\}\), because \(n(n+2)\) has no prime factor below \(\sqrt{x + 2}\) exactly when \(n\) and \(n + 2\) are both primes at least as large as \(\sqrt{x + 2}\), and the twin prime pairs below that size are too few to matter. For Goldbach’s conjecture one takes \(\mathcal{A} = \{\, n(N - n) : n \le N \,\}\) for an even number \(N\). In each case \(\mathcal{A}_d\) is easy to count, because divisibility of \(n(n+2)\) by a prime \(p\) is a condition on the residue of \(n\) modulo \(p\) (namely \(n \equiv 0\) or \(n \equiv -2\)).

1.1 Legendre’s formula

The oldest way to compute \(S(\mathcal{A}, z)\) is inclusion and exclusion, which Adrien-Marie Legendre (1752-1833) wrote down in 1808 for the primes. Figure 1 shows the idea for the integers up to \(100\) and the primes \(2\), \(3\), and \(5\). Subtracting the multiples of \(2\), of \(3\), and of \(5\) from \(100\) removes the multiples of \(6\), \(10\), and \(15\) twice, so they are added back, and the multiples of \(30\), which were removed three times and then added back three times, are subtracted once more. The Möbius function \(\mu\) of Unit 6 records these signs, with \(\mu(d) = +1\) for \(d = 1\) and for a product of an even number of distinct primes, \(-1\) for a product of an odd number, and \(0\) when \(d\) has a square factor.

The full unit is part of the program

Want to see a complete unit first? Unit 3, Prime Numbers and Unique Factorization, is free to read.