18.785: Analytic Number Theory, MIT, spring 2007 (K.S. Kedlaya)
The Bombieri-Vinogradov theorem (statement)
In this unit, we state the Bombieri-Vinogradov theorem, which is a surprisingly strong
control on the error terms in the prime number theorem in arithmetic progressions. We alsomention some related theorems and conjectures. To attack these (which we will do in thenext unit), we will need to bring to bear everything we have studied in the course so far!

1Statement of the theorem

For m, N coprime positive integers, putXψ(x; N, m) =n≤x,n≡m

Λ(n).

(mod N )Recall that the prime number theorem in arithmetic progressions says ψ(x; N, m) ∼ x/φ(N ),and that unconditionally we could get an error termx
ψ(x; N, m) =+ O(x(log x)−A )φ(N )for any fixed A > 0. This is only meaningful if N = O((log x)A ). However, under GRH (forthe Dirichlet characters of modulus N ),x+ O(x1/2 (log x)2 ),ψ(x; N, m) =φ(N )and this is meaningful for N = O(x1/2 (log x)−2 ).
The Bombieri-Vinogradov theorem is an amazingly strong unconditional replacement for
the GRH bound. It says that if you pick out the worst error term modulo N for each N up
to about x1/2 , and add these up, you get roughly what GRH predicts you should get.
Theorem 1 (Bombieri-Vinogradov). For any fixed A > 0, there exist constants c = c(A)and B = B(A) such thatXN ≤Q

max ∗ ψ(x; N, m) −m∈(Z/N Z)x≤ cx(log x)−Aφ(N )for Q = x1/2 (log x)−B .
It is expected that one can do better than this.
Conjecture 2 (Elliott-Halberstam). For any fixed A > 0 and  > 0, there exists c > 0 suchthatXx≤ cx(log x)−Amax ∗ ψ(x; N, m) −m∈(Z/N Z)
φ(N )
N ≤Q
for Q = x1− .
1This conjecture appears to be extremely hard; for instance, it is not known to follow from
GRH. One of the results of Goldston-Pintz-Yıldırım is that the Elliott-Halberstam almost
implies the twin primes conjecture: it implies that there are infinitely many pairs of primes
at distance ≤ 16. In fact, this (with 16 replaced by some other constant, depending on )
would follow if we could prove the weaker version of Elliott-Halberstam in which Q = x1/2+ ,for any fixed  > 0. (Even that does not follow from GRH.)
Note that in the Bombieri-Vinogradov theorem, for each modulus N we look at the worst
error term among arithmetic progressions of that modulus. If we instead average over theprogressions, we should be able to take Q larger, and in fact that is what happens. (Note:there is a typo in the statement of the theorem in Iwaniec-Kowalski.)
Theorem 3 (Barban, Davenport, Halberstam). For any fixed A > 0, there exist constantsc = c(A) and B = B(A) such that
2XX x≤ cx2 (log x)−A
ψ(x; N, m) −φ(N )∗N ≤Qm∈(Z/N Z)

for Q = x(log x)−B .
Finally, we note that Bombieri proved a slightly stronger result, which I will not beproving in this course. (See Davenport §28 for a proof by Montgomery.)
Theorem 4. For any fixed A > 0, there exists c > 0 such thatXx≤ cx1/2 Q(log x)5max ∗ ψ(x; N, m) −m∈(Z/N Z)
φ(N )
N ≤Q

for x1/2 (log x)−A ≤ Q ≤ x1/2 .

Exercises
1. (a) Check that Theorem 4 implies Theorem 1.
(b) Check that Conjecture 2 implies a slightly weakened version of Theorem 3, in
which we take Q = x1− .
2. Use the Bombieri-Vinogradov theorem, plus the strong Brun-Titchmarsh inequality
y2y+Oπ(x + y; N, m) − π(x; N, m) <φ(N ) log(y/N )N log2 (y/N )(where π(x; N, m) is the number of primes p ≤ x with p ≡ m (mod N )) to prove thatX
ζ(2)ζ(3)τ (p − 1) ∼x,ζ(6)p≤xwhere τ (n) counts the number of divisors of n. (Hint: √use Dirichlet’s hyperbola method
to reduce to counting primes ≡ 1 (mod d) over d ≤ x.)2