Skip to main content

Notes on analytic number theory

Kiran S. Kedlaya

Chapter 16 A multiplicative large sieve inequality

In this chapter, we convert the additive large sieve inequality (Theorem 15.5), which involves characters of the additive group, into a result about Dirichlet characters.
🔗

Section 16.1 A specialization of the additive large sieve

We will use the additive large sieve inequality (Theorem 15.5) in the special case
\begin{equation} S = \{a/q: 1 \leq q \leq Q, 0 \leq a \lt q, \gcd(a,q) = 1\}\text{.}\tag{16.1.1} \end{equation}
Note that if \(a/q, a'/q' \in S\) are distinct and \(m \in \ZZ\text{,}\) then
\begin{equation} \left| \frac{a}{q} - \frac{a'}{q'} - n \right| = \left| \frac{*}{qq'} \right| \geq Q^{-2}\text{.}\tag{16.1.2} \end{equation}
That is, \(S\) is \(\delta\)-spaced for \(\delta = Q^{-2}\text{.}\) We then obtain the following.
🔗

Proof.

🔗

Section 16.2 The Bombieri–Davenport inequality

We now ask the question: what if we replace the exponentials in the large sieve by the primitive Dirichlet characters of all moduli \(q \leq Q\text{?}\) (One can prove a stronger inequality in which some terms correspond to imprimitive characters, but we won’t need this.)
🔗

Proof.

As in the proof of the functional equation for Dirichlet \(L\)-functions (Chapter 6), we use the expansion of primitive Dirichlet characters in terms of Gauss sums:
\begin{equation*} \chi(n) = \tau(\overline{\chi})^{-1} \sum_{a \in \ZZ/q\ZZ} \overline{\chi}(a) \exp(2\pi i an/q)\text{,} \end{equation*}
where
\begin{equation*} \tau(\chi) := \sum_{b \in \ZZ/q\ZZ} \chi(b) \exp(2 \pi i b/q) \end{equation*}
has the property that
\begin{equation*} |\tau(\chi)| = \sqrt{q}\text{.} \end{equation*}
If we put
\begin{equation*} S(\alpha) := \sum_{M \lt n \leq M+N} a_n \exp(2 \pi i \alpha n)\text{,} \end{equation*}
we can then write
\begin{equation*} \frac{q}{\phi(q)} \left| \sum_{M\lt n\leq M+N} a_n \chi(n) \right|^2 = \frac{1}{\phi(q)} \left| \sum_{a \in \ZZ/q\ZZ} \overline{\chi}(a) S(a/q) \right|^2\text{.} \end{equation*}
Summing over \(1 \leq q \leq Q\) and \(\chi\) primitive gives the left side of (16.2.1).
🔗
To obtain an upper bound, we sum over \(1 \leq q \leq Q\) and all \(\chi\text{,}\) primitive or not. By orthogonality of characters for the group \((\ZZ/q\ZZ)^\times\) (Theorem 4.10), this yields
\begin{equation*} \sum_{1 \leq q \leq Q} \sum_{a \in (\ZZ/q\ZZ)^\times} |S(a/q)|^2 = \sum_{1 \leq q \leq Q} \sum_{a \in (\ZZ/q\ZZ)^\times} \left| \sum_{M \lt m \leq M+N} a_n \exp(2 \pi i an/q) \right|^2 \end{equation*}
as an upper bound for the left side of (16.2.1). Applying Theorem 16.1 gives the right side of (16.2.1), completing the proof.
🔗
🔗
🔗

Section 16.3 An application of the large sieve

We will use the large sieve crucially in the Bombieri–Vinogradov theorem, but first let us illustrate its use with one of its original applications, due to Linnik.
🔗

Definition 16.3.

Let \(\{a_n\}_n\) be a sequence of complex numbers \(a_n\) with finite support. Let \(P\) be a set of primes. For each \(p \in P\text{,}\) we wish to exclude a set of residue classes \(\Omega_p\) of size \(\omega(p)\text{.}\) That is, we wish to compute \(Z\text{,}\) the sum of \(a_n\) over those \(n\) which do not reduce to a class in \(\Omega_p\) for any \(p \in P\text{.}\)
🔗
🔗
So far, we are in the setup of the sieve of Eratosthenes (Definition 11.6), but with slightly different notation. The difference is that we do not require \(\omega(p)\) to be as small as before; that’s what makes this a “large sieve”.
🔗

Proof.

Proof.

We first reduce to the case where \(q\) is prime. Suppose \(q = q_1q_2\) and we know the desired result for both \(q_1\) and \(q_2\text{.}\) By the Chinese remainder theorem,
\begin{align*} \sum_{a \in (\ZZ/q\ZZ)^*} \left|S\left( \frac{a}{q} \right) \right|^2 \amp= \sum_{a_1 \in (\ZZ/q_1\ZZ)^*} \sum_{a_2 \in (\ZZ/q_2\ZZ)^*} \left| S\left( \frac{a_1}{q_1 + \frac{a_2}{q_2}} \right) \right|^2\\ \amp\geq h(q_2) \sum_{a_1 \in (\ZZ/q_1\ZZ)^*} \left|S\left( \frac{a_1}{q_1} \right) \right|^2\\ \amp\geq h(q_1) h(q_2) |S(0)|^2 = h(q) |S(0)|^2 \end{align*}
It thus remains to prove the case where \(q\) is prime; we leave this case as an exercise (Exercise 16.4.3).
🔗
🔗
Here is Linnik’s application of the large sieve.
🔗

Definition 16.6.

For \(p\) prime, let \(q(p)\) be the least positive integer which is not a quadratic residue modulo \(p\text{.}\) It is conjectured that \(q(p) = O(p^\epsilon)\) for any \(\epsilon > 0\text{,}\) but unconditionally this is only known for \(\epsilon > e^{-1/2}/4 \cong 0.152\text{.}\) On the other hand, under the generalized Riemann Hypothesis (Conjecture 10.4), one can even improve this to \(q(p) = O(\log^2 p)\text{.}\)
🔗
🔗

Proof.

For convenience, we will prove instead that for some \(c = c(\epsilon)\text{,}\) for any \(N\) there are at most \(c\) primes \(p\leq \sqrt{N}\) with \(q(p) > N^\epsilon\text{.}\)
🔗
Let \(P\) be the set of primes \(p \leq \sqrt{N}\) such that \(\legendre{n}{p} = 1\) for all \(n \leq N^\epsilon\text{,}\) and let \(\Omega_p\) be the classes of quadratic nonresidues mod \(p\text{.}\) (This is indeed a large sieve because \(\omega(p) = (p-1)/2\text{,}\) so \(h(p) = (p-1)/(p+1) \sim 1/2\) as \(p \to \infty\text{,}\) whereas in our earlier examples \(\omega(p)\) was bounded.)
🔗
We will now sieve on the set \(\{1, \dots, N\}\text{,}\) i.e., take \(a_n = 1\) for \(1 \leq n \leq N\) and \(a_n = 0\) otherwise. The resulting sifted set includes all \(n \leq N\) with no prime divisors greater than \(N^\epsilon\text{;}\) if we let \(Z_\epsilon\) be the number of these, then Theorem 16.4 applied with \(Q = \sqrt{N}\) yields
\begin{equation*} Z_\epsilon \leq 2N H^{-1}\text{.} \end{equation*}
On the other hand, if we let \(X_\epsilon\) be the number of primes \(p \leq \sqrt{N}\) with \(q(p) > N^\epsilon\text{,}\) then because \(h(p) \geq 1/3\) for all \(p\text{,}\)
\begin{equation*} \frac{1}{3} X_\epsilon \leq \sum_{p \leq \sqrt{N}, q(p) \geq N^\epsilon} h(p) \leq H\text{.} \end{equation*}
Hence \(X_\epsilon Z_\epsilon \leq 6N\text{.}\)
🔗
To conclude, we need to show that \(Z_\epsilon \geq cN\) for some \(c>0\text{.}\) In fact it can be shown that \(Z_\epsilon \sim cN\) for some \(N\text{,}\) but as we don’t care about the particular constant, it will suffice to exhibit a special class of numbers being counted by \(Z_\epsilon\) which are sufficiently numerous. Namely, take \(n = m p_1 \cdot p_k \leq N\) with \(N^{\epsilon - \epsilon^2} \lt p_j \lt N^\epsilon\) for \(j=1, \dots, k = \epsilon^{-1}\text{;}\) then
\begin{equation*} Z_\epsilon \geq \sum_{p_1,\dots,p_k} \left\lfloor \frac{N}{p_1 \cdots p_k} \right\rfloor \geq cN\text{,} \end{equation*}
completing the proof.
🔗
🔗
🔗

Exercises 16.4 Exercises

1.

Prove the following multivariate version of the additive large sieve inequality (but without optimizing the constant). Fix \(\delta > 0\) and \(d \geq 1\text{,}\) and let \(\alpha_i = (\alpha_{i,1}, \dots, \alpha_{i,d}) \in \RR^d/\ZZ^d\) be points which are \(\delta\)-spaced, in the sense that the distance from each \(\alpha_{i,k}-\alpha_{j,k}\) to the nearest integer is at least \(\delta\) (whenever \(i \neq j\) and \(1 \leq k \leq d\)). Prove that there exists \(c = c(d)\) (independent of \(\delta\) and the \(\alpha_i\)) such that for any \(a_n \in \CC\) with \(n\) running over \(\{1, \dots, N\}^d\text{,}\)
\begin{equation*} \sum_i \left| \sum_n a_n \exp(2 \pi i (n \cdot \alpha_i)) \right|^2 \leq c (\delta^{-d} + N^d) \sum_n |a_n|^2\text{.} \end{equation*}
🔗
🔗

2.

Prove directly (by expanding the squares) that if we take take all characters, not just the primitive ones, of a single modulus \(q\text{,}\) then the large sieve inequality holds with the constant \(q+N\text{.}\) (This is not very useful in practice.)
🔗
🔗

3.

Prove Lemma 16.5 in the case that \(q\) is prime.
🔗
Hint.
There is no loss of generality in assuming that there is at most one \(n\) in each residue class modulo \(p\text{,}\) and none in the classes in \(\Omega_p\text{,}\) such that \(a_n \neq 0\text{.}\) Then use orthogonality of characters on \(\ZZ/q\ZZ\text{.}\)
🔗
🔗
🔗
🔗
🔗
PrevTopNext