arXiv:1709.07021v1 [math.GR] 20 Sep 2017

UNIQUELY LABELLED GEODESICS OF COXETER GROUPS
ELISABETH FINK AND KIRILL ZAINOULLINE

Abstract. Studying geodesics in Cayley graphs of groups has been a very
active area of research over the last decades. We introduce the notion of a
uniquely labelled geodesic, abbreviated with u.l.g. These will be studied first
in finite Coxeter groups of type An . Here we introduce a generating function,
and hence are able to precisely describe how many u.l.g.’s we have of a certain
length and with which label combination. These results generalize several
results about unique geodesics in Coxeter groups. In the second part of the
paper, we expand our investigation to infinite Coxeter groups described by
simply laced trees. We show that any u.l.g. of finite branching index has finite
length. We use the example of the group D̃6 to show the existence of infinite
u.l.g.’s in groups which do not have any infinite unique geodesics. We conclude
by exhibiting a detailed description of the geometry of such u.l.g.’s and their
relation to each other in the group D̃6 .

1. Introduction
Coxeter groups are historically very important and occur naturally as reflection
groups (see e.g. [Hu90]). Over the decades they have sparked immense interest from
various sides of mathematics and physics.
In particular, geodesics on their Cayley graphs, shortest connections between
points which represent reduced words, have been of special interest [St84], [BH93],
[He94], [Ed95], [St97], [El97], [EE10], [LP13], [HNW], [Ha17]. In [AC13] and [CK16]
the authors introduce a formal power series with coefficients the number of geodesics
for right-angled and even Coxeter groups based on trees. The paper [MT13] relates
geodesics and quasi-geodesics for Coxeter groups. Related to the formal power
series of geodesic growth is the growth series of a group introduced in [P90]. This
series has been studied for different types of Coxeter groups in for example [CD91],
[M03], [A04] and been generalized in [GN97].
In this paper we introduce the notion of a uniquely labelled geodesic. Instead
of limiting our investigation to the existence of geodesics and their uniqueness, we
reach out to geodesics which are unique with respect to their total label combination
seen along the path going to a fixed point in the graph. For example, in abelian
groups these consist only of powers of the generators, as any word with more than
one letter can be written in any other order of the generators and would still yield
the same element. On the other hand, any unique geodesic is also the unique
geodesic with that label combination reaching to the element it represents.
2010 Mathematics Subject Classification. 20F55, 20F65, 05E15.
Key words and phrases. Coxeter group, unique geodesic, generating function, reduced word.
1

2

E. FINK AND K. ZAINOULLINE

Geometrically speaking, it can be shown that a word in the generators of a group
can only be a u.l.g. if it is a connected path on the Coxeter diagram which is a graph
describing the group. Hence asking for a certain u.l.g. is the equivalent of the graph
theoretical problem of finding a connected path in a graph with visiting each vertex
a given number of times.
In the first part of the paper, we study the finite Coxeter groups of type A with
n generators. We introduce a generating function, a power series in n variables,
where each monomial represents a certain label combination. We then give a precise
formula for each coefficient depending on the monomial (Corollary 3.6). Based on
this, we give exact formulas for the number of non-zero coefficients (Corollary 3.7)
as well as the total number of u.l.g.’s in these groups (Theorem 3.8), both dependent
on n.
In the second part of the paper, we expand our study to infinite groups. We
introduce the notion of a branching index (Definition 5.1) which roughly speaking
describes the turning behaviour of a connected path in the Coxeter-Dynkin diagram.
We show that any u.l.g. with finite branching index has finite length (Theorem 5.9).
We then study the affine group D̃6 [BB, Appendix A1, Table 2]. In this group, we
exhibit an infinite periodic u.l.g. (Theorem 6.6). We show that there are indeed two
more different u.l.g.’s and relate these with each other geometrically (Theorem 6.8).
Acknowledgements. Both authors were partially supported by the NSERC Discovery Grant RGPIN-2015-04469.
2. Coxeter groups
Let W be a Coxeter group of rank n that is given by generators and relations
W = hs1 , . . . , sn | s2i = 1, (si sj )mij = 1i,
where mij ≥ 2 are the Coxeter exponents. Consider its Cayley graph C with respect
to the chosen generators s1 , . . ., sn : vertices of C correspond to elements w ∈ W
and two vertices w and w′ are connected by an edge and labelled by i iff
w′ = wsi and l(w′ ) = l(w) + 1,
where l : W → Z≥0 is the length function on W . Then the shortest path ρ(w)
connecting 1 and w ∈ W corresponds to a reduced expression for w = si1 . . . sil and
its length coincides with the length l of w; such a path will be called a geodesic.
We will use a slightly different labeling of the Cayley graph: instead of an integer
i ∈ {1, . . . , n} we put the standard vector {(0, . . . , 1, . . . , 0)} where 1 is at the ith
position. By a (total) label of a geodesic ρ(w) denoted by ρ
~(w) we call the sum of
labels (considered as vectors in Zn ) of all edges of ρ or, equivalently, it is an n-tuple
(i1 , . . . , in ), where ik is the number of generators sk used to express w.
We say ρ(w) is a uniquely labelled geodesic (u.l.g.) on the Cayley graph of W , if
there is only one geodesic connecting 1 and w with label ρ~(w). Observe that u.l.g.’s
correspond to elements w ∈ W that have a unique reduced expression for a given
label.
We define the generating function
UC (t1 , . . . , tn ) =

X

(i1 ,...,in )

ai1 ,...,in ti11 . . . tinn ,

UNIQUELY LABELLED GEODESICS OF COXETER GROUPS

3

where ai1 ,...,in is the number of u.l.g.’s with label (i1 , . . . , in ), i.e.,
~(w) = (i1 , . . . , in )}|.
ai1 ,...,in = |{w ∈ W | ρ(w) is a u.l.g. with ρ
2.1. Example. The Cayley graph of the symmetric group
S4 = hs1 , s2 , s3 | s2i = 1, (s1 s2 )3 = 1, (s2 s3 )3 = 1, [s1 , s3 ] = 1i
has the form
❧ 1 ❘❘❘❘❘
❘3❘❘
❧❧❧❧
1❧
❧
2
❘❘❘❘
❧

)
u❧❧❧❧
s2 ❘❘
s1 ❘❘
❧ s3 ◗◗◗◗◗
❧
♠
❘
❘
❧
❧
♠
❘
❘
❧
❧
♠
❘
❘
❧
❧
♠
❘
❘
2◗◗◗
♠2♠
❧❧❧❘❧❘3❘❘❘
❧❧❧❘❧❘3❘❘❘
◗◗(
u❧❧❧1
)
u❧❧❧1
)
v♠♠♠♠
s1 s3
s2 s1
s2 s3 ◗
s3 s2
s1 s2
◆◆◆◆
◗◗◗
❋❋
♠♠
♣♣
①
♠
♣
♠
♣
❋
①
◗
2
2 ◗
1◆◆◆
3
2
1
3
♠
❋
①
♣
◗
♠
♣
❋❋
◆'
◗( 
 v♠♠

w♣♣
①①
①
s3 s2 s1
s1 s2 s3
s2 s3 s2
3❋
❋❋ ①s1 s3 s2❋❋ ①①1
❃❃❖❖❖ s1 s2 s1
♦
❃❃ ❖❖❖❖
♦♦♦
①①❋❋
①①❋❋
❖❖❖
❃
♦♦♦
①① ❋" |①① ❋❋
♦
①
♦
s2 s1 s3
❖❖❖
♦
3
1❋
1❃
❋❋
①3
❃❃
❖2❖
♦♦♦ 1
①①
❋❋
2♦
❖❖❖
❃❃3
♦
①
2
♦
❋" w♦♦♦
❖' |①①



s1 s2 s3 s1
s3 s2 s1 s3
◗◗◗◗ s1 s2 s3 s2 ❘❘❘❘❧❧❧ s2 s1 s3 s2 ❘❘❘❘❧❧❧ s3 s2 s1 s2
♠
❧❘❘
♠♠♠
2◗◗◗
2
❧❧❧❘❘ 1❘❘
◗( u❧❧3 ❧❧ 1❘❘)
) v♠♠♠♠
u❧❧3
s3 s2 s1 s3 s2
s1 s2 s3 s1 s2
❘❘❘❘ s1 s3 s2 s3 s1
❧❧❧
3❧
2
1❘❘❘
❧
❘)  u❧❧❧
s1 s2 s3 s1 s2 s1

which gives a polynomial generating function
UC (t1 , t2 , t3 ) = 1 + (t1 + t2 + t3 ) + (2t1 t2 + 2t2 t3 )
+ (t21 t2 + t1 t22 + 2t1 t2 t3 + t22 t3 + t2 t23 )
+ 2t1 t22 t3 + (t21 t22 t3 + t1 t22 t23 + 2t1 t32 t3 ).
2.2. Example. Suppose Γ is a finite graph where each two vertices are connected
by at most one edge. Let W be a right-angled Coxeter group associated to Γ,
i.e. adjacent vertices α and β of Γ correspond to generators sα and sβ in W with
(sα sβ )∞ = 1 (there are no relations between sα and sβ ), nonadjacent vertices
correspond to commuting generators and s2α = 1 for all α.
Since there are no relations between adjacent generators, u.l.g.’s in W are in
1-1 correspondence to (connected) paths on Γ. Hence, if we index vertices of Γ
(generators of W ) as α1 , . . . , αn , then the coefficient ai1 ,...,in of the generating
function UC counts
the number of connected paths in Γ that pass through the vertex
αj exactly ij times.
2.3. Example. Suppose W is an affine Weyl group Ã2 , i.e.
W = {s1 , s2 , s3 | s2i = 1, (si sj )3 = 1, i 6= j}.
Its Coxeter-Dynkin diagram Γ is a triangle

α1

④④
④④
④
④
④④

α3 ❈
❈❈
❈❈
❈❈
❈
α2

4

E. FINK AND K. ZAINOULLINE

where edges correspond to the braid relations (si sj )3 = 1 (there are no commuting
generators). Then the infinite word (s1 s2 s3 )∞ has the property that any finite
connected subword is a unique geodesic, in particular, it is a u.l.g. So the generating
function UC is a formal power series (not a polynomial) in Z[[t1 , t2 , t3 ]]. This has
been extensively studied in [LP13] and is closely related to the famous problem of
constructing infinite reduced words.
In the present paper we construct infinite u.l.g.’s (hence, infinite reduce words)
for some Coxeter groups whose Coxeter-Dynkin diagrams are simply-laced tree.
3. Coxeter groups of type A
Consider the case of a finite Coxeter group W of type A of rank n, i.e., mij = 2
if |i − j| > 1 and mij = 3 if |i − j| = 1 or, equivalently, the Coxeter-Dynkin diagram
of W is a chain:
◦2
◦3
...
◦n−1
◦n
◦1
We have the following observations that hold for any group of type A
3.1. Lemma. All non-zero monomials of UC are of the form
i

l+1
till tl+1
. . . timm ,

1 ≤ l ≤ m ≤ n,

where all the exponents il , il+1 , . . . , im are non-zero.
Proof. Assume that a geodesic (reduced word) ρ(w) contains no generator sk , where
2 ≤ k ≤ n − 1, but it contains generators from both subsets S = {s1 , . . . , sk−1 } and
T = {sk+1 , . . . , sn }. Then without loss of generality, ρ(w) must contain a subword
xy where x ∈ S, y ∈ T , i.e., w = u · xy · v. Since xy = yx, w can also be written
as w = u · yx · v. Both ways of writing w result in two different geodesics with the
same labels. Hence, ρ(w) can not be a u.l.g.

From the proof it follows
3.2. Corollary. In a u.l.g. ρ(w) with l(w) ≥ 2, any two adjacent generators w =
. . . si sj . . . must satisfy the condition |i − j| = 1.
3.3. Lemma. Suppose ρ(w) is a u.l.g. Then it can not contain subwords of the
form
sm sm−1 . . . sl+1 sl sl+1 . . . sm−1 sm sm−1 ,
sm−1 sm sm−1 . . . sl+1 sl sl+1 . . . sm−1 sm ,
sl sl+1 . . . sm−1 sm sm−1 . . . sl+1 sl sl+1 ,
sl+1 sl sl+1 . . . sm−1 sm sm−1 . . . sl+1 sl , where l + 2 ≤ m.
Proof. It is enough to prove it for the first word only (other words follow by symmetry). Suppose ρ(w) ∈ W contains such a subword. Then applying relations in
the Coxeter group we obtain
sm sm−1 . . . sl+1 sl sl+1 . . . sm−1 sm sm−1 =
sm sm−1 . . . sl+1 sl sl+1 . . . sm sm−1 sm =
sm sm−1 sm . . . sl+1 sl sl+1 . . . sm−1 sm =
sm−1 sm sm−1 . . . sl+1 sl sl+1 . . . sm−1 sm .

UNIQUELY LABELLED GEODESICS OF COXETER GROUPS

5

Since the first and the last subwords are different but have the same number of
occurrences of each generator, i.e., the same label, ρ(w) can not be a u.l.g.

Any word ρ(w) that does not contain subwords of the lemma, must have one of
the following forms (up to inversing the indices of generators sk 7→ sn+1−k ):
I. Suppose n ≥ 1 and l ≤ m. It decreases from m to l, that is ρ(w) = sm sm−1 . . . sl .
II. Suppose n ≥ 2 and l < i, j. First, it decreases from i till l and then it increases
till j.
si

sj
❇❇
⑤>
❇❇
⑤
❇ ⑤⑤⑤
sl

III. Suppose n ≥ 3 and l < i, j < m. First, it decreases from i till the absolute
minimum index l, then it increases till the absolute maximum index m and, finally,
decreases again till some index j. This can be depicted as follows:

si

✶✶
✶✶
✶✶


sm
✡D ✸✸✸
✡
✸✸
✡✡
✸
✡✡
✡
sj
✡
✡
✡✡

sl

3.4. Corollary. For n ≥ 3 the maximal length of a u.l.g. is 3n − 4.
Proof. The longest such word is of the form III (i = n − 1, l = 1, m = n, j = 2)
sn−1 sn−2 . . . s2 s1 s2 . . . sn−1 sn sn−1 . . . s2 ,
its length is 3n − 4 and it is a u.l.g. with label (1, 3, 3, . . . , 3, 3, 1).



The following theorem describes monomials of UC
3.5. Theorem. A non-zero monomial of UC has to be of the following type
I. tl tl+1 . . . tm for l ≤ m,
II. tl (tl+1 . . . ti )2 ti+1 . . . tm (and the inverse by tk 7→ tn+1−k ) for l < i ≤ m,
III. (a) tl (tl+1 . . . ti )2 (ti+1 . . . tj−1 )(tj . . . tm−1 )2 tm for l < i < j < m,
(b) tl (tl+1 . . . tj−1 )2 (tj . . . ti )3 (ti+1 . . . tm−1 )2 tm for l < j ≤ i < m.
Observe that Type III(a) for |i − j| = 1 overlaps with Type II for m = i + 1.
Proof. All words of forms I, II and III are u.l.g.’s that have labels and, hence,
monomials of the respective types I, II and III.

3.6. Corollary. We have the following formula for the generating function
X
aı ti11 . . . tinn ,
UC (t1 , . . . , tn ) =
ı=(i1 ,...,in )

6

E. FINK AND K. ZAINOULLINE

where the coefficients aı depend on the type of the label (monomial) ı = (i1 , . . . , in )
as follows

Type I with l = m or Type II with m = i

1

2
Type I with l < m or Type II with m > i + 1 or Type III(b),
aı =
4
Type III(a) with |i − j| > 1,



2(m − l) Type III(a) with |i − j| = 1 or Type II with m = i + 1.
Proof. We prove the last case only (previous cases follow similarly). Given a minimum index l and a maximum index m (m ≥ l + 3) as the initial index i of
a generator of the word we can choose any i ∈ {l + 1, . . . , m − 2} which gives
(m − 2) − (l + 1) + 1 = m − l − 2 different options. Inversing the indices gives the
same number of options. Hence, we obtain 2(m − l − 2) options for Type III(a).
As for Type II, a minimum index l and a maximum index m = i + 1 (m ≥ l + 2)
give two different words (up to an inverse), so we have exactly 4 options. Hence,
aı = 2(m − l − 2) + 4 = 2(m − l).

3.7. Corollary. There are exactly
in UC (incl. the constant term).

1 4
1 3
17 2
1
12 n − 6 n + 12 n − 3 n + 1

non-zero coefficients

Proof. We sum the number of respective coefficients for each type of a u.l.g.
In type I there are following cases for each pair (l, m)
(1) Case |m − l| > 1: the choices of m and l divide the list of n indices into
three parts 0 . . . 01 | 1 . . . 1 | 10 . . . 0 which gives n−1
options.
2
(2) Case |m − l| = 1: there are n − 1 options to choose (l, l + 1).
(3) Case m = l: we have exactly n options.

Hence, in total for type I, we obtain n−1
+ 2n − 1 options.
2
In type II we have the following cases

(1) Case m = i+1: this amounts
to a partition into three parts 0 . . . 01 | 2 . . . 2 |

10 . . . 0 which gives n−1
options.
2
(2) Case |m − i| > 1: this amounts to a partition into four
 non-trivial parts
0 . . . 01 | 2 . . . 2 | 1 . . . 1 | 10 . . . 0, hence, giving us n−1
options. Since a
3

monomial is not symmetric, this number doubles to 2 · n−1
by reversing
3
the generators.
(3) Case m = i: if m < n, we split the list of indices
 into three non-trivial parts
0 . . . 01 | 2 . . . 2 | 0 . . . 0 which leads to n−1
options; if m = n, then we
2
split it into two non-trivial
parts
and,
hence,
obtain
n − 1 options. So, in

total we get n−1
+
n
−
1
possibilities.
Since
a
monomial
is not symmetric,
2
this number doubles to (n − 1)(n − 2) + 2n − 2 by reversing the generators.
Finally, in type III we have
(1) Type III(a), case |j − i| > 1: this is the same number as in Type III(b)
with |i + 1 − (j − 1)| > 1. Both need 5 partitions of n
0 . . . 01|2 . . . 2|1 . . . 1|2 . . . 2|10 . . . 0,
0 . . . 01|2 . . . 2|3 . . . 3|2 . . . 2|10 . . . 0,

UNIQUELY LABELLED GEODESICS OF COXETER GROUPS

7



n−1
hence, in both cases individually we have n−1
5−1 options. This gives 2 ·
4
options in total.
(2) Type III(a), case |j − i| = 1: we have a partition into three parts 0 . . . 01 |
2 . . . 2 | 10 . . . 0. However, we have already considered coefficients with these
exponents in Type II, case (1).
(3) Type III(b), j = l + 1: wehave a partition into three parts 0 . . . 01 | 3 . . . 3 |
10 . . . 0 giving again n−1
options.
2
(4) Type III(b) with m = i + 1: we have a partition into four non-trivial
parts

0 . . . 01 | 2 . . . 2 | 3 . . . 3 | 10 . . . 0 for which we obtain again n−1
options.
3

Since a monomial is not symmetric, this number doubles to 2 · n−1
by
3
reversing the generators.

A complete list of different monomials with non-zero coefficients is given for
A3 , A4 , A5 in the Appendix 7.1.
3.8. Theorem. In a Coxeter group of type An there are exactly


if n = 2
6
UC (1, 1, . . . , 1) = 19
if n = 3

 1 4 3 3 20 2 19
3 n − 2 n + 3 n − 2 n + 1 if n ≥ 4
uniquely labelled geodesics.
Proof. We combine the Corollaries 3.6 and 3.7. The geodesics counted in the proof
of 3.7 have the following coefficients and multiplicities:
Case of the proof

multiplicity

Type I, (1)

2

number of different geodesics of this type

n−1

Type I, (2)

2

n−1

Type I, (3)

1

n

Type II, (1)

4

n−1
2

Type II, (2)

2

Type II, (3)

1

Type III, (1)

4

Type III, (2)

2(m − l − 2)

Type III, (3)

2

Type III, (4)

2

2

2·



n−1
3



(n − 1)(n − 2) + 2n − 2

2 · n−1
4
1≤l<m≤n

2 · n−1
3

2 · n−1
3

The only non-obvious case is Type III, case (2), which only applies if n ≥ 4.
Here we obtain the sum:
n−2
n
X X
2(m − l − 2).
l=1 m=l+2

8

E. FINK AND K. ZAINOULLINE

Since only the case k = m − l − 2 > 0 matters and each k occurs (n − k)-times, the
sum transforms into
(*)

n−2
X n−l−2
X
l=1

2k = 31 n3 − 2n2 +

11
3 n

− 2.

k=1

2
In view of the table above, it gives 31 n4 − 34 n3 + 11
3 n − 5n for n < 4. If n ≥ 4, then
4
2
we add (*) and the result becomes n3 − n3 + 8n3 − n + 13 .


Using the description of u.l.g.’s we can recover a result of Hart [Ha17]
3.9. Corollary. In a symmetric group Sn+1 there are n2 + 1 elements with a unique
geodesic, i.e. a uniquely reduced expression.
Proof. A uniquely reduced expression corresponds to a word of type I. Hence, there
are at most n words of length 1, n − 1 (decreasing) words of length 2 which are of
the form si si−1 . In general, there are n − l words of length l, all of which must have
the form sj sj−1 . . . sj−l+1 . In total this gives n(n+1)
words. Adding an inverse for
2
n(n+1)
2
each word of length ≥ 2 gives
· 2 − n + 1 = n + 1 unique geodesics.

2
3.10. Remark. Observe that in type A the property of being a u.l.g. can be also
interpreted using the language of rhombic tilings of Elnitsky [El97].
Following [El97] we say that two geodesics ρ1 (w) and ρ2 (w) are C1 -equivalent if
ρ2 (w) is obtained from ρ1 (w) by applying a finite number of commuting relations,
i.e., by commuting subsequent generators si sj with |i−j| > 1 in the reduced expression for w. A function ρ(w) → ρ
~(w) (which assigns to a geodesic its label) factors
through C1 -equivalence, hence, if w has a u.l.g. ρ(w), then the C1 -equivalence class
of ρ(w) must contain only one element (the geodesic ρ(w) itself). The latter means
that
A rhombic tiling of the 2(n−1)-polygon corresponding to the equivalence class of a u.l.g. ρ(w) must have a unique ordering.
We say that a tile touches a border strongly if it touches it with 2 sides and the
border is on the left from the tile. Then a tiling has a unique ordering iff it satisfies
the following property:
Any border except the rightmost one has exactly one tile that
touches it strongly (i.e. with two sides).
4. Simply laced trees
We will now investigate the case when the Coxeter-Dynkin diagram Γ describing
the Coxeter group W is no longer a chain as in the type A case, but a finite graph
where any two vertices are connected by at most one edge, i.e., W has the Coxeter
exponents mij = 2 or 3 only. More precisely, a vertex α ∈ Π corresponds to a
generator sα of W . If two vertices α, β are adjacent (connected by an edge), then
the generators satisfy the braid relation sα sβ sα = sβ sα sβ , otherwise the generators
sα and sβ commute.

UNIQUELY LABELLED GEODESICS OF COXETER GROUPS

9

We index elements of Π from 1 to n = |Π|, i.e., Π = {α1 , . . . , αn }. Consider the
Cayley graph C of W with respect to the generators sα1 , . . . , sαn and the generating
function
X
aı ti11 . . . tinn
UC (t1 , . . . , tn ) =
ı=(i1 ,...,in )

which counts the number of u.l.g.’s in the Cayley graph of W . Observe that by
reindexing Π we reindex the variables ti and the label coordinates of ı. Sometimes
we will write the elements of Π as subscripts meaning the respective indices, i.e.,
tαj = tj and iαj = ij .
By the same arguments as in the type A-case, we obtain the following generalizations of Lemma 3.1, Corollary 3.2 and Lemma 3.3:
Q
4.1. Lemma. All non-zero monomials of UC are of the form α∈Π′ tiαα , where Π′
is a connected subset of vertices in Γ and iα > 0.
4.2. Corollary. In a u.l.g. ρ(w) with l(w) ≥ 2 any two adjacent generators w =
. . . sα sβ . . . correspond to adjacent (connected by an edge) vertices α, β in Γ.
In other words, a u.l.g. is necessarily a path (with possible returns) on the
Coxeter-Dynkin diagram Γ.
4.3. Lemma. A u.l.g. can not contain a subword of the following form
sα sβ · v · sβ sα sβ

and

sβ sα sβ · v · sβ sα ,

where v does not contain generators adjacent to sα .
By Corollary 4.2 we restrict to study paths on Γ. A path in Γ is called a simple
path or a path with no returns, if every vertex on it occurs exactly once. By a
turning vertex ν of a path ρ(w) we call a vertex corresponding to a generator sν
such that sµ sν sµ is a subword of w: we go from µ to ν and then back to µ. Let
(ν1 , . . . , νr ) be a list of subsequent (following the direction of the path) turning
vertices of ρ(w) (r = 0 corresponds to the empty list). Let ν0 and νr+1 denote the
starting and the ending vertex of the path ρ(w).
sν2
sνr
✞C ✽✽✽
✠D ✼✼✼
✞
✠
✼✼
✽✽
✞
✠
sν0
✼
✹✹
✽✽
✞✞
✠✠
✞
···
✼
✠
✹✹

✼✼
✞
✠
✞
✠
s
νr+1
✹✹ ✠✠
✼✼ ✞✞
✹ ✠✠
✼ ✞✞
sν1

sνr−1

We now restrict to the case when Γ is a tree.
4.4. Lemma. Let ρ(w) be a path corresponding to a reduced word in W . Let
(ν0 , . . . , νr+1 ) be the list of turning vertices (incl. the starting and the end point).
(1) Then for all 0 ≤ i ≤ r the subpath [νi , νi+1 ] passes through νi and νi+1
exactly one time. In particular, νi 6= νi+1 for all i.
(2) Moreover, if ρ(w) is a u.l.g., then for all 1 ≤ i ≤ r the subpath [νi−2 , νi+2 ]
passes through νi exactly one time (here to simplify the notation we set
ν−1 = ν0 and νr+2 = νr+1 ).
Proof. By definition, the subpath [νi , νi+1 ] passes through the intermediate turning
vertex νi . Hence, it is enough to show that all other vertices in the subpath are

10

E. FINK AND K. ZAINOULLINE

different from νi . Since Γ is a tree, all the subpaths [νi , νi+1 ] are simple, so (1)
follows.
Let ρ(w) be a u.l.g. Suppose the subpath [νi−2 , νi+2 ] contains a second copy of
νi . Then by (1) it has to be either in [νi−2 , νi−1 ) or in (νi+1 , νi+2 ]. Suppose it is in
(νi+1 , νi+2 ]. Since Γ is a tree, any path of length ≥ 2 that starts and ends at νi and
does not go through νi has to go through the same adjacent to νi vertex µi . Hence,

ρ(w) contains a subword sµi sνi sµi vsµi sνi of Lemma 4.3, a contradiction.
4.5. Corollary. A uniquely labelled geodesic ρ(w) has to be necessarily of the following form
Type I. A simple path, i.e. each generator in ρ(w) occurs exactly once.
Type II. A path with a single turn, i.e. r = 1.
Type III. A path with r ≥ 2 turns such that for all 1 ≤ i ≤ r the subpath [νi−2 , νi+2 ]
passes through the turning vertex νi exactly one time.
Observe that if Γ is a chain, then the types I, II and III become the respective
types of the A-case, hence, they are also provide sufficient conditions for being a
u.l.g. In general, there are paths of type III which are not u.l.g’s.
4.6. Example. Consider the Weyl group E6 with the Coxeter-Dynkin diagram
α2

α1

α3

α4

α5

α6

Consider a reduced word w = s3 s1 s3 s4 s2 s4 s5 s4 s3 s1 . It corresponds to a path of
type III with r = 3 and turning vertices (α3 , α1 , α2 , α5 , α1 ), however, it contains
a subword of Lemma 4.3, hence, it is not a u.l.g. So the condition that a reduced
word ρ(w) has type III is not sufficient for being a u.l.g.
4.7. Example. Consider the Weyl group D4 that is
W = {s0 , s1 , s2 , s3 | s2k = 1, [si , sj ] = 1 and (si s0 )3 = 1 for i, j > 0}.
Its Dynkin diagram Γ is (here αi correspond to si )
α2

α1

α0

α3

Consider the reduced word ρ(w) = s0 s1 s0 s2 s0 s3 s0 s1 s0 . It corresponds to the
path of type III
ρ(w) : α0 → α1 → α0 → α2 → α0 → α3 → α0 → α1 → α0
with r = 4 and turning vertices (α1 , α2 , α3 , α1 ).
The reduced expression graph taken modulo C1 -equivalence classes (two representatives of C1 -equivalence classes are connected by a directed edge labelled by i
if the first class is obtained from the second by applying s0 si s0 → si s0 si ) for w is

UNIQUELY LABELLED GEODESICS OF COXETER GROUPS

11

given by
/ 102301303
102301030
3
f◆◆◆
@ ◆◆◆
◆◆
◆◆
✁✁
✁
✁
1◆◆
1
3◆◆
✁
◆◆◆
◆◆◆
✁

&
✁
✁
/
o
/ 120230103
101203010
101230310
102013031
102030103
3
3
1
2
♣8
❤❤❤
✁✁ ♣♣♣8
♣
❤
❤
♣
❤
✁
❤
✁ ♣♣
♣♣
❤❤❤
2
1
✁✁ ♣♣1
♣♣3
❤❤❤❤1


✁✁♣♣♣
♣♣♣
s❤❤❤❤❤
010203010
101203101 o
102010301
120213031 ❱
1
k ❱❱❱❱
❂❂◆◆◆
◆◆◆
O
O
❱❱❱❱❱
❂❂ ◆◆
◆◆
❂❂ 1◆◆◆
1❱❱❱
2◆◆
1
3
❱❱❱❱
◆
◆◆&
❂❂ ◆◆&
❱❱
/
/ 201023031
010203101
012023101
120210301 o
201020301
3
2
2❂
1
8
O
❂❂
♣♣
♣♣
♣
♣
❂❂
♣
♣
♣
♣
❂❂
1
1
♣♣2
❂ ♣♣♣♣♣
x♣♣♣
/ 202102301
020102301
012023010
2
010230310

Since there is only one reduced expression with 5 generators s0 , the reduced word
ρ(w) is a u.l.g. for the label (5, 2, 1, 1).
Observe that the word w = (s0 s1 s0 s2 s0 s3 )2 s0 is not reduced. Indeed, we have
0102030102030 →(101)2(303)1(202)30 → 1023(101)230230 → 1023010230230 →
1023010203020 → 1023012023202 → 10230120302.

5. Uniquely labelled geodesics with finite branching index
Let Γ be a simply laced tree. By the valency of a vertex in Γ we denote the
number of vertices adjacent to it. A branching vertex is a vertex of valency at least
3. An end vertex is a vertex of valency 1. A branch of Γ is a maximal connected
subchain of Γ where all vertices have valency less or equal than 2.
5.1. Definition. Let ρ(w) be a u.l.g. and let (ν1 , . . . , νr ) be the list of its turning
vertices (without the starting and the end points) so that ρ(w) contains subwords
sµi sνi sµi , 1 ≤ i ≤ r. If the adjacent vertex µi is a branching vertex, then the νi is
called a short turning vertex, otherwise it is called a long turning vertex.
We define a branching index of ρ(w) with respect to the tree Γ as the number
(repetitions are possible) of short turning vertices that is
ı(ρ(w)) = |{i ∈ {1, . . . , r} | µi is a branching vertex of Γ}|.
If ρ(w) does not have turning vertices, we set ı(ρ(w)) = 0.
As an immediate consequence of Corollary 4.5 we obtain
5.2. Lemma. Suppose a u.l.g. visits a branch on the tree Γ, i.e., goes in and out
via the branching vertex γ attached to the branch. Then it has exactly one turning
vertex inside that branch. In other words, each visit of a branch corresponds to a
turning vertex in that branch.
5.3. Lemma. Suppose a u.l.g. ρ(w) visits the same branch more than once. Let
(γ1 , . . . , γs ), s > 1 be the corresponding list of turning vertices on that branch
(observe that it is a sublist of the list of all turning vertices of ρ(w)). Let di denote
the distance between γi and the branching vertex γ (observe that a short turning
vertex has distance 1 and a long one has distance > 1).

12

E. FINK AND K. ZAINOULLINE

Then any subpath [γi , γj ], i 6= j must contain a turning vertex γk of distance
dk = max(1, min(di , dj ) − 1).
Proof. Assume this is not the case. Then there are two long turning vertices a and
b of distances da > 1 and db > 1 such that all turning vertices between a and b are
of distance < (min(da , db ) − 1). Hence, the subpath [a, b] is a subword of a word of
Lemma 4.3, a contradiction.

5.4. Corollary. If γi is a long turning vertex, then either γi−1 or γi+1 has to be a
short turning vertex.
Consider now a u.l.g. ρ(w) of maximal length with trivial branching index, i.e.,
ı(ρ(w)) = 0.
5.5. Lemma. The u.l.g. ρ(w) contains all vertices of the tree.
Proof. Assume ρ(w) does not contain a vertex v of the tree but it does contain a
vertex x adjacent to v. Because of the tree structure, removing v will divide the tree
into two disconnected sets A and B and now ρ(w) can only use vertices in either of
the two sets. Since ρ(w) goes through x at least once it has the form w1 xw2 and
we can extend the path by replacing w1 xw2 with . . . w1 xvxw2 . . .. Hence ρ(w) is
not of maximal length, a contradiction.

5.6. Corollary. All turning vertices of ρ(w) have valency 1. In particular, every
end vertex can only be visited once.
5.7. Corollary. Let (ν1 , . . . , νr ) be turning vertices of ρ(w) and let d(νi , νi+1 ) denote
P
the distance between νi and νi+1 . Then the sum S = r−1
i=1 d(νi , νi+1 ) is maximal.

5.8. Proposition. Suppose the Coxeter-Dynkin diagram of W is a simply-laced tree
with n vertices. The maximal length of a u.l.g. with ı(ρ(w)) = 0 is bounded above
2
by n2 + 25 n − 7.
Proof. The maximal distance between end vertices is n − 1 (which is achieved in
the case of a chain). Let Ve denote the set of end vertices of the tree. Since |Ve | ≤ n
we obtain 12 (n − 1)n as a bound for the maximal value of S. However we need to
consider the beginning and the end of a word which can lie on a maximal subchain.
For this we use Corollary 3.4 and add 3(n − 1) − 4 and, hence, obtain the desired
bound.

5.9. Theorem. Let Γ be an arbitrary simply-laced tree with n vertices. Then a
u.l.g. with finite branching index ı(ρ(w)) = B has length at most n2 (B + 1) + n · B.
In other words, any u.l.g. in Γ with finite branching index has finite length.
Proof. Assume the branching index of ρ(w) is ı(ρ(w)) = B. We argue using the
total number of turning vertices V . If a vertex v appears in the list V twice, then
its occurances have to be separated by a short turning vertex on the same branch.
Consecutive long turning vertices have to be on different branches. Hence, a long
turning vertex x occurs at most B + 1 times in the list V . So the list V has length
at most B + (the number of short turning vertices)(B + 1) ≤ B + n · (B + 1).
Between each pair of turning vertices we visit at most n vertices. Hence, in total
we obtain the bound n · (B + n · (B + 1)).


UNIQUELY LABELLED GEODESICS OF COXETER GROUPS
1

2

3

1

4

2

3

1

4

a

ab

b a

a b

b a

a b

b a

a b

b a

a b

b a

1

13

3 2

2 4

4 1

1 3

3 2

2 4

4 1

1 3

3 2

a

31

b

2 3

Figure 1.

a

4 2

b

1 4

a

b

3 1

a

2 3

4 2

b

a

1 4

b

3 1

13

2

3

2 3

4
a

a

b

b

2 4

4

b

4 2

The transformations of w2 to the word with reduced middle part (1b23a4)3 .

6. Infinite uniquely labelled geodesics
In the present section we construct an example of an infinite reduced word so
that any finite connected subword is a u.l.g. We do it for a simply laced tree.
Observe that one such example is produced in Example 2.3 which is not a tree
case.
Consider the infinite group D̃6 with Coxeter-Dynkin diagram as follows:

2

1

3

a

b

4

We first give a word which is not reduced:
6.1. Lemma. The word (a1a2ab3b4b)n is not reduced.
Proof. The sequence b4ba1a2ab3b4ba1a2ab3b4b can be reduced to a sequence of
smaller length as
b4ba1a2a · 3b3 · 4ba1a2ab3b4b → b4ba1a2a3b4 · 3ba1a2ab3b4b →
b4ba1a2a3b4 · b3b3 · a1a2ab3b4b → b4ba1a2a3b4 · b3b · a1a2a · 3b3b4b →
b4ba1a2a3 · 4b4 · 3ba1a2a · b34b → b4b4 · a1a2a3 · b43b · a1a2ab34b → 4ba1a2a3b4a1a2ab34b.



Let W be a Coxeter group generated by S. In [S09] the authors rephrase a result
from [FZ07] as
6.2. Lemma. If S = I ∪ J where all elements in I respectively
Q J commute pairwise,
Q
and if W is infinite and irreducible, then the word ( i∈I si j∈J sj )n is reduced for
all n.
We define I = {a, 3, 4} and J = {b, 1, 2} and show that there exists an infinite
word which is ’close’ to the one that is reduced by Lemma 6.2.
We will then show that for w = a1ab3ba2ab4b the word wn is a u.l.g.
6.3. Lemma. The word w2 can be transformed into
1a3 · 1b2 · 3a4 · 2b1 · 4a3 · 1b2 · 3a4 · 2b4,
where the subword 1b2 · 3a4 · 2b1 · 4a3 · 1b2 · 3a4 is reduced.
These word reductions are depicted in Figure 1 and show a part of the Cayley
graph of D̃6 .
Proof. The word w2 = 1a1 · 3b3 · 2a2 · 4b4 · 1a1 · 3b3 · 2a2 · 4b4 can be written as
1a · 31b · 23 · a · 42 · b · 14 · a · 31 · b · 23 · a4 · 2 · b4 → 1a3 · 1b2 · 3a4 · 2b1 · 4a3 · 1b2 · 3a4 · 2b4.

The subword 1b2 · 3a4 · 2b1 · 4a3 · 1b2 · 3a4 is now reduced by Corollary 6.2.



14

E. FINK AND K. ZAINOULLINE

12p − 1

......

12p − 6
length 12n − 6

Figure 2.

The word wn , each block represents wp as in Figure 1 where the red line
represents the reduced part.

6.4. Corollary. The word wn has form
wn = 1a3(1b23a4)2n−12b4
and, hence, it has length at least 12n − 12.
Proof. Note that w2 · w reduces to
1a3 · 1b2 · 3a4 · 2b1 · 4a3 · 1b2 · 3a4 · 2b4 · a1ab3ba2ab4b →
1a3 · 1b23a42b14a31b23a4 · 2b4 · 1a13b32a24b4 →
1a3 · 1b23a42b14a31b23a4 · 2b1 · 4a3 · 1b2 · 3a4 · 2b4 → 1a3 · (1b23a4)5 2b4.

In general, we see that wn reduces to
1a3 · 1b2 · 3a4 · 1b2 · 3a4 · 1b2 · 3a4 · 2b4 → 1a3(1b23a4)2n−1 2b4.

The estimate of the length comes from having 6(2n − 1) + 6 letters. The part of
length 6(2n − 1) is reduced and we allow for cancellation of the prefix and suffix,
with 3 letters each, cancelling at most 12 letters.

6.5. Proposition. The word wn = (a1ab3ba2ab4b)n is reduced for all n ≥ 2.
Proof. We assume it is not, then there is a power p of w such that wp is not
p
p
reduced. The word wp has 12p letters. Denote by w−
and w+
the beginning and
p
end of the path in the Cayley graph labelled by w . We assume first, there is a
p
p
shorter connection between w−
and w+
in the Cayley graph with at most 12p − 1
n
n
the beginning and end
and w+
letters. Now assume n ≥ 13 · p and denote by w−
n
of the path in the Cayley graph labelled by w . This is depicted in Figure (2).
n
n
. Denote by s− and s+ the
with w+
There are n/p copies of wp connecting w−
two vertices connecting the reduced middle part (1b23a4)2n−1 of length 12n − 6 of
wn . Because each part wp of wn is connected by a path of length 12p − 1, we get
a connection from s− to s+ of length at most
n
p

· (12p − 1) + 6 = 12n −

n
p

+ 6 ≤ 12n − 13 + 6 = 12n − 7.

However, by Corollary 6.2 the subword (1b23a4)2n−1 between s− and s+ has length
12n − 6.

6.6. Theorem. The word wn = (a1ab3ba2ab4b)n is a u.l.g.
Proof. We observe that asymptotically there are each one third a’s, one third b’s
1
th every number 1, 2, 3 and 4. We first show that the only way to have a
and 12
u.l.g. with this distribution is a periodic word. Assume the infinite word is not
periodic. Then the maximal distance between two occurances of one of the letters
1, 2, 3, 4 must be bigger than 12, because it is 12 on average. Assume without loss
of generality that it is the letter 1 which has two occurances in the infinite word
of distance more than 12. Because of the symmetries of the Coxeter tree defining

UNIQUELY LABELLED GEODESICS OF COXETER GROUPS

15

D̃6 the same arguments work for 2, 3 and 4. This can only happen in one of the
following cases. (Recall that a u.l.g. has to be a connected path in the graph.)
We go through all other possiblities which do not yield the word (a1ab3ba2ab4b)n.
Most of them either contain either xyxy, xyx . . . xyx or xy . . . yxy with no x in the
dots. The first two are not reduced words, the latter not a u.l.g. A complete list of
cases can be found in the Appendix 7.2. We discuss only the cases which are not
immediate:
(5)
(17)
(23)
(27)
(28)
(31)
(33)

a1a2ab4b
a1ab4ba2ab3ba1
a1ab4b3ba2ab4ba1a
a1ab4b3bab4b3b
a1ab4ba2ab3b4bab3b
a1ab4ba2ab3b4ba1a
a1ab4ba2ab3b4ba1ab3b

(36)
(52)
(59)
(60)
(62)
(68)

a1ab4ba2ab3b4ba1a2ab3b
a1ab4ba2ab3b4ba1a2aba1a2a
a1ab4b3ba2ab4b3ba1a2ab4b
a1ab4b3ba2ab4b3ba1a2aba1a
a1ab4b3ba2ab4b3ba1a2abab
a1ab4b3ba2ab4b3ba1ab4b

(5) Isomorphic to (6) and follows because of the isomorphism 3 ↔ 4.
(17) a1ab4ba2ab3ba1 in this case the letter 1 occurs with distance 12.
(23) a1ab4b3ba2ab4ba1a this is the complex case: We easily verify that neither
b4b, b3b nor ab can be a prefix. Hence the only case to check is a2a1a . . . :
This can only occur after aba2a1a . . . , which can only occur after either
a1 · aba2a1a . . . or a2 · aba2a1a . . . .
The word a2aba2a1a = 2a2 · ba2a1a = 2ab · 2a2a · 1a is not reduced. Hence we need
to check a1aba2a · a1a . . . :
a1aba2a1ab4b3ba2ab4ba1a = a1ab · 2a2 · 1ab4b3ba2ab4ba1a
a1ab · 2a1 · 2a · b4b3ba2ab4ba1a = a1ab · 2a1 · a2a2 · b4b3ba2ab4ba1a
a1ab2a1a2ab4b3b · 2a2a · b4ba1a = 1a1 · b2a1a2ab4b3ba2b4ba1a
1a · b2 · 1a1a · 2ab4b3ba2b4ba1a = 1ab2 · a1 · 2ab4b3ba2b4ba1a.

The first word has length 23 the last word has length 21, hence it is not reduced
and cannot occur as part of a u.l.g.
(27)
a1ab4b3bab4b3b = a1ab4b3 · aba · 4b3b = a1a · 4b4 · 3aba4b3b
a1a4b3a · 4b4 · ab3b = a1a4b3a · b4b · ab3b
a14aba3 · b4b · ab3b = a14 · bab · 3b4bab3b.

Both the first and last term have 3 times a, six times b, once 1 and twice each 3
and 4. Hence it cannot be part of a u.l.g.
(28) This word is not reduced:
a1ab4ba2ab3b4bab3b = a1ab4ba2a · 3b3 · 4bab3b
a1ab4ba2a · 3b · 4 · 3b · ab3b = a1ab4ba2a · b3b3 · 4 · 3b · ab3b
a1ab4ba2a · 3b4 · b3b3 · ab3b = a1ab4ba2a · 3b4 · b3b · a · 3b3b
a1ab4ba2a · 3b4b3b · a · b3 = a1ab4ba2a3 · 4b4 · 3bab3
= a1a · b4b4 · a2a3b43bab3.

16

E. FINK AND K. ZAINOULLINE

(31) This is the inverse of 23. Hence it cannot be succeeded by anything valid.
(33) This word is not reduced:
a1ab4ba2ab3b4ba1ab3b = a1ab4ba2a · 3b3 · 4ba1ab3b
a1ab4ba2a3b · 4 · b3b3 · a1ab3b = a1ab4ba2a3b4 · b3b · a1a · 3b3b
a1ab4ba2a3 · 4b4 · 3ba1a · b3 = a1ab4b4 · a2a3 · b4 · 3ba1ab3
= a1a · 4b · a2a3b43ba1ab3.

(36) This word is not reduced:
a1ab4ba2ab3b4ba1a2ab3b = a1ab4ba2a · 3b3 · 4ba1a2ab3b
a1ab4ba2a · 3b4 · b3b3 · a1a2ab3b = a1ab4ba2a · 3 · 4b4 · 3ba1a2a · b3
a1a · b4b4 · a2a34b43ba1a2ab3 = a1a · 4b · a2a34b43ba1a2ab3.

(52) We study the end of the sequence a2ab3b4ba1a2aba1a2a and show it is not
reduced:
a2ab3b4ba1a2aba1a2a = a2ab3b4ba1 · 2a2 · ba1a2a
a2ab3b4ba · 21 · a2ba1a2a = a2ab3b4b · 2a2a · 1a2b · 1a1 · 2a
a2a · 2 · b3b4ba2 · 1a1 · 2b · 1a1 · 2a = 2a · b3b4ba2 · 1a · 2b · a1 · 2a.

(59) This word is not reduced:
a1ab4b3ba2ab4b3ba1a2ab4b = a1ab4b3ba2ab4 · 3b3 · a1a2ab4b
a1ab4b3ba2a · 3b3b · 4b3a1a2ab4b = a1ab4 · 3b · a2ab3 · 4b4 · 3a1a2ab4b
a1ab43ba2ab34b · 3a1a2a · 4b4b.

(60) This word is not reduced:
a1ab4b3ba2ab4b3ba1a2aba1a = a1ab4b3ba2ab4b3ba1 · 2a2 · ba1a
a1ab4b3ba2ab4b3b · 2a2a · 1 · a2 · ba1a = a1ab4b3b · a2a2 · b4b3ba2a1a2ba1a
a1ab4b3b · 2a · b4b3ba2 · 1a1 · 2ba1a = a1ab4b3b2ab4b3ba21a2b · 1a1a.

(62) The same as in 59, since the extra a1a2 in (59) has no effect on the technique.
(68) a1ab4b3ba2ab4b3ba1ab4b is not reduced by the same argument as in (59) as
well.
It is left to show that the above word does not transform into the one under the
isomorphisms 3 7→ 4 or 1 7→ 2.
Case 1: We look at 3 7→ 4 first:
w2 = a1ab3ba2ab4ba1ab3ba2ab4b = 1a1 · 3b3 · 2a2 · 4b4 · 1a1 · 3b3 · 2a2 · 4b4
= 1a31b23a42b14a31b23a42b4 = 1a32b13a41b23a42b13a42b4
= 1a32b31a14b42a23b31a24b4 = 1a23b3a1ab4ba2ab3b1a24b4.

Even though the last transformation of w2 contains the word w2 = a1ab4ba2ab3b,
the letter 1 occurs more often than in w2 . Further, the last line is not a u.l.g. which
implies that wn is a u.l.g.

UNIQUELY LABELLED GEODESICS OF COXETER GROUPS
a

1

ab

1 a
3

14
41

3

42
a

a

3

2

ab

2 a
3
b
23
42
13

ba
4

4

ba

13

ab

Figure 3.

ab

3

42
a

b

2

1

3 1 a 14
b
b
13
42

42
a

b
ab

1

ba

ba
3

ba
42
13

ab

4

42
a

ba
4

ab

a 23 b
42

13
b

1

2

ba

ab

ab

3

ba

2

ab

3 1 a 14
b
13
42

42 a
13

23
42

13

13

42

42
a

b

2

1

17

ba
3

ab
1

a

b
ba
4

4

b

b
3
1
1

b
ab

2

b
3

n
The geodesic wn on the top, the geodesic w2
on the bottom.

Case 2: We now check the isomorphism 1 7→ 2.
w2 = a1ab3ba2ab4b · a1ab3ba2ab4b = 1a1 · 3b3 · 2a2 · 4b4 · 1a1 · 3b3 · 2a2 · 4b4
= 1a31b23a42b14a31b23a42b4 = 1a3 · 2b1 · 3a4 · 1b2 · 3a4 · 2b1 · 3a42b4
= 1a3 · b41 · 2a2 · 3b3 · 1a1 · 4b4 · 2a2 · 3b4 = 1a3b41 · a2ab3ba1ab4b · 2a23b4.



6.7. Corollary. The words w2n = (a1ab4ba2ab3b)n and w3n = (a2ab3ba1ab4b)n are
u.l.g.’s for all n ≥ 1.
We finish with an observation regarding the two bi-infinite geodesic rays of wn
and w2n in the Cayley graph of W . We say two geodesics γ1 and γ2 are fellow
travelling if there exists a constant D such that every point on γ2 is at distance at
most D from a point on γ1 .
6.8. Theorem. The bi-infinite u.l.g.’s with labels
(1) wn = (a1ab3ba2ab4b)n
(2) w2n = (a1ab4ba2ab3b)n
(3) and w3n = (a2ab3ba1ab4b)n
are fellow travelling at distance at most 5 but at least 2 from each other on their
entire lengths.

Proof. We can reduce w2 = a1ab3ba2ab4b · a1ab3ba2ab4b as follows:
w2 = 1a1 · 3b3 · 2a2 · 4b4 · 1a1 · 3b3 · 2a2 · 4b4
= 1a31b23a42b14a31b23a42b4 = 1a32b13a41b23a42b13a42b4
= 1a32b31a14b42a23b31a24b4 = 1a23b3a1ab4ba2ab3b1a24b4.

We note that a cyclic permutation of the last line gives w22 and we applied 6
relations to get to the last line. However, as it can be verified in Figure 3, the
shortest distance actually remains uniformly bounded above by 5.
We note that this method is independent of how many copies of w we had in the
beginning. In a similar fashion it can be seen that we can obtain w3 = a2ab3ba1ab4b.
Hence we have a bundle of three bi-infinite geodesics which remain at distance at
most 5 from each other.

7. Appendix
7.1. Type A examples. We list the u.l.g.’s with different labels for the groups of
type An for n = 3, 4, 5 by enumerating all total labels which give a u.l.g. including

18

E. FINK AND K. ZAINOULLINE

the word of length 0, which gives the constant term in the generating function. It
can be verified that these numbers correspond to the formula in Corollary 3.7.
Type

Labels of u.l.g.’s

A3

100 110 120 122 010 011 012 221 001 111 021 131 121
210 000

A4

Type I: 1000 0100 0010 0001 1100 0110 0011 0111 1110

Total
number
15

33

1111 0000

Type II and III: 1200 0120 0012 1210 0121 1220 0122
0021 2210 0221 2221 1321 1231 1331 1310 0131 1211 1121
1222 1221 0210 2100

A5

Type I: 10000 01000 00100 00010 00001 11000 01100 00110

66

00011 11100 01110 00111 11110 01111 11111 00000

Type II: 12000 01200 00120 00012 21000 02100 00210 00021
01220 00122 22100 02210 00221 12220 01222 22210 02221
22221 12100 01210 00121 12110 01211 11210 01121 12111
12210 01221 12211 11221 12221 12200 12222 11121

Type III: 12121 12321 12310 13210 13100 01310 00131
01231 12331 13321 12231 13221 13310 01331 13331 01321

7.2. Infinite u.l.g.’s in the group D̃6 . We list all cases that have to be considered
in Theorem 6.6. Figure 4 depicts the first part of these words, and the corresponding
end-vertices of the trees labelled with T 2, T 3 and T 4 indicate that the tree continues
with Figure 5, 6 or 7.
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)

a1a2a1a
a1a2a2
a1a2aba2a
a1a2abab
a1a2ab4b
a1a2ab3b3b
a1a2ab3b4ba2a
a1a2ab3b4b3b
a1a2ab3bab
a1a2ab3ba2a
a1aba2ab
a1aba2a2
a1ab3bab
a1ab3b4b
a1ab4bab
a1ab4ba2ab4b
a1ab4ba2ab3ba1
a1ab4b3b4b
a1ab4b3ba2aba
a1ab4b3ba2ab3b

(21)
(22)
(23)
(24)
(25)
(26)
(27)
(28)
(29)
(30)
(31)
(32)
(33)
(34)
(35)
(36)
(37)
(38)
(39)
(40)

a1ab4b3ba2ab4b3b3
a1ab4b3ba2ab4ba2a
a1ab4b3ba2ab4ba1a
a1ab4b3baba
a1ab4b3bab3b
a1ab4b3bab4ba
a1ab4b3bab4b3b
a1ab4ba2ab3b4bab3b
a1ab4ba2ab3b4bab4b
a1ab4ba2ab3b4baba
a1ab4ba2ab3b4ba1a
a1ab4ba2ab3b4ba2a
a1ab4ba2ab3b4ba1ab3b
a1ab4ba2ab3b4ba1ab4b
a1ab4ba2ab3b4ba1aba
a1ab4ba2ab3b4ba1a2ab3b
a1ab4ba2ab3b4ba1a2ab4b
a1ab4ba2ab3b4ba1a1
a1ab4ba2ab3b4b3b
a1ab4ba2ab3b4b4

UNIQUELY LABELLED GEODESICS OF COXETER GROUPS

(41)
(42)
(43)
(44)
(45)
(46)
(47)
(48)
(49)
(50)
(51)
(52)
(53)
(54)

a1ab4b4
a1ab4b3b3
a1ab4b3ba2a2
a1ab4b3bab4b4
a1ab4ba2a2
a1ab4ba2ab3b3
a1ab4b3ba2ab4b4
a1ab4b3ba2ab4bab
a1ab4ba2ab3b4ba1a2abab
a1ab4ba2ab3b4ba1a2aba2a
a1ab4ba2ab3b4ba1a2aba1ab
a1ab4ba2ab3b4ba1a2aba1a2a
a1ab4ba2ab3b4ba1a2aba1a1a
a1ab4b3ba2ab4b3b4b

(55)
(56)
(57)
(58)
(59)
(60)
(61)
(62)
(63)
(64)
(65)
(66)
(67)
(68)

19

a1ab4b3ba2ab4b3ba2a
a1ab4b3ba2ab4b3ba1aba
a1ab4b3ba2ab4b3ba1a1a
a1ab4b3ba2ab4b3ba1a2ab3b
a1ab4b3ba2ab4b3ba1a2ab4b
a1ab4b3ba2ab4b3ba1a2aba1a
a1ab4b3ba2ab4b3ba1a2aba2a
a1ab4b3ba2ab4b3ba1a2abab
a1ab4b3ba2ab4b3baba
a1ab4b3ba2ab4b3bab4b
a1ab4b3ba2ab4b3bab3b
a1ab4ba2aba
a1ab4b3ba2ab4b3ba1ab3b
a1ab4b3ba2ab4b3ba1ab4b

Checking the cases of the tree:
• The following cases have been shown in the proof of Theorem 6.6:
{(5), (17), (28), (31), (33), (36), (52), (59), (60), (62), (68)}.
• The following cases contain a sequence xyxy and are hence not reduced:
{2, 4, 6, 12, 21, 24, 30, 38, 40, 41, 42, 43, 44, 45, 46, 47, 49, 53, 62, 63}.
• The following cases contain xyx . . . xyx where the dots do not contain x or
y. These cases are not reduced:
{1, 3, 7, 8, 10, 16, 18, 20, 22, 25, 29, 32, 34, 39, 50, 54, 55, 57, 58, 61, 65, 67}.
• The following cases contain xy . . . yxy and are hence not a u.l.g.:
{9, 11, 13, 15, 19, 26, 35, 37, 48, 51, 56, 66}.

20

E. FINK AND K. ZAINOULLINE

1
a
b
2

3
a

4
b
4

a

T2

b
a
b

b

1

2

2

3

a

a

14

2

13

a

4

b

1

2

b

a
3

b
11

2

12

4
2

b
6
b

a

4

b

5

9
a

3

a

b

2

10

3

a
b
7

8

Figure 4. Tree 1

4
a

3

2

b

41

b

15
a

a
3

4
b

42
2

b

4

2

b

a

a

66
4

3

3

a

18

43

b
b
24

16

a

b

b

3

25
a

27

4
a
1

3

b
19

b

b

a
4
a

20
3

1

3
a

17

4

2

47
b

39

T3

a

40

a

T4
22

b
26

4

23

Figure 5. Tree 2

UNIQUELY LABELLED GEODESICS OF COXETER GROUPS

21

1

b
4
2

b

a

a

3
b

1
29

a

2

a

1
a

28

38

32
30

31

b

a

a
3

35

4

b

b

4

b
3
a

34

b

33

b

2

1

36

b

a

49

a
50

1

b
2
51

a
52

Figure 6. Tree 3

a
53

37

22

E. FINK AND K. ZAINOULLINE

3

b

a

4

b
1

21

2

b

54

3
4

a

a

a

63

55

b
1

b
65

a

64

3

4

2

57

a

56
b

b
b

67

68
a

4
3
b

b

b
1
2

59

62

58
a
a
60

61

Figure 7. Tree 4

References
[AC13] Y. Antolin, L. Ciobanu, Geodesic growth in right-angled and even Coxeter groups, European Journal of Combinatorics 34 (2013), 859–874.
[A04] A. Avasjö, Automata and growth functions of Coxeter groups, Licentiate Thesis Department of Mathematics, KTH, 2004.
[BB] A. Björner, F. Brenti, Combinatorics of Coxeter Groups, GTM 231, Springer, 2005.
[BH93] B. Brink and R. Howlett, A finiteness property and an automatic structure for Coxeter
groups, Math. Ann. 296, (1993), 179–190.
[CD91] R. Charney, M. Davis, Reciprocity of growth functions of Coxeter groups, Geometriae
Dedicata 39 (1991), Issue 3, 373–378.
[CK16] L. Ciobanu, A. Kolpakov, Geodesic growth of right-angled Coxeter groups based on trees,
J. Algebr. Comb. 44 (2016), 249–264.
[Ed95] P. Edelman, Lexicographically first reduced words, Discrete Math. 147 (1995), no.1-3,
95–106.
[El97] S. Elnitsky, Rhombic tilings of polygons and classes of reduced words in Coxeter groups,
J. Combin. Theory Ser. A 77 (1997), no. 2, 193221.
[EE10] H. Eriksson, K. Eriksson, Words with intervening neighbours in infinite Coxeter groups
are reduced, The Electronic Journal of Combinatorics 17 (2010), no 9.
[FZ07] S. Fomin, A. Zelevinsky, Cluster algebras. IV. Coefficients, Compositio Math. 143 (2007),
no. 1, 112–164.
[GN97] R. I. Grigorchuk, T. Nagnibeda, Complete growth functions of hyperbolic groups, Invent.
Math. 130 (1997), 159–188.
[Ha17] S. Hart, How many elements of a Coxeter group have a unique reduced expression?
Preprint arXiv:1701.01138 (2017).

UNIQUELY LABELLED GEODESICS OF COXETER GROUPS

23

[He94] P. Headley, Reduced expressions in infinite Coxeter groups, PhD Thesis, University of
Michigan, 1994.
[HNW] C. Hohlweg, P. Nadeau and N. Williams, Automata, reduced words, and Garside shadows
in Coxeter groups, Journal of Algebra 457 (2016), 331–456.
[Hu90] J. Humphreys, Reflection groups and Coxeter groups. Cambridge studies in Advanced
Math. 29, Cambridge Univ. Press, 1990.
[LP13] T. Lam, P. Pylyavskyy, Total positivity for loop groups II: Chevalley generators, Transformation Groups 18 (2013), no. 1, 179–231.
[M03] M. J. Mamaghani, Complete growth series of Coxeter Groups with more than three generators, Bulletin of the Iranian Mathematical Society Vol. 29 No. 1 (2003), 65–76.
[MT13] M. Mihalik, S. Tschantz, Geodesically tracking quasi-geodesic paths for Coxeter groups,
Bull. London Math. Soc. 45 (2013), 700–714.
[P90] L. Paris, Growth series of Coxeter groups, Group theory from a geometrical viewpoint
(Trieste, 1990), 302–310, World Sci. Publ., River Edge, NJ, 1991.
[S09] D. Speyer, Powers of Coxeter elements in infinite groups are reduced, Proceedings of the
American Math. Soc. 137 (2009), no. 4, 1295–1302.
[St84] R. Stanley, On the number of Reduced Decompositions of Elements of Coxeter groups,
Europ. J. Combinatorics 5 (1984), 359–372.
[St97] J. Stembridge, Some combinatorial aspects of reduced words in finite Coxeter groups,
Transactions of the American Math. Soc. 349 (1997), no. 4, 1285–1332.
(Elisabeth Fink) Department of Mathematics and Statistics, University of Ottawa,
585 King Edward Street, Ottawa, ON, K1N 6N5, Canada
E-mail address: efink@uottawa.ca
URL: http://mysite.science.uottawa.ca/efink/
(Kirill Zainoulline) Department of Mathematics and Statistics, University of Ottawa,
585 King Edward Street, Ottawa, ON, K1N 6N5, Canada
E-mail address: kirill@uottawa.ca
URL: http://mysite.science.uottawa.ca/kzaynull/

