Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Chowla's least prime ≤Kq2log⁡2q\le K q^2\log^2 q≤Kq2log2q from a one-logarithm Chebyshev bound

Proved
GRH.least_prime_modEq_of_thetaAP_square_root_log

by mwm · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

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

Derive Chowla's 1934 conditional bound on the least prime in an arithmetic progression from a uniform one-logarithm Chebyshev lower bound.

Input: an absolute constant C≥0C\ge0C≥0 with

θ(x;q,a)  ≥  xφ(q)−Cxlog⁡x\theta(x;q,a)\;\ge\;\frac{x}{\varphi(q)}-C\sqrt{x}\log xθ(x;q,a)≥φ(q)x​−Cx​logx

for all moduli q≥1q\ge1q≥1, all aaa coprime to qqq, and all real x≥2x\ge2x≥2 (child GRH.grh_implies_thetaAP_square_root_log).

Output: an absolute constant K≥0K\ge0K≥0 such that for every q≥2q\ge2q≥2 and every aaa with gcd⁡(a,q)=1\gcd(a,q)=1gcd(a,q)=1 some prime p≤Kq2(log⁡q)2p\le K q^2(\log q)^2p≤Kq2(logq)2 satisfies p≡a(modq)p\equiv a\pmod qp≡a(modq).

The proof balances at x=Kq2(log⁡q)2x=K q^2(\log q)^2x=Kq2(logq)2: the main term x/φ(q)≥Kq(log⁡q)2x/\varphi(q)\ge K q(\log q)^2x/φ(q)≥Kq(logq)2 dominates the error Cxlog⁡xC\sqrt{x}\log xCx​logx once K\sqrt KK​ exceeds a fixed multiple of CCC (the sum is over primes only, so no prime-power noise enters); the prime sum then exceeds zero and produces the required prime. The concrete choice K=(64(C+1)(C+2)2)2K=(64(C+1)(C+2)^2)^2K=(64(C+1)(C+2)2)2 verifies uniformly for all q≥2q\ge2q≥2 and all C≥0C\ge0C≥0.

Preamble
import Mathlib
Formal statement
namespace GRH

/-- **Chowla's least-prime bound from a sharp Chebyshev lower bound (bridge).**
Given an absolute constant C ≥ 0 with the uniform one-logarithm Chebyshev lower bound

    θ(x; q, a) ≥ x / φ(q) - C * sqrt x * log x

for all moduli q ≥ 1, all a coprime to q, and all real x ≥ 2, there is an absolute constant
K ≥ 0 such that for every q ≥ 2 and every a coprime to q some prime p ≤ K * q^2 * (log q)^2
satisfies p ≡ a [MOD q].

The proof balances at x = K * q^2 * (log q)^2: the main term x / φ(q) ≥ K * q * (log q)^2
dominates the error C * sqrt x * log x once sqrt K exceeds a fixed multiple of C, so the prime
sum exceeds zero and yields the desired prime; the sum is over primes only, so no prime-power
noise enters. The concrete choice K = (64 * (C + 1) * (C + 2)^2)^2 makes the logarithmic
arithmetic work uniformly for q ≥ 2. -/
theorem least_prime_modEq_of_thetaAP_square_root_log
    (C : ℝ) (hC : 0 ≤ C)
    (hθ : ∀ (q a : ℕ), q ≠ 0 → a.Coprime q → ∀ x : ℝ, 2 ≤ x →
        x / (q.totient : ℝ) - C * Real.sqrt x * Real.log x ≤
          ∑ n ∈ (Finset.Ioc 0 ⌊x⌋₊).filter (fun n => n ≡ a [MOD q] ∧ n.Prime),
            Real.log (n : ℝ)) :
    ∃ K : ℝ, 0 ≤ K ∧
      ∀ (q : ℕ), 2 ≤ q → ∀ (a : ℕ), 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). Step 2 (bridge) of the reduction of GRH.grh_implies_least_prime_modEq.

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