[proofplan] We apply the [additive large sieve inequality](/theorems/7181) to the finite set of reduced fractions $a/q$ with $q \le Q$. The only arithmetic input is the Farey spacing estimate: two distinct reduced fractions of height at most $Q$ are separated modulo $1$ by at least $Q^{-2}$. Substituting this spacing parameter into the general additive large sieve gives exactly the stated constant $N - 1 + Q^2$. [/proofplan] [step:Define the reduced-fraction frequency set modulo $1$] Let $e: \mathbb{R} \to \mathbb{C}$ denote the map $t \mapsto \exp(2\pi i t)$. Define the finite set of reduced frequencies \begin{align*} \Theta_Q := \left\{\frac{a}{q} \in \mathbb{R} : 1 \le q \le Q,\ 1 \le a \le q,\ \gcd(a,q)=1\right\}. \end{align*} For each pair $(a,q)$ satisfying $1 \le q \le Q$, $1 \le a \le q$, and $\gcd(a,q)=1$, set \begin{align*} \theta_{a,q} := \frac{a}{q}. \end{align*} Then the left-hand side of the desired inequality is \begin{align*} \sum_{\theta \in \Theta_Q} \left|\sum_{M < n \le M+N} a_n e(n\theta)\right|^2, \end{align*} because the condition $\gcd(a,q)=1$ makes the representation $a/q$ reduced, so no two different pairs in the summation represent the same rational number except for the harmless endpoint convention $1/1 = 1$. [/step] [step:Verify that reduced fractions of height at most $Q$ are $Q^{-2}$-spaced modulo $1$] Let $\mathbb{R}/\mathbb{Z}$ denote the quotient additive group of [real numbers](/page/Real%20Numbers) modulo integers, so two real numbers represent the same point of $\mathbb{R}/\mathbb{Z}$ exactly when their difference lies in $\mathbb{Z}$. Let $\theta_{a,q},\theta_{b,r} \in \Theta_Q$ be distinct, where $1 \le q,r \le Q$, $1 \le a \le q$, $1 \le b \le r$, $\gcd(a,q)=1$, and $\gcd(b,r)=1$. Define the distance to the nearest integer by \begin{align*} \|t\|_{\mathbb{R}/\mathbb{Z}} := \min_{m \in \mathbb{Z}} |t-m| \end{align*} for $t \in \mathbb{R}$. Since $\theta_{a,q}$ and $\theta_{b,r}$ are distinct modulo $1$, the integer $ar-bq$ is nonzero unless the two fractions represent the same point of $\mathbb{R}/\mathbb{Z}$. Hence \begin{align*} \left|\frac{a}{q} - \frac{b}{r}\right| = \frac{|ar-bq|}{qr} \ge \frac{1}{qr} \ge \frac{1}{Q^2}. \end{align*} If the nearest-integer distance is realized without wrapping, this already gives \begin{align*} \left\|\frac{a}{q} - \frac{b}{r}\right\|_{\mathbb{R}/\mathbb{Z}} \ge \frac{1}{Q^2}. \end{align*} If wrapping occurs, then one fraction lies near $0$ and the other near $1$ in the interval $[0,1]$. The only element of $\Theta_Q$ equal to $1$ is $1/1$; otherwise both fractions lie in $(0,1)$. In either case the wrapped distance is bounded below by the distance from a reduced fraction with denominator at most $Q$ to either endpoint $0$ or $1$, which is at least $1/Q$ and therefore at least $1/Q^2$. Thus $\Theta_Q$ is $Q^{-2}$-spaced modulo $1$. [guided] The additive large sieve needs a spacing parameter, so we must prove that the frequencies $\theta_{a,q}=a/q$ cannot cluster too tightly modulo $1$. Here $\mathbb{R}/\mathbb{Z}$ denotes the quotient additive group of real numbers modulo integers; equivalently, two real numbers define the same point of $\mathbb{R}/\mathbb{Z}$ exactly when their difference is an integer. The relevant distance on this circle is \begin{align*} \|t\|_{\mathbb{R}/\mathbb{Z}} := \min_{m \in \mathbb{Z}} |t-m|. \end{align*} Take two distinct reduced fractions $\theta_{a,q}=a/q$ and $\theta_{b,r}=b/r$ with $q,r \le Q$. If they are distinct as points of $\mathbb{R}/\mathbb{Z}$, then the numerator $ar-bq$ is a nonzero integer, so $|ar-bq| \ge 1$. Therefore \begin{align*} \left|\frac{a}{q} - \frac{b}{r}\right| = \frac{|ar-bq|}{qr} \ge \frac{1}{qr} \ge \frac{1}{Q^2}. \end{align*} This proves the desired lower bound whenever the shorter arc between the two points on the circle is the ordinary interval between them. There remains the endpoint case where the shorter arc wraps around $0 \equiv 1$. Then one fraction is close to $0$ and the other is close to $1$. A reduced fraction $a/q$ with $1 \le q \le Q$ has distance at least $1/q \ge 1/Q$ from $0$ unless it is exactly $0$, which never occurs in our indexing. Similarly, it has distance at least $1/q \ge 1/Q$ from $1$ unless it is exactly $1$, and the only reduced fraction in our indexing equal to $1$ is $1/1$. Hence the wrapped distance is at least $1/Q$, which is stronger than $1/Q^2$. Thus every two distinct points of $\Theta_Q$ are separated modulo $1$ by at least $Q^{-2}$. [/guided] [/step] [step:Apply the additive large sieve with spacing $\Delta = Q^{-2}$] We use the additive large sieve inequality in its spacing form: if $\Theta \subset \mathbb{R}/\mathbb{Z}$ is a finite set with \begin{align*} \|\theta-\theta'\|_{\mathbb{R}/\mathbb{Z}} \ge \Delta \end{align*} for all distinct $\theta,\theta' \in \Theta$, then for every $M \in \mathbb{Z}$, every $N \in \mathbb{N}$, and every complex sequence $(c_n)_{M<n\le M+N}$, \begin{align*} \sum_{\theta \in \Theta}\left|\sum_{M<n\le M+N} c_n e(n\theta)\right|^2 \le (N-1+\Delta^{-1})\sum_{M<n\le M+N}|c_n|^2. \end{align*} This is the standard additive large sieve inequality in Hilbert-space form, citing a result not yet in the wiki: Additive Large Sieve Inequality. Apply this inequality with $\Theta=\Theta_Q$, $\Delta=Q^{-2}$, and $c_n=a_n$ for each integer $n$ satisfying $M<n\le M+N$. The spacing hypothesis was verified in the previous step, and the sequence is finite by the hypotheses on $M$ and $N$. Therefore \begin{align*} \sum_{\theta \in \Theta_Q}\left|\sum_{M<n\le M+N} a_n e(n\theta)\right|^2 \le (N-1+Q^2)\sum_{M<n\le M+N}|a_n|^2. \end{align*} Rewriting the sum over $\Theta_Q$ as the double sum over reduced residue classes gives \begin{align*} \sum_{q \le Q} \sum_{\substack{1 \le a \le q,\ \gcd(a,q)=1}} \left|\sum_{M < n \le M+N} a_n e\left(\frac{an}{q}\right)\right|^2 \le (N - 1 + Q^2)\sum_{M < n \le M+N} |a_n|^2. \end{align*} This is the desired inequality. [/step]