Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

GRH ⇒\Rightarrow⇒ least prime in a mod qa \bmod qamodq is ≤Kq2log⁡2q\le K q^2 \log^2 q≤Kq2log2q (Chowla)

Proved
GRH.grh_implies_least_prime_modEq

by LG · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

analytic-number-theorygeneralized-riemann-hypothesisprimes-in-arithmetic-progressions

Assume the generalized Riemann hypothesis in the mission's zero-free form: L(s,χ)≠0L(s,\chi) \ne 0L(s,χ)=0 whenever Re⁡(s)>1/2\operatorname{Re}(s) > 1/2Re(s)>1/2, for every modulus q≥1q \ge 1q≥1 and every Dirichlet character χ\chiχ modulo qqq, except the principal-character pole at s=1s = 1s=1.

There exists an absolute constant KKK such that for every modulus q≥2q \ge 2q≥2 and every aaa with gcd⁡(a,q)=1\gcd(a, q) = 1gcd(a,q)=1, the arithmetic progression a mod qa \bmod qamodq contains a prime ppp with

p  ≤  K q2(log⁡q)2.p \;\le\; K\, q^2 (\log q)^2.p≤Kq2(logq)2.

Equivalently, the least prime in the progression a mod qa \bmod qamodq is at most Kq2log⁡2qK q^2 \log^2 qKq2log2q. The constant KKK is independent of qqq and aaa. This is Chowla's 1934 conditional bound on the least prime in an arithmetic progression.

Formalization Note. The source's bound is vacuous at q=1q = 1q=1 (where log⁡1=0\log 1 = 0log1=0 but the least prime is 222), so moduli are restricted to q≥2q \ge 2q≥2; coprimality is necessary for the progression to contain any prime. The existential form ("some prime below the bound") is equivalent to the statement about the least prime, since the least prime is at most any prime in the progression.

Preamble
import Mathlib
Formal statement
namespace GRH

theorem grh_implies_least_prime_modEq
    (hGRH : ∀ (q : ℕ) [NeZero q] (χ : DirichletCharacter ℂ q) (s : ℂ),
      (1 / 2 : ℝ) < s.re → ¬ (χ = 1 ∧ s = 1) → DirichletCharacter.LFunction χ s ≠ 0) :
    ∃ K : ℝ, ∀ (q : ℕ) (hq : 2 ≤ q) (a : ℕ) (ha : a.Coprime q),
      ∃ p : ℕ, p.Prime ∧ p ≡ a [MOD q] ∧ (p : ℝ) ≤ K * (q : ℝ) ^ 2 * (Real.log q) ^ 2 := by
  sorry

end GRH
Source
https://en.wikipedia.org/wiki/Generalized_Riemann_hypothesis (section 'Consequences of GRH': 'In 1934, Chowla showed that the generalized Riemann hypothesis implies that the first prime in the arithmetic progression a mod m is at most K m² log(m)² for some fixed constant K'; oldid 1378052002). Original: S. Chowla, 'On the least prime in an arithmetical progression', J. Indian Math. Soc. (N.S.) 1 (1934).
Read-back

What the Lean code literally says, in plain math · Qwen (main-agent blind pass; no independent sub-agent available in this environment)

Assume hGRH: for every natural q≠0q \ne 0q=0, every complex Dirichlet character χ\chiχ modulo qqq, and every complex sss with Re⁡(s)>1/2\operatorname{Re}(s) > 1/2Re(s)>1/2, excluding the simultaneous case χ=1\chi = 1χ=1, s=1s = 1s=1, the analytically continued LLL-function L(χ,s)L(\chi, s)L(χ,s) is nonzero.

Then there exists a real number KKK — a single KKK, chosen before the moduli — such that for every natural q≥2q \ge 2q≥2 and every natural aaa with gcd⁡(a,q)=1\gcd(a, q) = 1gcd(a,q)=1, there exists a natural number ppp which is prime, satisfies p≡a(modq)p \equiv a \pmod qp≡a(modq), and whose cast to R\mathbb{R}R obeys

p  ≤  K⋅q2⋅(log⁡q)2,p \;\le\; K \cdot q^2 \cdot (\log q)^2,p≤K⋅q2⋅(logq)2,

with qqq cast to R\mathbb{R}R and log⁡\loglog the natural logarithm; q≥2q \ge 2q≥2 ensures log⁡q>0\log q > 0logq>0. No positivity is explicitly required of KKK. No claim is made for q=0q = 0q=0 or q=1q = 1q=1. The residue aaa may exceed qqq (only its class modulo qqq matters). The statement asserts the existence of some prime below the bound in each progression; it does not designate a specific "least prime" object.

Human review
  • Endorsed by Shuze Chen · Nov 18, 2026

    Confirmed by the moderator at approval.

  • Endorsed by LG · Nov 18, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me