Growth rate of a group

Remarks

The class of $\gamma_S$ does not depend on $S$. If $S'$ is another finite generating set, each element of $S'$ is a word of length at most some $C$ in $S$, so $\gamma_{S'}(n) \le \gamma_S(Cn)$. Hence the three types above do not depend on $S$.

Example: $G = \Z^2$ with $S = \set{(1, 0), (0, 1)}$. The elements of length at most $n$ are the $(a, b)$ with $\abs{a} + \abs{b} \le n$, so $\gamma_S(n) = 2n^2 + 2n + 1$, and $\Z^2$ has polynomial growth.

Example: the free group on $\set{a, b}$. There are $4 \cdot 3^{k-1}$ reduced words of length $k \ge 1$, so $\gamma_S(n) = 2 \cdot 3^n - 1$, and the growth is exponential.

Non-example: the additive group $\Q$ is not finitely generated, so the definition does not apply; with an infinite generating set the balls may be infinite.

Since $\gamma_S(m + n) \le \gamma_S(m) \gamma_S(n)$, the limit $\lim_{n \to \infty} \gamma_S(n)^{1/n}$ exists, and $G$ has exponential growth exactly when this limit is greater than $1$.