Small doubling and small tripling

DefinitionTao's small-doubling question (AIM Problem 3.5)#✓fully proved

The proposition that small doubling forces small tripling uniformly in all groups: there is a function \(f : \mathbb{R} \to \mathbb{R}\) such that for every group \(G\), every finite nonempty subset \(A \subseteq G\) and every real number \(K\), if \(|A \cdot A| \le K |A|\) then \(|A \cdot A \cdot A| \le f(K) |A|\). Here \(A \cdot A = \{ab : a, b \in A\}\) and \(A \cdot A \cdot A = \{abc : a, b, c \in A\}\).

def smallDoublingImpliesSmallTripling : Prop :=
  ∃ f : ℝ → ℝ, ∀ (G : Type) [Group G] [DecidableEq G] (A : Finset G) (K : ℝ), A.Nonempty →
    ((A * A).card : ℝ) ≤ K * A.card → ((A * A * A).card : ℝ) ≤ f K * A.card

Used by 1

Used bySmall doubling does not imply small tripling

TheoremSmall doubling does not imply small tripling#●ready to prove

There is no function \(f : \mathbb{R} \to \mathbb{R}\) such that for every group \(G\), every finite nonempty subset \(A \subseteq G\) and every real number \(K\) with \(|A \cdot A| \le K |A|\) one has \(|A \cdot A \cdot A| \le f(K) |A|\). Here \(A \cdot A = \{ab : a, b \in A\}\) and \(A \cdot A \cdot A = \{abc : a, b, c \in A\}\).

B. Green and M.-C. Chang pointed out the counterexample \(A = H \cup \{x\}\) with \(H\) a finite non-normal subgroup and \(x\) outside the normalizer of \(H\): then \(|A \cdot A|\) is comparable to \(|A|\), while \(|A \cdot A \cdot A|\) can be much larger.

public theorem_wanted smallDoublingImpliesSmallTripling_refuted :
    ¬ smallDoublingImpliesSmallTripling

Sources

• AIM workshop Recent trends in additive combinatorics (2004), problem list collected by E. Croot and V. F. Lev, https://aimath.org/WWN/additivecomb/additivecomb.pdf, Problem 3.5 (T. Tao) and Tao's comment; resolution: Tao's comment on Problem 3.5 in the AIM problem list (counterexample pointed out by B. Green and M.-C. Chang); T. Tao, Product set estimates for non-commutative groups, Combinatorica 28 (2008), 547-594, arXiv:math/0601431, comment to Problem 3.5: 'the problem as stated is false, as it follows by considering A = H ∪ {x} where H is a non-normal subgroup and x is not in the normalizer of H'; Tao's paper, Section 1 ('if A is the union of a subgroup and a point, then A · A will be small, but higher products such as A · A · A can be large') and Section 3 (A = H ∪ {x}, H a finite subgroup, x outside its normalizer: A² has size comparable to A, but A³ can be much larger), https://aimath.org/WWN/additivecomb/additivecomb.pdf.

Uses 1

Statement usesTao's small-doubling question (AIM Problem 3.5)

1 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.