= Solution
The standard primitive-character <multiplicative large sieve inequality> is
$$
\sum_{q\le Q}\frac q{\varphi(q)}\sum_{\chi\bmod q}^{*}
\left|\sum_{M<n\le M+N}a_n\chi(n)\right|^2
\le C(N+Q^2)\sum_n|a_n|^2,
$$
where the star restricts to <primitive Dirichlet characters>. This is the form used in analytic arguments for <Linnik's theorem>. The prime-power Gauss identities extend to arbitrary primitive conductors by the <Chinese remainder theorem>. Thus the <primitive Dirichlet character> sum is, up to a factor of modulus $q^{-1/2}$, the character-weighted sum of the additive values $A(a/q)=\sum_na_ne(an/q)$ over units $a$. <Orthogonality of Dirichlet characters>, extending the primitive-character summation to all characters, gives
$$
\frac q{\varphi(q)}\sum_{\chi\bmod q}^{*}|\sum_na_n\chi(n)|^2
\le\sum_{(a,q)=1}|A(a/q)|^2.
$$
The additive sieve on the $Q^{-2}$-spaced Farey points proves the displayed bound.
For both prime-interval applications, use the following <large sieve upper bound for sifted intervals>. Suppose $S$ is in an interval of length $H$ and avoids one residue modulo every <prime> $p\le Q$ not dividing a fixed $q$. Then
$$
|S|\le\frac{C(H+Q^2)}{\mathcal L_q(Q)},\qquad
\mathcal L_q(Q)=\sum_{\substack{d\le Q\\(d,q)=1}}\frac{\mu^2(d)}{\varphi(d)}.
$$
To prove it, choose the forbidden <Chinese remainder theorem> residue $r_d$ for each <squarefree> $d$. The <Ramanujan sum> $c_d(n-r_d)$ equals $\mu(d)$ on $S$, since $n-r_d$ is a unit modulo $d$. Therefore <Cauchy-Schwarz inequality> gives
$$
\sum_{(a,d)=1}\left|\sum_{n\in S}e(an/d)\right|^2\ge\frac{|S|^2}{\varphi(d)}.
$$
Indeed the linear combination with coefficients $e(-ar_d/d)$ has value $\mu(d)|S|$, and these coefficients have squared norm $\varphi(d)$. Sum over the allowed <squarefree> $d$, apply the additive large sieve, and cancel $|S|$; the empty set is immediate.
Finally $\mathcal L_1(Q)\ge c\log(2Q)$. <Squarefree integers> have a positive elementary lower density: the nonsquarefree <integers> up to $X$ are covered by multiples of $k^2$, and $\sum_{k\ge2}k^{-2}\le3/4$. <Partial summation> turns this density into the <harmonic> lower bound. Splitting each <squarefree> $d$ into its factors supported on <primes> dividing $q$ and its coprime part gives
$$
\mathcal L_1(Q)\le\prod_{p\mid q}\left(1+\frac1{p-1}\right)\mathcal L_q(Q)
=\frac q{\varphi(q)}\mathcal L_q(Q).
$$
Consequently $\mathcal L_q(Q)\ge c\,\varphi(q)\log(2Q)/q$, uniformly in $q$ and $Q$.
Back to article page
