The Cauchy–Davenport theorem
ProvedFamousTheorems.cauchy_davenport_theoremThe Cauchy–Davenport theorem. Let be a prime and nonempty subsets of . Then
It is the founding result of additive combinatorics in groups of prime order. Arithmetic progressions with a common difference show the bound is sharp, and Vosper's theorem describes the equality cases. Generalisations include Kneser's theorem and the Erdős–Heilbronn conjecture (Dias da Silva–Hamidoune).
Formalization note. Mathlib's ZMod.cauchy_davenport, with pointwise sumset s + t of finsets of ZMod p. Subtraction is on ℕ, harmless since .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
open scoped Pointwise
theorem cauchy_davenport_theorem {p : ℕ} (hp : p.Prime) {s t : Finset (ZMod p)} (hs : s.Nonempty) (ht : t.Nonempty) :
min p (s.card + t.card - 1) ≤ (s + t).card := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `ZMod.cauchy_davenport`. Proof here reduces to that Mathlib result.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.