Level B · Reproducible Number theory P-constant-65a-linnik-s-constant

Linnik's constant

For integers q≥ 2 and a with gcd(a,q)=1, let P(a,q) denote the least prime in the arithmetic progression a bmod q. <a href="#Xyl2011-def-Paq">[Xyl2011-def-Paq]</a> Linnik's theorem asserts that there exist constants C,L>0 such that P(a,q) ≤ C q^L (gcd(a,q)=1), uniformly for all q≥ 2.

Current state (tracked automatically)

Best known bounds for constant 65a: 1 ≤ C ≤ 2.4. Upper bound ([OAI2026], [IK2004], Deduced from the 7/8 quasi-Riemann hypothesis for Dirichlet L-functions ([OAI2026], Theorem 1.1) together with the classical 12/5 zero-density estimate ([IK2004), not yet independently verified; lower bound (Trivial: P(1,q)≥ q+1).
The best independently verified upper bound is 5 ([XylDiss2011], Attributed in modern literature to Xylouris's 2011 dissertation).

All tracked facts and sources

Fact	Value	Source
Best lower bound with an explicit value (constant 65a)	1 Trivial: P(1,q)≥ q+1.	Tao's optimization constants
Best upper bound with an explicit value (constant 65a)	2.4* [OAI2026], [IK2004] — Deduced from the 7/8 quasi-Riemann hypothesis for Dirichlet L-functions ([OAI2026], Theorem 1.1) together with the classical 12/5 zero-density estimate ([IK2004	Tao's optimization constants
Best upper bound with an explicit value, independently verified (constant 65a)	5 [XylDiss2011] — Attributed in modern literature to Xylouris's 2011 dissertation.	Tao's optimization constants

Read twice a day from public sources by deterministic collectors (no AI; the sentences above are filled-in templates): Tao's optimization constants (checked 2026-11-12). How it works.

From the catalogue. Imported from Terence Tao and contributors (optimizationproblems repository) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Try it with your chatbot Submit a claim Follow (RSS)

Cite

@misc{cairn-constant-65a-linnik-s-constant,
  title        = {Linnik's constant},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/constant-65a-linnik-s-constant}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-13}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Fconstant-65a-linnik-s-constant.json)](https://cairn-commons.com/problems/constant-65a-linnik-s-constant)

Claims: 0
Verified: 0
Disputed: 0
Refuted: 0
On the literature board: 0

Nobody has worked on this problem here yet

Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.

Get a task — one click
Your chatbot works on it — 5–10 minutes, in its own tab
Paste its answer here — check it and publish it under your name

What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.

or , ,

ChatGPT opens in a new tab and starts on the task right away; Claude opens with it filled in.

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

Description of constant

For integers $q \geq 2$ and $a$ with $g cd (a, q) = 1$ , let $P (a, q)$ denote the least prime in the arithmetic progression $a mod q$ . <a href="#Xyl2011-def-Paq">[Xyl2011-def-Paq]</a>

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

$P (a, q) \leq C q^{L} (g cd (a, q) = 1),$

uniformly for all $q \geq 2$ . <a href="#Xyl2011-def-Linnik">[Xyl2011-def-Linnik]</a>

We define

$C_{65} := L_{Lin},$

where $L_{Lin}$ is the infimum of all exponents $L$ for which such a bound holds (with some constant $C$ independent of $a, q$ ). <a href="#Xyl2011-def-Linnik">[Xyl2011-def-Linnik]</a>

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

$L_{Lin} \leq 5.$

Naslund's October 2026 computer-assisted preprint reports an improvement to $L_{Lin} \leq 3.99$ [[Nas2026](#Nas2026)].

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

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

Known upper bounds

Bound	Reference	Comments
$10000$	[[Xyl2011](#Xyl2011)]	Historical table entry (Pan 1957). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$5448$	[[Xyl2011](#Xyl2011)]	Historical table entry (Pan 1958). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$777$	[[Xyl2011](#Xyl2011)]	Historical table entry (Chen 1965). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$630$	[[Xyl2011](#Xyl2011)]	Historical table entry (Jutila 1971). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$550$	[[Xyl2011](#Xyl2011)]	Historical table entry (Jutila 1970). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$350$	[[MMT2024](#MMT2024)]	New $L$ -function-free proof of Linnik's problem (coarse exponent). <a href="#MMT2024-ub-350">[MMT2024-ub-350]</a>
$168$	[[Xyl2011](#Xyl2011)]	Historical table entry (Chen 1977). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$80$	[[Xyl2011](#Xyl2011)]	Historical table entry (Jutila 1977). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$36$	[[Xyl2011](#Xyl2011)]	Historical table entry (Graham 1977). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$20$	[[Xyl2011](#Xyl2011)]	Historical table entry (Graham 1981). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$17$	[[Xyl2011](#Xyl2011)]	Historical table entry (Chen 1979). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$16$	[[Xyl2011](#Xyl2011)]	Historical table entry (Wang 1986). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$13.5$	[[Xyl2011](#Xyl2011)]	Historical table entry (Chen-Liu 1989). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$11.5$	[[Xyl2011](#Xyl2011)]	Historical table entry (Chen-Liu 1991). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$8$	[[Xyl2011](#Xyl2011)]	Historical table entry (Wang 1991). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$5.5$	[[Xyl2011](#Xyl2011)]	Historical table entry (Heath-Brown 1992). <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>
$5.18$	[[Xyl2011](#Xyl2011)]	Published explicit effective exponent in Theorem 1.1. <a href="#Xyl2011-ub-5-18">[Xyl2011-ub-5-18]</a>
$5$	[[XylDiss2011](#XylDiss2011)]	Attributed in modern literature to Xylouris's 2011 dissertation. <a href="#MMT2024-ub-5">[MMT2024-ub-5]</a>
$2.4$ *	[[OAI2026](#OAI2026)], [[IK2004](#IK2004)]	Deduced from the $7/8$ quasi-Riemann hypothesis for Dirichlet $L$ -functions ([OAI2026], Theorem 1.1) together with the classical $12/5$ zero-density estimate ([IK2004], Theorem 10.4). The deduction is the contributing author’s, not the source’s: [OAI2026] does not state a Linnik bound, and the step combining it with the zero-density estimate has not been refereed or formalized. [OAI2026] is itself an unrefereed preprint.
$3.99$ *	[[Nas2026](#Nas2026)], [[NasRepo2026](#NasRepo2026)]	Naslund (2 October 2026), Theorem 1.1. Uses a weighted near-density estimate and exact LP certificates for 4,788 terminal cases on 4,196,879 threshold boxes. Certificates and verification code at commit `0400629`.

Known lower bounds

Bound	Reference	Comments
$1$		Trivial: $P (1, q) \geq q + 1$ .

Additional comments and links

Terminology. Some sources call $L_{Lin}$ "Linnik's constant" and reserve "Linnik's theorem" for the existence of some finite exponent $L$ . <a href="#Xyl2011-def-Linnik">[Xyl2011-def-Linnik]</a>

Methodological progress after classical zero-density proofs. A recent result gives a new $L$ -function-free proof with bound $p ≪ q^{350}$ . <a href="#MMT2024-ub-350">[MMT2024-ub-350]</a>

Verification of the $3.99$ bound. [[Nas2026](#Nas2026)] is a computer-assisted preprint that has not been refereed by a human. It has had multiple adversarial AI reviews, and [[Pal2026](#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. <a href="#Xyl2011-historical-table">[Xyl2011-historical-table]</a>

Wikipedia page on Linnik's theorem

References

<a id="XylDiss2011"></a>[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

<a id="Xyl2011"></a>[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
<a id="Xyl2011-def-Paq"></a>[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."
<a id="Xyl2011-def-Linnik"></a>[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."
<a id="Xyl2011-ub-5-18"></a>[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."
<a id="Xyl2011-historical-table"></a>[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]."

<a id="MMT2024"></a>[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
<a id="MMT2024-ub-5"></a>[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]."
<a id="MMT2024-ub-350"></a>[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 (mod q)$ (with the bound $p ≪ 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$ ."

<a id="Nas2026"></a>[Nas2026] Naslund, Eric. Linnik's constant is at most 3.99. Hexagon:2610.00018v1 (PDF), 2 October 2026, Theorem 1.1.

<a id="NasRepo2026"></a>[NasRepo2026] Naslund, Eric. Supporting code, certificates and partial Lean formalization. Repository at commit 0400629, October 2026.

<a id="Pal2026"></a>[Pal2026] Palomar registry, PALOMAR-2026-10-01-000020, version 1, registered 1 October 2026; source commit ecdbe3e.

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

<a id="IK2004"></a>[IK2004] Iwaniec, Henryk; Kowalski, Emmanuel. Analytic Number Theory. American Mathematical Society Colloquium Publications 53 (2004), Theorem 10.4 (Grand Density Theorem). Chapter 10.

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 87b4ebbd426f, Apache License 2.0; reformatted for this page. New records should also be reported there.