We prove that if a group $G$ is relatively hyperbolic with respect to virtually abelian peripheral subgroups then $G$ quasiisometrically embeds into a product of binary trees. This extends the result of Buyalo, Dranishnikov and Schroeder in which they prove that a hyperbolic group quasiisometrically embeds into a product of binary trees. To prove the main result, we use the machinery of projection complexes and quasi-trees of metric spaces developed by Bestvina, Bromberg, Fujiwara and Sisto <cit.> <cit.> <cit.> <cit.>. We build on this theory by proving that one can remove certain edges from the quasi-tree of metric spaces, and be left with a
tree of metric spaces which is quasiisometric to the quasi-tree of metric spaces. In particular, this reproves a result of Hume <cit.>. Further, inspired by Buyalo, Dranishnikov and Schroeder's Alice's Diary <cit.>, we develop a general theory of diaries and linear statistics. These notions provide a framework by which one can take a quasiisometric embedding of a metric space into a product of infinite-valence trees and upgrade it to a quasiisometric embedding into a product of binary trees.

§ INTRODUCTION

§.§ Results

In this paper, we prove the following result.

Let $G$ be a finitely generated group that is relatively hyperbolic with respect to virtually abelian peripheral subgroups $H_1, H_2, \dots, H_T$. Let $R_t$ denote the rank of a finite index abelian subgroup of $H_t$, and define $R = \max(R_1, R_2, \dots, R_T)$. Then $G$ quasiisometrically embeds into a product of $R + \max(\asdim(G), R+1) + 1$ binary trees. Since $\asdim(G)$ is finite <cit.>, this is a finite product of binary trees.

In particular, the fundamental group of a finite volume real hyperbolic manifold quasiisometrically embeds into a finite product of binary trees.

<Ref> should be compared with the result of Mackay and Sisto below <cit.>.

Let $G$ be a finitely generated group. Suppose $G$ is relatively hyperbolic with respect to peripheral subgroups $H_1, H_2, \dots, H_T$. Suppose also that each $H_t$ quasiisometrically embeds into a product of $m_t$ trees, and define $m = \max(m_1, m_2, \dots, m_T)$. Then $G$ quasiisometrically embeds into a product of $m + \max(\asdim(G), m+1) + 1$ trees. Since $\asdim(G)$ is finite <cit.>, this is a finite product of trees.

If a metric space $X$ quasiisometrically embeds into a finite product of trees then $X$ has finite asymptotic dimension. Hence the Mackay–Sisto result is itself a refinement of a result of Osin <cit.>: if a finitely generated group $G$ is relatively hyperbolic with respect to peripheral subgroups with finite asymptotic dimension, then $G$ has finite asymptotic dimension.

It is unclear to me whether the virtually abelian condition on the peripheral subgroups in <Ref> can be weakened. The obvious conjecture is that $G$ quasiisometrically embeds into a product of binary trees if and only if the peripheral subgroups do as well. In this paper, the virtual nilpotence of the peripheral subgroups is used in order to quasiisometrically embed the Bowditch space $X(G)$ into a product of binary trees (see <Ref>).

Can the virtually abelian condition be removed? If the peripherals quasiisometrically embed into products of binary trees, does $G$ do the same?

It follows from <cit.> that a virtually nilpotent but not virtually abelian finitely generated group cannot quasiisometrically embed into a product of trees. Hence, since peripheral subgroups are undistorted in a relatively hyperbolic group, if a single peripheral subgroup $H$ of a relatively hyperbolic group is virtually nilpotent but not virtually abelian, then $G$ cannot quasiisometrically embed into a product of trees. So, thanks to <cit.> and <Ref>, the picture is fully understood when the peripheral subgroups are virtually nilpotent.

Let $G$ be finitely generated and relatively hyperbolic with respect to virtually nilpotent peripheral subgroups. Then $G$ quasiisometrically embeds into a product of binary trees if and only if all the peripheral subgroups are virtually abelian.

<Ref> and <Ref> should themselves be compared with the two results below <cit.> <cit.>.

A hyperbolic group $G$ admits a quasiisometric embedding into a product of $n+1$ trees where $n$ is the topological dimension of the boundary.

A hyperbolic group admits a quasiisometric embedding into a product of $n+1$ binary trees where $n$ is the topological dimension of the boundary.

Buyalo and Lebedeva <cit.> also prove that for a hyperbolic group $G$ we have $\asdim(G) = n+1$ where $n$ is the topological dimension of the boundary.

<Ref> sits within the circle of ideas in coarse geometry and geometric group theory that involve constructing and obstructing metric embeddings between groups and spaces. Sometimes this is justified via Guoliang Yu's proof <cit.> that finitely generated groups with finite asymptotic dimension satisfy Novikov's conjecture. Indeed, a group that admits a coarse embedding into a finite product of trees has finite asymptotic dimension. Yu's result proves that, in principle, one can draw algebraic conclusions from metric embedding results for groups. However I am currently unaware of any algebraic deductions that stem specifically from a quasiisometric embedding into a product of binary trees. As an aside, it would be interesting to know whether there existed a quasiisometry invariant, analogous to the asymptotic dimension or linearly controlled asymptotic dimension (which is also known as the asymptotic Assouad–Nagata dimension), which could distinguish between a product of infinite-valence trees and a product of binary trees.

<Ref> implies several results which attempt to bound the size and dimension of hyperbolic and relatively hyperbolic groups. Indeed, <Ref> implies that hyperbolic groups quasiisometrically embed into products of binary trees <cit.> which implies that hyperbolic groups quasiisometrically embed into products of infinite-valence trees <cit.> which implies that hyperbolic groups have finite asymptotic dimension <cit.>. With that said, it would not be accurate to call <Ref> a generalisation of these results since its proof relies on <cit.> in an essential way. As far as I'm aware, <Ref>, the results of <cit.> and the thesis of Alina Rull <cit.>, in which Rull proves that an $n$-coloured right-angled Artin group or $n$-coloured right-angled Coxeter group admits a quasiisometric embedding into a product of $n$ binary trees, are the only results on the topic of quasiisometric embeddings into products of binary trees.

§.§ Ideas

There are two notable ideas that are developed in order to complete the proof of <Ref>.

§.§.§ The tree of metric spaces

The first new idea is to prove that by simply removing some edges from the quasi-tree of metric spaces $\qtoms$, as defined by Bestvina, Bromberg and Fujiwara <cit.>, we can form a tree of metric spaces $\toms$ which is quasiisometric to $\qtoms$. This will be covered in <Ref>. The construction is as follows. We fix an arbitrary vertex $B \in \Y$ in the projection complex $\pc$. We define $\T_K(\Y,B)$ to be the connected subgraph of $\pc$ formed by taking the union of all standard paths in $\pc$ based at $B$. In other words,

\[\T_K(\Y,B) = \bigcup_{X \in \Y} \Y_K[B,X]\]

where $\Y_K[B,X]$ denotes the standard path from $B$ to $X$. We write $\T = \T_K(\Y,B)$ for simplicity. In <Ref>, we prove that $\T$ is a subtree of $\pc$ that is quasiisometric to $\pc$. Now, for each pair $X,Y \in \Y$ which are connected by an edge in $\pc$, we fix arbitrary elements $p(X,Y) \in \pi_X(Y) \subset \C(X)$ and $p(Y,X) \in \pi_Y(X) \subset \C(Y)$. We form the tree of metric spaces $\toms$ by taking the disjoint union of the metric spaces $\C(Y)$ and then drawing an edge of length $K$ between $p(X,Y)$ and $p(Y,X)$ whenever there is an edge between $X$ and $Y$ in $\T$. We prove that $\toms$ is a subset of $\qtoms$ such that the inclusion map is a quasiisometry. In particular, this reproves a result of Hume (see <cit.>) who proved that the quasi-tree of metric spaces $\qtoms$ is quasiisometric to a tree-graded space whose pieces are the metric spaces $\C(Y)$. However, in Hume's work this quasiisometry is defined abstractly, following from the fact that $\qtoms$ satisfies a relative bottleneck property. In contrast, the quasiisometry given in <Ref> is a very explicit inclusion map.

§.§.§ Diaries and statistics

The second new idea is to use the theory of diaries and statistics described in <Ref>. This work is inspired by Alice's Diary, a function defined by Buyalo, Dranishnikov and Schroeder <cit.>. In this paper, a diary is defined as follows.

A diary is a height-preserving and order-preserving map (with respect to some chosen basepoints) from an infinite-valence tree to a uniformly locally finite tree.

We say that a map $f: T \rightarrow T'$ between rooted trees is order-preserving if $f(x')$ descends from $f(x)$ in $T'$ whenever $x'$ descends from $x$ in $T$. We say that $f: T \rightarrow T'$ is height-preserving if $f$ preserves the distance of points from the root vertices.

Since a diary is a graph homomorphism, it is always $1$-Lipschitz.

The following example gives a sketchy idea of how diaries can be used to upgrade quasiisometric embeddings into products of infinite-valence trees so that they become quasiisometric embeddings into products of binary trees.

Suppose $X$ is a metric space and suppose $T_\infty$ is a rooted infinite-valence tree and suppose $T_{< \infty}$ is a rooted uniformly bounded valence tree. Suppose we have a $(\lambda,\mu)$-quasiisometric embedding $F: X \rightarrow \prod_{q=1}^Q T_\infty$. Let $P$ be a property of pairs of sentences in $T_\infty$ (or, what is the same thing, $P$ is a subset of the product $T_\infty \times T_\infty$) and suppose we have a diary $D: T_\infty \rightarrow T_{< \infty}$ for which there exists a constant $M \geq 1$ such that

\[
d(D(y), D(y')) \geq \frac{1}{M} d(y,y')
\]

for all pairs $y,y' \in T_\infty$ satisfying $P$. We are interested in whether the composition

\begin{equation} \label{eq.compositionintro}
X \xrightarrow{F} \prod_{q=1}^Q T_\infty \xrightarrow{D \times D \times \dots \times D} \prod_{q=1}^Q T_{< \infty}
\end{equation}

is a quasiisometric embedding. Suppose products are given the $L^1$ metric.

Let $x,x' \in X$ and write $F(x) = (y_1, y_2, \dots, y_Q)$ and $F(x') = (y_1', y_2', \dots, y_Q')$. Then $d(F(x),F(x')) = \sum_{q=1}^Q d(y_q,y_q')$. Suppose $\mathfrak{q} \in \{1,2,\dots, Q\}$ is such that $d(y_\q,y_\q') = \max_q d(y_q,y_q')$. Then $d(y_\q,y_\q') \geq \frac{1}{Q} d(F(x),F(x'))$.

Suppose we manage to prove that the pair $y_\q, y_\q' \in T_\infty$ arising in this manner satisfy the property $P$. Then I claim that (<ref>) would be a quasiisometric embedding. The diary $D$ is $1$-Lipschitz and the map $F$ is a quasiisometric embedding so the composition (<ref>) is coarsely Lipschitz. For the lower bound of the quasiisometric inequality we have

\[d(D(y_\q), D(y_\q)) \geq \frac{1}{M}d(y_\q,y_\q') \geq \frac{1}{QM} d(F(x),F(x')) \geq \frac{1}{\lambda QM} d(x,x') - \mu \]

where the first lower bound follows from the fact that $y_\q$ and $y_\q'$ satisfy $P$. So $X$ admits a quasiisometric embedding into the product $\prod_{q=1}^Q T_{< \infty}$. As $T_{< \infty}$ has uniformly bounded valence, it admits a quasiisometric embedding into a binary tree.

It follows from the proof structure of <Ref> that we are interested in diaries which coarsely preserve the metric on pairs of element $y,y' \in T_\infty$ whenever they satisfy a certain property $P$. In <Ref>, we define four such properties, namely $(\aries)$, $(\leo)$, $(\virgo)$ and $(\taurus)$, all of which have associated diaries. In order to state these properties, it will be necessary to always assume that our infinite-valence trees and uniformly bounded valence trees have some extra structure; indeed, we will assume that they are sentence-trees and word-trees. See <Ref> for the definition of these concepts.

§.§ Outline of this paper

* In <Ref>, we provide some preliminary definitions and conventions.

* In <Ref>, we outline the theory of diaries and statistics that will be used in the proof of <Ref>. If a reader is only interested in the proof of <Ref>, then technically they would only need to understand the meaning of <Ref> and not its proof or the ideas surrounding Alice's Diary.

* In <Ref> and <Ref>, we provide some preliminary results on the Morse–Thue sequence and regular maps into products of binary trees.

* In <Ref>, the background on projection complexes and quasi-trees of metric spaces is provided. We also prove in particular that a quasi-tree of metric spaces $\qtoms$ is quasiisometric to a tree of metric spaces $\toms$.

* In <Ref>, we cover the relevant background on relatively hyperbolic groups.

* In <Ref>, we define standard paths in a group that is relatively hyperbolic with respect to virtually abelian peripheral subgroups. We prove that these standard paths are quasigeodesics.

* In <Ref>, we give the first stage of the proof of <Ref> by finding a quasiisometric embedding of $G$ into a product of infinite-valence sentence-trees.

* In <Ref>, using the theory developed in <Ref>, we upgrade this quasiisometric embedding so that it is into a product of uniformly bounded valence trees.

* In <Ref>, we look at a few questions arising from <Ref>, in particular the possibilities of extending the proof techniques to the mapping class group and graph manifold groups.

* <Ref> contains a formal definition of Alice's Diary. <Ref> contains the proofs of two results in <Ref> (some readers might assume their veracity but I wanted to be rigorous). <Ref> describes how diaries and statistics can be used to quasiisometrically embed the hyperbolic plane into a product of two binary trees. This proof follows a similar structure to the one given in <cit.>. It is meant to help the reader understand how to apply the ideas outlined in <Ref> in a simple setting.

§.§ Outline of the proof of the main theorem

Let $G$ be relatively hyperbolic with respect to virtually abelian peripheral subgroups $H_1, \dots H_T$. Let $R$ be the maximal rank of finite index abelian subgroups of the peripheral subgroups. Let $S$ be a finite generating set of $G$. Let $A$ be the finite alphabet $S \cup S^{-1}$, let $W$ be the set of finite words on $A$ and let $T_W$ be the sentence-tree whose vertices are in bijection with the free monoid $W^*$. Using work of Dahmani and Yaman <cit.> and work of Buyalo, Dranishnikov and Schroeder <cit.>, we can prove there exists a regular map $\phi: G \rightarrow \prod_{q=1}^Q \tb$ where $Q \leq \max(\asdim(G),R+1) + 1$ (see <Ref> and <Ref>) and where $\tb$ denotes the rooted binary tree.

(Step 1) For each $1 \leq r \leq R$ and $x,z \in G$, we define a canonical standard path (which is a quasigeodesic) from $x$ to $z$ called the $r$'th ordered standard path. This is <Ref>.

(Step 2) By partitioning the $r$'th ordered standard path from $e \in G$ to $x \in G$ (which corresponds to an element of $W$) into several words, we may define a map $F_r: G \rightarrow T_W$.

(Step 3) We prove that $F_1 \times \dots \times F_R \times \phi: G \rightarrow \prod_{r = 1}^R T_W \times \prod_{q=1}^Q \tb$ is a quasiisometric embedding. The proof of this step uses the fact that the quasi-tree of metric spaces is quasiisometric to a tree of metric spaces (which is proved in <Ref>).

(Step 4) We choose several finite statistics and linear statistics, and constants $\jf$, $\jl$, $N$ and $\epsilon$ so that <Ref> induces a diary $D: T_W \rightarrow T_\Omega$ which coarsely preserves the metric on a pair of sentences in $T_W$ whenever they satisfy $\leo(\scalf, \jf)$ or $\taurus(\scall, \jl, N, \epsilon)$.

(Step 5) We prove that

\[G \xrightarrow{F_1 \times \dots \times F_R \times \phi} \prod_{r = 1}^R T_W \times \prod_{q=1}^Q \tb \xrightarrow{D \times \dots D \times \id} \prod_{r = 1}^R T_\Omega \times \prod_{q=1}^Q \tb\]

is a quasiisometric embedding. We follow the proof structure described in <Ref>; in other words, we reduce the problem to proving that a pair of sentences $\alpha$, $\beta \in T_W$ satisfy either the property $\leo(\scalf, \jf)$ or the property $\taurus(\scall, \jl, N, \epsilon)$.

Since the uniformly bounded valence word-tree $T_\Omega$ is quasiisometric to $\tb$, we are done.

§.§ Acknowledgements

Thank you to Alessandro Sisto for alerting me to the result of <cit.>. Thank you to David Hume for a useful and enlightening discussion. Finally, thank you to my supervisor Cornelia Drutu for suggesting that I consider relatively hyperbolic groups in this work.

§ DEFINITIONS AND CONVENTIONS

§.§ Numbers

We use $\N_0$ to denote the non-negative integers and $\N$ to denote the positive integers. Notation such as $\R_{> 0}$ means the set $\{x \in \R : x > 0\}$.

§.§ Coarse geometry

Throughout this subsection, let $X$ and $Y$ be a pair of metric spaces and let $\lambda \geq 1$, $\mu \geq 0$ be a pair of constants.

We say that $f: X \rightarrow Y$ is $(\lambda,\mu)$-coarsely Lipschitz if

\[d(f(x),f(x')) \leq \lambda d(x,x') + \mu\]

A $(\lambda,0)$-coarsely Lipschitz function $f:X \rightarrow Y$ is $\lambda$-Lipschitz.

A $(\lambda,\mu)$-quasiisometric embedding $f: X \rightarrow Y$ is a function which satisfies

\[\frac{1}{\lambda} d(x,x') - \mu \leq d(f(x),f(x')) \leq \lambda d(x,x') + \mu\]

for all $x,x' \in X$. It is a $(\lambda,\mu)$-quasiisometry if in addition, for all $y \in Y$ there exists $x \in X$ such that $d(y,f(x)) \leq \mu$. A $(\lambda,0)$-quasiisometric embedding $f: X \rightarrow Y$ is a $\lambda$-bilipschitz embedding. A $(\lambda,0)$-quasiisometry $f: X \rightarrow Y$ is a $\lambda$-bilipschitz homeomorphism.

A metric space $X$ has bounded growth at some scale if there are constants $0 < r < R$ and $N \in \N$ such that all open balls of radius $R$ can be covered by $N$ open balls of radius $r$.

The following proposition will be used, briefly, in <Ref>.

If a metric space $X$ admits a quasiisometric embedding into a uniformly bounded degree connected graph $\Gamma$ then $X$ has bounded growth on some scale.

Suppose we have some $(\lambda,\mu)$-quasiisometric embedding $\phi: X \rightarrow \Gamma$. Suppose that $D$ is a uniform bound on the degree of vertices of $\Gamma$. We may assume that $\phi$ takes elements of $X$ to vertices of $\Gamma$. Consider an open ball $B$ of radius $R$ in $X$. Then $\phi(B)$ is contained with an open ball $B'$ of radius $\lambda R + \mu$ in $\Gamma$. $B'$ contains at most $D^{\lambda R + \mu}$ vertices. For each vertex $v \in B'$ with $\phi^{-1}(v) \cap B$ non-empty, choose an element $x_v \in B$ with $\phi(x_v) = v$. If we consider balls of radius $\mu$ around all of the $x_v$, we can see that we have covered $B$ by $D^{\lambda R + \mu}$ balls of radius $\mu$.

Let $X$ be a metric space. Sometimes, but not always, we will denote the metric on $X$ by $d_X$, with a subscript to indicate the metric space. Other times, when the metric space is clear, we will just write $d$.

§.§ Groups

Let $G$ be a group and let $S$ be a finite generating set. We use the notation $\Gamma(G,S)$ to indicate the Cayley graph of $G$ with respect to $S$, which is the graph with vertex set $G$ and an edge $\{g,gs\}$ for all $g \in G$ and $s \in S$.

Let $\Gamma(G,S)$ be a Cayley graph and suppose a subgroup $H \leq G$ is generated by some finite set $S_H \subset S$. We may think of the Cayley graph $\Gamma(H,S_H)$ as being a connected subgraph of $\Gamma(G,S)$. Given $g \in G$, we use the notation

\[g\Gamma(H,S_H)\]

to refer to the image of the subgraph $\Gamma(H,S_H)$ under the isometric action of $g$. So $g\Gamma(H,S_H)$ has vertex set $gH$ and the edges correspond to the generators $S_H$.

§.§ Trees

Let $T$ be a simplicial rooted tree with root vertex $v_0$.

* Say that two vertices of $T$ are adjacent if they are distinct and connected by an edge.

* The children of a vertex $v \in T$ are precisely the vertices $v' \in T$ which are adjacent to $v$ and for which $d_T(v_0,v') > d_T(v_0,v)$.

* We say that a vertex $v' \in T$ descends from a vertex $v \in T$ if the unique geodesic from $v_0$ to $v'$ passes through $v$. If $v'$ descends from $v$ then $v$ is an ancestor of $v'$.

* Given two vertices $u, v \in T$, the lowest common ancestor of $u$ and $v$, denoted $\lca(u,v)$, is the common ancestor of $u$ and $v$ with the greatest distance from the basepoint $v_0$.

* We say that $T$ has uniformly bounded valence or uniformly bounded degree or that it is uniformly locally finite if there is a constant $M \in \N$ such that every vertex of $T$ has degree at most $M$.

Now suppose $T$ and $T'$ are simplicial rooted trees with root vertices $v_0$ and $v_0'$ respectively.

* We say that a map $f: T \rightarrow T'$ is height-preserving if for all vertices $v \in T$ we have $d(v_0,v) = d(v_0', f(v))$.

* We say that $f: T \rightarrow T'$ is order-preserving if the following implication holds: if $v'$ descends from $v$ in $T$ then $f(v')$ descends from $f(v)$ in $T'$.

§.§ Words and sentences

§.§.§ Words

An alphabet is just a set of letters. We will often denote alphabets by $A$, $B$ or $C$ and we will often denote letters by $a$ and $b$. We say that the alphabet is finite if there are finitely many letters.

A word is an empty, finite, or infinite string of letters from an alphabet $A$. The length of a word $u$ is the number of letters in it. We denote this by $\length(u)$.

For example, if $A = \{a,b\}$ then $u = abab$ is a word of length $4$ on the alphabet $A$. We will often denote by $W$ the set of all finite words on an alphabet $A$. We will often denote words themselves by the letters $u$, $v$ or $w$. To indicate the concatenation of a pair of words into a longer word, we simply write the two words next to each other. For example, if $u = abab$ and $v = aaa$ then

\[uv = ababaaa\]

We write $\ola{w}$ to denote the word $w$ written backwards. So $\ola{abcd} = dcba$ and so on.

Further, we sometimes need to refer to the position of a letter $a$ within a word $u$. To do this, we might refer to the distance of $a$ from the start or end of $u$. If we say $a$ has distance $d$ from the start of $u$ that means $a$ is the $d$'th letter in the word $u$. If we say that $a$ has distance $d$ from the end of $u$ that means $a$ is the $(\length(u) - d + 1)$'th letter of $u$, or, equivalently, the $d$'th letter of $\ola{u}$. For example, in the word $u = abaca$, the letter $c$ has distance $2$ from the end of $u$ and distance $4$ from the start of $u$.

§.§.§ Sentences

A sentence is a string of words. We will often denote sentences by the Greek letters $\alpha$ and $\beta$. In order to describe the words which make up a sentence, we will use overlines to indicate where one word ends and another begins. For example, if $A = \{a,b\}$ then

\[\alpha = \ol{abab} \ol{aaa} \ol{ba}\]

is a sentence that consists of the three words $abab$, $aaa$ and $ba$. If $u = abab$, $v = aaa$ and $w = ba$ we can also write

\[\alpha = \ol{u} \ \ol{v} \ \ol{w}\]

The purpose of the overlines is so that we can distinguish between the single word $uvw$ and the three word sentence $\ol{u} \ \ol{v} \ \ol{w}$. The length of a sentence is the number of words in it. We denote this by $\length(\alpha)$.

Sentences are, of course, just words on an alphabet of words. To indicate the concatenation of a pair of sentences into a longer sentence, we simply write the two sentences next to each other. For example, if $\alpha = \ol{abab} \ol{aaa} \ol{ba}$ and $\beta = \ol{ab} \ol{a}$ then

\[\alpha \beta  = \ol{abab} \ \ol{aaa} \ \ol{ba} \ \ol{ab} \ \ol{a}\]

Given a sentence $\alpha$ and $m \in \N$, we can write $\alpha^m$ to indicate the sentence $\alpha$ written $m$ times. For example, $(\ol{a} \ol{b})^3 = \ol{a} \ol{b} \ol{a} \ol{b} \ol{a} \ol{b}$.

The following notation will be convenient in <Ref>.

Suppose we have a group $G$ generated by a finite set $S$ and suppose $A = S \cup S^{-1}$ is our alphabet. If $q \in \Z$ and $q < 0$, and if $s \in S$, then $(\ol{s})^q$ indicates the sentence $(\ol{s^{-1}})^{-q}$. For example, $(\ol{s})^{-3} = \ol{s^{-1}} \ \ol{s^{-1}} \ \ol{s^{-1}}$.

§.§.§ Word-trees and sentence-trees

Given an alphabet $A$, we will use the notation $T_A$ to indicate the word-tree on $A$. The tree $T_A$ is defined precisely so that its vertices are in bijection with finite words on the alphabet $A$. Every edge of $T_A$ will be labelled by an element of $A$. The word-tree $T_A$ is defined as follows. As a set, $T_A$ is precisely the rooted tree where every vertex has $\absval{A}$ children. Further, given a vertex $v \in T_A$, the $\absval{A}$ edges which go between $v$ and its children are labelled by the elements of $A$, with every such edge having a label in $A$, and no two such edges having the same label. We will now describe the natural bijection between the vertices of $T_A$ and finite words on the alphabet $A$. First, we associate the empty word $\emptyset$ to the root vertex of $T_A$. Now let $v$ be a vertex in $T_A$. The geodesic from $\emptyset$ to $v$ in $T_A$ travels along a series of labelled edges. These labels, read in order, make up the word that we associate to $v$. Thus every vertex in $T_A$ has a corresponding word on $A$. Indeed, we will often identify them. The vertices at distance $n$ from the root of $T_A$ correspond to words of length $n$ on the alphabet $A$.

The following notation for the rooted binary tree will be used frequently in this paper.

If $A = \{0,1\}$ then $T_{A} = \tb$ is a rooted binary tree whose vertices correspond to finite strings of zeros and ones.

Let $A$ be a finite alphabet and let $W$ be the set of non-empty finite words on $A$. Analogous to the word-tree on $A$, we have a sentence-tree on $A$ which is exactly the tree $T_W$, i.e. the word-tree on $W$. So the vertices of $T_W$ are in bijection with sentences on $A$, and the edges of $T_W$ are labelled by finite words on $A$. The vertices at distance $n$ from the root vertex of $T_W$ correspond to sentences with $n$ words.

Note that if $A$ is a finite alphabet then $T_A$ is a uniformly bounded valence tree, whereas $T_W$ is a tree with countable valence at every vertex.

§.§.§ Notation for pairs of sentences

Let $T_W$ be a sentence-tree and suppose we have a pair of sentences $\alpha$, $\beta \in T_W$. In this paper, this situation will occur so frequently that it is useful to have some standard notation for the words that make up these sentences.

Given sentences $\alpha, \beta \in T_W$, we can always write

\begin{equation} \label{eq.alpha}
\alpha = \ol{u_1} \ \ol{u_2} \dots \ol{u_p} \ \ol{u_{p+1}} \dots \ol{u_{p+m}}
\end{equation}

\begin{equation} \label{eq.beta}
\beta = \ol{u_1} \ \ol{u_2} \dots \ol{u_p} \ \ol{u_{p+1}'} \dots \ol{u_{p+n}'}
\end{equation}

where $u_{p+1} \neq u_{p+1}'$ and $m,n \geq 0$. In (<ref>), $u_1$, $u_2$, …, $u_p$, $u_{p+1}$, …, $u_{p+m-1}$, $u_{p+m}$ are the words that make up the sentence $\alpha$. In (<ref>), $u_1$, $u_2$, …, $u_p$, $u_{p+1}'$, …, $u_{p+n-1}'$, $u_{p+n}'$ are the words that make up the sentence $\beta$. Therefore, the sentence $\ol{u_1} \ \ol{u_2} \dots \ol{u_p}$ is the lowest common ancestor of the sentences $\alpha$ and $\beta$ in the tree $T_W$ and $d_{T_W}(\alpha,\beta) = m+n$.

§ DIARIES

In 100 Years of Solitude a plague of insomnia afflicts the town of Macondo. The most troubling effect of the insomnia plague is that it ultimately leads to memory loss.

One day he was looking for the small anvil that he used for laminating metals and he could not remember its name. His father told him: “Stake.” Aureliano wrote the name on a piece of paper that he pasted to the base of the small anvil: stake. In that way he was sure of not forgetting it in the future. It did not occur to him that this was the first manifestation of a loss of memory, because the object had a difficult name to remember. But a few days later he discovered that he had trouble remembering almost every object in the laboratory. Then he marked them with their respective names so that all he had to do was read the inscription in order to identify them. When his father told him about his alarm at having forgotten even the most impressive happenings of his childhood, Aureliano explained his method to him, and José Arcadio Buendía put it into practice all through the house and later on imposed it on the whole village. With an inked brush he marked everything with its name: table, chair, clock, door, wall, bed, pan. He went to the corral and marked the animals and plants: cow, goat, pig, hen, cassava, caladium, banana. Little by little, studying the infinite possibilities of a loss of memory, he realized that the day might come when things would be recognized by their inscriptions but that no one would remember their use. Then he was more explicit. The sign that he hung on the neck of the cow was an exemplary proof of the way in which the inhabitants of Macondo were prepared to fight against loss of memory: This is the cow. She must be milked every morning so that she will produce milk, and the milk must be boiled in order to be mixed with coffee to make coffee and milk. Thus they went on living in a reality that was slipping away, momentarily captured by words, but which would escape irremediably when they forgot the values of the written letters.

100 Years of Solitude, Gabriel García Márquez

The human effort to record daily events in journals, databases and diaries is an attempt to record as effectively as possible the infinite detail of day-to-day life in finite packets of information. To record everything is a lost cause: you can only hope to record the key features of an event. For example, it is a waste of time to write in your diary The sun rose today. because this always happens. Far better to take note of the events that distinguish the day from every other.

§.§ Diaries

A diary, as defined in this paper, and perhaps in its normal sense as well, is some system of converting infinite quantities of data that occur on days $1,2,3, \dots, i$ into finite diary entries at the end of each day.

A diary is a height-preserving and order-preserving map (with respect to some chosen basepoints) from an infinite-valence tree to a uniformly locally finite tree.

Since a diary is a graph homomorphism, it is always $1$-Lipschitz.

Throughout this section, we will assume that the infinite-valence trees have some extra structure; we will assume that they are sentence-trees as defined in <Ref>. So, for the remainder of this section, we suppose that $A$ is a finite alphabet of letters, we suppose that $W$ is the set of finite but non-empty words on $A$ and we suppose that $T_W$ is the associated sentence-tree. We will also assume that the codomain of a diary is a word-tree $T_\Omega$ for some finite set $\Omega$.

Let $\last: W \rightarrow A$ be the function which outputs the last letter of a word $w \in W$. Then there exists a diary $\ld: T_W \rightarrow T_{A}$ which just outputs the last letter of every word in $\alpha \in T_W$. More precisely,

\[\ld(\ol{w_1} \dots \ol{w_i}) = \last(w_1) \dots \last(w_i)\]

For example, $\ld(\ol{abc} \ \ol{bc} \ \ol{aa}) = c c a$.

The term diary comes from the following metaphor. Every day, our protagonist Alice receives some sort of input data (it could be an image, or a voice note, or a text message) which may be very long, in the form of a finite word in $W$. Every day, she has only a finite amount of time to record the data in her diary, and there are only finite many letters in the English alphabet, and she can only write at a certain pace, and therefore the daily entry in her diary may be summed up as an element of some finite set $\Omega$. Suppose that on days $1,2, \dots, i$ Alice receives the input data $w_1$, $w_2$, …, $w_i \in W$ respectively and in response to this data Alice records $v_1$, $v_2$, …, $v_i \in \Omega$ in her diary. We have thus defined a map $D: T_W \rightarrow T_\Omega$ by $D(\ol{w_1} \dots \ol{w_i}) = \ol{v_1} \dots \ol{v_i}$ and it is a diary: it is height-preserving because Alice writes exactly one diary entry per day and it is order-preserving because Alice does not "re-write" diary entries.

We will be interested in understanding whether a given diary $D: T_W \rightarrow T_\Omega$ can successfully distinguish between two sentences $\alpha, \beta \in T_W$ (meaning that $D(\alpha) \neq D(\beta)$). As the following example demonstrates, this theory can be applied to understanding when we can upgrade quasiisometric embeddings into products of infinite-valence trees to quasiisometric embeddings into products of binary trees. The following example explains how the theorems in this section are used to prove <Ref>. It is the same idea as <Ref>, but now phrased in terms of sentence-trees and word-trees.

Suppose $X$ is a metric space and suppose we have a $(\lambda,\mu)$-quasiisometric embedding $F: X \rightarrow \prod_{q=1}^Q T_W$. Let $P$ be a property of pairs of sentences in $T_W$ (or, what is the same thing, $P$ is a subset of the product $T_W \times T_W$) and suppose we have a diary $D: T_W \rightarrow T_\Omega$ for which there exists a constant $M \geq 1$ such that

\begin{equation} \label{eq.ablb}
d_{T_\Omega}(D(\alpha), D(\beta)) \geq \frac{1}{M} d_{T_W}(\alpha,\beta)
\end{equation}

for all pairs $\alpha$ and $\beta$ satisfying $P$. We are interested in whether the composition

\begin{equation} \label{eq.composition}
X \xrightarrow{F} \prod_{q=1}^Q T_W \xrightarrow{D \times D \times \dots \times D} \prod_{q=1}^Q T_\Omega
\end{equation}

is a quasiisometric embedding. Suppose products are given the $L^1$ metric.

Let $x,z \in X$ and write $F(x) = (\alpha_1, \alpha_2, \dots, \alpha_Q)$ and $F(z) = (\beta_1, \beta_2, \dots, \beta_Q)$. Then $d(F(x),F(z)) = \sum_{q=1}^Q d_{T_W}(\alpha_q,\beta_q)$. Suppose $\mathfrak{q} \in \{1,2,\dots, Q\}$ is such that $d_{T_W}(\alpha_\q,\beta_\q) = \max_q d_{T_W}(\alpha_q,\beta_q)$. Then $d_{T_W}(\alpha_\q,\beta_\q) \geq \frac{1}{Q} d(F(x),F(z))$.

Suppose we manage to prove that the pair $\alpha_\q, \beta_\q \in T_W$ arising in this manner satisfy the property $P$. Then I claim that (<ref>) would be a quasiisometric embedding. The diary $D$ is $1$-Lipschitz and the map $F$ is a quasiisometric embedding so the composition (<ref>) is coarsely Lipschitz. For the lower bound of the quasiisometric inequality we have

\[d_{T_\Omega}(D(\alpha_\q), D(\beta_\q)) \geq \frac{1}{M} d_{T_W}(\alpha_\q,\beta_\q) \geq \frac{1}{QM} d(F(x),F(z)) \geq \frac{1}{\lambda QM} d_X(x,z) - \mu \]

where the first lower bound follows from the fact that $\alpha_\q$ and $\beta_\q$ satisfy $P$. As $\Omega$ is finite, $T_\Omega$ is quasiisometric to a binary tree (assuming $\absval{\Omega} > 1$).

In the remainder of this section, we will provide four criteria $(\aries)$, $(\leo)$, $(\virgo)$ and $(\taurus)$ on pairs of sentences, analogous to the property $P$ in <Ref>, which imply that a certain diary $D$ coarsely preserves the metric on those sentences as in (<ref>).

I do not know how to approach the situation described in <Ref> without assuming that the infinite-valence tree is a sentence-tree. It is for this reason that it is necessary in the proof of <Ref> to find a quasiisometric embedding of $G$ into a product of sentence-trees, as opposed to some abstract infinite-valence trees. This is why the quasiisometric embedding in <Ref> needs to be chosen very carefully.

The ideas behind these criteria stem from the work of Buyalo, Dranishnikov and Schroeder <cit.> on Alice's Diary. Alice's Diary allows one to quasiisometrically embed subsets of products of infinite-valence trees into products of uniformly bounded valence trees in certain circumstances. However, the results that Buyalo, Dranishikov and Schroeder prove on Alice's Diary (in particular <cit.>) are phrased in an ad hoc manner. It was my aim to unravel the ideas and theorems which are latent in their work, and to provide easy to use and flexible criteria so that one may find quasiisometric embeddings into products of binary trees in many contexts.

I would also like to express my appreciation of Buyalo, Dranishnikov and Schroeder's paper. They chose to use metaphor to help the reader understand the Alice's Diary function, and it was this metaphor and the questions it raised that sparked my curiosity on the topic.

§.§ Finite statistics

A finite statistic is a function $\stat: T_W \rightarrow \Omega$ where $\Omega$ is some finite set. If we wish to specify the domain of $\stat$ we say that it is a finite statistic on $T_W$.

You might think of $\stat(\alpha)$ as being a fact about $\alpha$ that contains a uniformly bounded amount of information. It is a statistic in the sense that it is a value which can be calculated from some input data $\alpha$. We can use finite statistics to create diaries as follows.

Suppose we have a finite statistic $\stat: T_W \rightarrow \Omega$ and suppose $T_\Omega$ is the word-tree on $\Omega$. Then the diary $D: T_W \rightarrow T_\Omega$ defined by

\[D(\ol{w_1} \ \ol{w_2} \dots \ol{w_i}) = \stat(\ol{w_1}) \stat(\ol{w_1} \ \ol{w_2}) \dots \stat(\ol{w_1} \ \ol{w_2} \dots \ol{w_i}) \]

is the diary associated to $\stat: T_W \rightarrow \Omega$.

Let $\kappa \in \N$ be a constant and let $\Omega_\kappa$ denote the set of all words in $W$ of length at most $\kappa$. Consider the map $\trunc_\kappa: T_W \rightarrow \Omega_\kappa$ which is such that $\trunc_\kappa(\ol{w_1} \ \ol{w_2} \dots \ol{w_i})$ is equal to the final $\kappa$ letters of the word $w_i$. Then $\trunc_\kappa$ is a finite statistic on $T_W$. The associated diary simply returns the final $\kappa$ letters of each word in the sentence. If the letters in $A$ are thought of as events, and the words in $W$ as sequences of events that occur on a given day, then this diary is the one in which Alice records at the end of the day the $\kappa$ most recent events.

Hypothetically, Alice could be more imaginative in her choice of diary.

Suppose $A = \{0,1\}$ and let $\Omega$ be the set $\{n / 10^{5} : 0 \leq n \leq 10^{5} \}$. Let $\av_5: T_W \rightarrow \Omega$ be defined so that $\av_5(\ol{w_1} \dots \ol{w_i})$ is the element of $\Omega$ closest to the the average value of the string $w_1 w_2 \dots w_i$, rounding up if necessary. Let $D: T_W \rightarrow T_\Omega$ be the associated diary. In other words, on day $i$ Alice records the average of $w_1 w_2 \dots w_i$ up to $5$ decimal places.

We may now provide our first criterion for when there exists a diary that coarsely preserves a pair of sentences.

Let $\scalf$ be a finite collection of finite statistics on the same sentence-tree $T_W$ (but the finite statistics are allowed to have different codomains). Let $0 \leq \delta < 1$, $J \in \N$ be constants. Consider the following property, pronounced Aries, that a pair of sentences $\alpha$ and $\beta$ in the forms described by <Ref> might possess.

We say that $\alpha$, $\beta$ satisfy $\aries(\scalf,\delta,J)$ if there exists some $1 \leq j \leq \delta \min(m,n) + J$ and $\stat \in \scalf$ such that

\[\stat(\ol{u_1} \dots \ol{u_p} \ \ol{u_{p+1}} \dots \ol{u_{p+j}}) \neq \stat(\ol{u_1} \dots \ol{u_p} \ \ol{u_{p+1}'} \dots \ol{u_{p+j}'})\]

Property ($\aries$) is saying that there exists a fact about $\alpha$ and $\beta$ which distinguishes them and which only requires a finite amount of information to state. The purpose of the constants $\delta$ and $J$ is to ensure that this distinguishing fact separates $\alpha$ and $\beta$ sufficiently close to their lowest common ancestor $\ol{u_1} \dots \ol{u_p}$.

There exists a finite set $\Omega = \Omega(\scalf)$, a diary $D = D(\scalf)$ which is a function $D: T_W \rightarrow T_\Omega$, and a constant $M = M(\delta,J) \geq 1$, such that

\[\frac{1}{M} d_{T_W}(\alpha,\beta) \leq d_{T_{\Omega}}(D\alpha,D\beta) \leq d_{T_W}(\alpha,\beta)\]

for all $\alpha,\beta$ satisfying $\aries(\scalf,\delta,J)$.

Write $\scalf = \{\stat^k: T_W \rightarrow \Omega^k : 1 \leq k \leq K \}$. We begin by combining all the finite statistics in $\scalf$ into a single finite statistic $\bigstat: T_W \rightarrow \Omega$. Set $\Omega = \prod_{k = 1}^K \Omega^k$. We define $\bigstat: T_W \rightarrow \Omega$ by

\[
\bigstat(\ol{w_1} \dots \ol{w_i}) =
\begin{pmatrix}
\stat^1(\ol{w_1} \dots \ol{w_i}) \\
\stat^2(\ol{w_1} \dots \ol{w_i}) \\
\vdots \\
\stat^K(\ol{w_1} \dots \ol{w_i})
\end{pmatrix}
\]

Let $D: T_W \rightarrow T_\Omega$ be the diary associated to $\bigstat$. More explicitly

\[D(\ol{w_1} \dots \ol{w_i}) = \bigstat(\ol{w_1}) \bigstat(\ol{w_1} \  \ol{w_2}) \dots \bigstat(\ol{w_1} \ \ol{w_2} \dots \ol{w_i})\]

Suppose $\alpha,\beta$ satisfy $\aries(\scalf, \delta,J)$. Then there exists $1 \leq j \leq \delta \min(m,n) + \delta$ and $1 \leq k \leq K$ such that $\stat^k(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}}) \neq \stat^k(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}'})$. It follows that $\bigstat(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}}) \neq \bigstat(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}'})$ and so

\[d_{T_\Omega}(D\alpha,D\beta) \geq (p+m) - (p+j-1) + (p+n) - (p+j-1) = m+n - 2j + 2\]

We have two cases: either $m+n < 4J / (1 - \delta)$ or $m+n \geq 4J / (1 - \delta)$. In the first case, we have

\[d_{T_\Omega}(D\alpha,D\beta) \geq m+n - 2j + 2 \geq 2 = \frac{1 - \delta}{2J} \frac{4J}{1 - \delta} \geq \frac{1 - \delta}{2J} (m+n)\]

In the second case, we have

\[d_{T_\Omega}(D\alpha,D\beta) \geq m+n - 2j + 2 \geq m+n - \delta (m+n) - 2J \geq \frac{1-\delta}{2} (m+n)\]

So if we set $M = 2J / (1 - \delta)$ then we are done.

So we may now address the situation described in <Ref>: if the sentences $\alpha_\q, \beta_\q \in T_W$ satisfy $\aries(\scalf,\delta,J)$ for some uniform choices of $\scalf$, $\delta$ and $J$, then the diary $D = D(\scalf)$ given by <Ref> will be such that (<ref>) is a quasiisometric embedding.

We say that $\alpha,\beta \in T_W$ satisfy $\leo(\scalf,J)$ if they satisfy $\aries(\scalf,0,J)$. This property is pronounced Leo.

In the next section, we are going to introduce Buyalo, Dranishnikov and Schroeder's Alice's Diary. Afterwards, in <Ref>, Alice's Diary will be used to create diaries that are more powerful than the ones which are made via finite statistics.

§.§ Alice's Diary

Let us add some more texture to our diary metaphor. We refer to a letter chosen from the finite alphabet $A$ as an event. On each day, several events occur in some order (thereby forming a word in $W$), and at the end of each day Alice dedicates $\kappa \in \N$ minutes to diary writing. Alice can write down one letter per minute and so records at most $\kappa$ letters in her diary each day. On each page she writes down only one letter, and so on each day she fills in at most $\kappa$ pages of her diary. The pages of her diary corresponding to a single day form a chapter. Alice wants to record the events on days $1,2,3,4,5,6,7, \dots$ to the best of her ability. She has perfect memory of past events but seems to always be paranoid that one day she might forget everything and only her diary will be left behind to remind her of what occurred.

If $\Omega_\kappa$ is the set of all words of length at most $\kappa$ on the alphabet $A$, then Alice's diary writing process defines a diary $D: T_W \rightarrow T_{\Omega_\kappa}$ (assuming she responds deterministically to possible sequences of events). A vertex in $T_W$ corresponds to some possible sequence of events over the course of several days, and a vertex in $T_{\Omega_\kappa}$ corresponds to a possible sequence of chapters in the diary.

The diary described in <Ref>, in which Alice simply records the final $\kappa$ events of the day provides an example of this sort of diary. However, this truncation diary might be very inefficient.

Let $\trunc_\kappa: T_W \rightarrow \Omega_\kappa$ be the truncation statistic from <Ref> and suppose $\kappa = 4$. Let $D: T_W \rightarrow T_{\Omega_\kappa}$ denote the associated truncation diary. Suppose we have some sentence $\alpha = \ol{w_1} \ \ol{w_2} \dots \ol{w_i} \in T_W$ such that half of the words in $\alpha$ have length $2$, and the other half of the words in $\alpha$ have length $8$. Then the diary $D: T_W \rightarrow T_{\Omega_4}$ described above is very wasteful: on the days when only two events occur Alice records only two letters in her diary as opposed to her maximum of 4 - she could have used that spare time to write about previous days on which eight events occurred! And indeed, the total amount of wastefulness (or viewed another way, the potential for gains in efficiency) is in the order of $i$ where $i$ is the length of the word $\alpha$.

The inefficiency of the truncation diary motivates the definition of Alice's Diary. Alice's Diary was invented by Buyalo, Dranishnikov and Schroeder <cit.>.

Alice's Diary $\ad_\kappa: T_W \rightarrow T_{\Omega_\kappa}$ is characterised by the following rule: Alice always records the most recent unrecorded event first.

It is easiest to understand Alice's Diary through an example. I have also provided a formal and non-metaphorical definition in the appendix, see <Ref>.

Let $A = \{a,b,c\}$ and $\kappa = 3$. Suppose that on day one, at first event $a$ occurs, then event $b$, then event $a$ again and then event $c$. So the associated word is $abac$. Since $\kappa = 3$, Alice only has time to write down $3$ letters at the end of the day, and so she records $cab$. That's because event $c$ occured most recently, then event $a$, then event $b$. Suppose that on day two, the associated word is $cb$. Then Alice writes down in her diary $bca$. The final $a$ she writes down was the first event of day one. Now suppose that on days three, four and five, the associated events are $accc$, $bcbc$ and $a$ respectively. Then the chapters that Alice records in her diary at the end of days three, four and five are $ccc$, $cbc$, $aba$. In the chapter corresponding to day five, the first page records an event from day five, the second page records an event from day four, and the third page records an event from day three. So we have shown that $\ad_3: T_W \rightarrow T_\Omega$ satisfies $\ad_3(\ol{abac} \ \ol{cb} \ \ol{accc} \ \ol{bcbc} \ \ol{a}) = \ol{cab} \ \ol{bca} \ \ol{ccc} \ \ol{cbc} \ \ol{aba}$.

So Alice's Diary is a greedy algorithm for creating diaries.

We would now like to understand how much information $\ad_\kappa$ captures about the original sentence. What does this mean? One interpretation is that we would like to understand when $\alpha \neq \beta \implies \ad_\kappa(\alpha) \neq \ad_\kappa(\beta)$. The statement that $\alpha \neq \beta$ roughly amounts to saying that the two sentences have letters which are in the same position yet correspond to a different element of $A$. You might call these "clashing" letters. So we would like to understand when the existence of clashing letters implies that $\ad_\kappa(\alpha) \neq \ad_\kappa(\beta)$. If we take the contrapositive of this statement, we find ourselves studying whether $\ad_\kappa(\alpha) = \ad_\kappa(\beta)$ implies that two letters in the same position in $\alpha$, $\beta$ must be the same element of $A$. Hopefully this justifies why the conclusion of <Ref> below is significant.

But first, we want to assume that our sentences $\alpha$ have some further structure.

Suppose that our alphabet $A$ contains a special character $\star$. We say that a word $u \in W$ is starred if $u = \star w$ for some word $w \in W$ that does not contain the letter $\star$. We say that a sentence $\alpha \in T_W$ is starred if all the constituent words of $\alpha$ are starred. Maybe $\star$ corresponds to the event of sunrise.

The primary reason to work with starred words is so that you can say the following: if $u$ and $u'$ are distinct starred words then there exist distinct letters $a \in u$ and $a' \in u'$ with the same distance to the end of their words.

In <Ref>, <Ref>, <Ref> and <Ref> that follow, we will always assume that we have two starred sentences $\alpha = \ol{\star u_1} \ \ol{\star u_2} \dots \ol{\star u_m}$ and $\beta = \ol{\star u_1'} \ \ol{\star u_2'} \dots \ol{\star u_n'}$ in $T_W$ and that $\ad_\kappa(\alpha) = \ol{v_1} \ \ol{v_2} \dots \ol{v_m}$ and $\ad_\kappa(\beta) = \ol{v_1'} \ \ol{v_2'} \dots \ol{v_n'}$.

Suppose the diary chapter $v_i$ has the form $v_i = u \star v$ where $u$ does not contain the letter $\star$. Then $u_i = \ola{u}$.

At the end of day $i$, Alice sets out writing her diary. She starts by recording the events of day $i$. If she does not fully record the events of day $i$, then there can be no $\star$ in that day's chapter. Since $v_i = u \star v$, it follows that Alice records day $i$ in its entirety. Since Alice always records the most recent events first, her recording of day $i$ must come at the start of the word $v_i$ and the $\star$ in $\star u_i$ must be the first $\star$ of chapter $i$. It follows that $u_i = \ola{u}$.

Suppose that $\ad_\kappa(\alpha) = \ad_\kappa(\beta)$. If a word $\star u_i$ has length at most $\kappa$ then $u_i' = u_i$. Similarly, if a word $\star u_j'$ has length at most $\kappa$ then $u_j = u_j'$.

Suppose $\star u_i$ has length at most $\kappa$. It follows that $v_i$ is of the form $\ola{u_i} \star v$ for some word $v$. Since $v_i' = v_i$, by <Ref> we deduce that $u_i' = u_i$. The case when $\star u_j'$ has length at most $\kappa$ follows similarly.

Let $i \leq \min(m,n)$ and suppose $a \in \star u_i$ and $a' \in \star u_i'$ are letters such that

* $a,a'$ have the same distance from the end of their words;

* there exists $i \leq j \leq \min(m,n)$ and $1 \leq k \leq \kappa$ such that event $a$ is recorded on page $k$ of diary chapter $v_j$;

* $u_l$ has the same length as $u_l'$ for $i+1 \leq l \leq j$.

Then $a'$ is recorded on page $k$ of diary chapter $v_j'$

Write $\star u_i = vaw$ and $\star u_i' = v'a'w'$. The content of the first condition is that $w$ has the same length as $w'$. The position of $a$ within the diary words $\ol{v_i} \ \ol{v_{i+1}} \dots \ol{v_{j}}$ depends only on the lengths of the words $w, u_{i+1}, \dots, u_j$. Similarly, the position of $a'$ within the diary words $\ol{v_i'} \ \ol{v_{i+1}'} \dots \ol{v_{j}'}$ depends only on the lengths of the words $w', u_{i+1}', \dots, u_j'$. It follows that $a$ and $a'$ appear on the same page of $v_j$ and $v_j'$ respectively.

Suppose that $\ad_\kappa(\alpha) = \ad_\kappa(\beta)$. Let $a$ be a letter in the word $\star u_i$ and let $a'$ be a letter in the word $\star u_i'$ and suppose

* $a,a'$ have the same distance from the end of their words;

* The events $a$ and $a'$ are recorded in the diaries of $\alpha$ and $\beta$.

Then there exists $i \leq j \leq m$ and $1 \leq k \leq \kappa$ such that $a,a'$ appear on page $k$ of chapters $v_j$ and $v_j'$ respectively. Consequently, $a,a'$ correspond to the same element of $A$.

Write $\star u_i = vaw$ and $\star u_i' = v'a'w'$. The content of the first condition on $a,a'$ is that $w$ has the same length as $w'$. If $a$ is recorded within $v_i$ then it follows that $aw$ and $a'w'$ both have length at most $\kappa$ and the conclusion clearly holds. So assume that $a$ is recorded within $v_j$ for some $i+1 \leq j \leq m$. Then clearly $\star u_j$ has length at most $\kappa$ and so <Ref> implies that $u_j = u_j'$. We will prove by induction that $u_l = u_l'$ for $i+1 \leq l \leq j$. So fix $i+1 \leq l \leq j$ and suppose $u_{l+1} = u_{l+1}', u_{l+2} = u_{l+2}', \dots, u_j = u_j'$. Looking for a contradiction, suppose that $u_l \neq u_l'$. Then we can find distinct letters $b \in \star u_l$ and $b' \in \star u_l'$ with the same distance to the end of their words. We also know that $b$ must appear in one of the diary words $v_l$, $v_{l+1}, \dots, v_{j}$ because for Alice to record event $a$ in chapter $v_j$, she must already have recorded event $b$ on some earlier page of the diary. It then follows from <Ref>, and the fact that the diaries are equal, that $b$ and $b'$ correspond to the same element of $A$, which is a contradiction. Thus $u_l = u_l'$.

So we have shown that $u_l = u_l'$ for all $i+1 \leq l \leq j$. We can now apply <Ref> again to conclude that $a$ and $a'$ appear on the same page of $v_j = v_j'$ and thus are equal.

In my view, the above theorem is the fundamental observation on Alice's Diary. To paraphrase it: if you know two diaries are equal, and if you have two events that are

* recorded in the diary;

* occur on the same day;

* are in the same position (with respect to the ends of their words);

then those two events correspond to the same element of $A$.

It leads us naturally to trying to understand when we can guarantee that an event is recorded in the diary. We need some further definitions.

Suppose we have a sentence $\alpha = \ol{u_1} \ \ol{u_2} \dots \ol{u_m} \in T_W$ and suppose $a$ is some letter in $u_i$. We can write $u_i = vaw$ where $v$ and $w$ are some words on the alphabet $A$. Then the sentence

\[ \ol{aw} \ \ol{u_{i+1}} \dots \ol{u_m} \]

is the tail-sentence of $a$. Similarly, the sentence

\[\ol{u_1} \dots \ol{u_{i-1}} \ \ol{va}\]

is the head-sentence of $a$.

In terms of our analogy, the tail-sentence of $a$ consists of $a$ and every event that happens after $a$. The head-sentence of $a$ consists of $a$ and every event that happens before $a$.

The average word length (AWL) of a sentence $\alpha = \ol{u_1} \ \ol{u_2} \dots \ol{u_m} \in T_W$ is the amount of letters in $u_1 u_2 \dots u_m$ divided by $m$. We will often write $\awl(\alpha)$ to denote the average word length of $\alpha$.

Suppose $\alpha = \ol{u_1} \ \ol{u_2} \dots \ol{u_m} \in T_W$ and let $a$ be some letter in $u_i$. Suppose that the tail-sentence of $a$ has average word length $N \geq 1$. If $\kappa \geq N$ then $a$ is recorded in $\ad_\kappa(\alpha)$.

We will prove the contrapositive. Suppose that $a$ is not recorded in $\ad_\kappa(\alpha)$. Write $\ad_\kappa(\alpha) = \ol{v_1} \ \ol{v_2} \dots \ol{v_m}$. A chapter only has fewer than $\kappa$ pages when Alice has successfully recorded all past events already. It follows that $v_i$, $v_{i+1}$, …, $v_m$ all have $\kappa$ pages. Since Alice would only record an event that happened prior to $a$ if $a$ had already been recorded, we know that every page of the chapters $v_i$, $v_{i+1}$, …, $v_m$ corresponds to an event that happened after $a$. It follows that the tail-sentence of $a$ has at least $\kappa(m - i + 1) + 1$ letters. It consists of $m-i+1$ words and hence the average word length of the tail-sentence is greater than $\kappa$.

Suppose $\alpha$, $\beta$ are starred sentences in $T_W$. Write

\[\alpha = \ol{u_1} \ \ol{u_2} \dots \ol{u_p} \ \ol{u_{p+1}} \dots \ol{u_{p+m}} \]

\[\beta = \ol{u_1} \ \ol{u_2} \dots \ol{u_p} \ \ol{u_{p+1}'} \dots \ol{u_{p+n}'}\]

where $u_{p+1} \neq u_{p+1}'$. Write $\ad_\kappa(\alpha) = \ol{v_1} \ \ol{v_2} \ \dots \ \ol{v_{p+m}}$ and $\ad_\kappa(\beta) = \ol{v_1'} \ \ol{v_2'} \ \dots \ \ol{v_{p+n}'}$. Suppose we have letters $a \in u_{p+j}$ and $a' \in u_{p+j}'$ which satisfy the following

* $a$ and $a'$ correspond to different elements of the alphabet $A$;

* $a$ and $a'$ are at equal distance from the ends of their words;

* the AWL of the tail-sentence of $a$ is $N$ and the AWL of the tail-sentence of $a'$ is $N'$;

Let $i \in \N_0$ be such that $p+j+i \leq p+\min(m,n)$. If $\kappa \geq N \frac{m-j+1}{i+1}$ and $\kappa \geq N' \frac{n-j+1}{i+1}$ then

\[d(\ad_\kappa(\alpha),\ad_\kappa(\beta)) \geq d(\alpha,\beta) -2j - 2i \]

Suppose the amount of letters in the tail-sentence of $a$ is $l$ and the amount of letters in the tail-sentence of $a'$ is $l'$. Then $N = \frac{l}{m-j+1}$ and $N' = \frac{l'}{n-j+1}$. Consider the truncated sentences $\alpha_{p+j+i} = \ol{u_1} \dots \ol{u_{p+j+i}}$ and $\beta_{p+j+i} = \ol{u_1} \dots \ol{u_{p+j+i}'}$. The AWL of the tail-sentence of $a \in \alpha_{p+j+i}$ is at most $\frac{l}{i+1} = N \frac{m-j+1}{i+1}$. So, by <Ref>, if $\kappa \geq N \frac{m-j+1}{i+1}$ then $a$ is recorded in $\ad_\kappa(\alpha_{p+j+i})$. Similarly, if $\kappa \geq N' \frac{n-j+1}{i+1}$ then $a'$ is recorded in $\ad_\kappa(\beta_{p+j+i})$. It then follows from <Ref> that $\ad_\kappa(\alpha_{p+j+i}) \neq \ad_\kappa(\beta_{p+j+i})$ and the corollary follows.

§.§ Linear statistics

<Ref> provides a way of roughly preserving the metric on pairs of sentences $\alpha,\beta \in T_W$ (of the forms described in <Ref>) when there is a uniform bound $L$ on the length of the words $u_{p+1}, u_{p+2}, \dots, u_{p+m}$ and $u_{p+1}', u_{p+2}', \dots, u_{p+n}'$. When this is the case, we may choose the finite statistic $\trunc_L: T_W \rightarrow \Omega_L$ and the constants $\delta = 0$, $J = 1$. With these choices, the sentences $\alpha, \beta$ will satisfy $\aries(\trunc_L, 0, 1)$. However, in the "real-life" situations that arise from attempting to quasiisometrically embed groups into products of binary trees, we will need to deal with situations in which there is no uniform bound on the words $u_{p+1}, u_{p+2}, \dots, u_{p+m}, u_{p+1}', u_{p+2}', \dots, u_{p+n}'$. However, we will often find that these words are short on average. It is for these situations that we will need linear statistics and their associated diaries.

Intuitively, where a finite statistic is some uniformly bounded quantity that can be calculated from a sentence $\ol{w_1} \ \ol{w_2} \dots \ol{w_i}$, a linear statistic is a quantity that can be calculated from $\ol{w_1} \ \ol{w_2} \dots \ol{w_i}$ that contains a linear amount of information with respect to some variable $c \in \N_0$.

Suppose, as ever, we have a finite alphabet $A$ and an associated sentence-tree $T_W$. Suppose we have another, potentially distinct, finite alphabet $B$ and let $T_B$ be the word-tree on $B$. Given a number $c \in [0,\infty]$ let $\Omega_c$ denote all words on the alphabet $B$ of length at most $c$. So we can identify the sets $\Omega_c$ with subsets of the vertices of $T_B$. A linear statistic on $T_W$ consists of a constant $\tau \geq 1$ and a collection of finite statistics $\{\stat_c: T_W \rightarrow \Omega_{\tau c} : c \in \N_0\}$ such that if $c \leq c'$ then $\stat_{c'}(\ol{w_1} \dots \ol{w_i})$ descends from $\stat_{c}(\ol{w_1} \dots \ol{w_i})$ in $T_B$. We will typically denote a linear statistic just by $\stat_c: T_W \rightarrow \Omega_{\tau c}$ as opposed to $\{\stat_c : T_W \rightarrow \Omega_{\tau c} : c \in \N_0\}$. Associated to every linear statistic $\stat_c: T_W \rightarrow \Omega_{\tau c}$ is an infinite statistic $\stat_{\infty}: T_W \rightarrow \Omega_\infty$ defined by $\stat_\infty(\ol{w_1} \dots \ol{w_i}) = \lim_{c \rightarrow \infty} \stat_c(\ol{w_1} \dots \ol{w_i})$.

So $\stat_{c}(\ol{w_1} \dots \ol{w_i})$ is a collection of facts about the sentence $\ol{w_1} \dots \ol{w_i}$ that contain steadily more information as $c$ increases. Since the image of $\stat_c$ is in $\Omega_{\tau c}$, the amount of information contained in the word $\stat_c(\ol{w_1} \dots \ol{w_i})$ is comparable in size to $c$. If $\stat_{c'}(\ol{w_1} \dots \ol{w_i})$ descends from $\stat_{c}(\ol{w_1} \dots \ol{w_i})$ that means that the former contains at least as much information as the latter. This happens when when $c \leq c'$.

Let's now consider some examples of linear statistics.

Let $B = A$. If we define $\trunc_c(\ol{w_1} \dots \ol{w_i})$ to be the final $\tau c$ letters of the word $u_i$ written backwards (i.e. starting from the final letter) then $\trunc_c: T_W \rightarrow \Omega_{\tau c}$ is a linear statistic.

Let $B = A$. Let $l = \length(w_1 w_2 \dots w_i)$. Let $a_1, a_2, \dots, a_l$ denote all the letters in the word $w_1 w_2 \dots w_i$. Let $\sigma \in S_l$ be a permutation which we call the order of priority. We can define $\oop(\sigma)_c: T_W \rightarrow \Omega_{\tau c}$ by letting $\oop(\sigma)_c(\ol{w_1} \dots \ol{w_i})$ be the first $\tau c$ letters of the word $a_{\sigma(1)} a_{\sigma(2)} \dots a_{\sigma(l)}$. Then $\oop(\sigma)$ is a linear statistic.

Let $B = \{0\}$. We can define $\howmany_c: T_W \rightarrow \Omega_c$ by setting

\[
\howmany_c(\ol{w_1} \dots \ol{w_i}) =
\begin{cases}
\emptyset & \textrm{if } \length(w_i) > c \\
0 & \textrm{if } \length(w_i) \leq c
\end{cases}
\]

Then $\howmany_c$ is a linear statistic. You might even just identify $\howmany_c$ with the question "does $w_i$ have at most $c$ letters?".

Let $B = A$. Let $\ol{w_1} \dots \ol{w_i} \in T_W$ and let $a_1, a_2, \dots, a_l$ denote all the letters in the word $w_1 w_2 \dots w_i$. Suppose we define $\periodic_c: T_W \rightarrow \Omega_c$ by setting $\periodic_c(\ol{w_1} \dots \ol{w_i}) = a_1 a_{\lfloor l / c \rfloor} a_{2 \lfloor l / c \rfloor} a_{3 \lfloor l / c \rfloor} \dots a_{c \lfloor l / c \rfloor}$. So $\periodic_c(\ol{w_1} \dots \ol{w_i})$ outputs the word formed by taking every $\lfloor l/c \rfloor$'th letter of the word $w_1 w_2 \dots w_i$. One might reasonably think that this is a linear statistic on $T_W$ since $\periodic_c(\ol{w_1} \dots \ol{w_i})$ is a word that contains $c$ letters. But it fails to satisfy the defining condition of a linear statistic: there is no reason to think that $\periodic_{c'}(\ol{w_1} \dots \ol{w_i})$ will descend from $\periodic_c(\ol{w_1} \dots \ol{w_i})$ when $c' > c$.

We now come to our second criterion. Let $\scall$ be a finite collection of linear statistics on the same tree $T_W$ (but the linear statistics are allowed to have different codomains). Let $0 \leq \delta < 1$, $J \in \N$, $N > 0$, $\epsilon > 0$ be constants. Consider the property, pronounced Virgo, that a pair of vertices $\alpha, \beta \in T_W$ of the form described in <Ref> might possess. It is somewhat analogous to ($\aries$).

We say that $\alpha$, $\beta$ satisfy $\virgo(\scall,\delta,J,N,\epsilon)$ if there exists some $1 \leq j \leq \delta \min(m,n) + J$ and $\stat_c \in \scall$ such that

($\virgo 1$)  $\awl(\ol{u_{p+j+1}} \dots \ol{u_{p+m}})$ and $\awl(\ol{u_{p+j+1}'} \dots \ol{u_{p+n}'})$ are both at most $N$;
($\virgo 2$)  $\length(u_{p+j}) \geq \epsilon (m+n)$ or $\length(u_{p+j}) \geq \epsilon (m+n)$ or $u_{p+j} \neq u_{p+j}'$;
($\virgo 3$) $\stat_{m+n}(\ol{u_1} \dots \ol{u_p} \ \ol{u_{p+1}} \dots \ol{u_{p+j}}) \neq \stat_{m+n}(\ol{u_1} \dots \ol{u_p} \ \ol{u_{p+1}'} \dots \ol{u_{p+j}'})$.

($\virgo$) is saying that there exists some fact about $\alpha$ and $\beta$ which distinguishes them. However, unlike in the case of ($\aries$) and ($\leo$), this fact can now contain an unbounded amount of information, as long as the amount of information is at most linear with respect to $m+n = d_{T_W}(\alpha,\beta)$. The cost of this upgrade is that you very much need the $\awl$ of the tail-sentences to be uniformly bounded.

There exists a finite set $\Omega = \Omega(\scall,\delta,J,N,\epsilon)$, a diary $D = D(\scall,\delta,J,N,\epsilon)$ which is a function $D: T_W \rightarrow T_\Omega$, and a constant $M = M(\delta,J) \geq 1$, such that

\[\frac{1}{M} d_{T_W}(\alpha,\beta) \leq d_{T_{\Omega}}(D\alpha,D\beta) \leq d_{T_W}(\alpha,\beta)\]

for all $\alpha,\beta$ satisfying $\virgo(\scall,\delta,J,N,\epsilon)$.

The theorem is powerful for this reason: when $m+n = d_{T_W}(\alpha,\beta)$ is very large, $\stat_{m+n}(\ol{u_1} \dots \ol{u_p} \ \ol{u_{p+1}} \dots \ol{u_{p+j}})$ and $\stat_{m+n}(\ol{u_1} \dots \ol{u_p} \ \ol{u_{p+1}'} \dots \ol{u_{p+j}'})$ contain vast amounts of information about our sentences and so <ref> is more likely to hold.

* write $\scall = \{\stat_c^k : 1 \leq k \leq K\}$;

* let $\tau^k \geq 1$ be the constant associated to the linear statistic $\stat_c^k$;

* let $B^k$ denote the finite alphabet associated to the linear statistic $\stat^k_c$;

* let $\stat^k_\infty$ denote the infinite statistic associated to $\stat^k_c$;

* let $\tau = \max_k \tau^k$;

* let $\omega$ be the smallest natural number which is at least $\tau / \epsilon$;

* let $\star$ and $\bigstar$ be two special letters.

Let $u = b_1 b_2 b_3 \dots$ be a word on some alphabet, and let $l = \length(u)$. For $r \in \N$, we define

\[\norm_r(u) =
\begin{cases}
b_1 b_2 \dots b_r & r \leq l \\
b_1 b_2 \dots b_l (\star)^{r-l} & r > l
\end{cases}
\]

So $\norm_r(u)$ is the same as $u$ except it has been either truncated or otherwise extended by $\star$'s so that it has exactly $r$ letters (the word has been "normalised"). Recall that $\ola{u}$ is the word $u$ written backwards.

If $\ol{w_1} \dots \ol{w_i}$ is an element of $T_W$ then we define a function $\widehat{\stat_\infty^k}$ with domain $T_W$ by

\[\widehat{\stat_\infty^k}(\ol{w_1} \dots \ol{w_i}) = \ola{\norm_{\omega \length(w_i)}(\stat_\infty^k(\ol{w_1} \dots \ol{w_i}))}\]

So $\widehat{\stat_\infty^k}(\ol{w_1} \dots \ol{w_i})$ is a word on the alphabet $B^k \cup \star$ of length exactly $\omega \length(w_i)$. Let $W'$ denote the set of finite words on the finite alphabet

\[A' = \bigstar \cup \left(A \times \prod_{k = 1}^K (B^k \cup \star) \right)\]

Then we have a map $I: T_W \rightarrow T_{W'}$ given by

\[I(\ol{w_1}\dots\ol{w_i}) =
\ol{
\bigstar
\begin{pmatrix}
(w_1)^\omega \\
\widehat{\stat_\infty^1}(\ol{w_1}) \\
\widehat{\stat_\infty^2}(\ol{w_1}) \\
\vdots \\
\widehat{\stat_\infty^K}(\ol{w_1})
\end{pmatrix}
\
\ol{
\bigstar
\begin{pmatrix}
(w_2)^\omega \\
\widehat{\stat_\infty^1}(\ol{w_1} \ \ol{w_2}) \\
\widehat{\stat_\infty^2}(\ol{w_1} \ \ol{w_2}) \\
\vdots \\
\widehat{\stat_\infty^K}(\ol{w_1} \ \ol{w_2})
\end{pmatrix}
\dots
\ol{
\bigstar
\begin{pmatrix}
(w_i)^\omega \\
\widehat{\stat_\infty^1}(\ol{w_1} \ \ol{w_2} \dots \ol{w_i}) \\
\widehat{\stat_\infty^2}(\ol{w_1} \ \ol{w_2} \dots \ol{w_i}) \\
\vdots \\
\widehat{\stat_\infty^K}(\ol{w_1} \ \ol{w_2} \dots \ol{w_i})
\end{pmatrix}
\]

It can be checked that $I$ is an isometric embedding: evidently it is height-preserving and order-preserving, and it is injective since if $I(\ol{w_1} \dots \ol{w_i}) = I(\ol{w_1'} \dots \ol{w_i'})$ then $(w_l)^\omega = (w_l')^\omega$ for all $1 \leq l \leq i$ and so $w_l = w_l'$ for all $1 \leq l \leq i$.

\[U = \frac{12 \tau J}{1 - \delta} + \omega N + 1 \quad \textrm{and} \quad V = \frac{12(\tau + \epsilon)J}{1 - \delta} + \omega N + 1\]

and let $\kappa$ be the smallest natural number that is larger than $\frac{16U}{1 - \delta}$ and $\frac{64J\tau}{1-\delta}$ and $\frac{16V}{1 - \delta}$ and $\frac{64J(\tau+\epsilon)}{1-\delta}$. Let $\ad_\kappa: T_{W'} \rightarrow T_{\Omega_\kappa}$ be Alice's Diary for the value of $\kappa$ given above. Let $D = \ad_\kappa \circ I$. The map $D: T_W \rightarrow T_{\Omega_\kappa}$ is a diary since it is height-preserving and order-preserving. Suppose $\alpha, \beta \in T_W$ satisfy $\virgo(\scall,\delta,J,N,\epsilon)$, and suppose, as ever, that they have the form given by <Ref>. We can assume that

\begin{equation} \label{eq.mnub}
m \leq 2 \min(m,n) \quad \textrm{and} \quad n \leq 2 \min(m,n)
\end{equation}

otherwise, we would have $\absval{m - n} \geq (m+n)/3$ and so $d(D\alpha, D\beta) \geq (m+n)/3$ and we would be done by choosing $M(\delta,J) \geq 3$. Let $1 \leq j \leq \delta \min(m,n) + J$ and $\stat^k_c \in \scall$ be those given by condition $\virgo(\scal,\delta,J,N,\epsilon)$. We have three cases: $\length(u_{p+j}) \geq \epsilon (m+n)$ or $\length(u_{p+j}') \geq \epsilon (m+n)$ or $u_{p+j} \neq u_{p+j}'$.

Case 1: We suppose first that $\length(u_{p+j}) \geq \epsilon (m+n)$.

Either (1) or (2) below occurs.

* There exist letters

\[ b \in \widehat{\textup{stat}_\infty^k}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}}) \]

\[b' \in \widehat{\textup{stat}_\infty^k}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}'}) \]

which are distinct and at the same distance $d \leq \tau(m+n)$ from the end of their words;

* $\length(\widehat{\textup{stat}_\infty^k}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}})) \geq \tau(m+n)$ but $\length(\widehat{\textup{stat}_\infty^k}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}'})) < \tau(m+n)$.

First, note that $\length(\widehat{\textup{stat}_\infty^k}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}})) \geq \tau (m+n)$ since $\length((u_{p+j})^\omega) = \omega \length(u_{p+j}) \geq \omega \epsilon (m+n) \geq \tau (m+n)$.

Now suppose that (2) doesen't occur, i.e. $\length(\widehat{\textup{stat}_\infty^k}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}'})) \geq \tau(m+n)$. So $\tau(m+n) \leq \omega \length(u_{p+j}')$. For a contradiction, suppose that (1) also doesen't occur. Then the final $\tau(m+n)$ letters of $\widehat{\textup{stat}_\infty^k}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}})$ and $\widehat{\textup{stat}_\infty^k}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}'})$ must be the same. It follows that the first $\tau(m+n)$ letters of $\norm_{\omega \length(u_{p+j})}(\stat_\infty^k(\ol{u_1} \dots \ol{u_{p+j}}))$ and $\norm_{\omega \length(u_{p+j}')}(\stat_\infty^k(\ol{u_1} \dots \ol{u_{p+j}'}))$ must be the same. But $\norm_{\omega \length(u_{p+j})}(\stat_\infty^k(\ol{u_1} \dots \ol{u_{p+j}}))$ contains $\stat_{m+n}^k(\ol{u_1} \dots \ol{u_{p+j}}))$ as an initial subword since $\tau(m+n) \leq \omega \length(u_{p+j})$. Similarly, $\norm_{\omega \length(u_{p+j}')}(\stat_\infty^k(\ol{u_1} \dots \ol{u_{p+j}'}))$ contains $\stat_{m+n}^k(\ol{u_1} \dots \ol{u_{p+j}'}))$ as an initial subword since $\tau(m+n) \leq \omega \length(u_{p+j}')$. We have a contradiction since $\stat_{m+n}^k(\ol{u_1} \dots \ol{u_{p+j}})) \neq \stat_{m+n}^k(\ol{u_1} \dots \ol{u_{p+j}'}))$.

It follows from the claim that there exist letters

\[
\in
\bigstar
\begin{pmatrix}
(u_{p+j})^\omega \\
\widehat{\stat_\infty^1}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}}) \\
\widehat{\stat_\infty^2}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}}) \\
\vdots \\
\widehat{\stat_\infty^K}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}})
\end{pmatrix}
\quad \textrm{and} \quad
\in
\bigstar
\begin{pmatrix}
(u_{p+j}')^\omega \\
\widehat{\stat_\infty^1}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}'}) \\
\widehat{\stat_\infty^2}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}'}) \\
\vdots \\
\widehat{\stat_\infty^K}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}'})
\end{pmatrix}
\]

which are distinct and both at distance $d \leq \tau (m+n)$ from the end of their words (in case (2) you choose $b'$ to be the $\bigstar$ at the beginning of the word). Now, suppose that the sentence $\ol{u_{p+j+1}}\dots\ol{u_{p+m}}$ has exactly $l$ letters. This implies that the tail-sentence of

\[
\in
\]

has at most $\tau(m+n) + \omega l + (m-j)$ letters. So it has average word length at most

\[\frac{\tau(m+n) + \omega l + (m-j)}{m-j+1} \leq \tau\frac{m+n}{m-j} + \omega N + 1 \leq \tau\frac{3m}{m-j} + \omega N + 1\]

where we have used that $\awl(\ol{u_{p+j+1}} \dots \ol{u_{p+m}}) = l / (m-j) \leq N$ together with (<ref>). We now need to divide into two subcases: either $J \leq \frac{1 - \delta}{16} \min(m,n)$ or $J > \frac{1 - \delta}{16} \min(m,n)$.

Case 1a: We suppose $J \leq \frac{1 - \delta}{16} \min(m,n)$. In particular, we have $J \leq \frac{1 - \delta}{2} \min(m,n)$ and $2 \leq \frac{1 - \delta}{8}(m+n)$. Then the average word length of $b \in I(\alpha)$ is at most

\[\tau\frac{3m}{m-j} + \omega N + 1 \leq \tau \frac{3m}{m - \delta m - J} + \omega N + 1 \leq \tau \frac{6}{1 - \delta} + \omega N + 1 \leq U\]

By similar arguments, the average word length of the tail-sentence of $b' \in I(\beta)$ is also at most $U$. In order to apply <Ref> to the starred sentences $I(\alpha)$ and $I(\beta)$, we choose

\[i = \left\lceil \frac{\min(m,n) - j}{2} \right\rceil\]

from which it follows that

\[U \frac{m-j+1}{i+1} \leq 4U \frac{m - j}{\min(m,n) - j} \leq 4U \frac{2 \min(m,n)}{\min(m,n) - \delta \min(m,n) - J} = \frac{16U}{1 - \delta} \leq \kappa\]

and similarly $U \frac{n-j+1}{i+1} \leq \kappa$. Hence, <Ref> tells us that

\begin{align*}
d(\ad_\kappa \circ I(\alpha), \ad_\kappa \circ I(\alpha)) &\geq d_{T_{W'}}(I(\alpha),I(\beta)) - 2j - 2i \\
&= (m - j - i) + (n - j - i) \\
&\geq ((m-j)/2 - 1) + ((n-j)/2 - 1) \\
&\geq ((m-\delta m - J)/2) + ((n-\delta n - J)/2) - 2 \\
&\geq \frac{(1 - \delta)m}{4} + \frac{(1 - \delta)n}{4} - 2 \\
&\geq \frac{(1 - \delta)(m+n)}{4} - \frac{(1 - \delta)(m+n)}{8} \\
&= \frac{1 - \delta}{8} d_{T_W}(\alpha,\beta)
\end{align*}

If we choose $M(\delta,J) \geq 8 / (1 - \delta)$ then we are done in this case.

Case 1b: We suppose $J > \frac{1 - \delta}{16} \min(m,n)$. Then, using (<ref>), we have $m,n \leq \frac{32J}{1-\delta}$ and so $m+n \leq \frac{64J}{1-\delta}$. Recall that $b \in I(\alpha)$ and $b' \in I(\beta)$ are both at distance $d \leq \tau (m+n)$ from the ends of their words. So, since $\kappa \geq \frac{64J\tau}{1-\delta} \geq \tau(m+n) \geq d$, they are distance at most $\kappa$ from the ends of their words. It follows that Alice records the events $b$ and $b'$ on page $d$ of chapter $p+j$ of the diary. It follows that chapter $p+j$ of $\ad_\kappa \circ I(\alpha)$ is distinct from chapter $p+j$ of $\ad_\kappa \circ I(\beta)$. Hence,

\begin{align*}
d(\ad_\kappa \circ I(\alpha), \ad_\kappa \circ I(\alpha)) &\geq (p+m) - (p+j-1) + (p+n) - (p+j-1) \\
&= m+n - 2j + 2 \\
&\geq 2 \\
&= \frac{1-\delta}{32J} \frac{64J}{1-\delta} \\
&\geq \frac{1-\delta}{32J} (m+n)
\end{align*}

So if we choose $M(\delta,J) \geq \frac{32J}{1 - \delta}$ then we are done in this case too.

Case 2: We are done for symmetrical reasons in the case when $\length(u_{p+j}') \geq \epsilon (m+n)$.

Case 3: Finally, we suppose that $\length(u_{p+j}) \leq \epsilon (m+n)$, $\length(u_{p+j}') \leq \epsilon (m+n)$ and $u_{p+j} \neq u_{p+j}'$. Two possibilities can occur: (1) there exist distinct letters $a \in (u_{p+j})^\omega$ and $a' \in (u_{p+j}')^\omega$ which are at the same distance from the end of their words and this distance is at most $\epsilon \omega (m+n) \leq (\tau + \epsilon)(m+n)$ or (2) $\length((u_{p+j})^\omega) \neq \length((u_{p+j}')^\omega)$. In either case, it follows that there exist distinct letters $b \in I(\alpha)$ and $b' \in I(\beta)$ which occur on the $(p+j)$'th day and which have equal distance $d \leq (\tau + \epsilon)(m+n)$ from the ends of their words. The proof now proceeds along the same lines as Case 1 and Case 2; a similar argument, splitting into cases depending on the magnitude of $J$, will give us that $d(\ad_\kappa \circ I(\alpha), \ad_\kappa \circ I(\alpha)) \geq \frac{1 - \delta}{32J} d_{T_W}(\alpha, \beta)$.

We will now define another useful criterion, pronounced Taurus, which makes use of the fact that we always know that $u_{p+1} \neq u_{p+1}'$ when $\alpha$ and $\beta$ have the form given by <Ref>. It is somewhat analogous to condition $\leo(\scalf,J)$. As before, suppose that $\scall$ is some finite collection of linear statistics on $T_W$ (with possibly different codomains) and that $J \in \N$, $N > 0$ and $\epsilon > 0$ are constants.

We say that $\alpha$, $\beta$ satisfy $\taurus(\scall, J, N, \epsilon)$ if there exists some $1 \leq j \leq J$ such that

($\taurus 1$)  $\awl(\ol{u_{p+j+1}} \dots \ol{u_{p+m}})$ and $\awl(\ol{u_{p+j+1}'} \dots \ol{u_{p+n}'})$ are both at most $N$;
($\taurus 2$)   if $1 \leq j' \leq j$ is such that we have $\length(u_{p+j''}) \leq \epsilon (m+n)$ and $\length(u_{p+j''}') \leq \epsilon (m+n)$ for all $j' < j'' \leq j$  then there exists $\stat_c \in \scall$ such that $\stat_{m+n}(\ol{u_1} \dots \ol{u_p} \ \ol{u_{p+1}} \dots \ol{u_{p+j'}}) \neq \stat_{m+n}(\ol{u_1} \dots \ol{u_p} \ \ol{u_{p+1}'} \dots \ol{u_{p+j'}'})$.

There is no denying that <ref> is ugly. But you can observe that if we replaced <ref> with the following more friendly condition

($\taurus 2'$) for all $1 \leq j' \leq j$ there exists $\stat_c \in \scall$ such that $\stat_{m+n}(\ol{u_1} \dots \ol{u_p} \ \ol{u_{p+1}} \dots \ol{u_{p+j'}}) \neq \stat_{m+n}(\ol{u_1} \dots \ol{u_p} \ \ol{u_{p+1}'} \dots \ol{u_{p+j'}'})$.

then we would have created a new property, called $(\taurus')$, which implies $(\taurus)$. So $(\taurus)$ is a weaker (and thus easier to prove) condition. And indeed the weaker form will be needed in the proof of <Ref>. It is also worth noting that <ref> implies that there exists a linear statistic $\stat_c \in \scall$ such that $\stat_{m+n}(\ol{u_1} \dots \ol{u_p} \ \ol{u_{p+1}} \dots \ol{u_{p+j}}) \neq \stat_{m+n}(\ol{u_1} \dots \ol{u_p} \ \ol{u_{p+1}'} \dots \ol{u_{p+j}'})$.

There exists a finite set $\Omega = \Omega(\scall,J,N,\epsilon)$, a diary $D = D(\scall,J,N,\epsilon)$ which is a function $D: T_W \rightarrow T_\Omega$, and a constant $M = M(J) \geq 1$, such that

\[\frac{1}{M} d_{T_W}(\alpha,\beta) \leq d_{T_{\Omega}}(D\alpha,D\beta) \leq d_{T_W}(\alpha,\beta)\]

for all $\alpha,\beta$ satisfying $\taurus(\scall,J,N,\epsilon)$.

Suppose that $\alpha,\beta$ satisfy $\taurus(\scall, J, N, \epsilon)$. We let the map $D: T_W \rightarrow T_{\Omega}$ be the diary $D(\scall,0,J,N + 6J^2\epsilon,\epsilon)$ given by <Ref>.

Note that if $m < (m+n) / 3$ then $n > 2 (m+n) / 3$ and so $\absval{m - n} > (m+n) / 3$, which implies $d_{T_\Omega}(D\alpha,D\beta) \geq (m+n) / 3$. So we are done when $m < (m+n) / 3$ by choosing $M = M(J) \geq 3$. Similarly we are done if $n < (m+n) /3$. So we can assume that $m,n \geq (m+n) / 3$.

$\alpha$ and $\beta$ satisfy $\virgo(\scall,0,J,N+6J^2\epsilon,\epsilon)$

Since $\alpha, \beta$ satisfy $\taurus(\scall, J, N, \epsilon)$, we know that there exists $1 \leq j \leq J$ such that <ref> and <ref> hold. In particular, $\awl(\ol{u_{p+j+1}}\dots\ol{u_{p+m}}) \leq N \leq N + 6J^2\epsilon$, $\awl(\ol{u_{p+j+1}'}\dots\ol{u_{p+n}'}) \leq N \leq N + 6J^2\epsilon$ and there exists $\stat_c \in \scal$ such that $\stat_{m+n}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}}) \neq \stat_{m+n}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j}'})$. Hence, if $\length(u_{p+j}) \geq \epsilon (m+n)$ or $\length(u_{p+j}) \geq \epsilon (m+n)$ then $\alpha, \beta$ satisfy $\virgo(\scall, 0, J, N + 6J^2\epsilon,\epsilon)$ and the claim is proved. So we can assume both lengths are at most $\epsilon (m+n)$. But this implies that

\begin{align*}
\awl(\ol{u_{p+j}} \dots \ol{u_{p+m}}) &= \frac{ \length(u_{p+j+1} \dots u_{p+m}) + \length(u_{p+j})}{m-j+1} \\
&\leq \awl(\ol{u_{p+j+1}}\dots\ol{u_{p+m}}) + \frac{\epsilon(m+n)}{m-j+1} \\
&\leq N + \frac{3\epsilon m}{m-J+1} \\
\begin{cases}
N + 6\epsilon & \textrm{when $m \geq 2J$} \\
N + 6J\epsilon & \textrm{when $m \leq 2J$}
\end{cases} \\
&\leq N + 6J^2 \epsilon
\end{align*}

and similarly $\awl(\ol{u_{p+j}'} \dots \ol{u_{p+n}'}) \leq N + 6J^2$. It also implies, since $\alpha$ and $\beta$ satisfy $\taurus(\scall, J, N, \epsilon)$, that there exists $\stat_c \in \scall$ such that $\stat_{m+n}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j-1}}) \neq \stat_{m+n}(\ol{u_1} \dots \ol{u_p} \dots \ol{u_{p+j-1}'})$. So if $\length(u_{p+j-1}) \geq \epsilon (m+n)$ or $\length(u_{p+j-1}') \geq \epsilon (m+n)$ then the claim is proved. So we can assume that they are both at most $\epsilon (m+n)$. Continuing in this way, we can assume that $\length(u_{p+2})$, $\length(u_{p+3})$, …, $\length(u_{p+j})$ and $\length(u_{p+2}')$, $\length(u_{p+3}')$, …, $\length(u_{p+j}')$ are all at most $\epsilon (m+n)$. It follows that $\awl(\ol{u_{p+2}} \dots \ol{u_{p+m}})$ and $\awl(\ol{u_{p+2}'} \dots \ol{u_{p+n}'})$ are both at most $N + 6J^2\epsilon$. Since $u_{p+1} \neq u_{p+1}'$, $\alpha$ and $\beta$ satisfy $\virgo(\scall, 0, J, N + 6J^2\epsilon,\epsilon)$ and the claim is proved.

It follows that if $M = M(0,J)$ is the constant given by <Ref> then we have

\[\frac{1}{M} d_{T_W}(\alpha,\beta) \leq d_{T_{\Omega}}(D\alpha,D\beta) \leq d_{T_W}(\alpha,\beta)\]

and we are done.

Recall the definition of $\leo(\scalf,J)$ from <Ref>. The following corollary combines conditions $\leo(\scalf,J)$ and conditions $\taurus(\scall,J,N,\epsilon)$ so that we can use them simultaneously.

Let $\scalf$ be a finite collection of finite statistics, let $\scall$ be a finite collection of linear statistics, let $\jf \in \N$, let $\jl \in \N$, let $N \geq 1$, and finally let $\epsilon > 0$.

Then there exists a finite set $\Omega = \Omega(\scalf,\scall, \jl, N,\epsilon)$, a diary $D = \\ D(\scalf,\scall,\jl, N,\epsilon)$ which is a function $D: T_W \rightarrow T_\Omega$, and a constant $M = M(\jf, \jl)$, such that

\[\frac{1}{M} d_{T_W}(\alpha,\beta) \leq d_{T_{\Omega}}(D\alpha,D\beta) \leq d_{T_W}(\alpha,\beta)\]

for all $\alpha,\beta$ satisfying $\leo(\scalf, \jf)$ or $\taurus(\scall, \jl, N, \epsilon)$.

Let $\df: T_W \rightarrow T_{\omegaf}$ be the diary $D(\scalf)$ given by <Ref>, and let $\mf = \mf(0,\jf)$ be the associated constant. Let $\dl: T_W \rightarrow T_{\omegal}$ be the diary $D(\scall,\jl,N,\epsilon)$ given by <Ref>, and let $\ml = \ml(\jl)$ be the associated constant. Let $\Omega = \omegaf \times \omegal$; we think of $\Omega$ as being a finite alphabet. Define $M = \max(\mf,\ml)$. We define the diary $D: T_W \rightarrow T_{\Omega}$ by

\[
D(\ol{w_1} \dots \ol{w_i}) =
\begin{pmatrix}
\df(\ol{w_1}) \\
\dl(\ol{w_1}) \\
\end{pmatrix}
\begin{pmatrix}
\df(\ol{w_1} \ \ol{w_2}) \\
\dl(\ol{w_1} \ \ol{w_2}) \\
\end{pmatrix}
\dots
\begin{pmatrix}
\df(\ol{w_1} \ \ol{w_2} \dots \ol{w_i}) \\
\dl(\ol{w_1} \ \ol{w_2} \dots \ol{w_i}) \\
\end{pmatrix}
\]

Suppose that $\alpha,\beta \in T_W$ satisfy $\leo(\scalf,\jf)$ or $\taurus(\scall, \jl, N, \epsilon)$. Since $D$ is a diary, we have $d_{T_{\Omega}}(D\alpha,D\beta) \leq d_{T_W}(\alpha,\beta)$. If $\alpha, \beta$ satisfy $\leo(\scalf,\jf)$ then

\[d_{T_{\Omega}}(D\alpha,D\beta) \geq d_{T_{\omegaf}}(\df\alpha,\df\beta) \geq \frac{1}{\mf}d_{T_W}(\alpha,\beta)\]

If $\alpha, \beta$ satisfy $\taurus(\scall, \jl, N,\epsilon)$ then

\[d_{T_{\Omega}}(D\alpha,D\beta) \geq d_{T_{\omegal}}(\dl\alpha,\dl\beta) \geq \frac{1}{\ml}d_{T_W}(\alpha,\beta)\]

In either case,

\[d_{T_{\Omega}}(D\alpha,D\beta) \geq \frac{1}{M}d_{T_W}(\alpha,\beta)\]

and so we are done.

It should hopefully be clear that the above argument can be repeated in order to combine any of the criteria $(\aries)$, $(\leo)$, $(\virgo)$, $(\taurus)$.

<Ref> is used repeatedly in the proof of <Ref>. <Ref> gives an idea as to how <Ref> is used in the proof of <Ref>. First, we need to thoughtfully choose the data $\scalf,\scall,\jl, N, \epsilon$ at the start of the proof in order to define the map $D(\scalf,\scall,\jl, N, \epsilon)$ given by <Ref> which is a function $D: T_W \rightarrow T_\Omega$. We then analyse all the possible pairs $\alpha_\q$, $\beta_\q$ to ensure that they satisfy $\leo(\scalf, \jf)$ or $\taurus(\scall, \jl, N, \epsilon)$. You might think of this as finding a finite or linear (with respect to $m+n = d_{T_W}(\alpha_\q, \beta_\q)$) fact which distinguishes $\alpha_\q$ from $\beta_\q$. Once this is done, we have proved that there exists a quasiisometric embedding $X \rightarrow \prod_{q=1}^Q T_\Omega$.

If a reader would like to the see the criteria $(\leo)$ and $(\virgo)$ in action in a relatively simple setting then they should read <Ref> in which these ideas are applied in order to quasiisometrically embed the hyperbolic plane into a product of binary trees. The theorems in this current section and also those in the next section (which is short) suffice for the understanding of this example.

§ THE MORSE–THUE SEQUENCE

A remarkable feature of the Buyalo, Dranishnikov and Schroeder paper is their use of the Morse–Thue sequence in the proof of their result. We will also use the Morse–Thue sequence when proving <Ref>.

Consider the substitution rule $0 \mapsto 01$ and $1 \mapsto 10$. Then start from $0$ and perform the substitutions

\[0 \mapsto 01 \mapsto 0110 \mapsto 01101001 \mapsto \dots\]

to obtain a nested family of sequences $t_k$ of length $2^k$ in the alphabet $\{0,1\}$. The resulting limit sequence is called the Morse–Thue sequence.

We will use the notation $\mt(n)$ to refer to the $n$th term of the Morse–Thue sequence. We will use the notation $\mt[a,b]$ to refer to the substring of the Morse–Thue sequence between the $a$th term and the $b$th term (inclusive). Given a finite word $u = a_1 a_2 \dots a_l$ on some alphabet $A$, we define $\mt(u) := \mt(1)\mt(2)\dots\mt(l) = \mt[1,l]$.

An amazing property of the sequence is the following.

The Morse–Thue sequence is cube-free: it contains no string of the form $www$ where $w$ is any word on the alphabet $\{0,1\}$.

<Ref> has the following corollary.

Suppose we have two identical substrings of the Morse–Thue sequence of length $3k$. Denote these substrings by $\mt[a-3k+1, a]$ and $\mt[b-3k+1, b]$. Then

\[ \absval{a - b} \leq k \implies a = b \]

The above corollary says that if you take a substring $w$ of the Morse–Thue sequence, then you cannot shift $w$ a small amount and land on an identical substring.

Suppose $\absval{a - b} \leq k$ and $a \neq b$. Suppose, without loss of generality, that $a > b$. The key observation is that $\mt(n) = \mt(n + a - b)$ for $b - 3k + 1 \leq n \leq b$. Hence,

\[w = \mt[b-3k+1,b-3k+1+(a-b-1)]\]

is the same string as

\[w' = \mt[b-3k+1+(a-b),b-3k+1+(a-b-1)+(a-b)]\]

which in turn is the same string as
\[w'' = \mt[b-3k+1+2(a-b),b-3k+1+(a-b-1)+2(a-b)]
\]

The substrings $w,w',w''$ are adjacent and equal in the Morse–Thue sequence and so we have a contradiction.

The following corollary describes how we will apply the Morse–Thue sequence.

Let $A$ be a finite alphabet and let $T_A$ be the word-tree on $A$ (whose vertices are in bijection with the free monoid $A^*$). Suppose $w,w' \in A^*$ are distinct words on $A$ that satisfy $d_{T_A}(w,w') \leq k$. Then either the final $3k$ letters of $w$ and $w'$ are distinct or the final $3k$ letters of $\mt(w)$ and $\mt(w')$ are distinct.

If $\length(w) < 3k$ or $\length(w') < 3k$ then obviously the final $3k$ letters of $w$ and the final $3k$ letters of $w'$ are distinct. So we may assume that $\length(w) \geq 3k$ and $\length(w') \geq 3k$. Suppose that the final $3k$ letters of $\mt(w)$ are the same as the final $3k$ letters of $\mt(w')$. Since $\absval{\length(w) - \length(w')} \leq k$, it follows from <Ref> that $\length(w) = \length(w')$. Since $d_{T_A}(w,w') \leq k$, it follows that there exists letters $a \in w$ and $a' \in w'$ which are distinct and at the same distance $d \leq k/2$ from the end of their words. It follows that the final $3k$ letters of $w$ and $w'$ are distinct.

§ REGULAR MAPS AND BINARY TREES

The notion of a regular map notably appears in the work of Benjamini, Schramm and Timár <cit.> on separation profiles since separation profiles are monotone under regular maps.

Let $\phi: V(\Gamma) \rightarrow V(\Gamma')$ be a map between the vertex sets of connected bounded degree graphs $\Gamma$, $\Gamma'$. We say that $\phi$ is regular if $\phi$ is Lipschitz and if there is a uniform bound on the cardinality of $\phi^{-1}(v)$.

Two important examples of regular maps are coarse embeddings and subgroup inclusion. It is possible to define a regular map between arbitrary metric spaces, but we will not do so here. In the lemma below, the maps $\phi$ and $\Phi$ should be interpreted as having vertex sets as domain and codomain, although this is dropped from the notation.

Suppose $\phi: \Gamma \rightarrow \prod_{q=1}^Q \tb$ is a regular map of a bounded degree graph (with base vertex $v_0 \in \Gamma$) into the product of $Q$ binary trees. Then there exists a finite alphabet $C$, with associated word-tree $T_C$, and a Lipschitz embedding $\Phi: \Gamma \rightarrow \prod_{q = 1}^{Q} T_C$ such that

* $\Phi(v)$ is a vertex for all vertices $v \in \Gamma$;

* $\Phi$ is injective on the vertices of $\Gamma$;

* the basepoint $v_0 \in \Gamma$ is mapped by $\Phi$ to the product of the roots $\mathbf{\emptyset} = (\emptyset,\emptyset, \dots, \emptyset)$.

Let $m \in \N$ be a uniform upper bound on the amount of vertices in $\phi^{-1}(v)$. Let $n \in \N$ and let $T$ denote the $n$-ary rooted tree. That is, $T$ is the rooted tree such that every vertex has $n$ children. I think it is clear that if $n \in \N$ is much larger than $m$ then by adjusting $\phi$ by a uniformly bounded amount, we can define an injective and coarsely Lipschitz map $\Phi: \Gamma \rightarrow \prod_{q=1}^Q T$ which takes $v_0 \in \Gamma$ to the basepoint of $\prod_{q=1}^Q T$. Further, a coarsely Lipschitz map whose domain is the vertex set of a graph is in fact Lipschitz. So $\Phi$ is Lipschitz on the vertices of $\Gamma$.

Finally, by setting $C = \{1,2,3, \dots, n\}$, we can identify $T$ with the word-tree $T_C$. This completes the proof of the lemma.

§ PROJECTION COMPLEXES

§.§ Background

Various metric spaces can be understood by considering projections of subspaces onto other subspaces. As we shall see in <Ref>, due to work of Sisto, the metric of a relatively hyperbolic group can be understood by considering projections of peripheral cosets onto other peripheral cosets <cit.>. Similarly, the metric on the mapping class group $MCG(\Sigma)$ can be understood by considering the projection of curves in $\Sigma$ onto curve complexes of subsurfaces of $\Sigma$ <cit.> <cit.>. Bestvina, Bromberg and Fujiwara <cit.> innovated two structures that you can associate to such metric spaces: the projection complex $\pc$ and the quasi-tree of metric spaces $\qtoms$. Bestvina, Bromberg and Fujiwara also found a general set of conditions that a set of projections must satisfy such that $\pc$ and $\qtoms$ exist. The theory of projection complexes and quasi-trees of metric spaces is outlined effectively and properly in <cit.>, though in this section I briefly provide some of the necessary background.

Let $\Y$ be an indexing set such that for each $Y \in \Y$ we have an associated geodesic metric space $\C(Y)$. Suppose also that for each $Y \in \Y$ we have a function

\[\pi_Y: \Y \setminus \{Y\} \rightarrow \textrm{non-empty subsets of } \C(Y)\]

We call these functions projections. We then define $d_Y^\pi: \Y \setminus \{Y\} \times \Y \setminus \{Y\} \rightarrow [0,\infty]$ by

\[d_Y^\pi(X,Z) = \diam(\pi_Y(X) \cup \pi_Y(Z))\]

We call these functions the projection distances. The collection of maps $\{\pi_Y\}$ satisfy the projection axioms if there exists a constant $\xi < \infty$, known as the projection constant, such that

(P3) $\diam(\pi_Y(X)) \leq \xi$ for all distinct $X,Y \in \Y$;
(P4) if $X,Y,Z \in \Y$ are distinct and such that $d_Y^\pi(X,Z) > \xi$ then $d_X^\pi(Y,Z) \leq \xi$;
(P5) $\{Y : d_Y^\pi(X,Z) > \xi\}$ is finite for each pair $X,Z \in \Y \setminus \{Y\}$.

The axioms <ref> - <ref> are those that appear in "real-life", however we need them to satisfy an extra axiom in order to conduct the theory of projection complexes. The collection of maps $\{\pi_Y\}$ satisfy the strong projection axioms if, in addition to <ref> - <ref>, the following condition also holds

(P4') if $X,Y,Z \in \Y$ are distinct and such that $d_Y^\pi(X,Z) > \xi$ then $\pi_X(Y) = \pi_X(Z)$.

Bestvina, Bromberg and Fujiwara prove that, given projections $\{\pi_Y\}$ satisfying the projection axioms, we can adjust the projections $\pi_Y(X)$ by a uniformly bounded amount so that the projections $\{\pi_Y\}$ now satisfy the strong projection axioms with respect to some possibly larger projection constant $\theta$. This is the content of the following theorem (see <cit.>).

Suppose we have a collection of maps $\{\pi_Y\}$ satisfying the projection axioms with projection constant $\xi$. Then there exists a new collection of projections

\[ \{\pi_Y': \Y \setminus \{Y\} \rightarrow \textrm{non-empty subsets of } \C(Y) \}\]

such that if $d_Y(X,Z) := \diam(\pi_Y'(X) \cup \pi_Y'(Z))$ then

* $\pi_Y'(X) \subseteq N_\xi(\pi_Y(X))$;

* $\{\pi_Y'\}$ now satisfy the strong projection axioms <ref> - <ref> and <ref> with respect to the projection constant $\theta = 11\xi$;

* $d_Y^\pi - 2\xi \leq d_Y \leq d_Y^\pi + 2\xi$.

Further, if all the metric spaces $\C(Y)$ are graphs, and all the projections $\pi_Y(X) \subset \C(Y)$ are collections of vertices, then $\pi_Y'(X) \subset \C(Y)$ is also a collection of vertices.

The Further part of the above theorem may be deduced from the definition of $\pi_Y'(X)$ in <cit.>. Indeed, one may write $\pi_Y'(X)$ as a union $\bigcup_W \pi_Y(W)$ where the union is over a non-empty set.

Given a collection of projections $\{\pi_Y : Y \in \Y\}$ with projection distances $d_Y: \Y \setminus \{Y\} \times \Y \setminus \{Y\} \rightarrow [0,\infty)$ and projection constant $\theta$ satisfying the strong projection axioms, we can now define standard paths, the projection complex and the quasi-tree of metric spaces.

For a constant $K \geq 0$, define

\[\Y_K(X,Z) = \{Y \in \Y : d_Y(X,Z) > K\}\]

\[\Y_K[X,Z] = \Y_K(X,Z) \cup \{X,Z\}\]

In what follows, we will also use the notation

\[L(X,Z) = \absval{\Y_K(X,Z)}\]

\[L[X,Z] = \absval{\Y_K[X,Z]}\]

One should interpret the statement $Y \in \Y_K(X,Z)$ as saying that $Y$ is between $X$ and $Z$.

The projection complex is the graph $\pc$ with vertex set $\Y$ and an edge between two vertices if $\Y_K(X,Z) = \emptyset$.

We now state three results which describe the structure of the sets $\Y_K[X,Z]$. These are Lemma 2.3, Proposition 2.4 and Corollary 2.6 of <cit.> respectively.

For $K \geq 2\theta$, and $Y,Y' \in \Y_K(X,Z)$, the following conditions are equivalent

* $d_Y(X,Y') > \theta$;

* $d_{Y'}(Y,Z) > \theta$;

* $d_Y(Y',Z) \leq \theta$;

* $d_{Y'}(X,Y) \leq \theta$;

* $d_Y(Y',W) = d_Y(Z,W)$ for all $W \neq Y$;

* $d_{Y'}(Y,W) = d_{Y'}(X,W)$ for all $W \neq Y'$.

Given $K \geq 2\theta$ and two distinct elements $Y, Y' \in \Y_K(X,Z)$, we write $Y < Y'$ if any of the above equivalent conditions hold. Write $X < Y$ and $Y < Z$ for all $Y \in \Y_K(X,Z)$ and write $X < Z$.

Suppose $K \geq 2\theta$. The relation $<$ on $\Y_K[X,Z]$ defines a total order with least element $X$ and greatest element $Z$. Further, if $Y < Y' < Y''$ in $\Y_K[X,Z]$ then $d_{Y'}(Y, Y'') = d_{Y'}(X,Z)$.

Let $K \geq 2\theta$. Suppose $Y, Y'' \in \Y_K[X,Z]$ and for some $Y' \in \Y$ we have $d_{Y'}(Y,Y'') > K$. Then $Y' \in \Y_K(X,Z)$.

We now state some important facts about the graph $\pc$. These are Lemma 3.1, Theorem 3.5, Lemma 3.6 and Corollary 3.7 from <cit.> respectively.

Let $K \geq 2\theta$. Suppose $\Y_K[X,Z] = \{X < X_1 < \dots < X_k < Z\}$. Then

\[X \rightarrow X_1 \rightarrow \dots \rightarrow X_k \rightarrow Z\]

is a path in $\pc$.

We refer to the sets $\Y_K[X,Z]$ as standard paths in $\pc$. Note that for any $X,Z \in \Y$ we have $\Y_K[X,Z] = \Y_K[Z,X]$ as a set, and $\Y_K[Z,X]$ is the path $\Y_K[X,Z]$ walked in reverse.

For $K \geq 3\theta$, $\pc$ is a quasi-tree.

Suppose $K \geq 2\theta$. Let $X,Y,Z$ be distinct elements of $\Y$. Write $\Y_K[X,Y] = \{X = Y_0 < Y_1 < \dots < Y_k < Y_{k+1} < Y\}$ and $\Y_K[Y,Z] = \{Y = Z_0 < Z_1 < \dots < Z_l < Z_{l+1} < Z\}$. Then the standard path $\Y_K[X,Z]$ is the concatenation of three disjoint segments:

* it begins with an initial segment $X \rightarrow Y_1 \rightarrow \dots \rightarrow Y_i$ in $\Y_K[X,Y]$ for some $0 \leq i \leq k$;

* it then has a (possibly empty) middle segment with at most $2$ vertices which are in neither $\Y_K[X,Y]$ or $\Y_K[Y,Z]$;

* finally, it ends with a terminal segment $Z_{j} \rightarrow Z_{j+1} \rightarrow \dots \rightarrow Z_l \rightarrow Z$ for some $1 \leq j \leq l+1$.

The above lemma is the key to understanding the geometry of the projection complex. It says that the standard paths $\Y_K[X,Z]$, $\Y_K[X,Y]$, $\Y_K[Y,Z]$ almost form a tripod. Instead, the three standard paths have a cycle of length at most $9$ in their centre. See <Ref>.

A triangle of standard paths. Taken from <cit.>.

For $K \geq 3\theta$, standard paths are quasigeodesics; for all $X,Z \in \Y$ we have

\[(L[X,Z] - 1)/2 \leq d_{\pc}(X,Z) \leq L[X,Z] - 1\]

§.§ Quasi-trees of metric spaces

Suppose again that $\{\pi_Y : Y \in \Y\}$ satisfies <ref> - <ref> and  <ref> with respect to the projection constant $\theta$. Suppose also that $K \geq 3\theta$.

The quasi-tree of metric spaces $\qtoms$ is built by taking the disjoint union of the metric spaces $\C(Y)$ and then adding an edge of length $K$ between every element of $\pi_X(Y)$ and every element of $\pi_Y(X)$ whenever there is an edge between $X$ and $Y$ in $\pc$. We will often refer to one of the edges between $\pi_X(Y)$ and $\pi_Y(X)$ as a transverse edge.

The name of $\qtoms$ comes from the fact that crushing all the disjoint metric spaces $\C(Y)$ that make up $\qtoms$ to points leaves us with the quasi-tree $\pc$.

It is useful to extend the definitions of $\pi_Y$, $d_Y$ and $\Y_K(\cdot , \cdot )$ over to elements $x \in \C(X) \subseteq \qtoms$.

For $x \in \C(X) \subseteq \qtoms$ and $z \in \C(Z) \subseteq \qtoms$ and $Y \in \Y$

* we define
$\pi_Y(x) =
\begin{cases}
\pi_Y(X) & \text{if $Y \neq X$} \\
\{x\} & \textrm{if $Y = X$}
\end{cases}

* we define $d_Y(x,z) = \diam(\pi_Y(x) \cup \pi_Y(z))$ where the diameter is taken with respect to the metric on $\C(Y)$;

* we define $\Y_K(x,z) = \{Y \in \Y : d_Y(x,z) > K\}$.

We then have the following distance formula for $\qtoms$ <cit.>. It says that we can approximate distances in $\qtoms$ by just looking at the projections.

If $K \geq 4\theta$, then for all $x \in \C(X) \subseteq \qtoms$ and $z \in \C(Z) \subseteq \qtoms$ we have

\[\frac{1}{4} \sum_{Y \in \Y_K(x,z)} d_Y(x,z) \leq d_{\qtoms}(x,z) \leq 2 \sum_{Y \in \Y_K(x,z)} d_Y(x,z) + 3K\]

§.§ Constructing a tree of metric spaces

Suppose we have a collection of projections $\{\pi_Y : Y \in \Y\}$ with projection distances $d_Y: \Y \setminus \{Y\} \times \Y \setminus \{Y\} \rightarrow [0,\infty)$ and projection constant $\theta$ that satisfy axioms <ref> - <ref> and <ref>. Let $K \geq 4\theta$.

Let $B \in \Y$ be a fixed basepoint. This corresponds to a vertex of $\pc$. We can define the following subgraph of $\pc$.

\[\T_K(\Y,B) := \bigcup_{X \in \Y} \Y_K[B,X] \]

We will generally write $\T = \T_K(\Y,B)$ for simplicity. In the above, $\Y_K[B,X]$ should be interpreted as a path that includes the relevant edges as described in <Ref>.

By definition $\T$ is a connected subgraph of $\pc$ that must contain all the vertices of $\pc$.

The subgraph $\T \subseteq \pc$ is a tree.

First we need a preliminary lemma.

Let $\Y_K[X,Z] = \{X = X_0 < X_1 < \dots< X_k < X_{k+1} = Z\}$ be the standard path from $X$ to $Z$. Let $0 \leq i < j \leq k + 1$. Then $\{X_i < X_{i+1} < \dots < X_j\}$ is the standard path from $X_i$ to $X_j$.

Let $P$ denote the path $\{X_i < X_{i+1} < \dots < X_j\}$. Consider $l$ such that $i < l < j$. Then, since $X_i < X_l < X_j$ in $\Y_K[X,Z]$, <Ref> implies that $d_{X_l}(X_i,X_j) = d_{X_l}(X,Z) > K$. Hence, $X_l \in \Y_K[X_i,X_j]$. So $P \subseteq \Y_K[X_i,X_j]$.

Now suppose that $Y \in \Y_K(X_i,X_j)$. Then $d_Y(X_i,X_j) > K$ which, by <Ref>, implies that $Y \in \Y_K(X,Z)$. It also implies that $X_i < Y < X_j$ in $\Y_K[X,Z]$ and hence $Y \in P$. Hence $\Y_K[X_i,X_j] \subseteq P$. So $P$ and $\Y_K[X_i,X_j]$ share the same vertex set.

We therefore just need to check that the order in which the vertices are traversed in $\Y_K[X_i,X_j]$ is consistent with the order $X_i < X_{i+1} < \dots< X_j$ in $P$. Suppose that $i < l < m < j$. Then $d_{X_l}(X_i, X_m) > K$ since $X_i < X_l < X_m$ in $\Y_K[X,Z]$. But this implies that $X_l < X_m$ in $\Y_K[X_i,X_j]$ as well.

We begin by proving the following claim.

Suppose we have a standard path $\Y_K[B,X] = \{B = X_0 < X_1 < \dots< X_k < X_{k+1} = X\}$ and suppose there exists another vertex $Z$ connected by an edge (in $\T$) to $X$ such that $Z \neq X_k$. Then $\{B < X_1 < \dots < X_k < X < Z\}$ is the standard path from $B$ to $Z$.

Since the edge from $X$ to $Z$ is in $\T$, we know that there exists some vertex $U \in \Y$ such that $\Y_K[B,U] = \{B = X_0' < X_1' < \dots < X_l' < X_{l+1}' = U\}$ and $\{X,Z\} = \{X_j', X_{j+1}'\}$. Suppose for a contradiction that $X = X_{j+1}'$ and $Z = X_j'$. Then, by <Ref>, $B < X_1' < X_2' < \dots < X_{j-1}' < Z < X$ is the standard path from $B$ to $X$. It follows that $Z = X_k$ which contradicts our assumption on $Z$. So $X = X_j'$ and $Z = X_{j+1}'$. By <Ref>, we know that $B < X_1' < \dots < X_j'$ is the standard path from $B$ to $X$. <Ref> also implies that $B < X_1' < \dots < X_{j+1}'$ is the standard path from $B$ to $Z$. Hence $B < X_1 < \dots < X_k < X < Z$ is the standard path from $B$ to $Z$.

Suppose in $\T$ we have a cycle $C = \{Y_0, Y_1, \dots, Y_{l-1}\}$ where there is an edge between $Y_i$ and $Y_{i+1}$ (taken modulo $l$). Let $Y \in C$ and suppose that the path $\Y_K[B,Y]$ first intersects $C$ at the vertex $Y' \in C$. It follows that the standard path $\Y_K[B,Y'] = \{B < X_1 < \dots < X_k < Y'\}$ only intersects $C$ at $Y'$. Suppose, for simplicity, that $Y' = Y_0$. By the claim, we know that $B < X_1 < \dots < X_k < Y_0 < Y_1$ is the standard path from $B$ to $Y_1$. Similarly, we know that $B < X_1 < \dots < X_k < Y_0 < Y_1 < Y_2$ is the standard path from $B$ to $Y_2$. Continuing in this way, we find that $B < X_1 < \dots < X_k < Y_0 < Y_1 < Y_2 < \dots < Y_l < Y_0$ is the standard path from $B$ to $Y_0$ which is of course nonsense.

The inclusion map $\T \hookrightarrow \pc$ is a quasiisometry.

Evidently the inclusion map is Lipschitz; it remains to prove the lower bound of the quasiisometric inequality.

Consider the triple $B,X,Z$. By <Ref>, the path $\Y_K[X,Z]$ can be described as follows: an initial segment that is also initial within $\Y_K[X,B]$, a middle segment of length at most $2$, and a terminal segment that is also terminal in $\Y_K[B,Z]$. Let $Y'$ be the vertex at which $\Y_K[X,Z]$ diverges from $\Y_K[X,B]$ and let $Y''$ be the vertex at which $\Y_K[X,Z]$ joins $\Y_K[B,Z]$. Let $Y$ be the vertex at which $\Y_K[B,X]$ and $\Y_K[B,Z]$ diverge. By <Ref> we have

\begin{equation}
L[X,Y] \leq L[X,Y'] + 3 \label{eqn.ub1}
\end{equation}

\begin{equation}
L[Y,Z] \leq L[Y'',Z] + 3 \label{eqn.ub2}
\end{equation}

Now, by the definition of $\T$, we have that

\begin{equation}
d_\T(X,Z) = d_\T(X,Y) + d_\T(Y,Z) = L[X,Y] - 1 + L[Y,Z] - 1 \label{eqn.treedist}
\end{equation}

We also know that

\begin{equation}
L[X,Z] \geq L[X,Y'] + L[Y'', Z] - 1 \label{eqn.lb1}
\end{equation}

\begin{align*}
d_{\pc}(X,Z) &\geq \frac{1}{2}(L[X,Z] - 1) & \textrm{by \Cref{cor.pcdist}} \\
&\geq \frac{1}{2}(L[X,Y'] + L[Y'', Z] - 1) & \textrm{by \eqref{eqn.lb1}} \\
&\geq \frac{1}{2}(L[X,Y] - 3 + L[Y, Z] - 3 - 1) & \textrm{by \eqref{eqn.ub1} and \eqref{eqn.ub2}} \\
&= \frac{1}{2}(d_\T(X,Z) - 5) &\textrm{by \eqref{eqn.treedist}}
\end{align*}

and so we are done.

A key fact about the projection complex $\pc$ is that it is a quasi-tree (see <Ref>). <Ref> above provides a very explicit quasiisometry from $\pc$ to a tree. We can use $\T = \T(\Y,B)$ to define a tree of metric spaces $\toms$ as follows.

For each pair $X,Y \in \Y$ which are connected by an edge in $\pc$, fix an arbitrary element $p(X,Y) \in \pi_X(Y) \subset \C(X)$ and an arbitrary element $p(Y,X) \in \pi_Y(X) \subset \C(Y)$. In order to define $\toms$, we take the disjoint union of the metric spaces $\C(X)$ and draw an edge of length $K$ between $p(X,Y)$ and $p(Y,X)$ whenever there is an edge between $X$ and $Y$ in $\T$.

By all rights, we should be using the notation $p_X(Y)$ instead of $p(X,Y)$ in order to properly mimic the existing notation $\pi_X(Y)$. However, in the proof of <Ref> we will need to consider elements of $\Y$ with subscripts in their notation—having the additional subscript in $p_X(Y)$ would be painful to read.

Evidently, there exists a natural inclusion map $\toms \hookrightarrow \qtoms$.

The inclusion $\toms \hookrightarrow \qtoms$ is a quasiisometry.

We first need a lemma about the projection complex.

Let $X,Y,Z$ be distinct vertices of $\pc$.

* If $W$ is an element of $\Y_K[X,Y]$ and $\Y_K[X,Z]$ but not $\Y_K[Y,Z]$ then $d_W(Y,Z) \leq K$.

* If $W$ is an element of $\Y_K[X,Y]$ but not $\Y_K[X,Z]$ and not $\Y_K[Y,Z]$ then $d_W(X,Y) \leq 2K$.

The first statement is immediate. For the second, note that $d_W(X,Y) \leq d_W(X,Z) + d_W(Z,Y) \leq 2K$.

Coarse surjectivity is almost immediate: every element $x \in \qtoms$ is at distance at most $K/2$ from a metric space $\C(Y) \subset \toms$. Further, it is clear that the inclusion map is Lipschitz. It remains to prove the lower bound of the quasiisometric inequality.

Let $x \in \C(X)$ and $z \in \C(Z)$. To produce a lower bound on $d_{\qtoms}(x,z)$, it is sufficient to find a nice path from $x$ to $z$ in $\toms$ whose length is comparable to the distance from $x$ to $z$ in $\qtoms$.

We begin by finding a quasigeodesic from $x$ to $z$ in $\qtoms$ (we will then find a path from $x$ to $z$ in $\toms$ of a comparable length). Suppose that $\Y_K[X,Z] = \{X = X_0 < X_1 < \dots < X_{n-1} < X_{n} = Z\}$. We have the following path $\gamma$ from $x$ to $z$ in $\qtoms$

\[
\adjustbox{scale=1,center}{
\begin{tikzcd}[cramped]
x & {p(X_0,X_1)} \\
& {p(X_1,X_0)} & {p(X_1,X_2)} \\
&& {p(X_2,X_1)} & \dots & {p(X_{n-2},X_{n-1})} \\
&&&& {p(X_{n-1},X_{n-2})} & {p(X_{n-1},X_{n})} \\
&&&&& {p(X_{n},X_{n-1})} & z
\arrow[from=1-1, to=1-2]
\arrow[from=1-2, to=2-2]
\arrow[from=2-2, to=2-3]
\arrow[from=2-3, to=3-3]
\arrow[from=3-3, to=3-4]
\arrow[from=3-4, to=3-5]
\arrow[from=3-5, to=4-5]
\arrow[from=4-5, to=4-6]
\arrow[from=4-6, to=5-6]
\arrow[from=5-6, to=5-7]
\end{tikzcd}
\]

where each arrow either corresponds to a geodesic in $\C(X_i)$ or to a transverse edge between pairs of disjoint metric spaces. A segment $p(X_i,X_{i+1}) \rightarrow p(X_{i+1},X_{i})$ has length $K$. Each segment $p(X_{i},X_{i-1}) \rightarrow p(X_{i},X_{i+1})$ has length at most $d_{X_{i}}(x,z)$. Similarly, $x \rightarrow p(X_0,X_1)$ has length at most $d_{X_0}(x,z)$ and $p(X_n,X_{n-1}) \rightarrow z$ has length at most $d_{X_n}(x,z)$. Thus the length of $\gamma$ is at most

\[\sum_{i} d_{X_i}(x,z) + nK \]

It is shown in the proof of <cit.> that

\[\sum_{i} d_{X_i}(x,z) + nK \leq 2 \sum_{Y \in \Y_K(x,z)} d_Y(x,z) + 3K\]

Applying <Ref> we see that

\[2 \sum_{Y \in \Y_K(x,z)} d_Y(x,z) + 3K \leq 8 d_{\qtoms}(x,z) + 3K \]

and so $\gamma$ has length at most $8 d_{\qtoms}(x,z) + 3K$. So $\gamma$ is an $(8,3K)$-quasigeodesic in $\qtoms$.

We will now find a path in $\toms$ that is very close to $\gamma$. Let $X_i$ be the vertex of $\pc$ at which $\Y_K[X,Z]$ and $\Y_K[X,B]$ diverge (if they never diverge, then we are done, as $\gamma$ will lie inside $\toms$). Let $X_j$ be the vertex of $\pc$ at which $\Y_K[Z,X]$ and $\Y_K[Z,B]$ diverge (if they never diverge, then we are done, as $\gamma$ will lie inside $\toms$). Finally, let $Y$ be the vertex of $\pc$ at which $\Y_K[B,X]$ and $\Y_K[B,Z]$ diverge (if they never diverge, then we are done, as $\gamma$ will lie inside $\toms$). We can also assume that $X_i$, $X_j$ and $Y$ are distinct: if any of them are equal then $\gamma$ lies inside $\toms$. By <Ref>, we have a geodesic of length at most $6$ from $X_i$ to $X_j$ in $\T$. This geodesic in $\T$ has the form $X_i \rightarrow \dots \rightarrow Y \rightarrow \dots \rightarrow X_j$. Now let $\eta$ be a geodesic in $\toms$ from $p(X_i,X_{i+1})$ to $p(X_j,X_{j-1})$.
The path $\eta$ is a "diversion" from $\gamma$ between $p(X_i,X_{i+1})$ and $p(X_j,X_{j-1})$. If we can show that $\eta$ has uniformly bounded length then we will be done, as the path which travels along $\gamma$ but takes the diversion $\eta$ will be a path in $\toms$ of comparable length to $\gamma$.

The only metric spaces $\C(W)$ that $\eta$ travels through are those corresponding to the geodesic $X_i \rightarrow \dots \rightarrow Y \rightarrow \dots \rightarrow X_j$ in $\T$ described previously. The intersection of $\eta$ with $\C(X_i)$ corresponds to case (1) of <Ref> and hence has length at most $K$. Similarly, the intersection of $\eta$ with $\C(Y)$ or $\C(X_j)$ has length $K$. The intersection of $\eta$ with a metric space other than $\C(X_i), \C(Y), \C(X_j)$ corresponds to case (2) of <Ref> and hence has length at most $2K$. We conclude, by also taking into account the length of the transverse edges that $\eta$ travels along, that $\eta$ has length at most $17K$.

§ RELATIVELY HYPERBOLIC GROUPS

§.§ Background

Let $G$ be a group with finite generating set $S$ and let $\Gamma(G,S)$ denote the Cayley graph of $G$ with respect to $S$. When we speak of the metric on $G$, we are actually referring to the metric induced by $\Gamma(G,S)$, but we will generally denote it by $d_G$ nonetheless. Suppose that $\H$ is some collection of subgroups of $G$. Elements of $$̋ are called peripheral subgroups. Let $\G$ be the collection of all cosets of peripheral subgroups. In other words, $\G = \{gH : H \in \H\}$. Elements of $\G$ are called peripheral cosets. Let us suppose as well that for each $H \in \H$, $S ∩H$ generates the subgroup $H$.

\begin{definition} \label{def.conedoff}
The \textit{coned-off graph} of $G$ with respect to $\H$ is the graph formed by taking the Cayley graph $\Gamma(G,S)$ and then adding an edge between $g$ and $g'$ (if it's not already there) whenever $g$ and $g'$ are contained in the same peripheral coset. Although the coned-off graph depends on $\H$, this is omitted from the notation and the coned-off graph is simply denoted by $\hat{G}$.
\end{definition}

The coned-off graph is (coarsely) what you get if you crush every peripheral coset to a point. We will now define the \textit{Bowditch space} $X(G)$, a metric space closely related to $Ĝ$.

\begin{definition} \label{def.horoball}
Suppose that $\Gamma$ is a connected graph with vertex set $V_\Gamma$ and edge set $E_\Gamma$. Suppose also that every edge has length $1$. The \textit{horoball} $\mathcal{H}(\Gamma)$ is the graph with vertex set
\[V_{\mathcal{H}(\Gamma)} = V_{\Gamma} \times \N_0\]
and edge set
\[E_{\mathcal{H}(\Gamma)} = \{\{(v,n), (v',n)\} : \{v,v'\} \in E_{\Gamma}, n \in \N_0\} \sqcup \{\{(v,n),(v,n+1)\} : v \in V_{\Gamma}, n \in \N_0\} \]
We insist that edges of the form $\{(v,n), (v',n)\}$ have length $e^{-n}$ and edges of the form $\{(v,n),(v,n+1)\}$ have length $1$.
\end{definition}

So the horoball $ℋ(Γ)$ consists of countably many copies of $Γ$ stacked on top of each other, getting smaller and smaller as one travels higher.

\begin{definition} \label{def.bowditchspace}
The \textit{Bowditch space} of $G$ with respect to $\H$ is formed by taking $\Gamma(G,S)$ and then, for every $gH \in \G$, attaching a copy of $\mathcal{H}(\Gamma(H,S \cap H))$ to the subgraph $g\Gamma(H,S \cap H)$. The Bowditch space is denoted by $X(G)$.
\end{definition}

The Bowditch space, like the coned-off graph, also involves contracting the peripheral cosets. However it does so less brutally; where the coned-off graph created a path of length $1$ between any two vertices in the same peripheral coset, the Bowditch space creates a path between the vertices whose length is the $\log$ of their distance as elements of $g\Gamma(H,S \cap H)$.

The definition we use below is equivalent to all the other definitions of relative hyperbolicity. It is due to Groves and Manning \cite{GM}.

\begin{definition} \label{def.relhyp}
We say that $G$ is \textit{relatively hyperbolic} with respect to $\H$ if $X(G)$ is hyperbolic.
\end{definition}

\begin{remark}
Due to \cite[Theorem 1.1]{OSIN2}, if $G$ is relatively hyperbolic we may always assume that $\H$ is finite and that every $H \in \H$ is finitely generated.
\end{remark}

Strangely, I cannot find it recorded in the literature that \cite[Theorem 1.2]{BDS} is really an \textit{if and only if}. I'll record it here, since we have it almost for free.

\begin{corollary}[Buyalo--Dranishnikov--Schroeder, Bonk--Schramm] \label{cor.bdsbs}
If $X$ is a visual hyperbolic metric space then $X$ admits a quasiisometric embedding into a finite product of binary trees if and only if the boundary of $X$ is a doubling metric space. Further, if the boundary of $X$ is a doubling metric space, then $X$ admits a quasiisometric embedding into a finite product of $n+1$ binary trees, where $n$ is the linearly controlled metric dimension of the boundary.
\end{corollary}

\begin{proof}
The backwards implication of the if and only if, and the \textit{Further} part of the corollary, are exactly \cite[Theorem 1.2]{BDS}.

So suppose $X$ is a visual hyperbolic metric space that admits a quasiisometric embedding into a finite product of binary trees. Then obviously $X$ admits a quasiisometric embedding into a uniformly bounded degree graph. So \Cref{prop.bgoss} tells us that $X$ has bounded growth on some scale. Hence, \cite[Theorem 9.2]{BS} tells us that the boundary of $X$ is doubling.
\end{proof}

\begin{corollary}[Buyalo--Dranishnikov--Schroeder, Dahmani--Yaman, Bonk--Schramm] \label{cor.X(G)intobinarytrees}
Suppose $H$ is relatively hyperbolic with respect to $\H$. Then $X(G)$ quasiisometrically embeds into a finite product of binary trees if and only if all the subgroups in $\H$ are virtually nilpotent. Further, if all the subgroups in $\H$ are virtually nilpotent then $X(G)$ quasiisometrically embeds into a product of $n+1$ binary trees where $n$ is the linearly controlled metric dimension of the boundary of $X(G)$.
\end{corollary}

\begin{proof}
Mackay and Sisto \cite[Proposition 4.5]{MS2} use the main result of Dahmani and Yaman's paper \cite{DY} to prove that all the peripheral subgroups are virtually nilpotent if and only if the boundary of $X(G)$ is doubling. It then follows from \Cref{cor.bdsbs} that all the peripheral subgroups are virtually nilpotent if and only if $X(G)$ quasiisometrically embeds into a finite product of binary trees.

The \textit{Further} part of the corollary follows from \Cref{cor.bdsbs}.
\end{proof}

Recall from \Cref{ex.binarytree} that $\tb$ denotes the rooted binary tree.

\begin{corollary} \label{cor.VAbinary}
Suppose $\H = \{H_1, H_2, \dots, H_T\}$, suppose each peripheral subgroup $H_t$ is virtually abelian, and define $R = \max_t R_t$ where $R_t$ is the rank of a finite index abelian subgroup of $H_t$. Then there exists a quasiisometric embedding $\phi': X(G) \rightarrow \prod_{q=1}^Q \tb$ where $Q$ is at most $\max(\asdim(G), R+1) + 1$. We may assume that the image of $\phi'$ is contained in the vertex set of $\prod_{q=1}^Q \tb$.
\end{corollary}

\begin{proof}
\Cref{cor.X(G)intobinarytrees} implies that $X(G)$ quasiisometrically embeds into a product of $n+1$ binary trees where $n$ is the linearly controlled metric dimension of the boundary of $X(G)$. Proposition 3.6 and Proposition 3.4 of \cite{MS} combine to prove that $n \leq \max(\asdim(G),R+1)$ as desired.
\end{proof}

\begin{corollary} \label{cor.relhypreg}
Let $G$ be as in \Cref{cor.VAbinary}. Then there exists a regular map $\phi: G \rightarrow \prod_{q=1}^Q \tb$ where $Q \leq \max(\asdim(G),R+1) + 1$.
\end{corollary}

\begin{proof}
Let $\phi$ be the composition $G \hookrightarrow X(G) \rightarrow \prod_{q=1}^Q \tb$ where the second map is $\phi'$ from \Cref{cor.VAbinary}. By the assumption on $\phi'$, the image of $\phi$ is in the vertex set of $\prod_{q=1}^Q \tb$.

Since $G \rightarrow X(G)$ is Lipschitz and $\phi': X(G) \rightarrow \prod_{q=1}^Q \tb$ is coarsely Lipschitz we conclude that $\phi$ is Lipschitz.

Let $v$ be a vertex of $\prod_{q=1}^Q \tb$. Since $\phi': X(G) \rightarrow \prod_{q=1}^Q \tb$ is coarsely Lipschitz, the preimage of $v$ in $X(G)$ is contained in a ball of uniformly bounded radius in $X(G)$. But a ball of uniformly bounded radius in $X(G)$ can contain only a uniformly bounded amount of elements of $G \subset X(G)$. So $\phi^{-1}(v) \subset G$ has a uniformly bounded cardinality.
\end{proof}

We now state some results on the metric structure of relatively hyperbolic groups. These are \cite[Lemma 4.15]{DS} and \cite[Lemma 1.13, Proposition 1.14 and Lemma 1.15]{SISTO}.

\begin{proposition}[Dru\textcommabelow{t}u--Sapir] \label{prop.ds}
Peripheral cosets are undistorted in $G$. That is, the natural map $gH \subseteq G \rightarrow g\Gamma(H,S \cap H)$ is a quasiisometry.
\end{proposition}

Given $gH \in \G$ and $x \in G$, we define $\pi_{gH}(x) \subseteq gH$ to be the nearest point projection of $x$ onto $gH \subseteq \Gamma(G,S)$, i.e.
\[\pi_{gH}(x) = \{y \in gH : d_G(x,y) = \min_{z \in gH} d_G(x,z)\}\]

\begin{lemma}[Sisto] \label{lem.sisto1}
There exists $M$ such that if $\hat{\gamma}$ is a geodesic in the coned-off graph $\hat{G}$ connecting $x \in G$ to $y \in gH$ then the first point in $\hat{\gamma} \cap gH$ is at distance (taken with respect to the metric on $\Gamma(G,S)$) at most $M$ from $\pi_{gH}(x)$.
\end{lemma}

The \textit{lift} of a geodesic $\hat{\gamma}$ in $\hat{G}$ is a path $\gamma$ in $G$ obtained by substituting edges of $\hat{\gamma}$ that go between $g, g' \in kH$ with a geodesic in the subgraph $k\Gamma(H, S \cap H)$ from $g$ to $g'$.

\begin{proposition}[Sisto] \label{prop.sisto}
There exist $\lambda \geq 1$, $\mu \geq 0$ so that if $\hat{\gamma}$ is a geodesic in $\hat{G}$ then its lifts are $(\lambda,\mu)$-quasigeodesics.
\end{proposition}

Let $\bar{B}_r(x)$ denote the closed $r$-ball around some point $x \in G$.

\begin{lemma}[Sisto] \label{lem.sisto2}
There exists $L$ so that if $d_G(\pi_{gH}(x),\pi_{gH}(z)) \geq L$ for some ${gH} \in \G$ and $x,z \in G$ then
\begin{enumerate}
\item all $(\lambda,\mu)$-quasigeodesics in $\Gamma(G,S)$ connecting $x$ to $z$ intersect $\bar{B}_R(\pi_{gH}(x))$ and $\bar{B}_R(\pi_{gH}(z))$ where $R = R(\lambda,\mu)$;
\item all geodesics in $\hat{G}$ connecting $x$ to $z$ contain an edge between two elements of $gH$.
\end{enumerate}
\end{lemma}

\subsection*{Relatively hyperbolic groups as projection complexes}

As before, let $G$ be finitely generated with respect to a finite generating set $S$ and relatively hyperbolic with respect to a set of peripheral subgroups $\H$ (where $S \cap H$ generates each $H \in \H$) and let $\G$ be the set of peripheral cosets.

The set of peripheral cosets $\G$ will be our indexing set, taking the place of $\Y$ in \Cref{sec.pc}. I have chosen to use the notation $\G$ in this context so that there is a clear demarcation between the general theory of projection complexes given in \Cref{sec.pc} and the specific case of relatively hyperbolic groups given here. However, for ease of notation, we will frequently refer to cosets by the notation $X,Y,Z,W$ as in \Cref{sec.pc}.

We associate to each $gH \in \G$ the metric space $\C(gH) = g\Gamma(H,S \cap H)$. Given $Y = gH \in \G$ and $x \in \C(X)$, we define, as in the previous subsection, $\pi_Y(x) \subseteq \C(Y)$ to be the nearest point projection of $x$ onto $gH \subseteq \Gamma(G,S)$.
Then we have the projection data given by
\[\pi_Y(X) = \{\pi_Y(x) : x \in \C(X)\} \]
There is a slight subtlety in the above definitions; the nearest-point projections $\pi_Y$ are determined by the metric in $\Gamma(G,S)$, but we think of them as being subsets of $\C(Y) = g\Gamma(H,S \cap H)$.

Mackay and Sisto \cite{MS} notice that, by applying the work of Sisto \cite{SISTO}, the following result holds.

\begin{theorem}[Mackay--Sisto] \label{thm.p3-p5}
The metric spaces $\C(Y) = g\Gamma(H,S \cap H)$ together with the projection data
\[ \pi_Y: \G \setminus Y \rightarrow \textrm{non-empty subsets of } \C(Y)\]
satisfy axioms \ref{condition.p3} - \ref{condition.p5} for some projection constant $\xi$.
\end{theorem}

It follows that we can apply all the theory developed in \Cref{sec.pc} on the projection complex $\pc$, the quasi-tree of metric spaces $\qtoms$ and the tree of metric spaces $\toms$ to relatively hyperbolic groups. So let us use \Cref{thm.modification} to upgrade our projections $\{\pi_Y\}$ so that they now satisfy the \textit{strong} projection axioms with respect to a constant $\theta$, and let us define $\pcg$, $\qtomsg$ and $\tomsg$ for some $K \geq 4\theta$ accordingly.

Suppose $\H = \{H_1, H_2, \dots, H_T\}$. A group element $g \in G$ has $T$ possible images in the quasi-tree of metric spaces $\qtomsg$. Therefore, to properly specify a vertex of $\qtomsg$ we need specify the group element \textit{and} the coset. We write $g \in gH_t$ to mean the copy of $g$ that sits within the coset $gH_t \subset \qtomsg$. Let's define $\iota_t: G \rightarrow \qtomsg$ by $\iota_t(g) = g \in gH_t$. It is not difficult to prove that the embeddings $\iota_t: G \rightarrow \qtomsg$ are the same up to bounded distance; for lack of a better choice, we will always consider the embedding $\iota_1: G \rightarrow \qtomsg$.

\begin{notation} \label{notation.images}
A group element $g \in G$ has a natural image in $\hat{G}$ and $X(G)$. We will denote both of these images in $\hat{G}$ and $X(G)$ by $g$.
\end{notation}

Sisto \cite{SISTO} proves that the distance in a relatively hyperbolic group can be understood in terms of projections onto peripheral cosets and the distance in the coned-off graph. In order to state Sisto's theorem, we need some notation.

\begin{notation} \label{not.approx}
Let $A,B,L \in \R$, let $\lambda \geq 1$ and let $\mu \geq 0$.
\begin{itemize}
\item We write $A \approx_{\lambda,\mu} B$ if $A/\lambda - \mu \leq B \leq \lambda A + \mu$. If $A$ and $B$ are quantities which depend on a pair of group elements $g$ and $h$ (for example if $A = d_G(g,h)$ and $B = d_X(f(x),g(x))$ for some $f: G \rightarrow X$ and metric space $X$) then we might write $A \approx B$ if $A \approx_{\lambda,\mu} B$ for some $\lambda \geq 1$ and $\mu \geq 0$ which don't depend on $g$ and $h$ (in other words, $\lambda$, $\mu$ are \textit{uniform} constants).
\item We define $\{\{A\}\}_L$ to be $0$ if $A \leq L$ and to be $A$ if $A > L$.
\end{itemize}
\end{notation}

Let $Y = gH$ and let $\rho_Y: G \rightarrow Y$ be \textit{some} choice of nearest-point projection onto $Y$.

\begin{theorem}[Sisto] \label{thm.relhypdistanceformula}
There exists $L_0 \in \R$ such that for each $L \geq L_0$ there exist $\lambda, \mu$ such that the following holds. If $g,h \in G$ then
\[d_G(g,h) \approx_{\lambda,\mu} \sum_{Y \in \G} \{\{ d_G(\rho_Y(g),\rho_Y(h)) \}\}_L + d_{\hat{G}}(g,h) \]
\end{theorem}

It follows from \Cref{thm.relhypdistanceformula} and \Cref{thm.qtomsdistanceformula} that you may approximate distances in $G$ via the images of group elements in $\qtomsg$, $\hat{G}$ and $X(G)$. I have relegated the proofs of the following two corollaries to the appendix because, though intuitive, they are slightly technical. Further, they appear as \cite[Theorem 4.1]{MS}. Mackay and Sisto \cite{MS} prove this result by simply comparing the distance formula for relatively hyperbolic groups (\Cref{thm.relhypdistanceformula}) directly with the distance formula for $\qtoms$ (\Cref{thm.qtomsdistanceformula}). However, I believe that if one is to be completely rigorous then some further checks have to be made since \Cref{thm.relhypdistanceformula} and \Cref{thm.qtomsdistanceformula} are not automatically directly comparable (for example, \Cref{thm.relhypdistanceformula} concerns the nearest point projection, whereas \Cref{thm.qtomsdistanceformula} concerns the \textit{modified} projections given by \Cref{thm.modification}). See \Cref{appchap.2} for the proofs of these corollaries.

\begin{corollary} \label{cor.embedding1}
For sufficiently large $K$, the map $G \rightarrow \qtomsg \times \hat{G}$ given by
\[g \mapsto (\iota_1(g), g)\]
is a quasiisometric embedding.
\end{corollary}

\begin{corollary} \label{cor.embedding2}
For sufficiently large $K$, the map $G \rightarrow \qtomsg \times X(G)$ given by
\[g \mapsto (\iota_1(g), g)\]
is a quasiisometric embedding.
\end{corollary}

\section{Standard paths in relatively hyperbolic groups with virtually abelian peripherals} \label{sec.standardpaths}

In this section, we will use the theory developed in \Cref{sec.relhyp} to define a collection of canonical quasigeodesic paths between two group elements $x,z \in G$ when $G$ is relatively hyperbolic with respect to virtually abelian peripheral subgroups.

So suppose $G$ is relatively hyperbolic with respect to virtually abelian peripheral subgroups $H_1, H_2, \dots, H_T$. Let $R_t$ denote the rank of a finite index abelian subgroup of $H_t$, and define $R = \max(R_1, R_2, \dots, R_T)$. Let $A_t \cong \Z^{R_t}$ be a finite index subgroup of $H_t$. A virtually abelian group always contains a normal, finite index abelian subgroup. Therefore without loss of generality we may assume that $A_t$ is normal in $H_t$. Suppose $G$ is generated by a finite set $S$. We may assume that $S_{H_t} := S \cap H_t$ generates $H_t$ and that $S_{A_t} := S_{H_t} \cap A_t$ generates $A_t$. We write $S_{H_t} = S_{A_t} \cup \{b_{t,1}, b_{t,2}, \dots, b_{t,R'_t}\}$ where $b_{t,r} \not \in A_t$ for $1 \leq r \leq R'_t$. Further, we may assume the following: that $S_{A_t} = \{a_{t,1}, a_{t,2}, \dots, a_{t,R_t}\}$ and that identifying
\[a_{t,1}^{q_1} a_{t,2}^{q_2} \dots a_{t,R_t}^{q_{R_t}} \in \Gamma(A_t, S_{A_t})\]
\[(q_1, q_2, \dots, q_{R_t}) \in \Gamma(\Z^{R_t},\{(1,0,\dots,0), (0,1,\dots,0), \dots, (0,0,\dots,1)\})\]
gives a graph isomorphism. In other words, we assume that the subgraph $g\Gamma(A_t, S_{A_t})$ is a \textit{grid} for all $g \in G$. Let $I_t$ denote the cardinality of the quotient group $H_t / A_t$ and write $I = \max_t I_t$.

As in \Cref{sec.relhyp}, let $\G = \{gH_t : g \in G, 1 \leq t \leq T\}$ and define the projections $\{\pi_Y\}$ using the nearest point projections. We then modify $\{\pi_Y\}$ by a uniformly bounded amount using \Cref{thm.modification} so that they now satisfy axioms \ref{condition.p3}-\ref{condition.p5} and \ref{condition.p4'} with respect to the projection constant $\theta$. Since the original projections are collections of vertices, the modified projections will be too, as described in \Cref{thm.modification}. The new projection distances will be denoted by $d_Y$. We choose $K$ to be at least $4 \theta + 2I$, and large enough that \Cref{cor.embedding2} holds. In particular, since $K \geq 4\theta$, all the results in \Cref{sec.pc} hold and we can define $\pcg$ and $\qtomsg$. By setting $B = H_1$, we can also define $\T = \T_K(\G,B)$ as in \Cref{def.tree}. In order to define $\tomsg$ as in \Cref{def.toms}, we arbitrarily choose vertices $p(X,Y) \in \pi_X(Y)$ and $p(Y,X) \in \pi_Y(X)$ for every distinct pair $X,Y \in \G$ that are connected by an edge in $\pcg$.

\subsection*{Standard non-abelian paths between cosets of $A_t$ in $H_t$}
Let us write $H_t / A_t = \{h_{t,1} A_t, h_{t,2} A_t, \dots, h_{t,I_t} A_t\}$.

\begin{definition} \label{def.nonabelianpath}
For $1 \leq i \leq I_t$, let $\psi_{t,i} \in \langle b_{t,1}, b_{t,2}, \dots, b_{t,R'_t} \rangle$ be some fixed path in $G$ from $e$ to the coset $h_{t,i} A_t$ of length at most $I_t$. This is possible since $H_t / A_t$ is a group of cardinality $I_t$ that is generated by the set $\{b_{t,r}A_t : 1 \leq r \leq R_t' \}$.

Given two group elements $k, k'$ in the same coset of $H_t$, say $k,k' \in gH_t$, there exists a unique $1 \leq i \leq I_t$ such that for all group elements $l \in kA_t$ we have that $l\psi_{t,i} \in k'A_t$. We refer to $\psi_{t,i}$ as \textit{the standard non-abelian path} from the coset $kA_t$ to the coset $k'A_t$.
\end{definition}

\subsection*{Standard paths in $g\Gamma(H_t,S_{H_t})$} \label{subsec.cosetsp}

\begin{definition} \label{def.bp}
Given a coset $Y \in \G$, write
\[\G_K[H_1, Y] = \{H_1 = Y_1 < Y_2 < \dots < Y_{L-1} < Y_L = Y\}\]
The \textit{basepoint} of $Y$, which we denote by $p_0(Y)$, is defined to be $p(Y,Y_{L-1})$ if $Y \neq H_1$ and defined to be the identity $e$ if $Y = H_1$.
\end{definition}

\begin{definition} \label{def.spcoset}
Suppose $k$ and $k'$ are vertices of $\C(Y) = g\Gamma(H_t,S_{H_t})$. Let $\psi_{t,i}$ be the standard non-abelian path from the coset $kA_t$ to the coset $p_0(Y)A_t$. Let $\psi_{t,j}$ be the standard non-abelian path from the coset $p_0(Y)A_t$ to the coset $k'A_t$. A \textit{standard path} from $k$ to $k'$ in $\C(Y)$ is any path which is formed by concatenating the following three paths
\begin{itemize}
\item The standard non-abelian path $\psi_{t,i}$;
\item A geodesic in $p_0(Y)\Gamma(A_t,S_{A_t})$ formed of the abelian generators $\{a_{t,1}, \dots, a_{t,R_t}\}$ that takes us from $k\psi_{t,i}$ to $k'\psi_{t,j}^{-1}$;
\item The standard non-abelian path $\psi_{t,j}$.
\end{itemize}
\end{definition}