Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 149 (Introduction to Approximate Groups)

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

Let $\pi :G\to G/[G,G]$ be the abelianization map. Its image $\pi (A)$ is again a $K$-approximate group. Apply the large-progression form of the Freiman-Green-Ruzsa theorem to $\pi (A)$. It gives a finite subgroup $H$, elements $x_1,\dots ,x_r$, and lengths $L_1,\dots ,L_r$, withand

The large lifted product from a coset progression applied to this progression givesBriefly, choose a section of $\pi$ on $\pi (A^6)$. Multiplication by that section is multiplicative up to $A^{12}\cap [G,G]$; lifting successively the subgroup part and each progression direction therefore places every element of $A^6\cap {\pi }^{-1}(HP)$ in the displayed product. The fiber-counting lemma for a quotient map gives $|A^6\cap {\pi }^{-1}(HP)|\ge \exp (-K^{O(1)})|A|$, which proves the estimate.

SetThe intersection of an approximate group power with a subgroup shows that each $A_i$ is a $K^{O(1)}$-approximate group contained in $A^{O(1)}$. The preimage of a cyclic subgroup of $G/[G,G]$ has step less than $s$. The same is true of the preimage of the finite subgroup $H$ because $G$ is a torsion-free group. Consequently each $⟨A_i⟩$ has step less than $s$, and the displayed estimate is the required conclusion.

WriteUnder the improved bounds allowed in the question, $r=O({\log }^{O(1)}(2K))$ andMoreover $AC\subseteq A^{O(1)}$, whose size is at most $K^{O(1)}|A|$ by the higher product bound for an approximate group. ThusThe Ruzsa covering lemma supplies $X\subseteq A$ of size at most $\exp (O({\log }^{O(1)}(2K)))$ such thatTaking the $B_i$ to be the factors in this last product giveswhere $k\le O({\log }^{O(1)}(2K))$ and every $B_i$ is a $K^{O(1)}$-approximate group in $A^{O(1)}$ generating a subgroup of step less than $s$.

We induct on the nilpotency class $s$. For $s=1$, the group is Abelian, so take $C_1=A$ and no $X_i$. For $s>1$, part (i) writeswith $X$ small and every $⟨B_i⟩$ of class at most $s-1$. Apply the induction hypothesis to each $B_i$. Since $B_i\subseteq A^{O(1)}$ and its approximation parameter is $K^{O(1)}$, all resulting small sets lie in $A^{O_s(1)}$, all their sizes are at mostand all resulting approximate groups lie in $A^{O_s(1)}$ and have approximation parameter $K^{O_s(1)}$. Their generated subgroups are abelian groups.

There are $O({\log }^{O(1)}(2K))$ factors at each of at most $s$ induction levels. Absorbing the resulting products of the bounds into the $O_s$ notation givesKeeping the factors in the order supplied by the induction yields the required product of the $X_i$ and $C_j$ containing $A$.

Use the product from part (ii). Move each selected element of each small set $X_i$ to the left, conjugating every approximate-group factor that it crosses. For each tuple $\mathbf{x}\in X_1\times \cdots \times X_m$, the corresponding part of the product is therefore contained inwhere every $D_{j,\mathbf{x}}$ is a conjugate subset of some $C_j$. Conjugation preserves cardinality, the approximation parameter, and the property that the generated subgroup is abelian. The conjugating elements belong to $A^{O_s(1)}$, so $D_{j,\mathbf{x}}\subseteq A^{O_s(1)}$ after enlarging the implicit constant.

The number of tuples is at mostThese translated products cover $A$, so one has size at least the reciprocal fraction of $|A|$. For that tuple, put $D_j=D_{j,\mathbf{x}}$. Thenwhere $q=n\le O_s({\log }^{O_s(1)}(2K))$, and each $D_j$ is a $K^{O_s(1)}$-approximate group generating an abelian subgroup.

Composition and inversion in the Affine group of the complex line areThe mapis therefore a surjective group homomorphism with kernelIts target is Abelian, so $[G,G]\subseteq N$. On the other hand, the stated computation givesFixing any $a\ne 1$ and varying $b$ produces every translation. Thus $N\subseteq [G,G]$, and hence

The Solymosi sum-product theorem over the complex numbers states that if finite $U,V,W\subseteq \mathbb{C}$ satisfy $U\ne \{0\}$ and $W\ne \{0\}$, then

Write $N=[G,G]$ and identify it with $(\mathbb{C},+)$ as in part (a). If every two members of $A$ commuted, then $⟨A⟩$ would be Abelian, contrary to hypothesis. Thus some commutator of two members of $A$ is a nonidentity translation in $A^4\cap N$. Consequently the translation-coordinate setcontains both zero and a nonzero element.

The identityshows that $T\pi (A)$ is contained in the translation coordinates of $A^6\cap N$, while $T+T$ is contained in those of $A^8\cap N$. The intersection of an approximate group power with a subgroup therefore givesApply the Solymosi sum-product theorem over the complex numbers with $U=V=T$ and $W=\pi (A)$. Since $1\in \pi (A)$, its hypotheses hold, andCancelling $|T{|}^2$ and absorbing the absolute constant proves

Choose one representative from $A$ above each point of $\pi (A)$ and collect them in $X$. Part (c) gives $|X|\le K^{O(1)}$. If $a\in A$ has the same image as $x\in X$, then $x^{-1}a\in A^2\cap N$, soThis is the required covering of $A$ by at most $K^{O(1)}$ left cosets of the abelian translation subgroup $N$.

The set $B=A^2\cap N$ is a $K^{O(1)}$-approximate group by the intersection of an approximate group power with a subgroup. Apply the Freiman-Green-Ruzsa theorem inside $N\cong (\mathbb{C},+)$. Because the additive group of the complex numbers is a torsion-free group, the finite subgroup part is trivial, so there is an abelian progression $P$ withSince $|B|\le |A^2|\le K|A|$, enlarging the implicit constant gives

Put $t=\lceil \sqrt{n}\rceil$ and consider the powerswhere $L$ is maximal subject to $5^{L+1}t\le n/20$. For $n$ sufficiently large in terms of $d$, one has $L+1\ge \frac{1}{3}{\log }_{5}n$. Since the successive growth ratios telescope,Thus one ratio is at most $n^{d/(L+1)}\le 5^{3d}$. For the corresponding $m=5^{i}t$,

Set $B=S^m$. Then $|B^3|\le O_d(1)|B|$, so the small-tripling argument from Question 1(b) makesan $O_d(1)$-approximate group. Apply the Breuillard-Green-Tao structure theorem for approximate groups. It gives subgroupssuch that$C/H$ is a nilpotent group of class $O_d(1)$, and $A$ is covered by $O_d(1)$ left cosets of $C$.

It remains to pass from a covering to an index bound. The ball $S^m\subseteq A$ meets only $O_d(1)$ vertices of the Schreier graph of $G/C$. If $G/C$ had more vertices, a simple path from $C$ would give more than that many distinct cosets within distance $O_d(1)$. Since $m\ge \sqrt{n}$ and $n$ is sufficiently large, this is impossible. Therefore

Apply part (a). The subgroup $H$ is finite because it lies in the finite set $S^{\lfloor n/2\rfloor }$. Conjugation gives a homomorphismIts kernel $C_0$ has finite index in $C$ and centralizes $H$. Since $C_{0}H/H$ is a subgroup of the $O_d(1)$-step nilpotent group $C/H$, it is itself nilpotent of class $O_d(1)$. Hencefor some $s=O_d(1)$. As $C_0$ centralizes $H$, one more group commutator vanishes, so ${\gamma }_{s+2}(C_0)=\{1\}$. Thus $C_0$ is nilpotent of class at most $s+1=O_d(1)$.

Both $[G:C]$ and $[C:C_0]$ are finite, soThis is the Gromov theorem on groups of polynomial growth in the form needed here.

The Cayley graph ${\mathrm{Cay}}_S(G)$ is a connected graph with $|G|$ vertices. A shortest path never repeats a vertex, so it has at most $|G|-1$ edges. Therefore

Fix $\epsilon >0$ and set $d=2/\epsilon$. Suppose, towards a contradiction, thatwhere $\lambda$ will absorb constants depending only on $\epsilon$. Put $n=\lfloor |G{|}^{\epsilon }\rfloor$. Once $\lambda$ is large enough, $n\ge N(d)$, $n<D$, andPart (a) yields $H⊴C<G$ with $[G:C]=O_{\epsilon }(1)$, $H\subseteq S^{\lfloor n/2\rfloor }$, and $C/H$ nilpotent of class $O_{\epsilon }(1)$.

The subgroup core ${\bigcap }_{g\in G}gC{g}^{-1}$ is normal in $G$ and has index at most $[G:C]!$. Since $G$ is a simple group, the core is either $\{1\}$ or $G$. In the first case $|G|\le [G:C]!=O_{\epsilon }(1)$, which is excluded by increasing $\lambda$. Hence the core is $G$, so $C=G$.

Now $H⊴G$. Since $n/2<D$, the ball $S^{\lfloor n/2\rfloor }$ is not all of $G$, so $H\ne G$. Simplicity gives $H=\{1\}$, and therefore $G=C/H$ is a nilpotent group. A nontrivial finite nilpotent group has nontrivial center of a group; simplicity would force that center to be all of $G$, making $G$ Abelian. This contradicts the assumption that $G$ is non-abelian. Consequently