Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Three primes: Siegel--Walfisz, Farey arcs, singular series and integral

Definition
Vino_threeprimes

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

circle-methodnumber-theorythree-primesvinogradov

The vocabulary of the Hardy--Littlewood--Vinogradov circle method for the three primes theorem.

  • SiegelWalfisz states the Siegel--Walfisz theorem as a Prop, in Dirichlet-character form: for every A>0A>0A>0 there are C,c>0C,c>0C,c>0 with ∣ψ(N,χ)−δχN∣≤CNe−clog⁡N\bigl|\psi(N,\chi)-\delta_\chi N\bigr|\le CN e^{-c\sqrt{\log N}}​ψ(N,χ)−δχ​N​≤CNe−clogN​ for every character χ\chiχ modulo q≤(log⁡N)Aq\le(\log N)^Aq≤(logN)A. Mathlib does not yet contain this theorem, so it is carried as a hypothesis.
  • R n is the weighted representation count ∑a+b+c=nΛ(a)Λ(b)Λ(c)\sum_{a+b+c=n}\Lambda(a)\Lambda(b)\Lambda(c)∑a+b+c=n​Λ(a)Λ(b)Λ(c), singSeries n the singular series S(n)=∑qμ(q)2φ(q)−3cq(−n)\mathfrak S(n)=\sum_q \mu(q)^2\varphi(q)^{-3}c_q(-n)S(n)=∑q​μ(q)2φ(q)−3cq​(−n), mainTerm n the predicted main term 12S(n)n2\tfrac12\mathfrak S(n)n^221​S(n)n2, and integrand n α the cube S(α,N)3e(−nα)S(\alpha,N)^3e(-n\alpha)S(α,N)3e(−nα) whose integral over the circle is R(n)R(n)R(n).
  • arcParam B n =P=⌊(log⁡N)B⌋+1=P=\lfloor(\log N)^B\rfloor+1=P=⌊(logN)B⌋+1, rad B n =ρ=P/N=\rho=P/N=ρ=P/N, fareyPairs P the reduced fractions a/qa/qa/q with q≤Pq\le Pq≤P, and major/minor the resulting Farey dissection of the circle; majorInt, minorInt are the integrals of the integrand over them.
  • v β N =∑m<Ne(βm)=\sum_{m<N}e(\beta m)=∑m<N​e(βm) is the linear generating function, arith q =μ(q)/φ(q)=\mu(q)/\varphi(q)=μ(q)/φ(q) the arithmetic factor of the major-arc approximation, singIntTrunc n ρ the truncated singular integral, truncSeries P n the truncated singular series, and T, J their values at the arc parameters.
  • ThreePrimesAsymptotic and ThreePrimesExistence are the two conclusions: R(n)=12S(n)n2+o(n2)R(n)=\tfrac12\mathfrak S(n)n^2+o(n^2)R(n)=21​S(n)n2+o(n2), and every sufficiently large odd nnn is a sum of three primes.
Definition code
/-
# Vinogradov's three primes theorem, conditional on Siegel–Walfisz — statement and reduction

## What this file is

The three primes theorem (every sufficiently large odd `n` is a sum of three primes) is
proved by the Hardy–Littlewood–Vinogradov circle method.  Its major-arc analysis needs the
prime number theorem in arithmetic progressions with an error term uniform in the modulus
`q ≤ (log N)^A` — the **Siegel–Walfisz theorem** — which Mathlib does not have.  This file

1. states Siegel–Walfisz as a `Prop` (`SiegelWalfisz`), in the *Dirichlet character* form;
2. states the weighted asymptotic `R(n) = ½ 𝔖(n) n² + o(n²)` and the existence theorem,
   both conditional on `SiegelWalfisz`;
3. reduces them to explicitly stated pieces, each proved here or AVAILABLE on the platform
   (the file is now complete: every piece is discharged);
4. proves the assembly bookkeeping, the passage from the asymptotic to the existence
   statement, the major-arc main-term identity, and the elementary estimates.

The structural template is `Solutions/M_waring_final.lean` (the proved Waring assembly).

## Why the character form of Siegel–Walfisz

`Vino.vmSum_coprime_char_expansion` (platform, Proved) writes the coprime part of the
exponential sum at a rational point as

  `φ(q) ∑_{n<N, (n,q)=1} Λ(n) e(bn/q) = ∑_{χ mod q} χ⁻¹(b) τ(χ) ψ(N, χ⁻¹)`,

so the input the major arcs actually consume is a bound on `ψ(N,χ) = ∑_{n<N} Λ(n)χ(n)` for
*every* character `χ` mod `q`, uniformly in `q ≤ (log N)^A`.  This is also the form in which
Siegel–Walfisz is proved (zero-free regions of `L(s,χ)` plus Siegel's theorem); the
arithmetic-progression form `ψ(N;q,a) = N/φ(q) + O(N e^{-c√log N})` is *derived* from it by
finite character orthogonality, and conversely, so nothing is lost.  Finally, the character
form makes the principal-character case explicit: `χ = 1` is the prime number theorem with
the de la Vallée-Poussin error term, up to the `O(log q · log N)` contribution of the
`n` sharing a factor with `q`.

## Parameters

`N = n + 1` (so `∑_{a,b,c<N}` captures every representation of `n`);
`P = ⌊(log n)^B⌋₊ + 1` with `B > 12` fixed (the major arcs are `|α − a/q| ≤ P/N`, `q ≤ P`);
Farey order `Q = ⌊N/P⌋` for the dissection.  On the minor arcs `q > P`, and the Vaughan bound
gives `‖S‖ ≪ N (log N)^{4 − B/2}`; with Parseval `∫|S|² ≤ N (log N)²` the minor-arc integral is
`≪ N² (log N)^{6 − B/2} = o(N²)`.  On the major arcs Siegel–Walfisz with `A = B` gives
`S(a/q+β) = μ(q)/φ(q)·v(β) + O(q (1+|β|N) N (log N)^{-B'})`, and the total major-arc error is
`≪ N² P⁵ (log N)^{2−B'} = o(N²)` for `B' > 5B + 2`.
-/
import Definitions.Def_CircleMethod_char
import Definitions.Def_Vino_primes
import Definitions.Def_Vino_ramanujan
import Definitions.Def_Vino_dirichlet
import Theorems.Thm_Vino_three_primes_count
import Theorems.Thm_Vino_integral_cube_orthogonality
import Theorems.Thm_Vino_vmSum_coprime_char_expansion
import Theorems.Thm_Vino_vmSum_split_coprime
import Theorems.Thm_Vino_vmSum_add_one
import Theorems.Thm_Vino_vmSum_zero_len
import Theorems.Thm_Vino_norm_vmSum_le
import Theorems.Thm_Vino_norm_vmSum_le_mul_log
import Theorems.Thm_Vino_psi_le
import Theorems.Thm_Vino_psi_nonneg
import Theorems.Thm_Vino_continuous_e
import Theorems.Thm_Vino_intervalIntegrable_e
import Theorems.Thm_CircleMethod_divisor_bound
import Theorems.Thm_Vino_norm_ramanujan_le
import Theorems.Thm_Vino_ramanujan_mul_unit
import Theorems.Thm_Vino_ramanujan_neg
import Theorems.Thm_Vino_ramanujan_eq_sum_units
import Theorems.Thm_Vino_singSeriesDvd_eq_prod
import Theorems.Thm_Vino_singSeriesDvd_ne_zero_of_odd
import Theorems.Thm_Vino_singSeries_euler_product
import Theorems.Thm_Vino_prod_threePrimeFactor_pos
import Theorems.Thm_Vino_threePrimeFactor_two_of_odd
import Theorems.Thm_Vino_threePrimeFactor_pos_of_odd
import Theorems.Thm_Vino_card_coprime_filter
import Theorems.Thm_Vaughan_norm_vmSum_minor_le
import Theorems.Thm_CircleMethod_farey_cover_coprime
import Theorems.Thm_CircleMethod_rat_sep
import Theorems.Thm_CircleMethod_norm_sum_e_le
import Theorems.Thm_CircleMethod_norm_sum_e_le_inv_nrm
import Theorems.Thm_CircleMethod_integral_e_orthogonality
import Theorems.Thm_CircleMethod_e_add
import Theorems.Thm_CircleMethod_e_neg
import Theorems.Thm_CircleMethod_e_zero
import Theorems.Thm_CircleMethod_e_intCast
import Theorems.Thm_CircleMethod_e_add_intCast
import Theorems.Thm_CircleMethod_e_sub_intCast
import Theorems.Thm_CircleMethod_norm_e
import Theorems.Thm_CircleMethod_nrm_le
import Theorems.Thm_CircleMethod_nrm_le_half
import Theorems.Thm_CircleMethod_nrm_nonneg
import Mathlib.NumberTheory.ArithmeticFunction.VonMangoldt
import Mathlib.NumberTheory.ArithmeticFunction.Moebius
import Mathlib.NumberTheory.DirichletCharacter.Basic
import Mathlib.Analysis.SpecialFunctions.Pow.Real
import Mathlib.Analysis.SpecialFunctions.Pow.Asymptotics
import Mathlib.Analysis.SpecialFunctions.Log.Basic
import Mathlib.Analysis.Complex.ExponentialBounds
import Mathlib.Analysis.Asymptotics.Lemmas
import Mathlib.Analysis.Asymptotics.Defs
import Mathlib.MeasureTheory.Integral.Bochner.Set
import Mathlib.MeasureTheory.Integral.IntervalIntegral.Basic
import Mathlib.MeasureTheory.Integral.IntervalIntegral.Periodic
import Mathlib.MeasureTheory.Function.LocallyIntegrable
import Mathlib.MeasureTheory.Measure.Lebesgue.Integral
import Mathlib.Topology.Algebra.InfiniteSum.NatInt
import Mathlib.Analysis.Normed.Group.InfiniteSum
import Mathlib.Data.Nat.Totient
import Mathlib.Data.Nat.Factorization.Induction
import Mathlib.Data.Nat.Squarefree
import Mathlib.Data.Nat.Log
import Mathlib.Analysis.PSeries
import Mathlib.Analysis.SpecialFunctions.Integrals.Basic
import Mathlib.NumberTheory.Divisors
import Theorems.Thm_CircleMethod_sum_e_div_orthogonality
import Theorems.Thm_CircleMethod_norm_e_sub_one_le_two_pi_mul
import Mathlib.NumberTheory.DirichletCharacter.Orthogonality
import Mathlib.NumberTheory.DirichletCharacter.Bounds
import Mathlib.RingTheory.RootsOfUnity.AlgebraicallyClosed
import Mathlib.Analysis.Complex.Polynomial.Basic
import Mathlib.FieldTheory.IsSepClosed
import Mathlib.Analysis.Real.Pi.Bounds
import Mathlib.Algebra.BigOperators.Module
import Mathlib.Data.ZMod.Units

open CircleMethod Vino Finset Filter Asymptotics MeasureTheory
open scoped Topology

namespace ThreePrimes

open Classical in
/-- **Siegel–Walfisz** (character form).  For every `A > 0` there are constants `C` and
`c > 0` such that for every modulus `q ≥ 1`, every Dirichlet character `χ` mod `q`, and every
`N ≥ 2` with `q ≤ (log N)^A`,

  `‖ψ(N, χ) − δ_χ N‖ ≤ C N exp(−c √(log N))`,

where `ψ(N,χ) = ∑_{n<N} Λ(n) χ(n)` (`Vino.vmSumChar`) and `δ_χ = 1` for the principal
character and `0` otherwise.  (The `χ = 1` case is the prime number theorem with the de la
Vallée-Poussin error term, up to the `O(log q · log N)` mass of the `n` not coprime to `q`.) -/
def SiegelWalfisz : Prop :=
  ∀ A : ℝ, 0 < A → ∃ C c : ℝ, 0 < c ∧
    ∀ (q : ℕ), 1 ≤ q → ∀ (χ : DirichletCharacter ℂ q) (N : ℕ), 2 ≤ N →
      (q : ℝ) ≤ Real.log N ^ A →
        ‖vmSumChar q χ N - (if χ = 1 then (N : ℂ) else 0)‖
          ≤ C * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log N))

open Classical in
/-- The power-of-logarithm saving that the circle method actually consumes: for all `A, B > 0`,
`‖ψ(N,χ) − δ_χ N‖ ≤ C N (log N)^{−B}` uniformly for `q ≤ (log N)^A`. -/
def SiegelWalfiszLog : Prop :=
  ∀ A B : ℝ, 0 < A → 0 < B → ∃ C : ℝ,
    ∀ (q : ℕ), 1 ≤ q → ∀ (χ : DirichletCharacter ℂ q) (N : ℕ), 2 ≤ N →
      (q : ℝ) ≤ Real.log N ^ A →
        ‖vmSumChar q χ N - (if χ = 1 then (N : ℂ) else 0)‖
          ≤ C * (N : ℝ) * Real.log N ^ (-B)

/-- `R(n) = ∑_{n₁+n₂+n₃=n} Λ(n₁)Λ(n₂)Λ(n₃)`, the weighted number of representations of `n`
as a sum of three prime powers (`Λ`-weighted). -/
noncomputable def R (n : ℕ) : ℝ :=
  ∑ a ∈ range (n + 1), ∑ b ∈ range (n + 1), ∑ c ∈ range (n + 1),
    if a + b + c = n then
      (ArithmeticFunction.vonMangoldt a : ℝ) * (ArithmeticFunction.vonMangoldt b : ℝ)
        * (ArithmeticFunction.vonMangoldt c : ℝ)
    else 0

/-- The singular series of the three primes problem,
`𝔖(n) = ∑_{q ≥ 1} μ(q) c_q(n) / φ(q)³` (the `q = 0` term of `Vino.singTerm` is `0`). -/
noncomputable def singSeries (n : ℤ) : ℂ := ∑' q : ℕ, singTerm q n

/-- The main term `½ 𝔖(n) n²`. -/
noncomputable def mainTerm (n : ℕ) : ℂ := (1 / 2 : ℂ) * singSeries (n : ℤ) * (n : ℂ) ^ 2

/-- The circle-method integrand `S(α, n+1)³ e(−nα)`. -/
noncomputable def integrand (n : ℕ) (α : ℝ) : ℂ :=
  (vmSum α (n + 1)) ^ 3 * e (-(n : ℝ) * α)

/-- **The weighted three primes asymptotic** (conditional):
`R(n) = ½ 𝔖(n) n² + o(n²)`.  Stated here; proved in §9 (`three_primes_asymptotic`) from the
pieces of §§3–8. -/
def ThreePrimesAsymptotic : Prop :=
  (fun n : ℕ => (R n : ℂ) - mainTerm n) =o[atTop] (fun n : ℕ => (n : ℝ) ^ 2)

/-- **Vinogradov's three primes theorem** (conditional): every sufficiently large odd `n` is
a sum of three primes.  Stated here; proved in §9 (`three_primes`). -/
def ThreePrimesExistence : Prop :=
  ∃ N₀ : ℕ, ∀ n : ℕ, N₀ ≤ n → Odd n →
    ∃ p₁ p₂ p₃ : ℕ, p₁.Prime ∧ p₂.Prime ∧ p₃.Prime ∧ p₁ + p₂ + p₃ = n

/-- `P = ⌊(log N)^B⌋₊ + 1` with `N = n + 1`. -/
noncomputable def arcParam (B : ℝ) (n : ℕ) : ℕ := ⌊Real.log ((n : ℝ) + 1) ^ B⌋₊ + 1

/-- The half-width `ρ = P / N` of the major arcs. -/
noncomputable def rad (B : ℝ) (n : ℕ) : ℝ := (arcParam B n : ℝ) / ((n : ℝ) + 1)

/-- The Farey pairs `(q, a)` with `1 ≤ a ≤ q ≤ P`, `(a, q) = 1`. -/
def fareyPairs (P : ℕ) : Finset (ℕ × ℕ) :=
  (Finset.Icc 1 P).biUnion fun q =>
    ((Finset.Icc 1 q).filter fun a => Nat.Coprime a q).image fun a => (q, a)

/-- The major arcs. -/
noncomputable def major (B : ℝ) (n : ℕ) : Set ℝ :=
  ⋃ p ∈ fareyPairs (arcParam B n),
    Set.Icc ((p.2 : ℝ) / (p.1 : ℝ) - rad B n) ((p.2 : ℝ) / (p.1 : ℝ) + rad B n)

/-- The minor arcs. -/
noncomputable def minor (B : ℝ) (n : ℕ) : Set ℝ :=
  Set.Ico (rad B n) (1 + rad B n) \ major B n

/-- `v(β) = ∑_{m<N} e(βm)`, the main-term generating function. -/
noncomputable def v (β : ℝ) (N : ℕ) : ℂ := ∑ m ∈ range N, e (β * (m : ℝ))

/-- The arithmetic factor `μ(q)/φ(q)` of the main term at `a/q`. -/
noncomputable def arith (q : ℕ) : ℂ :=
  ((ArithmeticFunction.moebius q : ℤ) : ℂ) / (Nat.totient q : ℂ)

/-- The truncated singular integral `J(n, ρ) = ∫_{−ρ}^{ρ} v(β)³ e(−nβ) dβ` (with `N = n+1`). -/
noncomputable def singIntTrunc (n : ℕ) (ρ : ℝ) : ℂ :=
  ∫ β in (-ρ)..ρ, (v β (n + 1)) ^ 3 * e (-(n : ℝ) * β)

/-- The truncated singular series `∑_{q ≤ P} μ(q) c_q(n) / φ(q)³`. -/
noncomputable def truncSeries (P : ℕ) (n : ℤ) : ℂ := ∑ q ∈ Finset.Icc 1 P, singTerm q n

/-- The error made on the arc around `a/q` when `S³` is replaced by `(arith(q) v)³`. -/
noncomputable def arcErr (n : ℕ) (q a : ℕ) (ρ : ℝ) : ℂ :=
  ∫ β in (-ρ)..ρ, ((vmSum ((a : ℝ) / (q : ℝ) + β) (n + 1)) ^ 3 - (arith q * v β (n + 1)) ^ 3)
    * e (-(n : ℝ) * β)

/-- The five quantities entering the assembly. -/
noncomputable def minorInt (B : ℝ) (n : ℕ) : ℂ := ∫ α in minor B n, integrand n α

noncomputable def majorInt (B : ℝ) (n : ℕ) : ℂ := ∫ α in major B n, integrand n α

noncomputable def J (B : ℝ) (n : ℕ) : ℂ := singIntTrunc n (rad B n)

noncomputable def T (B : ℝ) (n : ℕ) : ℂ := truncSeries (arcParam B n) (n : ℤ)

noncomputable def target (n : ℕ) : ℝ := (n : ℝ) ^ 2

/-- The prime powers `p^k ≤ n` with `k ≥ 2`. -/
noncomputable def primePowNonPrime (n : ℕ) : Finset ℕ :=
  (range (n + 1)).filter fun a => IsPrimePow a ∧ ¬ a.Prime

end ThreePrimes
Source
I. M. Vinogradov, Representation of an odd number as a sum of three primes, Dokl. Akad. Nauk SSSR 15 (1937), 291-294; R. C. Vaughan, The Hardy-Littlewood Method, 2nd ed., Cambridge Tracts 125, Chapter 3; H. Davenport, Multiplicative Number Theory, 3rd ed., GTM 74, Chapters 22-26
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 paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me