[proofplan]
We prove the stated inequality by finite-dimensional Hilbert-space duality. The dual estimate is converted from primitive character sums to additive exponential sums using the Gauss sum formula for primitive Dirichlet characters. The resulting additive frequencies are the reduced fractions $a/q$ with $q \leq Q$, so the dual additive large sieve gives the factor $N-1+Q^2$. Finally, [Bessel's inequality](/theorems/540) in the finite character group controls the new additive coefficients by the original primitive-character coefficients.
[/proofplan]
[step:Pass to the finite-dimensional dual inequality]
Let
\begin{align*}
I := \{n \in \mathbb{Z} : M < n \leq M+N\}
\end{align*}
and let
\begin{align*}
\mathcal{P}_Q := \{(q,\chi) : q \in \mathbb{N},\ q \leq Q,\ \chi \text{ is a primitive Dirichlet character modulo } q\}.
\end{align*}
Define the [linear map](/page/Linear%20Map) $T: \mathbb{C}^{I} \to \mathbb{C}^{\mathcal{P}_Q}$ by
\begin{align*}
T((a_n)_{n \in I}) := \left(\left(\frac{q}{\varphi(q)}\right)^{1/2}\sum_{n \in I} a_n \chi(n)\right)_{(q,\chi)\in \mathcal{P}_Q}.
\end{align*}
The desired estimate is exactly $\|T a\|_{\ell^2(\mathcal{P}_Q)}^2 \leq (N-1+Q^2)\|a\|_{\ell^2(I)}^2$ for every $a \in \mathbb{C}^I$.
By finite-dimensional Hilbert-space duality, this is equivalent to the adjoint estimate
\begin{align*}
\sum_{n \in I}\left|\sum_{q \leq Q}\left(\frac{q}{\varphi(q)}\right)^{1/2}\sum_{\chi \bmod q}^{*} b(q,\chi)\chi(n)\right|^2 \leq (N-1+Q^2)\sum_{q \leq Q}\sum_{\chi \bmod q}^{*}|b(q,\chi)|^2
\end{align*}
for every family of complex numbers $b(q,\chi)$ indexed by $\mathcal{P}_Q$. Indeed, the adjoint formally contains $\overline{\chi(n)}$, but replacing each primitive character $\chi$ by its conjugate $\overline{\chi}$ only relabels the same finite set of primitive characters modulo $q$.
[guided]
We want to prove an inequality for all coefficient sequences $(a_n)_{n \in I}$. It is useful to regard the left-hand side as the squared norm of a linear operator. Define
\begin{align*}
I := \{n \in \mathbb{Z} : M < n \leq M+N\}
\end{align*}
and
\begin{align*}
\mathcal{P}_Q := \{(q,\chi) : q \in \mathbb{N},\ q \leq Q,\ \chi \text{ is a primitive Dirichlet character modulo } q\}.
\end{align*}
Now define the linear map $T: \mathbb{C}^{I} \to \mathbb{C}^{\mathcal{P}_Q}$ by
\begin{align*}
T((a_n)_{n \in I}) := \left(\left(\frac{q}{\varphi(q)}\right)^{1/2}\sum_{n \in I} a_n \chi(n)\right)_{(q,\chi)\in \mathcal{P}_Q}.
\end{align*}
With the usual $\ell^2$ norms, the theorem says precisely that
\begin{align*}
\|Ta\|_{\ell^2(\mathcal{P}_Q)}^2 \leq (N-1+Q^2)\|a\|_{\ell^2(I)}^2
\end{align*}
for every $a \in \mathbb{C}^I$.
Because both vector spaces are finite-dimensional Hilbert spaces, the operator norm of $T$ equals the operator norm of its adjoint $T^*$. Therefore it is enough to prove the adjoint estimate
\begin{align*}
\sum_{n \in I}\left|\sum_{q \leq Q}\left(\frac{q}{\varphi(q)}\right)^{1/2}\sum_{\chi \bmod q}^{*} b(q,\chi)\chi(n)\right|^2 \leq (N-1+Q^2)\sum_{q \leq Q}\sum_{\chi \bmod q}^{*}|b(q,\chi)|^2
\end{align*}
for every family $b(q,\chi) \in \mathbb{C}$. The actual Hilbert-space adjoint contains $\overline{\chi(n)}$ rather than $\chi(n)$. This makes no difference: if $\chi$ is primitive modulo $q$, then $\overline{\chi}$ is also primitive modulo $q$, and the map $\chi \mapsto \overline{\chi}$ is a bijection on the primitive characters modulo $q$. Thus arbitrary coefficients may be relabelled, giving the displayed dual form.
[/guided]
[/step]
[step:Convert primitive character sums into additive exponential sums]
Define the additive character map $e: \mathbb{R} \to \mathbb{C}$ by
\begin{align*}
e(x) := \exp(2\pi i x).
\end{align*}
For a primitive Dirichlet character $\chi$ modulo $q$, define the Gauss sum functional value $\tau(\overline{\chi}) \in \mathbb{C}$ by
\begin{align*}
\tau(\overline{\chi}) := \sum_{r \bmod q} \overline{\chi}(r)e\left(\frac{r}{q}\right).
\end{align*}
The primitive Gauss sum identity gives, for every $n \in \mathbb{Z}$,
\begin{align*}
\chi(n) = \frac{1}{\tau(\overline{\chi})}\sum_{\substack{a \bmod q,\ \gcd(a,q)=1}} \overline{\chi}(a)e\left(\frac{an}{q}\right),
\end{align*}
and $|\tau(\overline{\chi})|=q^{1/2}$. This uses the standard primitive-character Gauss sum evaluation: the [Fourier transform](/page/Fourier%20Transform) identity is the [Fourier Transform of a Primitive Dirichlet Character](/theorems/4384), and the size estimate is the [Magnitude of a Primitive Dirichlet Gauss Sum](/theorems/4385).
For integers $n$ not coprime to $q$, the same primitive identity remains valid because both sides vanish.
Substituting this identity into the dual expression gives
\begin{align*}
\sum_{q \leq Q}\left(\frac{q}{\varphi(q)}\right)^{1/2}\sum_{\chi \bmod q}^{*} b(q,\chi)\chi(n) = \sum_{q \leq Q}\sum_{\substack{a \bmod q,\ \gcd(a,q)=1}} c_{q,a} e\left(\frac{an}{q}\right),
\end{align*}
where, for each reduced residue class $a \bmod q$, define $c_{q,a} \in \mathbb{C}$ by
\begin{align*}
c_{q,a} := \frac{q^{1/2}}{\varphi(q)^{1/2}}\sum_{\chi \bmod q}^{*}\frac{b(q,\chi)\overline{\chi}(a)}{\tau(\overline{\chi})}.
\end{align*}
Since $|\tau(\overline{\chi})|=q^{1/2}$, the quotient
\begin{align*}
\frac{q^{1/2}}{\tau(\overline{\chi})}
\end{align*}
has absolute value $1$.
[guided]
The goal of this step is to replace each multiplicative character value $\chi(n)$ by an additive exponential sum. Define the additive character map $e: \mathbb{R} \to \mathbb{C}$ by
\begin{align*}
e(x) := \exp(2\pi i x).
\end{align*}
For a primitive Dirichlet character $\chi$ modulo $q$, define the Gauss sum value $\tau(\overline{\chi}) \in \mathbb{C}$ by
\begin{align*}
\tau(\overline{\chi}) := \sum_{r \bmod q} \overline{\chi}(r)e\left(\frac{r}{q}\right).
\end{align*}
Because $\chi$ is primitive modulo $q$, the primitive Gauss sum formula applies and gives, for every $n \in \mathbb{Z}$,
\begin{align*}
\chi(n) = \frac{1}{\tau(\overline{\chi})}\sum_{\substack{a \bmod q,\ \gcd(a,q)=1}}\overline{\chi}(a)e\left(\frac{an}{q}\right),
\end{align*}
with the size evaluation
\begin{align*}
|\tau(\overline{\chi})| = q^{1/2}.
\end{align*}
This is exactly where primitivity is used: the non-vanishing and sharp size of the Gauss sum are part of the primitive-character formula, and when $\gcd(n,q)>1$ both sides of the primitive identity are zero. Substituting this identity into the dual sum and collecting the coefficient of each additive character $e(an/q)$ gives
\begin{align*}
\sum_{q \leq Q}\left(\frac{q}{\varphi(q)}\right)^{1/2}\sum_{\chi \bmod q}^{*} b(q,\chi)\chi(n) = \sum_{q \leq Q}\sum_{\substack{a \bmod q,\ \gcd(a,q)=1}} c_{q,a}e\left(\frac{an}{q}\right),
\end{align*}
where the additive coefficient $c_{q,a} \in \mathbb{C}$ is defined by
\begin{align*}
c_{q,a} := \frac{q^{1/2}}{\varphi(q)^{1/2}}\sum_{\chi \bmod q}^{*}\frac{b(q,\chi)\overline{\chi}(a)}{\tau(\overline{\chi})}.
\end{align*}
The normalization is chosen so that the quotient
\begin{align*}
\frac{q^{1/2}}{\tau(\overline{\chi})}
\end{align*}
has absolute value $1$. Thus the Gauss sum conversion changes multiplicative characters into additive phases without increasing the coefficient size except for the explicit finite Fourier normalization handled in the next step.
[/guided]
[/step]
[step:Bound the additive coefficients by Bessel's inequality]
For each $q \leq Q$, define the coefficient map $\beta_q: \{\text{primitive characters modulo }q\} \to \mathbb{C}$ by
\begin{align*}
\beta_q(\chi) := \frac{q^{1/2}}{\tau(\overline{\chi})} b(q,\chi).
\end{align*}
Then $|\beta_q(\chi)|=|b(q,\chi)|$, and
\begin{align*}
c_{q,a} = \frac{1}{\varphi(q)^{1/2}}\sum_{\chi \bmod q}^{*} \beta_q(\chi)\overline{\chi}(a).
\end{align*}
Let $G_q := (\mathbb{Z}/q\mathbb{Z})^\times$ be the finite multiplicative group of reduced residue classes modulo $q$. The full set of Dirichlet characters modulo $q$ is an [orthonormal basis](/page/Orthonormal%20Basis) of $\ell^2(G_q)$ with normalized [inner product](/page/Inner%20Product)
\begin{align*}
(f,g)_{\ell^2(G_q)} := \frac{1}{\varphi(q)}\sum_{a \in G_q} f(a)\overline{g(a)}.
\end{align*}
Extend $\beta_q$ by zero to a function on the full character group modulo $q$. [Parseval's identity](/theorems/434) on the finite group $G_q$ gives
\begin{align*}
\sum_{a \in G_q}|c_{q,a}|^2 = \sum_{\chi \bmod q}|\beta_q(\chi)|^2 = \sum_{\chi \bmod q}^{*}|\beta_q(\chi)|^2 = \sum_{\chi \bmod q}^{*}|b(q,\chi)|^2.
\end{align*}
In particular, the required Bessel bound holds after restricting to primitive characters.
[guided]
Fix a modulus $q \leq Q$. The coefficients $c_{q,a}$ are finite Fourier transforms on the finite abelian group
\begin{align*}
G_q := (\mathbb{Z}/q\mathbb{Z})^\times.
\end{align*}
The relevant [Hilbert space](/page/Hilbert%20Space) is $\ell^2(G_q)$ with normalized inner product
\begin{align*}
(f,g)_{\ell^2(G_q)} := \frac{1}{\varphi(q)}\sum_{a \in G_q} f(a)\overline{g(a)}.
\end{align*}
The Dirichlet characters modulo $q$ are exactly the characters of the finite abelian group $G_q$, and the full character set is an orthonormal basis of this Hilbert space.
Define the coefficient map $\beta_q: \{\text{primitive characters modulo }q\} \to \mathbb{C}$ by
\begin{align*}
\beta_q(\chi) := \frac{q^{1/2}}{\tau(\overline{\chi})}b(q,\chi).
\end{align*}
The Gauss sum evaluation gives $|\tau(\overline{\chi})|=q^{1/2}$, so
\begin{align*}
|\beta_q(\chi)| = |b(q,\chi)|.
\end{align*}
The additive coefficient is then
\begin{align*}
c_{q,a} = \frac{1}{\varphi(q)^{1/2}}\sum_{\chi \bmod q}^{*}\beta_q(\chi)\overline{\chi}(a).
\end{align*}
Why does this have a good square-sum bound in $a$? Extend $\beta_q$ by zero from the primitive characters to all Dirichlet characters modulo $q$. Then $c_{q,a}$ is the inverse finite Fourier transform of this extended coefficient function, with the normalization matching the inner product above. Parseval's identity on $G_q$ gives
\begin{align*}
\sum_{a \in G_q}|c_{q,a}|^2 = \sum_{\chi \bmod q}|\beta_q(\chi)|^2.
\end{align*}
Since the extension is zero on non-primitive characters, this becomes
\begin{align*}
\sum_{a \in G_q}|c_{q,a}|^2 = \sum_{\chi \bmod q}^{*}|\beta_q(\chi)|^2 = \sum_{\chi \bmod q}^{*}|b(q,\chi)|^2.
\end{align*}
Equivalently, this is Bessel's inequality for the subset of primitive characters inside the full orthonormal character basis. The factor $\varphi(q)^{-1/2}$ in the definition of $c_{q,a}$ is precisely what makes the normalized [Parseval identity](/theorems/248) have constant $1$.
[/guided]
[/step]
[step:Apply the dual additive large sieve to the reduced fractions]
The fractions $a/q$ appearing above are indexed by $q \leq Q$ and reduced residue classes $a \bmod q$. If $0 \leq a < q$, $\gcd(a,q)=1$, $0 \leq a' < q'$, and $\gcd(a',q')=1$, then equality $a/q=a'/q'$ implies $q=q'$ and $a=a'$; hence these reduced fractions are distinct.
The interval $I=\{n \in \mathbb{Z}: M<n\leq M+N\}$ has exactly $N$ consecutive integer points, and the additive frequencies are precisely the reduced fractions $a/q$ with $q \leq Q$. As in the locally staged [Additive Large Sieve Inequality for Reduced Fractions](/theorems/7182) [quotetheorem:TEMP-23], these reduced fractions are $Q^{-2}$-spaced in $\mathbb R/\mathbb Z$. Apply the locally staged [Dual Additive Large Sieve Inequality](/theorems/7184) [quotetheorem:TEMP-25] with $\Delta=Q^{-2}$ to the coefficients $c_{q,a}$ attached to these reduced fractions. It gives
\begin{align*}
\sum_{n \in I}\left|\sum_{q \leq Q}\sum_{\substack{a \bmod q,\ \gcd(a,q)=1}} c_{q,a}e\left(\frac{an}{q}\right)\right|^2 \leq (N-1+Q^2)\sum_{q \leq Q}\sum_{\substack{a \bmod q,\ \gcd(a,q)=1}} |c_{q,a}|^2.
\end{align*}
Combining this with the Bessel bound from the preceding step yields
\begin{align*}
\sum_{n \in I}\left|\sum_{q \leq Q}\sum_{\substack{a \bmod q,\ \gcd(a,q)=1}} c_{q,a}e\left(\frac{an}{q}\right)\right|^2 \leq (N-1+Q^2)\sum_{q \leq Q}\sum_{\chi \bmod q}^{*}|b(q,\chi)|^2.
\end{align*}
Using the identity from the Gauss-sum conversion step, this is exactly the required dual primitive-character estimate.
[guided]
We now apply the additive large sieve to the frequencies produced by the Gauss sum formula. First verify the hypotheses on those frequencies. Choose representatives $0 \leq a < q$ and $0 \leq a' < q'$ with $\gcd(a,q)=1$ and $\gcd(a',q')=1$. If $a/q=a'/q'$, then cross-multiplication gives $aq'=a'q$. Since each fraction is in lowest terms, uniqueness of reduced rational representation gives $q=q'$ and then $a=a'$. Thus the reduced fractions $a/q$ are distinct.
The index set $I=\{n \in \mathbb{Z}: M<n\leq M+N\}$ consists of $N$ consecutive integers, and every frequency has the required form $a/q$ with $q \leq Q$ and $\gcd(a,q)=1$. The reduced-fraction spacing used in the locally staged [Additive Large Sieve Inequality](/theorems/7181) for Reduced Fractions [quotetheorem:TEMP-23] gives $\Delta=Q^{-2}$, so the locally staged Dual Additive Large Sieve Inequality [quotetheorem:TEMP-25] applies to the coefficient family $(c_{q,a})$ and gives
\begin{align*}
\sum_{n \in I}\left|\sum_{q \leq Q}\sum_{\substack{a \bmod q,\ \gcd(a,q)=1}} c_{q,a}e\left(\frac{an}{q}\right)\right|^2 \leq (N-1+Q^2)\sum_{q \leq Q}\sum_{\substack{a \bmod q,\ \gcd(a,q)=1}} |c_{q,a}|^2.
\end{align*}
The previous step proved the coefficient estimate
\begin{align*}
\sum_{\substack{a \bmod q,\ \gcd(a,q)=1}} |c_{q,a}|^2 \leq \sum_{\chi \bmod q}^{*}|b(q,\chi)|^2
\end{align*}
for each fixed $q \leq Q$. Summing that estimate over $q \leq Q$ and inserting it into the additive large sieve bound gives
\begin{align*}
\sum_{n \in I}\left|\sum_{q \leq Q}\sum_{\substack{a \bmod q,\ \gcd(a,q)=1}} c_{q,a}e\left(\frac{an}{q}\right)\right|^2 \leq (N-1+Q^2)\sum_{q \leq Q}\sum_{\chi \bmod q}^{*}|b(q,\chi)|^2.
\end{align*}
Finally, the Gauss-sum conversion step identified the inner additive sum with the dual primitive-character expression. Hence this is exactly the dual estimate needed for the original multiplicative large sieve.
[/guided]
[/step]
[step:Return from the dual estimate to the stated inequality]
The preceding step proves
\begin{align*}
\|T^*b\|_{\ell^2(I)}^2 \leq (N-1+Q^2)\|b\|_{\ell^2(\mathcal{P}_Q)}^2
\end{align*}
for every $b \in \mathbb{C}^{\mathcal{P}_Q}$. Hence $\|T^*\|^2 \leq N-1+Q^2$. Since $T$ is a linear map between finite-dimensional Hilbert spaces, $\|T\|=\|T^*\|$, and therefore
\begin{align*}
\|Ta\|_{\ell^2(\mathcal{P}_Q)}^2 \leq (N-1+Q^2)\|a\|_{\ell^2(I)}^2
\end{align*}
for every $a \in \mathbb{C}^{I}$. Written out in coordinates, this is
\begin{align*}
\sum_{q \leq Q}\frac{q}{\varphi(q)}\sum_{\chi \bmod q}^{*}\left|\sum_{M<n\leq M+N}a_n\chi(n)\right|^2 \leq (N-1+Q^2)\sum_{M<n\leq M+N}|a_n|^2.
\end{align*}
This is the desired multiplicative large sieve inequality for primitive Dirichlet characters.
[guided]
The dual estimate has now been proved for every coefficient family $b \in \mathbb{C}^{\mathcal{P}_Q}$:
\begin{align*}
\|T^*b\|_{\ell^2(I)}^2 \leq (N-1+Q^2)\|b\|_{\ell^2(\mathcal{P}_Q)}^2.
\end{align*}
This says exactly that the squared operator norm of $T^*$ is at most $N-1+Q^2$. Because $T: \mathbb{C}^I \to \mathbb{C}^{\mathcal{P}_Q}$ is a linear map between finite-dimensional Hilbert spaces, the singular values of $T$ and $T^*$ coincide, so $\|T\|=\|T^*\|$. Consequently, for every $a \in \mathbb{C}^I$,
\begin{align*}
\|Ta\|_{\ell^2(\mathcal{P}_Q)}^2 \leq (N-1+Q^2)\|a\|_{\ell^2(I)}^2.
\end{align*}
Finally expand the definitions of $T$, $I$, and the two finite $\ell^2$ norms. The left-hand side becomes
\begin{align*}
\sum_{q \leq Q}\frac{q}{\varphi(q)}\sum_{\chi \bmod q}^{*}\left|\sum_{M<n\leq M+N}a_n\chi(n)\right|^2,
\end{align*}
and the right-hand side becomes
\begin{align*}
(N-1+Q^2)\sum_{M<n\leq M+N}|a_n|^2.
\end{align*}
This is precisely the inequality stated in the theorem.
[/guided]
[/step]
