Theorem 1.6 — |BB| ≤ α|B| and |BbB| ≤ β|B| for all b ∈ B give |Bʰ| ≤ α^(8h−17)β^(h−2)|B| for h > 2
ProvedPlunneckeType.Tao.theorem_1_6This is an explicit form of a theorem of Tao on product sets in non-abelian groups.
Let be a group, not necessarily abelian, and let be a finite subset of . Write for the product set of finite sets , for the -fold product, for , and for the number of elements of . Let be real numbers and suppose that
Then for every integer ,
In words: a finite set with small doubling whose "two-sided translates" are all small has small -fold products for every , with a bound polynomial in and whose exponents are explicit. In an abelian group , so the second hypothesis is automatic; in a non-abelian group small doubling alone does not control , which is why the second hypothesis is needed.
Formalization Note is a natural number with ; under this hypothesis the exponents and are exact natural numbers (at the printed exponent would be negative, and the theorem does not claim that case). Cardinalities are cast to . There is no sign hypothesis on or : if is nonempty the hypotheses force , and if is empty both sides are . The group is an arbitrary Group, never a commutative one.
import Mathlib open scoped Pointwise open Finset
namespace PlunneckeType.Tao
/-- Petridis, arXiv:1101.3507v3, p. 4, Theorem 1.6 (an explicit form of Tao's theorem). Let `B`
be a finite set in a (not necessarily commutative) group with `|BB| ≤ α|B|` and `|BbB| ≤ β|B|` for
all `b ∈ B`. Then for every `h > 2`, `|Bʰ| ≤ α^(8h−17) β^(h−2) |B|`. The natural-number exponents
`8h − 17` and `h − 2` are exact because `h ≥ 3`. -/
theorem theorem_1_6 {G : Type*} [Group G] [DecidableEq G] (B : Finset G) (α β : ℝ)
(hBB : (#(B * B) : ℝ) ≤ α * #B)
(hBbB : ∀ b ∈ B, (#(B * {b} * B) : ℝ) ≤ β * #B)
(h : ℕ) (hh : 2 < h) :
(#(B ^ h) : ℝ) ≤ α ^ (8 * h - 17) * β ^ (h - 2) * #B := by sorry
end PlunneckeType.Tao
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.