Regularity of quasigeodesics characterizes hyperbolicity

Abstract

We characterize hyperbolic groups in terms of quasigeodesics in the Cayley graph forming regular languages. We also obtain a quantitative characterization of hyperbolicity of geodesic metric spaces by the non-existence of certain local $(3,0)$-quasigeodesic loops. As an application, we make progress towards a question of Shapiro regarding groups admitting a uniquely geodesic Cayley graph.

1. Introduction

Hyperbolic groups were introduced by Gromov [14] and revolutionized the study of finitely generated groups. Arguably, their most remarkable feature is that hyperbolicity connects several, and at a first glance independent, areas of mathematics. Confirming this, there are several different characterizations of hyperbolicity—such as the geometric thin triangle condition [14], the dynamical characterization via convergence actions [3], surjectivity of the comparison map in bounded cohomology [11, 19, 20] and vanishing of $\ell^\infty$-cohomology [12], linear isoperimetric inequality [14], all asymptotic cones being $\mathbb{R}$-trees [14], and others [1, 4, 14, 15, 25, 27, 30].

Another significant feature of hyperbolic groups is that they present very strong algorithmic properties. Most notably, they have solvable isomorphism problem [6, 28], they are biautomatic [10] and so the word problem can be solved via finite state automata, and sets of their rational quasigeodesics form a regular language [16].

This last property will be a central focus in the article, and we call it rational regularity, or for short $\mathbb{Q}\mathbf{REG}$.

Definition 1.1. A finitely generated group G is $\mathbb{Q}\mathbf{REG}$ if for all rational $\lambda \geq 1$, real $\epsilon \geq 0$, and finite generating sets S, the $(\lambda, \epsilon)$-quasigeodesics in the Cayley graph $\Gamma(G,S)$ form a regular language.

As mentioned in [16], Holt and Rees prove that every word hyperbolic group is $\mathbb{Q}\mathbf{REG}$. It is natural to ask if this provides a characterization of hyperbolic groups, as was conjectured in [5, problem 1]. The main result of the article is the following.

Theorem 1.2. A finitely generated group is hyperbolic if and only if it is $\mathbb{Q}\mathbf{REG}$.

We remark that it is necessary to not consider only geodesics. In [18], Cannon proved that for any finite generating set the geodesics in a hyperbolic group form a regular language. However, this does not characterize hyperbolicity: Neumann and Shapiro [21, Propositions 4.1 and 4.4] prove that for any finite generating set the geodesics in an abelian group form a regular language.

In fact, we prove the following strong converse to the result of Holt and Rees.

Theorem 1.3. Let G be a finitely generated non-hyperbolic group. Then for all finite generating sets S and all $\lambda^\prime \gt 54$, the set of $(\lambda^\prime,0)$-quasigeodesics is not regular in $\Gamma(G,S)$.

Once this is proved, it is clear that non-hyperbolic groups can never be $\mathbb{Q}\mathbf{REG}$.

To prove Theorem 1.3, we need a strong quantitative characterization of hyperbolicity. It is known that a geodesic metric space is hyperbolic if and only if local quasigeodesics are global quasigeodesics [14, Proposition 7.2.E]. More precisely, the contrapositive can be stated as follows: a space is non-hyperbolic if and only if there exists a pair of constants $(\lambda, \epsilon)$, a sequence $L_n \rightarrow \infty$ and a sequence of L_n-locally $(\lambda,\epsilon)$-quasigeodesic paths which are not global $(\lambda^\prime,\epsilon^\prime)$-quasigeodesics for any uniform choice of constants $(\lambda^\prime,\epsilon^\prime)$. Hence, a priori, to check for hyperbolicity, one would want to consider all choices of $(\lambda, \epsilon)$ and all choices of locally $(\lambda,\epsilon)$-quasigeodesic paths. We get around this using a criterion of Hume and Mackay [17] that essentially states that one needs only consider L-locally $(18,0)$-quasigeodesic loops whose length is comparable to L. To prove Theorem 1.3, we use such a sequence of loops to contradict the pumping lemma.

One of the limitations of the criterion of Hume and Mackay is that it only works for graphs, as it relies on Papasoglu’s bigon criterion [25], which is false for general geodesic metric spaces. We remark that a version of the bigon criterion for general metric spaces appeared in the master’s thesis of Pomroy [26], a proof can be found in [4, Appendix]. We develop a characterization of hyperbolicity, analogous to Hume and Mackay, that works for all geodesic metric spaces and does not rely on any bigon criteria.

Theorem 1.4. A geodesic metric space X is not hyperbolic if and only if there exists a sequence $L_n \rightarrow \infty$ and a sequence of non-constant L_n-locally $(3,0)$-quasigeodesic loops γ_n that satisfy $\ell(\gamma_n) \leq K L_n$, where K is some constant that does not depend on n.

Note that requiring that the loops are non-constant implies that $\operatorname{diam} (\gamma_n)$ diverges to infinity. Indeed, $(3,0)$-quasigeodesics are injective and for γ_n to be a loop we must have that $[0,L_n]$ is a proper subset of the domain. Therefore, morally, Theorem 1.4 states that in a non-hyperbolic group there are paths that are very well-behaved locally, but globally are loops of increasing size, hence cannot be global quasi-geodesics for any choice of constants.

Although striking, the presence of a sharp gap in the behaviour of local-quasigeodesics is not surprising. For instance, it is known that the Dehn function of a finitely presented group has a gap. A deep theorem of Wenger [31], extending results of [2, 14, 22, 24], shows that if the isoperimetric function satisfies $D(x) \leq \frac{1-\epsilon}{4\pi}x^2$, then it is in fact linear.

Our strategy in proving Theorem 1.4 relies on the study of asymptotic cones of metric spaces. If X is non-hyperbolic, then there is an asymptotic cone that is not a tree [15, 2.A], and it contains a simple loop. By using a series of approximations, we exploit this loop to produce a family of loops of controlled length that are locally $(3,0)$-quasigeodesic.

1.1. A question of Shapiro

A natural class of graphs to consider is the class of geodetic graphs. A connected graph is called geodetic if for any pair of vertices there is exactly one geodesic connecting them. In [29], Shapiro asked when a group admits a (locally finite) geodetic Cayley graph. He conjectures that such a group needs to be plain, that is, a free product where the factors are either free or finite. In [23], Papasoglu proved that a geodetic hyperbolic group is virtually free. It is still open whether all geodetic groups are hyperbolic, and whether all geodetic virtually free groups are plain.

We provide an answer to the first implication under an additional, language theoretic, assumption.

Theorem 1.5. Let G be a finitely generated group with a generating set S such that $\Gamma(G, S)$ is geodetic. If there exists λ > 3 such that the language of $(\lambda, 0)$-quasigeodesics is regular, then G is hyperbolic and hence virtually free.

1.2. Structure of the article

In §2, we give the necessary background on Cayley graphs, hyperbolic metric spaces, quasigeodesics, languages, automata, and asymptotic cones. In §3, we provide proofs of the results from §1. More specifically, in §3.1, we prove Theorem 1.4 and compare it to [17, Proposition 1.5], in §3.2, we prove Theorems 1.2 and 1.3, and in §3.3, we prove Theorem 1.5.

2. Background

2.1. Cayley graphs, hyperbolicity, and quasigeodesics

Let G be a finitely generated group with generating set S. We denote by $\Gamma(G,S)$ the Cayley graph of G with respect to S, that is, the graph with vertices G and edges $\{g,gs\}$ where $g\in G$ and $s\in S$. We denote by ${\lvert g \rvert}$ the word-length of g with respect to S; equivalently, this is equal to $d_{\Gamma(G,S)}(e,g)$.

Let $\delta\geq 1$. A metric space X is δ-hyperbolic if every geodesic triangle in X is δ-thin. Here a geodesic triangle is δ-thin if every edge is contained in the δ-neighbourhood of the two other edges. We say a finitely generated group G is hyperbolic if the Cayley graph $\Gamma(G,S)$ is a δ-hyperbolic metric space for some finite generating set S.

Let $\lambda\geq1$ and $\epsilon\geq0$. Given metric spaces X and Y, a $(\lambda,\epsilon)$-quasi-isometric embedding $f\colon X\to Y$ is a function satisfying

\begin{align*} \frac{1}{\lambda} d_X(x,y) - \epsilon \leq d_Y(f(x),f(y)) \leq \lambda d_X(x,y) + \epsilon \end{align*}

for all $x,y \in X$.

Definition 2.1. In the context of a Cayley graph $\Gamma(G,S)$, by a $(\lambda,\epsilon)$-quasigeodesic of length $a \in {\mathbb N}$, we mean a simplicial path $c: [0,a] \rightarrow \Gamma(G,S)$ such that for any two integers $x,y \in [0,a]$ we have

\begin{align*} d_{[0,a]}(x,y) \leq \lambda d_G(c(x),c(y)) + \epsilon. \end{align*}

Equivalently, a $(\lambda,\epsilon)$-quasigeodesic is a finite word w on the alphabet $S \cup S^{-1}$ for which $\textrm{length}(u) \leq \lambda d_G(e,u) + \epsilon$ for all subwords of u of w.

Definition 2.2. In the context of an arbitrary metric space X, a $(\lambda,\epsilon)$-quasigeodesic of length a > 0 in X is a quasiisometric embedding $c\colon [0,a]\to X$.

Given a path $c\colon [0,a]\to \Gamma(G,S)$ or $c\colon [0,a]\to X$, we say that c is an L-locally $(\lambda,\epsilon)$-quasigeodesic or an $(L,\lambda,\epsilon)$-local-quasigeodesic if c restricted to each subset of $[0,a]$ of length L is a $(\lambda,\epsilon)$-quasigeodesic. We say c is a $(L, \lambda,\epsilon)$-quasigeodesic loop if, in addition, $c(0)=c(a)$. We denote the length of a path c by $\ell(c)$.

2.2. Regular languages and automata

The following definitions are standard and may be found in [10, chapter 1]. Given a finite set A, let $A^*$ be the free monoid generated by A, i.e. the set of finite words that can be written with letters in A. A language over the alphabet A is a subset $L\subseteq A^*$. A finite state automaton (FSA) $\mathcal{M}$ over the alphabet A consists a finite oriented graph $\Gamma(\mathcal{M})$, together with an edge label function $\ell\colon E(\Gamma(\mathcal{M})) \to A$, a chosen vertex $q_I \in V(\Gamma(\mathcal{M}))$ called the initial state and subset $Q_F \subset V(\Gamma(\mathcal{M}))$ of final states. The vertices of $\Gamma(\mathcal{M})$ are often referred to as states.

Let ${\mathcal{M}}$ be an FSA over an alphabet A. We say a string $w\in L$ is accepted by A if and only if there is an oriented path γ in $\Gamma(\mathcal{M})$ starting from q_I and ending in a vertex $q \in Q_F$ such that γ is labelled by w. A language L is regular if and only if there exists an FSA ${\mathcal{M}}$ such that L coincides with the strings of $A^*$ accepted by ${\mathcal{M}}$.

Let G be a group generated by a finite set S. An element $w \in (S \cup S^{-1})^\ast$ labels a path in $\Gamma(G,S)$ which starts at e. We say w is a geodesic/ $(\lambda,\epsilon)$-quasigeodesic/ $(L,\lambda,\epsilon)$-local-quasigeodesic word if it labels a path in $\Gamma(G,S)$ with the corresponding property.

We say that the set $L^{(\lambda,\epsilon)}$ of $(\lambda,\epsilon)$-quasigeodesic words w over $S \cup S^{-1}$ form the $(\lambda,\epsilon)$-quasigeodesic language of G over S.

2.3. Asymptotic cones

In this section, we will give the necessary background on asymptotic cones. These concepts and definitions will only be needed for the proof of Theorem 1.4 in §3.1. The idea of an asymptotic cone first appeared in the proof of Gromov’s Polynomial Growth Theorem [13]; however, it was first formalized by Wilkie and van den Dries [32].

An ultrafilter ω on $\mathbb{N}$ is a set of nonempty subsets of $\mathbb{N}$ which is closed under finite intersection, upwards-closed, and if given any subset $X\subseteq\mathbb{N}$, contains either X or $\mathbb{N}\backslash X$. We say ω is non-principal if ω contains no finite sets. We may equivalently view a non-principal ultrafilter ω as a finitely additive measure on the class $2^{\mathbb{N}}$ of subsets of $\mathbb{N}$ such that each subset has measure equal to 0 or 1, and all finite sets have measure 0. If some statement P(n) holds for all $n\in X$ where $X\in\omega$, then we say that P(n) holds ω-almost surely.

Let ω be a non-principal ultrafilter on $\mathbb{N}$ and let X be a metric space. If $(x_n)_{n\in\mathbb{N}}$ is a sequence of points in X, then a point x satisfying for every ϵ > 0 that $\{n\ |\ d(x_n,x)\leq\epsilon\}\in\omega$ is called an ω-limit of x_n and denoted by $\lim_\omega x_n$. Given a bounded sequence $x_n \in X$, there always exists a unique ultralimit $\lim_\omega x_n$.

Let ω be a non-principal ultrafilter on $\mathbb{N}$. Let $(X_n,d_n)_{n\in\mathbb{N}}$ be a sequence of metric spaces with specified base-points $p_n\in X_n$. Say a sequence $(y_n)_{n\in\mathbb{N}}$ is admissible if the sequence $(d_{X_n}(p_n,y_n))_{n\in \mathbb{N}}$ is bounded. Given admissible sequences $x=(x_n)$ and $y=(y_n)$, the sequence $(d_{X_n}(x_n,y_n))$ is bounded and we define $\hat d_\infty(x,y) := \lim_\omega d_n(x_n,y_n)$. Denote the set of admissible sequences by ${\mathcal{X}}$. For $x,y\in{\mathcal{X}}$ define an equivalence relation by $x\sim y$ if $\hat d_\infty(x,y)=0$. The ultralimit of $(X_n,p_n)$ with respect to ω is the metric space $(X_\infty,d_\infty)$, where $X_\infty={\mathcal{X}}/\sim$ and for $[x],[y]\in X_\infty$ we set $d_\infty([x],[y])=\hat d_\infty(x,y)$. Given an admissible sequence of elements $x_n \in X_n$, we define their ultralimit in $X_\infty$ to be $\lim_\omega x_n := [(x_n)]$. Given a sequence of subsets $A_n \subset X_n$, we can define their ultralimit in $X_\infty$ to be the set $\lim_\omega(A_n) := \{{[(x_n)]} \mid x_n\in A_n\}$, where we only consider admissible sequences $(x_n)$.

Let ω be a non-principal ultrafilter on $\mathbb{N}$ and let $(\mu_n)$ be a diverging, non-decreasing sequence. Let (X, d) be a metric space and consider the sequence of metric spaces $X_n=\left(X,\frac{1}{\mu_n}d\right)$ for $n\in\mathbb{N}$ with basepoints $(p_n)$. The ω-ultralimit of the sequence $(X_n,p_n)$ is called the asymptotic cone of X with respect to ω, $(\mu_n)$, and $(p_n)$ and denoted $\textrm{Cone}_\omega(X,(\mu_n),(p_n))$. If the sequence of basepoints is constant, then we denote the asymptotic cone by $\textrm{Cone}_\omega(X,(\mu_n))$. In the case of a finitely generated group, we always assume that the basepoint is the identity.

The following is [8, Proposition 3.29(c)] which we will use in the proof of Theorem 1.4.

Proposition 2.3. Consider a non-principal ultrafilter ω on ${\mathbb N}$ and a sequence of metric spaces $(X_n, d_n)$ with basepoints $p_n \in X_n$. Suppose there exists a simple geodesic triangle in $(X_\infty, d_\infty)$. Then there exists a (possibly different) simple geodesic triangle Δ in $X_\infty$, a constant $k \geq 2$, and a sequence of simple geodesic k-gons P_n in X_n such that $\lim_\omega(P_n) = \Delta$.

3. Proofs of the results

3.1. A characterization of hyperbolic geodesic metric spaces

In this section, we prove Theorem 1.4, and this is a version of a result of Hume and Mackay [17, Proposition 5.1] for arbitrary metric spaces.

Definition 3.1. Let X be a metric space and consider the following condition:

(⋆)\begin{align} \begin{aligned} &\mathrm{There~exists~an~increasing~sequence~of~positive~numbers~}L_n \rightarrow \infty\\ &\mathrm{and~a~pair~of~constants~} K, \lambda \geq 1\mathrm{~such~that~for~every~}n\mathrm{~there~exists~a}\\ &\mathrm{non}\text{-}\mathrm{constant~}L_n\text{-}\mathrm{locally~}(\lambda,0)\text{-}\mathrm{quasigeodesic~loop~} \gamma_n\mathrm{~in~}X\mathrm{~with~}\ell(\gamma_n) \leq KL_n. \end{aligned} \end{align}

At times, it is convenient to specify the values of the constants K and λ. In that case we say that a metric space X satisfies (⋆) with constants $(K, \lambda)$.

Proposition 3.2. If a metric space X satisfies (⋆), then X is not hyperbolic.

Proof. If X is hyperbolic then it satisfies the local-to-global property for quasigeodesics: for every choice of $\lambda, \epsilon$, there exist constants $L = L(\lambda, \epsilon)$, $\lambda^\prime = \lambda^\prime(\lambda, \epsilon)$, and $\epsilon^\prime = \epsilon^\prime(\lambda, \epsilon)$ such that every L-locally $(\lambda, \epsilon)$-quasigeodesic is a global $(\lambda^\prime,\epsilon^\prime)$-quasigeodesic.

Suppose X satisfies the local-to-global property for quasigeodesics and X satisfies (⋆) with constants $(K, \lambda)$. Let $L = L(\lambda, 0)$ be the constant given by the local-to-global property. Choose $n \in \mathbb{N}$ such that $L_n \geq L$. Then γ_n is an L-locally $(\lambda, 0)$-quasigeodesic. However, γ_n is a loop and so cannot be a $(\lambda^\prime, \epsilon^\prime)$-quasigeodesic for any choice of $\lambda^\prime,\epsilon^\prime$.

Proposition 3.3. If X is a non-hyperbolic geodesic metric space, then there exists a constant $K \geq 1$ such that X satisfies (⋆) with constants $(K,3)$.

Proof. Since X is not hyperbolic, there exists an ultrafilter ω and a non-decreasing scaling sequence µ_n such that $\mathrm{Cone}_\omega(X, (\mu_n))$ is not a real tree. In particular, there exists a simple geodesic triangle $\Delta \subseteq \mathrm{Cone}_\omega(X, (\mu_n))$. Using Proposition 2.3, up to replacing Δ with another simple geodesic triangle, we obtain that $\Delta = \lim_\omega (P_n)$, where each P_n is a geodesic k-gon in X for some k. Let $z_n^1, \ldots, z_n^k$ be the vertices of P_n, where the labels are taken respecting the cyclic order on P_n. From now on, we always consider the indices mod k. Denote by $e_n^{i}$ the geodesic segment connecting $z_n^i, z_n^{i+1}$, that is the appropriate restriction of P_n.

Consider the points $z_\omega^i = (z_n^i)\in \Delta$, and let $e_\omega^i = \lim_\omega(e_i)$. It is a standard argument to show that $e^i_\omega$ are geodesic segments whose endpoints are $z_\omega^i$, see for instance [7, lemma 10.48, exercise 10.71]. Since $\lim_\omega(P_n) = \Delta$, we have $e^i_\omega \subseteq \Delta$. Since there are only k edges, for any ρ > 1, ω-almost surely we have

(3.2)\begin{equation} \ell(e_n^i)\leq \rho \mu_n \ell(e_\omega^i). \end{equation}

In particular, ω-almost surely we have $\ell(P_n) \leq \rho \mu_n \ell(\Delta)$, that is to say that the length of the polygons P_n is bounded above by a linear function of µ_n. Our goal is to modify the polygons P_n to obtain loops that are $(c\mu_n)$-locally $(3, 0)$-quasigeodesics for some c > 0, and whose lengths are comparable to those of the P_n.

To this end, we restrict our attention to only some edges of P_n. We say that an index $1 \leq i \leq k$ is active if $e_\omega^i \neq \{z_\omega^i\}$. Let $i_1 \leq \cdots \leq i_d$ be the active indices. From now on, we will only consider edges with active indices, and thus we rename $e_\omega^{i_j}$ as $a_\omega^j$ and $e_n^{i_j}$ as $a_n^j$. Thus, $a_\omega^1, \ldots, a_\omega^d$ is a subdivision of the triangle Δ into a geodesic d-gon. Since Δ is simple and its edges are compact, we have that there exists a δ > 0 such that for all edges $a_\omega^{i}$ and points $x\in a_\omega^{i}$ we have

\begin{align*} \max \{d(x, a_\omega^{i-1}), d(x, a_\omega^{i+1})\} \geq \delta. \end{align*}

For any active edge $a_n^i$ and $x\in a_n^i$, ω-almost surely we have

(3.3)\begin{equation} \max \{d(x, a_n^{i-1}), d(x, a_n^{i+1})\} \geq \delta\rho^{-1} \mu_n. \end{equation}

Further, since the terminal vertex of $a_\omega^i$ and the initial vertex of $a_\omega^{i+1}$ coincide, ω-almost surely we have

(3.4)\begin{equation} d(a_n^i, a_n^{i+1}) \leq \frac{1}{2} \delta \rho^{-1} \mu_n. \end{equation}

The intuitive idea is now as follows. For infinitely many n, we have a collection of geodesic segments ( $a_n^j$) whose length keeps increasing (3.2) and such that we have some control on the distance between them (3.3) and (3.4). Using this, we can connect the segments to obtain loops of controlled length which are locally quasigeodesics.

More formally, fix n such that (3.2), (3.3), and (3.4) are satisfied and orient the $a_n^j$ with the orientation of P_n that agrees with the numbering. Let $L_n = \frac{1}{2}\delta\rho^{-1} \mu_n$. From now on, we will drop the subscript n and denote, for instance, $L_n = L$. Let q ¹ be the first point of a ¹ such that $d(q^1, a^2) \leq L$. By the continuity of the distance function and the choice of q ¹, we see that $d(q^1,a^2)= L$.

Let p ² be a point in a ² such that $d(q^1,p^2)=L$. Therefore, we see that $d(p^2,a^3)\geq \delta\rho^{-1} \mu_n \gt L$. Let q ² be the first point in a ² after p ² such that $d(q^2,a^3)\leq L$. Again, we have $d(q^2,a^3)= L$, and let $p^3\in a^3$ be a point such that $d(q^2, p^3)= L$. We iterate this procedure until we obtain a point $q^d \in a^d$ and a point $p^1\in a^1$ such that $d(q^d, p^1) = L$.

We claim that $d(p^j, q^j)\geq L$. Indeed, since $d(p^j, a^{j-1})\leq L$, Eq. (3.3) implies $d(p^j, a^{j+1})\geq \delta\rho^{-1} \mu_n = 2L$, and the result follows from the triangle inequality.

From now on, we denote by $[p^j, q^j]$ the restriction of a^j between $p^j, q^j$, and we choose once and for all geodesic segments $[q^j, p^{j+1}]$ connecting $q^j, p^{j+1}$. Let $\gamma_n = \gamma$ be the concatenation

\begin{align*} \gamma = [p^1, q^1] \ast [q^1, p^2] \ast \cdots \ast [q^d, p^1], \end{align*}

where we consider γ to be parameterized by arc length. We will show that γ is a $(L; 3, 0)$-local quasigeodesic.

Let $x,y$ be two points of γ of parameterized distance less than L. We denote by $d_\gamma(x,y)$ the parameter distance. We will prove that $d_\gamma(x,y)\leq 3 d(x,y)$. If a and b are contained in the same segment of γ, then the inequality clearly holds. Thus, we can assume that x and y are on two consecutive segments of γ since the length of each segment of γ is at least L.

Firstly, consider the case $x\in [p^j, q^j]$, $y\in [q^j, p^{j+1}]$. If $x = q^j$, then we would be in the previous case, so $x\neq q^{j}$. We claim $d(x,y) \gt d(q^j,y)$. If not, this would contradict the choice of q^j as the first point at distance L from $a^{j+1}$. Indeed, $d(x,y)\leq d(q^j,y)$ implies $d(x,p^{j+1})\leq d(q^j,p^{j+1})$. Therefore, $d(x,y) \gt d(q^j,y)$. In particular:

\begin{align*} d_\gamma(x,y)=d(x,q^j)+d(q^j,y)\leq \bigl(d(x,y)+d(y,q^j)\bigr)+d(q^j,y)\leq 3 d(x,y). \end{align*}

Consider now the case $x\in [q^{j-1}, p^j]$ and $y\in [p^j, q^j]$. Since $d(q^{j-1},a^j)=d(q^{j-1},p^j)$, we have $d(x,y)\geq d(x,p^j)$. Hence

\begin{align*} d_\gamma(x,y)=d(x,p^j)+d(p^j,y)\leq d(x,p^j)+\bigl(d(p^j,x)+d(x,y)\bigr)\leq 3 d(x,y). \end{align*}

Thus, γ is a $(L;3,0)$-local quasigeodesic, where $L= L_n = \frac{1}{2}\delta\rho^{-1} \mu_n$. To conclude the proposition, we need to bound the length of γ linearly in terms of µ_n. However, observe that $d(q^j, p^{j+1}) = L$ for all j and $d(p^j, q^j) \leq \ell(a^j_n) \leq \rho \mu_n \ell (a^j_\infty)$. Setting $M= \max \ell(a^j_\infty)$, we obtain

\begin{align*} \ell(\gamma)\leq d\left(\frac{1}{2}\delta\rho^{-1} \mu_n + \rho M \mu_n\right) = d\left(\frac{1}{2}\delta\rho^{-1} + \rho M\right) \mu_n. \end{align*}

Theorem 1.4. A geodesic metric space X is not hyperbolic if and only if there exists a sequence $L_n \rightarrow \infty$ and a sequence of non-constant L_n-locally $(3,0)$-quasigeodesic loops γ_n that satisfy $\ell(\gamma_n) \leq K L_n$, where K is some constant that does not depend on n.

Proof. One direction is given by Proposition 3.3 and the other by Proposition 3.2.

In [17], by an 18-bilipschitz embedded cyclic subgraph in X, Hume and Mackay mean an injective graph homomorphism $\phi: C_n \rightarrow X$ of the circular graph C_n into the graph X such that $d_{C_n}(x,y) \leq 18 d_{X}(\phi(x),\phi(y))$ for all vertices $x,y \in C_n$. We now compare our results above to the following proposition of Hume and Mackay.

Proposition 3.4. ([17], Proposition 5.1)

Let X be a connected graph. X is hyperbolic if and only if there is some N such that every 18-bilipschitz embedded cyclic subgraph in X has length at most N.

From this, we obtain a version of Theorem 3.3 with different constants. Notably in Hume and Mackay’s result, we obtain a good multiplicative constant but a relatively large additive constant, whereas in our result, Theorem 3.3, the size of the constants is reversed.

Corollary 3.5. Let K > 2. If G is a non-hyperbolic group, then for any finite generating set S, the Cayley graph $\Gamma(G,S)$ satisfies (⋆) with constants $(K, 18)$.

Proof. Proposition 3.4 tells us that there exists an increasing sequence of natural numbers $l_n \rightarrow \infty$ and a sequence of 18-bilipschitz embedded cyclic subgraphs in $\Gamma(G,S)$ of length l_n. We may write these cyclic subgraphs as injective graph homomorphisms $\phi_n : C_{l_n} \rightarrow \Gamma(G,S)$. If $L_n = \lfloor l_n/2 \rfloor$ then any subpath in $C_{l_n}$ of length L_n is a geodesic. So $C_{l_n}$ is L_n-locally $(1,0)$-quasigeodesic, from which it follows that its image in $\Gamma(G,S)$ is L_n-locally $(18,0)$-quasigeodesic. For l_n sufficiently large we have $l_n \leq KL_n$, and by passing to a subsequence if necessary, we may assume that $L_n \rightarrow \infty$ is an increasing sequence. The result follows.

3.2. Regularity

Proposition 3.6. Suppose $\Gamma(G,S)$ is a Cayley graph that satisfies (⋆) with constants $(K,\lambda)$. Then for all $\lambda^\prime \gt (2K - 1)\lambda$, the set of $(\lambda^\prime,0)$-quasigeodesics does not form a regular language.

Proof. To prove the proposition, we will show that any automata accepting the language of $(\lambda^\prime,0)$-quasigeodesics must have infinitely many distinct states. In particular, the language is not accepted by an FSA and so is not regular.

Fix a generating set S such that the Cayley graph $\Gamma(G,S)$ satisfies (⋆) with constants $(K, \lambda)$. Let $\lambda^\prime \gt (2K - 1)\lambda$. Write $l_n = \ell(\gamma_n)$.

We need to choose the parametrization of our loops γ_n thoughtfully.

Claim. There exists an arclength parametrization $\gamma_n: [0,l_n] \rightarrow \Gamma(G,S)$ of the loop n such that if $T_n \in {\mathbb N}$ is the minimal natural number such that $\gamma_n \rvert_{[0,T_n]}$ is not a $(\lambda^\prime,0)$-quasigeodesic, then $\gamma_n \rvert_{[1,T_n]}$ is a $(\lambda^\prime,0)$-quasigeodesic.

Proof of Claim

To begin with, suppose $\gamma_n^\prime: [0,l_n] \rightarrow \Gamma(G,S)$ is some arbitrary parametrization by arclength of the loop γ_n. Let $T_n^\prime \in {\mathbb N}$ be the minimal natural number such that $\gamma_n^\prime \rvert_{[0,T_n^\prime]}$ is not a $(\lambda^\prime,0)$-quasigeodesic. It follows that there exists a non-empty collection of non-negative integers

\begin{align*} {\mathcal{T}}_n^\prime = \{T \in {\mathbb N}_0: T \leq T_n^\prime\ \textrm{and }\lambda^\prime {\lvert}{\gamma_n^\prime(T)^{-1}\gamma_n^\prime(T_n^\prime)}{\rvert} \lt T_n^\prime - T\}. \end{align*}

Let $S_n^\prime = \max {\mathcal{T}}_n^\prime$. Consider now the alternate parametrization $\gamma_n: [0,l_n] \rightarrow \Gamma(G,S)$ of our loop defined by $\gamma_n(t) = \gamma_n^\prime(t + S_n^\prime)$. It follows that $\gamma_n(0) = \gamma_n^\prime(S_n^\prime)$ and $\gamma_n(T_n^\prime - S_n^\prime) = \gamma_n^\prime(T_n^\prime)$. If we define $T_n = T_n^\prime - S_n^\prime$ then

• • $\gamma_n \rvert_{[0,T_n - 1]}$ is a $(\lambda^\prime,0)$-quasigeodesic;

• • $\gamma_n \rvert_{[0,T_n]}$ is not a $(\lambda^\prime,0)$-quasigeodesic;

• • $\gamma_n \rvert_{[1,T_n]}$ is a $(\lambda^\prime,0)$-quasigeodesic;

and the claim follows.

Evidently, we may also assume that $\gamma_n(0) = e$ for all n. For each n, we fix the following notation:

• • Let t_n be the maximal natural number such that $\gamma_n \rvert_{[0,t_n]}$ is a $(\lambda,0)$-quasigeodesic;

• • let T_n be the minimal natural number such that $\gamma_n \rvert_{[0,T_n]}$ is not a $(\lambda^\prime,0)$-quasigeodesic;

• • let $g_n := \gamma_n(t_n)$;

• • let $h_n := \gamma_n(t_n)^{-1}\gamma_n(T_n)$. So $\gamma_n(T_n) = g_n h_n$.

Now, let $m \in \mathbb{N}$ be arbitrary and let n be such that

(3.5)\begin{equation} L_n \gt \frac{2KL_m}{\kappa} \end{equation}

where κ is the positive constant

(3.6)\begin{equation} \kappa := \frac{1}{\lambda} - \frac{2K - 1}{\lambda^\prime}. \end{equation}

We will show that the $(\lambda^\prime,0)$-quasigeodesics $\gamma_m \rvert_{[0,t_m]}$ and $\gamma_n \rvert_{[0,t_n]}$ are in different states at times t_m and t_n, respectively.

Let $\eta: [0, t_m + T_n - t_n]$ denote the concatenation of $\gamma_m \rvert_{[0,t_m]}$ with the path $\gamma_n \rvert_{[t_n,T_n]}$.

Suppose first that $\eta \rvert_{[0,t_m + T_n - t_n - 1]}$ is not a $(\lambda^\prime,0)$-quasigeodesic. Then we are done since we know that $\gamma_n \rvert_{[0,t_n]}$ concatenated with $\gamma_n \rvert_{[t_n,T_n - 1]}$ is a $(\lambda^\prime,0)$-quasigeodesic (by the minimality of T_n) whereas $\gamma_m \rvert_{[0,t_m]}$ concatenated with the same path is not a $(\lambda^\prime,0)$-quasigeodesic. So we may assume that $\eta \rvert_{[0,t_m + T_n - t_n - 1]}$ is a $(\lambda^\prime,0)$-quasigeodesic.

Suppose we have proven that $\eta \rvert_{[0,t_m + T_n - t_n]}$ is a $(\lambda^\prime,0)$-quasigeodesic. Then $\gamma_n \rvert_{[0,t_n]}$ concatenated with the path $\gamma_n \rvert_{[t_n, T_n]}$ is not a $(\lambda^\prime,0)$-quasigeodesic (by the definition of T_n), but $\gamma_m \rvert_{[0,t_m]}$ concatenated with the same path is a $(\lambda^\prime,0)$-quasigeodesic. It follows that the $(\lambda^\prime,0)$-quasigeodesics $\gamma_m \rvert_{[0,t_m]}$ and $\gamma_n \rvert_{[0,t_n]}$ are in different states at times t_m and t_n, respectively. So we would like to prove that $\eta \rvert_{[0,t_m + T_n - t_n]}$ is a $(\lambda^\prime,0)$-quasigeodesic. Looking for a contradiction, suppose this is false. Then there exists some $0 \leq t \leq t_m + T_n - t_n$, $t \in {\mathbb N}_0$, such that

\begin{align*} \lambda^\prime {\lvert}{\eta(t)^{-1}\eta(t_m + T_n - t_n)}{\rvert} \lt t_m + T_n - t_n - t. \end{align*}

If $t \geq t_m$, then $\gamma_n \rvert_{[t,T_n]}$ is not a $(\lambda^\prime,0)$-quasigeodesic. However, by our assumption on the parametrizations of the loops, we know this is not the case. So we may assume that $t \leq t_m$. Hence,

(3.7)\begin{equation} \lambda^\prime {\lvert}{\gamma_m(t)^{-1} g_m h_n}{\rvert} \lt t_m + T_n - t_n - t. \end{equation}

To conclude the proof, we’ll need to recall the following inequalities. By condition (⋆), we have:

(3.8)\begin{align} L_m &\leq t_m \leq KL_m; \end{align}

(3.9)\begin{align} L_n &\leq t_n; \end{align}

(3.10)\begin{align} T_n &\leq KL_n \leq Kt_n. \end{align}

Since the path γ_m is simplicial, and since $\gamma_n\vert_{[0,t_n]}$ is a $(\lambda,0)$-quasigeodesic, we have:

(3.11)\begin{align} {\lvert}{\gamma_m(t)^{-1} g_m}{\rvert} &\leq t_m - t; \end{align}

(3.12)\begin{align} \frac{t_n}{\lambda} &\leq {\lvert}{g_n}{\rvert}. \end{align}

Finally, since $\gamma_n \rvert_{[0,T_n - 1]}$ and $\gamma_n \rvert_{[1,T_n]}$ are both $(\lambda^\prime,0)$-quasigeodesics yet $\gamma_n \rvert_{[0,T_n]}$ is not a $(\lambda^\prime,0)$-quasigeodesic, we obtain:

(3.13)\begin{align} {\lvert}{\gamma_n(T_n)}{\rvert} & \lt \frac{T_n}{\lambda^\prime}. \end{align}

We have ${\lvert}{h_n}{\rvert} \geq {\rvert}{g_n} - {\lvert}{\gamma_n(T_n)}{\rvert}$, so by (3.12) and (3.13), we see that ${\lvert}{h_n}{\rvert} \geq \frac{t_n}{\lambda} - \frac{T_n}{\lambda^\prime}$. It then follows from (3.10) that

(3.14)\begin{equation}\lvert{h_n}\rvert\geq \left(\frac{1}{\lambda} - \frac{K}{\lambda^\prime}\right)t_n.\end{equation}

Now, $\lvert{\gamma_m(t)^{-1} g_m h_n}\rvert \geq \lvert{h_n}\rvert - \lvert{\gamma_m(t)^{-1} g_m}\rvert$, so by (3.14) and (3.11) we obtain

(3.15)\begin{equation} \lvert{\gamma_m(t)^{-1} g_m h_n}\rvert \geq \left(\frac{1}{\lambda} - \frac{K}{\lambda^\prime}\right)t_n - (t_m - t). \end{equation}

Combining our assumption (3.7) with (3.10), we obtain

(3.16)\begin{equation} \lambda^\prime\lvert{\gamma_m(t)^{-1} g_m h_n}\rvert\leq t_m - t + (K-1)t_n. \end{equation}

Next, combining (3.15) and (3.16) yields

\begin{align*} \frac{t_m - t + (K-1)t_n}{\lambda^\prime} \geq \left(\frac{1}{\lambda} - \frac{K}{\lambda^\prime}\right)t_n - (t_m - t). \end{align*}

This rearranges to

\begin{align*} 0 &\geq \left(\frac{1}{\lambda} - \frac{(2K - 1)}{\lambda^\prime}\right)t_n - \left(1 + \frac{1}{\lambda^\prime}\right)(t_m-t);\\ &\geq \kappa t_n - 2(t_m-t), \end{align*}

where κ is defined in (3.6). Now,

\begin{align*} t_n \leq \frac{2(t_m - t)}{\kappa} \leq \frac{2t_m}{\kappa}, \end{align*}

and so by (3.8) and (3.9) we have

\begin{align*} L_n \leq \frac{2KL_m}{\kappa} \end{align*}

which contradicts (3.5). So $\eta \rvert_{[0,t_m + T_n - t_n]}$ is a $(\lambda^\prime,0)$-quasigeodesic and so the $(\lambda^\prime,0)$-quasigeodesics $\gamma_m \rvert_{[0,t_m]}$ and $\gamma_n \rvert_{[0,t_n]}$ are in different states at times t_m and t_n, respectively.

Let $\xi: \mathbb{N} \rightarrow \mathbb{N}$ be the function

\begin{align*} \xi(m) = \min \left\{n \in \mathbb{N} : L_n \gt \frac{2KL_m}{\kappa}\right\}. \end{align*}

Let $(n_i)_{i \in {\mathbb N}}$ be the integer sequence defined inductively by $n_1 = 1$, $n_{i+1} = \xi(n_i)$. By the above, we know that for every $i \in {\mathbb N}$ and for every j < i, $\gamma_{n_i}(t_{n_i})$ is in a different state to $\gamma_{n_j}(t_{n_j})$ as a $(\lambda^\prime,0)$-quasigeodesic. It follows that there are infinitely many different $(\lambda^\prime,0)$-states. Hence, the $(\lambda^\prime,0)$-quasigeodesics in $\Gamma(G,S)$ cannot form a regular language.

Theorem 1.3. Let G be a finitely generated non-hyperbolic group. Then for all finite generating sets S and all $\lambda^\prime \gt 54$ the set of $(\lambda^\prime,0)$-quasigeodesics is not regular in $\Gamma(G,S)$.

Proof. Since G is not hyperbolic, by Theorem 3.3, for each finitely generated Cayley graph Γ of G, there exists some K > 1 such that Γ satisfies (⋆) with constants $(K,3)$. Instead, by corollary 3.5, we may take the constants $(K,18)$ with K > 2—we choose to work with these constants. Now, Proposition 3.6 implies that for all $\lambda^\prime \gt (2\times 2-1)\times 18=54$, the set of $(\lambda^\prime,0)$-quasigeodesics is not regular in $\Gamma(G,S)$, as required.

Theorem 1.2. A finitely generated group is hyperbolic if and only if it is $\mathbb{Q}\mathbf{REG}$.

Proof. That hyperbolicity implies $\mathbb{Q}\mathbf{REG}$ was proven by Holt and Rees in [16]. The other direction is given by our Theorem 1.3.

Theorem 1.3 suggests that for every non-hyperbolic group G and every finite generating set S there exists some infimal value of λ such that for all $\lambda^\prime \gt \lambda$ the language of $(\lambda^\prime,0)$-quasigeodesics in $\Gamma(G,S)$ is not regular. Given a non-hyperbolic group G, it is interesting to ask what this infimal λ might be. As far as we are aware, there are no known examples of non-hyperbolic Cayley graphs $\Gamma(G,S)$ with regular $(\lambda,0)$-quasigeodesics unless λ = 1.

Conjecture 3.7

If G is a non-hyperbolic finitely generated group, then for all generating sets S, and for all $\lambda^\prime \gt 1$, the $(\lambda^\prime,0)$-quasigeodesics in $\Gamma(G,S)$ do not form a regular language.

3.3. Geodetic Cayley graphs

Finally, we prove our application to Shaprio’s question on geodetic Cayley graphs.

Theorem 1.5. Let G be a finitely generated group with a generating set S such that $\Gamma(G, S)$ is geodetic. If there exists λ > 3 such that the language of $(\lambda, 0)$-quasigeodesics is regular, then G is hyperbolic and hence virtually free.

Proof. Let Γ be a graph. An isometrically embedded circuit (IEC) is a simplicial loop of length $2n+1$ such that the restriction of each subsegment of length at most n is a geodesic.

We claim that if Γ is geodetic and not hyperbolic then there are IECs of arbitrarily large length. So suppose Γ is geodetic and there is a uniform bound on the length of IECs. We will show that Γ is hyperbolic. By [25, Theorem 1.4], a Cayley graph is hyperbolic if and only if all geodesic bigons are uniformly thin, i.e. any two geodesics sharing endpoints have uniformly bounded Hausdoff distance. Consider an arbitrary geodesic bigon in Γ. Since Γ is geodetic, if the geodesic endpoints are vertices, the geodesics need to coincide. Further, it is straightforward to check that if the endpoints are both in an edge one can reduce to a case where at least one endpoint is a vertex. So, the only case left is a bigon where one endpoint is a vertex and the other is the midpoint of an edge. By [9, lemma 4], such a configuration produces an IEC. Since these have uniformly bounded length, the bigon is thin. So Γ is hyperbolic and the claim is proved.

Observe that an IEC of length $2n+1$ is an n-local geodesic. By Proposition 3.6, we conclude that if a group is non-hyperbolic and geodetic, then for any $\lambda^\prime \gt 3$ the set of $(\lambda^\prime, 0)$-quasigeodesics cannot form a regular language.