Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The fundamental counting identity of the circle method

Proved
CircleMethod.circle_method_count

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

analytic-number-theorycircle-methodexponential-sumsnumber-theory

The identity on which the entire Hardy--Littlewood circle method rests.

Let AAA be a finite set of integers and let

fA(θ)=∑a∈Ae(aθ),e(θ)=exp⁡(2πiθ),f_A(\theta)=\sum_{a\in A}e(a\theta),\qquad e(\theta)=\exp(2\pi i\theta),fA​(θ)=a∈A∑​e(aθ),e(θ)=exp(2πiθ),

be its exponential generating function. Then for every s∈Ns\in\mathbb{N}s∈N and every n∈Zn\in\mathbb{Z}n∈Z,

∫01fA(θ)s e(−nθ) dθ  =  #{(a1,…,as)∈As  :  a1+⋯+as=n}.\int_0^1 f_A(\theta)^s\,e(-n\theta)\,d\theta \;=\; \#\bigl\{(a_1,\dots,a_s)\in A^s \;:\; a_1+\cdots+a_s=n\bigr\}.∫01​fA​(θ)se(−nθ)dθ=#{(a1​,…,as​)∈As:a1​+⋯+as​=n}.

The proof is a single expansion followed by orthogonality: fA(θ)s=∑(a1,…,as)∈Ase((a1+⋯+as)θ)f_A(\theta)^s=\sum_{(a_1,\dots,a_s)\in A^s}e\bigl((a_1+\cdots+a_s)\theta\bigr)fA​(θ)s=∑(a1​,…,as​)∈As​e((a1​+⋯+as​)θ), and ∫01e(mθ) dθ\int_0^1 e(m\theta)\,d\theta∫01​e(mθ)dθ is 111 when m=0m=0m=0 and 000 otherwise, so every tuple whose sum differs from nnn is annihilated.

The significance is that an arithmetic quantity — a count of representations — has been written as an analytic one, an integral over the circle. The method then estimates that integral by splitting the circle into major arcs, where fAf_AfA​ is large and computable, and minor arcs, where fAf_AfA​ is small. Nothing in the method is possible before this identity is available.

Formalization Note. Tuples are functions Fin s→A\mathrm{Fin}\,s\to AFins→A, so they are ordered and repetitions are allowed. No hypotheses are placed on AAA, sss or nnn: the degenerate cases A=∅A=\emptysetA=∅ and s=0s=0s=0 are included, and for s=0s=0s=0 both sides reduce to [ n=0 ][\,n=0\,][n=0].

Preamble
import Definitions.Def_CircleMethod_genfun
import Mathlib.Analysis.SpecialFunctions.Pow.Real
import Mathlib.Analysis.SpecialFunctions.Integrals.Basic
import Mathlib.NumberTheory.Divisors
import Mathlib.Data.Fintype.Pi
open Finset
Formal statement
namespace CircleMethod

theorem circle_method_count (A : Finset ℤ) (s : ℕ) (n : ℤ) :
    (∫ θ in (0:ℝ)..1, (f A θ) ^ s * e (-(n : ℝ) * θ))
      = ((((Fintype.piFinset (fun _ : Fin s => A)).filter
            (fun v => ∑ i, v i = n)).card : ℕ) : ℂ) := by sorry

end CircleMethod
Source
R. C. Vaughan, The Hardy-Littlewood Method, 2nd ed., Cambridge Tracts in Mathematics 125, Cambridge University Press, 1997, Section 1.1, equations (1.3)-(1.4) (the fundamental identity of the circle method).
Read-back

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

Read-back of CircleMethod.circle_method_count

The statement is universally quantified over three explicit arguments, with no hypotheses of any kind on them: a finite set AAA of integers (a Finset of Z\mathbb{Z}Z, so its elements are distinct integers, and it is allowed to be empty, and its elements may be negative or zero), a natural number sss (allowed to be 000), and an integer nnn (allowed to be negative or zero). There are no typeclass assumptions beyond those already carried by Z\mathbb{Z}Z, N\mathbb{N}N, R\mathbb{R}R and C\mathbb{C}C, and no positivity, nonemptiness, or size condition is imposed.

Two auxiliary notions from the bundle enter the statement and are unfolded here. First, for a real number θ\thetaθ,

e(θ)  =  exp⁡ ⁣(2πi θ)∈C,e(\theta) \;=\; \exp\!\big(2\pi i\,\theta\big) \in \mathbb{C},e(θ)=exp(2πiθ)∈C,

the complex exponential of 2πi2\pi i2πi times θ\thetaθ (with π\piπ and θ\thetaθ viewed as complex numbers). Second, for a finite set A⊆ZA \subseteq \mathbb{Z}A⊆Z and a real θ\thetaθ,

fA(θ)  =  ∑a∈Ae(a θ)  =  ∑a∈Aexp⁡ ⁣(2πi a θ)∈C,f_A(\theta) \;=\; \sum_{a \in A} e\big(a\,\theta\big) \;=\; \sum_{a \in A} \exp\!\big(2\pi i\, a\,\theta\big) \in \mathbb{C},fA​(θ)=a∈A∑​e(aθ)=a∈A∑​exp(2πiaθ)∈C,

where each integer aaa is first cast to a real number and multiplied by θ\thetaθ; the sum ranges over the elements of the finite set AAA, each occurring once. (An additional definition in scope, nrm(θ)=∣θ−round(θ)∣\mathrm{nrm}(\theta) = |\theta - \mathrm{round}(\theta)|nrm(θ)=∣θ−round(θ)∣, the distance from θ\thetaθ to a nearest integer, plays no role in this statement.)

The assertion is an equality of two complex numbers. The left-hand side is the oriented interval integral of a complex-valued function of the real variable θ\thetaθ, taken from 000 to 111:

∫01(fA(θ))s e(−n θ) dθ  =  ∫01(∑a∈Aexp⁡(2πi a θ)) ⁣sexp⁡ ⁣(−2πi n θ) dθ,\int_{0}^{1} \big(f_A(\theta)\big)^{s}\, e\big(-n\,\theta\big)\, d\theta \;=\; \int_{0}^{1} \Big(\sum_{a \in A} \exp(2\pi i\, a\,\theta)\Big)^{\!s} \exp\!\big(-2\pi i\, n\,\theta\big)\, d\theta ,∫01​(fA​(θ))se(−nθ)dθ=∫01​(a∈A∑​exp(2πiaθ))sexp(−2πinθ)dθ,

where sss is the exponent of an ordinary power in C\mathbb{C}C (so the integrand is the constant function 111 times e(−nθ)e(-n\theta)e(−nθ) when s=0s = 0s=0, including at points where fA(θ)=0f_A(\theta) = 0fA​(θ)=0), and the integer nnn is cast to a real number and then negated before being multiplied by θ\thetaθ. This is an interval integral in the Bochner sense; by the convention attached to that construction it would evaluate to 000 if the integrand failed to be integrable on [0,1][0,1][0,1], so the equation is an equation between two complex numbers in all cases, with no integrability hypothesis stated.

The right-hand side is a cardinality, first as a natural number and then cast into C\mathbb{C}C. Consider the set of all functions

v:{0,1,…,s−1}⟶Zv : \{0, 1, \dots, s-1\} \longrightarrow \mathbb{Z}v:{0,1,…,s−1}⟶Z

(indexed by the sss-element type Fin s\mathrm{Fin}\,sFins) such that vi∈Av_i \in Avi​∈A for every index iii — that is, the set of ordered sss-tuples (v0,…,vs−1)(v_0, \dots, v_{s-1})(v0​,…,vs−1​) of elements of AAA, with repetitions allowed and order significant. Among these, keep exactly those satisfying

∑ivi  =  n,\sum_{i} v_i \;=\; n,i∑​vi​=n,

the sum being over all sss indices, and take the number of tuples so retained. The claim is that this count, viewed as a complex number, equals the integral above:

∫01(fA(θ))s e(−nθ) dθ  =  #{ v∈As  :  ∑i=0s−1vi=n }.\int_{0}^{1} \big(f_A(\theta)\big)^{s}\, e(-n\theta)\, d\theta \;=\; \#\Big\{\, v \in A^{s} \;:\; \sum_{i=0}^{s-1} v_i = n \,\Big\}.∫01​(fA​(θ))se(−nθ)dθ=#{v∈As:i=0∑s−1​vi​=n}.

Several degenerate instances are silently included by the quantifiers. If s=0s = 0s=0, the left-hand side is ∫01e(−nθ) dθ\int_0^1 e(-n\theta)\,d\theta∫01​e(−nθ)dθ and the right-hand side counts the tuples indexed by the empty index set: there is exactly one such (the empty tuple), its sum is the empty sum 000, so the count is 111 when n=0n = 0n=0 and 000 otherwise — and this holds regardless of AAA, in particular for A=∅A = \varnothingA=∅. If A=∅A = \varnothingA=∅ and s≥1s \ge 1s≥1, then fA(θ)=0f_A(\theta) = 0fA​(θ)=0 for every θ\thetaθ, the left-hand side is 000, and there are no admissible tuples, so the right-hand side is 000 as well. Since AAA is a finite set rather than a multiset, repeated integers cannot occur among the summands of fAf_AfA​, though a single element of AAA may of course be reused across several coordinates of a tuple vvv. The equation is asserted for every integer nnn, including those that are not representable as such a sum, in which case the right-hand side is the cast of 000.

The declaration is stated as a theorem whose proof is left as sorry, i.e. no proof is supplied.

Human review
  • Endorsed by tianyipeng · Sep 2, 2026

  • Endorsed by tabbott · Sep 2, 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