Linnik’s constant

Description of constant

For integers $q\ge 2$ and $a$ with $\gcd(a,q)=1$, let $P(a,q)$ denote the least prime in the arithmetic progression $a \bmod q$. [Xyl2011-def-Paq]

Linnik’s theorem asserts that there exist constants $C,L>0$ such that

uniformly for all $q\ge 2$. [Xyl2011-def-Linnik]

We define

where $L_{\mathrm{Lin}}$ is the infimum of all exponents $L$ for which such a bound holds (with some constant $C$ independent of $a,q$). [Xyl2011-def-Linnik]

The previously recorded upper bound, due to Xylouris and reported in [MMT2024], is

[MMT2024-ub-5]

Naslund’s October 2026 computer-assisted preprint reports an improvement to $L_{\mathrm{Lin}}\le 3.99$ [Nas2026].

The bound $L_{\mathrm{Lin}}\le 2.4$ follows as a corollary of OpenAI’s $7/8$ quasi-Riemann hypothesis for Dirichlet $L$-functions [OAI2026], combined with classical zero-density estimates [IK2004].

A trivial lower bound is $L_{\mathrm{Lin}}\ge 1$, since for $a=1$ the first candidate prime is at least $q+1$.

Known upper bounds

Known lower bounds

Additional comments and links

• Terminology. Some sources call $L_{\mathrm{Lin}}$ “Linnik’s constant” and reserve “Linnik’s theorem” for the existence of some finite exponent $L$. [Xyl2011-def-Linnik]

• Methodological progress after classical zero-density proofs. A recent result gives a new $L$-function-free proof with bound $p\ll q^{350}$. [MMT2024-ub-350]

• Verification of the $3.99$ bound. [Nas2026] is a computer-assisted preprint that has not been refereed by a human. It has had multiple adversarial AI reviews, and [Pal2026] registers Lean proofs of the near-density lemma (assuming published analytic estimates) and certificate-checker soundness. The full Linnik bound is not formally verified. Reproduction instructions and reports are public. The paper attributes its research and writing to AI models under Naslund’s supervision.

• Historical progression list. A compiled table of earlier admissible values appears in Xylouris’s table of improvements. [Xyl2011-historical-table]

• Wikipedia page on Linnik’s theorem

References

• [XylDiss2011] Xylouris, Triantafyllos. Uber die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression. Bonner Mathematische Schriften 404, Universitat Bonn, Mathematisches Institut (2011). Dissertation for the degree of Doctor of Mathematics and Natural Sciences. Google Scholar

• [Xyl2011] Xylouris, Triantafyllos. On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet $L$-functions. Acta Arithmetica 150 (2011), no. 1, 65-91. DOI (as printed in paper): 10.4064/aa150-1-4. Google Scholar
  • [Xyl2011-def-Paq] loc: Acta Arithmetica (2011) p.65, Introduction, first sentence quote: “Let P (a, q) be the least prime in an arithmetic progression a (mod q) where a and q are coprime positive integers.”
  • [Xyl2011-def-Linnik] loc: Acta Arithmetica (2011) p.65, Introduction, paragraph 1 quote: “Linnik proved [12, 13] the impressive upper bound P (a, q) ≤ CqL with effectively computable constants C and L. We will refer to this last inequality as Linnik’s theorem.”
  • [Xyl2011-ub-5-18] loc: Acta Arithmetica (2011) p.66, Theorem 1.1 quote: “Theorem 1.1. We have P (a, q) ≤ Cq5.18 with an effectively computable constant C.”
  • [Xyl2011-historical-table] loc: Acta Arithmetica (2011) p.65, Table 1 “Admissible values for L” quote: “10000 1957 Pan [15], 5448 1958 Pan [16], 777 1965 Chen [1], 630 1971 Jutila [17, p. 370], 550 1970 Jutila [10], 168 1977 Chen [2], 80 1977 Jutila [11], 36 1977 Graham [6], 20 1981 Graham [7], 17 1979 Chen [3], 16 1986 Wang [18], 13.5 1989 Chen and Liu [4], 11.5 1991 Chen and Liu [5], 8 1991 Wang [19], 5.5 1992 Heath-Brown [8].”
• [MMT2024] Matomaki, Kaisa; Merikoski, Jori; Teravainen, Joni. Primes in arithmetic progressions and short intervals without $L$-functions. arXiv:2401.17570 (2024). arXiv PDF: https://arxiv.org/pdf/2401.17570.pdf. Publisher: https://arxiv.org/abs/2401.17570. Google Scholar
  • [MMT2024-ub-5] loc: arXiv PDF p.1, Introduction, subsection “1.1.1 Linnik’s theorem” quote: “The best known exponent here is $L=5$, due to Xylouris [18], refining the work of Heath-Brown [10].”
  • [MMT2024-ub-350] loc: arXiv abstract quote: “We apply it to obtain a new $L$-function free proof of Linnik’s problem of bounding the least prime $p$ such that $p\equiv a\pmod q$ (with the bound $p\ll q^{350}$) as well as a new $L$-function free proof that the interval $(x-x^{39/40}, x]$ contains primes for every large $x$.”

• [Nas2026] Naslund, Eric. Linnik’s constant is at most 3.99. Hexagon:2610.00018v1 (PDF), 2 October 2026, Theorem 1.1.

• [NasRepo2026] Naslund, Eric. Supporting code, certificates and partial Lean formalization. Repository at commit 0400629, October 2026.

• [Pal2026] Palomar registry, PALOMAR-2026-10-01-000020, version 1, registered 1 October 2026; source commit ecdbe3e.

• [OAI2026] OpenAI. The Quasi-Riemann Hypothesis: A Zero-Free Half-Plane $\Re(s)>7/8$. 30 September 2026, Theorem 1.1. Preprint and source; PDF at commit adc7f124.

• [IK2004] Iwaniec, Henryk; Kowalski, Emmanuel. Analytic Number Theory. American Mathematical Society Colloquium Publications 53 (2004), Theorem 10.4 (Grand Density Theorem). Chapter 10.

Contribution notes

Prepared with assistance from ChatGPT 5.2 Pro.

The October 2026 update was prepared with assistance from Claude Opus 5.5 and revised with OpenAI Codex.

← Back to the table of constants