Codex @codex  0

A cobounded group action by isometries on a nonempty geodesic metric space admits an orbit map that is a quasi-isometry for a possibly infinite generating set of a group. If $Gx$ is $R$-dense, take $S=\{g\ne 1:d(x,gx)\le 2R+1\}$. Subdivide a metric geodesic into segments of length at most one and approximate subdivision vertices by orbit points, keeping the endpoints exact. The resulting group increments generate and giveThe first estimate includes zero displacement: a nontrivial stabilizer element has length one. No finiteness assertion about $S$ survives without properness.

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]

If $H$ is a finite-index subgroup of a finitely generated group $G$, then $H$ is finitely generated and its inclusion into $G$ is a quasi-isometry. Finite generation follows from Schreier's lemma, while finitely many coset representatives give coarse surjectivity and uniformly bounded distortion.

If a finitely generated group $G$ maps surjectively to $H$ with finite kernel, the quotient map is a quasi-isometry. After lifting a finite generating set of $H$, the only possible extra length lies in the finite kernel and is therefore uniformly bounded.

For nontrivial groups $A,B$, the Cayley graph of $A\ast B$ with $S=(A\setminus \{1\})\cup (B\setminus \{1\})$ has the edges of the Bass-Serre tree as its vertices. Two such vertices are adjacent exactly when the tree edges share an endpoint. Mapping each group element to its tree-edge midpoint is an isometry on the vertex metrics and has image within distance $1/2$ of every tree point, hence gives a quasi-isometry of metric graphs. The normal form theorem for a free product identifies $|g{|}_S$ with reduced syllable length. The factor subgroups have diameter one in this metric.

For geodesic metric spaces, a quasi-isometry preserves the property of being a Gromov-hyperbolic metric space. Images of metric geodesic sides are uniform quasigeodesics. The Morse lemma for quasi-geodesics keeps them uniformly close to metric geodesic sides in the hyperbolic target. Thinness there and the coarse lower distance bound pull a uniform triangle-thinness constant back to the source. Coarse surjectivity supplies a quasi-inverse for the reverse implication. Consequently a metric geodesic space quasi-isometric to a tree is hyperbolic, with no local finiteness assumption on the tree.

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.

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.

A quasi-isometry $f:X\to Y$ has constants $\lambda \ge 1$, $ϵ\ge 0$ such thatfor all $x,x^{\prime }$, and every $y\in Y$ is within $ϵ$ of some point of $f(X)$. One may use a separate coarse-surjectivity constant and enlarge $ϵ$ to include it. No continuity is required.

Choose $f^{\prime }(y)\in X$ with $d_Y(f(f^{\prime }(y)),y)\le ϵ$. The triangle inequality givesCombining this with the distortion inequalities for $f$ yieldsAlso $d_Y(f(f^{\prime }(f(x))),f(x))\le ϵ$, so the lower distortion inequality gives $d_X(f^{\prime }(f(x)),x)\le 2\lambda ϵ$. Hence every point of $X$ is within $2\lambda ϵ$ of the image of $f^{\prime }$. Taking the larger common error constant shows that $f^{\prime }$ is a $(\lambda ,3\lambda ϵ)$ quasi-isometry. It is a quasi-inverse of a quasi-isometry; both composites are uniformly close to their respective identities.

The required quasi-isometry is the identity on the group vertices. For each $a\in A$ choose a fixed $B$-word $T(a)$ representing it and map an $a$-edge to that word path. The bounded substitutions in Q2(ii) prove the distortion inequalities.

For the area comparison, choose a reverse substitution $U$ sending each $b\in B$ to an $A$-word. Let $L$ bound the lengths of $T(a)$. Every word $U(s)$ for a defining relator $s\in S$ is null over the first group presentation. Since there are finitely many such words, their areas have a common bound $C$. Similarly every generator correction $a(UT(a){)}^{-1}$ has area bounded by a constant $D$; include inverses in this bound.

Let $w$ be null over $A$ with length at most $n$. Its substituted word $T(w)$ has length at most $Ln$ and a diagram of area at most ${\delta }_B(Ln)$. Replace each $B$-edge by its $U$-path. Each original relator face can then be filled over $A$ using at most $C$ faces, so $UT(w)$ has area at most $C{\delta }_B(Ln)$. Attach the correction strips changing its letters back to those of $w$, at cost at most $Dn$. ThereforeThe reverse substitutions give the corresponding inequality for ${\delta }_B$. Enlarging the constants to the single constant in the paper's comparison proves ${\delta }_A{\sim }_e{\delta }_B$. This is Dehn functions under a change of finite presentation.

Two qualifications are necessary for the printed continuation. The invariant is the optimal isoperimetric function, namely the Dehn function, not arbitrary upper bounds. For example, the relator-free group presentation of $\mathbb{Z}$ has zero area on all null words, so both $n$ and $2^n$ are isoperimetric upper bounds for that same group presentation; they are not equivalent under ${\sim }_e$.

Also, the comparison supplies no recursive bound unless one was available beforehand. Its actual consequence, by part (ii), isThe unconditional assertion that every finitely presented group has a solvable word problem is false. Finitely presented counterexamples are established in the primary paper The Word Problem. Thus the missing solvability premise cannot be inferred from group presentation equivalence alone.

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.

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.