Large Sieve Inequality

The large sieve inequality

Let \(0<\delta \le \tfrac12\). We say that \(x_1,\ldots,x_R\) are \(\delta\) well-spaced if \[\min_{\substack{r\ne s}} \,\lVert x_r-x_s\rVert>\delta,\] where \(\lVert u\rVert=\min_{n\in\mathbb{Z}} |u-n|\). Observe that \(R\le \delta^{-1}\). Now let \[S(x)=\sum_{M<n\le M+N} a_n\, e(nx).\]

Theorem (P.X. Gallagher). If \(x_1,\ldots,x_R\) are \(\delta\) well-spaced, then \[\sum_{r=1}^{R} |S(x_r)|^2 \le \,(\pi N+\delta^{-1}) \sum_{M<n\le M+N} |a_n|^2 .\]

Lemma (Sobolev–Gallagher). Let \(f(x)\) be continuously differentiable on \([a,b]\) and complex valued. Then \[\bigl|f\!\left(\tfrac{a+b}{2}\right)\bigr| \le \frac{1}{b-a}\int_a^b |f(x)|\,dx+\frac12\int_a^b |f'(x)|\,dx .\]

In other words, if \(f\) is large at the center, either it is large on average or its total variation is large.

Proof. Let \(a\le u\le b\). Then \[\int_a^u \frac{x-a}{b-a}\,f'(x)\,dx = \frac{u-a}{b-a} f(u) - \frac{1}{b-a}\int_a^u f(x)\,dx\] and \[-\int_u^b \frac{b-x}{b-a}\,f'(x)\,dx = \frac{b-u}{b-a} f(u) - \frac{1}{b-a}\int_u^b f(x)\,dx .\] Adding gives \[f(u)=\int_a^u \frac{x-a}{b-a}\,f'(x)\,dx +\int_u^b \frac{x-b}{b-a}\,f'(x)\,dx +\frac{1}{b-a}\int_a^b f(x)\,dx ,\] so \[\bigl|f\!\left(\tfrac{a+b}{2}\right)\bigr| \le \frac12\int_a^b |f'(x)|\,dx+\frac{1}{b-a}\int_a^b |f(x)|\,dx .\] Proof of the theorem. It suffices to prove the result for \[S(x) = \sum_{n=k}^{k} a_n\, e(n x)\] with \(k=\lfloor M/2 \rfloor\) (multiply the original \(S(x)\) by \(e(-x(M+k+1))\)). By lemma with \(f(x) = S(x)^2\), it follows that \[|S(x_r)|^2 \le \frac{1}{\delta} \int_{x_r - \frac{\delta}{2}}^{x_r + \frac{\delta}{2}} |S(x)|^2\,dx + \int_{x_r - \frac{\delta}{2}}^{x_r + \frac{\delta}{2}} |S(x) S'(x)|\,dx .\] So if we take \(\{x_r\} = x_r - \lfloor x_r \rfloor\), \(|\{x_r\} - \{x_s\}| \ge \lVert x_r-x_s\rVert\ge\delta\), and \[S(x_r) = \sum_{n=k}^{k} a_n\, e(\lfloor x_r \rfloor n) \, e(\{x_r\} n) = \sum_{n=k}^{k} a_n\, e(\{x_r\} n),\] then, the intervals of integration in \(\sum_{r=1}^R \int_{x_r - \frac{\delta}{2}}^{x_r + \frac{\delta}{2}}\) are not overlapping. It gives \[\begin{aligned} \sum_{r=1}^R |S(x_r)|^2 &\le \frac{1}{\delta} \int_0^1 |S(x)|^2 dx + \int_0^1 |S(x) S'(x)| dx\\ &\le \frac{1}{\delta} \sum_{n=k}^{k'} |a_n|^2 + \left( \int_0^1 |S(x)|^2 dx \int_0^1 |S'(x)|^2 dx \right)^{1/2}\\ &\le \frac{1}{\delta} \sum_{n=k}^{k} |a_n|^2 + \left( \frac{1}{\delta} \sum_{n=k}^{k} |a_n|^2 \cdot 4\pi^2 n^2 \sum_{n=k}^{k} |a_n|^2 \right)^{1/2}\\ &\le \left( \frac{1}{\delta} + 2\pi k \right) \sum_{n=k}^{k} |a_n|^2 .\end{aligned}\]

Theorem (Montgomery and Vaughan). If \(x_1,\ldots,x_R\) are \(\delta\) well-spaced, then \[\sum_{r=1}^R |S(x_r)|^2 \le (N + \delta^{-1} - 1) \sum_{n=M+1}^{M+N} |a_n|^2 .\]

Proof. It involves the duality of the bilinear form. Let \(\Delta = \Delta(N,\delta)\), \[\sum_{r=1}^R |S(x_r)|^2 \le \Delta \sum_{n=M+1}^{M+N} |a_n|^2\] is equivalent to \[\sum_{n=M+1}^{M+N} \left| \sum_{r=1}^R y_r\, e(n x_r) \right|^2 \le \Delta \sum_{r=1}^R |y_r|^2 ,\] for all \(y_r\). Then, we suppose there is a weight function such that \[\sum_{n=M+1}^{M+N} \left| \sum_{r=1}^R y_r e(n x_r) \right|^2 \le \sum_{n\in\mathbb{Z}} w(n) \left| \sum_{r=1}^R y_r e(n x_r) \right|^2\] with \(\sum_{n\in\mathbb{Z}} w(n) < \infty\), and put \[W(x) = \sum_{n\in\mathbb{Z}} w(n) e(n x).\] Then we expand the right-hand side and get \[= \sum_{r=1}^R \sum_{s=1}^R y_r \overline{y_s} \sum_{n\in\mathbb{Z}} w(n) e(n(x_r - x_s)) = \sum_{r=1}^R \sum_{s=1}^R y_r \overline{y_s} \, W(x_r - x_s).\] By a result in harmonic analysis, we could actually construct \(W(x)=0\) for \(1 \le \|x\| \le \delta\). Therefore, the above inequality only consists of \(|y_r|^2\), and such construction yields that \(W(0) = N - 1 + \delta^{-1}\), so the proof is complete.

Farey sequence of order \(Q\)

\[F_Q = \left\{ \frac{a}{q} : 1 \le a \le q, \; 1 \le q \le Q, \; (a,q) = 1 \right\}\] \[\left| \frac{a_1}{q_1} - \frac{a_2}{q_2} \right| = \frac{|a_1 q_2 - a_2 q_1|}{q_1 q_2} \ge \frac{1}{q_1 q_2} \ge \frac{1}{Q^2}.\] For different \(a_1, a_2, q_1, q_2\), then each of the points is spaced at least \(\delta = Q^{-2}\) apart.

Theorem. Let \(Q, N \ge 1\), and let \(a_n\) be complex numbers. Then \[\sum_{q \le Q} \sum_{\substack{a \,(\mathrm{mod}\, q) \\ (a,q)=1}} \left| \sum_{M < n \le M+N} a_n \, e\!\left( \frac{a n}{q} \right) \right|^2 \le (N + Q^2) \sum_{M < n \le M+N} |a_n|^2.\]

Applications I: In this chapter, we define the sieve as follows:

\[S(\mathcal{A}, \mathcal{P}, \Omega_p) = \{ n \in \mathcal{A} : n \; (\mathrm{mod} \; p) \notin \Omega_p \ \ \text{for any} \ \ p \in \mathcal{P} \}\] Let \(\mathcal{Z} = |S(\mathcal{A},\mathcal{P})|\) be the cardinality of the set.

Theorem (Montgomery’s large sieve). For the sieve \(S(\mathcal{A}, \mathcal{P}, \Omega_p)\) with \[\mathcal{A} \subset (M, M+N], \quad \omega(p) = |\Omega_p|, \quad \mathcal{Q} = \{ q \le Q : p \mid q \ \Rightarrow\ p \in \mathcal{P} \}\] then \[\mathcal{Z} \le \frac{N + Q^2}{L},\] where \[L = \sum_{q \in \mathcal{Q}} \mu^2(q) \prod_{p \mid q} \frac{\omega(p)}{p - \omega(p)}.\]

Proof. Let \[S(\alpha) = \sum_{n \in S(\mathcal{A},\mathcal{P},\Omega_p)} a_n \, e(\alpha n)\] with \(a_n\) complex. It suffices to prove that for each \(q \in \mathcal{Q}\), \[|S(0)|^2 \, \mu^2(q) \prod_{p \mid q} \frac{\omega(p)}{p - \omega(p)} \le \sum_{\substack{a=1 \\ (a,q)=1}}^{q} |S(a/q)|^2.\] Then, summing over \(q \in \mathcal{Q}\) with the large sieve inequality with \(a_n = 1\) for \(n \in S(\mathcal{A},\mathcal{P},\Omega_p)\) and \(a_n = 0\) otherwise, we obtain \[\mathcal{Z}^2 L \le (N + Q^2) \mathcal{Z} \quad\Rightarrow\quad \mathcal{Z} \le \frac{N + Q^2}{L}.\] We prove the above inequality by induction over the number of prime factors of \(q\). If \(q = p\), we have \[\begin{aligned} \sum_{\substack{a=1 \\ (a,p)=1}}^{p} |S(a/p)|^2 &= \sum_{a=1}^{p} |S(a/p)|^2 - |S(0)|^2\\ &= p\sum_{\substack{{b=1}\\b\notin \Omega_p}}^{p} \left| \sum_{\substack{n \in S(\mathcal{A},\mathcal{P},\Omega_p) \\ n \equiv b \ (\mathrm{mod}\ p)}} a_n \right|^2 - |S(0)|^2\\ &\le \frac{p}{p-\omega(p)} |S(0)|^2 - |S(0)|^2\\ &= \frac{\omega(p)}{p-\omega(p)} |S(0)|^2 \end{aligned}\] And if \(q = q_1 q_2\) with \((q_1, q_2) = 1\), and replace \(a_n e\!\left( \frac{n a_1}{q_1} \right)\) with \(a_n\), and by induction hypothesis for \(q_1 = q\), we obtain \[\sum_{\substack{a=1 \\ (a,q)=1}}^{q} \left| S\!\left( \frac{a}{q} \right) \right|^2 = \sum_{\substack{a_1=1 \\ (a_1,q_1)=1}}^{q_1} \left( \sum_{\substack{a_2=1 \\ (a_2,q_2)=1}}^{q_2} \left| \sum_{n \in S(\mathcal{A},\mathcal{P},\Omega_p)} a_n e\!\left( \frac{n a_1}{q_1} \right) e\!\left( \frac{n a_2}{q_2} \right) \right|^2 \right)\] \[\ge |S(0)|^2 \, \mu^2(q) \prod_{p \mid q} \frac{\omega(p)}{p - \omega(p)}.\]

Application II:

Corollary. Let \(\chi\) be a character \((\mathrm{mod}\ q)\) and put \(T(\chi) = \sum_{n=M+1}^{M+N} a_n \chi(n)\). Then for any \(Q \ge 1\), \[\sum_{q \le Q} \frac{q}{\varphi(q)} \sum_{\chi}{}^{*} |T(\chi)|^2 \le (N + Q^2) \sum_{n=M+1}^{M+N} |a_n|^2\] Here \(\sum_{\chi}^{*}\) denotes the sum over all primitive characters \(\chi \ (\mathrm{mod}\ q)\). It suffices to show that \[\sum_{\chi}{}^{*} |T(\chi)|^2 \le \frac{\varphi(q)}{q} \sum_{\substack{a=1 \\ (a,q)=1}}^{q} \left| \sum_{n=M+1}^{M+N} a_n e\!\left( \frac{n a}{q} \right) \right|^2.\] Note if \(\chi\) is primitive \((\mathrm{mod}\ q)\), then \[\chi(n) = \frac{1}{\tau(\overline{\chi})} \sum_{a=1}^{q} \overline{\chi}(a) e\!\left( \frac{n a}{q} \right)\] for all \(n\). Multiplying both sides by \(a_n\) and summing \(n\) from \(M+1\) to \(M+N\), we get \[T(\chi) = \frac{1}{\tau(\overline{\chi})} \sum_{a=1}^{q} \overline{\chi}(a) S(a/q)\] As \(|\tau(\chi)| = \sqrt{q}\) for \(\chi\) primitive, we find that \[\begin{aligned} \sum_{\chi}{}^{*} |T(\chi)|^2 &= \frac{1}{q} \sum_{\chi}{}^{*} \left| \sum_{a=1}^{q} \overline{\chi}(a) S(a/q) \right|^2\\ &\le \frac{1}{q} \sum_{\chi} \left| \sum_{a=1}^{q} \overline{\chi}(a) S(a/q) \right|^2,\end{aligned}\]

where \[\begin{aligned} \sum_{\chi} \left| \sum_{a=1}^{q} \overline{\chi}(a) S(a/q) \right|^2 &= \sum_{a=1}^{q} \sum_{b=1}^{q} S(a/q) \overline{S(b/q)} \sum_{\chi} \overline{\chi}(a) \chi(b)\\ &= \varphi(q) \sum_{\substack{a=1 \\ (a,q)=1}}^{q} |S(a/q)|^2\end{aligned}\]

Thus, the proof is complete.