Growth function of a discrete metric space (${\beta }_{X,x_0}$)

For a locally finite discrete metric space $X$ with basepoint $x_0$, its growth function isChanging the basepoint changes the argument by at most an additive constant. In a vertex-transitive metric space, including every Cayley graph, the growth function is exactly independent of the basepoint.

For a finitely generated group $G$ with finite generating set $S$, the growth function ${\beta }_{G,S}(r)$ is the number of group elements of word metric distance at most $r$ from the identity. Different finite generating sets change its scale only by multiplicative constants.

A finitely generated group has polynomial growth when, for some constants $C,D$, its growth function of a finitely generated group satisfiesThis property is independent of the finite generating set $S$.

For every $d>0$ there is $N(d)$ such that, if a group has a finite symmetric generating set $S$ containing the identity andfor some $n\ge N(d)$, then there are $H⊴C<G$ with $H\subseteq S^{\lfloor n/2\rfloor }$, $[G:C]=O_d(1)$, and $C/H$ nilpotent of class $O_d(1)$. A geometric-scale pigeonhole argument finds a large radius of small tripling, and the Breuillard-Green-Tao structure theorem for approximate groups supplies $H$ and $C$.

Every finitely generated group of polynomial growth of a group has a virtually nilpotent group structure. Applying the one-scale virtual nilpotence theorem gives a finite normal subgroup with nilpotent quotient; centralizing that finite subgroup produces a nilpotent subgroup of finite index.

Every finitely generated two-step nilpotent group has polynomial growth of a group. If $s_1,\dots ,s_k$ generate it, centrality of the commutators collects every word of length at most $n$ intowhere $|a_i|\le n$ and $|b_{ij}|=O(n^2)$. There are therefore only polynomially many possible collected words.

The matricesgenerate a free monoid in ${\mathrm{SL}}_2(\mathbb{Z})$. Hence the $2^n$ positive words of length $n$ are distinct and ${\mathrm{SL}}_2(\mathbb{Z})$ has exponential growth of a group.