Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 149 / 1

The Plünnecke-Ruzsa inequality states that, for all nonnegative integers $m,n$,Here $mA$ is the iterated sumset of $m$ copies of $A$, with $0A=\{0\}$. In particular, $|mA|\le K^m|A|$.

The Noncommutative Ruzsa triangle inequality says that nonempty finite subsets $B,C,D$ of a group satisfyThe Ruzsa covering lemma says that if $|CD|\le K|D|$, then some $X\subseteq C$ with $|X|\le K$ satisfies

Now let $A$ be a symmetric subset of a group, so $A^{-1}=A$ and $1\in A$. Apply the triangle inequality with the middle set $A$ to obtain, for $m\ge 4$,The hypothesis therefore gives $|A^m|\le K|A^{m-1}|$. Starting from $|A^3|\le K|A|$ proves

In particular $|A^5|\le K^3|A|$. Apply the covering lemma to $C=A^4$ and $D=A$. There is $X\subseteq A^4$ with $|X|\le K^3$ such thatThe set $A^2$ is symmetric and contains the identity element, so this inclusion is exactly the covering condition showing that

Small doubling alone is insufficient in a noncommutative group. Let $H$ be a finite group, let $G=H\ast ⟨x⟩$ be its free product with an infinite cyclic group, and putThen $A$ is symmetric and $|A^2|\le 5|H|+4=O(|A|)$, while $A^3$ contains the double coset $HxH$. Distinct pairs $(h_1,h_2)\in H^2$ give distinct reduced words $h_{1}x{h}_2$, so $|HxH|=|H{|}^2$. Letting $|H|\to \infty$ proves the small doubling does not control tripling in a noncommutative group phenomenon.

By the Plünnecke-Ruzsa inequality,Apply the Ruzsa covering lemma to $3A$ and $A$. Since $A=-A$, there is a set $X\subseteq 3A$ with $|X|\le K^4$ such thatAdding $A$ and reusing this inclusion inductively gives

A sum of $m-2$ members of the fixed set $X$ depends only on the multiplicity of each member. The number of possible multiplicity vectors is at most $m^{|X|}$, and thereforeSince $|2A|\le K|A|\le K^m|A|$, it follows thatFor fixed $K$, this differs from the Plünnecke–Ruzsa bound $K^m|A|$ only by a polynomial factor in $m$, so both have the same leading exponential function factor $K^m$.

Choose a covering set $X$ of size at most $K$ such that $A^2\subseteq XA$, as allowed by the definition of an approximate group. Discard every $x\in X$ for which $xA$ does not meet $A^2$. Each remaining $x$ belongs to $A^2{A}^{-1}=A^3$, so $X\subseteq ⟨A⟩$. Induction givesBecause $A$ is symmetric and contains the identity, $⟨A⟩={\bigcup }_{m\ge 1}{A}^m$. Hence

We use the bounded-exponent finitely generated nilpotent group order bound. In an $s$-step nilpotent group, a subgroup generated by $k$ elements is generated in collected form by the simple group commutators in those generators of weights at most $s$. There are at mostsuch commutators. Every one has order at most $r$, soTaking $H=⟨A⟩$ now gives