1 Bombieri–Vinogradov

1.1 Statement

The main result is the Bombieri–Vinogradov theorem, which gives a strong estimate for primes in arithmetic progressions on average over moduli.

Theorem 1

For each fixed \(A \geq 0\),

\[ \sum _{q \le Q} \max _{y \le x} \max _{a \in (\mathbb {Z}/q\mathbb {Z})^*} \left| \psi (y; q, a) - \frac{y}{\varphi (q)} \right| \ll _A \frac{x}{(\log x)^{A}} \]

uniformly for all \(x \ge 2\) and \(1 \le Q \le \frac{\sqrt{x}}{(\log x)^{A+3}}\).

Proof ▶

Apply 7 and absorb the error terms using 9.

1.2 Assumptions

We take Siegel–Walfisz and the large sieve inequality as axioms.

Assumption 2

✓

Let \(A, C {\gt} 0\). If \(1 \leq q \leq (\log x)^C\) and \(a \in (\mathbb {Z}/q\mathbb {Z})^*\), then

\[ \psi (x;q,a) = \frac{x}{\varphi (q)} + O_{A, C}\left(\frac{x}{(\log x)^A}\right). \]

Assumption 3

✓

Let \(Q \ge 1\), \(H \in \mathbb {Z}\), \(N \in \mathbb {Z}_{\ge 1}\) and \(c = (c_{H+1}, \dots , c_{H+N}) \in \mathbb {C}^N\) We then have

\[ \sum _{q \le Q} \mathop{{\sum \nolimits ^{*}}}_{\chi \pmod q} \frac{q}{\varphi (q)} \left| \sum _{H {\lt} n \le H+N} c_n \chi (n) \right|^2 \ll (N+Q^2) \| \vec{c} \| _2^2, \]

1.3 Definitions

Definition 4

✓

\[ \Delta _f(x ;q, a) := \sum _{n \le x, ~ n \equiv a \pmod q} f(n) ~ - \frac{1}{\varphi (q)} \sum _{n \le x, (n, q) = 1} f(n) \]

for \(x \ge 1\), \(q \in \mathbb {N}\)

Theorem 5

✓

\[ \Delta _f(y ;q, a) = \frac{1}{\varphi (q)} \sum _{\chi \pmod{q}, \chi \ne \chi _0} \bar\chi (a) \sum _{n \le y} f(n) \chi (n) \]

Proof ▶

Definition 6

✓

For \(f : \mathbb {N}\rightarrow \mathbb {R}\) and \(r : \mathbb {N}\) we use \(f_r\) to denote \(n \mapsto f(n) 1_{(n, r) = 1}\)

1.4 Reduction to \(\Delta _\Lambda \)

Bombieri–Vinogradov for \(\psi \) is reduced to a bound for \(\Delta _\Lambda \) via the following steps.

Theorem 7

For each fixed \(A \ge 0\) we have

\[ \sum _{q\le Q} \max _{\sqrt x \le y \le x} \max _{a \in (\mathbb {Z}/q\mathbb {Z})^*} \left| \Delta _{\Lambda }(y; q,a) \right| \ll _A \frac{x}{(\log x)^{A}} \]

uniformly for \(x \ge 2\) and \(1 \le Q \le \sqrt{x}/(\log (x))^{A+3}\)

Proof ▶

Follows from 13 and the triangle inequality, combining the bounds 16, 23, and 35.

Theorem 8

✓

\[ \Delta _{\Lambda }(x; q, a) = \psi (x; q,a) - \frac{1}{\varphi (q)} \sum _{n \le x, n \not\mid q} \Lambda (n) \]

Proof ▶

Theorem 9

✓

For all \(A \in \mathbb {N}\),

\[ \sum _{n \le x, n \not\mid q} \Lambda (n) = x + O_A(x/\log (x)^A+\log q \log x) \]

Proof ▶

1.5 Vaughan’s Identity

The von Mangoldt function decomposes as \(\Lambda = \Lambda ^\sharp + \Lambda ^\flat + \Lambda _{\le U}\), where \(UV \le \sqrt{x}\) and \(U, V \ge e^{\sqrt{\log x}}\).

Definition 10

✓

\(\Lambda ^\sharp = \mu _{\le V} * \log - (\Lambda _{\le U} * \mu _{\le V}) * 1\)

Definition 11

✓

\(\Lambda ^\flat = (\Lambda _{{\gt}U} * 1) * \mu _{{\gt}V}\)

Definition 12

✓

\(\Lambda _{\le U} = 1_{≤ U} \cdot \Lambda \)

Theorem 13

✓

Decompose \(\Lambda = \Lambda ^\sharp + \Lambda ^\flat + \Lambda _{\le U}\)

Proof ▶

1.6 Small Primes (\(\Lambda _{\le U}\))

The contribution of the small part \(\Lambda _{\le U}\) is bounded trivially.

Lemma 14

✓

\[ \sum _{n \le y} \Lambda (n) \ll U \log {x} \]

Proof ▶

Lemma 15

✓

For \(y, U {\gt} 0\), \(q \in \mathbb {N}\) and \(a \in \mathbb {Z}/q\mathbb {Z}\),

\[ |\Delta _{\Lambda _{\le U}}(y;\, q,\, a)| \ll U \log {x} \]

Proof ▶

Theorem 16

✓

For each fixed \(A \ge 0\), \(x \ge 2\) and \(1 \le Q \le \sqrt{x}/(\log x)^{A+3}\),

\[ \sum _{q \le Q} \max _{\sqrt{x} \le y \le x} \max _{a \in (\mathbb {Z}/q\mathbb {Z})^*} |\Delta _{\Lambda _{\le U}}(y;\, q,\, a)| \le Q\sqrt{x} \ll _A \frac{x}{(\log x)^{A+2}} \]

Proof ▶

1.7 Type I Sums (\(\Lambda ^\sharp \))

The sharp part \(\Lambda ^\sharp \) is a type I sum, bounded via Abel summation.

Lemma 17

✓

If \(f\) is an arithmetic function supported on \([1, y]\) then

\[ \Delta _{f*g}(x;\, q,\, a) = \sum _{\substack {k \le y \\ (k,q)=1}} f(k)\, \Delta _g\! \left(\frac{x}{k};\, q,\, a\bar{k}\right) \]

Proof ▶

Lemma 18

✓

For \(x \ge 1\), \(q \in \mathbb {N}\) and \(a \in (\mathbb {Z}/q\mathbb {Z})^*\),

\[ |\Delta _1(x;\, q,\, a)| \le 1 \]

Proof ▶

Carefully consider length \(q\) intervals. Alternatively, write

\[ \Delta _1(t;\, q,\, a) = \frac{1}{\varphi (q)} \sum _{a' \in (\mathbb {Z}/q\mathbb {Z})^*} \left( \sum _{\substack {n \le t \\ n \equiv a \pmod{q}}} 1 - \sum _{\substack {n \le t \\ n \equiv a’ \pmod{q}}} 1 \right) \]

and note each inner difference is bounded by \(1\) in absolute value.

Lemma 19

✓

If \(g\) is continuously differentiable on \([1, x]\) then

\[ \Delta _g(x;\, q,\, a) = \Delta _1(x;\, q,\, a)\, g(x) - \int _1^x \Delta _1(t;\, q,\, a)\, g'(t)\, \mathrm{d}t \]

Proof ▶

By Abel summation.

Lemma 20

✓

If \(g\) is continuously differentiable and monotone on \([1, x]\) with \(g(1) = 0\), then for all \(t \ge 1\) and \(a \in (\mathbb {Z}/q\mathbb {Z})^*\),

\[ |\Delta _g(x;\, q,\, a)| \le 2g(x) \]

Proof ▶

Theorem 21

✓

Let \(v \ge 0\) and let \(f\) be an arithmetic function supported on \([1, x]\). For \(x \ge 2\), \(q \in \mathbb {N}\) and \(a \in (\mathbb {Z}/q\mathbb {Z})^*\),

\[ |\Delta _{f * \log ^v}(x;\, q,\, a)| \le 2(\log x)^v \sum _{k \le x} |f(k)| \]

Proof ▶

Straightforward application of the previous lemmas.

Theorem 22

For \(U, V \ge 1\), \(x \ge 2\), \(q \in \mathbb {N}\), \(r \le x\) and \(a \in (\mathbb {Z}/q\mathbb {Z})^*\),

\[ \max _{y \le x} \max _{a \in (\mathbb {Z}/q\mathbb {Z})^*} |\Delta _{\Lambda ^\sharp _r}(y;\, q,\, a)| \ll UV \log x \]

Proof ▶

Apply 21 twice: once with \(f = \mu _{\le V,\, r}\), \(v = 1\), and once with \(f = \Lambda _{\le U} * \mu _{\le V,\, r}\), \(v = 0\), \(y = UV\).

Theorem 23

For each fixed \(A \ge 0\), \(x \ge 2\) and \(1 \le Q \le \sqrt{x}/(\log x)^{A+3}\),

\[ \sum _{q \le Q} \max _{\sqrt{x} \le y \le x} \max _{a \in (\mathbb {Z}/q\mathbb {Z})^*} |\Delta _{\Lambda ^\sharp }(y;\, q,\, a)| \ll _A \frac{x}{(\log x)^A} \]

Proof ▶

1.8 Type II Sums (\(\Lambda ^\flat \))

1.8.1 Definitions

Definition 24

✓

\[ S_r(y, \xi ) := \left|\sum _{n \le y} \Lambda _r^\flat (n)\, \xi (n)\right| \]

Definition 25

✓

\[ T_r(x, Q) := \sum _{(\log x)^C {\lt} d \le Q/r} \frac{1}{\varphi (d)} \mathop{{\sum \nolimits ^{*}}}_{\xi \pmod{d}} \max _{\sqrt{x} \le y \le x} S_r(y, \xi ) \]

1.8.2 Reduction to character sums

Lemma 26

This is a standard result. Let \(f\) be a function from Dirichlet characters. Then

\[ \sum _{\substack {\chi \pmod{q} \\ \chi \ne \chi _0}} f(\chi ) = \sum _{d \mid q} \mathop{{\sum \nolimits ^{*}}}_{\xi \pmod{d}} f(1_{(n,q)=1}\xi ) \]

Proof ▶

Lemma 27

Let \(f\) be an arithmetic function. For \(r \le x\), \(q {\gt} 1\) and \((a, q) = 1\),

\[ \mathop{{\sum \nolimits ^{*}}}_{\xi \pmod{q}} \bar\xi (a) \sum _{n \le y} \xi (n) f_r(n) = \sum _{d \mid q} \mu (q/d)\, \varphi (d)\, \Delta _{f_{rq}}(y;\, d,\, a) \]

Proof ▶

Fix \(P \in \mathbb {N}\) with \(q \mid P\). Define \(F_P\) and \(G_P\) on divisors of \(P\) by

\begin{align*} F_P(q) & := \sum _{\chi \ne \chi _0 \pmod{q}} \bar\chi (a) \sum _{n \le y} \chi (n) f_{rP}(n) = \Delta _{f_{rP}}(y;\, q,\, a), \\ G_P(d) & := \mathop{{\sum \nolimits ^{*}}}_{\xi \pmod{d}} \bar\xi (a) \sum _{n \le y} \xi (n) f_{rP}(n) \quad (d {\gt} 1),\quad G_P(1) = 0. \end{align*}

Since every non-principal character mod \(q\) factors through a unique primitive character, \(F_P(q) = \sum _{d \mid q} G_P(d)\). By Möbius inversion,

\[ G_P(q) = \sum _{d \mid q} \mu (q/d)\, F_P(d) = \sum _{d \mid q} \mu (q/d)\, \Delta _{f_{rP}}(y;\, d,\, a). \]

Set \(P = q\) to conclude.

Lemma 28

\[ \left|\Delta _{\Lambda ^\flat }(y;\, q,\, a)\right| \le \frac{1}{\varphi (q)} \left|\sum _{\substack {d \mid q \\ 1 {\lt} d \le (\log x)^C}} \sum _{s \mid d} \mu (d/s)\, \varphi (s)\, \Delta _{\Lambda ^\flat _q}(y;\, s,\, a)\right| + \frac{1}{\varphi (q)} \sum _{\substack {d \mid q \\ d {\gt} (\log x)^C}} \mathop{{\sum \nolimits ^{*}}}_{\xi \pmod{d}} S_{q/d}(y, \xi ) \]

Proof ▶

Theorem 29

\[ \frac{1}{\varphi (q)} \left|\sum _{\substack {d \mid q \\ 1 {\lt} d \le (\log x)^C}} \sum _{s \mid d} \mu (d/s)\, \varphi (s)\, \Delta _{\Lambda ^\flat _q}(y;\, s,\, a)\right| \ll _{A,C} \frac{x}{\varphi (q)\, (\log x)^{A+1}} \]

Proof ▶

Push the absolute values inside, then

\begin{align*} \sum _{d \mid q,\, d \le (\log x)^C} \sum _{s \mid d} \varphi (s)\, \left|\Delta _{\Lambda ^\flat _q}(y;\, s,\, a)\right| & \ll _{A,C} \sum _{d \le (\log x)^C} \left(\sum _{s \mid d} \varphi (s)\right) \frac{x}{(\log x)^{A+2C+1}} \\ & \ll \frac{x}{(\log x)^{A+2C+1}} \sum _{d \le (\log x)^C} d \\ & \ll \frac{x}{(\log x)^{A+1}}. \end{align*}

Theorem 30

\[ \sum _{q \le Q} \max _{\substack {\sqrt{x} \le y \le x \\ a \in (\mathbb {Z}/q\mathbb {Z})^*}} \left|\Delta _{\Lambda ^\flat }(y;\, q,\, a)\right| \le \sum _{r \le Q} \frac{T_r(x,Q)}{\varphi (r)} + O\! \left(\frac{x}{(\log x)^A}\right) \]

Proof ▶

Sum the error from 29 over \(q \le Q\) using \(\sum _{n \le x} 1/\varphi (n) \ll \log x\), then regroup the main sum by \(r = q/d\).

1.8.3 Large sieve estimates

Theorem 31

Let \(f\) and \(g\) be arithmetic functions supported on \([1, M]\) and \([1, N]\) respectively. For \(x, Q \ge 1\),

\[ \sum _{q \le Q} \mathop{{\sum \nolimits ^{*}}}_{\chi \pmod{q}} \frac{q}{\varphi (q)} \max _{y \le x}\left|\sum _{n \le y} (f*g)(n)\chi (n)\right| \ll \left(\sqrt{MN} + \sqrt{M}\, Q + \sqrt{N}\, Q + Q^2\right)(\log x)\, \| f\| _2\, \| g\| _2 \]

Proof ▶

Uses Cauchy–Schwarz and the large sieve inequality (3). The proof in the book uses the classical version of Perron’s integral formula as \(1_{n \le x} = \int _{-T}^{T}\frac{(x/n)^{\alpha +it}}{\alpha +it} dt/(2\pi ) + O(...)\) But we have a different version in PNT+. I haven’t worked out how this changes the proof yet.

Lemma 32

\[ \Lambda ^\flat (n) = \sum _{U {\lt} 2^j \le 2x/V} (f_j * g_j)(n) \quad \text{for } n \le x, \]

where \(f_j(k) = (\Lambda _{{\gt}U} * 1)(k)\, 1_{2^{j-1} {\lt} k \le 2^j}\) and \(g_j(\ell ) = \mu (\ell )\, 1_{V {\lt} \ell \le x/2^{j-1}}\).

Proof ▶

Theorem 33

For \(x, Q \ge 2\), \(U, V \in [1, x]\) and \(r \in \mathbb {N}\),

\[ \sum _{q \le Q} \mathop{{\sum \nolimits ^{*}}}_{\chi \pmod{q}} \frac{q}{\varphi (q)}\, \max _{y \le x} S_r(y, \chi ) \ll \left(x + \frac{Qx}{\sqrt{U}} + \frac{Qx}{\sqrt{V}} + Q^2\sqrt{x}\right)(\log x)^3 \]

Proof ▶

Apply the dyadic decomposition 32 (restricted to integers coprime to \(r\)) and apply 31 to each dyadic piece. When summing over \(j\) note \(U \le 2^j\), so \(\sum _{U \le 2^j} 2^{-j/2} \ll 1/\sqrt{U}\).

Theorem 34

\[ T_r(x,Q) \ll \frac{x}{(\log x)^{C-3}} + \frac{x(\log x)^4}{\sqrt{U}} + \frac{x(\log x)^4}{\sqrt{V}} + \frac{Q\sqrt{x}\, (\log x)^3}{r} \]

Proof ▶

Divide the sum defining \(T_r\) into dyadic intervals in \(d\) and apply 33.

Theorem 35

For each fixed \(A \ge 0\), \(x \ge 2\) and \(1 \le Q \le \sqrt{x}/(\log x)^{A+3}\),

\[ \sum _{q \le Q} \max _{\sqrt{x} \le y \le x} \max _{a \in (\mathbb {Z}/q\mathbb {Z})^*} \left|\Delta _{\Lambda ^\flat }(y;\, q,\, a)\right| \ll _A \frac{x}{(\log x)^A} \]

Proof ▶

Plug the bound from 34 into 30, then choose \(U = V = e^{\sqrt{\log x}}\) and \(C = A + 4\).