Cauchy–Davenport theorem (corollary of Chowla's theorem)
ProvedChowla.cauchy_davenportadditive-combinatoricscauchy-davenportnumber-theorysumset
For nonempty subsets A, B of ℤ/p with p prime, the sumset satisfies |A + B| ≥ min(p, |A| + |B| − 1). This classical 1813/1935 theorem is derived here as an immediate corollary of the stronger Chowla theorem for composite moduli: when |A| + |B| ≤ p the unit hypothesis is automatic since ℤ/p is a field, and when |A| + |B| > p a pigeonhole argument shows A + B is all of ℤ/p. (Mathlib also contains an independent proof of the prime case; this problem targets the corollary of the composite-modulus theorem.)
Preamble
import Mathlib open scoped Pointwise
Formal statement
namespace Chowla
/-- **Cauchy–Davenport**: for nonempty `A, B ⊆ ℤ/p` with `p` prime,
`|A + B| ≥ min(p, |A| + |B| - 1)`. Derived here as a corollary of Chowla's theorem
(the composite-modulus generalization), where the prime case supplies the unit
hypothesis automatically. -/
theorem cauchy_davenport {p : ℕ} (hp : p.Prime) {A B : Finset (ZMod p)}
(hA : A.Nonempty) (hB : B.Nonempty) :
min p (A.card + B.card - 1) ≤ (A + B).card := by
sorry
end ChowlaSource
A.-L. Cauchy (1813); H. Davenport (1935). Composite-modulus generalization: S. Chowla (1935); Nathanson arXiv:2407.12253 §7