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

Let $G$ be a finitely generated group whose word balls have cardinality at most $C(1+r{)}^d$, and let $K$ be a finitely generated infinite-index subgroup. Then $K$ has polynomial growth of a group of degree at most $d-1$. To prove this, let $S,T$ be finite generating sets of $G,K$, and bound the $S$-length of every $T$-generator by $M$. The infinite locally finite Schreier graph of left cosets of $K$ has at least $r+1$ vertices within radius $r$. Choose representatives $g_j$ of those cosets with $|g_j{|}_S\le r$. The sets $g_j{B}_T(r)$ are disjoint and lie in $B_S((M+1)r)$. Therefore $(r+1)|B_T(r)|\le C(1+(M+1)r{)}^d$, which gives the claimed bound. In particular an infinite-index finitely generated subgroup cannot occur if the right side would force its nonempty word balls to shrink to zero cardinality.

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 the following holds. Suppose a group $G$ has a finite symmetric generating set $S$ containing the identity, andThen there are subgroupswith $H\subseteq S^{\lfloor n/2\rfloor }$, bounded index of a subgroup $[G:C]=O_d(1)$, and nilpotent quotient group $C/H$ of class $O_d(1)$. In particular $H$ is finite. The containment allows $C=G$.^[ref]

A geometric-scale pigeonhole argument finds an intermediate word metric ball with bounded growth. The Breuillard-Green-Tao structure theorem for approximate groups then supplies the finite subgroup and the bounded-index nilpotent quotient.

For example, take a cyclic group of arbitrarily large prime order and $S=G$. The growth hypothesis holds, but every proper subgroup has index equal to that prime. Requiring a proper $C$ would therefore contradict an index bound depending only on $d$; choosing $C=G$ gives the valid nilpotent conclusion.

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.