Here is a frustrating fact about the primes. We believe — via the Generalised Riemann Hypothesis — that the primes are shared out beautifully evenly among the residue classes modulo q: the count of primes up to x lying in a class a \bmod q should be about x/\varphi(q), with an error no bigger than roughly \sqrt{x}. But we cannot prove GRH for even a single modulus. Unconditionally, our only tool — the Siegel–Walfisz theorem — gives that good error only for laughably small moduli, up to about (\log x)^A. Everything larger is, individually, a mystery.

The Bombieri–Vinogradov theorem (Enrico Bombieri and A. I. Vinogradov, independently, 1965) performs a small miracle. It says that even though we can't control any single large modulus, we can control almost all of them at once. On average over q right up to nearly \sqrt{x}, the primes are as equidistributed as GRH would predict. It is, in a phrase that has stuck, "the Generalised Riemann Hypothesis on average" — and it is completely unconditional.

The players: \psi(x;q,a) and its target

Recall the weighted prime count in an arithmetic progression. Using the von Mangoldt weight \Lambda(n) (which is \log p on prime powers p^k and 0 elsewhere),

When \gcd(a,q)=1, the \varphi(q) admissible classes ought to share the total \psi(x) \approx x equally, so the expected value is x/\varphi(q). The quantity we want to be small is the discrepancy

The maximum over a is the pessimist's choice: for each modulus we look at the worst residue class. Bombieri–Vinogradov then bounds the sum of these worst cases across all moduli.

The statement

Read the right-hand side as "negligible": x/(\log x)^A is smaller than x by any power of \log you like. Now count what the left-hand side is asking. There are about Q \approx \sqrt{x} moduli. The "trivial" size of each term — with no cancellation, just \psi(x;q,a) \le \psi(x) \approx x — would be around x/\varphi(q), and summing that over q \le Q gives roughly x \log Q \approx x \log x. So the theorem beats the trivial bound by an arbitrarily large power of \log x — and it does so summing over the worst residue class of each of \sqrt{x} different moduli.

Unpacking "GRH on average"

Why is this exactly the strength GRH would give? If GRH held for the Dirichlet L-functions mod q, the individual discrepancy would satisfy

Summing that conditional bound over all q \le \sqrt{x} would give about \sqrt{x}\cdot\sqrt{x}\,(\log x)^2 = x(\log x)^2 — the same ballpark as the unconditional Bombieri–Vinogradov bound, up to the log powers. In other words, for a huge range of applications where you only ever needed to sum the error over many moduli, Bombieri–Vinogradov is a free, unconditional substitute for GRH. You lose nothing by not having the Riemann Hypothesis — provided you can live with an average.

The catch is precisely that "average". GRH would tame every single modulus; Bombieri–Vinogradov only promises the bad moduli are rare enough that their combined damage stays below the noise. For most purposes in sieve theory and additive number theory, that is all you ever needed.

Seeing the range of control

The whole story is a story about how large a modulus you may take. Siegel–Walfisz reaches only a pinprick near the origin; Bombieri–Vinogradov (paying the price of an average) surges all the way to the \sqrt{x} barrier; and the Elliott–Halberstam conjecture dreams of pushing past it, almost to x itself. The axis below is the modulus q on a logarithmic scale.

The number \theta that indexes "how large a Q you may take", written Q = x^{\theta}, is called the level of distribution. Bombieri–Vinogradov establishes level \theta = \tfrac12; Elliott–Halberstam conjectures any \theta < 1.

Worked example — Siegel–Walfisz vs. Bombieri–Vinogradov

Let us make the gulf concrete. Take x = 10^{12}, so \log x \approx 27.6, and use A = 3 to fix the quality of the error we demand.

Siegel–Walfisz. It gives the GRH-quality error \psi(x;q,a) - x/\varphi(q) \ll x/(\log x)^A, but only for q \le (\log x)^A. Here that ceiling is

So Siegel–Walfisz can vouch for moduli up to about twenty thousand — and not one modulus beyond.

Bombieri–Vinogradov. On average, it reaches Q = \sqrt{x}/(\log x)^{B}. With \sqrt{x} = 10^{6} and, say, B = 11,

The log-power denominator makes the crude arithmetic at a single finite x misleading — the honest comparison is asymptotic. As x \to \infty, \sqrt{x}/(\log x)^B grows like x^{1/2 - o(1)}, whereas (\log x)^A stays a power of a logarithm. The ratio of the two reachable ranges is

Siegel–Walfisz stays forever trapped inside a logarithmic neighbourhood of 1; Bombieri–Vinogradov opens up a full square-root-of-x of moduli. That is the difference between (\log x)^A and x^{1/2} — polynomially-in-log versus polynomially-in-x, an unboundedly widening gap. The price for the enormous extension is only that the guarantee is now about the sum over q, not each q alone.

How it is proved — the two engines

You do not need the proof to use the theorem, but it helps to know what makes \sqrt{x} the natural stopping point. Two ideas do the heavy lifting.

1. The large sieve inequality. The large sieve is an analytic inequality that controls, all at once, how a sequence can correlate with the additive characters e(na/q) across many moduli q \le Q and all reduced residues a. Applied to Dirichlet characters it yields a bound on averages of L-functions — a mean value theorem — that is exactly as strong as summing GRH would be, but requires no hypothesis. This is where the "on average" strength is born, and where the Q^2 \le x, i.e. Q \le \sqrt{x}, condition enters: the large sieve is efficient precisely up to that range.

2. Vaughan's identity (a bilinear decomposition). To feed \Lambda(n) into the large sieve you must first tear it apart. Vaughan's identity (and, historically, Vinogradov's dispersion method) rewrites the von Mangoldt sum as a combination of bilinear "Type I" and "Type II" sums \sum_m \sum_n a_m b_n(\cdots). Bilinear sums are exactly the shape the large sieve devours, and the identity is what converts a statement about primes into a statement about such sums. Together — decompose with Vaughan, then estimate with the large sieve — they deliver the theorem.

The level of distribution and Elliott–Halberstam

Package the reach as a single number. We say the primes have level of distribution \theta if, for every A,

In this language, Bombieri–Vinogradov is the statement that \theta = \tfrac12 is admissible. The Elliott–Halberstam conjecture (1968) is the bold claim that any \theta < 1 works:

The gap between the proven \theta = \tfrac12 and the conjectured \theta \to 1 is one of the great chasms in the subject. Every increment of \theta above \tfrac12 would be a landmark — and the payoff is dramatic, as the next card shows.

Where Bombieri–Vinogradov earns its keep

This theorem is not a curiosity — it is a workhorse. Because it substitutes for GRH in any argument that only needs an average over moduli, it unlocks results that would otherwise be conditional:

Chen's theorem (1973). Chen Jingrun proved that every sufficiently large even number is a sum of a prime and a number with at most two prime factors (a "prime plus an almost prime") — the closest anyone has come to the Goldbach conjecture. Bombieri–Vinogradov is a central input: the sieve that produces the almost-prime needs equidistribution of primes in progressions up to nearly \sqrt{x}, and that is exactly what BV supplies unconditionally.

Bounded gaps between primes (Zhang, 2013). Yitang Zhang's breakthrough — the first proof that there are infinitely many pairs of primes differing by a bounded amount — needed a level of distribution beyond \tfrac12. He could not prove full Elliott–Halberstam, but he proved a Bombieri–Vinogradov-type result that pushes past \sqrt{x} for the restricted class of smooth (friable) moduli — moduli with only small prime factors. That extra room above the barrier, available for smooth q, was the crucial ingredient the Goldston–Pintz–Yıldırım sieve had been waiting for.

And the payoff scales with \theta. Under the full Elliott–Halberstam conjecture, the GPY / Maynard–Tao machinery drives the gap all the way down: EH would give infinitely many primes differing by at most 12, and a suitable generalisation would even yield the twin primes' gap of 2. The distance from \theta = \tfrac12 to \theta = 1 is, quite literally, the distance from "bounded gaps" to "twin primes".