arXiv:1510.01607v2 [math.CO] 15 Apr 2016

AUTOMATA, REDUCED WORDS AND GARSIDE SHADOWS IN
COXETER GROUPS
CHRISTOPHE HOHLWEG , PHILIPPE NADEAU, AND NATHAN WILLIAMS
Abstract. In this article, we introduce and investigate a class of finite deterministic automata that all recognize the language of reduced words of a
finitely generated Coxeter system (W, S). The definition of these automata
is straightforward as it only requires the notion of weak order on (W, S) and
the related notion of Garside shadows in (W, S), an analog of the notion of a
Garside family. Then we discuss the relations between this class of automata
and the canonical automaton built from Brink and Howlett’s small roots. We
end this article by providing partial positive answers to two conjectures: (1)
the automata associated to the smallest Garside shadow is minimal; (2) the
canonical automaton is minimal if and only if the support of all small roots is
spherical, i.e., the corresponding root system is finite.

1. Introduction
In this article, we introduce and investigate a class of finite deterministic automata that recognize the language Red(W, S) of reduced words of a finitely generated Coxeter system (W, S). The definition of these automata is straightforward,
requiring only the notion of (right) weak order ≤R on (W, S) [1, 2] and the related
notion of Garside shadows, introduced by M. Dyer and the first author in [13] as an
analog of the notion of a Garside family in a monoid; see [11, 10] and the references
therein. For general definitions and properties, we refer the reader to [25] regarding
automata and to [2, 22] regarding Coxeter groups.
A Garside shadow in (W, S) is a subset B ⊆ W that contains S and is closed
under join (for the right weak order) and by taking suffixes. In [13], the authors
show that finite Garside shadows exist
W in any Coxeter system (W, S). Let B be a
finite Garside shadow in (W, S). So X ∈ B for any bounded subset X of B, i.e.,
a subset that has an upper bound. Therefore, the following projection from W to
B is well-defined:
πB : W
w

→
7→

B
_
{g ∈ B | g ≤R w}

We denote by ` : W → N the length function of the Coxeter system (W, S).
Definition 1.1. We define a finite deterministic automaton AB (W, S) over the
alphabet S as follows:
Date: April 3, 2018.
2010 Mathematics Subject Classification. Primary 20F55; secondary 20F10; 05E15; 06F99.
Key words and phrases. Coxeter groups, Garside shadows, low elements, weak order, dominance order, small roots, automaton and reduced words.
 supported by NSERC Discovery grant Coxeter groups and related structures.
1

2

C. HOHLWEG, P. NADEAU, AND N. WILLIAMS

• the set of states is B;
• the initial state is the identity e of W , and all states are final;
s
• the transitions are: x → πB (sx) whenever `(sx) > `(x).
Since the intersection of Garside shadows is again a Garside shadow, there is a
smallest Garside shadow S̃ in (W, S). As a first example, the finite automaton built
out of the smallest Garside shadow S̃ for the infinite dihedral group is shown in
Figure 1. Further examples are given in §3.6 and in Figures 5 and 6.
Our main result is that AB (W, S) recognizes the language of reduced words of
(W, S).
Theorem 1.2. If B is a finite Garside shadow in (W, S), then the finite deterministic automaton AB (W, S) recognizes the language Red(W, S).
Theorem 1.2 is proved in §2. In §3, we show that an inclusion B ⊆ C of Garside shadows induces a surjective morphism AC (W, S) → AB (W, S) between their
associated automata. The smallest Garside shadow being finite [13, Corollary 1.2],
we are led to the following conjecture.
Conjecture 1. The automaton AS̃ (W, S) is the minimal automaton recognizing
Red(W, S).
Using Sage [23, S+ 09], we checked that Conjecture 1 holds for all Coxeter
groups W of rank at most 4 whose corresponding Coxeter graph ΓW has edge
labels less than 10; see Remark 3.15 for more details.
Our initial motivation for this work was to provide a purely combinatorial definition for an automaton that recognizes the language of reduced words. Indeed, as
we now recall, all previously-defined automata recognizing Red(W, S) require the
introduction of an auxiliary geometric representation and root system.
In 1993, B. Brink and R. Howlett [4] showed that finitely-generated Coxeter
groups are automatic, in the sense of [16], thereby filling a gap in the proof of the
“Parallel Wall Theorem” of [9]. For each Coxeter system (W, S), they provided a
word-acceptor—that is, a finite automaton that recognizes the language of lexicographically minimal reduced words in W . This particular automaton is built using
their notion of small roots, and therefore requires a geometric representation of
(W, S) and its associated root system. In a series of articles [7, 8, 5, 6], Casselman
explains how to perform practical computations in Coxeter groups using Brink and
Howlett’s word-acceptor.
We are often interested in all reduced words, not only those that are lexicographically-ordered; see for instance [26]. In his thesis [17], H. Eriksson studied a finite
deterministic automaton A0 (W, S) over S that recognizes the language Red(W, S).
The automaton A0 (W, S) is called the canonical automaton in [2, §4.8], and is built
using B. Brink and R. Howlett’s technology of small roots. An immediate consequence is that the language Red(W, S) is regular, a result we recover in Theorem 1.2.
In particular, the generating function for the number of reduced words in (W, S)
with respect to their length is a rational function.
For n ∈ N, the canonical automaton was extended, replacing small roots with
n-small roots, in [15] and [13] to the n-canonical automaton An (W, S). We recall these notions in §3, and discuss morphisms between An (W, S) and the automata AB (W, S) arising from certain finite Garside shadows B. In particular, we

AUTOMATA, REDUCED WORDS AND GARSIDE SHADOWS IN COXETER GROUPS

3

show in Corollary 3.13 that any n-canonical automaton surjects into the automaton
AS̃ (W, S), providing evidence for Conjecture 1.
Both H. Eriksson [17, Theorem 80] and P. Headley [19, Theorem V.8] prove that
en , the canonical automaton A0 (A
en , S) is minimal. Furthermore, they note
in type A
that A0 (W, S) is not minimal for general affine groups W .
We conjecture a necessary condition for the canonical automaton to be minimal.
The sufficient condition is shown in Proposition 3.14.
Conjecture 2. Let W be irreducible. Then A0 (W, S) is minimal if and only if
+
Σ = Φ+
sph , where Φsph denotes the set of roots whose support is a finite standard
parabolic subgroup.
Since A0 (W, S) surjects onto AS̃ (W, S) (Corollary 3.13), Conjecture 2 implies
Conjecture 1 for Coxeter systems for which Σ = Φ+
sph . In §3.5, we prove Conjecture 2 in the following cases.
Theorem 1.3. Conjecture 2 holds in each of the following cases:
(1) W is finite.
(2) W is right-angled, i.e. mst = 2 or ∞ for all s 6= t
(3) ΓW is a complete graph, i.e. mst > 2 for all s 6= t.
]
(4) W is of type A
n−1 .
(5) W has rank 3.
In the first four cases, Σ = Φ+
sph and A0 (W, S) is minimal.
We also checked that Conjecture 2 holds if W has rank 4 and mst < 10 for all
s 6= t; see Remark 3.15 for more details.
When (W, S) is an affine Coxeter system, P. Headley described a remarkable connection between the canonical automaton and the Shi arrangement [24]: the states
of A0 (W, S) are in bijection with the (minimal elements in the) connected regions
of the complement of the Shi arrangement for (W, S) [19]. The same relationship
holds for the states of An (W, S) and the regions of the n-Shi arrangement, as we
outline in §3.6.
2. Garside shadow automata
Fix (W, S) a Coxeter system with length function ` : W → N. The rank of W is
the cardinality of the set of simple reflections S. A word s1 · · · sk on the alphabet
S is a reduced word for w ∈ W if w = s1 · · · sk and k = `(w). For u, v, w ∈ W , we
say that:
• w = uv is reduced if `(w) = `(u) + `(v), i.e., the concatenation of any
reduced word for u with any reduced word for v is a reduced word for w;
• u is a prefix of w if a reduced word for u is a prefix of a reduced word for w;
• v is a suffix of w if a reduced word for v is a suffix of a reduced word for w.
Observe that if w = uv is reduced, then u is a prefix of w and v is a suffix of w.
The subset DL (w) = {s ∈ S | `(sw) < `(w)} of S is called the left descent set of
w ∈ W . The descent set plays an important role in the study of reduced words
since it coincides with the set of the possible first letters of reduced words of an
element w ∈ W ; see [2].
The standard parabolic subgroup WI is the subgroup of W generated by I ⊆ S.
It is well-known that (WI , I) is itself a Coxeter system and that the length function

4

C. HOHLWEG, P. NADEAU, AND N. WILLIAMS

`I : WI → N is the restriction of ` to WI . Moreover, WI is finite if and only if it
contains a longest element, which is then unique and is denoted by w◦,I .
The set XI := {x ∈ W | `(sx) > `(x), ∀s ∈ I} is the set of minimal-length
coset representatives for the coset WI \W . For any w ∈ W , there is a unique
decomposition w = wI wI , with wI wI reduced; see [2, Proposition 2.4.4]. See [22, 2]
for more details.
2.1. Weak order and Garside shadows. The (right) weak order is the order
on W defined by u ≤R v if u is a prefix of v. Since we only consider the right weak
order in this article, we only use from now on the term weak order. The weak order
gives a natural orientation of the Cayley graph of (W, S): for w ∈ W and s ∈ S,
we orient an edge w → ws if w ≤R ws. We recall the following well-known useful
properties linking descent sets and weak order, which is a rephrasing of part of [2,
Proposition 3.1.2].
Lemma 2.1. Let u, v ∈ W and s ∈ S.

(a) s ∈ DL (u) if and only if s ≤R u.
(b) If s ∈ DL (u) ∩ DL (v), then u ≤R v if and only if su ≤R sv.
(c) If s ∈
/ DL (u) and s ∈
/ DL (v), then u ≤R v if and only if su ≤R sv.
A. Björner [1, Theorem 8] proved that the weak order (W,
V ≤R ) is a complete
meet semilattice: for any A ⊆ W , there exists an infimum A ∈ W , also called
the meet of A; see [2, Chapter 3].
A subset X ⊆ W is bounded in W if there exists a g ∈ W such that x ≤R g for
any
W x ∈ X. Therefore, any bounded subset X ⊆ W admits a least upper bound
X called the join of X:
_
^
X = {g ∈ W | x ≤R g, ∀x ∈ X}.
When W is finite, any element w ∈ W is a prefix of the longest element w◦ , so
that W itself is bounded. In fact, (W, ≤R ) turns out to be a complete ortholattice;
see [2, Corollary 3.2.2].
Definition 2.2 ([13]). A subset B ⊆ W is a Garside shadow in (W, S) if B contains
S and:
W
(i) B is closed under join in the weak order: if X ⊆ B is bounded, then X ∈ B;
(ii) B is closed under taking suffixes: if w ∈ B, then any suffix of w is also in B.
Since a standard parabolic subgroup WI with its canonical set of generators
I ⊆ S forms a Coxeter system, it is natural to say that a subset B ⊆ WI is a Garside
shadow of (WI , I) if B contains I and verifies Conditions (i)–(ii) of Definition 2.2.
Note that if B is a Garside shadow in (W, S), then B ∩ WI is a Garside shadow
in (WI , I) [13, Remark 2.5(c)]. Since the intersection of Garside shadows is again
a Garside shadow, there exists a smallest Garside shadow of (W, S) containing
X ⊆ W , which we denote by GarS (X). In [13, Corollary 1.2], Dyer and the first
author show that the smallest Garside shadow
S̃ := GarS (S)
is finite. The automaton constructed from the smallest Garside shadow S̃ of the
infinite dihedral group is illustrated in Figure 1.

AUTOMATA, REDUCED WORDS AND GARSIDE SHADOWS IN COXETER GROUPS

5

Remark 2.3. The finiteness of S̃ is shown in [13] using the geometry of the root
system. A direct computational proof is still open. The problem of computing S̃
relies on finding an efficient criterion for a subset of W to be bounded.

sts

tst

st

ts

s

t

t
s

t
s

s

t
e

e

Figure 1. The weak order on the infinite dihedral group D∞ and the automaton
associated to the smallest Garside shadow {e, s, t}, which is represented by red
vertices.
2.2. Garside Shadow Projections.
Definition 2.4. Let B be a Garside shadow in (W, S). We call the surjection
πB : W
w

→ B
_
7
→
{g ∈ B | g ≤R w},

the B-projection.
Since S ⊆ B, the set {g ∈ B | g ≤R w} is non-empty and bounded for any w ∈ W .
Together with Condition (i) of Definition 2.2, this implies that the B-projection is
well-defined. Note that πB (w) can be characterized as the unique longest prefix of
w which belongs to B.
Proposition 2.5. Let B be a Garside shadow in (W, S) and u, w ∈ W , then:
(a) πB ◦ πB = πB ;
(b) πB (w) ≤R w, with equality holding if and only if w ∈ B;
(c) If u ≤R w, then πB (u) ≤R πB (w).
Proof. Properties (a) and (b) are clear from the definition. For (c), if u ≤R w then
x ≤R u implies x ≤R w for any x ∈ B, from which we conclude the proposition. 
The next proposition states that left descent sets are invariant under Garside
shadow projections.
Proposition 2.6. Let B be a Garside shadow in (W, S) and w ∈ W . Then
DL (w) = DL (πB (w)), and sπB (w) ≤R sw for any s ∈ S.
Proof. We first show DL (w) = DL (πB (w)). Let r ∈ DL (πB (w)). By Lemma 2.1(a)
and Proposition 2.5(b), we have r ≤R πB (w) ≤R w. So DL (πB (w)) ⊆ DL (w).
Conversely, let s ≤R w. Since S ⊆ B, we have s = πB (s) by Proposition 2.5(b).
Then s ≤R πB (w) by Proposition 2.5(c). So DL (w) ⊆ DL (πB (w)).

6

C. HOHLWEG, P. NADEAU, AND N. WILLIAMS

We now show sπB (w) ≤R sw for any s ∈ S. We write D := DL (w) =
DL (πB (w)). If s ∈
/ D, then the result follows from Proposition 2.5(b) and Lemma 2.1(c).
If s ∈ D, the statement follows from Proposition 2.5(b) and Lemma 2.1(b).

Remark 2.7. Definition 2.4 of πB and the proof of Proposition 2.6 require only
the conditions S ⊆ B and Condition (i) from Definition 2.2. The proof of Proposition 2.5 only uses properties of the weak order.
The next result is crucial for proving Theorem 1.2.
Proposition 2.8. Let B be a Garside shadow in (W, S). Let w ∈ W and s ∈ S
such that s ∈
/ DL (w). Then πB (sw) = πB (sπB (w)).
Proof. We have sπB (w) ≤ sw by Proposition 2.6. Therefore, by Proposition 2.5(c),
πB (sπB (w)) ≤R πB (sw). To complete the proof, we will show that πB (sw) ≤R
πB (sπB (w)), which is equivalent by Proposition 2.5 (a), (b), and (c) to the statement that πB (sw) ≤R sπB (w). We prove this last relation as follows. Using Proposition 2.6, we see that s ∈ DL (sw) = DL (πB (sw)), so that since πB (sw) ≤R sw
by Proposition 2.5(b), Lemma 2.1(b) allows us to conclude that sπB (sw) ≤R w.
Now sπB (sw) ∈ B because B is closed under taking suffixes by Definition 2.2(ii),
so that πB (sπB (sw)) = sπB (sw) ≤R πB (w) by Proposition 2.5(b,c). Multiplying
both sides by s and using Lemma 2.1(c) gives πB (sw) ≤R sπB (w).

Remark 2.9. The proof of Proposition 2.8 requires all the conditions from Definition 2.2.
Corollary 2.10. Let v ∈ W and s1 , . . . , sk ∈ S such that sk · · · s1 v is reduced.
Then
πB (sk · · · s1 v) = πB (sk πB (sk−1 πB (· · · s2 πB (s1 πB (v))))) = πB (sk · · · s1 πB (v)).
In particular:
(a) If w = sk · · · s1 is a reduced word, then
πB (w) = πB (sk · · · s1 ) = πB (sk πB (sk−1 πB (· · · s2 πB (s1 ))));
(b) If uv is reduced, u ∈ W , then πB (uπB (v)) = πB (uv).
Proof. We prove the first equality by induction on k > 0. The case k = 1 is
Proposition 2.8. Now assume the property for k − 1 > 0. Then since sk sk−1 · · · s1 v
is reduced, we have sk ∈
/ DL (sk−1 · · · s1 v). By Proposition 2.8, we obtain
πB (sk · · · s1 v) = πB (sk πB (sk−1 · · · s1 v)).
By induction, πB (sk−1 · · · s1 v) = πB (sk−1 πB (· · · s2 πB (s1 πB (v)))).
Now for the second equality, observe that πB (v) is a prefix of v by Proposition 2.5(b). Therefore sk · · · s1 πB (v) must be reduced, since sk · · · s1 v is reduced.
We conclude by applying the first equality to πB (v), recalling that πB is a projection. In particular (a) is obtained by taking v = e and (b) by considering a reduced
word sk · · · s1 for u.


AUTOMATA, REDUCED WORDS AND GARSIDE SHADOWS IN COXETER GROUPS

7

2.3. Garside Shadow Automata and Proof of Theorem 1.2. Before proving
Theorem 1.2, we recall some terminology about automata theory; see [25]. A finite
deterministic automaton A over the alphabet S is a quadruple (Q, q0 , F, δ) where
Q is a finite set of states, q0 ∈ Q is the initial state, F ⊆ Q is the set of final states,
s
and δ is a partial function Q × S → Q. If δ(q, s) = q 0 then q → q 0 is a transition.
An automaton A can thus be seen as a directed graph on the vertex set Q with
edges labeled by elements of S such that for any q, s there is at most one edge with
source q and label s.
For an automaton A, one naturally extends δ to a partial function Q × S ∗ → Q.
A word s1 · · · sk ∈ S ∗ is accepted by A if δ(q0 , s1 · · · sk ) is defined and is in F .
The set of all words accepted by A is the language recognized by A and denoted
by L(A). Languages L ⊆ S ∗ occurring in this way are called regular, and it is a
fundamental theorem of Kleene that the class of such languages coincides with the
class of rational languages; see [25, Theorem 2.1].
Let B be a Garside shadow. Recall from Definition 1.1 in the introduction that
the automaton AB (W, S) is defined by:
• the set of states is B;
• the initial state is the identity e of W , and all states are final;
s
• the transitions are: x → πB (sx) whenever s ∈
/ DL (x).

We denote AB := AB (W, S) if there is no possible confusion. We prove now that
AB (W, S) recognizes the language Red(W, S) of reduced words in (W, S).
Proof of Theorem 1.2. We prove the theorem by induction. Let P(k) (k ∈ N) be
the following property:
For any sequence s1 , . . . , sk of simple reflections, sk · · · s1 is reduced if and only
if there is a path in AB starting at the initial state e with edges labeled successively
by s1 , . . . , sk . The final state of such a path is πB (sk · · · s1 ).
By definition of AB , properties P(0) and P(1) are easily seen to be true. Now let
k > 1 be such that P(i) holds for all i < k, and consider any sequence s1 , . . . , sk ∈ S.
Let wj := sj · · · s1 , and let xj := πB (sj xj−1 ).
We first show that the sequence of edge labels for a path in AB is reduced.
Suppose there is a path in AB
s

s

s

sk−1

s

1
2
3
k
e→
x1 →
x2 →
· · · → xk−1 →
xk

from the state e to the state xk , with edges labeled by s1 , . . . , sk . By induction,
sk
sk−1 · · · s1 is reduced, so that by Corollary 2.10 πB (wk−1 ) = xk−1 . Since xk−1 →
xk is an edge in the automaton AB , sk ∈
/ DL (xk−1 ) by definition. Therefore
sk ∈
/ DL (wk−1 ), since DL (xk−1 ) = DL (wk−1 ) by Proposition 2.6. In particular,
since sk−1 · · · s1 is reduced, sk wk−1 = sk sk−1 · · · s1 is also reduced.
We now show that any reduced word sk sk−1 · · · s1 gives a path in AB from e,
with the desired edge labels and ending state. For the sake of contradiction, suppose
that the sequence s1 , . . . , sk does not define a path in AB .
This gives rise to two cases, both of which lead to a contradiction of our initial
assumption that sk sk−1 · · · s1 is reduced. If the initial sequence s1 , . . . , sk−1 does
not define a path in AB , then, by induction sk−1 · · · s1 is not reduced, contradicting
our assumption. Otherwise, the sequence s1 , . . . , sk−1 ends at the state xk−1 and, by
induction, sk−1 · · · s1 is reduced. In particular, πB (wk−1 ) = xk−1 by Corollary 2.10.
Since s1 , . . . , sk does not define a path, sk ∈ DL (xk−1 ), so that sk ∈ DL (wk−1 ) by

8

C. HOHLWEG, P. NADEAU, AND N. WILLIAMS

Proposition 2.6. But then sk sk−1 · · · s1 = sk wk−1 is not reduced, which again
contradicts our initial assumption.

Remark 2.11. Neither the definition of AB (W, S), the definition of πB nor the
proof of Theorem 1.2 requires B to be finite. However we chose to state the result
for finite Garside shadows in Theorem 1.2, since those produce finite automata.
2.4. Root systems and inversion sets. Before studying the relation between
Garside shadow automata and standard parabolic subgroups, we need to introduce
a geometric representation and a root system for (W, S).
Recall that a quadratic space (V, B) is a data of a real vector space V with a
symmetric bilinear form B. The group OB (V ) is the group consisting of all linear
maps that preserve B. For any non-isotropic vector α ∈ V , i.e., B(α, α) 6= 0, we
B(α,v)
α, for all v ∈ V .
associate a B-reflection sα given by the formula sα (v) = v −2 B(α,α)
We consider now a geometric representation of (W, S), i.e., a faithful representation of W as a subgroup of OB (V ), where S is mapped into the set of B-reflections
associated to a simple system ∆ = {αs | s ∈ S} (s = sαs ). Then the W -orbit
Φ = W (∆) is a root system with positive roots Φ+ = coneΦ (∆) and negative roots
Φ− = −Φ+ , where cone(X) is the set of nonnegative linear combination of vectors
in X ⊆ V and coneΦ (X) = cone(X) ∩ Φ; see [21, §1] for more details.
We recall now some useful well-known results linking roots and reduced words
in (W, S).
The left inversion set of w ∈ W of w ∈ W is defined by N (w) := Φ+ ∩ w(Φ− ).
The following proposition may be found in [20, §2.3-§2.5]; part (b) is due to
M Dyer [12].
Proposition 2.12. The map N : (W, ≤R ) → (P(Φ+ ), ⊆) is a poset monomorphism. Furthermore:
(a) For any u, w ∈ W , u ≤R w if W
and only if N (u)
S ⊆ N (w); 
(b) For any bounded X ⊆ W , N ( X) = coneΦ
x∈X N (x) .
If I ⊆ S, then ∆I := {αs | s ∈ I} is a simple system with root system ΦI :=
+
WI (∆I ) and positive root system Φ+
I := ΦI ∩ Φ for the standard parabolic subgroup WI . The following statement is well-known; we include a proof here for
completeness.
Corollary 2.13. Let I ⊆ S and w = wI wI with wI ∈ WI and wI ∈ XI , then
N (wI ) = N (w) ∩ Φ+
I .
Proof. The left-to-right inclusion follows from Proposition 2.12(a) since wI is a
−1
−1
prefix of w. Now let α ∈ N (w)∩Φ+
(α) = (wI )−1 wI−1 (α)
I . So wI (α) ∈ ΦI and w
+
−
I −1
+
I
is an element of Φ . Now (w ) (ΦI ) ⊆ Φ , since w ∈ XI . Thus wI−1 (α) must
be in Φ−

I , and so α ∈ N (wI ).
2.5. Parabolic Subgroups. We now discuss the behaviour of Garside shadows
with respect to standard parabolic subgroups.
Let B be a Garside shadow in (W, S) and WI be the standard parabolic subgroup
generated by I ⊆ S. Then B ∩ WI is a Garside shadow [13, Remark 2.5(c)]. Let
(I)
AB (W, S) be the restriction of the automaton AB (W, S) to the states corresponding to B ∩ WI and to the transitions corresponding to s ∈ I.
Proposition 2.14. Let B be a Garside shadow and I ⊆ S.

AUTOMATA, REDUCED WORDS AND GARSIDE SHADOWS IN COXETER GROUPS

9

(a) The restriction of πB to WI is the (B ∩ WI )-projection πB∩WI : WI → B ∩ WI .
(I)
(b) AB (W, S) = AB∩WI (WI , I).
Proof. (a) By definition of Garside shadow projections, we need to show that for
any w ∈ WI we have {g ∈ B | g ≤R w} = {g ∈ B ∩ WI | g ≤R w}.
The right-to-left inclusion is obvious. Now let w ∈ WI and g ≤R w. Since
w ∈ WI , any reduced word for w uses only letters from I, by [2, Corollary 1.4.8(ii)].
In particular any prefix of w is in WI . Since g ≤R w, g is a prefix of WI . Therefore
g ∈ WI , which concludes the proof of (a).
(I)

(b) By definition, the states of AB (W, S) and of AB∩WI (WI , I) are the same. The
fact that the transitions are the same follows by (a).


Remark 2.15 (Minimal automata and restriction to standard parabolic subgroups).
We do not know if the restriction of a Garside shadow to WI is compatible with Garside closure [13, Remark 2.5(c)]. In other words, if B is a Garside shadow in (WI , I),
(I)
is GarS (B) ∩ WI = B? In particular, we do not know if AS̃ (W, S) = AI˜(WI , I).
Another way to restrict a Garside shadow to a standard parabolic subgroup
is by the mean of the minimal coset representatives decomposition; the associated
automaton structure is discussed in Proposition 3.2. Recall that any element w ∈ W
has a unique decomposition w = wI wI with wI ∈ WI and wI ∈ XI . We denote by
pI : W → WI the projection defined by pI (w) := wI .
Proposition 2.16. Let B be a Garside shadow in (W, S) and I ⊆ S.
(a) The set pI (B) is a Garside shadow in (WI , I).
(b) We have pI ◦ πB = πpI (B) ◦ pI .
Remark 2.17. We have B ∩ WI ⊆ pI (B), but equality does not hold in general.
Indeed, let S = {s, t, u} and W = {S | s2 = t2 = u2 = 1, su = us}. One checks that
B := {1, s, t, u, su, tu, stu} is a Garside shadow for (W, S). Now pick I = {s, t}.
Then we have pI (stu) = st ∈
/ B while stu ∈ B, so st ∈ pI (B) \ (B ∩ WI ).
To prove the proposition, we need the following lemma.
W
W
Lemma 2.18. Let X be a bounded set in W and I ⊆ S, then pI ( X) = pI (X).
Proof. By Corollary 2.13 and Proposition 2.12(b) we have


N pI

_

X



=N

_

!



X ∩ ΦI = coneΦ

[
x∈X

N (x)

∩ ΦI .

Since our statement is about combinatorics of reduced words, we consider without
loss of generality the simple system to be a basis of V . So in particular span(ΦI )
is a supporting hyperplane of cone(∆). Therefore,
!
!
[
[
coneΦ
N (x) ∩ ΦI = coneΦ
N (x) ∩ ΦI ,
x∈X

x∈X

since there are only finitely many generators for each cone. So by Corollary 2.13
we obtain
!
 _ 
[
N pI
X
= coneΦI
N (pI (x)) .
x∈X

10

C. HOHLWEG, P. NADEAU, AND N. WILLIAMS

Finally, by Proposition 2.12(b) and Corollary 2.13 again we have:
!
_

 _ 
[
N
pI (X) = coneΦI
N (pI (x)) = N pI
X .



x∈X

Proof of Proposition 2.16. (a) We verify the conditions in Definition 2.2. It is clear
that pI (B) ⊆ WI . Now, since pI (s) = s for any s ∈ I and I ⊆ S ⊆ B we
have I ⊆ pI (B). For Condition
(i), consider X ⊆ B bounded inWW . So pI (X) is
W
bounded in W , so its join W pI (X) exists.WWe have to show that pI (X) ∈ pI (B).
By
since
W Lemma 2.18 we have pI (X) = pI ( X), which is an element of pI (B)
X ∈ B. For Condition (ii), consider w ∈ B and a suffix v of wI . Since wI ∈ XI ,
the expression vwI is reduced. Therefore, vwI is a suffix of w ∈ B. Since B is a
Garside shadow, vwI ∈ B. Furthermore, pI (vwI ) = v, so v ∈ pI (B).
(b) It is enough to show that for w ∈ W , we have
{pI (g) | g ∈ B, g ≤R w} = {g 0 ∈ pI (B) | g 0 ≤R pI (w)}.

But this follows easily from Proposition 2.12(a) together with Corollary 2.13.

3. Morphisms and Garside Shadow Automata
In this section, we discuss morphisms between Garside shadow automata, then
we compare the automata of a particular family of Garside shadows, the set of n-low
elements with the family of n-canonical automata. We first recall the definitions of
morphisms of automata, minimal automata, and the concept of minimal roots for
(W, S).
3.1. Morphisms of automata. We refer the reader to [25, Chapter II(3)] for
additional details on morphisms of automata. Here we shall only use this notion in
a particular case suited to our various automata.
Definition 3.1 (see [25, Chapter II(3)]). Let A = (Q, q0 , F, δ) and A0 = (Q0 , q00 , F 0 , δ 0 )
be two finite deterministic automata over the same alphabet S. A function f : Q →
Q0 is a morphism of automata between A and A0 if
(i) f (q0 ) = q00 ;
(ii) f (F ) ⊆ F 0 ;
s
s
(iii) If q1 → q2 is a transition in A, then f (q1 ) → f (q2 ) is a transition in A0 .
A morphism of automata f is totally surjective if f is surjective, satisfies f −1 (F 0 ) =
s
F and if, for any transition q10 → q20 in A0 , there exists q1 , q2 such that f (q1 ) =
s
q10 , f (q2 ) = q20 and q1 → q2 in A. In this case A0 is called a quotient of A.
If f is a morphism between A and A0 then L(A) ⊆ L(A0 ). If f is totally surjective
then L(A) = L(A0 ).
The following proposition gives a first example of a totally surjective morphism
related to Garside shadow automata and arising from the surjection pI from Proposition 2.16.

Proposition 3.2. Let I ⊆ S and B be a Garside shadow in (W, S). The automaton
AB (W, I) is defined by taking the same states B, initial state e, and final states as
AB (W, S), but with only the transitions of AB (W, S) corresponding to letters in I.
Then the surjection pI : B → pI (B) induces a totally surjective morphism from
AB (W, I) to ApI (B) (WI , I).

AUTOMATA, REDUCED WORDS AND GARSIDE SHADOWS IN COXETER GROUPS

11

Proof. Let us first show that pI verifies the conditions in Definition 3.1. We have
pI (e) = e, and all states are final in both AB (W, I) and ApI (B) (WI , I), so (i) and
s
(ii) hold. To prove (iii), let w → πB (sw) be a transition in AB (W, I) with s ∈ I \
s
DL (w). We have to show that pI (w) → pI (πB (sw)) is a transition in ApI (B) (WI , I).
s
Since DL (w) ∩ I = DL (pI (w)), there is a transition pI (w) → πpI (B) (spI (w)). The
equality pI (πB (sw)) = πpI (B) (spI (w)) is then guaranteed by Proposition 2.16(b)
since pI (sw) = spI (w) for any s ∈ I \ DL (w).
s
To prove that pI is totally surjective, let pI (w) → πpI (B) (spI (w)) be a transition
s
in ApI (B) (WI , I), with w ∈ B and s ∈ I \ DL (pI (w)). Then w → πB (sw) is a
transition in AB (W, I) since DL (w) ∩ I = DL (pI (w)), and we conclude as in the
previous paragraph.

Minimal automata. Given a regular language L ∈ S ∗ , there exists an automaton
R(L) which recognizes L and is a quotient of all automata that recognize L, called
the minimal automaton of L.
It can be constructed as follows: given u ∈ S ∗ , define u−1 L to be the set of
v ∈ S ∗ such that uv ∈ L, and let QL = {u−1 L | u ∈ S ∗ }. We then define
R(L) = (QL , qL , FL , δL ) with qL = L, FL = {u−1 L | u ∈ L} and transitions
δL (u−1 L, a) = (ua)−1 L. This automaton clearly recognizes L.
Now pick any deterministic, complete1 automaton A such that L = L(A). Given
q ∈ Q, let Lq (A) be the language recognized by the automaton A with q replacing
q0 as initial state. If Lq (A) = Lq0 (A) then q and q 0 are called equivalent states.
Then q 7→ Lq (A) is a totally surjective morphism from A to R(L). Therefore in
order to prove that an automaton is minimal, one must show that distinct states
are never equivalent.
Remark 3.3. Denote by Amin (W, S) the minimal automaton that recognizes the
(I)
language Red(W, S). For I ⊆ S, we define the automaton Amin (W, S) to be the
restriction of Amin (W, S) to the transitions in I and the states that can be reached
(I)
from the initial state using these transitions. We now show that Amin (W, S) =
Amin (WI , I), so that minimal automata remain minimal upon restriction to a parabolic subgroup.
(I)
Let q1 , q2 be distinct states in Amin (W, S); q1 , q2 can be reached by reading (reduced words for elements) w1 , w2 ∈ WI , respectively. Since q1 , q2 are non-equivalent
states in Amin (W, S) by minimality, there exists w ∈ W such that w1 w is reduced
while w2 w is not reduced. Now use the decomposition w = wI wI with wI ∈ WI and
wI ∈ XI , then w1 wI is reduced while w2 wI is not reduced. So the states are not
(I)
equivalent in Amin (W, S), which is therefore the minimal automaton Amin (WI , I)
that recognizes Red(WI , I).
(I)
Therefore—assuming Conjecture 1—we conclude that AS̃ (W, S) = AI˜(WI , I),
resolving our question in Remark 2.15.
3.2. Inclusion of Garside shadows and morphisms of automata.
Proposition 3.4. If C ⊆ B are two Garside shadows, then πC ◦ πB = πC .
1This means that δ is defined everywhere. Any automaton can be transformed into a complete
one by adding a non-final sink state † and transitions δ(q, s) := † whenever δ is not previously
defined.

12

C. HOHLWEG, P. NADEAU, AND N. WILLIAMS

Proof. It is enough to show that for w ∈ W , we have

{g ∈ C | g ≤R πB (w)} = {g ∈ C | g ≤R w}.

The left-to-right inclusion follows from Proposition 2.5(b). Now let g ∈ C such that
g ≤R w. Since C ⊆ B we have by Proposition 2.5(b,c) that
g = πB (g) ≤R πB (w),

which concludes the proof.



Corollary 3.5. If C ⊆ B are two Garside shadows, then the C-projection πC
induces a totally surjective morphism from AB to AC . In particular, AS̃ is a
quotient of any Garside shadow automaton.
Proof. The C-projection πC : B → C is surjective, since if w ∈ C, then w ∈ B and
πC (w) = w. We now show that πC verifies the conditions in Definition 3.1.
(i) Since e ∈ C, πC (e) = e.
s
(ii) Let w → πB (sw) be a transition in AB with s ∈
/ DL (w). We have to show that
s
πC (w) → πC (πB (sw)) = πC (sw) is a transition in AC , using Proposition 3.4.
Since DL (w) = DL (πC (w)) by Proposition 2.6, we have s ∈
/ DL (πC (w)). So
s
πC (w) → πC (sπC (w)) is a transition in AC by definition, and we conclude by
Proposition 2.8.
(iii) This holds since all states are final in both automata and πC is surjective.
s

To prove that πC is totally surjective, it remains to show that, if v → v 0 is a
s
transition in AC , there is a transition u → u0 in AB with πC (u) = v and πC (u0 ) = v 0 .
But this is guaranteed by taking u := v and u0 := v since C ⊆ B.

To conclude this discussion, we show Conjecture 1 in the finite case.
Proposition 3.6. Assume that W is finite. Then S̃ = W and AS̃ is the minimal
automaton that recognizes Red(W, S).
Proof. The fact that W is finite implies that S̃ = W [13, Proposition 2.2(3)].
Therefore πS̃ = πW = IdW , the identity map on W . Thus AS̃ has states indexed
s
by W and transitions w → sw if s ∈
/ DL (w).
Let u, v ∈ W be two equivalent states , i.e. for any s1 , s2 , · · · , sk , we have that
sk · · · s1 u is reduced if and only if sk · · · s1 v is reduced. We must prove that u = v
. Let k ≥ 0 be maximal so that there exist s1 , s2 , · · · , sk with sk · · · s1 u reduced;
note that k exists since W is finite. By hypothesis, sk · · · s1 v is reduced and k
is necessarily also maximal for that property. But there is a unique element w
satisfying DL (w) = S, namely the longest element w◦ [2, Proposition 2.3.1(ii)].
This shows that sk · · · s1 u = w◦ = sk · · · s1 v and thus u = v.

3.3. Small Inversion Sets and Low Elements. In [4], the authors introduced
a partial order  on Φ+ called the dominance order defined by:
αβ

⇐⇒

+

(∀w ∈ W, β ∈ N (w) =⇒ α ∈ N (w)).

The ∞-depth of β ∈ Φ is the number of positive roots strictly dominated by β:
dp∞ (β) := |{α ∈ Φ+ | α ≺ β}|.

Definition 3.7. Let n ∈ N, we say that a root β ∈ Φ+ is n-small if dp∞ (β) ≤ n
and set Σn (W ) to be the set of n-small roots.

AUTOMATA, REDUCED WORDS AND GARSIDE SHADOWS IN COXETER GROUPS

13

A 0-small root is called a small root and we write Σ(W ) := Σ0 (W ). B. Brink and
R. Howlett showed in [4] that Σn is finite for n = 0. This result was later extended
by X. Fu [18] to all n ≥ 0. The (left) n-small inversion set of w ∈ W is
Σn (w) := N (w) ∩ Σn ,
and we denote by Λn (W ) ⊆ P(Σn (W )) the set of all n-inversion sets. Since Σn (W )
is finite, Λn (W ) is also finite. We write Σ(w) := Σ0 (w).
Definition 3.8. An element w ∈ W is n-low if N (w) = coneΦ (Σn (w)). We denote
by Ln (W ) the set of n-low elements in W .
A 0-low element is called a low element and we write L(W ) := L0 (W ). Low
elements were introduced by P. Dehornoy, M. Dyer, and the first author in [11],
and extended for any n ∈ N by M. Dyer and the first author in [13]. We refer the
reader to [13, §3.1-§3.3] for more details and examples; examples of low elements
are also given in Figure 4. We summarize here some results concerning n-small
inversion sets and n-low elements.
Theorem 3.9 ([13]). Let n ∈ N.
(a) The map Σn : Ln (W ) → Λn (W ) is injective.
(b) The set Ln (W ) of n-low elements is finite and closed under join in (W, ≤R ).
(c) The set of low elements L(W ) is a finite Garside shadow in (W, S).
(d) If (W, S) is finite, affine or with Coxeter graph with edges labelled by 3, ∞, then
the set Ln (W ) of n-low elements is a finite Garside shadow in (W, S).
The statements (a) and (b) are [13, Proposition 3.26], the statement (c) is [13,
Theorem 1.1] and (d) is [13, Theorem 1.3 and Theorem 4.17]. We end this discussion
by recalling two conjectures from [13]:
[13, Conjecture 1]: The set Ln (W ) is a finite Garside shadow in (W, S).
[13, Conjecture 2]: The map Σn : Ln (W ) → Λn (W ) is a bijection.
3.4. Low Element Automata and Canonical Automata. Let n ∈ N∗ , the
n-canonical automaton is the finite automaton An (W, S) over S defined as follows:
• the (finite) set of states is Λn (W );
• the initial state is ∅(= Σn (e)) and all states are final;
s
• the transitions are: A → {αs } ∪ (s(A) ∩ Σn ) whenever αs ∈
/ A.
As shown in [13], if A = Σn (w) then s ∈
/ DL (w) if and only if αs ∈
/ A, and in this
case {αs } ∪ (s(A) ∩ Σn ) = Σn (sw). The transitions are thus well defined. Also, one
has immediately that if w = s1 · · · sk is reduced, then the path from ∅ with labels
s1 , . . . , sk ends in the state Σn (w).
Therefore the n-canonical automaton An (W, S) recognizes Red(W, S), for any
n ∈ N.
The 0-canonical automaton, or simply the canonical automaton, was studied by
H. Eriksson in his thesis [17] and named in [2, §4.8].
When Ln (W ) is a Garside shadow in (W, S)—which we suspect is always the
case [13, Conjecture 1]— we may consider the associated finite Garside shadow
projection and automaton.
Proposition 3.10. Let n ∈ N.
(a) The Garside shadow projection πLn (W ) is well-defined.

14

C. HOHLWEG, P. NADEAU, AND N. WILLIAMS

(b) The map πn : Λn (W ) → Ln (W ) defined by πn (Σn (w)) := πLn (W ) (w) is a
well-defined surjection.
(c) The map π0 induces a totally surjective morphism from the canonical automaton
A0 (W, S) to the automaton AL(W ) (W, S).
(d) If Ln (W, S) is a Garside shadow in (W, S), then πn induces a totally surjective morphism from the n-canonical automaton An (W, S) to the automaton
ALn (W ) (W, S).
Proof. (a) As observed in Remark 2.7, the definition of the Garside shadow projection πLn (W ) only requires Ln (W ) to contain S and be closed under taking
joins, which is guaranteed by Theorem 3.9(b).
(b) The fact that πn is surjective follows from the definition of Λn (W ). To prove
that πn is well-defined, let u, v ∈ W such that Σn (u) = Σn (v). We have to
show that πLn (W ) (u) = πLn (W ) (v). By Definition 2.4, it is enough to show that
{g ∈ Ln (W ) | g ≤R u} = {g ∈ Ln (W ) | g ≤R v}.

Let g ∈ Ln (W ) such that g ≤R u. By Proposition 2.12, we have N (g) ⊆ N (u),
and therefore Σn (g) ⊆ Σn (u) = Σn (v). Since g is n-low we have by definition
N (g) = coneΦ (Σn (g)) ⊆ coneΦ (Σn (v)) ⊆ N (v).

Therefore, again by Proposition 2.12, g ≤R v. This shows the left-to-right
inclusion, and we conclude the other inclusion by symmetry.
(c) This follows from (d) and Theorem 3.9(c).
(d) We must check the three conditions of Definition 3.1:
(i) This follows from the fact that πn (∅) = πn (Σn (e)) = πLn (W ) (e) = e.
(ii) This follows since every state in both automata is final and πn is surjective.
(iii) By definition of the transitions in ALn (W ) (W, S) and An (W, S), one must
check that if s ∈
/ DL (w), then πLn (W ) (sπLn (W ) (w)) = πLn (W ) (sw). This
follows immediately from Proposition 2.8.
s
To prove that πn is totally surjective, it remains to show that, if w →
s
πLn (W ) (sw) is a transition in ALn (W ) (W, S), then Σn (w) → Σn (sw) is a trans
sition in An (W, S). But s ∈
/ DL (w), therefore αs ∈
/ Σn (w), and so Σn (w) →
Σn (sw) is a transition in An (W, S).

Remark 3.11. Let n ∈ N. If the map Σn : Ln (W ) → Λn (W ) is a bijection, i.e.
[13, Conjecture 2] has a positive answer, then πn would induce a isomorphism from
the n-canonical automaton An (W, S) to ALn (W ) (W, S).
Proposition 3.12. If W is finite, then the canonical automaton A0 (W, S) is minimal.
Proof. Since W is finite, we have Φ+ = Σ(W ). Then in particular Σ(w) = N (w)
for any w ∈ W and therefore L(W ) = W = S̃, by Proposition 3.6. So N = Σ :
L(W ) = W = S̃ → Λ(W ) is a bijection and therefore A0 (W, S) and AS̃ (W, S) are
isomorphic. The result follows therefore by Proposition 3.6.

The next corollary of Proposition 3.10, together with Corollary 3.5, strengthens
the evidence for Conjecture 1.
Corollary 3.13. The automaton AS̃ (W, S) associated to the smallest Garside
shadow S̃ in (W, S) is a quotient of all canonical automata An (W, S).

AUTOMATA, REDUCED WORDS AND GARSIDE SHADOWS IN COXETER GROUPS

15

Figure 2 illustrates all of our automata recognizing Red(W, S), and the maps
between them.

p2
A2

πL2
π2

p1
A1

πL1
π1

p0
A0

AL2
AL1
πL0

π0

AL0

πS̃

AS̃

pmin

Amin

Figure 2. Commutative diagram relating the various automata described in this
article. The projections πi are conjectured to be bijections [13, Conjecture 2], and so
is pmin (Conjecture1). The sets Li ⊆ W are conjectured to be Garside shadows [13,
Conjecture 1]; only L0 is known to be. Finally Conjecture 2 characterizes when the
bottom row pmin ◦ πS̃ ◦ π0 is an isomorphism.
3.5. Minimality of the canonical automaton. A positive root β ∈ Φ+ =
coneΦ (∆) has
P a unique expression with nonnegative linear combination of vectors
in ∆: β = s∈S as αs , with as ≥ 0; we define the support of β to be the set
supp(β) := {s ∈ S | as > 0}.

We say that a positive root β is spherical if the standard parabolic subgroup
Wsupp(β) is finite, and we write Φ+
sph for the set of spherical roots.
Spherical roots are always small. Now if the reverse inclusion holds, the following
proposition shows that the canonical automaton is minimal, so that one implication
in Conjecture 2 is true.
Proposition 3.14. Let W be irreducible. If Σ = Φ+
sph , then A0 (W, S) is minimal.
The following proof is inspired by Theorem V.8 in P. Headley’s thesis [19].
Proof. Let Σ(u) and Σ(v) be two equivalent states of A0 (W, S). This means that
for any s1 , s2 , · · · , sk in S, we have that sk · · · s1 u is reduced if and only if sk · · · s1 v
is reduced. We have to show that Σ(u) = Σ(v).
Assume that they are distinct, so that, up to exchanging the role of u and v,
there is α ∈ Σ(u) \ Σ(v). By assumption, Σ = Φ+
sph , so there is I ⊆ S such that WI
+
is finite and α ∈ ΦI .
Now we use the decompositions u = uI uI and v = vI v I in WI × XI . The
expression wu is reduced if and only if wuI is reduced, since guI is reduced for any
g ∈ WI . So we have that for any s1 , . . . , sk ∈ I, sk · · · s1 uI is reduced if and only if
sk · · · s1 vI is reduced.
Since WI is finite, the automaton A0 (WI , I) is minimal by Proposition 3.12.
Therefore Σ(uI ) = Σ(vI ). Note that Σ(uI ) := Σ(u) ∩ ΦI and Σ(vI ) := Σ(v) ∩ ΦI

16

C. HOHLWEG, P. NADEAU, AND N. WILLIAMS

are small inversion sets for (WI , I), by Corollary 2.13 and the definition of small
inversion sets. But α was chosen to be in ΦI ∩ Σ(u), which contradicts that α ∈
Σ(u) \ Σ(v). Therefore, Σ(u) = Σ(v).

We conclude by proving Theorem 1.3.
Proof of Theorem 1.3.
(1) This is Proposition 3.12, since A0 (W, S) and AS̃ (W, S)
are isomorphic in this case.
(2) Here Σ = Φ+
sph = S; see for instance [11, Proposition 5.1(iii)]. So we are in
the case of Proposition 3.14.
+
(3) In this case Φ+
sph consists of the union of all Φs,t where mst < ∞. This
is equal to the whole ofΣ since the support of a small root is a tree with
no ∞-edge [3]. We conclude again by Proposition 3.14. Note that one can
actually give an explicit description of the canonical automaton in this case
and prove its minimality directly.
(4) The fact that the automaton is minimal in this case is due to Eriksson [17,
Theorem 80]. Now recall that the Coxeter graph is a simply-laced cycle.
Since the support of a small root is a tree [3], we have Σ = Φ+
sph here and
the conjecture holds by Proposition 3.14.
(5) The case of complete graphs was already checked, so one may assume that
we have generators s, t, u with msu = 2 and 3 ≤ mst ≤ mtu . Denote
m = mst and p = mtu . If p = ∞, or if m = 3 and p < 6, we have Σ = Φ+
sph ,
so Proposition 3.14 gives us the result.
We may now assume (m = 3 and p ≥ 6) or (m, p ≥ 4); in particular W
is not finite. Write ci = 2 cos(π/i). Then α := usαt = cm αs + αt + cp αu
is a small root which is not spherical, so that Σ 6= Φ+
sph . To show that
the conjecture holds we thus need to find two distinct equivalent states in
A0 (W, S).
Now su and tsu are reduced words, with distinct final states in A0 (W, S)
given by Σ(su) = {αs , αu } and Σ(sut) = {αs , αu , α}. We have DL (su) =
DL (tsu) = {s, u}, so only t can be read from any of these states. Now a
quick computation shows t(α) = α + (c2m + c2p − 1)αt . Since c2m + c2p − 1 ≥
2 for all considered values of m and p, we have t(α) ∈
/ Σ and therefore
Σ(tsu) = Σ(tsut). This shows that Σ(su) and Σ(tsu) are equivalent states,
and thus that A0 (W, S) is not minimal.

Remark 3.15 (On Conjectures 1 and 2). Using Sage [23, S+ 09], we wrote code to
compute the set of small roots. We used these to compute the canonical automaton,
from which we determined the minimal automaton. It is simple to test if a given
small roots is spherical by examining the simple roots that occur in its support, from
which we are able to check Conjecture 2. This code is sufficiently fast to compute
examples in rank 5—for example, we determined that the minimal automaton for
e 5 has size 58965.
D
We also wrote a naive implementation to determine the minimal Garside shadow
using Definition 2.2 to check Conjecture 1. This code finishes in a few minutes on
standard hardware in rank four (and below), but already takes longer than several
hours in rank five.

AUTOMATA, REDUCED WORDS AND GARSIDE SHADOWS IN COXETER GROUPS

17

Our software confirms that Conjectures 1 and 2 hold for all Coxeter groups of
rank 4 with edge labels less than 10. Figure 3 includes data for a few selected
Coxeter groups of low rank.
Name Coxeter Diagram |A0 (W, S)| |ASe(W, S)| |Amin (W, S)| |Σ| |Φ+
sph |
1

e2
A
e2
C
e2
G

3

1

4

3
2

4

3

1

3

2

6

3

1

3

2

3
3

3
3

e3
A
e3
C

3

1

2

3

3

4

4
2

3
4

3

e3
B

3

1

4

4

16

16

16

6

6

25

24

24

8

7

49

41

41

12

8

125

125

125

12

12

343

317

317

18

15

343

315

315

18

15

92

92

92

15

15

164

164

164

21

21

91

80

80

18

14

100

90

90

30

25

2
3

4
3
3

1

4

2

5
4

4
3
3

1

4

2

5
5

4
3
3

1

4

2

5
6

4
1

3

2

5

9

6

4

8

3

Figure 3. Numerical data for selected Coxeter groups. Note that in affine type
fn , |A0 (W, S)| = (h + 1)n and |Σ| = nh, where h is the Coxeter number of the
W
corresponding finite Weyl group.
3.6. Canonical automata and Shi arrangements. We end this article by describing some rank 3 examples of automata. It turns out these examples can be
drawn in a very nice way: their states form a convex set in the (dual of the)
geometric representation of (W, S). The reason in the affine case is related to a
property of the Shi arrangement, which leads us to discuss a generalization of the
Shi arrangement for any Coxeter system.
Let Φ0 be a reduced, irreducible, crystallographic root system of rank r for a
finite Weyl group W0 in a real vector space V0 with W0 -invariant positive definite
scalar product h·, ·i. Let Φ+
0 be a choice of positive roots, let ∆0 = {α1 , α2 , . . . , αn }

18

C. HOHLWEG, P. NADEAU, AND N. WILLIAMS

Pn
be the corresponding simple roots. The height of a positive root α = i=0 ci αi is
Pn
+
i=0 ci ; for example, the highest root αh in Φ0 has height h − 1, where h is the
Coxeter number of W0 . Define V := V0 ⊕ Rδ and define the set of affine roots to be
Φ := {α + kδ | α ∈ Φ and k ∈ Z}.
The positive affine roots are Φ+ := {α + kδ | α ∈ Φ+
0 and k ≥ 0 ∈ Z} ∪ {α + kδ | α ∈
−Φ+
0 and k > 0 ∈ Z}, and the simple affine roots are ∆ := ∆0 ∪ {α0 }, where
α0 := −αh + δ.
For α ∈ Φ0 and k ∈ Z, we consider in V0 , seen as an affine space, the affine
hyperplane
Hα,k := {x ∈ V0 | hx, αi = k}.
The affine Weyl group W is the group generated by affine reflections in the simple
affine hyperplanes : Hα,0 for α ∈ ∆0 and Hαh ,1 . The fundamental alcove K is the
(interior of the) compact region bounded by the simple affine hyperplanes. The
closure of K is a fundamental domain for the action of W .
The n-Shi arrangement is the collection of hyperplanes

Shin (W ) := Hα,k | α ∈ Φ+ , −n + 1 ≤ k ≤ n .
We abbreviate Shi(W ) := Shi1 (W ), and call it the Shi arrangement2. The roots
corresponding to the hyperplanes in Shin (W ) coincide with the n-small roots, so
that Σn can be thought of as a generalization of the n-Shi arrangement to any
Coxeter group. The crystallographic affine root system Φ is easily and bijectively
convertible to a root system; so the dominance order and n-small roots are welldefined in a crystallographic root system. It particular, the only relations in the
dominance order on Φ+ are α + kδ  α + `δ for α ∈ Φ, k ≤ ` ∈ Z; see [13,
Example 3.9]. We obtain therefore the following proposition.
Proposition 3.16. If (W, S) is of affine type, then
Shin (W ) = {Hα | α ∈ Σn (W )}.
e2 and C
e2 are drawn in Figure 4.
The Shi arrangements for types A
In affine type, the small inversion sets have previously been studied under the
guise of the minimal alcoves of the n-Shi arrangement. More precisely, for W of
affine type, Λn (W ) = {w ∈ W | {w(αs ) | s ∈ DL (w)} ⊆ Σn }. The corresponding
statement for n-low elements and general type is given as [13, Conjecture 2], restated
above in §3.
It turns out that there are (nh + 1)r n-low elements in affine type. The reason
for this is that the inverses of such elements coalesce into an (nh + 1)-fold dilation
of the fundamental alcove.
Theorem 3.17 (J. Y. Shi). Let K be the fundamental alcove for an affine Weyl
group W , and let h be the Coxeter number of the corresponding finite Weyl group
W0 . Then
{w−1 K | w an n-low element} ∼
= (nh + 1)K.

2This was called the sandwich arrangement in [19]

AUTOMATA, REDUCED WORDS AND GARSIDE SHADOWS IN COXETER GROUPS

19

������

���
����

���

��

��

�

�

������

��

�

���

��

�
��

����

����

���

���

��

���

��

�

��

�������

���

�

�

����

����

�

��

�����

��

���

��

���

����

�����

����

�������

Figure 4. A2 and C2 Shi arrangements.
In particular, the alcoves corresponding to the inverses of n-low elements form a
e1 = I2 (∞)
convex set. This theorem is illustrated for the infinite dihedral group A
in Figures 1 and 5, which show the automata built from the 1- and 2-low elements,
e2 and C
e2 , simultaneously
respectively. Figure 6 illustrates this theorem for types A
drawing the automaton.
We note that convexity does not necessarily hold for the subset of alcoves coming
e2 , S̃ =
from the inverses of elements in S̃, as seen for example in Figure 6—for C
Σ \ {s1 s3 s2 }.

��

�

�

�

��

Figure 5. The automaton A1 (I2 (∞), S), drawn using Theorem 3.17.
On the basis of the affine rank three examples, it is tempting to conjecture that
equivalent states are given by intersecting intervals in the weak order with Ln (W ).
The (non-affine) triangle group (5, 3, 5) is a counterexample to this claim.
When the Coxeter system (W, S) is of indefinite type, i.e., W is not finite nor
affine, the isotropic cone Q = {x ∈ V | B(x, x) = 0}, and the region where x ∈ V
verifies Q(x, x) < 0, are nonempty. In this case, following [21, 14], we consider the
projective representation for (W, S) associated to the geometric representation of

20

C. HOHLWEG, P. NADEAU, AND N. WILLIAMS

�������

������

����
����

�����

���

����

���
��

��

�

����

��

��

�

���

�

��

�

��

���

�

���

��

���

��

����

���

�����

����

��

�

�

�

��

����

�������

������

���

��

���

e2 , S) and A0 (C
e2 , S), drawn using Theorem 3.17. A
Figure 6. The automata A0 (A
[green, red, blue] edge represents multiplication by [s1 , s2 , s3 ]. There is one omitted
e2 , S).
(red) edge between 132 and 213 in A0 (C
(W, S), with roots system Φ and simple system ∆ in §2.4. More precisely, since
Φ = Φ+ t Φ− is encoded by the set of positive roots Φ+ , we represent Φ by an
b there is an affine hyperplane V1 in V transverse to Φ+ , i.e., for any
‘affine cut’ Φ:
+
b So Rβ ∩ V1 = {β}
b
β ∈ Φ , the ray R+ β intersects V1 in a unique nonzero point β.
b = {βb | β ∈ Φ} is contained in the
for any β ∈ Φ. The set of normalized roots Φ
b
compact set conv(∆) and therefore admits a set E of accumulation points called
b The group W acts on Φ
b t E ∪ conv(E)
the set of limit roots, which verifies E ∈ Q.
[
componentwise: w · x = w(x).
Now, the role of the affine space V0 for an affine Coxeter system (W, S) with
the tiling obtained by the action of W on the fundamental alcove K is replaced for
indefinite Coxeter systems by a tiling of the imaginary convex body conv(E) by the
projective action of W on the non-empty fundamental region
b | B(x, αs ) ≥ 0, ∀s ∈ S}.
K = {x ∈ conv(∆)
b bounded
Denote Hα = {x ∈ V | B(x, α) = 0}, then K is the region of conv(∆)
by the hyperplanes Hα . This is illustrated in Figure 7 and Figure 8; see also [14,
Figures 2 and 14]. We refer the reader to [14] for more details.
In view of Proposition 3.16, it is natural to give the following definition.
Definition 3.18. Let (W, S) be an indefinite Coxeter system. The n-Shi arrangement of (W, S) is the collection of hyperplanes
Shin (W, S) := {Hα = {x ∈ V | B(x, α) = 0} | α ∈ Σn (W )} .
If [13, Conjecture 2], restated above in §3, is true, it would mean that the set
Ln (W ) of n-low elements parameterized the region of the n-Shi arrangement. Furthermore, each region Shin (W, S) would be have a unique minimal-length region of
the form w · K with w ∈ Ln (W ). Moreover, we observed in numerous cases in rank
3 and 4 the following statement.

AUTOMATA, REDUCED WORDS AND GARSIDE SHADOWS IN COXETER GROUPS

21

Figure 7. The automaton A0 (W, S) for W the triangle group (3, 3, ∞).
Conjecture 3. Let n ∈ N, then the subset
convex body is convex.

S

w∈Ln (W )

w−1 · K of the imaginary

Reasonable evidence for Conjecture 3 is supplied by the fact that Ln (W ) is
closed under taking suffixes. Figure 8 illustrates Conjecture 3 for several rank three
examples.

Figure 8. The regions
and (4, 7, 2).

S

w∈Ln (W )

w−1 · K for the triangle groups (3, 3, 6),(3, 4, 4),

22

C. HOHLWEG, P. NADEAU, AND N. WILLIAMS

Acknowledgments. This work was initiated in LaCIM (Montreal) while Philippe
Nadeau was visiting thanks to a research travel grant from the Laboratoire International Franco-Québécois de Recherche en Combinatoire (LIRCO). The first author
(CH) thanks Christophe Reutenauer for interesting conversations regarding minimality of automata and restriction to standard parabolic subgroups. We thank an
anonymous referee for suggesting that we provide more evidence for Conjectures 1
and 2.

References
[1] A. Björner. Orderings of Coxeter groups. In Combinatorics and algebra (Boulder, Colo.,
1983), volume 34 of Contemp. Math., pages 175–195. Amer. Math. Soc., Providence, RI,
1984.
[2] A. Björner and F. Brenti. Combinatorics of Coxeter Groups, volume 231 of GTM. Springer,
New York, 2005.
[3] B. Brink. The set of dominance-minimal roots. J. Algebra, 206(2):371–412, 1998.
[4] B. Brink and R. Howlett. A finiteness property and an automatic structure for coxeter groups.
Math. Ann., 296:179–190, 1993.
[5] B. Casselman. Computation in Coxeter groups. I. Multiplication. Electron. J. Combin.,
9(1):Research Paper 25, 22 pp. (electronic), 2002.
[6] B. Casselman. Computation in Coxeter groups. II. Constructing minimal roots. Represent.
Theory, 12:260–293, 2008.
[7] W. A. Casselman. Machine calculations in Weyl groups. Invent. Math., 116(1-3):95–108,
1994.
[8] W. A. Casselman. Automata to perform basic calculations in Coxeter groups. In Representations of groups (Banff, AB, 1994), volume 16 of CMS Conf. Proc., pages 35–58. Amer.
Math. Soc., Providence, RI, 1995.
[9] M. Davis, M. Shapiro. Coxeter groups are automatic. Preprint, 1991.
[10] P. Dehornoy, with F. Digne, E. Godelle, D. Krammer, and J. Michel. Foundataions of Garside
theory, volume 22 of EMS Tracts in Mathematics European Mathematical Society (EMS),
Zürich, 2015.
[11] P. Dehornoy, M. Dyer, and C. Hohlweg. Garside families in Artin-Tits monoids and low
elements in Coxeter groups. Comptes Rendus Mathematique, 353:403–408., 2015.
[12] M. J. Dyer. On the weak order of Coxeter groups. 2011. http://arxiv.org/abs/1108.5557.
[13] M. Dyer and C. Hohlweg. Small roots, low elements, and the weak order in Coxeter groups.
ArXiv e-prints, May 2015.
[14] M. Dyer, C. Hohlweg, and V. Ripoll. Imaginary cones and limit roots of infinite Coxeter
groups. http://arxiv.org/abs/1303.6710, Mar. 2013.
[15] T. Edgar. Dominance and regularity in coxeter groups. PhD Thesis, University of Notre
Dame, 2009. http://etd.nd.edu/ETD-db/.
[16] D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson, and W. P.
Thurston. Word processing in groups. Jones and Bartlett Publishers, Boston, MA, 1992.
[17] H. Eriksson. Computational and combinatorial aspects of Coxeter groups. ProQuest LLC,
Ann Arbor, MI, 1994. Thesis (Takn.dr)–Kungliga Tekniska Hogskolan (Sweden).
[18] X. Fu. The dominance hierarchy in root systems of Coxeter groups. J. Algebra, 366:187–204,
2012.
[19] P. Headley. Reduced expressions in infinite Coxeter groups. UMI, Ann Arbor, MI, 1994.
Thesis–University of Michigan.
[20] C. Hohlweg and J.-P. Labbé. On Inversion Sets and the Weak Order in Coxeter Groups.
http://arxiv.org/abs/1502.06926, 2015.
[21] C. Hohlweg, J.-P. Labbé, and V. Ripoll. Asymptotical behaviour of roots of infinite Coxeter
groups. Canad. J. Math., 66:323–353, 2014.
[22] J. E. Humphreys. Reflection groups and Coxeter groups, volume 29. Cambridge University
Press, Cambridge, 1990.
[S+ 09] SageMath, the Sage Mathematics Software System (Version x.y.z), The Sage Developers,
YYYY, http://www.sagemath.org.

AUTOMATA, REDUCED WORDS AND GARSIDE SHADOWS IN COXETER GROUPS

23

[23] The Sage-Combinat community, Sage-Combinat: enhancing Sage as a toolbox for computer
exploration in algebraic combinatorics, http://combinat.sagemath.org, 2008.
[24] J. Y. Shi. The Kazhdan-Lusztig cells in certain affine Weyl groups, volume 1179 of Lecture
Notes in Mathematics. Springer-Verlag, Berlin, 1986.
[25] J. Sakarovitch. Elements of automata theory, Translated from the 2003 French original by
Reuben Thomas. Cambridge University Press, Cambridge, 2009.
[26] J.-Y. Shi. The reduced expressions in a Coxeter system with a strictly complete Coxeter
graph. Adv. Math., 272:579–597, 2015.
(Christophe Hohlweg) Université du Québec à Montréal, LaCIM et Département de
Mathématiques, CP 8888 Succ. Centre-Ville, Montréal, Québec, H3C 3P8, Canada
E-mail address: hohlweg.christophe@uqam.ca
URL: http://hohlweg.math.uqam.ca
(Philippe Nadeau) CNRS & Institut Camille Jordan, Université Claude Bernard Lyon
1, 69622 Villeurbanne Cedex, France
E-mail address: nadeau@math.univ-lyon1.fr
URL: http://math.univ-lyon1.fr/~nadeau
(Nathan Williams) Université du Québec à Montréal, LaCIM, CP 8888 Succ. CentreVille, Montréal, Québec, H3C 3P8, Canada
E-mail address: nathan.f.williams@gmail.com
URL: http://thales.math.uqam.ca/~nwilliams/

