Theorem 3.1 — in an abelian group, gives one nonempty with for all
ProvedPlunneckeType.Abelian.theorem_3_1Let be an abelian group, written additively, and let and be finite subsets of with nonempty. Write , and for let ( summands) be the iterated sumset, with . Let be a real number such that
Then there is a nonempty subset such that
This is Petridis's strengthening of Plünnecke's inequality: the subset does not depend on . Combined with Ruzsa's triangle inequality it yields the Plünnecke–Ruzsa bound .
Formalization Note The paper says "there exists "; would satisfy that trivially, while the paper's minimises , a ratio defined for nonempty . So the statement assumes nonempty and asserts nonempty. "For all " is read as every natural number ; the case is the true statement . is the -fold sumset h • B, not the dilate . The quantifiers are ; the weaker is Theorem 1.1 of the paper.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib open scoped Pointwise open Finset
namespace PlunneckeType.Abelian
/-- Petridis, *New proofs of Plünnecke-type estimates for product sets in groups*,
arXiv:1101.3507v3, p. 7, Theorem 3.1. In an abelian group, if `|A + B| ≤ α|A|` and `A` is
nonempty, then one nonempty `X ⊆ A` satisfies `|X + hB| ≤ α^h |X|` for every `h`, where
`hB = h • B` is the `h`-fold sumset (`0 • B = {0}`). The same `X` serves every `h`. Without
`X.Nonempty` the statement would be satisfied by `X = ∅`. -/
theorem theorem_3_1 {G : Type*} [AddCommGroup G] [DecidableEq G] (A B : Finset G) (α : ℝ)
(hA : A.Nonempty) (hAB : (#(A + B) : ℝ) ≤ α * #A) :
∃ X ⊆ A, X.Nonempty ∧ ∀ h : ℕ, (#(X + h • B) : ℝ) ≤ α ^ h * #X := by sorry
end PlunneckeType.Abelian
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.