Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 143 / 3

For a locally finite discrete metric space $(X,d)$ with basepoint $x_0$, the growth function of a discrete metric space isIn a Cayley graph, left multiplication by $g{x}_0^{-1}$ is a graph isometry carrying $x_0$ to any other vertex $g$. It therefore gives a bijection $B(x_0,r)\to B(g,r)$ for every $r$. Thus the growth function of a fixed Cayley graph is exactly independent of the basepoint.

Choose any finite generating set $T$ of the finitely generated group $H$. Starting from a finite generating set $S_0$ of $G$, setEvery $T$-word in $H$ of length at most $r$ is also an $S$-word in $G$ of length at most $r$. The inclusion of the corresponding word-metric balls is injective, so the growth function of a finitely generated group satisfies

A finitely generated group has polynomial growth of a group if its growth function is bounded above by $C(1+r{)}^D$ for some constants $C,D$.

Let $G$ be generated by $s_1,\dots ,s_k$. Since $G$ is a two-step nilpotent group, every group commutator $[s_i,s_j]$ is central. Commuting letters past one another therefore collects every word of length at most $n$ into the formThe generator exponents satisfy $|a_i|\le n$. At most $n(n-1)/2$ exchanges are needed during collection, so $|b_{ij}|\le n^2$ is a sufficient bound. With $m=k(k-1)/2$, the number of possible collected expressions is at mostRelations can only reduce this count. This proves the polynomial growth of a finitely generated two-step nilpotent group, so every finitely generated two-step nilpotent group has polynomial growth.

Consider the matricesTheir projective action on the positive real line isThese disjoint images give the monoid version of the ping-pong lemma: after removing a common initial letter, two different positive words act differently. Thus $A,B$ generate a free monoid. There are $2^n$ distinct positive words of length $n$, all lying in the radius-$n$ word ball for any generating set enlarged to contain $A,B$. Therefore the Exponential growth of SL2 of Z gives