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$.

A finitely generated group of isometries acting properly discontinuously on a complete connected $n$-dimensional Riemannian manifold with nonnegative Ricci curvature has polynomial growth of a group of degree at most $n$. Choose $\rho >0$ so distinct points of an orbit are separated by more than $2\rho$. Let $L$ be the largest displacement of the base point by a generator. The radius-$m$ word metric ball maps into the metric ball of radius $Lm$, with fibers of size the finite stabilizer $|{\Gamma }_p|$. Disjoint radius-$\rho$ balls around these orbit points have equal volume and fit inside the ball of radius $Lm+\rho$. The Bishop-Gromov inequality bounds their number by $(1+Lm/\rho {)}^n$, giving the displayed estimate.

For a compact connected Riemannian manifold with nonnegative Ricci curvature, its finitely generated fundamental group acts freely and properly discontinuously on the complete universal cover. The preceding polynomial growth of properly discontinuous isometry groups bound applies. The degree-one Hurewicz theorem identifies first integral homology with the abelianization of the fundamental group. If its free rank is $b_1(M)$, this group maps onto ${\mathbb{Z}}^{b_1(M)}$. Choosing lifts of a basis gives at least a constant times $m^{b_1(M)}$ distinct elements in a word ball of radius a constant times $m$. The upper bound of order $m^{\dim M}$ forces the displayed inequality.

A properly discontinuous group action by isometries of a finitely generated group on a complete $n$-dimensional Riemannian manifold of nonnegative Ricci curvature yields the displayed group growth bound. Distinct orbit points are uniformly separated, while a word of length $m$ moves a basepoint by at most $Dm$. Pack disjoint equal-volume small balls about the orbit points into $B(p,Dm+\epsilon )$ and apply the Bishop-Gromov inequality. A finite point stabilizer contributes its order to the bound; freeness is unnecessary.

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.