OpenFrontiers
Join
← Back to the index
OP-12081OpenNumber theory

Elliott-Halberstam level-of-distribution exponent (C66C_{66})

Elliott-Halberstam level-of-distribution exponent: determine C66C_{66} or improve its bounds; the repository records 12\frac{1}{2} (lower) and 1 (upper).

MSC 11N13 · Primes in congruence classes

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

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

ψ(x;q,a) := ∑n≤x, n≡a (mod q)Λ(n).\psi(x;q,a)\ :=\ \sum_{n\le x,\ n\equiv a\ (\mathrm{mod}\ q)} \Lambda(n).

[Ked2007-def-psi]

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

∑q≤Qmax⁡(a,q)=1∣ψ(x;q,a)−xϕ(q)∣ ≪A x(log⁡x)−Afor Q=x1/2(log⁡x)−B(A).\sum_{q\le Q}\max_{(a,q)=1}\left\lvert\psi(x;q,a)-\frac{x}{\phi(q)}\right\rvert \ \ll_A\ x(\log x)^{-A} \qquad \text{for }Q=x^{1/2}(\log x)^{-B(A)}.

[Ked2007-BV]

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

∑q≤Qmax⁡(a,q)=1∣ψ(x;q,a)−xϕ(q)∣ ≪A x(log⁡x)−Afor all Q≤xϑ(log⁡x)−B.\sum_{q\le Q}\max_{(a,q)=1}\left\lvert\psi(x;q,a)-\frac{x}{\phi(q)}\right\rvert \ \ll_A\ x(\log x)^{-A} \qquad \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

C66 := ϑEH,C_{66}\ :=\ \vartheta_{\mathrm{EH}},

where ϑEH\vartheta_{\mathrm{EH}} is the supremum of admissible levels ϑ\vartheta. [Ked2007-BV]

The Bombieri-Vinogradov theorem implies

ϑEH ≥ 12.\vartheta_{\mathrm{EH}}\ \ge\ \frac{1}{2}.

[Ked2007-BV]

The Elliott-Halberstam conjecture predicts the optimal value

ϑEH = 1.\vartheta_{\mathrm{EH}}\ =\ 1.

[Ked2007-EH]

The best established range currently is

12 ≤ C66 ≤ 1.\frac12\ \le\ C_{66}\ \le\ 1.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

  • Conjectural endpoint. Elliott-Halberstam asks for the same type of estimate up to Q=x1−ϵQ=x^{1-\epsilon} for each fixed ϵ>0\epsilon>0. [Ked2007-EH]

  • Original conjecture source. The original paper reference is Elliott-Halberstam, A conjecture in prime number theory. [EH1970-original]

  • Classical background source. See also Vinogradov's density-hypothesis paper for Dirichlet LL-series. [Vin1965]

  • Status note. The same source remarks that this conjecture appears extremely hard. [Ked2007-hard]

  • Wikipedia page on the Elliott-Halberstam conjecture

References (from the repository page)

  • [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

  • [Ked2007-def-psi] loc: bombieri.pdf p.1, section "1 Statement of the theorem" quote: "For m,Nm, N coprime positive integers, put ψ(x;N,m)=∑n≤x, n≡m (mod N)Λ(n)\psi(x; N, m)=\sum_{n\le x,\ n\equiv m\ (\mathrm{mod}\ N)} \Lambda(n)."

  • [Ked2007-BV] loc: bombieri.pdf p.1, Theorem 1 (Bombieri-Vinogradov) quote: "For any fixed A>0A>0, there exist constants c=c(A)c=c(A) and B=B(A)B=B(A) such that ∑N≤Qmax⁡m∈(Z/NZ)∗∣ψ(x;N,m)−xϕ(N)∣≤cx(log⁡x)−A\sum_{N\le Q}\max_{m\in (\mathbb{Z}/N\mathbb{Z})^\ast}\left\lvert\psi(x;N,m)-\frac{x}{\phi(N)}\right\rvert \le c x(\log x)^{-A} for Q=x1/2(log⁡x)−BQ=x^{1/2}(\log x)^{-B}."

  • [Ked2007-EH] loc: bombieri.pdf p.1, Conjecture 2 (Elliott-Halberstam) quote: "For any fixed A>0A>0 and ϵ>0\epsilon>0, there exists c>0c>0 such that ∑N≤Qmax⁡m∈(Z/NZ)∗∣ψ(x;N,m)−xϕ(N)∣≤cx(log⁡x)−A\sum_{N\le Q}\max_{m\in(\mathbb{Z}/N\mathbb{Z})^\ast}\left\lvert\psi(x;N,m)-\frac{x}{\phi(N)}\right\rvert \le c x(\log x)^{-A} for Q=x1−ϵQ=x^{1-\epsilon}."

  • [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."

  • [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

  • [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)."

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

  • [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

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 12\frac{1}{2}; best known upper bound 1. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
11 Trivial ceiling in the standard level-of-distribution formulation.

Known lower bounds

Bound Reference Comments
1/21/2 [Ked2007] Bombieri-Vinogradov range Q=x1/2(log⁡x)−BQ=x^{1/2}(\log x)^{-B}. [Ked2007-BV]
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Elliott-Halberstam level-of-distribution exponent ($C_{66}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.