Here is a curious piece of naming. The large sieve is not, at heart, a sieve at all — not in the combinatorial sense of Eratosthenes, or Brun, or Selberg, where you cross out multiples of primes and try to keep track of what survives. It is a single, clean analytic inequality about how large a trigonometric polynomial can be at a spread-out set of points. Everything else — the primes, the residue classes, the Bombieri–Vinogradov theorem — is a consequence squeezed out of that one inequality.

The name comes from what it is good at. A classical ("small") sieve removes, for each prime p, a bounded number of residue classes — usually just one or two. The large sieve is built to handle the opposite regime: removing many residue classes per prime, up to a positive proportion of all of them. Ask "how many integers up to N can dodge, say, half the residues modulo every prime p \le \sqrt N?" and it is the large sieve that answers.

The exponential sum at the heart of it

Fix complex numbers a_1, a_2, \dots, a_N — think of them as weights on the integers, often just the indicator of some set. Form the exponential sum

This is a trigonometric polynomial in the real variable \alpha, periodic with period 1, so we only ever need to look at it on the unit interval [0,1). Its total L^2-size over a full period is pinned by Parseval's identity,

so on average |S(\alpha)|^2 is exactly \sum |a_n|^2. The large sieve is the statement that if you sample S at points that are spread far enough apart, the sampled values cannot conspire to be much larger than that average all at once.

Well-spaced points

Call a finite set of points \alpha_1, \dots, \alpha_R in [0,1) \delta-spaced if any two of them differ by at least \delta, measured on the circle (so 0.99 and 0.01 are only 0.02 apart, wrapping around). The canonical example is the set of Farey fractions: all reduced fractions a/q with q \le Q. Two distinct such fractions a/q and a'/q' satisfy

because the numerator is a nonzero integer. So the Farey fractions of order Q are \delta-spaced with \delta = Q^{-2}. That single observation is what connects the abstract analytic inequality to arithmetic.

The analytic large sieve inequality

Read the shape of it. The right-hand side is the Parseval average \sum |a_n|^2 multiplied by a factor N + \delta^{-1}. The N is the "length" of the sum; the \delta^{-1} is (roughly) how many \delta-spaced points can fit into [0,1). The inequality says: sampling gives you nothing worse than the number of samples times the average — you never beat the mean by a constant factor, no matter how adversarially you place the points or choose the coefficients. The constant here is not optimal; the sharp version, due to Montgomery–Vaughan and Selberg, replaces N + \delta^{-1} with N - 1 + \delta^{-1}, which is best possible.

The arithmetic form: summing over Farey fractions

Feed the well-spaced Farey fractions into the analytic inequality. Take the points to be all reduced a/q with q \le Q and 1 \le a \le q, (a,q)=1. They are Q^{-2}-spaced, so \delta^{-1} = Q^2 and we land on the form most number theorists carry in their head:

The double sum ranges over every primitive fraction with denominator up to Q — there are about \tfrac{3}{\pi^2}Q^2 of them — and each measures how much the sequence a_n "resonates" with the frequency a/q. The factor is N + Q^2, and this is the number that governs everything.

Duality — the trick that makes it provable

The large sieve is really a statement about the norm of a linear map, and the cleanest proofs go through duality. Any inequality of the form

holds with a constant \Delta if and only if its dual holds with the same \Delta:

Here \varphi_n(r) = e(n\alpha_r). The two directions are the operator norm of a matrix and of its conjugate transpose — and those are equal. This is more than a formality: the dual form is often the one you can actually prove (bounding \sum_n |\sum_r b_r e(-n\alpha_r)|^2 by opening the square and controlling the off-diagonal terms with the spacing \delta), and then duality hands you back the form you wanted. It also means the large sieve can be read either as "samples of a polynomial are controlled by its coefficients" or as "a sum of well-spaced characters is nearly orthogonal" — same inequality, two faces.

The character form

For arithmetic applications the most useful repackaging replaces the additive frequencies e(na/q) with Dirichlet characters. Using the orthogonality of characters to convert the sum over residues a into a sum over characters \chi \bmod q, and restricting to primitive characters (the star on the sum), one obtains:

The starred sum \sum^{*}_{\chi} runs over the primitive characters mod q, and the weight q/\varphi(q) is the bookkeeping factor that appears when you sort the Gauss-sum relation between additive and multiplicative characters. This is the version that plugs directly into the theory of L-functions: the inner sum \sum a_n \chi(n) is a character sum, and the inequality bounds the mean square of character sums over all moduli and all primitive characters at once. It is precisely this "average over characters" that makes the next theorem possible.

The payoff: Bombieri–Vinogradov

The single most celebrated application of the large sieve is the Bombieri–Vinogradov theorem, often described as "the Generalised Riemann Hypothesis on average". Recall that GRH would control the error in the prime-counting function \pi(x; q, a) — primes up to x in the arithmetic progression a \bmod q — for every individual modulus q. Bombieri–Vinogradov proves that the same quality of error holds when you average over all moduli q \le \sqrt x / (\log x)^A:

No one knows how to prove GRH for even a single modulus — yet the large sieve delivers this on-average statement unconditionally. The character-form inequality is the key input: it converts the mean square of character sums (which is what the error terms become after expanding in characters) into a clean bound, and the range q \le \sqrt x is exactly the Q \asymp \sqrt N sweet spot from the vignette above. For countless problems that "morally" want GRH — the Titchmarsh divisor problem, gaps between primes, the parity barrier results — Bombieri–Vinogradov, and hence the large sieve, is a working substitute.

Worked example — sifting out many residue classes

Let's see the large sieve do the job its name promises. Suppose \mathcal{A} is a set of integers in [1, N], and for each prime p \le Q the elements of \mathcal{A} avoid \omega(p) residue classes modulo p — that is, they occupy at most p - \omega(p) of the p classes. We want to bound Z = |\mathcal{A}|.

Step 1. Take a_n = 1 if n \in \mathcal{A} and 0 otherwise, so \sum |a_n|^2 = Z and S(0) = Z. Plug into the arithmetic form.

Step 2. The arithmetic that turns "avoids \omega(p) classes" into a lower bound on the left-hand side (via Cauchy–Schwarz on each \sum_a |S(a/p)|^2, the summands weighted by the missing classes) gives the clean statement below, where the sum runs over squarefree q \le Q built from the sifting primes:

Step 3 — a concrete number. Suppose every prime p \le Q kills half its residues, so \omega(p) \approx p/2 and each factor \omega(p)/(p-\omega(p)) \approx 1. Then L is at least the number of primes up to Q, and in fact the full squarefree sum makes L grow like a power of Q. Choosing the optimal Q \asymp \sqrt N gives a bound of the shape |\mathcal{A}| \ll N / L \ll \sqrt{N}\,(\log N)^{O(1)} — a genuine saving over the trivial N. A set dodging a positive proportion of residues modulo every small prime must be tiny. That is the large sieve in one line: many forbidden classes ⇒ few survivors.