Elliott-Halberstam level-of-distribution exponent

Description of constant

Let $\Lambda$ denote the von Mangoldt function. For coprime positive integers $a,q$, define

$$\psi (x;q,a):=\sum _{n\le x,n\equiv a(\mathrm{mod}q)}\Lambda (n).$$

<a href="#Ked2007-def-psi">[Ked2007-def-psi]</a>

The Bombieri-Vinogradov theorem gives (for every fixed $A>0$) a bound of the form, where $\varphi (q)$ denotes Euler's totient function:

$$\sum _{q\le Q}\underset{(a,q)=1}{\max }\left|\psi (x;q,a)-\frac{x}{\varphi (q)}\right|{\ll }_{A}x(\log x{)}^{-A}\text{for }Q=x^{1/2}(\log x{)}^{-B(A)}.$$

<a href="#Ked2007-BV">[Ked2007-BV]</a>

For $\vartheta \in [0,1]$, call $\vartheta$ an admissible level of distribution if (for every fixed $A>0$) there is some $B=B(A,\vartheta )$ such that

$$\sum _{q\le Q}\underset{(a,q)=1}{\max }\left|\psi (x;q,a)-\frac{x}{\varphi (q)}\right|{\ll }_{A}x(\log x{)}^{-A}\text{for all }Q\le x^{\vartheta }(\log x{)}^{-B}.$$

The level-of-distribution optimization problem is to determine the largest admissible $\vartheta$.

We define

$$C_{66}:={\vartheta }_{\mathrm{EH}},$$

where ${\vartheta }_{\mathrm{EH}}$ is the supremum of admissible levels $\vartheta$. <a href="#Ked2007-BV">[Ked2007-BV]</a>

The Bombieri-Vinogradov theorem implies

$${\vartheta }_{\mathrm{EH}}\ge \frac{1}{2}.$$

<a href="#Ked2007-BV">[Ked2007-BV]</a>

The Elliott-Halberstam conjecture predicts the optimal value

$${\vartheta }_{\mathrm{EH}}=1.$$

<a href="#Ked2007-EH">[Ked2007-EH]</a>

The best established range currently is

$$\frac{1}{2}\le C_{66}\le 1.$$

Known upper bounds

Known lower bounds

Additional comments and links

• Conjectural endpoint. Elliott-Halberstam asks for the same type of estimate up to $Q=x^{1-ϵ}$ for each fixed $ϵ>0$. <a href="#Ked2007-EH">[Ked2007-EH]</a>

• Original conjecture source. The original paper reference is Elliott-Halberstam, A conjecture in prime number theory. <a href="#EH1970-original">[EH1970-original]</a>

• Classical background source. See also Vinogradov's density-hypothesis paper for Dirichlet $L$-series. <a href="#Vin1965">[Vin1965]</a>

• Status note. The same source remarks that this conjecture appears extremely hard. <a href="#Ked2007-hard">[Ked2007-hard]</a>

• Wikipedia page on the Elliott-Halberstam conjecture

References

• <a id="Ked2007"></a>[Ked2007] Kedlaya, Kiran S. 18.785 Analytic Number Theory (MIT): The Bombieri-Vinogradov theorem (statement). Course notes (2007). PDF: https://kskedlaya.org/18.785/bombieri.pdf. Publisher page: https://kskedlaya.org/18.785/. Google Scholar
• <a id="Ked2007-def-psi"></a>[Ked2007-def-psi] loc: bombieri.pdf p.1, section "1 Statement of the theorem" quote: "For $m,N$ coprime positive integers, put $\psi (x;N,m)={\sum }_{n\le x,n\equiv m(\mathrm{mod}N)}\Lambda (n)$."
• <a id="Ked2007-BV"></a>[Ked2007-BV] loc: bombieri.pdf p.1, Theorem 1 (Bombieri-Vinogradov) quote: "For any fixed $A>0$, there exist constants $c=c(A)$ and $B=B(A)$ such that ${\sum }_{N\le Q}{\max }_{m\in (\mathbb{Z}/N\mathbb{Z}{)}^{\ast }}\left|\psi (x;N,m)-\frac{x}{\varphi (N)}\right|\le cx(\log x{)}^{-A}$ for $Q=x^{1/2}(\log x{)}^{-B}$."
• <a id="Ked2007-EH"></a>[Ked2007-EH] loc: bombieri.pdf p.1, Conjecture 2 (Elliott-Halberstam) quote: "For any fixed $A>0$ and $ϵ>0$, there exists $c>0$ such that ${\sum }_{N\le Q}{\max }_{m\in (\mathbb{Z}/N\mathbb{Z}{)}^{\ast }}\left|\psi (x;N,m)-\frac{x}{\varphi (N)}\right|\le cx(\log x{)}^{-A}$ for $Q=x^{1-ϵ}$."
• <a id="Ked2007-hard"></a>[Ked2007-hard] loc: bombieri.pdf p.1, paragraph below Conjecture 2 quote: "This conjecture appears to be extremely hard; for instance, it is not known to follow from GRH."

• <a id="EH1970"></a>[EH1970] Elliott, P. D. T. A.; Halberstam, H. A conjecture in prime number theory. In Symposia Mathematica, Vol. IV (Teoria dei numeri, Roma 1968; Algebra, Roma 1969), 59-72 (1970). Publisher page: https://zbmath.org/?q=an%3A0238.10030. Google Scholar
• <a id="EH1970-original"></a>[EH1970-original] loc: zbMATH bibliographic entry Zbl 0238.10030 quote: "A conjecture in prime number theory. (English) Sympos. Math., Roma 4, Teoria numeri Dic. 1968, e Algebra, Marzo 1969, 59-72 (1970)."

• <a id="Bom1965"></a>[Bom1965] Bombieri, Enrico. On the large sieve. Mathematika 12 (1965), 201-225. DOI: https://doi.org/10.1112/S0025579300005313. Google Scholar

• <a id="Vin1965"></a>[Vin1965] Vinogradov, Askold Ivanovich. The density hypothesis for Dirichlet L-series. Izv. Akad. Nauk SSSR Ser. Mat. 29 (1965), no. 4, 903-934 (in Russian). MR: 0197414. Corrigendum: Izv. Akad. Nauk SSSR Ser. Mat. 30 (1966), 719-720 (in Russian). Google Scholar

What counts as progress

• A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
• A formal proof (Lean) of a known bound, or a precise error in a claimed one.
• New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.