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^2A^{-1}=A^3$, so $X\subseteq\langle A\rangle$. Induction gives
$$
A^m\subseteq X^{m-1}A.
$$
Because $A$ is symmetric and contains the identity, $\langle A\rangle=\bigcup_{m\geq1}A^m$. Hence
$$
\langle A\rangle=\langle X\rangle A.
$$

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 most
$$
k+k^2+\cdots+k^s\leq sk^s
$$
such commutators. Every one has order at most $r$, so
$$
|\langle X\rangle|\leq r^{s|X|^s}\leq r^{sK^s}.
$$
Taking $H=\langle A\rangle$ now gives
$$
\boxed{A\subseteq H,\qquad |H|\leq|\langle X\rangle|\,|A|
\leq r^{sK^s}|A|.}
$$

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/iii/paper-149/1/d/solution