# Large sieve inequality

I am currently reading the book Opera de Cribro by John Friedlander and Henryk Iwaniec, and in particular studying the large sieve. One important thing to remember is that the “large sieve” is not really a sieve in the conventional sense. A ‘sieve’ typically refers to a choice of sieve weights, for example a combinatorial sieve is usually some way of defining sieve weights $\lambda_d$ in such a way that $\lambda_d = \mu(d)$ for some positive integers $d$, while $\lambda_d = 0$ for others. The large sieve does not involve a choice of sieve weights; and indeed, is usually independent from such choices (at least in its distilled from, the Bombieri-Vinogradov theorem).

The large sieve is actually just an inequality, which is not strictly number-theoretical. In fact, it applies equally well to any “well-spaced” points on the unit circle. The full force of this philosophy has recently been brought to bear on the Vinogradov Mean Value Theorem, in this paper. We write it in its most general form. We will adopt the convention $e(x) = e^{2 \pi i x}$ and for a given sequence $(a_n)$ of complex numbers, define $S(\alpha) = \displaystyle \sum_{M < n \leq M+N} a_n e(\alpha n)$. Now suppose that $\alpha_1, \cdots, \alpha_r$ are well-spaced real numbers with respect to some parameter $\delta$, meaning that for $k \ne l$, the number $\alpha_k - \alpha_l$ is at least $\delta$ away from an integer. We will write the distance of a real number $\beta$ from an integer as $\lVert \beta \rVert$. In other words, we insist that if $k \ne l$, then $\lVert \alpha_k - \alpha_l \rVert \geq \delta$.

Moreover, it is clear that we can have at most $\delta^{-1}$ many $\alpha_j$‘s. From the Cauchy-Schwarz inequality, we see that $\lvert S(\alpha) \rvert^2 \leq N \sum_{M < n \leq M+N} |a_n|^2$. Therefore, any upper bound for the term

$\displaystyle \sum_r \lvert S(\alpha_r)\rvert^2$

must include $N, \delta^{-1}$. The remarkable thing is that this is enough! Indeed, Selberg proved the following sharp form of the large sieve inequality:

$\displaystyle \sum_r \lvert S(\alpha) \rvert^2 \leq (N + \delta^{-1} -1) \sum_n |a_n|^2.$

This has the following striking number-theoretic interpretation. Consider all the rational numbers $a/q$ with $\gcd(a,q) = 1$ and $1 \leq q \leq Q$. Observe that any two such rationals differ by at most $1/Q^2$, in other words, these rationals are $Q^2$-spaced. Then the large sieve inequality gives the following

$\displaystyle \sum_{q \leq Q} \sum_{\substack{a \pmod{q} \\ \gcd(a,q) = 1}} \left \lvert S \left(\frac{a}{q}\right) \right \rvert^2 \leq \left(Q^2 + N - 1\right) \sum_n |a_n|^2.$

There are striking consequences to this inequality, including the famous theorem of Linnik.