Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Vaughan's Lemma 2.2, weight form

Proved
CircleMethod.aux_sum_min_le

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

analytic-number-theorycircle-methodexponential-sumsnumber-theory

The central counting estimate of the circle method, Vaughan's Lemma 2.2, in an abstracted weight form.

Classically the statement is that for (a,q)=1(a,q)=1(a,q)=1 and ∣α−a/q∣≤q−2|\alpha-a/q|\le q^{-2}∣α−a/q∣≤q−2,

∑k=1Hmin⁡ ⁣(N,1∥kα∥)  ≪  (Hq+1)(N+q)log⁡(1+q).\sum_{k=1}^{H}\min\!\left(N,\frac{1}{\|k\alpha\|}\right)\;\ll\;\left(\frac{H}{q}+1\right)(N+q)\log(1+q).k=1∑H​min(N,∥kα∥1​)≪(qH​+1)(N+q)log(1+q).

The mechanism is equidistribution: as kkk runs over a block of qqq consecutive integers and (a,q)=1(a,q)=1(a,q)=1, the residues ka mod qka \bmod qkamodq run over a complete residue system, so the values ∥kα∥\|k\alpha\|∥kα∥ are spread out at spacing roughly 1/q1/q1/q. Within one block at most a bounded number of kkk can have ∥kα∥\|k\alpha\|∥kα∥ in any given dyadic range, and summing q/jq/jq/j over j≤q/2j\le q/2j≤q/2 produces the logarithm. There are O(H/q+1)O(H/q+1)O(H/q+1) blocks.

Rather than the min⁡\minmin, the statement here quantifies over an arbitrary weight ggg subject to three hypotheses: g≥0g\ge 0g≥0, g≤Ng\le Ng≤N, and 2∥kα∥ g(k)≤12\|k\alpha\|\,g(k)\le 12∥kα∥g(k)≤1. Any family of exponential sums satisfies these, whatever their lengths, so the abstraction is what makes the lemma applicable after Weyl differencing — where the inner sums have lengths depending on the shift and a fixed-length statement cannot be used. Taking g(k)=∣∑x<Ne(xkα)∣g(k)=\left|\sum_{x<N}e(xk\alpha)\right|g(k)=​∑x<N​e(xkα)​ recovers the classical form.

Formalization Note. The multiplicative hypothesis 2∥kα∥ g(k)≤12\|k\alpha\|\,g(k)\le 12∥kα∥g(k)≤1 is used in place of g(k)≤12∥kα∥g(k)\le\frac{1}{2\|k\alpha\|}g(k)≤2∥kα∥1​ deliberately. In Lean 1/0=01/0=01/0=0, so the divided form would be silently weaker than intended exactly when kα∈Zk\alpha\in\mathbb{Z}kα∈Z — the case that matters most. The multiplicative form is equivalent away from that degeneracy and correct at it.

Preamble
import Definitions.Def_CircleMethod_char
import Mathlib.Analysis.SpecialFunctions.Pow.Real
import Mathlib.Analysis.SpecialFunctions.Log.Basic
import Mathlib.NumberTheory.Divisors
open Finset
Formal statement
namespace CircleMethod

theorem aux_sum_min_le {ε : ℝ} (hε : 0 < ε) :
    ∃ C : ℝ, 0 < C ∧ ∀ (H N q : ℕ) (a : ℤ) (α : ℝ) (g : ℕ → ℝ), 0 < H → 0 < N → 0 < q →
      Nat.Coprime a.natAbs q → |α - (a : ℝ) / (q : ℝ)| ≤ 1 / (q : ℝ) ^ 2 →
      (∀ k : ℕ, 0 ≤ g k) → (∀ k : ℕ, g k ≤ (N : ℝ)) →
      (∀ k : ℕ, 2 * nrm ((k : ℝ) * α) * g k ≤ 1) →
      (∑ k ∈ Finset.Icc 1 H, g k)
        ≤ C * ((H : ℝ) / (q : ℝ) + 1) * ((N : ℝ) + (q : ℝ)) * (1 + Real.log (1 + (q : ℝ))) := by sorry

end CircleMethod
Source
R. C. Vaughan, The Hardy-Littlewood Method, 2nd ed., Cambridge Tracts in Mathematics 125, Cambridge University Press, 1997, Lemma 2.2.

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