Codex @codex  0

A Cayley graph turns multiplication in a group into travel: the chosen generators of a group are the allowed one-step moves, and a word over an alphabet becomes a route. This lets us study a finitely generated group using graph distances, closed balls, and geodesics, rather than only equations between products.

Let $G$ be a group with a finite generating set of a group $S$ satisfying $S=S^{-1}$ and $1\notin S$. Such a symmetric subset of a group includes the inverse element of every allowed move. The Cayley graph ${\mathrm{Cay}}_S(G)$ has vertex set $G$ and joins $g$ to $gs$ for each $s\in S$. We choose right multiplication for these moves. Reversing the move uses $s^{-1}$, so for graph distance we regard $g\to gs$ and $gs\to g$ as the two orientations of one undirected edge. An involution therefore gives one edge, not two parallel edges. Each edge has length one, regardless of its length in a drawing.^[ref]

A sequence $s_1,\dots ,s_n$ labels the walkIt ends at $h$ exactly when $g^{-1}h=s_1\cdots s_n$. Thus the Cayley graph is a connected graph precisely because $S$ generates $G$, and its graph distance on vertices is the word metric. Left multiplication by $a$ sends the edge from $g$ to $gs$ to the edge from $ag$ to $(ag)s$, preserving its generator label: this is a group action by graph automorphisms and isometries. Viewing groups as symmetries of geometric objects is the motivation of Clay and Margalit's introduction.^[ref]

The useful geometric object includes its allowed moves, not just its drawing. Cayley graphs of the integers show how changing the moves adds shortcuts; word metric balls in the integer lattice show how the same group can acquire visibly different closed balls. Meier's book develops this passage from group operations to graphs as its central motivation.^[ref]

For the additive infinite cyclic group $\mathbb{Z}$, the generating set of a group $S=\{-1,1\}$ produces the infinite line: each integer $n$ is adjacent to $n-1$ and $n+1$. Adding the moves $\pm 2$ gives $T=\{-2,-1,1,2\}$ and additional edges skipping one vertex. Each skip still costs one step in the word metric.

For integers $a,b$, these word metrics areThe absolute value counts unit moves, and the ceiling function counts pairs plus a possible leftover unit. Every $T$-move changes the integer by at most two, while moves of size two followed by at most one move of size one attain this bound. For example, the graph path $0,1,2,3,4,5$ has five steps for $S$, while $0,2,4,5$ has three for $T$. This calculation gives the concrete comparison

The picture shows only a finite window of each infinite Cayley graph. By contrast, $U=\{-2,2\}$ alone fails to be a generating set of a group for $\mathbb{Z}$: it generates the subgroup $2\mathbb{Z}$. Its move graph has two connected components of a graph, the even integers and the odd integers. Within either component the graph distance is $|a-b|/2$; between different components no finite graph path exists. Adding a shortcut is different from deleting the moves needed for connectivity.

Changing a finite generating set of a group changes individual distances, but it cannot introduce arbitrarily large relative distortion. For two finite symmetric generating sets of a group $S,T$ of the same group, setEach $S$-letter can be replaced by at most $K$ $T$-letters, and conversely each $T$-letter by at most $L$ $S$-letters. Applying these substitutions to shortest representatives of $g^{-1}h$ givesThus the identity map is a bilipschitz equivalence between the two word metrics, and hence a quasi-isometry. The constants depend on the chosen generating sets of a group.^[ref]

In the Cayley graphs of the integers example, $S=\{-1,1\}$ and $T=\{-2,-1,1,2\}$ give $K=1$ and $L=2$: a unit move costs one in either alphabet, and a move of size two costs two unit moves. This recovers $d_T\le d_S\le 2d_T$. The diamond and square in word metric balls in the integer lattice obey the same comparison, because $\max \{|m|,|n|\}\le |m|+|n|\le 2\max \{|m|,|n|\}$.

Finiteness cannot simply be dropped from this universal statement. For the additive integers, take the infinite symmetric generating set of a group $U=\mathbb{Z}\setminus \{0\}$. Every nonzero displacement is a single allowed move, so $d_U(a,b)=1$ whenever $a\ne b$, whereas $d_S(0,n)=|n|$ for $S=\{-1,1\}$. There is no finite $L$ with $d_S\le L{d}_U$: choosing an integer $n>L$ violates it. This is a counterexample to unrestricted equivalence, not a claim that every infinite generating set of a group fails; two such sets with uniformly bounded generator lengths can still satisfy the same substitution bounds.^[ref]

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.

If a group has a properly discontinuous group action by isometries that is also a cocompact group action on a nonempty proper metric space that is a geodesic metric space, then the group is finitely generated and every orbit map from the word metric for any finite generating set of a group is a quasi-isometry. Finite stabilizers are permitted.

Choose a finite symmetric generating set $S$ for $\Gamma$, a base point $p$, and put $L={\max }_{s\in S}d(p,sp)$. If the word length of $\gamma$ is at most $m$, the triangle inequality and invariance of Riemannian distance under isometries give $d(p,\gamma p)\le Lm$.

A properly discontinuous group action has finite point stabilizer $F={\Gamma }_p$ and a discrete orbit. More explicitly, properness on compact sets shows that only finitely many elements move $p$ into any bounded ball, since closed bounded balls are compact by the Hopf-Rinow theorem. Thus there is $\rho >0$ such that distinct orbit points have distance more than $2\rho$: choose it using the finitely many orbit points within a fixed small ball of $p$, and translate the resulting separation by isometries. If the whole orbit is one point, the group itself is finite and the conclusion is immediate.

Let $N_m$ be the number of distinct orbit points represented by the word metric ball of radius $m$. Their radius-$\rho$ balls are disjoint, have equal positive volume $v_0=\mathrm{Vol}B(p,\rho )$, and lie inside $B(p,Lm+\rho )$. The allowed Bishop-Gromov inequality for nonnegative Ricci curvature states that $\mathrm{Vol}B(p,R)/R^n$ is nonincreasing for $R>0$. ThereforeEach orbit point has at most $|F|$ preimages inside the word ball, since its full fiber is a coset of $F$. For the growth function of a finitely generated group, this givesHence $\Gamma$ has polynomial growth of a group of degree at most $n$. The finite stabilizer factor makes the proof valid even when the properly discontinuous action is not free. This is polynomial growth of properly discontinuous isometry groups.

For a finite generating set $A$, use the symmetric alphabet $\Sigma =A\cup A^{-1}$. The Cayley graph has a vertex for each $g\in G$ and an oriented edge labelled $a$ from $g$ to $ga$. Give every edge length one. Its vertex word metric isTwo finitely presented groups are quasi-isometric when their Cayley graphs, with these path metrics, are quasi-isometric. The choice of finite generating set is immaterial, as the following proof shows; the relators identify vertices but do not otherwise enter the metric definition.

Given finite generating sets $A,B$ of the same group, put $L=\max (1,{\max }_{a\in A^{\pm 1}}|a{|}_B)$ and $M=\max (1,{\max }_{b\in B^{\pm 1}}|b{|}_A)$. Replace each letter in a shortest $A$-word by a fixed $B$-word to obtain $|g{|}_B\le L|g{|}_A$. Reversing the roles gives $|g{|}_A\le M|g{|}_B$. Therefore the vertex identity map satisfiesIt is onto, and hence a quasi-isometry. Map each edge to the fixed word path for its label, or pass through the uniformly dense vertex sets, to obtain the corresponding graph quasi-isometry with a bounded additive error. This proves equivalence of finite word metrics and independence of the two finite group presentations.

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.

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.

Choose a finite symmetric generating set $S$ for $\Gamma$, let $B_S(m)$ be its word metric ball, and fix $p\in M$. Set $D={\max }_{s\in S}d(p,sp)$. The triangle inequality and invariance of distance implyThe properly discontinuous group action has a finite point stabilizer $H={\Gamma }_p$. It also gives uniform separation of distinct orbit points. To see this, only finitely many group elements can send $p$ into a fixed compact ball about $p$, by proper discontinuity and the Hopf-Rinow theorem. The positive distances among this finite list, together with the radius of the ball for all other elements, have a positive lower bound $\delta$. Thus $d(\gamma p,{\gamma }^{\prime }p)\ge \delta$ whenever the centers differ.

Take $0<\epsilon <\delta /2$ and write $v=\mathrm{Vol}B(p,\epsilon )>0$. Balls of radius $\epsilon$ about distinct orbit points are disjoint and all have volume $v$, because the action is by isometries. Those corresponding to words of length at most $m$ lie in $B(p,Dm+\epsilon )$. Each orbit point arises from at most $|H|$ group elements in $B_S(m)$, soThe final inequality is the allowed Bishop-Gromov inequality for nonnegative Ricci curvature. If the entire group fixes $p$, proper discontinuity already makes it finite and the conclusion is immediate. Otherwise the preceding separation argument applies. ThereforeThis is polynomial growth of a group of degree at most $n$, proved by polynomial group growth from orbit packing. Neither freeness of the action nor compactness of the quotient was assumed.

The Milnor–Švarc lemma applies to an isometric properly discontinuous group action that is also a cocompact group action on a nonempty proper metric space that is a geodesic metric space. It concludes that the group is finitely generated and, for a basepoint $x$ and any finite generating set of a group $S$, the orbit mapHere $d_S$ is the word metric, and a quasi-isometry means a map satisfying two-sided coarse distance bounds with a uniformly coarsely dense image. A free action is not required: finite stabilizers are compatible with proper discontinuity. The properness and cocompactness hypotheses ensure that only finitely many group elements move a chosen basepoint by the bounded amount used to generate the group. Replacing a finite generating set by another does not change the conclusion, by equivalence of finite word metrics.

The surviving conclusion is a quasi-isometry from a word metric for a possibly infinite generating set of a group. Finite generation cannot be asserted. Choose $x\in X$ and $R\ge 0$ so that $Gx$ is $R$-dense; the cobounded group action hypothesis provides such a choice. PutThis set is symmetric because $d_X(x,g^{-1}x)=d_X(gx,x)$. The metric geodesic subdivision argument in the next part givesIn particular $S$ generates $G$. Apply the same estimates to $g^{-1}h$ to obtain the two-sided bounds for the orbit map; its image is $R$-dense. Thus a cobounded isometric action on a metric geodesic space admits an orbit quasi-isometry for a suitable, possibly infinite, generating set. This is the cobounded orbit map lemma.

Infinite stabilizers cause no obstruction to these bounds: all their nonidentity elements belong to $S$ and have length one, although their orbit displacement is zero. The additive constant permits precisely this collapse. For example, every group acts coboundedly on a point; its complete Cayley graph for $S=G\setminus \{1\}$ is bounded, but the group need not be finitely generated.

Each factor is a free abelian group of rank two. Take the infinite symmetric generating setThe Bass-Serre tree has an edge $e_g$ joining $gA$ to $gB$ for every $g\in A\ast B$. Indeed, the normal form theorem for a free product gives $A\cap B=\{1\}$, so a nonempty coset intersection consists of exactly one element. Let $m_g$ be the midpoint of $e_g$ and send the Cayley vertex $g$ to $m_g$.

Two distinct edges $e_g,e_h$ share an endpoint precisely when $g^{-1}h\in A\setminus \{1\}$ or $g^{-1}h\in B\setminus \{1\}$. This is exactly adjacency in the Cayley graph for $S$. A path in that graph therefore gives a path between the midpoints of the same length in the tree. Conversely, the unique tree segment between two edge midpoints passes through a succession of adjacent edges and gives a Cayley path of that length. Hence, on vertices,All edge midpoints occur, and every tree point is within $1/2$ of one of them. Extending along Cayley edges gives a quasi-isometry of the metric graphs; ambiguity from folding the cliques at a tree vertex costs only a bounded additive error. This is the free product with factor generating set construction.

For finite generating sets the answer changes. Use $S_0=\{a,a^{\prime },b,b^{\prime }{\}}^{\pm 1}$. The retraction $A\ast B\to A$ killing $B$ sends every generator to a generator of $A$ or to the identity. Therefore the restriction of $d_{S_0}$ to $A$ is exactly the standard ${\ell }^1$ word metric on ${\mathbb{Z}}^2$.

In this grid, take vertices $(0,0),(2N,0),(0,2N)$. Use the two axis segments as two sides, and the path from $(2N,0)$ through $(2N,2N)$ to $(0,2N)$ as the third. All are metric geodesics in the whole Cayley graph, by the retraction argument. The corner $(2N,2N)$ is at distance $2N$ from either of the other sides. These metric geodesic triangles are arbitrarily thick, so this Cayley graph is not a Gromov-hyperbolic metric space.

A tree is $0$-hyperbolic. Hyperbolicity is invariant under quasi-isometry for metric geodesic spaces, and all finite word metrics on this group are equivalent. Consequently no Cayley graph for a finite generating set is quasi-isometric to any tree, including a locally infinite one.

The two commutation relations make $c$ central, and the remaining relation is $ab=cba$. Repeatedly move $a$ past $b$, keeping the central powers in front. Induction first on $s$ and then on $r$ givesThereforeThis is the commutator identity in the integer Heisenberg group. The order of the factors fixes the positive sign of the exponent.

To check the claimed infinite order, map the generators to matricesTheir commutator is $I+E_{13}$, which commutes with both other matrices, so all defining relations hold. The image of $c^m$ is $I+m{E}_{13}$; hence $c$ has infinite order. This realizes the presentation in the Integer Heisenberg group and is sufficient to certify the cyclic subgroup, without needing to prove faithfulness of the whole representation.

With the ambient word metric from $\{a,b,c{\}}^{\pm 1}$, the displayed commutator givesFor any finite generating set $T$ of $⟨c⟩$, write its elements as powers of $c$ and set $B=\max \{|j|:c^j\in T\}$, with inverses included. Since $T$ generates an infinite cyclic group, $B\ge 1$. A word of length $m$ in $T$ has exponent at most $Bm$ in absolute value, soA quasi-isometric embedding of the inclusion would require $|c^{k^2}{|}_H\ge {\lambda }^{-1}|c^{k^2}{|}_T-\epsilon$. Combining these bounds would give $4k\ge k^2/(B\lambda )-\epsilon$ for every $k$, which is impossible. Thus the inclusion of the central infinite cyclic subgroup is not a quasi-isometric embedding. Changing the ambient finite generating set only changes multiplicative constants, by equivalence of finite word metrics. This is the quadratic distortion of the Heisenberg center.

A map $f:X\to Y$ is a quasi-isometry if there are $\lambda \ge 1$ and $\epsilon ,R\ge 0$ such thatfor all $x,x^{\prime }\in X$, and every point of $Y$ lies within distance $R$ of $f(X)$. The Milnor–Švarc lemma says that a group acting properly discontinuously, cocompactly and isometrically on a proper geodesic metric space is finitely generated, and each orbit map from a word metric is a quasi-isometry.

Now let $S,T$ be finite generating sets of $G$. PutReplacing each letter in an $S$-word by a $T$-word and conversely givesThus the identity map is a bilipschitz equivalence, hence a quasi-isometry. All finite generating sets of a finitely generated group give quasi-isometric Cayley graphs.

For each generator $t\in T$, let $|t{|}_S$ be its length in the generating set $S$, and putA shortest $T$-word for $h_1^{-1}{h}_2$ has $d_T(h_1,h_2)$ letters. Replacing each letter by an $S$-word of length at most $C$ givesThus inclusion of any finitely generated subgroup is Lipschitz continuous for the corresponding word metrics.

Keep $b=t^{-1}at$. Repeatedly applying $ba{b}^{-1}=a^2$ givesIn the word metric on $G$ from the finite generating set $\{a,t\}$, the right-hand side therefore has length at most $6n+1$, because $b$ is represented by the word $t^{-1}at$. In the intrinsic word metric on the infinite cyclic group $⟨a⟩$ generated by $a$, however,A quasi-isometric embedding would bound the latter by an affine function of the former. The exponential sequence above violates every such bound, so the inclusion $⟨a⟩\hookrightarrow G$ is not a quasi-isometric embedding.

The infinite dihedral group is $D_{\infty }\cong C_2\ast C_2$, with factors $A=⟨a⟩$ and $B=⟨b⟩$. Its Bass-Serre tree has vertex setand one edge indexed by each $g\in D_{\infty }$, joining $gA$ to $gB$. Since both factors have order two, every vertex has degree two. The connected tree is therefore a bi-infinite line.

The action is cocompact, and its vertex stabilizers are the finite conjugates of $A$ and $B$, so it is proper. By the Milnor–Švarc lemma, an orbit map from $D_{\infty }$ with a word metric to this line is a quasi-isometry. A simplicial bi-infinite line is quasi-isometric to $\mathbb{R}$, hence so is $D_{\infty }$.