Proof of Theorem 3.1, inductive step — for a minimal-growth
ProvedPlunneckeType.Abelian.theorem_3_1_stepadditive-combinatoricsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1plunnecke-ruzsasumsets
Let be an abelian group, written additively, and let , be finite subsets of . For write ( summands) for the iterated sumset, with . Let be a real number with
and let be a nonempty subset of minimal growth under addition of :
Then for every integer
This is the inductive step in the proof of Theorem 3.1: applied for it gives with the same for every .
Formalization Note The minimality is stated cross-multiplied, , which avoids division. is the -fold sumset h • B (not the dilate ), and is natural-number subtraction, guarded by the hypothesis .
Preamble
import Mathlib open scoped Pointwise open Finset
Formal statement
namespace PlunneckeType.Abelian
/-- Petridis, arXiv:1101.3507v3, p. 7, proof of Theorem 3.1 (the inductive step). Let `A, B` be
finite sets in an abelian group with `|A + B| ≤ α|A|`, and let `X ⊆ A` be nonempty and minimise
`|Z + B|/|Z|` over the nonempty `Z ⊆ A` (stated cross-multiplied). Then for every `h ≥ 1`,
`|X + hB| ≤ α |X + (h - 1)B|`, where `hB = h • B` is the `h`-fold sumset. -/
theorem theorem_3_1_step {G : Type*} [AddCommGroup G] [DecidableEq G] (A B X : Finset G) (α : ℝ)
(hAB : (#(A + B) : ℝ) ≤ α * #A)
(hXA : X ⊆ A) (hX : X.Nonempty)
(hmin : ∀ Z ⊆ A, Z.Nonempty → (#(X + B) : ℝ) * #Z ≤ #(Z + B) * #X)
(h : ℕ) (hh : 1 ≤ h) :
(#(X + h • B) : ℝ) ≤ α * #(X + (h - 1) • B) := by sorry
end PlunneckeType.Abelian
Source
G. Petridis, New proofs of Plünnecke-type estimates for product sets in groups, arXiv:1101.3507v3, p. 7, proof of Theorem 3.1 (the display |X + hB| = |(h−1)B + X + B| ≤ α|X + (h−1)B|)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.