The Plünnecke–Petridis inequality
ProvedFamousTheorems.pluennecke_petridisThe Plünnecke–Petridis inequality. Let be finite subsets of an additive group such that minimises the ratio among its nonempty subsets, i.e. for all . Then for every finite set ,
This is Petridis's key lemma, which gave a short proof of the Plünnecke–Ruzsa inequality for sets with . Plünnecke's original proof used graph theory.
Formalization note. Mathlib's Finset.pluennecke_petridis_inequality_add (the additive form of Finset.pluennecke_petridis_inequality_mul), with pointwise sumsets.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
open scoped Pointwise
theorem pluennecke_petridis {G : Type*} [AddGroup G] [DecidableEq G] {A B : Finset G} (C : Finset G)
(hA : ∀ A' ⊆ A, (A + B).card * A'.card ≤ (A' + B).card * A.card) :
(C + A + B).card * A.card ≤ (A + B).card * (C + A).card := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Finset.pluennecke_petridis_inequality_add`. Proof here reduces to that Mathlib result.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.