Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Prime counting in arithmetic progressions π(x;q,a)\pi(x; q, a)π(x;q,a)

Definition
GRH_Defs

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

analytic-number-theoryprime-number-theoremprimes-in-arithmetic-progressions

Let qqq and aaa be natural numbers and xxx a real number. The prime-counting function of the arithmetic progression a mod qa \bmod qamodq is

π(x; q,a)  =  #{ p≤x  :  p prime and p≡a(modq) }.\pi(x;\, q, a) \;=\; \#\{\, p \le x \;:\; p \text{ prime and } p \equiv a \pmod q \,\}.π(x;q,a)=#{p≤x:p prime and p≡a(modq)}.

For q=1q = 1q=1 this is the usual prime-counting function π(x)\pi(x)π(x); for general qqq it counts the primes up to xxx in the residue class aaa, and is the counting function appearing in the GRH-conditional prime number theorem for arithmetic progressions.

Formalization Note. The definition imposes no coprimality or positivity conditions: it is a finite filter over p<⌊x⌋+1p < \lfloor x \rfloor + 1p<⌊x⌋+1. For x<0x < 0x<0 the value is 000; for q=0q = 0q=0 the congruence means p=ap = ap=a. Coprimality gcd⁡(a,q)=1\gcd(a,q)=1gcd(a,q)=1 and q≥1q \ge 1q≥1 enter the theorem statements that use it, not the definition.

Definition code
import Mathlib

set_option autoImplicit false

namespace GRH

/-- `primeCountingAP q a x` is `π(x; q, a)`: the number of primes `p ≤ x` lying in the
residue class `a mod q`. For `x < 0` the value is `0`. -/
noncomputable def primeCountingAP (q a : ℕ) (x : ℝ) : ℕ :=
  (Finset.filter (fun p => p.Prime ∧ p ≡ a [MOD q]) (Finset.range (⌊x⌋₊ + 1))).card

end GRH
Source
https://en.wikipedia.org/wiki/Generalized_Riemann_hypothesis (section 'Consequences of GRH', item on the effective Dirichlet theorem, defining $\pi(x,a,d)$ as the number of primes $\le x$ in the progression $n d + a$; oldid 1378052002).
Read-back

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

For natural numbers q,aq, aq,a and a real number xxx, primeCountingAP q a x is the cardinality of the finite set of natural numbers ppp with p<⌊x⌋+1p < \lfloor x \rfloor + 1p<⌊x⌋+1 — equivalently p≤xp \le xp≤x when x≥0x \ge 0x≥0 — such that ppp is prime and p≡a(modq)p \equiv a \pmod qp≡a(modq), i.e. p mod q=a mod qp \bmod q = a \bmod qpmodq=amodq.

No coprimality condition on (a,q)(a, q)(a,q) and no positivity condition on qqq are imposed. Degenerate inputs: for q=0q = 0q=0, the congruence p≡a(mod0)p \equiv a \pmod 0p≡a(mod0) means p=ap = ap=a, so the value is 111 if aaa is prime and a≤xa \le xa≤x, and 000 otherwise; for q=1q = 1q=1 every ppp satisfies the congruence, so the value is the usual prime count π(x)\pi(x)π(x). For x<0x < 0x<0, the natural-number floor ⌊x⌋\lfloor x \rfloor⌊x⌋ is 000, the range is {0}\{0\}{0}, and the value is 000 since 000 is not prime. The output is a natural number.

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