Length functions on groups and actions on graphs

Abstract

We study generalizations of Chiswell’s theorem that 0-hyperbolic Lyndon length functions on groups always arise as based length functions of the group acting isometrically on a tree. We produce counter-examples to show that this Theorem fails if one replaces 0-hyperbolicity with δ-hyperbolicity. We then propose a set of axioms for the length function on a finitely generated group that ensures the function is bi-Lipschitz equivalent to a (or any) length function of the group acting on its Cayley graph with respect to some finite generating set.

KEYWORDS:

• Bi-Lipschitz equivalence
• Chiswell’s theorem
• group actions on graphs
• hyperbolicity
• Lyndon length functions

2020 MATHEMATICS SUBJECT CLASSIFICATION:

• 20E08
• 20F65
• 20F67

1 Introduction

One of the key insights of geometric group theory is that one can obtain information on a group by viewing it as a metric space, via the word metric on its Cayley graph. More generally if a group, G, acts isometrically on a metric space (X, d) one can elucidate properties of the group from this action. For instance, the class of hyperbolic groups is precisely the class of those groups admitting a proper, co-compact isometric action on some locally compact, geodesic δ-hyperbolic space X.

Given a (right) isometric action of G on (X, d), and a point p in X, one can define a G-invariant pseudo-metric—which we denote by d_p—on G via $d_p(g,h):=d(\mathit{pg},\mathit{ph})$, which is a metric precisely when the stabilizer of p is trivial. In fact, this metric on G can be encoded via the based length function.

Definition 1.1.

Let G act isometrically on the metric space (X, d). Then the based length function of G based at some point, $p\in X$ is the function, $l_p:G\to \mathbb{R}$, given by: $$l_p(g):=d(p,\mathit{pg})$$

It is straightforward to see that one can recover the invariant (pseudo) metric from the based length function via $d_p(g,h)=l_p(g{h}^{-1})$.

Of course, in order to obtain properties of the group it is helpful to impose conditions on the space and the action, just as for hyperbolicity above. A key area where one can recover a great deal of information about G is when X is a tree.

The source of inspiration for this paper is a striking result of Chiswell, that one can axiomatise the based length functions arising from actions on trees—sometimes called Lyndon length functions, following results from [6] - and, from the axioms, always recover an isometric action. Specifically,

Theorem 1.2.

[3] Suppose $l:G\to {\mathbb{R}}_{\ge 0}$ satisfies the following axioms:

A1: l(g) = 0 if g = 1

A2: $l(g^{-1})=l(g)$

A3: $c(g,h)\geqq 0$

H₀^:For all $g_1,g_2,g_3\in G$, and for all $0\le m\in \mathbb{Z}$ $c(g_1,g_2)\ge m,c(g_2,g_3)\ge m$ implies that $c(g_1,g_3)\ge m$,

where $$c(g,h):=\frac{1}{2}(l(g)+l(h)-l(g{h}^{-1})).$$

Then there exists an $\mathbb{R}$-tree, (X, d), admitting an isometric G-action and a point, $p\in X$, such that $l_p(g)=l(g)$. Moreover, if the images of l and c lie in $\mathbb{Z}$, then the tree will be simplicial.

Remark.

As noted above a function $d:G\times G\to \mathbb{R}$ can be defined from l and, from this point of view, A1’ says that d vanishes on the diagonal, A2 says that it is symmetric and A3 says that it satisfies the triangle inequality.

The function c(g, h) is then really the Gromov product and axiom H₀ should be thought of as a 0-hyperbolicity condition (see, for example, [1] for a discussion on hyperbolic groups, spaces and the Gromov product). Chiswell’s theorem can then be summarized as saying that a 0-hyperbolic Lyndon length function is always a based length function on a 0-hyperbolic space.

With this in mind, we are motivated to ask the following questions.

Questions.

• Is there a generalization of Chiswell’s theorem for isometric group actions on metric graphs?

• In particular, is there a generalization of Chiswell’s theorem for isometric actions on δ-hyperbolic graphs?

Remark.

In the spirit of Chiswell’s result, we will consider graphs whose edge lengths may not be integers. For instance, one could take the Cayley graph of a group with respect to some generating set, and then equivariantly assign positive real lengths to edges.

It turns out that these questions are somehow too broad in their scope. Given a (strictly positive) length function on G (see Definition 2.2 for the definition of a length function) there is always a metric graph whose based length function is equal to this function: take the complete graph on G where the edge between g and h has length $l(h{g}^{-1})$—Lemma 3.1. The based length function on this graph, with respect to the basepoint 1, is equal to l. However, this action is not particularly useful.

In order to rule out this kind of example we will add some restrictions.

Questions. Let us suppose that G is finitely generated and let us restrict ourselves to isometric, co-compact actions on locally compact graphs, X.

• Given a (strictly positive) length function, l, does G admit an isometric, co-compact action on a locally compact metric graph, X, such that l = l_p for some $p\in X$?

• What if we add the hypothesis that l is δ-hyperbolic (see Definition 2.2 for the definition of hyperbolicity)?

It turns out that the answer to both of these questions is no. By Proposition 3.4, there exists a δ-hyperbolic length function which cannot arise as the based length function associated to any isometric, co-compact action on a locally compact graph.

However, that example is bi-Lipschitz equivalent to a length function on a Cayley graph with respect to a finite generating set. (Note that, for a finitely generated groups, all based length functions on Cayley graphs with respect to finite generated sets are bi-Lipschitz equivalent). But one can also produce examples of δ-hyperbolic length functions which are not bi-Lipschitz equivalent to any based length function on a Cayley graph, as in Proposition 3.7. In fact, every finitely generated group admits a hyperbolic length function.

Theorem 3.8.

There exists a finitely generated group, G, with a hyperbolic length function, $l:G\to {\mathbb{R}}_{\ge 0}$ such that $l\ne l_p$ for any co-compact, metric G-graph.

Moreover, any finitely generated group admits a (free) hyperbolic length function. In particular, we can find an example of a group G with a hyperbolic length function, l, which is not quasi-isometric to any based length function arising from an isometric action of G on a geodesic and proper δ-hyperbolic metric space.

This leads us to the following.

Questions.

Suppose that G is finitely generated.

• Can one axiomatise those length functions which are bi-Lipschitz equivalent to some (and hence all) based length functions on a Cayley graph for G (with respect to a finite generating set)?

• Can we make these axioms apply to—for instance—any free F_n action on a simplicial tree as well as Cayley graphs?

• Does this axiomatisation define a connected/contractible/finite dimensional subspace of ${\mathbb{R}}^G$ on which $\text{Aut}(G)$ acts?

Remark.

We do come up with a axiom scheme, below, and we observe that these axioms hold for all sufficiently well behaved actions—see Proposition 4.1 and Corollary 4.2—and in particular to all points of Culler-Vogtmann space.

The third question here arises from the fact that one key use of Chiswell’s Theorem is in the study of group actions on trees, and the definition of the space of such actions which are then encoded via functions (usually the translation length function, which is related to the Lyndon length function). See [5] for the seminal paper on the ‘Outer Space’ of free actions on trees, encoded by length functions (amongst other things).

It is clear that the space of all length functions which are bi-Lipscitiz to one arising from a Cayley graph is a contractible space (because a linear combination of such functions is another such function). Therefore, this provides a contractible space on which $\text{Aut}(G)$ acts. However, it is far too large and so one might hope that an axiomatisation could provide a more reasonable subspace.

With these questions in mind, we propose the following axioms for our length functions:

Definition 4.3.

Let G be a group. We say that $l:G\to {\mathbb{R}}_{\ge 0}$ is a graph-like length function if it satisfies the following axioms:

A1:l(g) = 0 if and only if g = 1

A2:$l(g^{-1})=l(g)$

A3:$c(g,h)\geqq 0$

A4:For all $R\ge 0$, the closed ball $B_R:=\{g\in G|l(g)\le R\}$ is finite

A5:There exists $0\le ϵ<1$ and K > 0 such that, for any $g\in G$, if l(g) > K then there exists an $x\in G$ with:

1. $0<l(x)\le K$, and

2. $c(g{x}^{-1},x^{-1})\le \frac{ϵl(x)}{2}$.

Remark.

Here, the mysterious looking axiom A5 is encoding the fact that if one had a reasonable action on a graph, then one could approximate geodesics in the graph with uniform quasi-geodesics built from the translates of finitely many paths; it is morally a co-compactness condition expressed solely in terms of the length function. In fact, we prove that this axiom holds for a fairly wide class of actions in Proposition 4.1 and Corollary 4.2.

We also note that if G acts on its Cayley graph then one easily gets that the based length function satisfies these axioms with K = 1 and ϵ = 0. However, if once considers actions on graphs with more than one orbit of vertices, then one quickly discovers that the correct condition is A5(ii) with $ϵ\ne 0$. Moreover, scaling the graph by a constant clearly changes the value of K. For these reasons, to allow these kinds of deformations, we consider these axioms for more general K and ϵ.

It turns out that this is indeed sufficient to prove the following:

Theorem 4.8.

Let $l:G\to {\mathbb{R}}_{\ge 0}$ be a graph-like length function on a group G. Then l is bi-Lipschitz equivalent to some (and hence to all) based length function l_p arising from a locally compact, co-compact, metric G-graph with a properly discontinuous action and with $\text{Stab}(p)=1$.

Note that in view of Theorem 3.8, since any finitely generated group admits a hyperbolic length function, the extra axioms are clearly necessary.

Remark.

We should note that another length function one can extract from an action is the translation length function, which has the advantage of not relying on a basepoint. This is the point of view of [4]. An important result here, building on the work of [4], is that of [7] which states that a translation length function (which is 0-hyperbolic) always arises from an action on a tree. However, this builds crucially on Chiswell’s Theorem 1.2 so it seems reasonable to start with Lyndon length functions.

2 Preliminaries

We begin with some preliminary definitions and notation. Let G be a group.

Definition 2.1.

Given a metric, $d:G\times G\to {\mathbb{R}}_{\ge 0}$, on a group G we say that d is right-invariant if $d(g_{1}h,g_{2}h)=d(g_1,g_2)$ for all $g_1,g_2,h\in G$.

Definition 2.2.

A map $l:G\to {\mathbb{R}}_{\ge 0}$ which satisfies the following axioms is called a length function:

A1: l(g) = 0 if and only if g = 1

A2: $l(g^{-1})=l(g)$

A3: $c(g,h)\geqq 0$

where $$\begin{array}{c}c(g,h):=\frac{1}{2}(l(g)+l(h)-l(g{h}^{-1}))\hfill \end{array}$$ is the Gromov product of $g,h\in G$.

If, in addition, l satisfies

H ${}_{\delta }$: $c(g_1,g_2)\ge m,c(g_2,g_3)\ge m$ implies that $c(g_1,g_3)\ge m-\delta$ for some $\delta \ge 0$, we say it is a δ-hyperbolic length function. The condition $H_{\delta }$ is referred to as δ-hyperbolicity.

Remark.

Given a length function, it is easy to verify that $d(g,h):=l(g{h}^{-1})$ is a right-invariant metric on G. In particular, A3 is equivalent to the triangle inequality, which can be written as $$\begin{array}{c}l(g{h}^{-1})\mathit{\leqq l}(g)+l(h)\hfill \end{array}$$

Also note that here we write axiom A1: l(g) = 0 if and only if g = 1 rather than A1’: l(g) = 0 if g = 1. This is largely because we end up wanting to characterize those length functions which are bi-Lipschitz equivalent (or quasi-isometric) to those arising from Cayley graphs. We will sometimes emphasize this by saying that the length function is free.

Definition 2.3.

A metric graph is a 1-dimensional CW-complex with a metric structure. A metric tree is a metric graph in which any two vertices are connected by exactly one simple path. We always equip metric graphs with the path metric.

Definition 2.4.

By a metric G-graph, we mean a metric graph Γ together with an isometric right action of G on Γ, sending vertices to vertices and edges to edges.

Since we think of our graphs as metric spaces, given a point p in Γ, we may invoke Definition 1.1; $l_p(g)=d_{\Gamma }(p,p.g)$ is the based length function on Γ, based at p.

3 Hyperbolicity, length functions and counter-examples

Given a length function, l, as in Definition 2.2—that is to say, given a metric on G - one can always construct some metric graph on which G acts isometrically and such that l = l_p:

Lemma 3.1.

Let l be a length function on the group, G, as in Definition 2.2.

Let Γ be the complete graph on vertex set G, where the length of the edge between g and h is set to $l(g{h}^{-1})=l(h{g}^{-1})$. Then G acts isometrically on Γ and l is equal to the based length function on Γ - Definition 1.1—based at the vertex 1.

However, this is not a very useful object and we will want to insist on some finiteness conditions; namely, co-compactness and (usually) local compactness.

Since this work arose as an attempt to generalize the celebrated result of Chiswell, Theorem 1.2, it is a natural way to try to generalise that result by weakening 0-hyperbolicity to δ-hyperbolicity and instead only expecting the action to be on a (hyperbolic) graph. It turns out that this doesn’t work and we present two counter-examples, in Propositions 3.4 and 3.7.

Before presenting the first example, it is worthwhile observing some examples of hyperbolic length functions which do arise as the length function of a co-compact action on a graph. In these examples, we can take an existing length function and deform it slightly, but the following examples show that in doing so one might still end up with a length function arising from an action on a graph.

Examples 3.2.

For both of these examples, our group is the infinite cyclic group, $\mathbb{Z}$.

1. Given $0\le ϵ<1$, define:

   $\begin{array}{ccc}l(n)& =& \{\begin{array}{cc}1+ϵ& \text{if }n=\pm 1\\ \left|n\right|& \text{otherwise}\end{array}\end{array}$

   One can verify that this is the length function of the Cayley Graph of $\mathbb{Z}$, with respect to the generating set $\{1,2,3\}$ where 1 is given length $1+ϵ$, 2 is given length 2 and 3 is given length 3.

2. Again, given $0\le ϵ<1$, define:

   $\begin{array}{ccc}l(n)& =& \{\begin{array}{cc}0& \text{if }n=0\\ \left|n\right|+ϵ& \text{otherwise}\end{array}\end{array}$

   This is actually 0-hyperbolic, and arises from a non-minimal action on a tree. More precisely, take a graph with two vertices, u and v, and two edges, one of which is a loop of length 1 at v and the other is an edge of length $ϵ/2$ joining u to v. The fundamental group of that graph is $\mathbb{Z}$ and the action on the universal cover gives our length function (with respect to any lift of u).

Next we show how to deform the standard length function on $\mathbb{Z}$ so as to end up with something that does not arise from an action.

In order to proceed, we need the following observation:

Lemma 3.3.

Let Γ be a co-compact, metric G-graph and $p\in \Gamma$. Let $l_p(g)=d_{\Gamma }(p,p.g)$ denote the based length function. Then there exist finitely many positive real numbers, ${\alpha }_1,\dots ,{\alpha }_k$ such that, for any $g\in G,l_p(g)$ belongs to the submonoid of the (additive) real numbers generated by the α_i.

That is, for every g, there exist nonnegative integers n_i such that $l_p(g)=\sum n_i{\alpha }_i$.

Proof.

We simply let the α_i be the lengths of the edges in Γ. Since the action is isometric and there are finitely many edge-orbits, it suffices to take only finitely many of them. □

Now we are ready to show that a δ-hyperbolic length function need not come from an action on a graph.

Proposition 3.4.

For any $0\le ϵ<1$, the function $l_{ϵ}:\mathbb{Z}\to {\mathbb{R}}_{\ge 0}$ defined by $l_{ϵ}(n)=\left|n\right|+{ϵ}^{\left|n\right|}$, for $n\ne 0$ and $l(0)=0$ is a hyperbolic length function.

For $ϵ=1/2$, this cannot be equal to any based length function arising from a co-compact, isometric action of $\mathbb{Z}$ on a metric graph.

Proof.

First we verify axioms A1–A3 and H ${}_{\delta }$ from Definition 2.2. Note that for ϵ = 0, this is just the standard length function of $\mathbb{Z}$ acting on the line (which is 0-hyperbolic). For each $l_{ϵ}$ we define $c_{ϵ}$ to be the corresponding Gromov product. Note that both l₀ and c₀ take values in $\mathbb{Z}$.

Observe that A1 and A2 are clear for all ϵ directly from the definition. To verify A3, notice that $$l_0(n)\le l_{ϵ}(n)\le l_0(n)+ϵ,$$and hence that for any $n,m\in \mathbb{Z}$, $$c_{ϵ}(n,m)\ge c_0(n,m)-ϵ/2.$$

Therefore, since c₀ takes values in $\mathbb{Z}$, and $ϵ<1$, the only values for which $c_{ϵ}(n,m)$ could be negative would be those where $c_0(n,m)=0$. Since, for positive integers n, k we have that $c_0(n,n+k)=c_0(-n,-n-k)=n$, we see that $c_0(n,m)$ can only be zero if one of n, m is zero or if one is positive and one is negative. We calculate: if n, m are positive then $$c_{ϵ}(0,n)=c_{ϵ}(0,-n)=0$$and, $$c_{ϵ}(n,-m)={ϵ}^n+{ϵ}^m-{ϵ}^{n+m}>0.$$

This verifies A3. To verify H ${}_{\delta }$, note that the inequality $l_0(n)\le l_{ϵ}(n)\le l_0(n)+ϵ$ also gives us that $ϵ+c_0(n,m)\ge c_{ϵ}(n,m)$. Hence we get, for all n, m, $$ϵ+c_0(n,m)\ge c_{ϵ}(n,m)\ge c_0(n,m)-ϵ/2.$$

But since l₀ is 0-hyperbolic, this implies that $l_{ϵ}$ is $\frac{3\epsilon }{2}$-hyperbolic.

To see that $l_{1/2}$ cannot arise as the length function coming from a co-compact metric $\mathbb{Z}$-graph, we invoke Lemma 3.3 and argue by contradiction. That is, suppose that $l_{1/2}$ arises from the action of $\mathbb{Z}$ on a co-compact metric graph, Γ. Then, by Lemma 3.3, we have ${\alpha }_1,\dots ,{\alpha }_k$ such that for any $g\in G$, there exist positive integers, $n_1,\dots ,n_k$ with $l_{1/2}(g)={\sum }_{i=1}^k{n}_i{\alpha }_i$. We now show that this is not possible.

Without loss of generality, by enlarging the set, we may assume that ${\alpha }_1=1$. Further, again without loss of generality, we may assume that ${\alpha }_1,\dots ,{\alpha }_r$ is a maximal, $\mathbb{Q}$-linearly independent subset of the α_i. Thus for any j > r, α_j is a $\mathbb{Q}$-linear sum of ${\alpha }_1,\dots ,{\alpha }_r$. Fix such an expression for each j (in fact, it is unique) and notice that the denominators in the coefficients of these expressions are bounded. In particular, this means that any expression ${\sum }_{i=1}^k{n}_i{\alpha }_i$, where the n_i are integers can be re-written as an expression ${\sum }_{i=1}^r{q}_i{\alpha }_i$, where the q_i are now rational, but with bounded denominator. In particular, this means that there exists an integer, M, such that for any $g\in \mathbb{Z}$, there exists integers m_i such that, $$l_{1/2}(g)=\frac{1}{M}\sum _{i=1}^r{m}_i{\alpha }_i.$$

However, notice that $l_{1/2}(g)$ are rational for every g, and the set ${\alpha }_1,\dots ,{\alpha }_r$ are $\mathbb{Q}$-linearly independent. Hence the $\mathbb{Q}$-linear independence forces m_i = 0 for $i\ge 2$, and therefore, $$l_{1/2}(g)=\frac{1}{M}{m}_1{\alpha }_1=\frac{1}{M}{m}_1.$$

This is clearly impossible, since the values of $l_{1/2}$ do not belong to the additive cyclic subgroup generated by a rational number. □

Remark.

Note that the same proof shows that $l_{ϵ}$ cannot be equal to any length function arising from a co-compact, isometric action of $\mathbb{Z}$ on a metric graph for any rational ϵ.

The idea of Proposition 3.4 is that we started with a 0-hyperbolic length function (which is the standard length function of $\mathbb{Z}$ acting on its Cayley graph) and deformed it slightly to obtain a length function that is δ-hyperbolic but is not equal to any based length function coming from a co-compact graph. Naturally, since this is a small deformation we obtain a length function which is bi-Lipschitz equivalent to the original length function. We could also consider quasi-isometry.

Definition 3.5.

We say that two length functions l₁, l₂ on a group G are quasi-isometric if there exists $A\ge 1,B\ge 0$ such that, $\forall g\in G$, $$\frac{1}{A}{l}_1(g)-B\le l_2(g)\le A{l}_1(g)+B.$$

If, in addition, we can take B = 0, we say that l₁, l₂ are bi-Lipschitz equivalent.

We record a standard consequence of the Svarc-Milnor Lemma (see, for example, [2], I.8.19):

Lemma 3.6.

Let X, Y be co-compact, locally compact metric G-graphs. Then for all points $p\in X,q\in Y$ such that $\text{Stab}(p)=\text{Stab}(q)=1$, the based length functions l_p and l_q are bi-Lipschitz equivalent.

Instead of seeking length functions on G which are equal to the based length function of a suitable G-graph, we can instead seek $l:G\to {\mathbb{R}}_{\ge 0}$ which lies in the quasi-isometry class of a suitable G-graph, ideally a Cayley graph for G. Our aim is then to produce axioms for a length function that make it quasi-isometric, or bi-Lipschitz equivalent to a based length function on a Cayley graph.

Even here it turns out that hyperbolicity is not sufficient.

Proposition 3.7.

Let G be a finitely generated group and let $|.|:G\to \mathbb{R}$ be the word metric with respect to some finite generating set. Define a function, $l:G\to \mathbb{R}$ by $l(g):=\hspace{0.17em}\log \hspace{0.17em}(|g|+1)$. Then this is a δ-hyperbolic length function, for a uniform $\delta =\frac{1}{2}\log \hspace{0.17em}32$.

When $G=\mathbb{Z}$ then l is not quasi-isometric (and hence not bi-Lipschitz equivalent) to any based length function on a geodesic and proper hyperbolic space—for an isometric action of $\mathbb{Z}$.

Proof.

First we verify the axioms from Definition 2.2. We immediately see that l satisfies axioms A1 and A2. To see that A3 holds we observe that for all $g,h\in G,\left|g\right|+\left|h\right|\ge \left|g{h}^{-1}\right|$. Thus, Tuesday, December 19, 2023 at 6:47 pm $$\begin{array}{cc}\hspace{0.17em}\log \hspace{0.17em}(|g|+1)+\hspace{0.17em}\log \hspace{0.17em}(|h|=1)=\hspace{0.17em}\log \hspace{0.17em}((\left|g\right|+1)(\left|h\right|+1))\hfill & \hfill \\ =\hspace{0.17em}\log \hspace{0.17em}(|g\left|\right|h|+|g|+|h|+1)\hfill & \hfill \\ \ge \hspace{0.17em}\log \hspace{0.17em}(|g|+|h|+1)\hfill & \hfill \\ \ge \hspace{0.17em}\log \hspace{0.17em}(|g{h}^{-1}|+1)\hfill & \hfill \\ \Rightarrow c(g,h)=\frac{1}{2}(l(g)+l(h)-l(g{h}^{-1}))\ge 0\hfill & \hfill \end{array}$$

Thus l is a length function.

To see that the length function is δ-hyperbolic, consider the function, $$d(g,h):=e^{2c(g,h)}=\frac{(|g|+1)(|h|+1)}{\left|g{h}^{-1}\right|+1},g,h\in G.$$

It will be sufficient to show that there exists a $\delta \ge 0$ such that for any three group elements, g, h, k, and any $R\ge 0$, $$d(g,h)\ge e^{2R}\text{ and }d(h,k)\ge e^{2R}\Rightarrow d(g,k)\ge e^{2(R-\delta )}.$$

To do this, first observe the following two inequalities: (1) $$\left|g\right|\ge 2\left|h\right|\Rightarrow 2(|h|+1)\ge d(g,h)$$(1) (2) $$d(g,h)\ge \min \{\frac{\left|g\right|+1}{2},\frac{\left|h\right|+1}{2}\}.$$(2)

To see that 1 is true, simply observe that if $\left|g\right|\ge 2\left|h\right|$ then, $$\left|g{h}^{-1}\right|+1\ge \left|g\right|-\left|h\right|+1\ge \frac{\left|g\right|}{2}+1\ge \frac{\left|g\right|+1}{2},$$from which it follows that $2(|h|+1)\ge d(g,h)$.

To see that 2 is true, observe that if $\left|g\right|\ge \left|h\right|$ then, $\left|g{h}^{-1}\right|+1\le \left|g\right|+\left|h\right|+1\le 2(|g|+1)$, from which the desired inequality follows.

To verify that our length function is hyperbolic, let us suppose that we have a triple of group elements, g, h, k, and a real number, $R\ge 0$ such that $d(g,h)\ge e^{2R}\text{ and }d(h,k)\ge e^{2R}$.

Our aim is to find a (uniform) $\delta >0$ such that $d(g,k)\ge e^{2(R-\delta )}$.

We set $\Lambda =\max \left\{\right|g|,|h|,|k\left|\right\}$ and $\lambda =\min \left\{\right|g|,|h|,|k\left|\right\}$ the argument breaks into two cases now, depending on whether $\Lambda \ge 4\lambda$, or $\Lambda <4\lambda$.case(i): $\Lambda \ge 4\lambda$:

Without loss of generality, we will assume that $\left|g\right|\ge \left|k\right|$. In particular this implies, from Equation (2)(2) $$d(g,h)\ge \min \{\frac{\left|g\right|+1}{2},\frac{\left|h\right|+1}{2}\}.$$(2) , that $d(g,k)\ge \frac{\left|k\right|+1}{2}$.

Suppose first that $\left|h\right|\ge 2\left|k\right|$. Then from Equation (1)(1) $$\left|g\right|\ge 2\left|h\right|\Rightarrow 2(|h|+1)\ge d(g,h)$$(1) , $2(|k|+1)\ge d(h,k)$. Therefore, $$d(g,k)\ge \frac{\left|k\right|+1}{2}\ge \frac{d(h,k)}{4}\ge \frac{e^{2R}}{4},$$as required (with $\delta =\hspace{0.17em}\log \hspace{0.17em}(2)$). (We haven’t used the fact that $\Lambda \ge 4\lambda$ yet).

If instead we have that, $\left|h\right|<2\left|k\right|$ then we must get that $\left|g\right|>2\left|h\right|$, since $\Lambda \ge 4\lambda$.

Hence equations (1)(1) $$\left|g\right|\ge 2\left|h\right|\Rightarrow 2(|h|+1)\ge d(g,h)$$(1) , (2)(2) $$d(g,h)\ge \min \{\frac{\left|g\right|+1}{2},\frac{\left|h\right|+1}{2}\}.$$(2) give us that $$d(g,k)\ge \frac{\left|k\right|+1}{2}>\frac{\left|h\right|+1}{4}\ge \frac{d(g,h)}{8}\ge \frac{e^{2R}}{8},$$as required (here with $\delta =\frac{1}{2}\log \hspace{0.17em}(8)$).case(ii): $\Lambda <4\lambda$.

Here, we invoke the triangle inequality to get that: $$\left|g{k}^{-1}\right|+1\le 2\max \left\{\right|g{h}^{-1}|+1,|h{k}^{-1}|+1\}.$$

Without loss of generality, we assume that $\left|g{h}^{-1}\right|\ge \left|h{k}^{-1}\right|$. Then, $$d(g,k)\ge \frac{{(\lambda +1)}^2}{2(|g{h}^{-1}|+1)}>\frac{{(\Lambda +1)}^2}{32(|g{h}^{-1}|+1)}\ge \frac{d(g,h)}{32}\ge \frac{e^{2R}}{32}.$$

This completes the proof that our length function is δ-hyperbolic (with $\delta =\frac{1}{2}\log \hspace{0.17em}(32)$ as the final and maximal estimate).

To finish, note that if $\mathbb{Z}$ were to act isometrically on a locally compact hyperbolic space, X, with based length function l_p, then either l_p would have to be bounded, or quasi-isometric to a linear function. Since $\hspace{0.17em}\log \hspace{0.17em}(|n|+1)$ is neither, it is not quasi-isometric to such an l_p. □

Theorem 3.8.

There exists a finitely generated group, G, with a hyperbolic length function, $l:G\to {\mathbb{R}}_{\ge 0}$ such that $l\ne l_p$ for any co-compact, metric G-graph.

Moreover, any finitely generated group admits a (free) hyperbolic length function. In particular, we can find an example of a group G with a hyperbolic length function, l, which is not quasi-isometric to any based length function arising from an isometric action of G on a geodesic and proper δ-hyperbolic metric space.

Proof.

This is simply the content of Propositions 3.4 and 3.7. □

4 Axioms for graph-like length functions

We finally turn to positive results and produce an set of axioms that do result in length functions which are bi-Lipschitz equivalent to the based length function on a (or any) Cayley graph with respect to some finite generating set.

Before introducing our axioms, we would like to demonstrate that they are reasonable, to the extent that they arise naturally from group actions on fairly general yet well behaved spaces. So we consider the following, noting that the hypotheses on X are satisfied by a locally finite metric graph equipped with the path metric and a co-compact group action.

Proposition 4.1.

Let X be a geodesic metric space with a given basepoint, p. Suppose a group, G, acts on X isometrically, and co-boundedly. Then there exist constants, K > 0 and $0<{ϵ}_0\le 1$ such that for any $g\in G$ with $d(p,\mathit{pg})\ge K$, there exists an $x\in G$ such that:

• $0<d(p,\mathit{px})\le K$ and,

• ${ϵ}_{0}d(p,\mathit{px})+d(\mathit{px},\mathit{pg})\le d(p,\mathit{pg})$

Proof.

Recall that,

• X geodesic means that for any two points in X there exists an isometry from a closed real interval to X where the images of the endpoints are our given two points of X.

• The action is co-bounded means there is a closed ball whose G translates cover X.

Since the action is co-bounded, there exists a closed ball centered at p, of radius $K/3$ say, whose G translates cover X. Set $B=B_{K/3}(p)$ to be this ball.

Given $g\in G$ with $d(p,\mathit{pg})\ge K$, let $q\in X$ be the point on a geodesic from p to pg such that $d(p,q)=K/2$. Since q is on a geodesic we also have $d(p,\mathit{pg})=d(p,q)+d(q,\mathit{pg})$.

Now, since the translates of B cover X, there exists some $x\in G$ such that $q\in \mathit{Bx}$. This implies that $d(q,\mathit{px})\le K/3$.

First note that $d(p,\mathit{px})>0$ since, $$d(p,\mathit{px})\ge d(p,q)-d(\mathit{px},q)\ge K/2-K/3=K/6>0.$$

Next note that, $$d(p,\mathit{px})\le d(p,q)+d(q,\mathit{px})\le K/2+K/3=5K/6.$$and also, $$d(\mathit{px},\mathit{pg})\le d(\mathit{px},q)+d(q,\mathit{pg})\le K/3+(d(p,\mathit{pg})-K/2)=d(p,\mathit{pg})-K/6.$$

Putting these together we get that, $$\frac{1}{5}d(p,\mathit{px})+d(\mathit{px},\mathit{pg})\le K/6+(d(p,\mathit{pg})-K/6)=d(p,\mathit{pg}).$$

Hence we are done, with ${ϵ}_0=1/5$. □

Corollary 4.2.

With the same hypotheses as above, set:

• $l_p(g)=d(p,\mathit{pg})$ and,

• $c_p(g,h)=\frac{1}{2}(l_p(g)+l_p(h)-l_p(g{h}^{-1}))$.

Then there exists $0\le ϵ<1$ and K > 0 such that, for any $g\in G$, if $l_p(g)>K$ then there exists an $x\in G$ with:

1. $0<l_p(x)\le K$, and

2. $c_p(g{x}^{-1},x^{-1})\le \frac{ϵl_p(x)}{2}$.

Proof.

Just set $ϵ=1-{ϵ}_0$ from Proposition 4.1 since $$\begin{array}{cccc}{c}_p(g{x}^{-1},x^{-1})& \le & \frac{ϵl_p(x)}{2}& \iff \\ & & & \\ l_p(g{x}^{-1})+l_p(x)-l_p(g)& \le & ϵl_p(x)& \iff \\ & & & \\ (1-ϵ)l_p(x)+l_p(g{x}^{-1})& \le & l_p(g)& \end{array}$$and the last line is equivalent to the conclusion of Proposition 4.1 (where we have also used the fact that $l_p(w)=l_p(w^{-1})$ for all w which is just a consequence of the symmetry of the metric). □

The idea is that a fairly general class of spaces and actions satisfy the equation given by Corollary 4.2 and hence we will add this as a axiom for our length functions. Therefore, we propose the following.

Definition 4.3.

Let G be a group. We say that $l:G\to {\mathbb{R}}_{\ge 0}$ is a graph-like length function if it satisfies the following axioms:

A1: l(g) = 0 if and only if g = 1

A2:$l(g^{-1})=l(g)$

A3:$c(g,h)\geqq 0$

A4:For all $R\ge 0$, the closed ball $B_R:=\{g\in G|l(g)\le R\}$ is finite

A5:There exists $0\le ϵ<1$ and K > 0 such that, for any $g\in G$, if l(g) > K then there exists an $x\in G$ with:

1. $0<l(x)\le K$, and

2. $c(g{x}^{-1},x^{-1})\le \frac{ϵl(x)}{2}$.

Remark.

We note that A4 is really a statement about the action being properly discontinuous, especially in view of Proposition 4.7, which says that in the presence of A5, A4 is equivalent to the statement that B_K is finite.

A1:In view of Proposition 4.1 and Corollary 4.2 one should view A5 as a co-compactness condition; the challenge here was writing an axiom down which could be stated purely in terms of the length function.

As noted in the introduction, for a standard Cayley graph with respect to a finite generating set, its based length function will satisfy these axioms with K = 1 and ϵ = 0. The A5 condition with ϵ = 0 is effectively saying that for every $g\in G$, there is an x of length at most K, such that px lies on a geodesic from p to pg.

For an example of a group acting on a graph where $ϵ\ne 0$, consider the free group of rank 2, F₂, realized as the fundamental group of a graph with two vertices, u, v, and three edges: an edge-loop at u, E_u, an edge-loop at v, E_v, and an edge from u to v, E_uv. The action of F₂ on the universal cover, T, of this graph will induced a based length function which is graph-like, but not with ϵ = 0.

Namely, take a lift of, $\overline{u}$ of u, as the basepoint of T and consider the orbit of $\overline{u}$ under the group elements corresponding to elements of the fundamental group of the form $g_n=E_{uv}{E}_v^n{E}_{uv}{}^{-1}$, for $n\in \mathbb{Z}$. Then the geodesic from $\overline{u}$ to $\overline{u}{g}_n$ only meets the orbit of $\overline{u}$ at its endpoints. Hence this cannot satisfy the A5 condition with ϵ = 0 for any K.

In fact, it is straightforward to see that any free F_n action on a metric tree - that is, any point in Culler Vogtmann space—satisfies the axioms above, with K = 1 but not necessarily with ϵ = 0.

Let us start with the following preparatory results:

Lemma 4.4.

A length function satisfying A4 is discrete.

Proof.

Recall that we say a length function $l:G\to {\mathbb{R}}_{\ge 0}$ is discrete if there exists $\mu >0$ such that, for all nontrivial $g\in G,l(g)\ge \mu$.

If G = 1, then l is immediately discrete. Otherwise, take $\mu =\min \{R>0|B_R\ne 1\}$. Since A4 holds, this this minimum will be realized by some R > 0. □

Lemma 4.5.

Let l satisfy A5. Then for the g, x listed in A5, we have that: $$l(g{x}^{-1})\le l(g)-(1-ϵ)l(x).$$

Proof.

By A5, $$\begin{array}{cc}c(g{x}^{-1},x^{-1})\hfill & \le \frac{ϵl(x)}{2}\hfill \\ \Rightarrow \frac{1}{2}(l(g)+l(x)-l(g{x}^{-1}))\hfill & \le \frac{ϵl(x)}{2}\hfill \\ \Rightarrow l(g)+l(x)-l(g{x}^{-1})\hfill & \le \mathit{ϵl}(x)\hfill \\ \Rightarrow l(g{x}^{-1})\hfill & \le l(g)+(1-ϵ)l(x)\hfill \end{array}$$

□

Lemma 4.6.

The ball $B_K=\{g\in G|l(g)\le K\}$ is a generating set for G. In particular, by A4, G is finitely generated.

Proof.

We will show, by induction on n, that $〈B_K〉$ contains all group elements g with $$l(g)\le K+(1-ϵ)\mathit{n\mu }$$

(taking ϵ from Definition 4.3, A5, and μ from Lemma 4.4) and hence contains all of G.

Firstly, take $g\in G$ such that $l(g)\le K$. Then $g\in B_K\in 〈B_K〉$, and we are done.

Now assume that, for all $g\in G$ satisfying $l(g)\le K+(1-ϵ)(n-1)\mu$, g lies in $〈B_K〉$.

Take g such that $l(g)\le K+(1-ϵ)\mathit{n\mu }$. Then, by Lemma 4.5, there exists $x\in B_k$ such that $$\begin{array}{cccc}l(g{x}^{-1})\hfill & \le l(g)-(1-ϵ)l(x)\hfill & \hfill & \hfill \\ \hfill & \le K+(1-ϵ)\mathit{n\mu }-(1-ϵ)\mu \hfill & \hfill & \mathrm{(}\text{by properties of }g\text{and Lemma} 4.4)\hfill \\ \hfill & =K+(1-ϵ)(n-1)\mu \hfill & \hfill & \hfill \end{array}$$

Thus $g{x}^{-1}\in 〈B_K〉$, and since $x\in B_K$, this means that $g=g{x}^{-1}x\in 〈B_K〉$. □

Proposition 4.7.

Let $l:G\to {\mathbb{R}}_{\ge 0}$ satisfy A1, A2, A3 and A5. Let $K,ϵ$ be as in A5 and suppose that the ball $B_K=\{g\in G|l(g)\le K\}$ is finite. Then,

1. For any nontrivial $g\in G$, there exists a finite sequence, $x_0,\dots ,x_k$ such that:

   1. Each $0<l(x_i)\le K$ (i.e. each $x_i\in B_K\setminus \left\{1\right\}$),

   2. $l(g{x}_0{}^{-1}{x}_1{}^{-1}\dots x_k{}^{-1})=0$, and

   3. $(1-ϵ){\sum }_{i=0}^{k}l(x_i)\le l(g)\le {\sum }_{i=0}^{k}l(x_i)$.

2. Axiom A4 holds - that is to say, the ball B_R is finite for all $R\ge 0$.

Proof.

Part (a) is clearly true if $l(g)\le K$, since we can just take g = x₀. To prove it in general, we use the discreteness of the length function to argue by induction. More precisely, we let P_n be the statement that (a) holds for all g with $l(g)\le K+(1-ϵ)\mathit{n\mu }$. Thus our initial observation is that P₀ holds. We also observe that, since B_K is finite, there exists a minimum length, $\mu >0$, for elements in B_K.

Suppose then that $P_{n-1}$ holds and consider a $g\in G$ with $l(g)\le K+(1-ϵ)\mathit{n\mu }$. If $l(g)\le K$ then we are done, as above. Otherwise, by Lemma 4.5 and the existence of μ, there exists an $x\in G$ with $0<l(x)\le K$ and (3) $$l(g{x}^{-1})\le l(g)-(1-ϵ)l(x)\le K+(1-ϵ)(n-1)\mu .$$(3)

Now by the induction hypothesis applied to $g_0=g{x}^{-1}$ we can find $x_1,\dots ,x_k\in G$ such that

1. Each $0<l(x_i)\le K$

2. $l(g_0{x}_1{}^{-1}{x}_2{}^{-1}\dots x_k{}^{-1})=0$, and

3. $(1-ϵ){\sum }_{i=1}^{k}l(x_i)\le l(g_0)\le {\sum }_{i=1}^{k}l(x_i)$.

Now set x = x₀. Then, by Equation (3)(3) $$l(g{x}^{-1})\le l(g)-(1-ϵ)l(x)\le K+(1-ϵ)(n-1)\mu .$$(3) , we have that, $$(1-ϵ)\sum _{i=0}^{k}l(x_i)=(1-ϵ)l(x)+(1-ϵ)\sum _{i=1}^{k}l(x_i)\le (1-ϵ)l(x)+l(g_0)\le l(g).$$

Moreover, by A3, $$l(g)\le l(x)+l(g_0)\le \sum _{i=0}^{k}l(x_i).$$

Hence, by induction, (a) result holds for all g.

We now prove (b). Let $M\ge 0$, and let S_M denote the following set of finite sequences: $$S_M=\{x_0,\dots x_k\in B_K\setminus \{1\left\}\right|\sum _{i=1}^{k}l(x_i)\le M\}$$

Let $R\ge 0$, and let $g\in B_R$. Set $M_R=\frac{R}{(1-ϵ)}$.

By (a), there exists a sequence $x_0,\dots x_k\in S_{M_R}$ such that $g=x_k\dots x_0$. Therefore, if we can prove that $S_{M_R}$ is finite, we will prove that B_R is finite.

Recall that, for all $x\in B_K,l(x)\ge \mu$. Therefore, for all sequences in $S_{M_R}$, $$\frac{R}{(1-ϵ)}=M_R\ge \sum _{i=1}^{k}l(x_i)\ge \mathit{k\mu }\Rightarrow k\le \frac{R}{(1-ϵ)\mu }$$

Thus $S_{M_R}$ is a set of sequences of elements from the finite set B_K, and the length k of these sequences has an upper bound. Thus $S_{M_R}$ is finite, and we are done. □

Theorem 4.8.

Let $l:G\to {\mathbb{R}}_{\ge 0}$ be a graph-like length function on a group G. Then l is bi-Lipschitz equivalent to some (and hence to all) based length function l_p arising from a locally compact, co-compact, metric G-graph with a properly discontinuous action and with $\text{Stab}(p)=1$.

Proof.

We take Γ to be the Cayley graph on the set $B_K=\{g\in G|l(g)\le K\}$, but instead of assigning every edge length 1, we assign it the length of the corresponding generating element under l. That is, the vertex set of Γ is G, and we join two vertices, g, h by an edge if and only if $g{h}^{-1}=y\in B_K$; in that case we assign that edge a length of l(y). (Note that $h{g}^{-1}=y^{-1}$ will also be in B_K in that case and have the same length). Γ is then equipped with the path metric.

We then take the base point p to be the vertex corresponding to the identity. By Lemma 4.6, B_K is a finite generating set for G; hence Γ is well-defined and the action of G is co-compact.

We can immediately see that $0=l(1)=l_p(1)$, so we shall restrict our attention to nontrivial $g\in G$. For $g\in G$ we write, as always, $l_p(g)=d_{\Gamma }(p,p·g)$ to denote the based length induced by Γ. The metric on Γ is the path metric, and so the distance from p to pg is the infimum of the lengths of all edge paths from p to $p·g$. Thus for all $g\ne 1$, $$\begin{array}{cc}{l}_p(g)\hfill & =\inf \{\sum _{i=0}^k{l}_p(y_i)|y_0,\dots ,y_k\in B_K,y_k\dots y_0=g\}\hfill \\ \hfill & =\inf \{\sum _{i=0}^{k}l(y_i)|y_0,\dots ,y_k\in B_K,y_k\dots y_0=g\}\hfill \end{array}$$where the second equality arises from the fact that $l_p(y)=l(y)$ for all $y\in B_K$, as these are the edges of Γ.

By Proposition 4.7 (a), there exists a sequence $x_0,\dots ,x_k\in B_K$ such that $x_k\dots x_0=g$ and $\frac{1}{\lambda }{\sum }_{i=0}^{k}l(x_i)\le l(g)$, where $\lambda =\frac{1}{1-ϵ}$. Thus $\frac{1}{\lambda }{l}_p(g)\le l(g)$.

Conversely, by inductively applying A3, the triangle inequality, $l(g)\le {\sum }_{i=0}^{k}l(y_i)={\sum }_{i=0}^k{l}_p(y_i)$ for all sequences $y_0,\dots ,y_k\in B_K$ with $y_k\dots y_0=g$. Thus $l(g)\le l_p(g)$.

We have $\frac{1}{\lambda }{l}_p(g)\le l(g)\le$ $l_p(g)$, hence l_p is bi-Lipschitz equivalent to l with bi-Lipschitz constant $\lambda =\frac{1}{1-ϵ}$.

Therefore, by Corollary 3.6, l lies in the bi-Lipschitz equivalence class of all based length functions arising from free, locally compact, co-compact metric G-graphs. □

Remark.

A hyperbolic graph-like length function is a length function that satisfies the axioms from Definition 4.3 as well as the $H_{\delta }$ axiom from Definition 2.2 for some $\delta >0$.