Open problem, Arithmetic and number theory, Analysis, posed 1968

Elliott–Halberstam conjecture

Open

For every $\theta < 1$ and every $A > 0$ , the error term $E(x; q) = \max_{\gcd(a,q)=1} \left| \pi(x; q, a) - \frac{\pi(x)}{\varphi(q)} \right|$ in the prime number theorem for arithmetic progressions satisfies $\sum_{1 \le q \le x^{\theta}} E(x; q) \ll_{\theta, A} \frac{x}{(\log x)^A}$ for all $x > 2$ .

Research frontier as of 2026

As of 2026, the full Elliott–Halberstam conjecture (which takes a maximum over all coprime residue classes $a \pmod{q}$ for each modulus $q$ ) is still open for every $\theta > 1/2$ ; the unconditional benchmark for the full maximum remains the Bombieri–Vinogradov theorem ( $\theta = 1/2$ ). However, when the residue class $a$ is fixed (or weighted smoothly) rather than maximized over, dramatic progress has pushed the level of distribution well past $1/2$ : after Bombieri–Friedlander–Iwaniec (1986), Zhang (2013), and Polymath8a (2014, reaching $\theta = 1/2 + 7/300$ for smooth moduli), Maynard (2020) and Pascadi, Stadlmann, Lichtman, and others have pushed the exponent for fixed-residue or smooth-weight variants past $3/5$ .

Best known results

For the full maximum over $\gcd(a,q)=1$ , the conjecture holds unconditionally for all $\theta < 1/2$ (Bombieri–Vinogradov theorem, 1965).
For a fixed residue class $a \ne 0$ and smooth or well-factorable weights over $q$ , the level of distribution exceeds $1/2$ unconditionally (Bombieri–Friedlander–Iwaniec 1986; Zhang 2013; Polymath8a 2014; Maynard 2020).
Assuming the Elliott–Halberstam conjecture, $\liminf_{n\to\infty} (p_{n+1}-p_n) \le 12$ (Maynard, 2013); assuming the generalized Elliott–Halberstam conjecture, $\liminf_{n\to\infty} (p_{n+1}-p_n) \le 6$ (Polymath8b, 2014).

Tools and where they stop

Tool	Achieved	Where it stops
Large sieve inequality and Vaughan's identity	Decomposes the prime indicator into Type I and Type II bilinear sums and bounds their average over primitive Dirichlet characters, proving the Bombieri–Vinogradov theorem ( $\theta < 1/2$ ).	Because the large sieve bounds $L^2$ norms of character sums without exploiting cancellation between different residue classes $a_q$ , it hits a hard square-root barrier at $\theta = 1/2$ .
Dispersion method and Kloosterman sum bounds (Deligne, Deshouillers–Iwaniec)	Applies Poisson summation and Weil/Deligne algebraic-geometry bounds or spectral theory of automorphic forms to push the level of distribution beyond $\theta = 1/2$ when $a$ is fixed.	Fails when the residue class $a_q$ varies arbitrarily with $q$ , because taking the maximum $\max_{\gcd(a,q)=1}$ destroys the smooth dependence on $q$ needed for Poisson summation.

Open questions

Does there exist any $\theta > 1/2$ for which the full Elliott–Halberstam bound (with $\max_{\gcd(a,q)=1}$ inside the sum) holds unconditionally?
For a fixed residue class $a \ne 0$ , can the level of distribution of primes be proved unconditionally for all $\theta < 1$ ?

References

Enrico Bombieri (1965). On the large sieve and its applications · DOI:10.1112/S0025579300005313
Peter D. T. A. Elliott, Heini Halberstam (1970). A conjecture in prime number theory
Enrico Bombieri, John B. Friedlander, Henryk Iwaniec (1986). Primes in arithmetic progressions to large moduli · DOI:10.1007/BF02392590
John B. Friedlander, Andrew Granville (1989). Limitations to the equi-distribution of primes I · DOI:10.2307/1971450