Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 5 / 5

For a finite symmetric generating alphabet $\Sigma$, the growth function of a finitely generated group isIt counts distinct elements, not words. Relations affect which words coincide, while the resulting coarse growth type is independent of the finite generating set.

Let $f:G\to H$ be a quasi-isometry between the vertex word metrics, with constants $\lambda ,ϵ$. A quasi-isometry of the metric graphs can be rounded to vertices with only bounded changes of these constants. If $f(g)=f(g^{\prime })$, its lower distortion bound gives $d_G(g,g^{\prime })\le \lambda ϵ$. Thus every nonempty fibre has at most $M={\beta }_G(\lceil \lambda ϵ\rceil )$ elements, independently of its centre. Also $f(B_G(1,n))$ lies in the ball of radius $\lambda n+ϵ$ about $f(1)$. Left translation in $H$ preserves ball cardinalities, soApply the same argument to a quasi-inverse of a quasi-isometry to get the reverse comparison. Enlarging all constants to an integer $K$ gives the two inequalities required by the paper's $\lesssim$ relation, and therefore ${\beta }_G{\sim }_e{\beta }_H$. This proves quasi-isometry invariance of the stated growth class.

For the exponential upper bound, put $q=|\Sigma |$. Every element in the radius-$n$ ball has a representative of length at most $n$. Hencewhere the last inequality follows by comparison with the binomial expansion of $(q+1{)}^n$; it also holds for the empty alphabet of the trivial group. Thus every finitely generated group has at most exponential growth, with no finite-relator assumption needed.

Use the standard coordinate generators of ${\mathbb{Z}}^d$. Its word metric is the ${\ell }^1$ metric, so its radius-$r$ ball consists of integer points satisfying ${\sum }_i|x_i|\le r$. For $d\ge 1$ it contains the cube $|x_i|\le \lfloor r/d\rfloor$ and is contained in the cube $|x_i|\le r$. Thusand its growth is bounded above and below by constant multiples of $r^d$ for large $r$.

If ${\mathbb{Z}}^n$ and ${\mathbb{Z}}^m$ are quasi-isometric, part (i) gives equivalent growth functions of a finitely generated group. For positive $n>m$, the required comparison $r^n\lesssim r^m$ would bound a positive constant times $r^n$ by $O(r^m+r)$, impossible as $r\to \infty$. Interchanging $n,m$ rules out $m>n$. Hence $n=m$. Conversely, for equal dimensions the identity is an isometry with standard generators; changing finite generators preserves quasi-isometry by Q2(ii). ThereforeIf dimension zero is allowed, ${\mathbb{Z}}^0$ is bounded and cannot be quasi-isometric to an unbounded positive-dimensional lattice. This boundedness argument is needed because the additive linear term in ${\sim }_e$ makes constant and linear growth functions of a finitely generated group equivalent; growth equivalence alone would not distinguish dimensions zero and one.

The answer is exponential growth in the paper's coarse-equivalence sense. Here are direct upper and lower bounds, avoiding an unsupported appeal to distortion.

Represent the generators by affine maps of the real line: $y(t)=t+1$ and $x(t)=t/3$. Then $x^{-1}yx(t)=t+3=y^3(t)$, so the defining relator is respected. In particular $y$ has infinite order: its distinct integral powers have distinct translation images.

Given $k$ digits $d_j\in \{0,1,2\}$, define $m_0=0$, $m_{j+1}=3m_j+d_{j+1}$ and $W_0$ empty, $W_{j+1}=x^{-1}{W}_{j}x{y}^{d_{j+1}}$. Induction using the relation shows $W_j=y^{m_j}$ in the group. Each step increases word length by at most four, so $|W_k|\le 4k$. The digit strings yield precisely all integers $0\le m_k<3^k$, and their corresponding group elements are distinct. ThereforeFor the upper bound, in the four-letter symmetric alphabet $\{x,x^{-1},y,y^{-1}\}$ there are at most $4\cdot 3^{j-1}$ freely reduced words of length $j\ge 1$. Every element of the ball has such a representative, givingThese bounds prove the exponential growth of the ternary affine Baumslag-Solitar group and show $\beta {\sim }_e(n\mapsto 2^n)$, since positive exponential bases and constant rescalings of the argument give the same coarse class. This determines its growth under the convention of the question; it does not assert an exact cardinality formula for every radius.