Large sieve

Definition

For real $x$ write $e(x) = e^{2\pi i x}$ and let $\norm{x}$ be the distance from $x$ to the nearest integer. Let $M$ be an integer, $N \ge 1$ an integer and $(a_n)_{M < n \le M+N}$ complex numbers, and let $$S(\alpha) = \sum_{M < n \le M + N} a_n\, e(n\alpha),$$ an exponential sum. Let $\delta \in (0, 1]$, and let $\alpha_1, \ldots, \alpha_R$ be real numbers with $\norm{\alpha_r - \alpha_s} \ge \delta$ for all $r \ne s$. The large sieve inequality is $$\sum_{r=1}^{R} \abs{S(\alpha_r)}^2 \le \left(N - 1 + \delta^{-1}\right) \sum_{M < n \le M+N} \abs{a_n}^2.$$ The large sieve is the method that bounds sifted sets by this inequality. Its arithmetic form reads as follows. For each prime $p \le Q$, let $\omega(p)$ residue classes modulo $p$ be removed, with $0 \le \omega(p) < p$. If $\mathcal{Z}$ is a set of integers in $(M, M+N]$ that meets none of the removed classes, then $$\#\mathcal{Z} \le \frac{N + Q^2}{L}, \qquad L = \sum_{q \le Q} \mu(q)^2 \prod_{p \mid q} \frac{\omega(p)}{p - \omega(p)},$$ where $\mu$ is the Möbius function.