Proof of the Large Sieve Inequality

The large sieve inequality is a fundamental tool in analytic number theory, bounding exponential sums over well-spaced frequencies. It underlies the Bombieri-Vinogradov theorem and many results on the distribution of primes.

Statement

Theorem6.3Large Sieve Inequality

Let $a_{M+1}, \ldots, a_{M+N}$ be complex numbers and let $\alpha_1, \ldots, \alpha_R \in \mathbb{R}$ satisfy $\|\alpha_r - \alpha_s\| \geq \delta > 0$ for $r \neq s$ (where $\|\cdot\|$ denotes distance to the nearest integer). Then: $\sum_{r=1}^R \left|\sum_{n=M+1}^{M+N} a_n e^{2\pi i n\alpha_r}\right|^2 \leq (N - 1 + \delta^{-1}) \sum_{n=M+1}^{M+N} |a_n|^2$

Proof

Method (Selberg-Montgomery-Vaughan). Define $S(\alpha) = \sum_{n=M+1}^{M+N} a_n e^{2\pi i n\alpha}$ .

We seek a trigonometric polynomial $T(\alpha) = \sum_{|k| \leq K} c_k e^{2\pi i k\alpha}$ with $K = \lfloor \delta^{-1} \rfloor$ such that $T(\alpha_r) = 1$ for all $r$ and $\int_0^1 |T(\alpha)|^2\, d\alpha$ is minimized.

By duality, the large sieve is equivalent to: there exist $b_1, \ldots, b_R$ with $\sum|b_r|^2 \leq 1$ such that $\left\|\sum_r b_r e^{2\pi i n\alpha_r}\right\|_{\ell^2}^2 \leq N + \delta^{-1} - 1$ .

Direct proof via Beurling-Selberg functions. Consider the Hermitian form $\sum_{r,s} B_{rs} z_r \bar{z}_s$ where $B_{rs} = \sum_{n=M+1}^{M+N} e^{2\pi i n(\alpha_r - \alpha_s)}$ . The large sieve is equivalent to showing the operator norm $\|B\| \leq N + \delta^{-1} - 1$ .

For the diagonal: $B_{rr} = N$ . For off-diagonal terms, $|B_{rs}| = |\sin(\pi N(\alpha_r - \alpha_s))/\sin(\pi(\alpha_r - \alpha_s))|$ .

Hilbert-type inequality. The key estimate: $\sum_{r \neq s} \frac{|z_r||z_s|}{|\sin(\pi(\alpha_r - \alpha_s))|} \leq (\delta^{-1} - 1)\sum|z_r|^2$ when $\|\alpha_r - \alpha_s\| \geq \delta$ . This follows because the quadratic form $\sum_{r \neq s} z_r\bar{z}_s / \sin(\pi(\alpha_r - \alpha_s))$ is bounded by $(\delta^{-1} - 1)$ times the identity, which can be proved using the Beurling-Selberg majorant/minorant for the characteristic function of an interval.

Combining: $\sum_r |S(\alpha_r)|^2 = \sum_{r,s} B_{rs} z_r \bar{z}_s \leq (N + \delta^{-1} - 1) \sum |a_n|^2$ where we identified $z_r = \sum a_n e^{2\pi i n\alpha_r}$ ... more precisely, expanding $\sum_r|S(\alpha_r)|^2$ and using the bound on the Hermitian form.

Alternatively (Montgomery-Vaughan): $\sum_r |S(\alpha_r)|^2 \leq \sum_n |a_n|^2 \sum_r \left|\sum_{|k|\leq K} c_k^{(r)} e^{2\pi ikn}\right|$ where $c_k^{(r)}$ are chosen optimally, leading to the stated bound with constant $N - 1 + \delta^{-1}$ . $\square$

■

ExampleLarge Sieve for Characters

Specializing to Dirichlet characters: $\alpha_r = a/q$ for Farey fractions with $q \leq Q$ . The spacing $\delta = 1/Q^2$ (Farey fractions are spaced at least $1/Q^2$ apart). The character form of the large sieve: $\sum_{q \leq Q} \frac{q}{\phi(q)} \sum_{\chi \bmod q}^* \left|\sum_{n=M+1}^{M+N} a_n \chi(n)\right|^2 \leq (N + Q^2) \sum |a_n|^2$ .

RemarkSharpness

The constant $N - 1 + \delta^{-1}$ is the best possible (it cannot be replaced by $\max(N, \delta^{-1})$ in general). The extremal case is achieved by an arithmetic progression of frequencies $\alpha_r = r\delta$ .