Skip to main content

Notes on analytic number theory

Kiran S. Kedlaya

Chapter 19 The Bombieri–Vinogradov theorem: proof

In this chapter, we prove the Bombieri–Vinogradov theorem in the form stated in Theorem 18.1.

Section 19.1 Bounding character sums

Definition 19.1.

For \(f\) an arithmetic function, put
\begin{equation*} D_f(x; N, m) := \sum_{n \leq x, n \equiv m \pmod{N}} f(n) - \frac{1}{\phi(N)} \sum_{n \leq x, n \in (\ZZ/N\ZZ)^*} f(n). \end{equation*}
That is, \(D_f(x; N,m)\) measures the deviation between the sum of \(f\) on an arithmetic progression versus the sum on all arithmetic progressions of the same modulus.
The following lemma tells us that bounding \(D_f(x; N, m)\) allows us to control the sum of \(f\) twisted by a Dirichlet character.
By Möbius inversion (Lemma 12.3), we can write
\begin{equation*} \sum_{n \in (\ZZ/s\ZZ)^*} f(n) \chi(n) = \sum_{k | s} \mu(k) \sum_{n \equiv 0\,(k)} f(n) \chi(n). \end{equation*}
We split this sum on \(k\) at \(K = \Delta^{-6}\text{.}\) We bound the sum for each fixed \(k > K\) by Cauchy–Schwarz; the total is thus dominated by
\begin{equation*} \sum_{k | s, k > K} |f|_2 (x/k)^{1/2} \leq |f|_2 x^{1/2} K^{-1/2} \tau(s). \end{equation*}
For the terms \(k \leq K\text{,}\) we write the sum as (using M\"obius inversion again)
\begin{equation*} \sum_{k|s, k \leq K} \mu(k) \sum_{\ell | k} \mu(\ell) \sum_{n \in (\ZZ/\ell\ZZ)^*} f(n) \chi(n). \end{equation*}
We split the inside sum over classes modulo \(\ell r\text{;}\) on each class, we apply (19.1.1). Since we are summing over all residue classes, and \(\chi\) is nonprincipal, the main terms cancel out; the sum is thus dominated by
\begin{equation*} |f| x^{1/2} \Delta^9 \sum_{k|s, k \leq K} \sum_{\ell|k} |\mu(\ell)| \phi(\ell r) \leq |f|_2 x^{1/2} \Delta^9 K \phi(r) \tau(s). \end{equation*}
Since \(K = \Delta^{-6}\text{,}\) we may add the two bounds to give the desired inequality.
Using the multiplicative large sieve inequality, we obtain the following.
We have
\begin{equation*} D_h(xy; N, a) = \frac{1}{\phi(N)} \sum_{\chi \neq \chi_0} \overline{\chi}(a) \left( \sum_m f(m) \chi(m) \right) \left( \sum_n g(n) \chi(n) \right), \end{equation*}
with \(\chi\) running over Dirichlet characters of modulus \(N\text{.}\) Rewriting this as a sum only over primitive characters (factoring \(N = rs\text{,}\) where \(r\) is the “primitive modulus”), and using the fact that \(\phi(rs) \geq \phi(r) \phi(s)\) for all \(r,s\text{,}\) we can bound the left side of the desired inequality by
\begin{equation} \sum_{s \leq Q} \frac{1}{\phi(s)} \sum_{1 \lt r \leq Q} \frac{1}{\phi(r)} \sum_{\chi} \left| \sum_{(m,s)=1} f(m) \chi(m) \right| \left| \sum_{(n,s)=1} g(n) \chi(n) \right|,\tag{19.1.2} \end{equation}
with \(\chi\) now running over primitive characters of level \(r\text{.}\)
We now split the sum over \(r\) at \(R = \Delta^{-1}\text{.}\) For \(r \leq R\text{,}\) we apply Lemma 19.2; those terms are dominated by
\begin{equation*} |f| |g| y^{1/2} \Delta^3 \sum_{s \leq Q} \frac{\tau(s)}{\phi(s)} \sum_{r \leq R} r \leq c |f| |g| y^{1/2} \Delta^3 R^2 \log^2 Q. \end{equation*}
(Note: we are not doing anything to the \(g\) terms other than bounding the whole sum by \(|g|\) and pulling it out. We apply the lemma to the \(f\) terms.) For \(r > R\text{,}\) we split the sum further into ranges like \(P \lt r \leq 2P\) and apply the multiplicative large sieve inequality (Theorem 17.2) in each range. More precisely, we apply Theorem 17.2 twice: once with the \(f\) sum to obtain
\begin{equation*} \sum_{P \lt r \leq 2P} \frac{1}{\phi(r)} \sum_{\chi} \left| \sum_{(m,s)=1} f(m) \chi(m) \right|^2 \leq \frac{1}{P} (4P^2 + x -1)|f|_2^2, \end{equation*}
and again with the \(g\) sum. Putting together with Cauchy–Schwarz, we get a bound
\begin{equation*} \sum_{P \lt r \leq 2P} \frac{1}{\phi(r)} \sum_{\chi} \left| \sum_{m \in (\ZZ/s\ZZ)^*} f(m) \chi(m) \right| \left| \sum_{n \in (\ZZ/s\ZZ)^*} g(n) \chi(n) \right| \leq \frac{1}{P} (4P^2 + x)^{1/2} (4P^2 + y)^{1/2} |f|_2 |g|_2. \end{equation*}
Now summing over \(P = R, 2R, \dots\) until \(P > Q\text{,}\) we get a bound on the sum over \(r\) in (19.1.2) of
\begin{equation*} c|f|_2|g|_2 (Q + x^{1/2} + y^{1/2} + x^{1/2} y^{1/2} R^{-1}). \end{equation*}
(That \(R^{-1}\) is the reason we had to limit this argument to \(r\) large.) The sum over \(s\) throws on another two factors of \(\log Q\text{,}\) yielding the claim.

Section 19.2 Proof of the theorem

We now proceed to the proof of the Bombieri–Vinogradov theorem. First, we mention an identity of Vaughan that will be useful: for any \(y,z \geq 1\) and \(n > z\text{,}\)
\begin{equation} \Lambda(n) = \sum_{b \leq y, b|n} \mu(b) \log \frac{n}{b} - \sum_{b \leq y, c \leq z, bc | n} \mu(b) \Lambda(c) + \sum_{b > y, c > z, bc |n} \mu(b) \Lambda(c). \tag{19.2.1} \end{equation}
Given \(x\text{,}\) define the incomplete logarithm
\begin{equation*} \lambda(\ell) = \log \ell - \sum_{k \leq x^{1/5}, k|\ell} \Lambda(k); \end{equation*}
then (19.2.1) with \(y=z=x^{1/5}\) implies that for \(x^{1/5} \lt n \leq x\text{,}\)
\begin{equation} \Lambda(n) = \sum_{\ell m = n, m \leq x^{1/5}} \lambda(\ell)\mu(m) + \sum_{\ell m = n, x^{1/5} \lt m \leq x^{4/5}} \lambda(\ell)\mu(m).\tag{19.2.2} \end{equation}
Let \(\Lambda_0(n)\) and \(\Lambda_1(n)\) denote the two sums on the right side of (19.2.2). Then
\begin{equation*} D_\Lambda(x; N, m) = D_{\Lambda_0}(x; N, m) + D_{\Lambda_1}(x; N, m) + O(x^{1/5} \log x), \end{equation*}
with the error term coming from terms with \(n \lt x^{1/5}\text{.}\)
It is straightforward to prove that
\begin{equation} \sum_{N \leq Q} \max_{m \in (\ZZ/N\ZZ)^*} |D_{\Lambda_0}(x; N, m)| = O(Q x^{2/5} \log x),\tag{19.2.3} \end{equation}
so we concentrate on the contribution from \(\Lambda_1\text{.}\) We want to apply Theorem 19.3, but we cannot write the sum \(\Lambda_1(n)\) as a convolution because of the restriction \(n \leq x\text{.}\)
To get around this, we cut the interval \(1 \leq n \leq x\) into \(O(\delta^{-1})\) subintervals of the form \(y \lt n \leq (1 + \delta)y\text{,}\) where \(x^{1/5} \lt \delta \leq 1\) is a parameter we will set later. We cover the summation range
\begin{equation*} \ell m = n, x^{1/5} \lt m \leq x \end{equation*}
by ranges
\begin{equation*} \ell m = n, L \lt \ell \leq (1+\delta) L, M \lt m \leq (1 + \delta) M \end{equation*}
with \(L,M\) taking values \((1+\delta)^j\text{.}\) We run \(L,M\) over the ranges \(x^{1/5} \lt L,M \lt x^{4/5}\) with \(LM = x\text{;}\) the only trouble is that we do not properly cover the areas \(n \lt x^{1/5}\) and \((1+\delta)^{-1} x \lt n \lt (1+\delta)x\text{.}\) The contribution from the error regions is \(O(\delta N^{-1} x \log x)\text{.}\)
What remains is the sum over \(L,M\) of
\begin{equation*} D(L,M; N, m) = \sum_{l,m \equiv m \pmod{N}} \lambda(\ell) \mu(m) - \frac{1}{\phi(N)} \sum_{lm \in (\ZZ/N\ZZ)^*}, \end{equation*}
where \(l,m\) run over \(L \lt \ell \leq (1+\delta) L, M \lt m \leq (1 + \delta) M\text{.}\) For each \(L,M\text{,}\) we may apply Theorem 19.3 with \(\Delta = (\log x)^{-A}\text{;}\) the hypothesis (19.1.1) is satisfied by virtue of the Siegel-Walfisz theorem (Theorem 11.11). If we take \(Q = \Delta x^{1/2}\text{,}\) we get
\begin{equation*} \sum_{N \leq Q} \max_{m \in (\ZZ/N\ZZ)^*} |D(L,M; N,m)| = O(\delta \Delta x (\log x)^3). \end{equation*}
Summing over \(L,M\text{,}\) we obtain
\begin{equation*} \sum_{N \leq Q} \max_{m \in (\ZZ/N\ZZ)^*} |D_{\Lambda_1}(x; N,m)| = O((\delta^{-1} x + \Delta) x (\log x)^3. \end{equation*}
We now choose \(\delta = \Delta^{1/2}\text{,}\) so this bound becomes \(\Delta^{1/2} x (\log x)^3\text{.}\) Adding back in (19.2.3) gives
\begin{equation*} \sum_{N \leq \Delta x^{1/2}} \max_{m \in (\ZZ/N\ZZ)^*} \left| \psi(x; N, m) - \frac{\psi(x)}{\phi(N)} \right| = O(\Delta^{1/2} x (\log x)^3). \end{equation*}
Using the prime number theorem with error term (Theorem 8.7), we can take \(\psi(x) = x + O(\delta x)\text{.}\) This gives the claim with \(B(A) = 2A + 6\text{.}\)

Section 19.3 The Barban-Davenport-Halberstam theorem

We leave the proof of the Barban-Davenport-Halberstam theorem (Theorem 18.4) to the reader; it is actually somewhat simpler than Bombieri-Vinogradov. Here is the key step.
We note in passing the following corollary.

Exercises 19.4 Exercises

<Prev^TopNext>