Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

The Siegel–Walfisz theorem, character form (Davenport §22) — the platform proposition `ThreePrimes.SiegelWalfisz`

Proved
Davenport.siegel_walfisz_char

by alya · Sep 3, 2026 · Mathlib c5ea003 (Lean v4.30.0)

analytic-number-theorydirichlet-l-functionnumber-theorysiegel-walfiszthree-primes

The Siegel–Walfisz theorem, character form (Davenport §22). For every A>0A>0A>0 there are constants CCC and c>0c>0c>0 such that for every modulus q≥1q\ge1q≥1, every Dirichlet character χ\chiχ modulo qqq, and every N≥2N\ge2N≥2 with q≤(log⁡N)Aq\le(\log N)^Aq≤(logN)A,

∥ψ(N,χ)−δχN∥  ≤  C Nexp⁡(−clog⁡N),ψ(N,χ)=∑n<NΛ(n)χ(n),\bigl\|\psi(N,\chi)-\delta_\chi N\bigr\|\;\le\;C\,N\exp\bigl(-c\sqrt{\log N}\bigr),\qquad \psi(N,\chi)=\sum_{n<N}\Lambda(n)\chi(n),​ψ(N,χ)−δχ​N​≤CNexp(−clogN​),ψ(N,χ)=n<N∑​Λ(n)χ(n),

where δχ=1\delta_\chi=1δχ​=1 if χ\chiχ is the principal character and δχ=0\delta_\chi=0δχ​=0 otherwise. In Davenport's notation: for any fixed A>0A>0A>0, ψ(x,χ)≪Axexp⁡(−CA(log⁡x)1/2)\psi(x,\chi)\ll_A x\exp(-C_A(\log x)^{1/2})ψ(x,χ)≪A​xexp(−CA​(logx)1/2) uniformly for χ≠χ0\chi\neq\chi_0χ=χ0​ and q≤(log⁡x)Aq\le(\log x)^Aq≤(logx)A, together with ψ(x,χ0)=x+O(xexp⁡(−c(log⁡x)1/2))\psi(x,\chi_0)=x+O(x\exp(-c(\log x)^{1/2}))ψ(x,χ0​)=x+O(xexp(−c(logx)1/2)) in the same range. The constants are ineffective, because Siegel's theorem is.

The statement of this theorem is literally the platform proposition ThreePrimes.SiegelWalfisz (definition file Vino_threeprimes), which the conditional three primes theorem ThreePrimes.three_primes takes as its hypothesis. Proving it therefore makes Vinogradov's theorem unconditional on the platform.

Preamble
import Definitions.Def_Vino_threeprimes
import Definitions.Def_Davenport_siegelWalfisz
import Mathlib.NumberTheory.LSeries.DirichletContinuation
import Mathlib.NumberTheory.DirichletCharacter.Basic
import Mathlib.NumberTheory.ArithmeticFunction.VonMangoldt
import Mathlib.NumberTheory.Chebyshev
import Mathlib.Analysis.SpecialFunctions.Pow.Real
import Mathlib.Analysis.SpecialFunctions.Pow.Complex
import Mathlib.Analysis.SpecialFunctions.Log.Basic
import Mathlib.Analysis.SpecialFunctions.Exp
import Mathlib.Analysis.SpecialFunctions.Sqrt
import Mathlib.Algebra.BigOperators.Finprod
import Mathlib.Data.Nat.Totient

open Finset DirichletCharacter Vino
Formal statement
namespace Davenport

theorem siegel_walfisz_char : ThreePrimes.SiegelWalfisz := by sorry

end Davenport
Source
H. Davenport, Multiplicative Number Theory, 3rd ed. (revised by H. L. Montgomery), GTM 74, Springer, 2000, https://doi.org/10.1007/978-1-4757-5927-3; §22 (The prime number theorem for arithmetic progressions (II)), pp. 132–134: ψ(x,χ) ≪ x exp(−C_N (log x)^{1/2}) for χ ≠ χ₀ mod q ≤ (log x)^N, and the principal-character case from §18/§20; statement identical to ThreePrimes.SiegelWalfisz (platform definition Vino_threeprimes)
Read-back

What the Lean code literally says, in plain math · claude-opus-4-8

Read-back: Davenport.siegel_walfisz_char

What the declaration is. Davenport.siegel_walfisz_char is a closed theorem — it takes no arguments, no variables, and no typeclass assumptions. Its statement is exactly the proposition ThreePrimes.SiegelWalfisz, which is a single Prop with no parameters. Unfolding that proposition, and unfolding Vino.vmSumChar inside it, the theorem asserts the following.

The character sum. For a natural number qqq, a Dirichlet character χ\chiχ modulo qqq with values in C\mathbb{C}C (i.e. a multiplicative character on the ring Z/qZ\mathbb{Z}/q\mathbb{Z}Z/qZ into C\mathbb{C}C), and a natural number NNN, write

S(q,χ,N)  =  ∑n=0N−1Λ(n) χ(n mod q)  ∈  C,S(q,\chi,N) \;=\; \sum_{n=0}^{N-1} \Lambda(n)\,\chi(n \bmod q) \;\in\; \mathbb{C},S(q,χ,N)=n=0∑N−1​Λ(n)χ(nmodq)∈C,

where Λ\LambdaΛ is the von Mangoldt function (regarded as a real number and then coerced into C\mathbb{C}C), and n mod qn \bmod qnmodq is the image of nnn in Z/qZ\mathbb{Z}/q\mathbb{Z}Z/qZ. Two features of this sum are literal and worth stating: the index set is {0,1,…,N−1}\{0,1,\dots,N-1\}{0,1,…,N−1}, so the summation runs over nnn strictly below NNN and includes n=0n=0n=0 (with Λ(0)=0\Lambda(0)=0Λ(0)=0 and Λ(1)=0\Lambda(1)=0Λ(1)=0, so those terms vanish); and χ\chiχ is a multiplicative character on Z/qZ\mathbb{Z}/q\mathbb{Z}Z/qZ, so χ\chiχ takes the value 000 at every non-unit residue, meaning the sum is effectively over those n<Nn < Nn<N with gcd⁡(n,q)=1\gcd(n,q)=1gcd(n,q)=1.

The assertion. The theorem states:

For every real number AAA with 0<A0 < A0<A, there exist real numbers CCC and ccc such that 0<c0 < c0<c and, for every natural number qqq with 1≤q1 \le q1≤q, for every Dirichlet character χ\chiχ modulo qqq with values in C\mathbb{C}C, and for every natural number NNN with 2≤N2 \le N2≤N, if

q  ≤  (log⁡N)Aq \;\le\; (\log N)^{A}q≤(logN)A

(real power of the natural logarithm; ≤\le≤, not <<<), then

∥ S(q,χ,N)  −  {Nif χ=10if χ≠1 ∥  ≤  C⋅N⋅exp⁡ ⁣(−c log⁡N),\left\| \, S(q,\chi,N) \;-\; \begin{cases} N & \text{if } \chi = 1 \\ 0 & \text{if } \chi \neq 1 \end{cases} \, \right\| \;\le\; C \cdot N \cdot \exp\!\left(-c\,\sqrt{\log N}\right),​S(q,χ,N)−{N0​if χ=1if χ=1​​≤C⋅N⋅exp(−clogN​),

where ∥⋅∥\|\cdot\|∥⋅∥ is the complex absolute value, χ=1\chi = 1χ=1 means χ\chiχ is the trivial (principal) character modulo qqq, and NNN in the main term is the natural number NNN coerced to C\mathbb{C}C.

Quantifier order and what depends on what. The constants CCC and ccc are chosen after AAA and before qqq, χ\chiχ, and NNN: they may depend only on AAA, and are uniform in the modulus qqq, in the character χ\chiχ, and in the length NNN. Only ccc is required to be positive; CCC carries no positivity or sign hypothesis at all (it is merely asserted to exist as a real number), and there is no other relation imposed between CCC and ccc. Nothing asserts that CCC or ccc is effectively computable, nor is any explicit value given.

Hypotheses on qqq, χ\chiχ, NNN. The only hypothesis on the modulus is 1≤q1 \le q1≤q (so q=0q = 0q=0 is excluded, but q=1q = 1q=1 is allowed). Nothing requires χ\chiχ to be primitive, non-principal, quadratic, of bounded conductor, or induced by anything; the single Dirichlet character quantifier ranges over all characters mod qqq, principal and non-principal alike, including the character that is identically 000 on non-units. The only hypothesis on the length is 2≤N2 \le N2≤N, together with the size constraint q≤(log⁡N)Aq \le (\log N)^{A}q≤(logN)A. No hypothesis relates NNN to qqq beyond that inequality, and there is no lower bound on NNN of the form "NNN sufficiently large in terms of AAA" other than what the inequality itself forces.

Degenerate and edge cases silently included.

  • Small NNN is vacuous. Since q≥1q \ge 1q≥1 and A>0A > 0A>0, the hypothesis q≤(log⁡N)Aq \le (\log N)^{A}q≤(logN)A forces (log⁡N)A≥1(\log N)^{A} \ge 1(logN)A≥1, hence log⁡N≥1\log N \ge 1logN≥1, hence N≥3N \ge 3N≥3. In particular the case N=2N = 2N=2 (where log⁡2≈0.693\log 2 \approx 0.693log2≈0.693 and (log⁡2)A<1(\log 2)^A < 1(log2)A<1) satisfies the hypotheses for no q≥1q \ge 1q≥1 at all, so the conclusion there is vacuously true; the effective range is N≥3N \ge 3N≥3.
  • The modulus q=1q = 1q=1. Z/1Z\mathbb{Z}/1\mathbb{Z}Z/1Z is the trivial ring, so the only Dirichlet character mod 111 is the trivial one; the branch χ=1\chi = 1χ=1 is taken, χ(n)=1\chi(n) = 1χ(n)=1 for every nnn, and the claim becomes a Prime Number Theorem statement with error term exp⁡(−clog⁡N)\exp(-c\sqrt{\log N})exp(−clogN​): ∣∑n<NΛ(n)−N∣≤CNexp⁡(−clog⁡N)\bigl|\sum_{n<N}\Lambda(n) - N\bigr| \le C N \exp(-c\sqrt{\log N})​∑n<N​Λ(n)−N​≤CNexp(−clogN​).
  • The principal character's main term. Whenever χ\chiχ is the trivial character mod qqq (for any q≥1q \ge 1q≥1), the quantity subtracted is exactly NNN — not N−1N-1N−1, not φ(q)qN\frac{\varphi(q)}{q}Nqφ(q)​N, not ψ(N)\psi(N)ψ(N), and not an integral. For every non-principal χ\chiχ the subtracted quantity is exactly 000, so the claim is a bound on ∥S(q,χ,N)∥\|S(q,\chi,N)\|∥S(q,χ,N)∥ itself.
  • Off-by-one. Because the sum stops at n=N−1n = N-1n=N−1 while the main term is NNN, the comparison is between ∑n≤N−1Λ(n)χ(n)\sum_{n \le N-1}\Lambda(n)\chi(n)∑n≤N−1​Λ(n)χ(n) and NNN.
  • The if is decided classically (open Classical in supplies decidability of the equality χ=1\chi = 1χ=1); it has no mathematical content beyond selecting the two branches above.
  • Bound shape. The right-hand side is C⋅N⋅e−clog⁡NC \cdot N \cdot e^{-c\sqrt{\log N}}C⋅N⋅e−clogN​ with ⋅\sqrt{\cdot}⋅​ the real square root and log⁡\loglog the real natural logarithm; the exponent is −clog⁡N-c\sqrt{\log N}−clogN​, i.e. square-root-of-log savings, not −c(log⁡N)3/5-c(\log N)^{3/5}−c(logN)3/5 and not a power saving.

Unused material in the bundle. The dependency file Definitions/Def_Davenport_siegelWalfisz.lean also defines ψ(N;q,a)=∑n<NΛ(n) [ n≡a mod q ]\psi(N;q,a) = \sum_{n<N} \Lambda(n)\,[\,n \equiv a \bmod q\,]ψ(N;q,a)=∑n<N​Λ(n)[n≡amodq] (psiAP), a zero-free-region boundary 1−c/log⁡(q(∣ℑs∣+2))1 - c/\log\bigl(q(|\Im s|+2)\bigr)1−c/log(q(∣ℑs∣+2)) (regionBoundary), the predicate ‘InRegion‘\text{`InRegion`}‘InRegion‘ saying that boundary is ≤ℜs\le \Re s≤ℜs, and IsExceptionalSet (a subsingleton set of real zeros in (0,1)(0,1)(0,1) of L(⋅,χ)L(\cdot,\chi)L(⋅,χ) for quadratic non-principal χ\chiχ, outside which L(s,χ)≠0L(s,\chi) \neq 0L(s,χ)=0 on the region for s≠1s \neq 1s=1), and Vino.gaussE defines a Gauss sum. None of these definitions occur in the statement of Davenport.siegel_walfisz_char; the statement uses only Vino.vmSumChar as unfolded above.

Proof status (factual). The declaration's proof body is sorry.

Human review
  • Endorsed by Shuze Chen · Sep 3, 2026

  • Endorsed by alya · Sep 3, 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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me