Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

∣S(p,a)∣≤kp|S(p,a)|\le k\sqrt{p}∣S(p,a)∣≤kp​ for prime moduli, elementary form

Proved
CMSharp.S_prime_bound_elementary

by tabbott · Sep 3, 2026 · Mathlib 0df444a (Lean v4.33.1)

analytic-number-theorycircle-methodexponential-sumsnumber-theory

Let ppp be a prime, k≥1k\ge1k≥1, and aaa an integer with p∤ap\nmid ap∤a. Then the complete exponential sum over the prime modulus ppp exhibits square-root cancellation:

∣S(p,a)∣=∣∑m<pe ⁣(amkp)∣  ≤  k p,e(θ)=e2πiθ.\left|S(p,a)\right|=\left|\sum_{m<p}e\!\left(\frac{am^{k}}{p}\right)\right|\;\le\;k\,\sqrt{p},\qquad e(\theta)=e^{2\pi i\theta}.∣S(p,a)∣=​m<p∑​e(pamk​)​≤kp​,e(θ)=e2πiθ.

An elementary route to square-root cancellation. The sharp form of this estimate is ∣S(p,a)∣≤(d−1)p|S(p,a)|\le(d-1)\sqrt p∣S(p,a)∣≤(d−1)p​ with d=gcd⁡(k,p−1)d=\gcd(k,p-1)d=gcd(k,p−1), which follows from evaluating S(p,a)S(p,a)S(p,a) as a sum of d−1d-1d−1 Gauss sums, each of modulus exactly p\sqrt pp​. The constant kkk stated here is weaker, but it is reachable without any multiplicative character theory, by a second-moment argument:

Writing T(t)=∑x mod pe(txk/p)T(t)=\sum_{x\bmod p}e(tx^{k}/p)T(t)=∑xmodp​e(txk/p), additive orthogonality gives the exact identity

∑t mod p∣T(t)∣2=p⋅#{(x,y):xk=yk}≤p(1+(p−1)k),\sum_{t\bmod p}|T(t)|^{2}=p\cdot\#\{(x,y): x^{k}=y^{k}\}\le p\left(1+(p-1)k\right),tmodp∑​∣T(t)∣2=p⋅#{(x,y):xk=yk}≤p(1+(p−1)k),

because xk=ykx^{k}=y^{k}xk=yk has at most kkk solutions yyy for each fixed xxx. Subtracting the term ∣T(0)∣2=p2|T(0)|^{2}=p^{2}∣T(0)∣2=p2 leaves ∑t≠0∣T(t)∣2≤p(p−1)(k−1)\sum_{t\neq0}|T(t)|^{2}\le p(p-1)(k-1)∑t=0​∣T(t)∣2≤p(p−1)(k−1). Separately, the substitution x↦cxx\mapsto cxx↦cx shows T(tck)=T(t)T(tc^{k})=T(t)T(tck)=T(t) for every c≠0c\neq0c=0, so summing ∣T(ack)∣2|T(ac^{k})|^{2}∣T(ack)∣2 over the p−1p-1p−1 nonzero ccc reproduces (p−1)∣T(a)∣2(p-1)|T(a)|^{2}(p−1)∣T(a)∣2 while covering each nonzero residue at most kkk times. Comparing the two counts yields ∣T(a)∣2≤k(k−1)p|T(a)|^{2}\le k(k-1)p∣T(a)∣2≤k(k−1)p, hence the stated bound.

Role. This is the one point in the proof of the classical estimate ∣S(q,a)∣≪q1−1/k+ε|S(q,a)|\ll q^{1-1/k+\varepsilon}∣S(q,a)∣≪q1−1/k+ε (Vaughan, Theorem 4.2) at which the trivial bound ∣S∣≤q|S|\le q∣S∣≤q is insufficient: at h=1h=1h=1 it overshoots by a factor p1/kp^{1/k}p1/k. Every higher prime power reduces to this case through the recursion S(ph,a)=pk−1S(ph−k,a)S(p^{h},a)=p^{k-1}S(p^{h-k},a)S(ph,a)=pk−1S(ph−k,a). Since 12≤1−1k\tfrac12\le1-\tfrac1k21​≤1−k1​ for k≥2k\ge2k≥2, square-root cancellation with any constant depending only on kkk is enough to drive the whole argument.

Preamble
import Definitions.Def_CircleMethod_waring
import Mathlib.Data.Nat.Prime.Basic
import Mathlib.Data.Real.Sqrt
Formal statement
namespace CMSharp

theorem S_prime_bound_elementary {k p : ℕ} (hk : 1 ≤ k) (hp : p.Prime) {a : ℤ}
    (ha : ¬ ((p : ℤ) ∣ a)) :
    ‖CircleMethod.S k p a‖ ≤ (k : ℝ) * Real.sqrt (p : ℝ) := by sorry

end CMSharp
Source
R. C. Vaughan, The Hardy-Littlewood Method, 2nd ed., Cambridge Tracts in Mathematics 125, Cambridge University Press, 1997, Chapter 4, Lemma 4.3 and Theorem 4.2 (prime-modulus case; the sharp constant there is gcd(k,p-1)-1, obtained via Gauss sums).

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