Tools on Fourier transforms
1. The large sieve inequality
The best version of the large sieve inequality from and (obtained at the same time by A. Selberg) is as follows.
Theorem (1974)
Let $M$ and $N\ge 1$ be two real numbers. Let $X$ be a set of points of $[0,1)$ such that $$ \min_{x,y\in X}\min_{k\in\mathbb{Z}}|x-y+k|\ge \delta>0. $$ Then, for any sequence of complex numbers $(a_n)_{M < n\le M+N}$, we have $$ \sum_{x\in X}\left| \sum_{M < n\le M+N} a_n \exp(2i\pi nx) \right|^2 \le \sum_{M < n\le M+N}|a_n|^2 (N-1+\delta^{-1}). $$
It is very often used with part of the Farey dissection.
Theorem (1974)
Let $M$ and $N\ge 1$ be two real numbers. Let $Q\ge1$ be a real parameter. For any sequence of complex numbers $(a_n)_{M < n\le M+N}$, we have $$ \sum_{q\in Q}\sum_{\substack{a\mod q,\\ (a,q)=1}}\left| \sum_{M < n\le M+N} a_n \exp(2i\pi na/q) \right|^2 \le \sum_{M < n\le M+N}|a_n|^2 (N-1+Q^2). $$
The summation over $a$ runs over all invertible classes $a$ modulo $q$.
Last updated on July 14th, 2013, by Olivier Ramaré