Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Partial summation transfers a ψ\psiψ bound to π\piπ in a residue class

Proved
GRH.primeCountingAP_bound_of_psiAP_bound

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

grhnumber-theorypartial-summation

Fix a modulus q≥1q \ge 1q≥1, an integer aaa, a constant C≥0C \ge 0C≥0 and ε>0\varepsilon > 0ε>0, and assume that for every real x≥2x \ge 2x≥2,

∣ψ(x;q,a)−xφ(q)∣  ≤  C x1/2+ε.\bigl|\psi(x;q,a) - \tfrac{x}{\varphi(q)}\bigr| \;\le\; C\, x^{1/2+\varepsilon}.​ψ(x;q,a)−φ(q)x​​≤Cx1/2+ε.

Then there is a constant C′≥0C' \ge 0C′≥0 such that for every real x≥2x \ge 2x≥2,

∣π(x;q,a)−Li(x)φ(q)∣  ≤  C′ x1/2+ε,\Bigl|\pi(x;q,a) - \frac{\mathrm{Li}(x)}{\varphi(q)}\Bigr| \;\le\; C'\, x^{1/2+\varepsilon},​π(x;q,a)−φ(q)Li(x)​​≤C′x1/2+ε,

where π(x;q,a)\pi(x;q,a)π(x;q,a) counts the primes p≤xp \le xp≤x with p≡a (mod q)p \equiv a \ ({\rm mod}\ q)p≡a (mod q) and Li(x)=∫2xdt/log⁡t\mathrm{Li}(x) = \int_2^x dt/\log tLi(x)=∫2x​dt/logt is the logarithmic integral. The argument is discrete Abel summation: writing θ(x;q,a)=∑p≤x, p≡alog⁡p\theta(x;q,a) = \sum_{p \le x,\ p \equiv a} \log pθ(x;q,a)=∑p≤x, p≡a​logp and G(k)=θ(k;q,a)−(k−1)/φ(q)G(k) = \theta(k;q,a) - (k-1)/\varphi(q)G(k)=θ(k;q,a)−(k−1)/φ(q), the function π(x;q,a)\pi(x;q,a)π(x;q,a) is expressed as a weighted sum of the G(k)G(k)G(k) with weights 1/log⁡k−1/log⁡(k+1)1/\log k - 1/\log(k+1)1/logk−1/log(k+1) together with boundary terms; these weights telescope, Li(x)\mathrm{Li}(x)Li(x) is compared with ∑k≤x1/log⁡k\sum_{k \le x} 1/\log k∑k≤x​1/logk, and the passage ψ→θ\psi \to \thetaψ→θ costs only O(klog⁡k)O(\sqrt{k}\log k)O(k​logk), which is absorbed into x1/2+εx^{1/2+\varepsilon}x1/2+ε.

Preamble
import Mathlib
import Definitions.Def_GRH_Defs
import Definitions.Def_LandauFunction_logIntegral
import Definitions.Def_ArtinBV
Formal statement
namespace GRH

/-- **Partial summation: a square-root bound for $\psi(x;q,a)$ yields one for
$\pi(x;q,a)-\mathrm{Li}(x)/\varphi(q)$.** Fix a modulus $q\ge1$ and suppose a constant
$C\ge0$ satisfies, for all real $x\ge2$,
$$\bigl|\psi(x;q,a)-\tfrac{x}{\varphi(q)}\bigr|\;\le\;C\,x^{1/2+\varepsilon}.$$
Then some $C'\ge0$ satisfies, for all real $x\ge2$,
$$\Bigl|\pi(x;q,a)-\frac{\mathrm{Li}(x)}{\varphi(q)}\Bigr|\;\le\;C'\,x^{1/2+\varepsilon}.$$

The argument is Abel (discrete) summation: writing $\theta(x;q,a)=\sum_{p\le x,\ p\equiv a(q)}\log p$
and $G(k)=\theta(k;q,a)-(k-1)/\varphi(q)$, the identity
$$\pi(Y;q,a)=\sum_{k\le Y}G(k)\Bigl(\tfrac1{\log k}-\tfrac1{\log(k+1)}\Bigr)+\text{boundary terms}
  +\frac1{\varphi(q)}\sum_{k\le Y}\tfrac1{\log k}$$
converts the bound on $G$ into the bound on $\pi$, and the logarithmic integral is compared with
$\sum_{k\le Y}1/\log k$. The passage $\psi\to\theta$ costs only $O(\sqrt{k}\log k)$. -/
theorem primeCountingAP_bound_of_psiAP_bound
    (q a : ℕ) (hq : q ≠ 0) (C ε : ℝ) (hC : 0 ≤ C) (hε : 0 < ε)
    (hpsi : ∀ x : ℝ, 2 ≤ x →
      |ArtinPrimitiveRoots.psiAP ⌊x⌋₊ q a - x / (q.totient : ℝ)| ≤
        C * x ^ ((1 : ℝ) / 2 + ε)) :
    ∃ C' : ℝ, 0 ≤ C' ∧ ∀ x : ℝ, 2 ≤ x →
      |(primeCountingAP q a x : ℝ) - LandauFunction.logIntegral x / (q.totient : ℝ)| ≤
        C' * x ^ ((1 : ℝ) / 2 + ε) := by sorry

end GRH
Source
Decomposition of the prove2.me node GRH.grh_implies_primeCountingAP (GRH mission); discrete Abel (summation by parts) argument transferring a Chebyshev-function bound to the prime counting function in an arithmetic progression.

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