Elliott–Halberstam conjecture

For $x\ge2$, integers $q\ge1$ and $a$, let $\pi(x;q,a)$ be the number of primes $p\le x$ with $p\equiv a\pmod q$. Let $\pi(x)$ be the number of primes $p\le x$, and let $\varphi$ be Euler's totient function. Define the maximal error

$$E(x;q)=\max_{\substack{a \bmod q\\ \gcd(a,q)=1}}\left|\pi(x;q,a)-\frac{\pi(x)}{\varphi(q)}\right| .$$

The primes have level of distribution $\theta$ if for every $A>0$

$$\sum_{q\le x^{\theta}}E(x;q)\ll_{\theta,A}\frac{x}{(\log x)^A}\qquad(x\ge2).$$

Conjecture (Elliott–Halberstam). The primes have level of distribution $\theta$ for every $\theta<1$. That is, for every fixed $\theta<1$ and every $A>0$ there is a constant $C(\theta,A)$ such that

$$\sum_{q\le x^{\theta}}\ \max_{\gcd(a,q)=1}\left|\pi(x;q,a)-\frac{\pi(x)}{\varphi(q)}\right|\le C(\theta,A)\,\frac{x}{(\log x)^A}\qquad\text{for all } x\ge2 .$$

The Bombieri–Vinogradov theorem proves this for every $\theta<1/2$. A solution must prove it for every $\theta<1$. The range cannot be extended to $\theta=1$, since the estimate fails for moduli up to $x/(\log x)^B$ (see below). [1, 2, 11]

Background

The prime number theorem for arithmetic progressions says that primes are equidistributed among the $\varphi(q)$ reduced residue classes modulo $q$ for each fixed $q$. For applications one needs this uniformly over many moduli. The generalized Riemann hypothesis gives each individual error as $O(x^{1/2}\log x)$, which yields level $\theta<1/2$ on average. Bombieri and A. I. Vinogradov proved this average result unconditionally in 1965 by means of the large sieve [2]. Elliott and Halberstam conjectured in 1968 that the average extends to all $\theta<1$ [1].

The conjecture has become a standard hypothesis in sieve theory. Goldston, Pintz and Yıldırım showed that any level $\theta>1/2$ implies bounded gaps between primes [5]. Many results on prime gaps, primes in tuples and almost-prime patterns are proved first under this conjecture and then unconditionally in weaker form. A generalized version replaces the indicator of primes by more general arithmetic functions, and gives stronger consequences [6].