In number theory, the Elliott-Halberstam conjecture is a conjecture about the distribution of prime numbers in arithmetic progressions. It has many applications in sieve theory. It is named for Peter T. D. A. Elliott and Heini Halberstam.

To state the conjecture requires some notation. Let $\backslash pi(x)$ denote the number of primes less than or equal to x. If q is a positive integer and a is coprime to q, we let

$\backslash pi(x;q,a)$

denote the number of primes less than or equal to x which are equal to a modulo q. Dirichlet's theorem on primes in arithmetic progressions then tells us that

$\backslash pi(x;q,a)\; \backslash approx\; \backslash frac\{\backslash pi(x)\}\{\backslash phi(q)\}$

when a is coprime to q. If we then define the error function

$E(x;q)\; =\; \backslash max\_\{(a,q)\; =\; 1\}\; \backslash left|\backslash pi(x;q,a)\; -\; \backslash frac\{\backslash pi(x)\}\{\backslash phi(q)\}\backslash right|$

where the max is taken over all a coprime to q, then the Elliott-Halberstam conjecture is the assertion that for every and $A\; >\; 0$ there exists a constant $C\; >\; 0$ such that

$\backslash sum\_\{1\; \backslash leq\; q\; \backslash leq\; x^\backslash theta\}\; E(x;q)\; \backslash leq\; C\; x\; /\; \backslash log^A\; x$

for all

$x\; >\; 2$.

This conjecture was proven for all

by Bombieri and A. I. Vinogradov (the Bombieri-Vinogradov theorem, sometimes known simply as Bombieri's theorem); this result is already quite useful, being an averaged form of the generalized Riemann hypothesis. It is known that the conjecture fails at the endpoint

$\backslash theta\; =\; 1$.

The Elliott-Halberstam conjecture has several consequences. One striking one is the recent result of Dan Goldston, Pintz, and Cem Yildirim ^* (see also [http://www.arxiv.org/abs/math.NT/0506067), which shows (assuming this conjecture) that there are infinitely many pairs of primes which differ by at most 16.

See also

---

• Barban-Davenport-Halberstam theorem
• Barban-Montgomery theorem

References

---

1. E. Bombieri, On the large sieve, Mathematika 12 (1965), 201-225
2. P.D.T.A. Elliot and H. Halberstam, A conjecture in prime number theory, Symp. Math. 4 (1968-1969), 59-72.
3. A.I. Vinogradov, The density hypothesis for Dirichlet L-series (in Russian), Izv. Akad. Nauk SSSR Ser. Mat. 29 (1965), 903-934.

Analytic number theoryConjectures