Bombieri–Vinogradov theorem

Let ${\displaystyle x}$ and ${\displaystyle Q}$ be any two positive real numbers with

${\displaystyle x^{1/2}\log ^{-A}x\leq Q\leq x^{1/2}.}$

Then

${\displaystyle \sum _{q\leq Q}\max _{y<x}\max _{1\leq a\leq q \atop (a,q)=1}\left|\psi (y;q,a)-{y \over \varphi (q)}\right|=O\left(x^{1/2}Q(\log x)^{5}\right)\!.}$

Here ${\displaystyle \varphi (q)}$ is the Euler totient function, which is the number of summands for the modulus q, and

${\displaystyle \psi (x;q,a)=\sum _{n\leq x \atop n\equiv a{\bmod {q}}}\Lambda (n),}$

where ${\displaystyle \Lambda }$ denotes the von Mangoldt function.

A verbal description of this result is that it addresses the error term in the prime number theorem for arithmetic progressions, averaged over the moduli q up to Q. For a certain range of Q, which are around ${\displaystyle {\sqrt {x}}}$ if we neglect logarithmic factors, the error averaged is nearly as small as ${\displaystyle {\sqrt {x}}}$. This is not obvious, and without the averaging is about of the strength of the Generalized Riemann Hypothesis (GRH).

• Elliott–Halberstam conjecture (a generalization of Bombieri–Vinogradov)
• Vinogradov's theorem (named after Ivan Matveyevich Vinogradov)

• Weisstein, Eric W. "Bombieri's Theorem". MathWorld.
• The Bombieri-Vinogradov Theorem, R.C. Vaughan's Lecture note.