The Legendre Sieve and Its Limits

Eratosthenes taught us to find the primes by crossing out multiples. But an analytic number theorist wants something sharper: not the list, but the count — how many numbers up to X survive after we knock out every multiple of every small prime? Turn that crossing-out into arithmetic and you get the sieve of Eratosthenes reborn as a formula — the Legendre sieve, written down by Legendre in 1808 while he chased the distribution of primes.

The formula is exact, elegant, and completely correct. It is also, for the questions we actually care about, almost useless — and understanding why it fails is the doorway to the whole of twentieth-century sieve theory. This lesson builds Legendre's formula, extracts its beautiful main term, and then watches its error term detonate. The repair — cutting the inclusion–exclusion short — is Brun's great idea, and the reason modern sieves exist at all.

The sieve setup

Fix a set of integers \mathcal{A} we want to sift — for a first taste, take \mathcal{A} = \{1, 2, \dots, X\}. Fix a sifting level z and bundle the small primes into one number, their product:

P(z) = \prod_{p < z} p.

The quantity we are after is the count of survivors — elements of \mathcal{A} divisible by none of the primes below z:

S(\mathcal{A}, P(z)) = \#\{\, a \in \mathcal{A} : \gcd(a, P(z)) = 1 \,\}.

Equivalently, a is counted precisely when it is divisible by no prime p < z.

Why does this count matter? Push z up to \sqrt{X} and every surviving a > 1 in \{1,\dots,X\} is prime — a composite a \le X always has a prime factor \le \sqrt{X}. So a good handle on S(\mathcal{A}, P(z)) would count the primes, and much more besides: twin primes, primes of the form n^2+1, Goldbach representations — all are sifting problems in disguise.

Legendre's formula: inclusion–exclusion becomes Möbius

To count the survivors, count the casualties and subtract — but subtracting "multiples of 2" and "multiples of 3" double-counts the multiples of 6, so we must add those back, then remove multiples of 30, and so on. That alternating dance is exactly inclusion–exclusion, and its bookkeeper is the Möbius function \mu(d). Let

A_d = \#\{\, a \in \mathcal{A} : d \mid a \,\}

count the elements divisible by d. Then Legendre's identity reads:

S(\mathcal{A}, P(z)) = \sum_{d \mid P(z)} \mu(d)\, A_d.

The identity is not an approximation — it is a bare-handed truth. Each a that is coprime to P(z) is counted once (only d=1 divides it among divisors of P(z)), while each a sharing k \ge 1 primes with P(z) is counted \sum_{j=0}^{k}\binom{k}{j}(-1)^j = 0 times. Everything sifted cancels perfectly; only the survivors remain.

Splitting each term: main part plus a remainder

Now approximate A_d. About one in every d integers is divisible by d, so if \mathcal{A}=\{1,\dots,X\} then A_d = \lfloor X/d \rfloor, which we write as a clean main part plus a small, honest error:

A_d = \frac{X}{d} + r_d, \qquad |r_d| < 1.

(In a general sieve A_d \approx (X/d)\cdot\omega(d)/\text{something} for a density factor, but the crude |r_d|\le 1 already tells the whole story.) Substitute this split into Legendre's formula and let the two pieces separate:

S(\mathcal{A}, P(z)) = \underbrace{X\sum_{d \mid P(z)} \frac{\mu(d)}{d}}_{\text{main term}} \; + \; \underbrace{\sum_{d \mid P(z)} \mu(d)\, r_d}_{\text{error term}}.

Everything now hinges on a race between these two sums. The left one is a thing of beauty; the right one is a time bomb. Let us admire the beauty first.

The main term: an Euler product, and Mertens

The main-term sum factors gorgeously. Because the divisors of P(z) are exactly the squarefree products of the primes p, and \mu is multiplicative, the sum over d unfolds into a product over primes:

\sum_{d \mid P(z)} \frac{\mu(d)}{d} = \prod_{p < z}\left(1 - \frac{1}{p}\right).

Each factor (1 - 1/p) is precisely "the proportion left after removing the multiples of p", and independence across distinct primes multiplies them. So the main term is

X\prod_{p

How big is that product? This is exactly the content of Mertens' third theorem, which pins it down asymptotically:

\prod_{p

where \gamma \approx 0.5772 is the Euler–Mascheroni constant.

So the main term is about X e^{-\gamma}/\log z. It shrinks — slowly, gracefully — as z grows, like X/\log z. If only the error term were negligible, this alone would essentially count the primes up to X. It isn't. Watch.

The catastrophe: counting the terms

The error term is \sum_{d\mid P(z)}\mu(d)\,r_d. Each individual r_d is tiny, |r_d|<1 — the trouble is how many there are. The divisors of P(z) are all the subsets of the primes below z, so their number is

\#\{\, d : d \mid P(z) \,\} = 2^{\pi(z)},

where \pi(z) counts the primes below z. The only bound we can honestly place on the error is the triangle inequality, term by term:

\left|\sum_{d\mid P(z)}\mu(d)\,r_d\right| \le \sum_{d\mid P(z)}|r_d| \le 2^{\pi(z)}.

And there it is. The main term is a placid \approx X/\log z; the error bound is 2^{\pi(z)}, which by the prime number theorem behaves like 2^{\,z/\log z} — doubly exponential in the useful variable. For the error to stay below the main term we need, very roughly,

2^{\pi(z)} \lesssim \frac{X}{\log z} \quad\Longrightarrow\quad \pi(z) \lesssim \log_2 X \quad\Longrightarrow\quad z \lesssim \log X.

Legendre's exact formula is only usable for z as small as \log X — a laughably low sifting level. At that level the main term X e^{-\gamma}/\log z \approx X/\log\log X is far too crude to isolate the primes (we needed z=\sqrt X!). The exact formula, pushed anywhere near where we want it, drowns in its own error.

Seeing the crossover

Here is the race, plotted on a logarithmic axis (we plot \log_{10} of each quantity, or the doubly-exponential error would run off the page instantly). Fix a large budget X = 10^{12}. The main term X\prod_{p barely moves — it drifts down like 1/\log z. The error bound 2^{\pi(z)} climbs a relentless staircase and blasts straight through it.

Before the crossover the formula is trustworthy; a hair past it, the guaranteed error is larger than the thing being computed, and Legendre's exact identity tells you nothing you didn't already know. No amount of cleverness in evaluating the r_d helps: there are simply too many of them to add up.

Worked example: watching the error win

Let's make it painfully concrete with X = 10^{12} and creep z upward, tracking both terms.

And we wanted z = \sqrt{X} = 10^6, where \pi(z)\approx 78{,}498 and the error bound is 2^{78498} — a number with over twenty thousand digits. The main term is a modest \sim 10^{12}/\log(10^6)\approx 7\times10^{10}. The exact formula is correct to the last unit, and yet the only bound we can prove on its error is astronomically larger than the answer. That is the tragedy of the Legendre sieve.

The single most important lesson of this page: the Legendre formula S = \sum_{d\mid P(z)}\mu(d)A_d is exactly true — no approximation, no hand-waving. The disaster is not an error in the formula; it is that we cannot evaluate it. We know each A_d = X/d + r_d only up to |r_d|<1, and there are 2^{\pi(z)} of them, so the accumulated uncertainty \sum|r_d|\le 2^{\pi(z)} swamps the main term for any z beyond \approx \log X.

The instinctive fix — "compute the r_d more precisely!" — is a trap. You cannot know \lfloor X/d\rfloor better than to the nearest integer without knowing d exactly, and even then, the individual roundings might conspire. The real fix is not more precision per term — it is fewer terms. Brun's insight was to truncate the inclusion–exclusion, keeping only divisors with few prime factors, accepting a controlled bias in the main term in exchange for an error over a manageable number of divisors. Truncation, not precision, is the escape.

It sounds like cheating: if you drop most of the divisors from an exact inclusion–exclusion, surely you get the wrong answer? The saving grace is a family of combinatorial inequalities — the Bonferroni inequalities. Truncating the alternating sum after an even number of levels gives an upper bound for the true count; after an odd number of levels, a lower bound. You never get the exact value, but you trap it between two computable estimates.

Brun's sieve refines this: keep only divisors d with at most k prime factors, choosing k so the number of surviving divisors — and hence the total error — stays under control, while the main term is only slightly distorted. It was enough for Brun to prove in 1919 that the sum of reciprocals of the twin primes converges — a result the Legendre sieve could never touch. Later, Selberg's sieve replaced the crude truncation with cleverly optimised weights, squeezing out sharper bounds still.

The moral, and where sieve theory begins

The Legendre sieve is the honest starting point and the cautionary tale of the whole subject. It establishes two enduring facts:

Every modern sieve — Brun's, Selberg's, the large sieve, the Bombieri–Vinogradov theorem, the Goldston–Pintz–Yıldırım machinery behind bounded gaps between primes — is, at heart, a smarter way to keep the beautiful main term while taming the number of error contributions. They all descend from this one formula and the one flaw in it. Legendre wrote down the exact answer; a century of mathematicians learned to make it usable.