Every sieve faces the same enemy. When you write down the number of survivors — the elements of a set that dodge all the small primes — the exact count comes out as an alternating sum carrying the Möbius signs \mu(d), and those signs make the error terms fight each other. The Legendre sieve gives an exact formula that is useless in practice, because it carries 2^{\pi(z)} error terms whose signs you cannot control. Brun's sieve tamed this by cleverly truncating the sum so the leftover error stays bounded — a combinatorial tour de force, but a fiddly one.

In 1947 Atle Selberg found a completely different, startlingly elegant fix. His idea is one of those moves that looks like cheating until you see how well it works: throw the signs away entirely and replace them with a square. A square is never negative, so it can only ever over-count — which is exactly what you want for an upper bound. And because the weights inside the square are now free real parameters, you can tune them optimally by a one-line calculus-of-several-variables minimisation. The result is the Selberg \Lambda^2 sieve: the cleanest, sharpest general upper-bound sieve in the subject, and the workhorse behind a huge fraction of modern results.

The set-up: what a sieve is counting

Fix a finite set \mathcal{A} of integers (say the integers up to x, or the values of some polynomial), a set of primes \mathcal{P}, and a cut-off z. Write P(z) = \prod_{p < z,\ p \in \mathcal{P}} p for the product of the sieving primes. The sifting function

counts the members of \mathcal{A} divisible by none of the sieving primes below z. When \mathcal{A} = \{n \le x\} and \mathcal{P} is all primes, the survivors with z = \sqrt{x} are essentially the primes between \sqrt{x} and x — sieving is how you count primes.

The engine is the same as always: for each d \mid P(z) we assume a good estimate for how many elements of \mathcal{A} are divisible by d,

where X \approx |\mathcal{A}|, the multiplicative g(d) is the "expected density" of the divisibility condition, and r_d is a small remainder. Everything below squeezes S between bounds using only these congruence counts.

Selberg's idea: the square that never lies

Start from the exact Legendre identity. The indicator that n is coprime to P(z) is

Those \mu(d) are the villains — signs you cannot manage. Selberg's stroke of genius is to notice one specific feature: the term d = 1 alone already contributes 1. So compare the indicator with a square. Pick any real numbers \lambda_1, \lambda_2, \lambda_3, \dots subject to the single normalisation

supported on d \le \sqrt{D} (with d \mid P(z)), and form the square \big( \sum_{d \mid \gcd(n, P(z))} \lambda_d \big)^{2}.

Why is this true? Split into two cases. If n is a survivor, then \gcd(n, P(z)) = 1, so the only divisor in range is d = 1, the inner sum is exactly \lambda_1 = 1, and the square is 1^2 = 1 — the left side is 1 too, so the inequality is an equality there. If n is not a survivor, the left side is 0 and the right side is a real square, hence \ge 0. Either way the right side dominates. That is the whole trick: a square is never negative, so it can only overshoot, which is precisely the licence an upper bound needs.

Summing: the main term becomes a quadratic form

Now sum the inequality over all n \in \mathcal{A}. Expanding the square gives a double sum over pairs d_1, d_2, and the elements counted are those divisible by both — i.e. by \operatorname{lcm}(d_1, d_2):

Insert the congruence estimate \#\{n : \ell \mid n\} = \frac{X}{\ell}g(\ell) + r_\ell with \ell = \operatorname{lcm}(d_1, d_2). The main terms collect into a quadratic form in the \lambda's, plus an error:

The error E is controlled because the \lambda's are supported on d \le \sqrt{D}, so every \operatorname{lcm} \le D and there are at most D distinct remainders in play. That leaves the real question, a clean optimisation problem.

The diagonalisation trick

A quadratic form with those messy \operatorname{lcm} coefficients looks forbidding, but Selberg's second beautiful move makes it collapse. Using multiplicativity and Möbius inversion one introduces new variables

where h is a suitable multiplicative weight built from g. This change of variables is invertible, and in the new coordinates the cross-terms vanish: the quadratic form becomes a plain sum of squares,

Diagonalising is what makes the minimisation trivial. A sum of squares with a single linear constraint (the normalisation \lambda_1 = 1 becomes \sum_e y_e = 1) is minimised by the classic Cauchy–Schwarz balance: put y_e \propto h(e). The minimum value is then the reciprocal of a single clean sum,

where G(D) is a sum of the multiplicative weights h(e) over the squarefree e \le \sqrt{D} dividing P(z). Everything funnels into that one quantity.

Seeing the optimisation

Every step above is, at heart, "minimise a positive quadratic subject to a linear constraint." It is worth seeing that shape concretely. Below is the 2-variable Selberg problem drawn as a curve: after fixing \lambda_1 = 1, the only free knob is a single weight \lambda_p, and the main term Q(\lambda_p) is an upward parabola. The sieve bound is the bottom of that parabola — slide off the optimum in either direction and the guaranteed upper bound only gets worse.

The vertex is where the derivative Q'(\lambda_p) = 0. Selberg's diagonalisation is nothing more than doing this vertex-finding in many variables at once, in coordinates chosen so the paraboloid has no tilted cross-terms and the minimum is read off instantly.

Worked example: the 2-variable Selberg optimisation

Let us actually turn the crank on the smallest non-trivial case, to watch the mechanism work. Sieve by a single prime p, so the only weights are \lambda_1 and \lambda_p, with the model density g(d) = 1 (so a fraction 1/d of \mathcal{A} is divisible by d). The quadratic form has diagonal coefficients 1/1 and 1/p, and one cross term with \operatorname{lcm}(1,p) = p:

Impose the constraint \lambda_1 = 1:

Now minimise in the single free variable. Differentiate and set to zero:

(Note the sign: the optimal weight came out negative — the minimisation rediscovers the Möbius-like \mu(p) = -1 all by itself, without our ever putting a sign in by hand.) Substitute back:

So the bound is S \le X \cdot \frac{p-1}{p} + E — exactly the right density (1 - 1/p) of integers surviving one prime, with G(D) = 1 + \frac{1}{p-1} = \frac{p}{p-1} matching 1/Q_{\min}. The machinery reproduces the obvious answer in the one case we can check by hand — which is exactly how you gain confidence that it is right in the millions of cases you cannot.

What it buys you

Feeding real densities into X/G(D) gives sharp, general upper bounds with good constants. Two headline consequences:

That twin-prime bound is famous: even though we still do not know that infinitely many twin primes exist, the Selberg sieve proves there are not too many — few enough that \sum 1/p over twin primes converges (Brun's constant). The sieve turns a question we cannot answer into a bound we can guarantee.