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

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