Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Weyl differencing: ∣S∣2|S|^2∣S∣2 as a difference sum

Proved
CircleMethod.weyl_squaring

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

analytic-number-theorycircle-methodexponential-sumsnumber-theory

The opening move of Weyl differencing. For any real-valued function φ\varphiφ on the natural numbers and any NNN,

(∑x=0N−1e(φ(x)))(∑x=0N−1e(φ(x)))‾  =  ∑x=0N−1∑y=0N−1e(φ(x)−φ(y)).\left(\sum_{x=0}^{N-1}e(\varphi(x))\right)\overline{\left(\sum_{x=0}^{N-1}e(\varphi(x))\right)} \;=\; \sum_{x=0}^{N-1}\sum_{y=0}^{N-1} e\bigl(\varphi(x)-\varphi(y)\bigr).(x=0∑N−1​e(φ(x)))(x=0∑N−1​e(φ(x)))​=x=0∑N−1​y=0∑N−1​e(φ(x)−φ(y)).

The left-hand side is ∣S∣2|S|^2∣S∣2 for SSS the exponential sum; the right-hand side replaces the phase φ\varphiφ by its differences. When φ\varphiφ is a polynomial of degree kkk, substituting y=x+hy=x+hy=x+h makes the inner phase φ(x+h)−φ(x)\varphi(x+h)-\varphi(x)φ(x+h)−φ(x) a polynomial of degree k−1k-1k−1 in xxx for each fixed hhh. Iterating the manoeuvre k−1k-1k−1 times reduces a degree-kkk Weyl sum to linear sums, which the geometric bound ∣∑x<Ne(xθ)∣≤min⁡ ⁣(N,12∥θ∥)\left|\sum_{x<N}e(x\theta)\right|\le\min\!\left(N,\frac{1}{2\|\theta\|}\right)​∑x<N​e(xθ)​≤min(N,2∥θ∥1​) already controls. Each squaring costs a square root in the final estimate, which is the origin of the exponent 21−k2^{1-k}21−k in Weyl's inequality.

Formalization Note. Stated as an equation in C\mathbb{C}C between SS‾S\overline{S}SS and the double sum, rather than in R\mathbb{R}R using ∣S∣2|S|^2∣S∣2, so that it can be chained with other complex identities without casting. No hypotheses on φ\varphiφ or NNN; the case N=0N=0N=0 gives 0=00=00=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 weyl_squaring (φ : ℕ → ℝ) (N : ℕ) :
    (∑ x ∈ Finset.range N, e (φ x)) * (starRingEnd ℂ) (∑ x ∈ Finset.range N, e (φ x))
      = ∑ x ∈ Finset.range N, ∑ y ∈ Finset.range N, e (φ x - φ y) := by sorry

end CircleMethod
Source
R. C. Vaughan, The Hardy-Littlewood Method, 2nd ed., 1997, Section 2.2, opening of the proof of Lemma 2.3 (the Weyl differencing / squaring step).
Read-back

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

The declaration weyl_squaring asserts the following, for every function φ:N→R\varphi : \mathbb{N} \to \mathbb{R}φ:N→R assigning a real number φ(x)\varphi(x)φ(x) to each natural number xxx, and for every natural number NNN (both universally quantified, with no hypotheses whatsoever imposed on either — φ\varphiφ is an arbitrary real-valued sequence, not assumed continuous, bounded, polynomial, or of any particular shape, and NNN is arbitrary, including N=0N = 0N=0):

(∑x=0N−1e(φ(x)))⋅(∑x=0N−1e(φ(x)))‾  =  ∑x=0N−1 ∑y=0N−1e(φ(x)−φ(y)).\left(\sum_{x = 0}^{N-1} e\bigl(\varphi(x)\bigr)\right)\cdot\overline{\left(\sum_{x = 0}^{N-1} e\bigl(\varphi(x)\bigr)\right)} \;=\; \sum_{x = 0}^{N-1}\ \sum_{y = 0}^{N-1} e\bigl(\varphi(x) - \varphi(y)\bigr).(x=0∑N−1​e(φ(x)))⋅(x=0∑N−1​e(φ(x)))​=x=0∑N−1​ y=0∑N−1​e(φ(x)−φ(y)).

Here the symbol eee is not a primitive: it is the additive character defined in this bundle by

e(θ)  =  exp⁡ ⁣(2πi θ)(θ∈R),e(\theta) \;=\; \exp\!\bigl(2\pi i\,\theta\bigr) \qquad (\theta \in \mathbb{R}),e(θ)=exp(2πiθ)(θ∈R),

a complex number of modulus 111, where the real argument θ\thetaθ is regarded as a complex number and π\piπ is the real circle constant. The bar denotes complex conjugation on C\mathbb{C}C (the canonical conjugation ring automorphism of the complex numbers), applied to the complete sum; thus the left-hand side is the product of the sum with its own conjugate, i.e. the squared modulus of that sum, written as a product rather than as ∣⋅∣2|\cdot|^2∣⋅∣2.

Both index ranges are the finite set of natural numbers {0,1,…,N−1}\{0, 1, \dots, N-1\}{0,1,…,N−1}, i.e. the NNN natural numbers strictly below NNN; the left-hand sum runs over this set, and the right-hand double sum runs over the same set independently in each of its two variables, giving N2N^2N2 terms. The argument of the character on the right is the real difference φ(x)−φ(y)\varphi(x) - \varphi(y)φ(x)−φ(y), subtraction in R\mathbb{R}R (so it may be negative; this is not truncated natural-number subtraction), and eee is then applied to that real difference.

Degenerate case: when N=0N = 0N=0 the index set is empty, both sides are the empty sum 000, the conjugate of 000 is 000, and the statement reads 0⋅0=00 \cdot 0 = 00⋅0=0. When N=1N = 1N=1 it reads e(φ(0)) e(φ(0))‾=e(φ(0)−φ(0))=e(0)e(\varphi(0))\,\overline{e(\varphi(0))} = e(\varphi(0) - \varphi(0)) = e(0)e(φ(0))e(φ(0))​=e(φ(0)−φ(0))=e(0). The equality is an equality of complex numbers, asserted unconditionally for all φ\varphiφ and all NNN simultaneously.

Two further definitions from this bundle are in scope but do not appear anywhere in the statement: the generating function fff of a finite set A⊆ZA \subseteq \mathbb{Z}A⊆Z, given by f(A,θ)=∑a∈Ae(aθ)f(A, \theta) = \sum_{a \in A} e(a\theta)f(A,θ)=∑a∈A​e(aθ), and the distance-to-the-nearest-integer function ∥θ∥=∣θ−round(θ)∣\|\theta\| = |\theta - \mathrm{round}(\theta)|∥θ∥=∣θ−round(θ)∣. Neither the sums here nor the character arguments are tied to fff, to any set AAA, to ∥⋅∥\|\cdot\|∥⋅∥, or to any rational approximation; the statement involves only the arbitrary sequence φ\varphiφ, the bound NNN, and the character eee.

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