Kneser's inequality for sumsets in finite abelian groups
Provedkneser_inequalityKneser's inequality (1953). Let and be nonempty finite subsets of a finite abelian group with
Then there exists a proper subgroup of with
where is the sumset. (The statement here is in -safe form: .)
This is the fundamental "stabilizer-corrected" strengthening of the Cauchy–Davenport theme: in a group with no nontrivial subgroups, such as , it recovers Cauchy–Davenport () — already proved on this platform. In general groups, the deficit in the sumset bound is exactly governed by the subgroup : the deeper Kneser's theorem states that when , one can take to be the stabilizer and then — the inequality proved here is the existential-subgroup half from which that follows.
The proof here follows the Dyson e-transform presentation of Nathanson (arXiv:2407.12253, Theorem 10): if all translates of stay in , the subgroup generated by fixes and serves as ; otherwise an e-transform strictly shrinks while preserving and only shrinking the sumset, and the induction hypothesis transfers the subgroup back.
Formalization Note The sumset is the pointwise Finset sum (open scoped Pointwise); the subgroup's size is Nat.card ↥H. Both nonemptiness hypotheses are necessary: with , no proper subgroup satisfies the conclusion, and without the cardinality hypothesis the inequality can force .
import Mathlib open scoped Pointwise
theorem kneser_inequality {G : Type*} [AddCommGroup G] [Fintype G] [DecidableEq G]
(A B : Finset G) (hA : A.Nonempty) (hB : B.Nonempty)
(hcard : A.card + B.card ≤ Fintype.card G) :
∃ H : AddSubgroup G, H ≠ ⊤ ∧ A.card + B.card ≤ (A + B).card + Nat.card H := by sorry