Cauchy--Davenport bound for the -th power residues
ProvedCircleMethod.card_kthPowers_gecircle-methodnumber-theorysingular-serieswaring
Let be prime and , and let be the set of -th power residues (including ). Then
Equivalently , which is the familiar count of -th powers in . Applied through the Cauchy--Davenport theorem — the -fold sumset has cardinality at least — it shows that once the sumset is all of : every residue class is a sum of -th powers modulo .
Preamble
/- # Positivity of the singular series in Waring's problem `singSeries k s n = ∑' q, locDens k s q n` is the singular series `𝔖(n)`. This file establishes its Euler product `𝔖(n) = ∏_p σ_p(n)`, `σ_p(n) = ∑_j A(p^j, n)`, bounds the tail of the product, and assembles a uniform lower bound `𝔖(n) ≥ c(k,s) > 0` from the local-solubility statement `LocalSolubility k s` (Vaughan, Lemmas 2.13–2.15). -/ import Definitions.Def_CircleMethod_singpos import Theorems.Thm_CircleMethod_locDens_mul import Theorems.Thm_CircleMethod_locDens_one import Theorems.Thm_CircleMethod_locDens_zero_modulus import Theorems.Thm_CircleMethod_locDens_bound import Theorems.Thm_CircleMethod_locDens_exponent_lt_neg_one import Theorems.Thm_CircleMethod_sing_series_summable_norm import Theorems.Thm_CircleMethod_e_zero import Theorems.Thm_CircleMethod_e_add import Theorems.Thm_CircleMethod_sum_e_div_orthogonality import Theorems.Thm_Vino_e_div_congr import Mathlib.NumberTheory.EulerProduct.Basic import Mathlib.NumberTheory.SumPrimeReciprocals import Mathlib.NumberTheory.Padics.Hensel import Mathlib.NumberTheory.Padics.RingHoms import Mathlib.Combinatorics.Additive.CauchyDavenport open Finset Filter Topology open Finset Filter Topology
Formal statement
namespace CircleMethod
theorem card_kthPowers_ge {p k : ℕ} [Fact p.Prime] (hk : 1 ≤ k) :
p ≤ 1 + k * ((Finset.univ.image (fun x : ZMod p => x ^ k)).card - 1) := by sorry
end CircleMethodSource
R. C. Vaughan, The Hardy-Littlewood Method, 2nd ed., Cambridge Tracts in Mathematics 125, Cambridge University Press, 1997, Section 2.6, Lemma 2.15; H. Davenport, On the addition of residue classes, J. London Math. Soc. 10 (1935), 30-32