# Finite-State Machines for Horospheres in Hyperbolic Right-Angled Coxeter
Groups

Noah Jillson, Daniel Levitin, Pramana Saldin, Katerina Stuopis, Qianruixi
Wang, Kaicheng Xue

Relatively little is known about the discrete horospheres in hyperbolic
groups, even in simple settings. In this paper we work with hyperbolic one-
ended right-angled Coxeter groups and describe two graph structures that mimic
the intrinsic metric on a classical horosphere: the Rips graph and the
divergence graph (the latter due to [3]). We develop, analyze, and implement
algorithms based on finite-state machines that draw large finite portions of
these graphs, and deduce various geometric corollaries about the path metrics
induced by these graph structures.

##  1\. Introduction

Horospheres. If $(X,d)$ is an unbounded geodesic metric space, and $\gamma$ is
a geodesic ray, (i.e. $\gamma:[0,\infty)\to X$ is an isometric embedding), the
Busemann Function associated to $\gamma$, $b_{\gamma}:X\to\mathbb{R}$ is
defined to be

$\lim_{t\to\infty}d(x,\gamma(t))-d(\gamma(t),x_{0}),$

where $x_{0}$ is a fixed base point in $X$. While this function depends on
$x_{0}$, the level sets, called horospheres, do not. In the case where $(X,d)$
is the hyperbolic space $\mathbb{H}^{n}$, then regardless of the choice of ray
$\gamma$ or value for the Busemann function, the space $b_{\gamma}^{-1}(r)$
with its intrinsic metric is isometric to the Euclidean space
$\mathbb{E}^{n-1}$. These horospheres are exponentially distorted relative to
their extrinsic metric. One views the ray $\gamma$ as encoding a point at
infinity on the boundary sphere $S^{n-1}=\partial\mathbb{H}^{n}$. The points
on this sphere are directions in $\mathbb{H}^{n}$, and the Euclidean space
$\mathbb{E}^{n-1}$ arises naturally as the stereographic projection of the
sphere.

In this paper, we study horospheres in the Cayley graphs of certain Right-
Angled Coxeter Groups (RACGs). These Cayley graphs come from a standard
presentation where the generators are order-$2$ elements $a_{i}$, subject only
to a collection of commutation relations between the generators. More
precisely, if $\Gamma=(V,E)$ is a finite simplicial graph, then the RACG
$W_{\Gamma}$ is the group

$\langle a_{i}\in V|a_{i}^{2},[a_{i},a_{j}]\text{ for }(a_{i},a_{j})\in
E\rangle.$

We will be interested in graph structures on these horospheres that provide
some notion of an intrinsic metric on a non-smooth space. It is a
straightforward calculation that unequal words on a horosphere are at distance
at least $2$ from one another, and therefore do not span an edge (see Lemma
4.1.3). Therefore, we will treat two notions of an intrinsic graph structure,
neither of which are the induced subgraph. First we discuss the k-Rips graph,
which connects two vertices exactly when they are at distance at most $k$ in
the ambient graph metric. One imagines this graph allowing them to traverse a
short distance along the horosphere as a coarse analogue of requiring a path
to be everywhere tangent to the horosphere in the smooth case. Second, we
treat (under an additional assumption) the divergence graph due to Cohen,
Goodman-Strauss, and Rieck [3]. Edges in this graph have a more complicated
description, and encode the existence of certain parallel lines that stay
close for all time. See Definition 5.1.1. In both cases, we are interested in
the induced path metric in the resulting graph. These graphs are infinite and
difficult to study in general, but under minor additional assumptions, we give
algorithms to draw large finite pieces of both of these graphs in
asymptotically optimal time.

######  Theorem 1.1.

Let $\Gamma$ be a graph satisfying the assumptions in Definition 2.6, and let
$W_{\Gamma}$ be the associated RACG. Let $\gamma=(a_{i}a_{j})^{\infty}$ be a
ray, and consider the set $H_{k}=b_{\gamma}^{-1}(k)$ for any integer $k$. A
subgraph of either the $2$-Rips graph or the divergence graph on $H_{k}$ with
$n$ vertices can be drawn in runtime $O(n\log(n))$. This time complexity is
optimal.

See Theorems 4.3.2 and 5.4.5 for further details, and Proposition 5.1.3 for
the additional assumption in the divergence graph case.

Optimality is unsurprising: we have $n$ vertices, and a positive proportion of
their labels have length that is linear in $\log(n)$. So just listing each
vertex already requires $\Omega(n\log(n))$ steps.

For the Rips graph case, our consideration of just the $2$-Rips graph is
justified by the following result, which is proved in Proposition 4.4.5.

######  Proposition 1.2.

For any $k_{1},k_{2}\geq 2$, the induced path metrics on the $k_{i}$-Rips
graphs on any horosphere are bi-Lipschitz equivalent.

Hyperbolic groups and their boundaries. The most important of the assumptions
on the graph $\Gamma$ for Theorem 1.1 is that there are no induced subgraphs
that are $4$-cycles. This is equivalent to the Cayley graph of $W_{\Gamma}$
being $\delta$-hyperbolic, i.e. displaying large-scale features similar to
that of the hyperbolic space [9, 14]. This assumption underlies all the
algorithms we write, allowing computations in RACGs to be carried out quickly
and with minimal memory usage in relatively simple finite-state machines
(FSMs) due to [2] (see Definition 2.9). This is true more generally for
hyperbolic groups that are not RACGs (i.e. groups with $\delta$-hyperbolic
Cayley graphs), but the FSMs may be considerably more difficult to describe
[8]. The bulk of the paper consists of reducing geometric questions down to
FSM-checkable properties about (pairs of) words in certain regular languages.

While this theorem is phrased for a fixed generating graph $\Gamma$ of the
group $W_{\Gamma}$, a caveat is in order. The complexity of these algorithms
is exponential in terms of the largest clique in the graph $\Gamma$. This
fact, though inconvenient, is expected. It is a straightforward consequence of
Papasoglu’s theorem on thin bigons that the groups $W_{\Gamma}$ become less
hyperbolic as the clique size of $\Gamma$ increases [15]. Since all of these
algorithms require hyperbolicity to work, it is unsurprising that they take
longer as $W_{\Gamma}$ becomes less hyperbolic.

Besides their algorithmic properties, it is a matter of mathematical folklore
that some properties of the horospheres in $\mathbb{H}^{n}$ should carry over
to hyperbolic groups. The Cayley graphs of these groups have boundaries
$\partial W_{\Gamma}$ consisting of (equivalence classes of) rays, equipped
with a suitable metric, but these boundaries can be topologically and
metrically much more complicated than the round spheres at the boundary of
$\mathbb{H}^{n}$. Nevertheless, it is expected that there should be a
topological and geometric analogy between these discrete horospheres and the
stereographic projections of the boundary.

The geometry of the boundary of a $\delta$-hyperbolic group is of particular
interest, for instance, because of its value to Gromov’s program of
classifying finitely-generated groups up to quasi-isometry [10]. See chapter
III.H.3 of [1] for more details. Nevertheless, to our knowledge there has been
little work to understand what an appropriate intrinsic metric on these
discrete horospheres might be, and what it might encode about the metric
structure of the boundary.

Geometry of Horospheres in RACGs. For the groups $G$ with the strongest
analogy to $\mathbb{H}^{n}$, the fundamental groups of closed hyperbolic
$n$-manifolds (and more generally cocompact lattices in semisimple Lie
Groups), there is a bi-Lipschitz model of $G$ in which the horospheres (with
respect to the Lie Group or symmetric space metric) receive a cocompact action
by a group $\mathbb{Z}^{n-1}$ (or more generally a discrete nilpotent group),
with exponentially distorted orbits [13]. This action is translation-like,
i.e. geometrically similar to right multiplication by the elements of a
subgroup. However, it is unclear how much of this translates to horospheres
with respect to the metric on the Cayley graph.

On this topic, we show connectivity and exponential distortion for the k-Rips
graph with $k\geq 2$. We note also that the connectivity of the Divergence
Graph was already known [3].

######  Proposition 1.3.

Let $W_{\Gamma}$ be a hyperbolic right-angled Coxeter group whose boundary,
$\partial W_{\Gamma}$, is connected. The $2$-Rips graph on the horosphere
$b_{\gamma}^{-1}(k$) is connected, for $\gamma$ a repeating ray.

See Proposition 4.4.6. Following the analogy between horospheres and
stereographic projections of the boundary, this proof breaks into cases based
on the connectivity of $\partial W_{\Gamma}\setminus\gamma(\pm\infty)$, where
$\gamma(\pm\infty)$ refers to the endpoints of the line
$(...a_{i}a_{j}a_{i}a_{j}...)$ on the boundary. See Proposition 4.5.2 and its
proof for further details. Along the way, in Remark 4.5.3 we give a
description of the set of path components of $\partial
W_{\Gamma}\setminus\gamma(\pm\infty)$, which to our knowledge has not yet
appeared in the literature without additional assumptions (for RACGs with no
cliques larger than edges, see [5, 4, 7]).

Putting the connectivity statement together with some general facts about the
divergence functions of a hyperbolic group then yields the conclusion that the
Rips graph is exponentially distorted.

######  Theorem 1.4.

Let $W_{\Gamma}$ be a hyperbolic right-angled Coxeter group with connected
boundary. There exist exponential functions $f_{1}$ and $f_{2}$ such that the
following holds. If $\gamma=(a_{i}a_{j})^{\infty}$ is any periodic ray, $w$
and $v$ are in $b_{\gamma}^{-1}(k)$, and if $d$ denotes the metric on
$W_{\Gamma}$ while $d_{H}$ denotes the path metric on the $2$-Rips graph, then

$f_{1}(d(w,v))\leq d_{H}(w,v)\leq f_{2}(d(w,v))$

.

See Theorem 4.5.1 for further details. It is an immediate corollary that the
divergence graph inherits an exponential lower bound on distortion, due to a
result in [3] that says that (in general) the divergence graph is a subgraph
of a $k$-Rips graph for a sufficiently large $k$, though we obtain a better
bound in the setting of RACGs. It is not obvious how to prove an upper bound
for divergence graphs in general. However if $\Gamma$ satisfies a technical
condition that holds, e.g., for any triangulation of a closed manifold, then
an upper bound can be deduced without trouble. See Proposition 5.5.3.

As a consequence of the lower bound, we further conclude that each Rips and
divergence graph is a graph of polynomial growth.

######  Corollary 1.5.

There is a polynomial $P$ depending on $\Gamma$ and $\\{a_{i},a_{j}\\}$ so
that a certain ball in the $2$-Rips graph grows with rate $|B(w_{0},r)|\leq
P(r)$. The same holds (with a possibly-different polynomial) in the divergence
graph.

See Corollaries 4.5.6 and 5.5.2 for more information. Note that by Proposition
1.2, this then holds with a different polynomial for each other Rips graph.
Also, the triangle inequality shows that
$|B(w,r)|\leq P(r+d(w,w_{0}))$. So every ball grows at a potentially-different
polynomial rate.

While we cannot presently give any nilpotent structure to the horospheres as
in [13], polynomial growth can be seen a first step toward such a structure.
More precisely, if we could find a bi-Lipschitz equivalent graph structure
that was coarsely vertex transitive, then a theorem of Trofimov would tell us
that the horospheres are approximately Cayley graphs of nilpotent groups [18].
This would be a major step toward understanding the geometry of hyperbolic
RACGs. A discrete space foliated by a $\mathbb{Z}$-indexed family of
exponentially-distorted (approximate) nilpotent Cayley graphs would also match
with Heinze’s description of homogeneous negatively-curved Riemannian
manifolds as semidirect products $N\rtimes\mathbb{R}$ where $N$ is a simply-
connected nilpotent Lie group and $\mathbb{R}$ acts on $N$ by an expansion, so
that each coset of $N$ is exponentially distorted [11].

Further Remarks. One difficulty with studying horospheres in the Cayley graph
is that they are, even as sets, not particularly invariant objects. A choice
of a different generating set for the group $G$ may render the ray $\gamma$ no
longer geodesic. Even if this does not happen, changes of generating set may
scramble horospheres. For instance, consider the group $F_{2}=\langle
a,b\rangle$ with generating sets $S_{1}=\\{a,b\\}$, $S_{2}=\\{a,b,b^{3}\\}$.
It is a straightforward exercise to compute that if we take $\gamma(n)=a^{n}$
and $x_{0}$ to be the identity, then with respect to $S_{1}$,
$b_{\gamma}(a^{m}b^{m})=0$, while with respect to $S_{2}$,
$b_{\gamma^{\prime}}(a^{m}b^{m})\approx\frac{-2m}{3}$. Another advantage of
studying RACGs, then, is that they come equipped with a preferred generating
set, and thus a preferred Cayley graph and metric.

With minor modifications, the algorithms should all work for Rips and
divergence graphs defined with respect to any repeating ray, and yield similar
geometric properties. Without the assumption that the ray is an infinite
power, there is no hope of obtaining FSM-based algorithms to draw horospheres.
The geometric statements should still be true without the repeating
assumption, because they are mostly consequences of the algorithms in abstract
rather than the FSM implementations. However, all of the statements would
become considerably more technical and less enlightening. Therefore we have
chosen to focus on the simple case for this paper.

In the case of the 2-Rips graph and the divergence graph, the code is
available on Daniel Levitin’s github, at
https://github.com/dnlevitin/horospheres. The Main branch has the code used to
generate the figures in this paper.

Outline. The outline of the paper is as follows. In Section 2, we define the
basic objects of study. Section 3 lays out the finite-state machines that we
will use and combine repeatedly throughout the remainder of the paper.
Sections 4 and 5 treat the $2$-Rips graph and the divergence graph, and follow
a similar structure. First we introduce a normal form on the vertices that we
will use for our computations. We then describe an algorithm to find edges
between words whose normal forms have the same lengths, and then an algorithm
to find edges between words whose normal forms have different lengths. Both
sections conclude by proving the geometric corollaries of our description of
the edge set, including distortion estimates and polynomial growth. In Section
6, we give graphical examples that demonstrate the outputs of the algorithms
we have described.

Acknowledgments. Daniel Levitin would like to thank Mark Pengitore for first
introducing them the study of horospheres in hyperbolic groups. They would
also like to thank Enrico Le Donne for several interesting conversations about
distortions of horospheres.

The whole group of authors would like to thank the Madison Experimental
Mathematics lab, and its director Çağlar Uyanik and associate director Grace
Work, for facilitating this project. Daniel Levitin would like to thank them
especially for matching them with inquisitive and motivated undergraduates to
work with. The whole group would also like to thank this project’s faculty
mentor, Tullia Dymarz, for her guidance.

Daniel Levitin, Noah Jillson, Pramana Saldin, and Katerina Stuopis were
supported by NSF grant 2230900 during this project. Daniel Levitin was further
supported by NSF grant 1552234.

##  2\. Preliminaries

In this section, we will lay out background definitions from geometric group
theory.

######  Definition 2.1.

Let $G$ be a group with generating set $S$. They Cayley Graph of the $G$ with
generating set $S$, denoted $Cay(G,S)$, is the graph whose vertex set is $G$
and with edges $(g,gs)$ for each $g\in G$ and $s\in S$. We endow $Cay(G,S)$
with a metric $d_{S}$ by giving each edge length $1$ and taking the path
metric. We refer to the restriction of this metric to the vertex set (i.e. to
$G$) again as $d_{S}$. Note that on $G$ this metric is given by the formula
$d_{S}(g_{1},g_{2})=|g_{1}^{-1}g_{2}|_{S}$, where $|\cdot|_{S}$ denotes the
word length in terms of $S$. We will call $d_{S}$ the word metric (with
respect to S).

This allows us to associate a metric space to a group, and indeed a family of
metric spaces. Without going into great detail, there is a natural notion of
equivalence among the various metric $d_{S}$ arising from different choices of
generating sets. The large-scale geometric properties of the Cayley graph will
usually turn out to be independent of $S$.

When describing segments and rays in these spaces, we will consider either
edge paths in the Cayley graph or sequences in the group. It will usually not
matter which we consider.

######  Definition 2.2.

We will say that a word in the generating set is geodesic if the associated
edge path starting at the identity in the Cayley graph is distance-minimizing.
If the generating set $S$ carries an alphabetical order, then a word is a
shortlex geodesic if it is a geodesic and is alphabetically first among all
geodesics with the same start and endpoint.

One example of a crucial geometric property of a group that does not depend on
choice of generating set is that of negative curvature, which is formalized in
the following definition.

######  Definition 2.3.

Let $G$ be a group and $S$ a generating set. $G$ is said to be
$\delta$-hyperbolic for a non-negative real number $\delta$ if for any 3
points $x_{1}$, $x_{2}$, and $x_{3}$ in $G$, and any geodesic segments
$\gamma_{1}=[x_{1},x_{2}]$, $\gamma_{2}=[x_{2},x_{3}]$, and
$\gamma_{3}=[x_{3},x_{1}]$, then any $\gamma_{i}$ is in the
$\delta$-neighborhood of the union of the other two.

We will say that $G$ is hyperbolic if it is $\delta$-hyperbolic for some
$\delta$ and some choice of generating set. It is well-known that a change of
generating set can change the value of $\delta$, but that if $G$ is
$\delta$-hyperbolic with respect to some finit generating set $S$, it will be
hyperbolic with respect to any other finite generating set.

In this paper, we will study right-angled Coxeter Groups and their Cayley
graphs with respect to a special generating set.

######  Definition 2.4.

Let $\Gamma$ be a graph, with vertex set $V=\\{a_{i}\\}$ and edge set $E$. The
right-angled Coxeter group (RACG) determined by $\Gamma$, denoted
$W_{\Gamma}$, is the group with presentation $\langle V|R\rangle$ where $R$ is
the set of words $\\{a_{i}^{2},[a_{i},a_{j}]:(a_{i},a_{j})\in E\\}$.

We think about these relations as allowing us to cancel any two adjacent
copies of the same letter, and otherwise to reverse the order of an adjacent
pair of letters exactly when the associated vertices span an edge.

We will be interested in the Cayley graphs for the given generating set, and
we will order the generators by subscripts, i.e. $a_{1}<a_{2}<...$. When we
use the symbol $d$ for distance in a RACG, we always mean with respect to the
generating set $V$. Similarly, the expression $|w|$ means the length of any
geodesic word equivalent $w$ in the generating set $V$.

We fix some notation in the graph $\Gamma$ We will denote $Star(a_{i})$ to be
$a_{i}$ together with the vertices adjacent to $a_{i}$. The sets
$Star_{<}(a_{i})$ and $Star_{>}(a_{i})$ are those adjacent vertices earlier
and later than $a_{i}$ respectively, and $Star_{\leq}(a_{i})$ and
$Star_{\geq}(a_{i})$ are $Star_{<}(a_{i})$ and $Star_{>}(a_{i})$ together with
$a_{i}$. $Link(a_{i})$ means the set of vertices adjacent to $a_{i}$, and may
be decorated with a subscript as before. Finally, $Clique(\Gamma)$ is the size
of the largest clique in $\Gamma$.

For a RACG, a great deal is known about its properties just in terms of the
defining graph. For example hyperbolicity can be read off from the defining
graph.

######  Theorem 2.5.

[14]

Let $\Gamma$ be a graph without induced square subgraphs. Then $W_{\Gamma}$ is
hyperbolic.

######  Definition 2.6 (Standing Assumptions).

We make the following standing assumptions of all of our defining graphs
$\Gamma$.

  * •

$\Gamma$ has no induced square subgraphs, i.e. $W_{\Gamma}$ is hyperbolic.

  * •

$\Gamma$ is not a complete graph.

  * •

$\Gamma$ has no separating cliques, i.e., no (possibly empty) complete
subgraphs $K$ so that $\Gamma\setminus K$ is disconnected. In particular
$\Gamma$ is connected.

These assumptions are necessary and sufficient for the group $W_{\Gamma}$ to
be one-ended and hyperbolic.

######  Definition 2.7.

Let $\gamma$ be a geodesic ray in a hyperbolic RACG. The Busemann function
determined by $\gamma$ is the function $b_{\gamma}:W_{\Gamma}\to\mathbb{Z}$
defined by $b_{\gamma}(w)=\lim_{n\to\infty}d(\gamma(n),w)-d(\gamma(n),e)$
where $e$ denotes the identity.

A horosphere for $\gamma$ is a level set of $b_{\gamma}$. We will refer to the
$k$-horosphere to mean $b_{\gamma}^{-1}(k)$.

We will restrict our consideration for convenience to horospheres in
hyperbolic RACGs about the rays that we will colloquially refer to as
$\gamma=(a_{i}a_{j})^{\infty}$. That is, for any two vertices $a_{i}$ and
$a_{j}$ not spanning an edge in the defining graph, this geodesic starts at
the origin in the Cayley Graph, then traverses the edge to $a_{i}$, then to
$a_{i}a_{j}$, and so on forever. It is straightforward to verify that this
really is a geodesic.

We will be interested in putting graph structures on these horospheres. The
first such graph structure we define here. The second one is more complicated
and will be defined later.

######  Definition 2.8.

Let $(X,d)$ be a metric space. The $k$-Rips graph on $X$ is the graph whose
vertex set is $X$ and where edges connect points at $d$-distance at most $k$.

For us, $X$ will be a horosphere, and $d$ will be the restriction of the word
metric.

For our computations, we will use a formalism called a Finite-State Machine
(FSM).

######  Definition 2.9.

A Finite-State Machine $M$ consists of the following

  * •

A finite, labeled, directed graph $G=(V,E)$ (whose vertices are called
states), whose edges are labeled in the alphabet $\mathscr{A}$ such that every
vertex has exactly one directed edge exiting it labeled by each letter in
$\mathscr{A}$.

  * •

A special vertex $v\in V$ called the starting state

  * •

A subset $A$ of the vertices of $V$ called the accepted states.

We write $v_{1}\to_{a}v_{2}$ if there is an edge labeled $a$ from $v_{1}$ to
$v_{2}$.

Given such a machine $M$, the associated regular language $\mathscr{L}(M)$
consists of all strings of letters in $\mathscr{A}$ labeling paths from the
starting state to an accepted state.

We will usually not describe FSMs in this level of detail because it is
somewhat cumbersome. The following remarks provide some simplifications we
will usually use tacitly.

######  Remark 2.10.

Many of the languages $\mathscr{L}(M)$ we consider will be prefix-closed, i.e.
if $w=a_{i_{1}}a_{i_{2}}...a_{i_{n}}$ is an accepted word, then so are all
words $a_{i_{1}}a_{i_{2}}...a_{i_{k}}$ for $k<n$. In such a case, every non-
accepted state leads only to non-accepted states. Therefore, we can remove all
non-accepted states and the edges to and from them, and get a graph where the
words labeling directed paths are again $\mathscr{L}(M)$. When we describe an
FSM without specifying accepted states or where not every vertex has an
outgoing edge with every label, we mean that we are describing the accepted
subgraph of a machine $M$ associated to a prefix-closed language. The full
graph $G$ can be recovered by adding a single rejected vertex into the graph,
and directing each missing edge to go to this vertex.

Sometimes, we will describe a larger set of of vertices and edges than
strictly necessary.

######  Remark 2.11.

When we describe a finite-state machine, especially if it is derived from
another finite-state machine, we will specify a vertex set, labeled edge set,
and starting state. It will often be the case that from the starting state,
many vertices cannot be reached by a directed path. For instance, when
combining machines $M_{1}$ and $M_{2}$ that perform similar functions, we may
take a vertex set to be $M_{1}\times M_{2}$, even though there may be pairs of
vertices which contain mutually incompatible data. When this happens, we
implicitly intend to consider only the subgraph consisting of accessible
vertices and the edges between them.

A note on notation: the states in an FSM $M$ will often be defined in terms of
data that we want to use later. By a slight abuse of notation, if $w$ is in
$\mathscr{L}(M)$, then $M(w)$ will mean the final state that the word $w$ ends
on in the FSM $M$.

The motivation for defining regular languages is that we will often prefer to
think of a machine in terms of the language it accepts. For instance, the
following proposition is convenient to phrase as a combination theorem for
regular languages rather than one about finite-state machines.

######  Proposition 2.12.

Suppose $\mathscr{L}_{1}$ and $\mathscr{L}_{2}$ are regular languages. Then
the languages $\mathscr{L}_{1}\cap\mathscr{L}_{2}$,
$\mathscr{L}_{1}\cup\mathscr{L}_{2}$, and $\mathscr{L}_{1}\mathscr{L}_{2}$ are
all regular, where the last expression refers to the set of concattenations of
words in $\mathscr{L}_{1}$ with those in $\mathscr{L}_{2}$.

Furthermore, if $\mathscr{L}$ is a language with alphabet $\mathscr{A}$ and
$\mathscr{B}$ is a subset $\mathscr{A}$, the language
$\mathscr{L}|_{\mathscr{B}}$ consisting of words in $\mathscr{L}$ containing
only letters in $\mathscr{B}$, is regular.

For a proof, see any standard text on regular language theory, such as [8].

Here is one standard language we will use in these combinations.

######  Lemma 2.13.

Let $\mathscr{B}$ be a subset of $\mathscr{A}$. Then the language
$F_{\mathscr{B}}$, consisting of words in $\mathscr{A}$ that cannot be
rearranged to begin with a letter of $\mathscr{B}$, is regular111More
precisely, this is the set of words in $\mathscr{A}$ that cannot be made to
begin with a letter of $\mathscr{B}$ without cancellation. We will always
combine these languages with others that guarantee no cancellation occurs, so
that the resulting words cannot being with letters of $\mathscr{B}$..

###### Proof.

We define the relevant machine $M_{\mathscr{B}}$ whose vertices are subsets of
$\mathscr{B}$ and whose starting state is $\mathscr{B}$. From each state $S$,
we define edges leaving $S$ labeled by each letter not in $S$ by
$S\to_{a_{i}}S\cap Star(a_{i})$. As in Remark 2.10 these states are all
accepted, and every other edge leads to an inescapable rejected state.

One sees by induction that for a word $w$, $M_{\mathscr{B}}(w)$ is the set of
letters that, if written after $w$, could commute to the beginning. Therefore,
the fact that every state has edges exiting it labeled by its complement means
that the associated language is $F_{\mathscr{B}}$ as desired. ∎

From time to time we will need to restrict to words of odd or even length.

######  Lemma 2.14.

The languages $Odd(\mathscr{A})$ of odd-length words and $Even(\mathscr{A})$
of even-length words are regular222Again, these are without cancelling
letters, and we will always combine this language with others to guarantee no
cancellation. As it happens, in a RACG, letters cancel one pair at a time and
therefore preserve the parity, see [6].

###### Proof.

The associated machines have two vertices and every edge goes from the other.
In one, the start state is accepted and the other is rejected, and in the
other it’s the other way around. ∎

We will also use the following estimate on the size of the language
$\mathscr{L}$ of the machine $\mathscr{M}$. Its proof is an application of the
Perron-Frobenius theorem to the transition matrix of $\mathscr{M}$, after a
permutation to make this matrix block upper-triangular.

######  Lemma 2.15.

Let $\mathscr{M}$ be a FSM with language $\mathscr{L}$ and adjacency matrix
$A$. $A$ has a real eigenvalue $\lambda$ of maximal modulus (possibly with
multiplicity). If $\mathscr{L}_{n}$ denotes the set of words of $\mathscr{L}$
of length at most $n$, then the limit
$\lim_{t\to\infty}\frac{|\mathscr{L}_{n}|}{\lambda^{n}}$ converges to a
constant.

##  3\. Finite State Machines for Hyperbolic Right-Angled Coxeter Groups

As mentioned in the introduction, one advantage to working with RACGs is that
they admit convenient computations in FSMs. For instance, RACGs, hyperbolic or
otherwise, have a finite-state machine that accepts the set of all geodesics,
and a separate finite-state machine that accepts the set of all shortlex
geodesics. We make the following convention: when applied to words, the symbol
$``=^{\prime\prime}$ means that the expressions on both sides of the symbol
are identical words, while the symbol $``=_{Geo}^{\prime\prime}$ means that
the expression on the right of the symbol is a geodesic word equivalent to the
expression on the left.

######  Proposition 3.1.

Let $\Gamma=(V,E)$ be a graph. Then $Geo(W_{\Gamma})$, the set of geodesics in
the alphabet $V$ subject to the commutation and cancellations in $W_{\Gamma}$,
is a regular language. The associated FSM $M_{Geo}$ can be taken to have
states given by sets $S\subset V$ where
$M_{Geo}(w)=\\{a_{i}:|wa_{i}|=|w|-1\\}=\\{a_{i}:w=va_{i}\text{ and
}|v|=|w|-1\\}$, and edges leaving state $S$ labeled by all the elements of
$S^{c}$. The starting state is the empty set. As the geodesic language is
prefix-closed, all vertices are accepted states and unmentioned edges lead to
a single rejected state as in Remark 2.10

In more down-to-earth terms, the finite-state machine takes states which keep
track of, for a word $w$, which letters $a_{i}$ can commute to the end of $w$.

###### Proof.

First of all, we show that such a finite-state machine is well-defined, that
is, that we can determine $M_{Geo}(wa_{i})$ entirely from $M_{Geo}(w)$. This
is clear for the trivial word. If $M_{Geo}(w)$ is the collection of letters
that $w$ could end with after rearrangement for all words of length at most
$n$, and if $wa_{i}$ is geodesic, then $wa_{i}$ can end with $a_{i}$, or any
last letter of $w$ that also commutes with $a_{i}$. In particular,
$M_{Geo}(wa_{i})=\bigl{(}M_{Geo}(w)\cap star(a_{i})\bigr{)}\cup\\{a_{i}\\}$.
This shows that a machine exists whose states are subsets of $V$ as required.

We now must show that the language of this machine is $Geo(W_{\Gamma})$.
Suppose that $w$ is a geodesic word, but that $wa_{a}$ is not geodesic. By the
triangle inequality, $|wa_{i}|=|w|$ or $|wa_{i}|=|w|-1$. By a variant of the
Exchange Condition described in [6] we determine that $|wa_{i}|=|w|-1$. In
particular, $wa_{i}=_{Geo}v$ where $|v|=|w|-1$. Then by right multiplication,
$w=_{Geo}va_{i}$, so that $a_{i}$ is a last letter of $w$. Hence if
$a_{i}\not\in M_{Geo}(w)$, then $wa_{i}$ is geodesic. Therefore, if a word
$w=a_{i_{1}}a_{i_{2}}...a_{i_{n}}$ is accepted by $M_{Geo}$ and is not
geodesic, it must be because $v=a_{i_{1}}a_{i_{2}}...a_{i_{n-1}}$ was not
geodesic. Iterating, one sees a contradiction, showing that that all accepted
words are geodesics.

One shows by induction on length that $\mathscr{L}(M_{Geo})$ contains all the
geodesics in $W_{\Gamma}$. Certainly $\mathscr{L}(M_{Geo})$ contains the empty
word and all words of length $1$. If $w=a_{i_{1}}a_{i_{2}}...a_{i_{n}}$ is a
geodesic word of length $n$, and $\mathscr{L}(M_{Geo})$ contains all geodesic
words of length at most $n-1$, then $v=a_{i_{1}}a_{i_{2}}...a_{i_{n-1}}$ is an
accepted word for $M_{Geo}$, and since $w$ is geodesic, $a_{i_{n}}$ is not in
$M_{Geo}(v)$, so that there is an edge labeled by $a_{i_{n}}$ exiting
$M_{Geo}(v)$. Therefore, $w$ is in $\mathscr{L}(M_{Geo})$. ∎

The statement for the shortlex language is very similar.

######  Proposition 3.2.

Let $\Gamma$ be a graph, and fix an order $<$ on the $V$. The language
$ShortLex(W_{\Gamma})$, consisting of all shortlex geodesics, is regular. An
FSM $M_{lex}$ for this language can be taken to have states labeled by subsets
$S\subset V$ where $S(w)=\\{l_{i}:wl_{i}\text{is not shortlex}\\}$, and edges
leaving $S(w)$ corresponding to $S(w)^{c}$.

###### Proof.

Again we show that we can determine $M_{lex}(wa)$ from $M_{lex}(w)$. Suppose
$wa$ is shortlex and $waa^{\prime\prime}$ is not. Then either
$|waa^{\prime}|\leq|wa|$, which again by [6] implies that
$|waa^{\prime}|=|w|$, or $waa^{\prime}$ can be reordered to an alphabetically
earlier word.

In the first case, we claim it suffices to consider when $a^{\prime}=a$.
Suppose instead that $a^{\prime}$ cancels with a different letter in $wa$.
Then since $wa$ is assumed to be shortlex, we can write
$wa=v_{1}a^{\prime}v_{2}a$, where $a^{\prime}$ commutes with each letter in
$v_{2}a$, and $a^{\prime}$ is alphabetically earlier than the first letter of
$v_{2}$. But then the substring $v_{2}aa^{\prime}$ can already be reordered to
an alphabetically earlier word.

So by induction, we assume that $M_{lex}(w)$ consists of the last letter of
$w$ together with any letters $a_{i}$ so that $wa_{i}$ can be rearranged to be
alphabetically earlier. Then $M_{lex}(wa)$ can be taken to be
$\bigl{(}M_{lex}(w)\cap star(a)\bigr{)}\cup\\{a\\}\cup star_{<}(a)$. That is,
$M_{lex}(wa)$ consists of $a$, letters $a^{\prime}$ so that $aa^{\prime}$
should be rearranged to $a^{\prime}a$, as well as letters $a^{\prime}$ so that
$waa^{\prime}=_{Geo}wa^{\prime}a$ and $wa^{\prime}$ itself can be rearranged
to a lexicographically earlier word. This shows that $M_{lex}(wa)$ can be
computed entirely from $M_{lex}(w)$ and $a$.

An accepted word of this FSM is by definition a shortlex word. ∎

######  Remark 3.3.

Based on these two propositions, we can generate these two FSMs by a breadth-
first search. More precisely, we describe the algorithm as follows:

Start at the empty string. Since any letter should be allowed as a shortlex
geodesic on its own, compute $M_{Geo}(a_{i})$ or $M_{lex}(a_{i})$ for each $i$
and connect the start vertex to each such state by the edge $a_{i}$. Add the
start vertex into the set $C$ of “completed vertices”, i.e. those vertices
whose outgoing edges have been added.

For each vertex $S$ in the FSM but not in $C$, add outgoing edges labeled by
$S^{c}$, using the above calculation to determine which state such an edge
should reach. Add in new states as necessary if such a state has not yet been
reached in the algorithm. When this process is completed on a given vertex,
add that vertex to $C$.

Repeat until every vertex is in $C$.

##  4\. The Rips Graph on a Horosphere

###  4.1. A normal form for vertices

In this subsection, we will describe a process to generate a large set of
points on the same horosphere. This will serve as the vertex set for the
graphs we construct later on.

From now on, we assume that $a_{i}$ and $a_{j}$ are non-commuting letters, and
study the level sets $b_{\gamma}$ where $\gamma$ is the geodesic ray which we
will colloquially refer to as $(a_{i}a_{j})^{\infty}$, by which is meant the
ray starting at the origin and alternating $a_{i}$ and $a_{j}$ indefinitely.
We first prove a formula for the Busemann Functions $b_{\gamma}$. To obtain
this formula, some terminology is required.

######  Definition 4.1.1.

Let $w$ be a shortlex word. Then a prefix-suffix decomposition of $w$ is an
equality $w=_{Geo}w_{pref}w_{suff}$ so that $w_{pref}$ (the prefix) consists
entirely of the letters $a_{i}$ and $a_{j}$, and $w_{suff}$ (the suffix) is
shortlex and cannot be rearranged to begin with either $a_{i}$ or $a_{j}$.
Note that either $w_{pref}$ or $w_{suff}$ may be empty.

######  Lemma 4.1.2.

Every shortlex word has a unique prefix-suffix decomposition.

###### Proof.

To obtain the prefix-suffix decomposition, we read $w$ from left to right.
Each time we read a letter other than $a_{i}$ or $a_{j}$, we append it to
$w_{suff}^{\prime}$. When we read a letter $a_{i}$ or $a_{j}$, if every letter
so far in $w_{suff}^{\prime}$ commutes with the $a_{i}$ or $a_{j}$, we append
it to $w_{pref}$, and otherwise we append it to $w_{suff}^{\prime}$.

It is a simple induction on the length of $w$ to show that
$w=_{Geo}w_{pref}w_{suff}^{\prime}$. For $a_{i}\neq a_{k}\neq a_{j}$,
$wa_{k}=_{Geo}w_{pref}(w_{suff}^{\prime}a_{k})$ and for $a_{k}=a_{i}$ or
$a_{j}$, $wa_{k}=_{Geo}(w_{pref}a_{k})w_{suff}^{\prime}$ exactly when the new
copy of $a_{i}$ or $a_{j}$ commutes with all of $w_{suff}^{\prime}$, and
otherwise $wa_{k}=_{Geo}w_{pref}(w_{suff}^{\prime}a_{k})$.

The word $w_{pref}$ is now shortlex because $a_{i}$ and $a_{j}$ do not
commute, while any cancellation could already have happened in $w$. Similarly,
any cancellation in $w_{suff}^{\prime}$ could already have happened in $w$, so
that $w_{suff}^{\prime}$ is geodesic but not necessarily shortlex. We
therefore replace $w_{suff}^{\prime}$ with the shortlex rearrangement of equal
length, and term this word $w_{suff}$.

Uniqueness is then shown by a straightforward induction on length. ∎

It is immediate that a shortlex word is a suffix (e.g. for itself) if and only
if it cannot be rearranged to begin with either $a_{i}$ or $a_{j}$. When we
say that a word is a suffix, we mean it in this sense, because this notion is
independent of any attached prefix.

The existence and uniqueness of the prefix-suffix decomposition can also be
shown as follows: re-order the alphabet so that $a_{i}$ and $a_{j}$ are the
first two letters (the order between the two does not matter since they do not
commute). Then $w$ remains geodesic but is not necessarily shortlex.
Rearranging $w$ to be shortlex in this new letter order requires moving each
copy of $a_{i}$ and $a_{j}$ as early in the word as possible, so that $w$
begins with a word consisting of an alternation of $a_{i}$ and $a_{j}$. The
maximal such word is the prefix, and the remainder of the word is the suffix.
In particular, if $\\{i,j\\}=\\{1,2\\}$, the prefix and suffix can be read off
directly from the shortlex word $w$.

######  Lemma 4.1.3.

Let $w$ be shortlex and $w_{pref}w_{suff}$ be its prefix-suffix decomposition.
Then $b_{\gamma}(w)=|w_{pref}|+|w_{suff}|$ if the first letter of $w$ is
$a_{j}$, or $b_{\gamma}(w)=-|w_{pref}|+|w_{suff}|$ if the first letter of $w$
is $a_{i}$.

###### Proof.

To compute the Busemann Function, we only need to compute word lengths.
Therefore, $w$ need not be in shortlex order, so we may as well work with
$w_{pref}w_{suff}$. Since $a_{i}$ and $a_{j}$ do not commute, $w_{pref}$ can
be of the form $a_{i}a_{j}a_{i}a_{j}...$ or $a_{j}a_{i}a_{j}a_{i}...$. In the
first case, we compute

$b_{\gamma}(w)=\lim_{n\to\infty}|(a_{i}a_{j})^{-n}w_{pref}w_{suff}|-2n$

$(a_{i}a_{j})^{-1}=a_{j}a_{i}$, so that for $n$ sufficiently large, the
entirety of $w_{pref}$ cancels out of the expression
$(a_{i}a_{j})^{-n}w_{pref}w_{suff}$. The expression therefore has length
$2n-|w_{pref}|+|w_{suff}|$ at most. It cannot have shorter length since any
further cancellation would come between a letter $a_{i}$ or $a_{j}$ in
$(a_{i}a_{j})^{-n}$ and a letter at the start of $w_{suff}$, which is
impossible by assumption. Therefore, $b_{\gamma}(w)=-|w_{pref}|+|w_{suff}|$.

In the case where $w_{pref}$ begins with $a_{j}$,

$b_{\gamma}(w)=\lim_{n\to\infty}|(a_{i}a_{j})^{-n}w_{pref}w_{suff}|-2n$

and no cancellation is possible at all in this expression. It is immediate
that $b_{\gamma}(w)$ is the limit of a sequence whose value is constantly
$|w|=|w_{pref}|+|w_{suff}|$. ∎

Following this lemma, a prefix beginning with $a_{i}$ is termed a negative
prefix while a prefix beginning with $a_{j}$ is a positive prefix. Given a
positive prefix, we can make it more positive by adding letters on the end or
more negative by deleting its last letters, and vice versa for negative
prefixes. Every negative prefix is more negative than the empty prefix, and
every positive prefix is more positive than the empty prefix.

As a consequence of this description, it is usually better to keep track of
suffixes. If we know a value for $b_{\gamma}$, then every word on the
horosphere of this value is determined uniquely by its suffix. It will follow
from the next lemma that we can generate suffixes as the accepted language of
an FSM derived from the shortlex machine. When possible, we will try to
perform the computations in this paper by taking only the suffix as an input
because it is faster and requires less memory to generate them.

######  Lemma 4.1.4.

There is a finite-state machine $M_{Suff}$ whose accepted language consists of
shortlex words $w$ not equal to any geodesic word beginning with $a_{i}$ or
$a_{j}$.

###### Proof.

Let $M_{lex}$ denote the shortlex machine for $W_{\Gamma}$, with starting
state $\emptyset$. We will take the vertex set of $M_{Suff}$ to be that of
$M_{lex}$ times the power set $\mathscr{P}(\\{a_{i},a_{j}\\})$. The
$M_{lex}$-states will keep track of shortlex-forbidden letters, while the
subset of $\\{a_{i},a_{j}\\}$ will keep track of which letters, if written at
this stage, could commute to reach the beginning of the word. The starting
state will be the pair $\emptyset\times\\{a_{i},a_{j}\\}$.

Given a vertex $(S,P)$, we allow outgoing edges labeled by every letter
outside of $S\cup P$. The update rule is $(S,P)\to_{a_{l}}\left(\bigl{(}S\cap
star(a_{l})\bigr{)}\cup\\{a_{l}\\}\cup star_{<}(a_{l}),P\cap
star(a_{l})\right)$. That is, the state $S$ updates as usual for the shortlex
machine, and if $P$ was the subset of $\\{a_{i},a_{j}\\}$ commuting with every
letter read so far, then we remove a letter from $P$ when it does not commute
with the new input. We will refer to $P_{Suff}(w)$ as the $P$-component of
$M_{Suff}(w)$, so that $M_{Suff}(w)=M_{lex}(w),P_{Suff}(w)$

As in remark 2.11 we prune this graph of any vertices that cannot be reached
from the starting state.

The fact that this machine only accepts shortlex words in ensured by the first
coordinate, while the fact that these words are not allowed to have copies of
$a_{i}$ or $a_{j}$ that commute to the front is guaranteed by the second
coordinate. ∎

In the event that $\\{i,j\\}=\\{1,2\\}$, $M_{suff}$ has a particularly
convenient form. As mentioned, in such a case the shortlex order already
prevents nonempty words from being reordered to begin with either $a_{1}$ or
$a_{2}$. Therefore, $M_{suff}$ is just $M_{lex}$ with 2 edges deleted from
those exiting the starting state (those labeled by $a_{1}$ and $a_{2}$). It is
an inconvenient fact that, in general, it takes quadratic time to convert
between a shortlex word and its prefix-suffix form. Therefore, $M_{suff}$
rather than $M_{lex}$ is the correct machine to generate the vertex set of
Rips graph.

As a result of this lemma, we can generate a large set of points on a
horosphere of a fixed $b_{\gamma}$ value by taking the set of all suffixes of
length at most $k$, and then adding appropriate positive or negative prefixes
to achieve the desired $b_{\gamma}$ value. Next, we must compute the edge set
in the Rips graph for each point. While it is straightforward to check the
distance between each pair of vertices, this will be extremely time-consuming.
It will be more efficient to generate the edges from the ground up.

Recall that the $k$-Rips graph on a metric space $(X,d)$ consists of the space
$X$ with edges between points at distance at most $k$. We think of this graph
as describing what it means to move along a subspace of a metric space. Our
space $X$ will be a horosphere, which is a discrete set of points. Therefore,
we cannot make talk about paths staying inside the horosphere, but we can
demand that they only make short jumps. One might imagine zooming out from
such a picture to see this limit to a continuous path.

We will focus primarily on the $2$-Rips graph. Note that it is not at all
obvious that this graph should be connected.

Given a word $w$, the set of words $v$ at distance at most $2$ from $w$ is
$\\{wa_{k}a_{l}\\}$, but most of these words are not on the same horosphere as
$w$ because typically multiplying on the right by two letters lengthens the
suffix by $2$ while preserving the prefix. To generate these edges more
efficiently, it will be helpful to consider two separate cases: edges between
words $w$ and $v$ with the same prefix (and therefore the same length), edges
between words $w$ and $v$ with suffixes of different length.

###  4.2. Edges between words of the same suffix length

If $w$ and $v$ have the same length of suffix, then they necessarily have the
same prefix. So $w^{-1}v=w_{suff}^{-1}v_{suff}$ is a word of length 2, and
$|w_{suff}|=|v_{suff}|$. So given $w_{suff}$, we need to delete one letter and
then add one on. We first address the deletion step.

######  Lemma 4.2.1.

Let $w$ be a shortlex word, and let $a_{k}$ be a last letter in a geodesic
representative of $w$. Then the word $w_{k}$ obtained from $w$ by deleting the
last copy of $a_{k}$ is shortlex. Moreover, if $w$ is a suffix, so is $w_{k}$

###### Proof.

Suppose $w_{k}$ is not shortlex. Then there is some $a_{l}$ so that, in
$w_{k}$, this copy of $a_{l}$ either cancels or commutes earlier in a
favorable way. But then since $a_{k}$ is a last letter, either $a_{k}$ and
$a_{l}$ commute, or this copy of $a_{l}$ precedes the deleted copy of $a_{k}$.
In both cases, this cancelation or rearrangement is possible in $w$ so that
$w$ was not shortlex.

Suppose $w_{k}$ is shortlex but not a suffix. The argument is the same: there
is a copy of $a_{i}$ or $a_{j}$ that commutes to the beginning of the word.
Since $a_{k}$ is a last letter, either $a_{k}$ commutes with this copy of
$a_{i}$ or $a_{j}$, or the copy of $a_{i}$ or $a_{j}$ appears before $a_{k}$,
and in either case this rearrangement is possible in $w$. ∎

Next, we address the step of adding a letter. A priori, it suffices to write a
letter $a_{l}$ after $w_{k}$ permitted by $M_{GeoSuff}(w_{k})$, and then
perform a shortlex reordering. However, shortlex sorting a string of length
$n$ takes, a priori, $O(n^{2})$ steps. Here we give an operation that uses the
existing order on $w_{k}$ to alphebatize $w_{k}a_{l}$ in linear time.

######  Lemma 4.2.2.

Suppose $w$ is a shortlex suffix and $a_{l}$ is permitted by $M_{GeoSuff}(w)$.
The shortlex suffix equivalent to $wa_{l}$ can be computed in $O(|w|)$ steps.

###### Proof.

Write $w=a_{i_{1}}...a_{i_{n}}$. We read the letters of $w$ last to first.
When we read $a_{i_{k}}$, if $a_{l}\in Star_{<}(a_{i_{k}})$, we remember the
value $k$ as the current preferred insertion point of $a_{l}$. If $a_{i_{k}}$
does not commute with $a_{l}$, the algorithm terminates and outputs
$a_{i_{1}}...a_{i_{k}}...a_{i_{m-1}}a_{l}a_{i_{m}}...a_{i_{n}}$ where
$a_{i_{m}}$ is the preferred insertion point of $a_{l}$.

There are no favorable rearrangements of $a_{l}$ by assumption. Since the
remaining letters $a_{i_{1}},...a_{i_{n}}$ appear in the same order as in $w$,
which is shortlex, any rearrangements of these letters are necessarily
unfavorable. Therefore, this algorithm outputs a shortlex word. ∎

As a result, we can generate each word of the same suffix length as $w$ that
is within distance $2$ of $w$ quickly and with minimal duplication.

######  Lemma 4.2.3.

Let $w=_{Geo}w_{pref}w_{suff}$ be a word on the horosphere $b_{\gamma}=m$. The
set of words $\\{v:v_{pref}=w_{pref},b_{\gamma}(w)=b_{\gamma}(v),\text{and
}d(w,v)=2\\}$ can be computed in linear time with respect to the length of
$w$.

###### Proof.

We wish to delete a letter at the end of $w_{suff}$, for which it suffices to
multiply by a letter that $w_{suff}$ could be rearranged to end with. We
therefore compute $M_{Geo}(w_{suff})$. For each $a_{k}$ in
$M_{Geo}(w_{suff})$, we obtain $w_{k_{suff}}$ with $w_{k}$ as in Lemma 4.2.1.
These are again shortlex suffixes. We wish to enumerate every shortlex suffix
$w_{k_{suff}}a_{l}$. We therefore take, for each $w_{k_{suff}}$, the set of
successors to $w_{k_{suff}}$ in $M_{GeoSuff}$ and reorder according to Lemma
4.2.2.

There are at most $Clique(\Gamma)$ words $w_{k}$ each with at most $|V|-1$
successors. So we have a bounded number of strings of length $|w_{suff}|-1$ to
reorder, which takes $O(|w_{suff}|)=O(|w|)$ steps. ∎

Note that for each $w_{k_{suff}}$, $w_{suff}$ is the shortlex form of
$w_{k_{suff}}a_{k}$ so that this algorithm also returns $|M_{Geo}(w_{suff})|$
copies of the degenerate edge $(w_{suff},w_{suff})$. For convenience, we will
delete these edges, which does not change the asymptotic time complexity.

###  4.3. Edges between words of different suffix length

We will suppose that $w$ and $v$ are words on the same horosphere, and WLOG
that $v$ has the shorter suffix. If the prefix of $w$ is positive or empty,
then it gets one letter longer when the suffix shortens in order to preserve
the Busemann function. If the prefix of $w$ is negative, then it shortens in
order to preserve the Busemann function of $w$.

We describe these cases in the following lemma.

######  Lemma 4.3.1.

Let $w=_{Geo}w_{pref}w_{suff}$. Then the set of edges between $w$ and words
$v$ such that $|v_{suff}|=|w_{suff}|-1$ can be determined in linear time with
respect to the length of $w$ based only on $w_{suff}$ and $b_{\gamma}(w)$.

Of course, if one knows $w_{suff}$ and $b_{\gamma}(w)$, then one can
reconstruct $b_{\gamma}(w)$. The point is to emphasize that we can write such
an algorithm where we take as inputs an integer and a desired set of suffixes
to work with. We do not need to store the redundant information of the prefix
of each word.

###### Proof.

If $b_{\gamma(w)}\geq|w_{suff}|$, then the prefix of $w$ is non-negative
(beginning with $a_{j}$ or empty), and a letter must be added. If
$b_{\gamma(w)}-|w_{suff}|$ is even, then $w_{pref}$ ends with a copy of
$a_{i}$, so a copy of $a_{j}$ must be added, while if
$b_{\gamma(w)}-|w_{suff}|$ is odd, then $w_{pref}$ ends with a copy of $a_{j}$
so $a_{i}$ that must be added.

So, letting $k=i$ in the first case or $j$ in the second case, $v$ so that
$wa_{k}a_{l}=_{Geo}v$ or $wa_{l}a_{k}=_{Geo}v$ and so that
$w_{suff}a_{l}=_{Geo}v_{suff}$ where $a_{l}$ cancels with a letter in
$w_{suff}$. This means that there is an $a_{l}$ present in $w_{suff}$, so that
if $a_{k}$ does not commute with $a_{l}$, then in the expression
$wa_{k}a_{l}$, $a_{k}$ cannot reach $w_{pref}$. So in fact we only need to
consider the case $wa_{l}a_{k}=_{Geo}v$.

In order for $a_{l}$ to cancel with a letter of $w_{suff}$, $a_{l}\in
M_{Geo}(w_{suff})$. For each such $a_{l}$, we obtain a candidate suffix
$v_{suff}$ by deleting the last copy of $a_{l}$ in $w_{suff}$. If $a_{k}$
commutes with each remaining letter, i.e. if $a_{k}\in M_{\\{a_{i},a_{j}\\}}$,
then $wa_{l}a_{k}=_{Geo}v$ is a word of the desired form, and we keep the
suffix $v_{suff}$. Otherwise we discard it. One sees immediately that this
takes only linear time.

The case where $b_{\gamma(w)}<|w_{suff}|$ is equivalent. ∎

Combining all of the above, we have a complete algorithm for generating the
$2$-Rips graph on a subset of a horosphere.

######  Theorem 4.3.2.

Let $\Gamma$ be a graph satisfying the standing assumptions. Let $a_{i}$ and
$a_{j}$ two non-adjacent letters of $\Gamma$, and let
$\gamma=(a_{i}a_{j})^{\infty}$. Take $k$ to be an integer. Then $n$ vertices
of the $2$-Rips graph on horosphere $b_{\gamma}^{-1}(k)$ and the edges between
them can be generated by an algorithm whose runtime is $O(n\log(n))$.

###### Proof.

Using $M_{suff}$, we generate the set of suffixes of length at most $m$. The
number $n$ of these is exponential in $m$, so that this takes time asymptotic
to $O(n\log(n))$. For each such vertex, it takes $O(\log(n))$ steps to
generate all outgoing edges to suffixes of the same length by Lemma 4.2.3, and
$O(\log(n))$ steps to generate the outgoing edges to suffixes with different
length by Lemma 4.3.1. ∎

###  4.4. Connectivity of the Rips graph

We are almost prepared to show that the 2-Rips graph is connected. First we
will first need a technical lemma about the defining graph $\Gamma$.

######  Lemma 4.4.1.

Let $\Gamma$ be a graph satisfying the standing assumptions, and let
$\Gamma^{\prime}\subset\Gamma$ be a path component of
$\Gamma\setminus\\{a_{i},a_{j}\\}$. Then

  * •

the subgraph $K$ of vertices in $\Gamma^{\prime}$ adjacent to both $a_{i}$ and
$a_{j}$ is complete.

  * •

If $\Gamma^{\prime}\neq K$ then $\Gamma^{\prime}$ contains both vertices not
adjacent to $a_{i}$ and vertices not adjacent to $a_{j}$, and every vertex
adjacent to $a_{i}$ but not $a_{j}$ is connected to a vertex adjacent to
$a_{j}$ but not $a_{i}$ (and vice versa) by a path in
$\Gamma^{\prime}\setminus K$.

###### Proof.

For the first part, recall that $a_{i}$ and $a_{j}$ are nonadjacent. So if
$a_{k}$ and $a_{l}$ are adjacent to $a_{i}$ and $a_{j}$, the four vertices
will form an induced square subgraph unless $a_{k}$ and $a_{l}$ are adjacent.

For the second part, suppose $\Gamma^{\prime}$ contains a vertex $a_{k}$
adjacent to $a_{i}$ but not $a_{j}$. By assumption,
$\Gamma\setminus(K\cup\\{a_{i}\\})$ is connected, so that there is a path
between $a_{k}$ and $a_{j}$ which we may take not to contain $a_{j}$ so that
it stays in $\Gamma^{\prime}$. But then the second-last vertex in this path is
both connected to $a_{k}$ by a path in $\Gamma^{\prime}\setminus K$ adjacent
to $a_{j}$, and not adjacent to $a_{i}$. ∎

In order prove the connectedness of the Rips graph, it will be convenient to
have another FSM prepared. When proving connectedness, we will write a
geodesic suffix $a_{i_{1}}a_{i_{2}}...$ and not care about a shortlex
reordering. This is because in order to talk about paths in the Rips graph, we
will need to study edge paths along which the $k^{th}$ letter changes in a
prescribed way. It would be equivalent but much more painful notationally if
the $k^{th}$ letter were forced to wander around the suffix according to the
shortlex order.

######  Lemma 4.4.2.

There is a finite-state machine $M_{GeoSuff}$ whose accepted language consists
of geodesic words $w$ not equal to any geodesic word beginning with $a_{i}$ or
$a_{j}$.

Moreover, this finite-state machine has no dead-end states (i.e. states in
which no letter can be written).

Notice the slight difference from the statement of Lemma 4.1.4.

###### Proof.

We mimic the construction of $M_{Suff}$, but use $M_{Geo}$ rather than
$M_{lex}$ as our starting point. The states are
$M_{GeoSuff}(w)=(M_{Geo}(w),P_{Suff}(w))$, and the starting point
$(\emptyset,\\{a_{i},a_{j}\\})$. The proof that the machine accepts the
desired language is the same as the proof of Lemma 4.1.4, replacing the word
“shortlex” with “geodesic”.

The set of edges exiting a given state $M_{GeoSuff}(w)$ is
$\Gamma\setminus(M_{Geo}(w)\cup P_{Suff}(w))$. So there is an outgoing edge as
long as $\Gamma$ is not the union of a clique and a pair of letters that are
not adjacent. This is guaranteed by the standing assumption that there is no
separating clique in $\Gamma$. ∎

The following tool will be used repeatedly in proving connectivity of the Rips
graph.

######  Lemma 4.4.3.

Suppose $w=a_{j_{1}}...a_{j_{k}}$ is a geodesic suffix so that
$\Gamma\setminus M_{GeoSuff}(v)$ is connected whenever $v$ is a successor to
$w$. Then there is a connected subgraph of the $2$-Rips graph on a horosphere
consisting of the set of words of length $m$ with geodesic suffixes beginning
$a_{j_{1}}...a_{j_{k}}$.

The slightly artificial assumption that $\Gamma\setminus M_{GeoSuff}(v)$
always remains connected is chosen to cover two cases: one where
$M_{GeoSuff}(w)$ is a clique, and one where
$\Gamma\setminus(\\{a_{i},a_{j}\\}\cup K^{\prime}$ is connected for every
$K^{\prime}\subset K$. In the former case, either $a_{i}$ or $a_{j}$ cannot
commute to the start of the word and will not be able to regardless of which
letters continue to be written. In the latter case, $\Gamma\setminus
M_{GeoSuff}(v)$ will always be connected regardless of whether it is a
successor to $w$.

###### Proof.

We prove this by induction on $k$. If $k=m-1$, an edge is guaranteed by Lemma
4.2.3. So all we need to show is that if the result is true for $k=n+1$ then
it is true for $k=n$.

So suppose the graph whose vertices are the words whose geodesic suffixes
begin $a_{j_{1}}...a_{j_{n+1}}$ is connected. Then from each word
$a_{j_{1}}....a_{j_{m}}$ there is a path to each geodesic suffix
$a_{j_{1}}...a_{j_{n+1}}a_{j_{n+2}^{\prime}}...a_{j_{m^{\prime}}}$. Choose a
path from
$a_{j_{n+1}}=a_{j_{n+1_{0}}},a_{j_{n+1_{1}}}...a_{j_{n+1_{l}}}=a_{j_{n+1^{\prime}}}$
in $\Gamma\setminus M_{GeoSuff}(a_{j_{1}}...a_{j_{n}})$. By assumption, we can
find a path to a geodesic suffix
$a_{j_{1}}...a_{j_{n+1}}a_{j_{n+1_{1}}}...a_{j_{m}^{\prime}}$ as long as there
is a geodesic suffix of length $m$ beginning
$a_{j_{1}}...a_{j_{n+1}}a_{j_{n+1_{1}}}$. This is guaranteed by the assertion
in Lemma 4.4.2 that $M_{GeoSuff}$ does not have dead ends. But then since
$a_{j_{n+1}}$ and $a_{j_{n+1_{1}}}$ commute, we can write this as the geodesic
suffix $a_{j_{1}}...a_{j_{n+1_{1}}}a_{j_{n+1}}...a_{j_{m}^{\prime}}$.

If we do this $l$ times, we obtain a word that with suffix begin
$a_{j_{1}}...a_{j_{n}}a_{j_{n+1}^{\prime}}$. Doing this one more time then
gives any word whose suffix begins
$a_{j_{1}}...a_{j_{n}}a_{j_{n+1}^{\prime}}$. Since $a_{j_{n+1}^{\prime}}$ was
arbitrary, it follows that in $l+1$ steps we can get to every word beginning
$a_{j_{1}}...a_{j_{n}}$ is connected. ∎

######  Corollary 4.4.4.

Consider all the graphs $\Gamma\setminus K^{\prime}$ where $K^{\prime}$ ranges
over all complete subgraphs of $\Gamma$, and all the path components of
$\Gamma\setminus(\\{a_{i},a_{j}\\}\cup K^{\prime})$ where $K^{\prime}$ ranges
over subgraphs of the clique $K$ adjacent to both $a_{i}$ and $a_{j}$. Let $D$
denote the maximum diameter of any such graph considered with its path metric,
not with the induced metric of $\Gamma$. Then if
$M_{GeoSuff}(a_{i_{1}}....a_{i_{k}})$ is a clique, the diameter of the set of
words whose (geodesic, not necessarily shortlex) suffixes have length $m$ and
begin with $a_{i_{1}}....a_{i_{k}}$ is at most $(D+1)^{m-k-1}$ (again where
this set is given its intrinsic path metric).

The need for $D$ to dominate the diameter of any component of
$\Gamma\setminus(\\{a_{i},a_{j}\\}\cup K^{\prime})$ will not be used in this
proof. It is included only to have a single constant in certain upper bounds
in the next subsection.

###### Proof.

If $k=m-1$, then the subgraph is a clique by Lemma 4.2.3. So suppose diameter
of the subgraph of words beginning $a_{i_{1}}...a_{i_{n}}b$ is at most
$D^{m-n-2}$ for each choice of $b$. Then the previous proof gives a path
between any two points whose suffixes begin $a_{i_{1}}...a_{i_{n}}$ with $l+1$
subpaths where $l$ is a path in a graph $\Gamma\setminus K^{\prime}$. We can
therefore take $l$ to be at most $D$. Each of these subpaths lies in a
subgraph of words whose suffixes begin with $a_{i_{1}}...a_{i_{n+1_{l-1}}}$,
and therefore can be taken to have at length at most $(D+1)^{m-n-2}$.
Therefore, the total path length is at most $(D+1)^{m-n-1}$. ∎

As a consequence, we see that all the $k$-Rips graphs on the same horosphere,
for any $k$, are bi-Lipschitz equivalent.

######  Proposition 4.4.5.

Let $k\geq 2$. The path metrics on any horosphere induced by the $k$-Rips
graph and the $2$-Rips graph are bi-Lipschitz equivalent.

###### Proof.

One direction is clear, because points at distance at most $2$ from one
another are therefore at most $k$ from one another. So the $k$-Rips graph
contains every edge of the $2$-Rips graph, and therefore the distance induced
from the $k$-Rips graph is bounded above by that of the $2$-Rips graph. So it
remains to show that the path distance in the $2$-Rips graph is at most
$L_{k}$ times the distance in the $k$-Rips graph for some constant $L_{k}$. It
suffices to do this edgewise, i.e., that every edge in the $k$-Rips graph has
at most distance $L_{k}$ in the $2$-Rips graph.

We will need to consider the following cases of edges in the $k$-Rips graph:
edges between words with the same suffix length, edges between words whose
suffix length differs by $1$, and edges between words whose suffix length
differs by at least $2$.

Case I: Same suffix length

Suppose $|w_{suff}|=|v_{suff}|$, so that
$w^{-1}v=_{Geo}w_{suff}^{-1}v_{suff}$, which reduces to a word of length at
most $k$. Then $w_{suff}w^{\prime}=_{Geo}v_{suff}$ for some word $w^{\prime}$
of length at most $k$. $w^{\prime}$ then has even length, and half of its
letters cancel with letters in $w_{suff}$. Write
$w_{suff}=_{Geo}a_{i_{1}}...a_{i_{l}}a_{i_{l+1}}...a_{i_{m}}$ where the
letters past $a_{i_{l}}$ cancel with $w^{\prime}$. If $l\geq clique(\Gamma)$,
then $M_{GeoSuff}(a_{i_{1}}...a_{i_{l}})$ is necessarily a clique. Since
$v_{suff}$ begins with $a_{i_{1}}...a_{i_{l}}$, then Corollary 4.4.4 shows
that the two at distance at most $(D+1)^{m-l-1}$ in the $2$-Rips graph. Since
$m-l=\frac{k}{2}$, this provides the desired bound.

There are only finitely many words for which $l=m-\frac{k}{2}<clique(\Gamma)$,
i.e. words whose suffix lengths are at most $clique(\Gamma)+\frac{k}{2}$. The
maximum $2$-Rips graph distance between two such points whose Cayley graph
distance is at most $k$ is therefore bounded.

Case II: Suffix length differing by 1

This is the hardest case. Suppose $|v_{suff}|=|w_{suff}|+1$, and WLOG let
$w_{pref}a_{i}=v_{pref}$. Once again there is a word $w^{\prime}$ of length at
most $k$ so that $ww^{\prime}=_{Geo}v$. There is an uncancelled prefix copy of
$a_{i}$ in $v$, as well as at most $\frac{k}{2}$ uncancelled suffix letters in
$v$ and at most $\frac{k}{2}-1$ uncancelled suffix letters of $w$. So as
before we write $w_{suff}=_{Geo}a_{i_{1}}...a_{i_{l}}a_{i_{l+1}}...a_{i_{m}}$
where the letters after $a_{i_{l}}$ cancel with letters of $w^{\prime}$, and
the first $l$ letters match letters in $v_{suff}$ and commute with $a_{i}$.

As before, as long as $l>clique(\Gamma)$, $M_{GeoSuff}(a_{i_{1}}...a_{i_{l}})$
is a clique. We then apply Corollary 4.3.1 to the set of words beginning with
these letters of length $m$ to find that the set has diameter at most
$(D+1)^{\frac{k}{2}-2}$. In particular, after distance at most
$(D+1)^{\frac{k}{2}-2}$ we can reach a new word where every suffix letter
commutes with $a_{i}$. We can then take a single edge to a word whose suffix
length matches that of $v$ by Lemma 4.3.1. Then a further application of
Corollary 4.3.1 to the set of suffixes of length $m+1$ beginning
$a_{i_{1}}...a_{i_{l}}$ allows us to reach $v$ in another
$(D+1)^{\frac{k}{2}-1}$ steps. So the total distance is bounded by
$(D+1)^{\frac{k}{2}-2}+1+(D+1)^{\frac{k}{2}-1}$.

Once again, the set of words $w$ for which
$l=|w_{suff}|-(\frac{k}{2}-1)<clique(\Gamma)$ is finite, so we have an
immediate bound on the lengths of $k$-Rips graph edges incident to these
vertices.

Case III: Suffix length differing by at least 2

Suppose $w$ and $v$ are at distance at most $k$, and
$|v_{suff}|-|w_{suff}|\geq 2$. Then there is an uncancelled prefix copy of
both $a_{i}$ and $a_{j}$ in $w^{-1}v$. By Lemma 4.4.1, there are at most
$clique(\Gamma)$ letters from $w_{suff}$ that can cancel with letters of
$v_{suff}$. Therefore,
$|v_{suff}|-|w_{suff}|+|w_{suff}|+|v_{suff}|-2clique(\Gamma)\leq k$.
Cancelling, $2|v_{suff}|\leq k+2clique(\Gamma)$. Since $v$ had the longer
suffix than $w$, we conclude that there are again only finitely many such
edges, and attain a maximum length of such an edge in the $2$-Rips graph. ∎

We now come to the main result of the section. We will present an alternate,
more direct proof under an additional assumption after this one.

######  Proposition 4.4.6.

Let $\Gamma$ be a graph satisfying the standing assumptions, and let $a_{i}$
and $a_{j}$ be non-adjacent vertices. Let $\gamma$ be the geodesic ray
$(a_{i}a_{j})^{\infty}$, and let $w=_{Geo}w_{pref}w_{suff}$ be an element of
$W_{\Gamma}$. Denote $G$ as the $2$-Rips graph on
$b_{\gamma}^{-1}(b_{\gamma}(w))$, the horosphere containing $w$. Let $v$ be
the word with empty suffix in $G$. Then there is a path in $G$ from $v$ to
$w$.

###### Proof.

Let $|w|=m$. Then there is an edge between $w$ and $v$ in the $m$-Rips graph,
so they are at distance $1$ in that graph. Since the $m$-Rips graph and the
$2$-Rips graph are Bi-Lipschitz, the distance between $w$ and $v$ in the
$2$-Rips graph is bounded, and therefore a path exists. ∎

Since there is a point in the horosphere to which every other point is
connected by a path, we see immediately that the horosphere is connected.

######  Theorem 4.4.7.

The $2$-Rips graph on a horosphere is connected.

Since the word on the horosphere of empty suffix is connected to every other
word, the horosphere is connected. However, as shown in the claim, depending
on the defining graph $\Gamma$ it is sometimes possible to connect vertices
without going through this word. The following proposition presents a simpler
proof of connectivity under an additional assumption. it is not immediately
obvious if it provides a better distance bound.

######  Proposition 4.4.8.

Suppose that $\Gamma\setminus(\\{a_{i},a_{j}\\}\cup K^{\prime})$ is connected
for each $K^{\prime}$ a (potentially empty) subclique of $K$ (where $K$ is
again the set of letters commuting with both $a_{i}$ and $a_{j}$). Then the
words on a given horosphere with suffix $a_{i_{1}}...a_{i_{n}}$ and
$a_{j_{1}}...a_{j_{m}}$ are connected through a path of words that of suffix
length at least $\min\\{n,m\\}$.

###### Proof.

By assumption, $\Gamma\setminus M_{GeoSuff}(w)$ is connected for each geodesic
suffix $w$. Therefore, we will again use Lemma 4.4.3.

For the words of suffix length $m$, the empty string satisfies the assumptions
of Lemma 4.4.3, so they are all connected. WLOG suppose $m<n$. Then $n-m$
times we use Lemma 4.4.3 to reach words satisfying the assumptions of Lemma
4.3.1, followed by one additional time to reach the word
$a_{i_{1}}...a_{i_{n}}$. ∎

###  4.5. Distortion of the Rips Graph

In this subsection, we will give an upper and lower bound on the exponential
distortion of geodesic paths in the Rips graph with respect to geodesic paths
in the Cayley Graph.

######  Theorem 4.5.1.

Let $\Gamma$ be a graph satisfying the standing assumptions, and let $a_{i}$
and $a_{j}$ be non-adjacent vertices. There are constants $C_{i}$ for
$i=1,2,3,4$ depending only on $\Gamma$ so that the following holds. Let
$d_{H}$ denote the combinatorial distance in the $2$-Rips graph on
$b_{\gamma}^{-1}(k)$, and $d$ denote the distance in the Cayley graph. Then
for any $w$, and $v$ on the $k$-horosphere,

$C_{1}C_{2}^{d(w,v)}\leq d_{H}(w,v)\leq C_{3}C_{4}^{d(w,v)}$

.

The upper bound follows from the methods of the previous section.

######  Proposition 4.5.2.

Let $w$ and $v$ be shortlex words with $b_{\gamma}(w)=b_{\gamma}(v)=k$. Denote
$d$ the distance in the Cayley graph and $d_{H}$ the path distance in the
$2$-Rips graph on the horosphere $b_{\gamma}^{-1}(k)$. Then $d_{H}(w,v)\leq
O_{\Gamma}(1)(D+1)^{d(w,v)}+d(w,v)+O_{\Gamma}(1)$.

Of course, the addition of the linear term $d(w,v)$ makes no difference, since
both $D+1$ and the distance between points is at least $1$. So we could delete
this term, but will keep it for convenience. In fact we could also subsume the
constant term into the exponential if we desired.

The proof of this proposition is somewhat lengthy and involves counting the
steps in the proofs of Propositions 4.4.6 and 4.4.8. However, when exactly we
can use which argument is somewhat subtle, and requires breaking into cases
that will likely be hard to follow for the reader unfamiliar with the JSJ
theory of RACGs. Therefore, some explanation is in order. We will not prove
the content of this remark, since it is not used in the sequel and is meant
only to aid the intuition.

######  Remark 4.5.3.

In the boundary $\partial W_{\Gamma}$, the pair $\\{\gamma(\pm\infty)\\}$ is a
cut pair exactly if it is the boundary of a 2-ended group $H$ so that
$W_{\Gamma}\cong G_{1}*_{H}G_{2}$ for groups $G_{1}$ and $G_{2}$ properly
containing $H$. $H$ can be taken to be the RACG generated by some subgraph of
$\Gamma$, necessarily containing $a_{i}$ and $a_{j}$, as well as some
subclique $K^{\prime}$ of the clique $K$ of vertices adjacent to $a_{i}$ and
$a_{j}$, such that the graph $\Gamma\setminus(\\{a_{i},a_{j}\\}\cup
K^{\prime})$ is disconnected.

The group $H_{max}=\langle\\{a_{i},a_{j}\\}\cup K\rangle$ is the maximal
2-ended subgroup whose endpoints are $\\{\gamma(\pm\infty)\\}$, and thus the
stabilizer of $\\{\gamma(\pm\infty)\\}$ in $W_{\Gamma}$. If $\Gamma_{1}$ is a
path component of $\Gamma\setminus(\\{a_{i},a_{j}\\}\cup K)$, and $K_{1}$ is
the clique of vertices in $K$ adjacent to vertices in $\Gamma_{1}$, then
$\Gamma_{1}$ is also a path component of
$\Gamma\setminus(\\{a_{i},a_{j}\\}\cup K_{1})$. By Lemma 4.4.1, $\Gamma_{1}$
contains vertices adjacent to $a_{i}$ and $a_{j}$. Denote
$H=\langle\\{a_{i},a_{j}\\}\cup K_{1}\rangle$, and
$G_{1}=\langle\Gamma_{1}\cup K_{1}\cup\\{a_{i},a_{j}\\}\rangle$. The
connectivity assumptions guarantee that $G_{1}$ is a 1-ended group in which
$\gamma(\pm\infty)$ is not a cut pair. The vertices in $K\setminus K^{\prime}$
generate a finite subgroup of $H_{max}$. In the amalgamation
$H_{max}*_{H}G_{1}$, left multiplying by a product of elements in $K\setminus
K_{1}$ fixes $\gamma(\pm\infty)$ (since these elements are in $H_{max}$, a
2-ended subgroup wtih $\gamma(\pm\infty)$ as its boundary), but sends $G_{1}$
to a coset that is not at finite distance. As a result,
$\partial(H_{max}*_{H}G_{1})$ has $2^{|K\setminus K_{1}|}$ copies of $\partial
G_{1}$ glued along $\gamma(\pm\infty)$. Moreover,
$\partial(H_{max}*_{H}G_{1})$ embeds into $\partial(W_{\Gamma})$. Applying the
same logic to each path component $\Gamma_{l}$ of
$\Gamma\setminus(\\{a_{i},a_{j}\\}\cup K)$ shows that $\gamma(\pm\infty)$
disconnect the boundary into $\sum_{l}2^{|K\setminus K_{l}|}$ path components.
These components of $\partial W_{\Gamma}\setminus\gamma(\pm\infty)$ are
therefore parameterized by a subgraph $\Gamma_{l}$ and a subset of $K_{l}$.

The point of the following proof is that Rips graph on a horosphere shows a
coarse version of these same properties. The vertex $w_{0}$ with empty suffix
is a member of the subgroup $\langle a_{i},a_{j}\rangle$ and the collection
$S$ of vertices with suffixes spelled in the letters of $K$ make up a “coarse
cut point” in the horosphere (i.e. a connected set of bounded diameter
disconnecting the horosphere into unbounded components) if and only if
$\gamma(\pm\infty)$ are a cut pair in $\partial W_{\Gamma}$. There are again
$\sum_{l}2^{|K\setminus K_{l}|}$ different components. We will show that each
suffix outside the coarse cut point $S$ determines a subgraph $\Gamma_{l}$ and
a subset of $K\setminus K_{l}$. Two points on the horosphere are connected by
a path that does not go near $w_{0}$ exactly when their suffixes determine the
same subgraph $\Gamma_{l}$ and subset of $K_{l}$. Such pairs of points will
admit a path like the one described in the proof of Proposition 4.4.8, while
any other pair essentially requires a concattenation of two of the paths
described in the proof of Proposition 4.4.6.

Crucially to this proof, two points on a horosphere that are close in the
Cayley graph metric will necessarily admit one of the shorter paths described
in Proposition 4.4.8. This will allow for the desired exponenital upper bound.

###### Proof.

In this proof, all paths will go from $w$ to $v$. The words $w_{1},w_{2},...$
represent specific intermediate words that the path goes through.

Take $w_{suff}=_{Geo}a_{i_{1}}...a_{i_{k}}$ and
$v_{suff}=_{Geo}a_{j_{1}}...a_{j_{l}}$. Write these letters in order such that
$a_{i_{1}}...a_{i_{m}}$ are adjacent to both $a_{i}$ and $a_{j}$ (hence all
commute with one another) and no other letter commuting with both can be
rearranged to the $m+1^{st}$ position of $w_{suff}$, and the same for $v$ and
the letters $a_{j_{1}},...a_{j_{n}}$.

Before getting to the main cases described in the remark above, two edge cases
must be handled.

If both $m=k$ and $n=l$, then $w$ and $v$ are at most distance
$2clique(\Gamma)$ apart in the Cayley graph, and are connected by a path of
length no more than $clique(\Gamma)$ edges long. So $d_{H}(w,v)\leq O(1)$ and
the result is immediate in this case.

If $m\neq k$ but $n=l$, or vice versa, then we can essentially use a single
path as descibed in Proposition 4.4.6. We will make repeated use of Lemma
4.4.1 and Corollary 4.4.4. It takes no more than $(D+1)^{k-m-2}$ steps to
reach a any word beginning $a_{i_{1}}...a_{i_{n}}a_{i_{n+1}}a^{\prime}$.
Taking $a^{\prime}$ to commute with $a_{i_{n+1}}$, it follows that we can
change the $m+1^{st}$ entry to an adjacent vertex in $(D+1)^{k-m-2}$ steps. We
need to reach a vertex commuting with the last prefix letter of $v$, so that a
prefix letter will commute to the end of the word and thus we will find a Rips
graph edge to a shorter word. The path from $a_{i_{m+1}}$ to such an edge is a
path in $\Gamma\setminus\\{a_{i},a_{j}\\}$, and therefore has length at most
$D$. After one more application of Corollary 4.4.4, we are able to delete a
letter from the suffix in $(D+1)^{k-m-1}+1$ steps. Call the resulting word
$w_{1}$

Deleting the next letter to reach $w_{2}$ therefore takes $(D+1)^{k-m-2}+1$
steps, and so on until we have deleted all the letters after $a_{i_{m}}$. In
total, this takes $k-m+\sum_{p=0}^{k-m-2}(D+1)^{p+1}\leq
k-m+\frac{1}{D}(D+1)^{k-m}\leq d(w,v)+O_{\Gamma}(1)(D+1)^{d(w,v)}$ steps to
get to this word $w_{j-m}$, since $d(w,v)\geq k-m$. Finally, it takes at most
$clique(\Gamma)=O_{\Gamma}(1)$ steps to change $a_{i_{1}},...a_{i_{m}}$ into
$a_{j_{1}},...a_{j_{n}}$.

We come now to the main cases, where both $w$ and $v$ contain letters outside
of the clique $K$. To the word $w$ we associate the subgraph $\Gamma_{w}$ of
$\Gamma$, which is the path component of
$\Gamma\setminus(\\{a_{i},a_{j}\\}\cup K)$ containing $a_{i_{m+1}}$. Similarly
$\Gamma_{v}$ is the path component containing $a_{j_{n+1}}$. Take $K_{w}$ to
be the letters in $a_{i_{1}}...a_{i_{m}}$ that are not adjacent to
$\Gamma_{w}$, and $K_{v}$ to be the letters in $a_{j_{1}},...a_{j_{n}}$ not
adjacent to $\Gamma_{v}$.

Case I: Either $\Gamma_{w}\neq\Gamma_{v}$ or $K_{w}\neq K_{v}$.

In this case we will assume WLOG that $k-m\geq l-n$.

In the first case, $a_{i_{m+1}}$ and $a_{j_{n+1}}$ do not commute, and the
only letters in $w_{suff}$ and $v_{suff}$ that could commute past them to
cancel with one another necessarily belong to $\\{a_{i},a_{j}\\}\cup K$. There
are none of these besides $a_{i_{1}},...a_{i_{m}}$ and
$a_{j_{1}},...a_{j_{n}}$ by assumption. In the second case, similarly, a
letter of $K_{w}\Delta K_{v}$ appears in the difference $w^{-1}v$ and prevents
any other letters outside of $a_{i_{1}},...a_{i_{m}}$ and
$a_{j_{1}},...a_{j_{n}}$ from cancelling. As a result, in either of these
cases,

$d(w,v)=|w_{suff}^{-1}w_{pref}^{-1}v_{pref}v_{suff}|\geq|k-l|+|\\{a_{i_{1}},...a_{i_{m}}\\}\Delta\\{a_{j_{1}},...a_{k_{n}}\\}|+k-m+l-n\geq|k-l|+|m-n|+k-m+l-n$

.

We proceed as in the previous case. First we will describe a path from $w$ to
the word $w_{k-m}=a_{i_{1}},...a_{i_{m}}$. If $m=k$, then we can skip this
first step. It takes no more than $(D+1)^{k-m-1}$ to delete the first letter,
then $(D+1)^{k-m-2}$, and so on. Thus, deleting $k-m$ letters takes at most
$\frac{1}{D}(D+1)^{k-m}+k-m$ steps. It them takes no more than
$clique(\Gamma)$ steps to change $a_{i_{1}},...a_{i_{m}}$ into
$a_{j_{1}},...a_{j_{n}}$. Reversing the roles of $v$ and $w$, it takes at most
$\frac{1}{D}(D+1)^{l-n}+l-n$ more steps to reach $v$.

So

(1) $\displaystyle|k-l|+|m-n|+k-m+l-n$ $\displaystyle\leq d(w,v)$ (2)
$\displaystyle d_{H}(w,v)$
$\displaystyle\leq\frac{1}{D}(D+1)^{k-m}+k-m+\frac{1}{D}(D+1)^{l-n}+l-n+clique(\Gamma)$
(3) $\displaystyle\leq\frac{2}{D}(D+1)^{k-m}+d(w,v)+clique(\Gamma)$

where we used the facts that $l-m\geq j-n$ and $d(w,v)\geq k-m+l-n$ in the
equation (3). It follows that

$d_{H}(w,v)\leq O_{\Gamma}(1)(D+1)^{d(w,v)}+d(w,v)+O_{\Gamma}(1)$

.

Case II: $\Gamma_{w}=\Gamma_{v}$ and $K_{w}=K_{v}$

In this case, we suppose WLOG that $k\geq l$, and also that the letters of
$K_{w}=K_{v}$ are rearranged to be the first $|K_{w}|$ letters
$a_{i_{1}},...a_{i_{|K_{w}|}}$ and $a_{j_{1}},...a_{j_{|K_{v}|}}$ of
$w_{suff}$ and $v_{suff}$.

Here the distance $d(w,v)\geq|k-l|+m-n+|k-m-(l-n)|$. However, in order for
letters past $a_{i_{m}}$ to cancel with letters past $a_{j_{n}}$, they must
commute with each prefix letter that does not cancel in
$w_{pref}^{-1}v_{pref}$. In particular, either $k-l\leq 1$, or $d(w,v)\geq
k-l|m-n|+k-m+l-n$ (i.e. cancellation is only possible between prefix letters
and between the $a_{i_{1}},...a_{i_{m}}$ and the $a_{j_{1}},...a_{j_{n}}$).

Case II(a): The only letters that cancel between $w_{suff}$ and $v_{suff}$ lie
in the clique $K$.

Note that, in particular, this happens when $k-l\geq 2$.

Here again the first step is to change the length of suffix of $w$. As before,
it takes at most
$(D+1)^{k-m-1}+1$ steps to reduce the length of the suffix of $w$ by $1$ and
reach $w_{1}$, and then $(D+1)^{k-m-2}$ to reduce the length the second time
to reach $w_{2}$, and so on. We therefore require at most
$\frac{1}{D}(D+1)^{k-m}+k-l$ steps to go from $w$ to $w_{k-l}$, which has the
desired suffix length.

The next step is to change $a_{i_{1}},...a_{i_{m}}$ into
$a_{j_{1}},...a_{j_{n}}$. Each $a_{i_{*}}$ that is not an $a_{j_{*}}$ is
necessarily adjacent to vertices in $\Gamma_{w}=\Gamma_{v}$, and vice versa.
Therefore, for $a_{i_{m}}$ through $a_{i_{|K_{w}|+1}}$, we repeatedly move to
a vertex where the $m+1^{st}$ letter is either $a_{j_{|K_{v}|+1}}$ if
$|K_{v}|+1\leq n$, and then commute this letter to position $|K_{v}|+1$, to
reach the word $w_{m-n+1}$. This takes $D(D+1)^{l-m-2}$ steps, and we do it
$n-|K_{v}|$ times. If $n>m+1$, then eventually we move to a vertex where the
$m+2^{nd}$ letter is $a_{j_{m+2}}$, then where the $m+3^{rd}$ letter is
$a_{j_{m+3}}$ and so on. Each of these take less than $D(D+1)^{l-m-2}$ steps.
So in at most $(n-|K_{v}|)D(D+1)^{l-m-2}$ steps, we reach a word
$w_{k-l+n-|K_{v}|}$ which begins $a_{j_{1}},...a_{j_{n}}$.

If $m>n$, it now takes $D(D+1)^{l-m-2}$ steps to replace $a_{i_{n+1}}$ with a
letter in $\Gamma_{w}$ and reach the word $w_{k-l+n-|K_{v}|+1}$, followed by
$D(D+1)^{l-m-1}$ to replace $a_{i_{n+2}}$ steps to replace $a_{i_{n+2}}$ with
a letter in $\Gamma_{w}$, and so on $m-n$ times. All told, this takes at most
$(D+1)^{l-n}$ steps. If $m\leq n$ then we can skip this step.

Finally, it takes $(D+1)^{l-n}$ more steps to reach $v$ as before.

In total, it takes $\frac{1}{D}(D+1)^{k-m}+k-l$ steps to go from $w$ to
$w_{k-l}$, followed by $(n-|K_{v}|)(D)(D+1)^{l-m-2}$ to reach
$w_{k-l+n-|K_{v}|}$, $(D+1)^{l-n}$ to reach $w_{k-l+n-|K_{v}|+1+m-n}$ (if
applicable), and $(D+1)^{l-n}$ steps to reach $v$.

Using the facts that $k\geq l$ and $|m-n|\leq clique(\Gamma)$, we see that

$\displaystyle d_{H}(w,v)$
$\displaystyle\leq\frac{1}{D}(D+1)^{k-m}+k-l+(n-|K_{v}|)(D)(D+1)^{l-m-2}+(D+1)^{l-n}+(D+1)^{l-n-2}$
$\displaystyle\leq\frac{1}{D}(D+1)^{k-m}+k-l+(clique(\Gamma))(D)(D+1)^{l-m-2}+(D+1)^{l-n}+(D+1)^{l-n-2}$
$\displaystyle\leq\frac{1}{D}(D+1)^{k-m}+k-l+(clique(\Gamma))(D)(D+1)^{l-m-2}\frac{(D+1)^{2}}{D^{2}}+(D+1)^{l-n}\frac{D+1}{D}+(D+1)^{l-n-2}\frac{D+1}{D}$
$\displaystyle\leq
k-1+\frac{1}{D}\bigl{(}(D+1)^{k-m}+clique(\Gamma)(D+1)^{l-m}+(D+1)^{l-n+1}+(D+1)^{l-n-1}\bigr{)}$
$\displaystyle\leq
k-1+\frac{1}{D}\bigl{(}(D+1)^{k-m}+clique(\Gamma)(D+1)^{k-m}+(D+1)^{k-n+1}+(D+1)^{k-n-1}\bigr{)}$
$\displaystyle\leq
k-1+\frac{1+clique(\Gamma)+(D+1)^{clique(\Gamma)+1}+(D+1)^{clique(\Gamma)-1}}{D}(D+1)^{k-m}$

Since $d(w,v)\geq k-l$ and also $d(w,v)\geq k-m$, it follows that $d(w,v)\leq
O_{\Gamma}(1)(D+1)^{d(w,v)}+d(w,v)$ and no constant term is needed in this
case.

Case II(b): Letters outside of $K$ cancel.

Note that this implies that $0\leq k-l\leq 1$. The thrust of the proof in this
case is that any such cancellation shortens the path between $w$ and $v$.

Reorder $w_{suff}$ and $v_{suff}$ so that
$w_{suff}=_{Geo}b_{i_{1}},...b_{i_{m}},...b_{i_{k}}$ and
$v_{suff}=_{Geo}b_{j_{1}},...b_{j_{m}},...b_{j_{l}}$, where the letters
$b_{i_{1}},...b_{i_{m}}=b_{j_{1}},...b_{j_{m}}$ are the suffix letters that
cancel in the expression
$w^{-1}v^{-1}=_{Geo}w_{suff}^{-1}w_{pref}^{-1}v_{pref}v_{suff}$ (by a slight
abuse of notation, the value of $m$ may no longer be the same as in the
previous cases). At least one of the $b_{i_{1}},...b_{i_{m}}$ is not in $K$ by
assumption, so $M_{GeoSuff}(b_{i_{1}},...b_{i_{m}})$ is a clique. Also since
each such letter cancels with the equivalent letter in $v$, if $w_{pref}\neq
v_{pref}$, then each such letter commutes with the single letter in
$w_{pref}^{-1}v_{pref}$.

Therefore, if $k-l=1$, then there is a word $w_{1}$ of length $k$ beginning
$b_{i_{1}},...b_{i_{m}}$ adjacent to a word of length $k-1=l$ again beginning
$b_{i_{1}},...b_{i_{m}}=b_{j_{1}},...b_{j_{m}}$. Therefore, applying Lemma
4.4.3, there is a path from $w$ to $w_{1}$ of length at most $(D+1)^{k-m-1}$,
1 more edge is required to shorten the suffix to the same length as
$v_{suff}$. Finally, another application of Lemma 4.4.3 shows that it takes no
more than $(D+1)^{l-m-1}$ edges to reach $v$. In total, this path has length
at most $2(D+1)^{k-m-1}+1=O(1)(D+1)^{d(w,v)}+O(1)$ since $d(w,v)\geq k-m$.

If instead $k=l$, the result is a direct application of Lemma 4.4.3, with
length at most $(D+1)^{k-m-1}\leq(D+1)^{d(w,v)}$ ∎

As a result, we deduce a lower bound from the divergence properties of
$\delta$-hyperbolic groups. We next give the lower bound. Somewhat
irritatingly, it involves the value of $\delta$, which is often hard to
compute precisely.

######  Proposition 4.5.4 ([1], Proposition III.H.1.6).

Let $X$ be a geodesic $\delta$-hyperbolic metric space, $w$ and $v$ two points
connected by a path $\sigma$, and a geodesic $[w,v]$. If $x\in[w,v]$, then

$d(x,im(\sigma))\leq\delta|log_{2}(\ell(\sigma))|+1$

, where $\ell(\sigma)$ is the length of $\sigma$.

Paraphrasing, if there is a geodesic between $w$ and $v$ with a point $x$ far
from the path $\sigma$, then $\sigma$ must be very long.

######  Corollary 4.5.5.

Let $w$ and $v$ be on the horosphere $b_{\gamma}^{-1}(k)$ and let $d_{H}$
denote the distance in the $2$-Rips graph on the horosphere. Then
$d_{H}(w,v)\geq 2^{\frac{d(w,v)-4-2\delta}{2\delta}}$.

###### Proof.

A geodesic from $w$ to $v$ is given by the expression
$w^{-1}v=_{Geo}w_{suff}^{-1}w_{pref}^{-1}v_{pref}v_{suff}$. Let $m$ letters of
$w_{suff}$ and $n$ letters of $v_{suff}$ survive cancellation. Then by Lemma
4.1.3, $w_{pref}^{-1}v_{pref}$ consists of $m-n$ letters, where a negative
number denotes deletions that decrease the Busemann function, while a positive
number denotes deletions that increase the Busemann function.

This geodesic therefore has length $2\max\\{m,n\\}$. Deleting a prefix letter
decreases the Busemann function value. So this path begins by decreasing the
Busemann function value $m$ times, followed by either descreasing it $n-m$
more times if $n>m$ or else increasing it $m-n$ times if $m>n$, and concludes
by increasing the Busemann function $n$ times. So the geodesic contains a
point $x$ whose Busemann function value is $k-\frac{d(w,v)}{2}$.

Now let $\sigma$ be any path between $w$ and $v$ in the 2-Rips graph on
$b_{\gamma}^{-1}(k)$. We can realize $\sigma$ in the Cayley graph as a
sequence of edge-pairs, each of which either first increases $b_{\gamma}$ and
then decreases it, or first decreases $b_{\gamma}$ and then increases it. In
particular, $\sigma$ follows a curve $\sigma^{\prime}$ in the Cayley graph
whose maximum Busemann function value is $k-1$. The geodesic $[w,v]$ therefore
avoids $\sigma^{\prime}$ by at least $\frac{d(w,v)}{2}-1$ since each Busemann
function is 1-Lipschitz.

Applying the proposition to $\sigma^{\prime}$ shows that
$\ell(\sigma^{\prime})\geq 2^{\frac{d(w,v)-4}{2\delta}}$ as a path in the
Cayley Graph. Then as an edge path, $\ell(\sigma)\geq
2^{\frac{d(w,v)-4-2\delta}{2\delta}}$ ∎

Notice that the rate of exponential distortion is slower the larger $\delta$
is. That is, the slowest distortion corresponds to the thickest triangle. This
is to be expected. See [12] for another circumstance where the minimal
exponential distortion rate of a horosphere corresponds to the least negative
curvature present.

This proves Theorem 4.5.1. As a free corollary, we obtain polynomial growth of
the $2$-Rips graph. Of course, since each $k$-Rips graph is bi-Lipschitz to
the $2$-Rips graph, this proves it for all of them.

######  Corollary 4.5.6.

There is a polynomial $P$ depending only on $\Gamma$ so that if $B(w_{0},r)$
is a ball of radius $r$ about the point with empty suffix in the $d_{H}$
metric on the $2$-Rips graph on $b_{\gamma}^{-1}(k)$, then

$|B(w_{0},r)|\leq P(r)$

.

Since all the Rips graphs are bi-Lipschitz, this will also hold for any other
Rips graph with a possibly-different polynomial.

###### Proof.

According to Lemma 2.15, the language of the shortlex suffix machine
$M_{Suff}$ grows at a rate asymptotic to $\lambda^{n}$, where $\lambda$
depends only on $\Gamma$. The set of words whose suffix has length at most
$n\delta$ is precisely the $2n\delta$ ball around $w_{0}$ in the Cayley graph,
intersected with $b_{\gamma}^{-1}(k)$. By Corollary 4.5.5, this contains a
$d_{H}$-ball of radius at least $2^{n-\frac{2}{\delta}-1}$. Therefore, for
sufficiently large $n$, $|B(w_{0},2^{n-\frac{2}{\delta}-1})|\leq
O_{\Gamma}(1)\lambda^{2n\delta}$. So if $P(x)$ is any polynomial whose growth
rate is at least $2\delta\log_{2}(\lambda)$, then so is
$P(x+\frac{2}{\delta}+1)=P_{1}(x)$. In particular, for sufficiently large $n$,

$|B(w_{0},2^{n-\frac{2}{\delta}-1})|\leq
O_{\Gamma}(1)P_{1}(2^{n-\frac{2}{\delta}-1})$

.

This shows the result for an unbounded set of radii. We must now modify
$P_{1}$ to some polynomial $P_{2}$ so that the result holds for every radius.
To do this, note that $|B(w_{0},r)|$ is monotone in $r$. For any $r$, between
$r$ and $2r$ there is a number of the form $2^{n-\frac{2}{\delta}-1}$ for some
$n$. For this value of $n$,

$O_{\Gamma}(1)P_{1}(2r)\geq
O_{\Gamma}(1)P_{1}(2^{n-\frac{2}{\delta}-1})\geq|B(w_{0},2^{n-\frac{2}{\delta}-1})|\geq|B(w_{0},r)|$

. So the result holds for $P_{2}(x)=P_{1}(2x)$ for sufficiently large $r$.
Then we can simply add a constant large enough to account for the small values
of $r$.

∎

##  5\. The divergence graph on a horosphere

###  5.1. Basic definitions

We next define the other graph structure we wish to study for a horosphere,
which is due to [3]. We present a specialization of their definition to the
case of horospheres in RACGs.

######  Definition 5.1.1.

Let $A$ be the adjacency matrix of the shortlex FSM. This matrix is not
necessarily irreducible. That is, the graph need not be connected (allowing
only directed paths). The graph can however be decomposed into connected
subgraphs $\Gamma_{i}$ so that there are edges from $\Gamma_{i}$ to
$\Gamma_{j}$ only if $i<j$.

Correspondingly, the adjacency matrix can be permuted into block upper
triangular form, with $\lambda_{i}$ the Perron-Frobenius eigenvalue of the
$i^{th}$ diagonal block $A_{i}$. We then divide the states into three classes
as follows. Large states are those in a subgraph $\Gamma_{i}$ whose adjacency
matrix has $|\lambda_{i}|$ maximal. Pre-large states are those in a subgraph
$\Gamma_{i}$ for which $|\lambda_{i}|$ is not maximal, but which is connected
by an oriented path to a subgraph $\Gamma_{j}$ for which $|\lambda_{j}|$ is
maximal. Small states are states that are neither large nor pre-large.

Since the Perron-Frobenius eigenvalues of the shortlex machine correspond to
the exponential growth rate of the group $G$, one should think that large and
pre-large states are those whose shortlex successors grow at rates comparable
to the growth of the group as a whole.

######  Definition 5.1.2.

For any geodesic ray $\gamma$, we define the state function $S$ by
$S(w)=\lim_{n\to\infty}M_{lex}(\gamma(n)^{-1}w)$. One may a priori need to
take a subsequential limit in order for this limit to exist. If so, choose a
subsequence $n_{i}$ so that $M_{lex}(\gamma(n_{i})^{-1}w)$ terminates for
every $w$ (this can always be done by a standard diagonalization trick from
analysis). We will address later on why this is unnecessary in our setting.

The Divergence Graph for the horosphere $H_{\gamma}(n)$ is the graph whose
vertex sets consists of the points on $H_{\gamma}(n)$ whose $S$-state is
either large or pre-large. Its edge set is described as follows.

We define a function $P_{0}$ on shortlex words so that $P_{0}$ applied to the
empty word returns the empty word, and given any nonempty shortlex word $w$,
$P_{0}(w)$ is $wa_{i}$ where $a_{i}$ is the last letter of $w$. That is,
$P_{0}$ deletes the last letter of shortlex words other than the identity. We
will abuse notation slightly by applying $P_{0}$ to non-shortlex words. By
writing this, we always mean that $P_{0}$ is to be applied to the shortlex
representative of the word.

With this notation, the horocylic predecessor function $P$ is defined as
$\lim_{n\to\infty}(a_{i}a_{j})^{n}P_{0}\bigl{(}(a_{i}a_{j})^{-n}w\bigr{)}$.
This stabilizes when $n$ is sufficiently large. We write the set $P^{-m}(w)$
to be the $m$-fold pre-image $P^{-1}(P^{-1}(...(w)...))$.

Then $w$ and $v$ are connected by an edge exactly when
$b_{\gamma}(w)=b_{\gamma}(v)$ and the infimum distance between $P^{-m}(w)$ and
$P^{-m}(v)$ is bounded above independent of $m$. If this last condition holds
(for any pair of words, regardless of whether they are on the same
horosphere), we will say the words have close horocyclic successors.
Equivalently, $P^{-m}(w)$ consists of the words $ww^{\prime}$ where
$w^{\prime}$ may be written from the state $S(w)$. So two words have close
horocyclic successors when their $S$ states allow for close successors.

By [3] Lemma 7.4, the divergence graph is connected for $W_{\Gamma}$ where
$\Gamma$ satisfies the standing assumptions.

This definition presents three difficulties. First of all, it is defined only
on some of the points in a horosphere. Second of all, the operation $P^{-m}$
may be hard to compute for a shortlex word $w$. Third of all, it would be
convenient to consider the a priori more restrictive condition that $(w,v)$ is
an edge when $b_{\gamma}(w)=b_{\gamma}(v)$ and there are geodesic rays
$\eta_{w}$ and $\eta_{v}$ starting at $w$ and $v$ respectively so that
$\eta_{w}$ can be read as an infinite edge sequence from the state $S(w)$ and
the same for $\eta_{v}$, and so that $d(\eta_{w}(n),\eta_{v}(n))$ is bounded
independent of $n$. (i.e. instead of having a sequence of pairs of segments
stay close for all time, we would like to have a single pair of rays that stay
close for all time). We will address these difficulties in Proposition 5.1.3,
Remark 5.1.5, and Proposition 5.1.10 respectively.

For the first difficulty, the next Proposition provides sufficient conditions
on the defining graph of a RACG for there to be no small states.

######  Proposition 5.1.3.

Let $\Gamma$ be a graph satisfying the standing assumptions,and where every
vertex $v$ has a vertex $v^{\prime}$ at distance at least $3$ from $v$. Then
in $M_{lex}$ is the starting vertex is the only pre-large vertex, and the
remainder of the graph is connected.

We note that, e.g. $\Gamma$ having diameter at least $5$ is sufficient for
this last condition.

###### Proof.

We show, from any state, we can reach $S(a_{k})$ for each $k$. Suppose $w$ is
a shortlex word with last letter $a_{l}$, and fix
$a_{l}=a_{j_{0}},a_{j_{2}},...a_{j_{m}}=a_{k}$ a path in $\Gamma$ from $a_{l}$
to $a_{k}$. We denote by $a_{j_{n}}^{\prime}$ a vertex at distance at least
$3$ from $a_{j_{n}}$.

Since $d_{\Gamma}(a_{j_{n}},a_{j_{n}}^{\prime})\geq 3$, the stars of
$a_{j_{n}}$ and $a_{j_{n}}^{\prime}$ do not intersect. Then by the definition
of the shortlex machine, any shortlex word ending with
$a_{j_{n}}^{\prime}a_{j_{n}}$ is in shortlex state $S(a_{j_{k}})$. Therefore,
the word $wa_{j_{1}}^{\prime}a_{j_{1}}...a_{j_{m}}^{\prime}a_{j_{m}}$ will end
in state $S(a_{j_{m}})=S(a_{k})$ as desired, as long as this word is shortlex.

By the definition of the shortlex machine, $S(v)$ is always a subset of the
star of the last letter of $v$. That is, we can always follow a shortlex word
$v$ with any letter not commuting with the last letter of $v$. By the triangle
inequality, the distance between $a_{j_{k}}$ and $a_{j_{k+1}}^{\prime}$ is at
least $2$, so that the two do not commute. Therefore
$wa_{j_{1}}^{\prime}a_{j_{1}}...a_{j_{m}}^{\prime}a_{j_{m}}$ is shortlex. ∎

For the rest of this section, it is assumed that there are no small states in
$M_{lex}$.

The second difficulty we mentioned with the divergence graph is determining
the operation $P$. For this purpose, we prove the following lemma.

######  Lemma 5.1.4.

Let $w=_{Geo}w_{pref}w_{suff}$ be the prefix-suffix decomposition of $w$. If
$w_{pref}$ is empty or begins with $a_{j}$, then after multiplying by
$(a_{i}a_{j})^{-2}$ the form of $(a_{i}a_{j})^{-n}w$ stabilizes. If instead
$w_{pref}$ begins with $a_{i}$, then after multiplying by
$(a_{i}a_{j})^{-\left(\left\lceil\frac{|w_{pref}|}{2}\right\rceil+2\right)}$,
the form of $(a_{i}a_{j})^{-n}w$ stabilizes.

Once stabilized, if $|w_{pref}|$ was odd, then
$(a_{i}a_{j})^{-m}w=_{Geo}w_{1}a_{j}w_{2}(a_{i}a_{j})^{k}a_{i}w_{3}a_{j}w_{4}$,
where $k\geq 1$, $w_{1}$ consists of letters commuting with $a_{j}$ and
$a_{i}$, and preceding $a_{j}$, $w_{2}$ consists of letters commuting with
$a_{j}$ and $a_{i}$ and preceding $a_{i}$, $w_{3}$ consists of letters
commuting with and preceding $a_{j}$, and
$w_{1}w_{2}w_{3}w_{4}=_{Geo}w_{suff}$.

If instead $|w_{pref}|$ was even, then
$(a_{i}a_{j})^{-m}w=_{Geo}w_{1}a_{j}w_{2}(a_{i}a_{j})^{k}w_{5}a_{i}w_{6}$
where $k$, $w_{1}$, and $w_{2}$ are as before, $w_{5}$ consists of letters
commuting with and preceding $a_{i}$, $w_{1}w_{2}w_{5}w_{6}=_{Geo}w_{suff}$.

Note that this only includes half of the expressions $\gamma(n)^{-1}w$, but
does show directly that the values of
$\lim_{n\to\infty}M_{lex}(\gamma(n)^{-1}w)$ converge for all $w$ along the
subsequence $n_{i}=2i$. See remark 5.1.6 for an argument that not even this
subsequence is necessary.

###### Proof.

Start by canceling as many letters as possible from $(a_{i}a_{j})^{-n}w$.
Since $w$ was shortlex, the only possible cancellations are between
$(a_{i}a_{j})^{-n}$ and letters of $w$. As $w_{suff}$ is not equal to any
geodesic word beginning with $a_{i}$ or $a_{j}$, cancellation only happens
with negative suffixes. For powers at least those given, we cancel any
negative prefix and leave a positive prefix of size at least $4$. So we are
left to find a shortlex form of the geodesic words
$a_{j}a_{i}...a_{i}w_{suff}$ and $a_{j}a_{i}...a_{j}w_{suff}$, and show that
these will not depend on the anything more than the parity of the positive
prefix.

We wish to show that, in shortlex form, these words are of the form
$w_{1}a_{j}w_{2}\mathbf{(a_{i}a_{j})^{k}a_{i}}w_{3}a_{j}w_{4}$ or
$w_{1}a_{j}w_{2}\mathbf{(a_{i}a_{j})^{k}}w_{5}a_{i}w_{6}$. That is, it
suffices to show that no letters of $w_{suff}$ end up inside the bolded
subwords. In order for a letter $a_{l}$ in $w_{suff}$ to commute into these
subwords, $a_{l}$ must commute with both $a_{i}$ and $a_{j}$. If $a_{l}$
follows both $a_{i}$ and $a_{j}$, then $a_{l}$ will not end up in the bolded
subword (if it did it should instead shift right).

So let $a_{l}$ precede one of $a_{i}$ or $a_{j}$. Since $a_{i}$ and $a_{j}$ do
not commute, any two letters $a_{k}$ and $a_{l}$ commuting with both of them
must commute with one another. Then if $a_{l}$ precedes $a_{j}$, we achieve a
shortlex-earlier word by shifting this copy of $a_{l}$ into $w_{1}$, while if
$a_{l}$ precedes $a_{i}$ but not $a_{j}$, then we reach an earlier word by
moving this $a_{l}$ into $w_{2}$. ∎

Following the above, we will say a horocyclically shortlex word is a word of
the form $w_{1}a_{j}w_{2}(a_{i}a_{j})^{k}a_{i}w_{3}a_{j}w_{4}$ or
$w_{1}a_{j}w_{2}(a_{i}a_{j})^{k}iw_{5}a_{i}w_{6}$ where the $w_{i}$ are as
before. A horocylic suffix is the geodesic suffix $w=w_{1}w_{2}w_{3}w_{4}$ or
$w=w_{1}w_{2}w_{5}w_{6}$. If we wish to be more precise, given a shortlex
suffix $w_{suff}$, we will say it has an odd horocyclic suffix and an even
horocyclic suffix form, depending on the parity of $|w_{suff}|$. If
$|w_{suff}|$ is even, then its even horocyclic suffix form is
$w_{1}w_{2}w_{5}w_{6}$, while its odd horocyclic suffix form is
$w_{1}w_{2}w_{3}w_{4}$, and vice versa if $|w_{suff}|$ is odd. As a result, if
we wish to consider a horosphere where $b_{\gamma}$ is even, we will consider
even horocyclic suffixes, and if we wish to consider a horosphere where
$b_{\gamma}$ is odd, we will consider odd horocyclic suffixes.

Two remarks are in order. Firstly and importantly we highlight when the
predecessor of a word may have the same suffix and different prefix.

######  Remark 5.1.5.

Since
$P(w)=\lim_{n\to\infty}(a_{i}a_{j})^{n}P_{0}\bigl{(}(a_{i}a_{j})^{-n}w\bigr{)}$,
$P(w)$ deletes the last letter of $w_{4}$ (resp. $w_{6}$) if it is nonempty.
If it is empty, then $P(w)$ is a word with the same suffix and a prefix that
is one letter more negative (lengthening a nonpositive prefix or shortening a
positive one), after which $P(w)_{6}=w_{3}$ (resp. $P(w)_{4}=w_{5}$). The
words $w_{1}$ and $w_{2}$ never change upon application of $P$.

In the other direction, $P^{-1}(w)$ consists of all words $wa_{k}$ where
$a_{k}$ is not in $S(w)$. Similarly $P^{-m}(w)$ contains $ww^{\prime}$ where
$w^{\prime}$ is a shortlex word that can be written starting at the state
$S(w)$.

$P^{-1}(w)$ contains a word of different prefix length when both $S(w)$
permits a letter $a_{i}$ or $a_{j}$ to be written, and this letter can be
rearracnged to reach the prefix. This happens when $w_{3}$ (resp. $w_{5}$) is
empty and $w_{4}$ (resp. $w_{6}$) commutes with and precedes $a_{i}$ (resp.
$a_{j}$) or is empty. In such a case, the first letter of $w_{4}$ (resp.
$w_{6}$), if existent, must not commute with $a_{j}$ (resp. $a_{i}$) because
if it did it would necessarily shift left to join $w_{2}$ (resp. $w_{1}$).
After changing the prefix, the old $w_{4}$ (resp. $w_{6}$) becomes the new
$w_{5}$ (resp. $w_{3}$).

Equivalently, $P^{-1}(w)$ contains a word of different prefix exactly when
$a_{i}$ (resp. $a_{j}$) is in $F_{a_{i},a_{j}}(w_{suff})$ (so that each letter
in the suffix commutes with $a_{i}$), and that $a_{i}$ is in neither
$M_{lex}(w_{3})$ nor $M_{lex}(w_{4})$ (so that both of them consist of letters
preceding $a_{i}$.) Since we wish to work with horocyclic suffixes, we can
instead check that $a_{i}$ is in $F_{a_{i}}(w_{1}w_{2}w_{3}w_{4})$, since the
machines $F_{\mathscr{B}}$ make no assumption that their inputs are shortlex.

As a result of this, the only words whose prefix can change twice in a row
must have trivial $w_{3}$ and $w_{4}$ (resp. $w_{5}$ and $w_{6}$), so that
they consist entirely of letters commuting with both $a_{i}$ and $a_{j}$, and
preceding at least one of them.

A second remark concerns the fact that $(a_{i}a_{j})^{-n}w$ only accounts for
half of the words $\gamma(n)^{-1}w$.

######  Remark 5.1.6.

If we take instead the words $a_{i}(a_{i}a_{j})^{-n}w=\gamma(n)^{-1}w$, where
$n$ is again sufficient to cancel any positive prefix, then the form of the
resulting word may change. In particular, letters that commute with both
$a_{i}$ and $a_{j}$ which precede $a_{i}$ but follow $a_{j}$ (i.e. those in
$w_{2}$) will now rearrange to the beginning of the word, along with those
letters of $w_{1}$ which commute with and precede both letters. The remaining
letters of $w_{1}$, which precede $a_{j}$ but follow $a_{i}$, will remain
where they were. Of course, either $a_{i}$ precedes $a_{j}$ or vice versa, so
only one of these two actually happens.

Regardless, it is a straightforward exercise with the definition of the
shortlex machine to show that
$M_{lex}(a_{i}(a_{i}a_{j})^{-n}w)=M_{lex}((a_{i}a_{j})^{-n}w)$.

For our purposes, we will consider words labeled by their horocylic suffixes.
It is an inconvenient fact that converting between shortlex and horocyclic
suffixes is a slow operation (it is $O(|w|^{2})$, while all other operations
so far are $O(|w|)$). To start, we show that we can generate horocyclic
suffixes efficiently.

######  Lemma 5.1.7.

There are finite-state machines $M_{1,2,3,4}$ and $M_{1,2,5,6}$ which accept
respectively the set of horocyclic suffixes $w=w_{1}w_{2}w_{3}w_{4}$ and
$w=w_{1}w_{2}w_{5}w_{6}$.

Of course, these are not the set of odd and even horocylic suffixes. We will
describe machines for those words later.

###### Proof.

We will prove this for $M_{1,2,3,4}$, as the proof for $M_{1,2,5,6,}$ is very
similar. We would like to say that the language $\mathscr{L}(M_{1,2,3,4})$ is
a concattenation of languages $L_{1}L_{2}L_{3}L_{4}$, and show that each one
is regular. This almost works.

A priori, $w_{1}$ is a word in $Star_{<}(a_{j})\cap Star(a_{i})$ and $w_{2}$
is a word in $Star_{<}(a_{i})\cap Star(a_{j})$ that cannot be rearranged to
begin with a letter in $Star_{<}(a_{j})\cap Star(a_{i})$. But by Lemma 4.4.1,
$Star(a_{i})\cap Star(a_{j})$ is a clique. Therefore, the letters of $w_{1}$
and $w_{2}$ commute, and so $w_{2}$ does not contain any letters in
$Star_{<}(a_{j})\cap Star(a_{i})$. Therefore, $L_{1}$ and $L_{2}$ are
$ShortLex|_{Star_{<}(a_{i})\cap Star_{<}(a_{j})}$ and
$ShortLex|_{Star_{<}(a_{i})\cap Star_{>}(a_{j})}$ and both are regular.

We would like to say that $L_{3}$ is $ShortLex|_{Star_{<}(a_{j})}\cap
F_{Star(a_{i})}$ and $L_{4}$ is $ShortLex\cap F_{Star_{\leq}(a_{j})}$, but
this is not quite right. First of all, $w_{4}$ might rearrange to begin with a
letter in $Star_{<}(a_{i})\cap Star_{>}(a_{j})$ that then commutes all the way
to the beginning of $w_{3}$. Such a letter should appear in $w_{1}$ or
$w_{2}$. We prevent this from happening by intersecting with the first-letter
excluder language $F_{Star_{<}(a_{i})\cap Star(a_{j})}$. Secondly, if $w_{3}$
is empty and a copy of $a_{i}$ commutes to the front of $w_{4}$, then this
letter should be in the prefix. Since the first letter of $w_{3}$ cannot
commute with $a_{i}$, we can prevent this by intersecting with the first-
letter exclude $F_{a_{i}}$. We then obtain a single language

$L_{3,4}=\Bigl{(}(ShortLex|_{Star_{<}(a_{j})}\cap
F_{Star(a_{i})})(ShortLex\cap
F_{Star_{\leq}(a_{j})\cup\\{a_{i}\\}})\Bigr{)}\cap
F_{\\{a_{i}\\}\cup(Star_{<}(a_{i})\cap Star(a_{j}))}$

, and the language $\mathscr{L}(M_{1,2,3,4})$ is the concattenation
$L_{1}L_{2}L_{3,4}$. ∎

######  Corollary 5.1.8.

There are machines $M_{odd}$ and $M_{even}$ that accept odd and even horocylic
suffixes.

###### Proof.

Since $L_{1,2,3,4}$ and $L_{1,2,5,6}$ are regular, as are the set of words of
even and odd length, $\mathscr{L}(M_{odd})=(L_{1,2,3,4}\cap
Even(V))\cup(L_{1,2,5,6}\cap Odd(V))$ is regular. Similarly,
$\mathscr{L}(M_{even})=(L_{1,2,3,4}\cap Odd(V))\cup(L_{1,2,5,6}\cap Even(V))$
is regular. ∎

In practice, we will not use these machines because a faster implementation is
possible to find the list of horocyclic suffixes. Nevertheless, it is helpful
to know that there is a regular language of horocyclic suffixes on each
horosphere.

Finally, let us show that, if $w$ and $v$ have close horocyclic successors,
then there are rays $\eta_{w}$ and $\eta_{v}$ of horocyclic successors to $w$
and $v$ that stay close. We will use the following standard lemma about
quadrilaterals in $\delta$-hyperbolic spaces, whose proof we include for
completeness.

######  Lemma 5.1.9 (e.g. [3] Lemma 3.9.).

Suppose $w$ and $v$ are any two points in a $\delta$-hyperbolic metric space
at distance at most $M$ from one another, and $\sigma_{w}$ and $\sigma_{v}$
are geodesic segments of length $L$ whose endpoints $\sigma_{v}(L)$ and
$\sigma_{w}(L)$ are again within $M$ of one another. Then for all $n$,
$\sigma_{w}(n)$ is within $3M+4\delta$ of $\sigma_{v}(n)$.

###### Proof.

Take geodesic segments $\overline{vw}$ between $w$ and $v$ and
$\overline{\sigma_{v}(L)\sigma_{w}(L)}$ between $\sigma_{w}(L)$ and
$\sigma_{v}(L)$. We start by showing that the quadrilateral
$vw\sigma_{w}(L)\sigma_{v}(L)$ is $2\delta$-thin, i.e. that each segment is
within the $2\delta$ neighborhood of the union of the other three. To see
this, e.g. for $\sigma_{w}$, draw a geodesic between $v$ and $\sigma_{w}(L)$.
Then the triangle $vw\sigma_{w}(L)$ is $\delta$-thin so that $\sigma_{w}$ is
within $\delta$ of the union of $\overline{vw}$ and
$\overline{v\sigma_{w}(L)}$. But the triangle $\sigma_{v}(L)v\sigma_{w}(L)$ is
also $\delta$-thin, so that $\overline{v\sigma_{w}(L)}$ is within $\delta$ of
the union of $\sigma_{v}$ and $\overline{\sigma_{v}(L)\sigma_{w}(L)}$.
Therefore, this quadrilateral is $2\delta$-thin by the triangle inequality.

Let $n$ be strictly between $M+2\delta$ and $L-M-2\delta$. This
$d(\sigma_{v}(n),v)>2+2\delta$, so that
$d(\sigma_{v}(n),\overline{vw})>2\delta$ by the triangle inequality.
Similarly, $d(\sigma_{v}(n),\overline{\sigma_{v}(L)\sigma_{w}(L)})>2\delta$.
Therefore, $\sigma_{v}(n)$ is within $2\delta$ of some $\sigma_{w}(m)$. We see
that $m\geq n-M-2\delta$, because otherwise the path from $v$ to
$\sigma_{v}(n)$ that concattenates the segments $\overline{vw}$,
$\sigma_{w}|_{[0,m]}$, $\overline{\sigma_{w}(m)\sigma_{v}(n)}$ has length less
than $n$. The same argument in revers shows that $m\leq n+M+2\delta$. So since
$\sigma_{w}$ is geodesic, $d(\sigma_{v}(n),\sigma_{w}(n))\leq
d(\sigma_{v}(n),\sigma_{w}(m))+d(\sigma_{w}(m),\sigma_{w}(n))\leq
2\delta+(M+2\delta)=M+4\delta$. This establishes the desired bound for $n$ not
near the endpoints of the interval $[0,L]$.

If $n$ is within $M+2\delta$ of $0$ or $L$, then
$d(\sigma_{w}(n),\sigma_{v}(n))\leq
d(\sigma_{w}(n),w)+d(2,v)+d(v,\sigma_{v}(n))\leq
M+2\delta+M+M+2\delta=3M+4\delta$ as required. ∎

The existence of close rays now follows from a discrete version of the Arzela-
Ascoli Theorem, which may also be thought of as a diagonalization argument.

######  Proposition 5.1.10.

Let $w$ and $v$ have close successors, bounded by a constant $M$. Then there
are geodesic rays $\eta_{w}$ and $\eta_{v}$ that stay at distance at most
$3(3M+4\delta)+4\delta$ apart for all time, such that $\eta_{w}$ can be read
starting from $S(w)$ and $\eta_{v}$ can be read starting from $S(v)$.

###### Proof.

Since $P^{0}(w)=w$ and $P^{0}(v)=v$, the assumption shows that $w$ and $v$ are
distance $M$ apart. Take a sequence of words $w=w_{0},w_{1},w_{2},...$ and
$v=v_{0},v_{1},v_{2},...$ so that $w_{i}$ (resp. $v_{i}$) is in $P^{-i}(w)$
(resp. $P^{-i}(v)$), and so that $d(w_{i},v_{i})<M$. Denote by
$\overline{w_{0}w_{i}}$ (resp. $\overline{v_{0}v_{i}}$) the horocyclically
shortlex segment between $w_{0}$ and $w_{i}$ (resp. between $v_{0}$ and
$v_{i}$).

By Lemma 5.1.9, the segments $\overline{v_{0}v_{i}}$ and
$\overline{w_{0}w_{i}}$ are within $4M+3\delta$ of one another for all time.

For $j\leq i$, denote $a_{i,j}$ the label of the $j^{th}$ edge that
$\overline{w_{0}w_{i}}$ traverses. Since there are only finitely many labels,
there is some letter, which we will denote $b_{1}$ that appears infinitely
many times as $a_{i_{1}}$. Pass to thesubsequence of $w_{i}$ whose first
letter is $b_{1}$ and repeat with $a_{i_{2}}$ to get a letter $b_{2}$, etc.
Each finite substring $b_{1},...b_{k}$ appears as the beginning of some, and
indeed infinitely many, of the $w_{i}$, so that $b_{1},...b_{k}$ is a
horocylic successor to $w$ for each $k$. Then the ray $\eta_{w}=b_{1}b_{2}...$
is a horocyclic successor to $w$ and $\eta_{w}(n)$ is within $3M+4\delta$ of
$v_{i_{n}}(n)$, where the index $i_{n}$ depends on $n$.

Each segment $\overline{v,v_{i_{n}}(n)}$ is therefore within the
$3(3M+4\delta)+4\delta$ neighborhood of $\eta_{w}$ by another application of
Lemma 5.1.9. We then repeat the prior diagonalization argument on these
segments to extract a horocyclic successor ray $\eta_{v}$ to $v$ that stays
within $9M+16\delta$ from $\eta_{w}$. ∎

###  5.2. An equivalent condition to close successor rays

In this subsection, we will prove a much more down-to-earth equivalent
condition for horocyclically shortlex words to have close successors. In later
subsections, we will show that this condition is checkable by certain FSMs.

In order for $w$ and $v$ to have close successors, it will be necessary to
cancel infinitely many successor letters of $w$ with those of $v$. To keep
track of cancellations, the following preliminary lemma will be useful.

######  Lemma 5.2.1.

Let $w=a_{i_{1}}a_{i_{2}}...a_{i_{n}}$ and $v=a_{j_{1}}a_{j_{2}}...a_{j_{m}}$
be shortlex words, and consider
$w^{-1}v=_{Geo}a_{i_{n}}...a_{i_{1}}a_{j_{1}}...a_{j_{m}}$. If a letter
$a_{i_{k}}$ of $w$ cancels, it cancels with a unique letter $a_{j_{l}}$ of
$v$. If so, letters after $a_{i_{k}}$ cannot cancel with letters before
$a_{j_{l}}$.

###### Proof.

Let $a_{i_{k}}$ be the first letter of $w$ that can cancel with two letters,
$a_{j_{l}}$ and $a_{j_{o}}$ of $v$, and let $o>l$. Then
$a_{i_{k}}=a_{j_{l}}=a_{j_{o}}$ in order to cancel, and there is a letter
$a_{j_{l^{\prime}}}$ with $l<l^{\prime}<o$ failing to commute with
$a_{j_{l}}=a_{j_{o}}$ because no cancellation can be possible between letters
of $v$. So in the product $w^{-1}v$, $a_{j_{l^{\prime}}}$ must cancel with
some letter of $w$ prior to $a_{i_{k}}$ canceling with $a_{j_{o}}$. But then
the $a_{j_{l^{\prime}}}$ appearing in $w$ must be before $a_{i_{k}}$, which
prevents $a_{i_{k}}$ from canceling with $a_{j_{l}}$.

So every letter of $w$ cancels with a unique letter of $v$ if it cancels at
all.

Now suppose that $k<p$ such that $a_{i_{k}}$ and $a_{i_{p}}$ both cancel, with
no other letters canceling in between them, and they cancel with $a_{j_{l}}$
and $a_{j_{o}}$ respectively for $l>o$. Take $k,p$ to be the first such pair
with linked cancellation.
$w^{-1}v=_{Geo}a_{i_{n}}...a_{i_{1}}a_{j_{1}}...a_{j_{m}}$, so that these
letters appear in order $a_{i_{p}}...a_{i_{k}}...a_{j_{o}}...a_{j_{l}}$.
Therefore, to cancel, we require that $a_{i_{k}}$ and $a_{i_{p}}$ commute.
Since none of the letters between $a_{i_{k}}$ and $a_{i_{p}}$ cancel, it
follows also that $a_{i_{p}}$ commutes with the intermediate letters, so that
$a_{i_{k}}$ is earlier in the alphabetic order than $a_{i_{p}}$.

Now in order for the letters $a_{j_{l}}=a_{i_{k}}$ and $a_{j_{o}}=a_{i_{p}}$
to appear in this order in the shortlex word $v$, we require a letter
$a_{j_{l^{\prime}}}$ between them not commuting with $a_{j_{l}}$. Then the
cancellation between $a_{i_{k}}$ and $a_{j_{l}}$ requires that
$a_{j_{l^{\prime}}}$ cancel first with a letter before $a_{i_{k}}$, and that
$a_{j_{o}}=a_{i_{p}}$ commutes with $a_{j_{l^{\prime}}}$. As a consequence,
the three letters $a_{j_{l^{\prime}}},a_{j_{l}}=a_{i_{k}},a_{j_{o}}=a_{i_{p}}$
appear in this order in $w$ and in the order
$a_{j_{o}},a_{j_{l^{\prime}}},a_{j_{l}}$ in the word $v$. Now if
$a_{j_{l^{\prime}}}$ precedes $a_{j_{o}}$ in the shortlexo order, then new
letter $a_{j_{l^{\prime\prime}}}$ failing to commute with $a_{j_{l^{\prime}}}$
must be inserted between the two in order for $v$ to be shortlex, which will
require a matching copy before $a_{j_{l^{\prime}}}$ in $w$. There are only
finitely many letters before $a_{i_{k}}$, so iterating this argument finitely
many times if needed, we may assume that $a_{j_{l}^{\prime\prime}}$ instead
follows $a_{j_{o}}$ in the shortlex order.

If instead $a_{j_{l^{\prime}}}>a_{j_{o}}=a_{i_{p}}$, then we need a letter
$a_{i_{p^{\prime}}}$ between the two in $w$ not commuting with
$a_{i_{p}}=a_{j_{o}}$. This new letter cannot be between $a_{i_{k}}$ and
$a_{i_{p}}$ since by assumption no cancellation happens between the two of
them, so it must occur before $a_{i_{k}}$. But then $a_{j_{l^{\prime\prime}}}$
and $a_{i_{p^{\prime}}}$ consitute an earlier alternating pair than
$a_{i_{k}}$ and $a_{i_{p}}$ in violation of the assumption. We thus repeatedly
insert letters between $a_{j_{l}}$ and $a_{j_{o}}$ and matching ones before
$a_{i_{k}}$ so that the new letter commutes with $a_{j_{l}}=a_{i_{k}}$.
$a_{i_{k}}=a_{j_{l}}$ is required to commute with this letter, so another
letter is required before to preserve the shortlexness of $v$. But since there
are finitely many letters between $a_{j_{l}}$ and $a_{j_{o}}$, this cannot
continue indefinitely. ∎

Of course, we need to consider cancellation between horocylically shortlex
words, and it will be inconvenient to keep track of the prefixes. The
following lemma shows that the same result extends to horocylic suffixes.

######  Lemma 5.2.2.

Let $p_{1}$, $p_{2}$, $w$, and $v$ be shortlex words so that $p_{1}w$ and
$p_{2}v$ are (not necessarily shortlex) geodesics. Denote by $w^{\prime}$ and
$v^{\prime}$ the order the letters of $w$ and $v$ appear in after shortlex
rearrangement of $p_{1}w$ and $p_{2}v$.

Label the letters of $w^{\prime}$ by $a_{i_{1}}...a_{i_{n}}$ and the letters
of $v^{\prime}$ by $a_{j_{1}}...a_{j_{m}}$ as before. Then in the difference
$(p_{1}w)^{-1}p_{2}v$, the letters of $w^{\prime}$ which cancel with letters
of $v^{\prime}$ do so uniquely, and if the letters $a_{i_{k}}$ and
$a_{i_{k^{\prime}}}$ with $k^{\prime}>k$ cancel with the letters $a_{j_{l}}$
and $a_{j_{l^{\prime}}}$, with $l^{\prime}>^{\prime}$, then $a_{i_{k}}$
cancels with $a_{j_{l}}$ and $a_{i_{k^{\prime}}}$ cancels with
$a_{j_{l^{\prime}}}$

Note that this lemma covers cases where the words $w$ and $v$ are suffixes of
potentially-different lengths.

###### Proof.

To see that $a_{i_{k}}$ cancels with a unique $a_{j_{l}}$, apply the previous
argument. If it cancels with $a_{j_{l}}$ and $a_{j_{l^{\prime}}}$, then there
is a letter $a_{j_{o}}$ between the two which fails to commute with
$a_{j_{l}}$ in order for $pv$ to be geodesic. But such a letter prevents
$a_{i_{k}}$ from commuting to reach $a_{j_{l^{\prime}}}$.

Since the order of the $a_{i_{k}}$ and $a_{j_{l}}$ is induced by the order in
a shortlex work, the letters $a_{i_{k^{\prime}}}$ for $k^{\prime}>k$ appear
later than $a_{i_{k}}$ in the shortlex word equivalent to $p_{1}w$, and the
same holds respectively for letters $a_{j_{l^{\prime}}}$ with $l^{\prime}<l$
appear earlier in the shortlex word for $p_{2}v$. Thus if $a{i_{k}}$ and
$a_{j_{l}}$ cancel, then a cancellation between $a{i_{k^{\prime}}}$ and
$a_{j_{l^{\prime}}}$ with $k^{\prime}>k$ and $l^{\prime}<l$ violates Lemma
5.2.1 applied to the shortlex words equivalent to $p_{1}w$ and $p_{2}v$. ∎

Colloquially, these lemmas say that cancellation between shortlex words or
between horocyclic suffixes must be unlinked. We will often refer to this fact
in these terms without a formal citation. As a result, we obtain a preliminary
necessary condition for $w$ and $v$ to have close successors.

######  Lemma 5.2.3.

Let $w_{horosuff}$ and $v_{horosuff}$ be horocylic suffixes, and multiply them
by sufficient prefixes so that the resulting words $w$ and $v$ are
horocyclically shortlex and on the same horosphere. Write
$w^{-1}v=_{Geo}w_{sub}^{-1}v_{sub}$ where $w_{sub}$ and $v_{sub}$ are the
subwords of $w$ and $v$ that do not cancel. Suppose $w_{sub}^{-1}v_{sub}$
contains a pair of letters $a_{k}$ and $a_{l}$ that do not commute, and that,
for any horocyclic successors $ww^{\prime}$ and $vv^{\prime}$ to $w$ and $v$,
this pair $a_{k}$ and $a_{l}$ still cannot be canceled. Then $w_{horosuff}$
and $v_{horosuff}$ do not have close horocylic successors.

###### Proof.

Suppose that $w$ and $v$ have horocyclic successors $ww^{\prime}$ and
$vv^{\prime}$. Recall that $w^{\prime}$ and $v^{\prime}$ are necessarily
shortlex.

Consider letters that cancel between $w^{\prime}$ and $v^{\prime}$. Since
$a_{k}$ and $a_{l}$ cannot be canceled, letters $a_{m}$, $a_{n}$ commuting
across $w_{sub}^{-1}v_{sub}$ must commute with $a_{k}$ and $a_{l}$. By the
first part of Lemma 4.4.1, the two commute.

Therefore, the letters of $w^{\prime}$ that can cancel with those in
$v^{\prime}$ must all be from a single clique in $\Gamma$. No such letter
$a_{k}$ appears more than once in $w^{\prime}$ and commutes across to
$v^{\prime}$, because these two letters $a_{k}$ then would cancel with one
another, so that $w^{\prime}$ is not shortlex. So there is a bound on the
number of cancellations possible between $w^{\prime}$ and $v^{\prime}$.

However, since $w_{sub}^{-1}v_{sub}$ is boundedly long, only boundedly many
cancellations may occur with letters of $w_{sub}^{-1}v_{sub}$. Therefore, only
boundedly many letters cancel out of $w^{\prime}$ and $v^{\prime}$. This means
that the reduced length of $(ww^{\prime})^{-1}vv^{\prime}$ grows without bound
as the lengths of $w^{\prime}$ and $v^{\prime}$ grow, so that the two do not
have close horocyclic successors. ∎

######  Proposition 5.2.4.

Retain the notation of Lemma 5.2.3. If the non-commuting letters $a_{k}$ and
$a_{l}$ in $w_{sub}^{-1}v_{sub}$ come from different words, and
$|w_{suff}|=|v_{suff}|$, then these letters will never cancel in any horocylic
successor.

###### Proof.

Suppose that $a_{k}$ is a letter of $w_{sub}^{-1}$ and $a_{l}$ is a letter of
$v_{sub}$. At most one of the two is a prefix letter. If one is, say $a_{k}$,
then by Remark 5.1.5, the only way to change $v$’s prefix in a successor is if
$v_{suff}$ commutes entirely with the prefix letter to be written. So $a_{k}$
can only be canceled if $v_{suff}$ commutes entirely with $a_{k}$, which it
does not by assumption.

Instead let both be suffix letters. Since the two do not commute, cancelation
of either one would first require the other to cancel, which would create
linked cancelation. ∎

######  Corollary 5.2.5.

Retain the notation of Proposition 5.2.4. If $(w,v)$ is an edge in the
divergence graph, and $w_{sub}^{-1}v_{sub}$ contains a pair of non-commuting
letters $a_{k}$ and $a_{l}$, then both of these letters appear in either the
subword $w_{sub}^{-1}$ or $v_{sub}$, and the letters of the other subword all
commute with one another and with $a_{k}$ and $a_{l}$.

###### Proof.

The first part of the conclusion is the contrapositive of Proposition 5.2.4.
Then the second part follows from Lemma 4.4.1. ∎

Besides the uncancelable clique, every other letter can be canceled by some
successor. In fact, there is a single successor in which every potentially-
cancelable letter does cancel.

######  Lemma 5.2.6.

Suppose $w$ and $v$ are horocylically shortlex words for which the clique
$K(v,w)$ of letters in $w_{sub}^{-1}v_{sub}$ is uncancelable. Then $K(v,w)$
includes either all of $w_{sub}^{-1}$ or all of $v_{sub}$ (potentially both).
Moreover, if $K(v,w)$ contains all of $w_{sub}^{-1}$ but not all of $v_{sub}$
(resp. all of $v_{sub}$ but not all of $w_{sub}^{-1}$), then there is a
horocyclic successor $w^{\prime}$ to $w$ (resp. a horocyclic successor
$v^{\prime}$ to $v$) such that $(ww^{\prime})^{-1}v$ (resp.
$w^{-1}vv^{\prime}$) contains only the uncancelable letters in $K(v,w)$.

###### Proof.

Let $a_{k_{0}}$ and $a_{l_{0}}$ be the first cancelable letters of $w$ and $v$
respectively, if they exist. If $S(v)$ does not permit $a_{k_{0}}$, then
$a_{k_{0}}$ can only be written into a successor of $v$ after another letter
$a_{k_{0}}^{\prime}$ not commuting with it. But this would mean $a_{k_{0}}$
cannot be canceled because no letter before $a_{k}$ can, so that there is no
letter to cancel with $a_{k_{0}}^{\prime}$. Analogously, $S(w)$ must permit
$a_{l_{0}}$. But then $wa_{l_{0}}$ and $va_{k_{0}}$ have linked cancellation,
since writing a letter in $w$ after $a_{k_{0}}$ cannot prevent $a_{k_{0}}$
from canceling. This proves the first assertion.

WLOG, then let $w$ contain cancelable letters. Denote them
$a_{k_{0}},...a_{k_{m}}$. The first such, $a_{k}$ is permitted by $S(v)$. The
result will then hold by repeated application of this same argument, provided
that $S(va_{k_{0}}...a_{k_{n}})$ always permits $a_{k_{n+1}}$. If this does
not happen then either $a_{k_{n+1}}$ is forbidden by $S(v)$ and each
$a_{k_{0}},...a_{k_{n}}$ commutes with $a_{k_{n+1}}$, or $a_{k_{n+1}}$
commutes with and precedes some earlier letter $a_{k_{o}}$ and commutes with
$a_{k_{o+1}},...a_{k_{n}}$. In the first case, $a_{k_{n+1}}$ can only be
written after $v$ if it is first preceded by an $a_{k_{n+1}}^{\prime}$ not
commuting with it. But this letter is therefore not $a_{k_{0}},...a_{k_{n}}$
and therefore does not cancel with any letter in $w$, so that $a_{k_{n+1}}$ is
not cancelable. In the second case, the letters $a_{k_{0}},...a_{k_{n+1}}$
appear in order in $w$, with additional letters interspersed. Between
$a_{k_{o}}$ and $a_{k_{n+1}}$ there appear only uncancelable letters of $w$,
and the letters $a_{k_{o+1}},...a_{k_{n}}$ (the other option would be to have
some letters in between that cancel with letters of $v$. But by unlinked
cancellation this would make $a_{k_{o}}$ uncancelable). By assumption,
$a_{k_{n+1}}$ commutes with each such letter, so that $w$ is not shortlex. ∎

As a consequence of this lemma, we can always find a single successor that
achieves the maximal amount of cancelation. We next show that determining
whether two words have close successors is easy in this setting. When two
words $w$ and $v$ with close successors differ by an uncancelable clique, we
can find successor rays $\eta_{w}$ and $\eta_{v}$ that are close for all time
in the simplest way possible.

######  Lemma 5.2.7.

Suppose $w^{-1}v=_{Geo}w_{sub}^{-1}v_{sub}$ where $w_{sub}^{-1}v_{sub}$
consists of a collection of commuting letters, with none canceling in any
successor. Call this clique $K(v,w)$. Then $w$ and $v$ have close successors
if and only if there are two nonadajacent letters $a_{k}$ and $a_{l}$
commuting with each letter of $K(v,w)$, so that $w(a_{k}a_{l})^{n}$ and
$v(a_{k}a_{l})^{n}$ are horocylic successors of $w$ and $v$ respectively.

We remark that since $a_{k}$ and $a_{l}$ commute with $K(v,w)$ and not with
one another (or else $(a_{k}a_{l})$ geodesic), then we only need to check
whether $a_{k}$ is in $S(w)$ (resp. $S(v)$) in order to determine if
$w(a_{k}a_{l})^{n}$ succeeds $w$, (resp. $v(a_{k}a_{l})^{n}$ succeeds $v$).

###### Proof.

Sufficiency is clear.

To see necessity, suppose to the contrary that there is no such pair of
letters for $K(v,w)$, but that $P^{-*}(w)$ and $P^{-*}(v)$ have close elements
for all time. Choose $w$ and $v$ so that $K(v,w)$ is maximal among
counterexamples.

There is a letter $a_{k}$ so that $P(wa_{k})=w$ and $P^{-*}(wa_{k})$ is
bounded infimum distance from $P^{-*}(v)$ (we need infinitely many horocylcic
successors to $w$, and there are only finitely many words in $P^{-1}(w)$, so
there must be at least one word $wa_{k}$ so that infinitely many of the chosen
horocyclic successors go through $wa_{k}$). By assumption, at least one of the
following holds of $a_{k}$:

  1. (1)

$a_{k}$ is not adjacent to $K(v,w)$.

  2. (2)

$a_{k}\in S(v)$.

  3. (3)

For each $a_{l}$ adjacent to $K(v,w)$, $a_{k}$ is adjacent to $a_{l}$.

In case (1), writing $a_{k}$ following $w$ creates an uncancelable pair. Since
$a_{k}$ and some letter $a_{m}$ in $K(v,w)$ do not commute, $a_{k}$ can only
be canceled by a letter following $v$, after $a_{m}$ is canceled, and $a_{m}$
is assumed uncancelable. Hence by Lemma 5.2.3, $wa_{k}$ and $v$ do not have
close successors.

In case (2) $a_{k}\cup K(v,w)$ is a clique. $a_{k}$ can be written after $v$
only after writing a letter $a_{k}^{\prime}$ not commuting with $a_{k}$. Such
a letter cannot cancel with any letters following $wa_{k}$ because this would
violate Lemma 5.2.2. As a result, $a_{k}$ cannot cancel. But now $a_{k}\cup
K(v,w)$ is a strictly larger uncancelable clique providing a counterexample,
violating the assumed maximality.

In case (3), note that there are finitely many such letters and they all
commute with one another by assumption. So we can write only words of length
at most $clique(\Gamma)$ in these letters to follow $w$ before we are forced
to write a letter that falls into cases (1) or (2). ∎

In fact, it suffices to apply Lemma 5.2.7 to the special successors described
in Lemma 5.2.6.

######  Proposition 5.2.8.

Let $w$ and $v$ be two horocyclically shortlex words and suppose there is a
horocyclic successor $v^{\prime}$ to $v$ so that $w^{-1}v^{\prime}$ consists
of the uncancelable clique $K^{\prime}(v,w)$. Then $w$ and $v$ have close
successors if and only if $w$ and $v^{\prime}$ do.

###### Proof.

Since $v^{\prime}$ is a successor to $v$, $P^{-*}(v^{\prime})$ is contained in
$P^{-*}(v)$. Therefore, one implication is immediate. We must show that if
$P^{-*}(v)$ is within finite distance of $P^{-*}(w)$, then so is
$P^{-*}(v^{\prime})$.

Suppose that the horocyclically shortlex rays $\eta_{w}$ and $\eta_{v}$ start
at $w$ and $v$ and stay close forever, but that $\eta_{v}$ does not pass
through $v^{\prime}$. Write the edges that $\eta_{v}$ traverses
$a_{i_{1}},a_{i_{2}},...$. Suppose $a_{j_{1}}...a_{j_{k}}$ is the
horocylically shortlex segment from $v$ to $v^{\prime}$, and let
$a_{i_{1}},...a_{i_{l}}=a_{j_{1}},...a_{j_{l}}$ but $a_{i_{l+1}}\neq
a_{j_{l+1}}$, for some $l<k$. This makes either $a_{i_{l+1}}$ or the copy of
$a_{j_{l+1}}$ in $w$ not cancel, since both canceling would create linked
cancelation.

Since $\eta_{w}$ and $\eta_{v}$ stay close for all time, there is a last
uncancelled letter. Let $w^{\prime\prime}$ and $v^{\prime\prime}$ be words on
$\eta_{w}$ and $\eta_{v}$ so that $w^{\prime\prime-1}v^{\prime\prime}$ is
exactly the clique of letters that will not cancel along the rays $\eta_{w}$
and $\eta_{v}$. Call this clique $K^{\prime}$. $K$ is a proper subclique of
$K^{\prime}$ because it contains either $a_{i_{l+1}}$ or $a_{j_{l+1}}$. By
Lemma 5.2.7, there are letters $a_{m_{1}}$ and $a_{n_{1}}$ that do not commute
with one another, commute with $K^{\prime}$ (hence with $K(v,w)$) and that one
of which (WLOG $a_{m_{1}}$) is permitted by $S(v^{\prime\prime})$ and
$S(w^{\prime\prime})$. If $a_{m_{1}}$ is permitted by $S(v^{\prime})$ and
$S(w)$, then the proof is complete.

For $a_{m_{1}}$ to be written after $w^{\prime\prime}$, it must either be
permitted by $S(w)$ or be preceded by some $a_{m_{2}}$ that it does not
commute with and which cancels a corresponding copy in $\eta_{v}$. In such a
case, set $a_{n_{2}}=a_{m_{1}}$ and repeat with the pair $a_{m_{2}}$ and
$a_{n_{2}}$. Note that $a_{m_{2}}$, while it does not necessarily commute with
$K(v^{\prime\prime},w^{\prime\prime})$, must still commute with $K(v,w)$ in
order for the pair to cancel. So we repeat the process with $a_{m_{2}}$ and
$a_{n_{2}}$. After finitely many steps we get a new pair of succesor rays
$\eta_{w}^{\prime}$ and $\eta_{v}^{\prime}$ which end with an alternating non-
commuting pair $a_{m^{\prime}}$ and $a_{n^{\prime}}$, such that both letters
commute with $K(v,w)$ and such that $a_{m^{\prime}}$ is permitted by $S(w)$
and commutes with the letters between itself and $w$. If $a_{m^{\prime}}$ is
permitted by $S(v^{\prime})$, then we will be done.

The end of the word $w$ consists only of uncancelable letters plus
$a_{j_{1}},...a_{j_{k}}$, but no letters canceling with those in $v$, and
$a_{m^{\prime}}$ commutes with each uncancelable letter by assumption.
Therefore, $a_{m^{\prime}}$ is permitted by $S(a_{j_{1}}...a_{j_{k}})$.
$v^{\prime}=va_{j_{1}}...a_{j_{k}}$, so that $a_{m^{\prime}}$ is forbidden in
$S(v^{\prime})$ only if it is forbidden in $S(v)$ and $a_{j_{1}},...a_{j_{k}}$
consists entirely of letters commuting with and preceding $a_{m^{\prime}}$.
But $a_{m^{\prime}}$ appears in $\eta_{v}^{\prime}$, so this would require
$a_{m^{\prime}}$ to be preceded after $v$ by a letter $a_{o}$ that it does not
commute with. Such a letter must cancel and cannot appear between $w$ and