# Coxeter groups are biautomatic

Damian Osajda† Instytut Matematyczny, Uniwersytet Wrocławski
pl. Grunwaldzki 2/4, 50–384 Wrocław, Poland  Institute of Mathematics, Polish
Academy of Sciences
Śniadeckich 8, 00-656 Warszawa, Poland<EMAIL_ADDRESS>and  Piotr
Przytycki‡ Department of Mathematics and Statistics, McGill University,
Burnside Hall, 805 Sherbrooke Street West, Montreal, QC, H3A 0B9, Canada
<EMAIL_ADDRESS>
###### Abstract.

We prove that Coxeter groups are biautomatic. From our construction of the
biautomatic structure it follows that uniform lattices in isometry groups of
buildings are biautomatic.

${\dagger}{\ddagger}$ Partially supported by (Polish) Narodowe Centrum Nauki,
UMO-2018/30/M/ST1/00668.

${\ddagger}$ Partially supported by NSERC, AMS, and LabEx CARMIN,
ANR-10-LABX-59-01

##  1\. Introduction

Coxeter groups were introduced in 1934 as abstractions of reflection groups
[Coxeter_1934]. They play a fundamental role in, among others, the theory of
Lie groups and algebras, the representation theory, the geometry of Riemannian
symmetric spaces, the topology of aspherical manifolds. Consequently, Coxeter
groups are important in other areas of science, e.g. physics, chemistry, and
biology. They are foundational objects for buildings — highly symmetric spaces
having deep connections with algebraic groups. On the other hand, multiple
existing ways of constructing them, make Coxeter groups a source of numerous
important, often very exotic, examples of groups. Being studied thoroughly
over decades, many important algebraic, geometric, and algorithmic properties
of Coxeter groups have been established. Among few most important basic open
problems concerning Coxeter groups, there has been the question of
biautomaticity.

The notion of biautomaticity was introduced in the classical book by
Epstein–Cannon–Holt–Levy–Paterson–Thurston [Epstein_et_al_1992] as a very
powerful means of understanding a group. Having biautomaticity established for
a finitely generated group, very roughly speaking, we know how to move, using
the generators, between any two given elements of the group. Moreover, the
resulting paths are determined by a finite state automaton, and are stable in
the sense that changing slightly the endpoints does not perturb the paths too
much. Such a property should be thought of as a strong form of controlling the
structure of the group.

######  Main Theorem.

Every Coxeter group is biautomatic.

Many partial results in this direction have been obtained in the past.
Davis–Shapiro [Davis-Shapiro_1991] showed a conjecturally weaker feature of
all Coxeter groups — the automaticity, under the assumption of the Parallel
Wall Theorem, and showed that their language does not provide a biautomatic
structure. Brink–Howlett [Brink-Howlett_1993] proved the Parallel Wall Theorem
and hence established the automaticity of all Coxeter groups using the same
language as [Davis-Shapiro_1991]. Biautomaticity has been established for a
few subclasses of Coxeter groups in: [Epstein_et_al_1992] (Euclidean and
Gromov hyperbolic), [Niblo-Reeves_1998, Niblo_Reeves_2003] (right-angled),
[Bahls_2006, Caprace_Mulherr_2005] (no Euclidean reflection triangles),
[Caprace_2009] (relatively hyperbolic), [Munro_et_al_2022] ($2$-dimensional).

Furthermore, there is an intensive research effort in deeper understanding
languages in Coxeter groups, for example the Davis–Shapiro–Brink–Howlett
language, see e.g. [Casselman_1994, Dyer-Hohlweg_2016, Yau_2021, Parkinson-
Yau_2022] and references therein. This is primarily inspired by computations
in representation theory, and leads to theoretical results concerning
algorithmic aspects of the languages, as well as to explicit computations and
software implementations of corresponding algorithms.

For our proof of the Main Theorem we introduce a new geodesic language: the
’voracious‘ language $\mathcal{V}$. Besides providing a biautomatic structure,
it has other interesting features compared to the previously considered
languages, e.g. to the aforementioned Davis–Shapiro–Brink–Howlett language. In
particular, $\mathcal{V}$ is preserved by the automorphisms of a Coxeter group
preserving its given generating set. An immediate consequence of this
property, together with a result by Światkowski [Swiatkowski_2006, Thm 6.7] on
geodesic languages for Coxeter groups, is the following.

######  Main Corollary.

Uniform lattices in isometry groups of buildings are biautomatic.

A uniform lattice here means a group acting properly and cocompactly on the
Davis realisation of a building associated to a Coxeter group. Previously, the
biautomaticity of such lattices has been shown in few particular cases in:
[Epstein_et_al_1992, Cartwright-Shapiro_1995] (Gromov hyperbolic and some
Euclidean), [Niblo-Reeves_1998, Davis_1998] (right-angled), [Gersten-
Short_1990, Gersten-Short_1991, Noskov_2000, Swiatkowski_2006] (some Euclidean
cases), [Munro_et_al_2022] ($2$-dimensional).

Organisation. In Section 2 we recall the notions of a Coxeter group and a
biautomatic structure, and we define the voracious projection and language
$\mathcal{V}$ used to prove the Main Theorem. In Section 3, we show that the
voracious projection is well defined. In Section 4, we prove that the distance
between any element of $W$ and its voracious projection is bounded above by a
constant depending only on $W$. We verify parts (ii) and (iii) of the
definition of biautomaticity in Section 5. In Section 6, we prove the
regularity of $\mathcal{V}$.

Acknowledgement. We thank Adrien Abgrall, Pierre-Emmanuel Caprace, Chris
Hruska, Jingyin Huang, and Zachary Munro for useful discussions. This paper
was written during our stay at the Institut Henri Poincaré in Paris, which we
thank for the hospitality.

##  2\. Preliminaries

We follow the notation adopted in [Munro_et_al_2022]. A _Coxeter group_ $W$ of
_rank_ $k$ is a group generated by a finite set $S$ of size $k$ subject only
to relations $s^{2}=1$ for $s\in S$ and $(st)^{m_{st}}=1$ for $s\neq t\in S$,
where $m_{st}=m_{ts}\in\\{2,3,\ldots,\infty\\}$. Here the convention is that
$m_{st}=\infty$ means that we do not impose a relation between $s$ and $t$.

Consider an arbitrary group $G$ with a finite symmetric generating set $S$.
For $g\in G$, let $\ell(g)$ denote the _word length_ of $g$, that is, the
minimal number $n$ such that $g=s_{1}\cdots s_{n}$ with $s_{i}\in S$ for
$i=1,\ldots,n$. Let $S^{*}$ denote the set of all words over $S$. If $v\in
S^{*}$ is a word of length $n$, then by $v(i)$ we denote the prefix of $v$ of
length $i$ for $i=1,\ldots,n-1$, and the word $v$ itself for $i\geq n$. For
$1\leq i\leq j\leq n,$ by $v(i,j)$ we denote the subword of $v(j)$ obtained by
removing $v(i-1)$. For a word $v\in S^{*}$, by $\ell(v)$ we denote the word
length of the group element that $v$ represents.

We say that $G$ is _biautomatic_ if there exists a regular language
$\mathcal{L}\subseteq S^{*}$ (see Section 6 for the definition of regularity)
and constants $C,C^{\prime}$ satisfying the following conditions.

  1. (i)

For each $g\in G$, there is a word in $\mathcal{L}$ representing $g$.

  2. (ii)

For each $s\in S$ and $g,g^{\prime}\in G$ with $g^{\prime}=gs,$ and each
$v,v^{\prime}\in\mathcal{L}$ representing $g,g^{\prime}$, for all $i\geq 1$ we
have $\ell\big{(}v(i)^{-1}v^{\prime}(i)\big{)}\leq C$.

  3. (iii)

For each $s\in S$ and $g,g^{\prime}\in G$ with $g^{\prime}=sg,$ and each
$v,v^{\prime}\in\mathcal{L}$ representing $g,g^{\prime}$, for all $i\geq 1$ we
have $\ell\big{(}v(i)^{-1}s^{-1}v^{\prime}(i)\big{)}\leq C^{\prime}$.

This definition agrees with the characterisation of biautomaticity in
[Epstein_et_al_1992, Lem 2.5.5], which is equivalent to the original
definition of biautomaticity if in condition (i) the set of words in
$\mathcal{L}$ representing each $g\in G$ is finite [Amrhein_2021, Thm 6].
Conditions (ii) and (iii) are called the ’fellow traveller property‘.

To define the voracious language, we need the following. By $X^{1}$ we denote
the _Cayley graph_ of $W$, that is, the graph with vertex set $X^{0}=W$ and
with edges (of length $1$) joining each $g\in W$ with $gs$, for $s\in S$. We
consider the action of $W$ on $X^{0}=W$ by left multiplication. This induces
an action of $W$ on $X^{1}$. For $r\in W$ a conjugate of an element of $S$,
the _wall_ $\mathcal{W}_{r}$ of $r$ is the fixed point set of $r$ in $X^{1}$.
We call $r$ the _reflection_ in $\mathcal{W}_{r}$ (for fixed $\mathcal{W}_{r}$
such $r$ is unique). Each wall $\mathcal{W}$ separates $X^{1}$ into two
components, called _half-spaces_ , and a geodesic edge-path in $X^{1}$
intersects $\mathcal{W}$ at most once [Ronan_2009, Lem 2.5]. Consequently, the
distance in $X^{1}$ between $g,h\in W$ is the number of walls separating $g$
and $h$.

For $g\in W$, let $\mathcal{W}(g)$ be the set of walls $\mathcal{W}$ in
$X^{1}$ that separate $g$ from the identity element $\mathrm{id}\in W$ and
such that there is no wall $\mathcal{W}^{\prime}$ separating $g$ from
$\mathcal{W}$.

We consider the partial order $\preceq$ on $W$, where $p\preceq g$ if $p$ lies
on a geodesic in $X^{1}$ from $\mathrm{id}$ to $g$. Equivalently, there is no
wall separating $p$ from both $\mathrm{id}$ and $g$.

For $g\in W$, let $P(g)\subset W$ be the set of elements $p\in W$ satisfying
$p\preceq g$ and such that there is no wall in $\mathcal{W}(g)$ separating $p$
from $\mathrm{id}$. Note that $P(g)$ is nonempty, since $\mathrm{id}\in P(g)$.
In Section 3 we will prove the following.

######  Theorem 2.1.

For every Coxeter group $W,$ and each $g\in W,$ the set $P(g)$ contains a
largest element with respect to $\preceq$.

This largest element will be called _the voracious projection_ $p(g)$ of $g$.
Note that $p(g)\neq g$ for $g\neq\mathrm{id}$.

We define the _voracious language_ $\mathcal{V}\subset S^{*}$ for $W$
inductively in the following way. Let $v\in S^{*}$ be a word of length $n$. If
$v$ represents the identity element of $W$, then $v\in\mathcal{V}$ if and only
if $v$ is the empty word. Otherwise, let $g\in W$ be the group element
represented by $v$, let $p$ be the voracious projection of $g$, and let
$w=p^{-1}g\in W$ and $k=\ell(w)$. We declare $v\in\mathcal{V}$ if and only if
$v(n-k)\in\mathcal{V}$ and $v(n-k+1,n)$ represents $w$. In particular,
$v(n-k)$ represents $p$. It follows inductively that $n=\ell(g)$. Such a
language is called _geodesic_. Note that the voracious language satisfies part
(i) of the definition of biautomaticity, and the set of words in $\mathcal{V}$
representing each $g\in G$ is finite.

The paths in $W$ formed by the words in the voracious language are inspired by
the normal cube paths for $\mathrm{CAT}(0)$ cube complexes [Niblo-Reeves_1998,
§3] used to prove the biautomaticity for right-angled (or, more generally,
cocompactly cubulated) Coxeter groups [Niblo_Reeves_2003]. Namely, the
voracious projection $p(g)$ of $g$ is ’so‘ voracious that the geodesics from
$g$ to $p(g)$ intersect all the walls in $\mathcal{W}(g)$ (even if it means
intersecting simultaneously other walls).

We will prove the Main Theorem with $\mathcal{L}$ the voracious language
$\mathcal{V}$. It is clear from the definition that the voracious language is
preserved by the automorphisms of $W$ stabilising $S$, allowing us to apply
[Swiatkowski_2006, Thm 6.7] on geodesic languages to obtain the Main Corollary
concerning buildings.

##  3\. Voracious projection is well defined

######  Definition 3.1.

Let $r,q\in W$ be reflections. Distinct walls
$\mathcal{W}_{r},\mathcal{W}_{q}$ _intersect_ , if $\mathcal{W}_{r}$ is not
contained in a half-space for $\mathcal{W}_{q}$ (this relation is symmetric).
Equivalently, $\langle r,q\rangle$ is a finite group. We say that such $r,q$
are _sharp-angled_ , if $r$ and $q$ do not commute and $\\{r,q\\}$ is
conjugate into $S$. In particular, there is a component of
$X^{1}\setminus(\mathcal{W}_{r}\cup\mathcal{W}_{q})$ whose intersection $F$
with $X^{0}$ is a fundamental domain for the action of $\langle r,q\rangle$ on
$X^{0}$. We call such $F$ a _geometric fundamental domain for $\langle
r,q\rangle$_.

######  Lemma 3.2.

Suppose that reflections $r,q\in W$ are sharp-angled, and that $g\in W$ lies
in a geometric fundamental domain for $\langle r,q\rangle$. Assume that there
is a wall $\mathcal{U}$ separating $g$ from $\mathcal{W}_{r}$ or from
$\mathcal{W}_{q}$. Let $\mathcal{W}^{\prime}$ be a wall distinct from
$\mathcal{W}_{r},\mathcal{W}_{q}$ that is the translate of $\mathcal{W}_{r}$
or $\mathcal{W}_{q}$ under an element of $\langle r,q\rangle$. Then there is a
wall $\mathcal{U}^{\prime}$ separating $g$ from $\mathcal{W}^{\prime}$.

###### Proof.

Consider the group $W_{0}<W$ generated by the $3$ reflections: $r,q$, and the
reflection in $\mathcal{U}$. By [Dyer_1990], with the rank bound established
in his Corollary 3.11 (see also [Deodhar_1989] or [Tits_1988, Prop 3]), we
have that $W_{0}$ can be identified with a Coxeter group of rank 3 such that

  * •

the reflections of $W_{0}$ are reflections of $W$, and

  * •

the connected components of the complement in $X^{1}$ of the walls of $W_{0}$
correspond (equivariantly) to the elements of $W_{0}$, and

  * •

pairs of such components with intersecting closure in $X^{1}$ correspond to
pairs of elements of $W_{0}$ differing by a generator of $W_{0}$.

Let $g_{0}$ be the element of $W_{0}$ corresponding to the above component
containing $g$. Then $r,q$ are still sharp-angled in $W_{0}$, with $g_{0}$ in
a geometric fundamental domain for $\langle r,q\rangle$. Thus to prove the
lemma, it suffices to prove it for $W$ of rank 3.

We can assume $S=\\{r,q,s\\}$, where $\mathrm{id}$ lies in the same geometric
fundamental domain for $\langle r,q\rangle$ as $g$. Since $\mathcal{U}$ is
disjoint from $\mathcal{W}_{r}$ or $\mathcal{W}_{q}$, the group $W$ is
infinite, so we can assume without loss of generality $m_{sr}\geq 3$. If
$m_{sq}\geq 3$, or $m_{sq}=2$ and

  * •

$m_{sr}=\infty$, or

  * •

$m_{sr}\geq 4$ and $\mathcal{W}^{\prime}\neq q\mathcal{W}_{r}$, or

  * •

$m_{sr}=3$ and
$\mathcal{W}^{\prime}\notin\\{q\mathcal{W}_{r},r\mathcal{W}_{q},qr\mathcal{W}_{q}\\}$,

then $\mathcal{W}_{s}$ is disjoint from $\mathcal{W}^{\prime}$. Since $g$ is
separated from $\mathcal{W}_{r}$ or $\mathcal{W}_{q}$ by $\mathcal{U}$, we
have $g\neq\mathrm{id}$. Thus $\mathcal{U}^{\prime}=\mathcal{W}_{s}$ separates
$g$ from $\mathcal{W}^{\prime}$, as desired. See Figure 1(a).

Figure 1. Proof of Lemma 3.2.

If $m_{sq}=2,m_{sr}<\infty,$ and $\mathcal{W}^{\prime}=q\mathcal{W}_{r}$, then
let $\mathcal{U}^{\prime}=s\mathcal{W}_{r}$. Note that $\mathcal{U}^{\prime}$
is disjoint from $\mathcal{W}^{\prime}$ since they are related by the point
symmetry $sq$. Furthermore, since $g$ is separated from $\mathcal{W}_{r}$ or
$\mathcal{W}_{q}$ by $\mathcal{U}$, and $m_{sr}<\infty,$ we have
$g\neq\mathrm{id},s$. Thus $\mathcal{U}^{\prime}$ separates $g$ from
$\mathcal{W}^{\prime}$, see Figure 1(b).

If $m_{sq}=2,m_{sr}=3,$ and $\mathcal{W}^{\prime}=qr\mathcal{W}_{q}$, then let
$\mathcal{U}^{\prime}=sr\mathcal{W}_{q}$. Again $\mathcal{U}^{\prime}$ is
disjoint from $\mathcal{W}^{\prime}$ since they are related by the point
symmetry $sq$. Furthermore, since $g$ is separated from $\mathcal{W}_{r}$ or
$\mathcal{W}_{q}$ by $\mathcal{U}$, we have $g\neq\mathrm{id},s,sr$. Thus
$\mathcal{U}^{\prime}$ separates $g$ from $\mathcal{W}^{\prime}$, see Figure
1(c).

Figure 2. Proof of Lemma 3.2, the case $m_{sq}=2,m_{sr}=3,$ and
$\mathcal{W}^{\prime}=r\mathcal{W}_{q}$.

It remains to consider the case where $m_{sq}=2,m_{sr}=3,$ and
$\mathcal{W}^{\prime}=r\mathcal{W}_{q}$. Suppose first the that wall
$srq\mathcal{W}_{r}$ is disjoint from $\mathcal{W}^{\prime}$, see Figure 2(a).
Then we can set $\mathcal{U}^{\prime}=srq\mathcal{W}_{r}$, since
$g\neq\mathrm{id},s,sr,srq$. Second, suppose that $srq\mathcal{W}_{r}$
intersects $\mathcal{W}^{\prime}$. Then let
$\mathcal{U}^{\prime}=srqr\mathcal{W}_{q}$, see Figure 2(b). Note that
$\mathcal{U}^{\prime}$ is disjoint from $\mathcal{W}^{\prime}$ since they are
related by the point symmetry that is the composition of the reflections in
$sr\mathcal{W}_{q}$ and in $\mathcal{W}_{r}$. If $\mathcal{U}^{\prime}$ does
not separate $g$ from $\mathcal{W}^{\prime}$, then
$g\in\\{\mathrm{id},s,sr,srq,srqr,srqrs\\}$. Since $g$ is separated from
$\mathcal{W}_{r}$ or $\mathcal{W}_{q}$ by $\mathcal{U}$, we have that
$g=srqrs$ is separated from $\mathcal{W}_{q}$ by
$\mathcal{U}=srqr\mathcal{W}_{s}$. But the reflection $r$ maps
$\mathcal{W}_{q}$ and $\mathcal{U}$ to $\mathcal{W}^{\prime}$ and
$srq\mathcal{W}_{r}$, contradicting the assumption that the latter walls
intersect. ∎

###### Proof of Theorem 2.1.

It suffices to show that for each $p_{0},p_{n}\in P(g)$ there is $p\in P(g)$
satisfying $p_{0}\preceq p\succeq p_{n}$. Let $(p_{0},p_{1},\ldots,p_{n})$ be
the vertices of a geodesic edge-path $\pi$ in $X^{1}$ from $p_{0}$ to $p_{n}$.
Note that $\pi$ does not intersect the walls in $\mathcal{W}(g)$, since
$p_{0},p_{n}$ lie both in their half-spaces containing $\mathrm{id}$.
Furthermore, for any wall $\mathcal{W}$ containing $\mathrm{id},g$ in the same
half-space, we have that $p_{0},p_{n}$ lie in that half-space, and so do all
$p_{i}$. Consequently, $p_{i}\preceq g$, and so $p_{i}\in P(g)$.

We will now modify $\pi$ and replace it by another embedded edge-path
(possibly not geodesic) from $p_{0}$ to $p_{n}$ with vertices in $P(g)$, so
that there is no $p_{i}$ with $p_{i-1}\succeq p_{i}\preceq p_{i+1}$. Then we
will be able to choose $p$ to be the largest $p_{i}$ with respect to
$\preceq$.

If $p_{i-1}\succeq p_{i}\preceq p_{i+1}$, then let
$\mathcal{W}_{r},\mathcal{W}_{q}$ be the walls separating $p_{i}$ from
$p_{i-1},p_{i+1}$, respectively. Since $p_{i-1}\preceq g,p_{i+1}\preceq g$,
the walls $\mathcal{W}_{r},\mathcal{W}_{q}$ intersect. Moreover, if $r$ and
$q$ do not commute, then $r,q$ are sharp-angled, with $g$ in a geometric
fundamental domain for $\langle r,q\rangle$. We claim that all the elements of
$R=\langle r,q\rangle(p_{i})$ lie in $P(g)$.

By [Ronan_2009, Thm 2.9], we have that all the elements of $R$ lie on
geodesics from $p_{i}$ to $g$, and hence they are $\preceq g$. Since
$p_{i-1},p_{i+1}$ are both in $P(g)$, we have that
$\mathcal{W}_{r},\mathcal{W}_{q}\notin\mathcal{W}(g)$. It remains to justify
that each remaining wall $\mathcal{W}^{\prime}$ that is the translate of
$\mathcal{W}_{r}$ or $\mathcal{W}_{q}$ under an element of $\langle
r,q\rangle$ does not belong to $\mathcal{W}(g)$. We can thus assume that $r$
and $q$ do not commute, since otherwise there is no such remaining
$\mathcal{W}^{\prime}$. Since $\mathcal{W}_{r}\notin\mathcal{W}(g)$, there is
a wall $\mathcal{U}$ separating $g$ from $\mathcal{W}_{r}$. By Lemma 3.2,
there is a wall $\mathcal{U}^{\prime}$ separating $g$ from
$\mathcal{W}^{\prime}$, justifying the claim.

We now replace the subpath $(p_{i-1},p_{i},p_{i+1})$ of $\pi$ by the second
edge-path with vertices in $R$ from $p_{i-1}$ to $p_{i+1}$. This decreases the
complexity of $\pi$ defined as the tuple $(n_{1},n_{2},\ldots,n_{\ell(g)})$,
where $n_{j}$ is the number of $p_{i}$ in $\pi$ with $\ell(p_{i})=j$, with
lexicographic order. After possibly removing a subpath, we can assume that the
new edge-path is embedded. After finitely many such modifications, we obtain
the desired path. ∎

##  4\. Bounding the voracious projection

######  Proposition 4.1.

Let $W$ be a Coxeter group. There exists a constant $C=C(W)$ such that for
each $g\in W,$ we have $\ell\big{(}p(g)^{-1}g\big{)}\leq C$, where $p(g)$ is
the voracious projection of $g$.

In the proof we need the following Parallel Wall Theorem.

######  Theorem 4.2 ([Brink-Howlett_1993, Thm 2.8]).

Let $W$ be a Coxeter group. There exists a constant $Q=Q(W)$ such that for
each $g\in W$ and a wall $\mathcal{W}$ at distance $>Q$ from $g$ in $X^{1}$,
there is a wall $\mathcal{W}^{\prime}$ separating $g$ from $\mathcal{W}$.

In particular, for $g\in W$, each of the walls in $\mathcal{W}(g)$ is at
distance $\leq Q$ from $g$.

######  Lemma 4.3.

Let $W$ be a Coxeter group. There exists a constant $C_{0}=C_{0}(W)$ such that
for each $g\in W$ and each $\mathcal{W}\in\mathcal{W}(g)$, there is $h\in W$
satisfying $h\preceq g$, at distance $\leq C_{0}$ from $g$ in $X^{1}$, and
separated from $g$ by $\mathcal{W}$.

###### Proof.

For $g\in W,$ and $\mathcal{W}\in\mathcal{W}(g)$, among elements $h\in W$
satisfying $h\preceq g$, and separated from $g$ by $\mathcal{W}$, consider $h$
with minimal distance $C_{0}$ from $g$ in $X^{1}$. Our goal is to bound
$C_{0}$ uniformly in $g$ and $\mathcal{W}$. We can assume $h=\mathrm{id}$.
Furthermore, by the minimality assumption, we have
$\mathcal{W}=\mathcal{W}_{s}$ for $s\in S$.

Note that for $t\in S\setminus\\{s\\}$, the wall $\mathcal{W}_{t}$ does not
separate $\mathrm{id}$ from $g$, since otherwise we could replace
$\mathrm{id}$ by $t$ contradicting the minimality assumption.

We now use the _Davis complex_ $X$ of $W,$ which is obtained from $X^{1}$ by
adding Euclidean polyhedra of edge length one spanned on all the cosets of
finite $\langle T\rangle$ for $T\subseteq S$ (see [Davis_2008, Prop 7.3.4]).
By [Moussong_1988] (see also [Bowditch_1995]), we have that $X$ is CAT(0). The
fixed point sets of the reflections of $W$ in $X$ are still called _walls_ ,
and they still separate $X$.

Let $\alpha$ be the minimal angle that can be formed between an intersection
$M$ of a wall with one such polyhedron $\sigma$, and a geodesic in $\sigma$
joining a vertex of $\sigma$ (all of which lie outside $M$) to a point of $M$.
Let $\gamma$ be the CAT(0) geodesic in $X$ between $\mathrm{id}$ and $g$.
Since $X$ and $X^{1}$ are quasi-isometric, we need to find a uniform bound for
the length $c$ of $\gamma$. By Theorem 4.2, there is a uniform bound $d$ for
the CAT(0) distance from $g$ to $\mathcal{W}_{s}$ in $X$. Let $\sigma$ be the
first polyhedron of $X$ with interior intersected by $\gamma$, and let
$M=\sigma\cap\mathcal{W}_{s}$. Note that $\gamma$ intersects $M$
(transversally at a point $m$) since $\gamma$ is disjoint from all
$\mathcal{W}_{t}$, for $t\in S\setminus\\{s\\}$. The length $c_{2}$ of the
second component of $\gamma\setminus\\{m\\}$ is $\geq
c-\mathrm{diam}(\sigma)$.

Since $X$ is CAT(0), by [Bridson-Hae_1999, II.1.7(5)], we have
$c_{2}\sin\alpha\leq d$, and so $c\leq\mathrm{diam}(\sigma)+d/\sin\alpha$, as
desired. ∎

###### Proof of Proposition 4.1.

By Theorem 4.2, there exists a constant $N=N(W)$ such that each
$\mathcal{W}(g)$ has size $\leq N$. For each $g\in W$, applying at most $N$
times Lemma 4.3, there is $h\in W$ satisfying $h\preceq g$, at distance $\leq
C=C_{0}N$ from $g$, and separated from $g$ by all
$\mathcal{W}\in\mathcal{W}(g)$. Consequently, $h\in P(g)$ and thus $h\preceq
p(g)\preceq g$, implying $\ell\big{(}p(g)^{-1}g\big{)}\leq C$, as desired. ∎

##  5\. Fellow traveller property

In this section we verify parts (ii) and (iii) of the definition of
biautomaticity.

######  Lemma 5.1.

Suppose that for $g,g^{\prime}\in W$, we have $p(g)\preceq g^{\prime}\preceq
g$. Then $p(g^{\prime})\preceq p(g)$.

###### Proof.

It suffices to prove $p(g^{\prime})\in P(g)$. We have $p(g^{\prime})\preceq
g^{\prime}\preceq g$. If $\mathcal{W}\in\mathcal{W}(g)$, and $\mathcal{W}$
separates $g^{\prime}$ from $\mathrm{id}$, then we have
$\mathcal{W}\in\mathcal{W}(g^{\prime})$. Consequently, $\mathcal{W}$ separates
$p(g^{\prime})$ from $g^{\prime}$, and hence from $g$. ∎

######  Corollary 5.2.

The voracious language satisfies part (ii) of the definition of biautomaticity
with $C$ replaced by $2C$ from Proposition 4.1.

###### Proof.

Let $g\in W$ and let $s\in S$ with $\ell(gs)<\ell(g)$. Let $g^{\prime}=gs$.
Since $p(g)\preceq g^{\prime}\preceq g$, iterating Lemma 5.1, we obtain

$\cdots\preceq p^{2}(g^{\prime})\preceq p^{2}(g)\preceq p(g^{\prime})\preceq
p(g)\preceq g^{\prime}\preceq g,$

where $p^{k}$ is defined inductively as $p^{0}(g)=g$ and
$p^{k}(g)=p(p^{k-1}(g))$ for $k>0$.

Let $v,v^{\prime}\in\mathcal{V}$ represent $g,gs,$ respectively. Let $1\leq
i\leq\ell(g)$, and let $h,h^{\prime}\in W$ be the elements represented by
$v(i),v^{\prime}(i)$, respectively. We then have $\ell(p^{k}(g^{\prime}))\leq
i\leq\ell(p^{k}(g))$, or $\ell(p^{k+1}(g))\leq i\leq\ell(p^{k}(g^{\prime}))$,
for some $k\geq 0$. Furthermore, by Proposition 4.1, we have that both
$h,h^{\prime}$ are at distance $\leq C$ from $p^{k+1}(g)$ (respectively,
$p^{k+1}(g^{\prime})$) in $X^{1},$ and so $\ell(h^{-1}h^{\prime})\leq 2C$. ∎

######  Lemma 5.3.

The voracious language satisfies part (iii) of the definition of
biautomaticity.

###### Proof of Lemma 5.3.

Let $C^{\prime}=2C(C+2Q)+2Q$, where $Q$ is the constant from Theorem 4.2 and
$C$ is the constant from Proposition 4.1.

We prove part (iii) of the definition of biautomaticity, with constant
$C^{\prime}$, inductively on $\ell(g)$, where we assume without loss of
generality $\ell(sg)>\ell(g)$. If $g=\mathrm{id}$, then there is nothing to
prove. Suppose now $g\neq\mathrm{id}$. Let $v,v^{\prime}\in\mathcal{V}$
represent $g,sg,$ respectively.

Assume first $\mathcal{W}_{s}\notin\mathcal{W}(sg)$. Then we have
$\mathcal{W}(sg)=s\mathcal{W}(g)$. Consequently, $p(sg)=sp(g)$. In particular,
the words $v^{\prime}\big{(}\ell(p(sg))\big{)}$ and
$sv\big{(}\ell(p(g))\big{)}$ represent the same element $sp(g)$ of $W$. Then
part (iii) of the definition of biautomaticity for $g$ follows inductively
from part (iii) for $p(g)$, for $i<\ell(p(sg))$, or from the definition of
$C$, for $i\geq\ell(p(sg))$.

Second, assume $\mathcal{W}_{s}\in\mathcal{W}(sg)$. Then $p(sg)$ and
$\mathrm{id}$ lie in the same half-space for $\mathcal{W}_{s}$. We claim that
for any element $h\preceq p(sg)$, there is no wall $\mathcal{W}^{\prime}$
separating $h$ from $\mathcal{W}_{s}$. Indeed, otherwise a geodesic from $sg$
to $\mathrm{id}$ passing through $h$ would intersect $\mathcal{W}^{\prime}$
twice. By the claim and Theorem 4.2, we have that $h$ is at distance $\leq 2Q$
from $sh$, which holds in particular for $h=p(sg)$. By the triangle
inequality, $sg$ and $sp(sg)$ are at distance $\leq C+2Q$ in $X^{1}$, and
hence so are $g$ and $p(sg)$. By Corollary 5.2, for $i<\ell(p(sg))$, we have
that the elements of $W$ represented by $v(i),v^{\prime}(i)$ are at distance
$\leq 2C(C+2Q)$ in $X^{1}$. Setting $h$ above to be the element of $W$
represented by $v^{\prime}(i)$, we obtain by the triangle inequality
$\ell\big{(}v(i)^{-1}sv^{\prime}(i)\big{)}\leq 2C(C+2Q)+2Q$, as desired. For
$i\geq\ell(p(sg)),$ we have obviously
$\ell\big{(}v(i)^{-1}sv^{\prime}(i)\big{)}\leq 2C$ as well. ∎

##  6\. Regularity

A _finite state automaton over $S$_ (or, shortly, _FSA_) is a finite directed
graph $\Gamma$ with:

  * •

vertex set $A$, edge set $E\subseteq A\times A$,

  * •

an edge labeling $\phi\colon E\to\mathcal{P}(S^{*})$ (the power set of
$S^{*}$), where each $\phi(e)$ is finite,

  * •

a _start state_ $a_{0}\in A$, and

  * •

a distinguished set of _accept states_ $A_{\infty}\subseteq A$.

A word $v\in S^{*}$ is _accepted by $\Gamma$_ if there exists a decomposition
$v=v_{0}\cdots v_{m}$ into subwords, and a directed edge-path $e_{0}\cdots
e_{m}$ in $\Gamma$ such that $e_{0}$ has initial vertex $a_{0}$, $e_{m}$ has
terminal vertex in $A_{\infty}$, and $v_{i}\in\phi(e_{i})$ for each
$i=0,\ldots,m$. A subset of $S^{*}$ is a _regular language_ if it is the set
of accepted words for some FSA over $S$.

######  Proposition 6.1.

The voracious language is regular.

To prove Proposition 6.1, we define an FSA $\Gamma$ over $S$ that will accept
exactly the voracious language.

######  Definition 6.2.

Let $\mathcal{U}$ be the set of walls that are not separated from
$\mathrm{id}$ by any other wall, which is finite by Theorem 4.2. The vertex
set $A$ of our FSA $\Gamma$ is the power set $\mathcal{P}(\mathcal{U})$. Let
$a_{0}=\emptyset\subset\mathcal{U}$, and $A_{\infty}=A$.

To define the edges from $a\in A$, suppose that $w\in W$ satisfies:

  1. (a)

$w$ is not separated from $\mathrm{id}$ by any wall in $a$, and

  2. (b)

$w$ is separated from each wall in $a$ by another wall, and

  3. (c)

$p(w)=\mathrm{id}$.

We then put en edge $e$ in $E$ between $a$ and $w^{-1}\mathcal{W}(w)$ with
$\phi(e)$ consisting of all the minimal length words representing $w$.

###### Proof of Proposition 6.1.

Let $\Gamma$ be the FSA from Definition 6.2, and let $\mathcal{V}$ be the
voracious language. We argue inductively on $j\geq 0$ that, among the words
$v\in S^{*}$ of length $\leq j$,

  * •

$\Gamma$ accepts exactly the words in $\mathcal{V}$, and

  * •

the accept state of each such word $v$ is $g^{-1}\mathcal{W}(g)$, where $v$
represents $g\in W.$

This is true for $j=0$ by our choice of $a_{0}$. Now let $n>0$ and suppose
that we have verified the inductive hypothesis for all $j<n$. Let $v$ be a
word in $S^{*}$ of length $n$.

Suppose first that $v$ is a word in $\mathcal{V}$ representing $g\in W$. Let
$p=p(g),w=p^{-1}g.$ By the definition of $\mathcal{V}$, we have
$v\big{(}\ell(p)\big{)}\in\mathcal{V}$. Moreover, $v\big{(}\ell(p)+1,n\big{)}$
represents $w$. By the inductive hypothesis, $\Gamma$ accepts
$v\big{(}\ell(p)\big{)}$. Furthermore, $v\big{(}\ell(p)\big{)}$ labels some
directed edge-path in $\Gamma$ from $a_{0}$ to $p^{-1}\mathcal{W}(p)$. We will
now show that $\Gamma$ has an edge $e$ from $a=p^{-1}\mathcal{W}(p)$ to
$g^{-1}\mathcal{W}(g)$, with $\phi(e)$ consisting of all minimal length words
representing $w$. To do that, we verify the conditions for $w$ from Definition
6.2. Condition (a) follows from the fact that $p\preceq g$ and so $g$ is not
separated from $p$ by any wall in $\mathcal{W}(p)$. Since $p\in P(g)$, we have
that $\mathcal{W}(p)$ is disjoint from $\mathcal{W}(g)$, which implies
condition (b) and $g^{-1}\mathcal{W}(g)=w^{-1}\mathcal{W}(w)$. Consequently,
$p(g)p(w)\in P(g)$ implying $p(w)=\mathrm{id}$, which is condition (c).

Conversely, let $v$ be accepted by $\Gamma$ and suppose that $v=v_{0}\cdots
v_{m}$ as in the definition of an accepted word. By the inductive hypothesis,
the word $v_{0}\cdots v_{m-1}$ belongs to $\mathcal{V}$ and represents $p\in
W$ such that $e_{m}$ starts at $a=p^{-1}\mathcal{W}(p)$. By the definition of
the edges, $v_{m}$ is a minimal length word representing an element $w$
satisfying the conditions (a,b,c). By condition (a), we have $p\preceq g$ for
$g=pw$. By condition (b), we have $w^{-1}\mathcal{W}(w)=g^{-1}\mathcal{W}(g)$.
Thus by condition (c), we have $p=p(g)$. Consequently, $v\in\mathcal{V}$, as
desired. ∎

## References