Theorem 1.5 — gives one nonempty with for every finite
ProvedPlunneckeType.Abelian.theorem_1_5Let be a group, not necessarily commutative, and let and be finite subsets of with nonempty. Write for the product set and for cardinality. Let be a real number such that
Then there is a nonempty subset such that for every finite set
This is a variant of a theorem of Ruzsa on triple products . Its feature is that a single set serves all sets at once, which is what allows it to be iterated: taking to be a power of in an abelian group yields the Plünnecke–Ruzsa inequalities.
Formalization Note The paper's statement says only "there exists "; since every product with the empty set is empty, would satisfy it trivially. The paper's is a minimiser of the ratio , which is defined for nonempty , so the statement assumes nonempty and asserts nonempty. The order of the factors in is kept: multiplies on the left, on the right. Cardinalities are cast to ; is an arbitrary real number, as on the page.
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. 3, Theorem 1.5. In a (not necessarily commutative) group, if `|AB| ≤ α|A|`
then some nonempty `X ⊆ A` satisfies `|CXB| ≤ α|CX|` for every finite set `C`, with the same `X`
for all `C`. The paper's `X` minimises `|ZB|/|Z|` over the nonempty `Z ⊆ A`; without
`X.Nonempty` the statement would be satisfied by `X = ∅`. -/
theorem theorem_1_5 {G : Type*} [Group G] [DecidableEq G] (A B : Finset G) (α : ℝ)
(hA : A.Nonempty) (hAB : (#(A * B) : ℝ) ≤ α * #A) :
∃ X ⊆ A, X.Nonempty ∧ ∀ C : Finset G, (#(C * X * B) : ℝ) ≤ α * #(C * X) := by sorry
end PlunneckeType.Abelian
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.