DUAL GARSIDE STRUCTURES AND COXETER SORTABLE
ELEMENTS

arXiv:1802.05418v1 [math.GR] 15 Feb 2018

THOMAS GOBET

Abstract. In Artin-Tits groups attached to Coxeter groups of spherical type,
we give a combinatorial formula to express the simple elements of the dual braid
monoids in the classical Artin generators. Every simple dual braid is obtained
by lifting an S-reduced expression of its image in the Coxeter group, in a way
which involves Reading’s c-sortable elements. It has as an immediate consequence that simple dual braids are Mikado braids (the known proofs of this
result either require topological realizations of the Artin groups or categorification techniques), and hence that their images in the Iwahori-Hecke algebras
have positivity properties. In the classical types, this requires to give an explicit description of the inverse of Reading’s bijection from c-sortable elements
to noncrossing partitions of a Coxeter element c, which might be of independent interest. The bijections are described in terms of the noncrossing partition
models in these types. While the proof of the formula is case-by-case, it is entirely combinatorial and we develop an approach which reduces a uniform proof
to uniformly proving a lemma about inversion sets of c-sortable elements.

Contents
1. Introduction
2. Coxeter groups and Coxeter elements
2.1. Coxeter groups and Artin groups
2.2. Coxeter elements and absolute order
2.3. Parabolic and reflection subgroups
2.4. Noncrossing partitions
3. Dual braid monoids
4. Coxeter sortable elements
5. Mikado braids and a closed formula for simple dual braids
5.1. Mikado braids
5.2. Simple dual braids are Mikado braids
5.3. A closed formula for simple dual braids
5.4. Proof of the main theorem
6. Bijections between noncrossing partitions and c-sortable elements
6.1. Type An
6.2. Type Bn
6.3. Type Dn
6.4. Type I2 (m)
6.5. Types E, F, H
7. Questions
References
1

2
4
4
5
6
7
8
10
11
11
13
13
15
16
16
20
21
33
34
34
34

2

THOMAS GOBET

1. Introduction
Dual braid monoids provide a Garside structure on braid groups of finite reflection groups, and are therefore central for instance in the study of the word problem
in generalized braid groups of complex reflection groups. They were introduced
by Birman, Ko and Lee [10] in type An , Bessis, Digne and Michel [8] in type Bn ,
and Bessis [5] for the remaining finite real reflection groups as well as for complex
reflection groups [7]. They give rise to a so-called dual approach for the study of
both reflection groups and their braid groups. In this paper, we are interested in
the dual braid monoids attached to finite real reflection groups.
The dual approach consists in the study of a real reflection group viewed as
a group generated by the set T of all its reflections, instead of just the set S
of reflections corresponding to the walls of a chamber. It gives rise to a rich
combinatorics involving the noncrossing partition lattices. More precisely, every
Garside monoid comes equipped with a finite set of simple elements, which may
be defined as the (left) divisors of the Garside element, and form a lattice under
left-divisibility in the monoid (for basics on Garside theory we refer the reader to
[21]). In the classical setting, i.e., when the generating set of the reflection group
W is a simple system S, this lattice is isomorphic to the lattice given by ordering
W by the (left) weak Bruhat order. In the dual setting, a choice of standard
Coxeter element c in W is required, and the set of simples is in bijection with a
subset NC(W, c) of W associated with that choice of standard Coxeter element;
the lattice structure on NC(W, c) coming from the lattice of simples is isomorphic
to the lattice of noncrossing partitions of a Coxeter element c [5]. This gives rise
to combinatorial models for the study of the simples and, more generally, of the
braid groups defined by their dual presentation. We call the simples of the dual
Garside structure the simple dual braids.
Denote by B(W ) the braid group associated with the finite Coxeter group
(W, S). The dual braid monoid Bc∗ associated with a choice c of Coxeter element embeds into its group of (left) fractions, which is isomorphic to B(W ). One
of the difficulties of the dual approach is that it is hard in general to express the
generators of Bc∗ (in bijection with T ) or the simples (in bijection with NC(W, c))
inside B(W ) in terms of the classical Artin generators. Indeed, generators of Bc∗
corresponding to simple reflections are sent to the corresponding Artin generators,
but for other reflections there is no immediate description. In [19, Proposition
3.13], Digne and the author gave a formula to express the dual generators in the
classical ones, but it does not give a braid word of smallest possible length in general. The aim of this paper is to give a combinatorial formula to express all the
simples of Bc∗ , not only the reflections, in the classical generators of B(W ) (see
Theorem 5.10 below). The formula for the simple xc associated to x ∈ NC(W, c)
is given by lifting any S-reduced expression of x, where each generator s in the reduced expression is replaced either by the corresponding Artin generator of B(W )
or its inverse, following a rule involving c-sortable elements. As an immediate consequence, the length of xc in B(W ) is equal to the length of x in W with respect
to S, in particular the braid word which we obtain for xc is of smallest possible
length (in fact, this shows that the length of xc in B(W ) is equal to the length of
x in W ).
The formula we give here is uniform and involves Reading’s c-sortable elements
(see [36]). To the best of our knowledge, this is the first application of these objects
to the study of braid groups. There are several motivations for giving a formula

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

3

to express the simple dual braids in the classical generating set: as we explain
below, the formula has as an immediate consequence that simple dual braids are
Mikado braids. This result was conjectured in a joint work with Digne [19], where
it was proven for every irreducible W except in type Dn . Type Dn was proven in a
joint work with Baumeister [4] and independently, Licata and Queffelec [34] proved
it in types An , Dn and En . The proofs there use either topological realizations
of the braid groups (i.e., in terms of Artin braids) or categorification techniques.
There are indeed indications that Mikado braids play an important role in the
categorifications of the braid groups (see [28], [34]). Another motivation consists
of searching for a construction of the dual braid monoids which would avoid using
the classification. In this perspective, a uniform proof of Lemma 4.6 of this paper
would be of interest since the formula which we give is case-free, but its proof relies
on Lemma 4.6 whose proof uses the classification. Finally, there are computational
motivations: the formula which we give allows one to compute a simple expressed
in the classical Artin generators much quicker than with the known approaches
(see Section 3 below).
Reading defined and studied c-sortable elements in the framework of what is
nowadays called the Coxeter-Catalan combinatorics. Coxeter sortable elements
form a combinatorially defined subset of W (attached to a choice of standard
Coxeter element c), which is in bijection with the set NC(W, c) of noncrossing
partitions of c and with c-clusters; they were indeed introduced to construct a
bijection between the set NC(W, c) and the set of c-clusters. Their definition allows
a natural and powerful way of arguing by induction, sometimes called Cambrian
recurrence (see Lemmatas 4.3 and 4.4 below). Such a procedure allows one to
prove results concerning noncrossing partitions for all standard Coxeter elements
simultaneously, which is difficult to perform if we stay in the world of noncrossing
partitions. This strategy is used to prove the main result (Theorem 5.10 below).
Let Read denote Reading’s bijection between c-sortable elements and c-noncrossing
partitions.
Mikado braids were defined (in spherical type) in [19] but they already appeared
before in the work of Dyer [24] and Dehornoy [20]. In spherical type, a Mikado
braid can be defined as a quotient of two simple elements of the classical Garside
structure, that is, two positive lifts of the elements of W in B(W ). The optimal
definition is the one appearing in work of Dyer [24, Section 9.1], which associates
a Mikado braid to two elements x, y of W (at least if W is finite): a Mikado braid
xN (y) is obtained by lifting any S-reduced expression s1 s2 · · · sk of x to the element
sε11 sε22 · · · sεkk ∈ B(W ),
where si is the classical Artin generator of B(W ) associated with si and εi ∈ {±1};
the rule to decide whether εi = 1 or −1 involves the inversion set N (y) of the
element y (see Section 5 for a precise definition). The element y is not unique in
general, that is, we may have xN (y) = xN (y′ ) for y 6= y ′ ∈ W . For infinite groups
one replaces inversion sets N (y) by biclosed sets of positive roots (which turn out
to be exactly inversion sets in the case where W is finite). Also note that by
definition, Mikado braids have the same length in the braid groups (with respect
to the generating set given by the Artin generators and their inverses) as their
images in the Coxeter group (with respect to S).
As explained above, simple dual braids were conjectured and then proven to
be Mikado braids, but in an indirect way: if x ∈ NC(W, c) and xc ∈ Bc∗ ⊆ B(W )
denotes the corresponding simple dual braid, then we have xc = xN (y) for some y ∈

4

THOMAS GOBET

W there is no hint of what "the" (or "a such") y could be (but rather algorithms
to find a possible y, which rely on the topological models for the Artin groups in
the classical types; see for instance [19, Proposition 5.7]). Our formula provides
an answer to that question:
Theorem 5.10 (Expressing simple dual braids in the classical generators). Let c
be a standard Coxeter element. Let x ∈ NC(W, c), let y := x−1 c (which also lies
in NC(W, c)). Then
xc = xRead−1 (y) .
The bijection Read is defined uniformly, hence the statement of the Theorem
does not require the classification of finite Coxeter groups. Unfortunately, it seems
that there is no explicit uniform description of its inverse Read−1 in the literature.
In Section 6 below, we provide a combinatorial description of Read−1 in the classical
types in terms of noncrossing partitions. These descriptions, which might be of
independent interest, are required to prove the following combinatorial Lemma
about c-sortable elements. The proof of it is the only one where we need to use
the classification:
Lemma 4.6. Let c be a standard Coxeter element. Let x ∈ NC(W, c), y := x−1 c.
Let s be initial in c, that is, ℓ(sc) < ℓ(c). Then
x−1 sx lies in N (y) if and only if it lies in N (Read−1 (y)).
It would be interesting to extend these results to the affine Coxeter groups of
en and C
en for the choices of Coxeter element for which there is a dual braid
type A
monoid (see [17],[18]). In these cases it is not known whether simple dual braids
are Mikado braids.
Mikado braids have interesting homological properties in the categorical incarnations of the braid groups (see [28], [34]). For instance, the fact that they lie
in the heart of the canonical t-structure on the bounded homotopy category of
Soergel bimodules can be used to derive positivity properties of their images in
the Iwahori-Hecke algebra of the Coxeter system (see Section 5.1 below for more
details). Combining this fact with the fact that simple dual braids are Mikado
braids, we obtain that the images of simple dual braids in the Hecke algebra have
positivity properties. In type An , these images yield a basis of the Temperley-Lieb
quotient of the Hecke algebra (see [27]).
Acknowledgements. The author thanks Anthony Henderson, Christophe Hohlweg,
Ivan Marin, Nathan Reading, Christian Stump and Nathan Williams for useful
discussions. He thanks François Digne and Jean Michel for providing computer
programs to check Lemma 4.6 in the exceptional types. This paper was written
in part when the author was funded by the ANR Geolie (project ANR-15-CE400012) at the Université de Lorraine in Nancy, and finalized while being supported
by an Australian Research Council (ARC) grant (grant number DP170101579) at
the University of Sydney. He thanks both organizations for their financial support.
2. Coxeter groups and Coxeter elements
2.1. Coxeter groups and Artin groups. A Coxeter system (W, S) is a group
W generated by a finite set S of elements satisfying s2 = e for every s ∈ S, subject
to additional braid relations: given s, t ∈ S, s 6= t, the braid relation of length
ms,t = mt,s ∈ {2, 3, . . . } ∪ {∞} between s and t is the relation st · · · = ts · · · ,

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

5

where st · · · (resp; ts · · · ) is the strictly alternating product of s and t with ms,t
factors and beginning by s (resp. by t). If ms,t = ∞ then no relation between
s and t is imposed. We denote by ℓ : W −→ Z≥0 the length function with
respect to
set S of W and by ≤ the Bruhat order on W . The
S the generating
−1
set T = w∈W wSw is the set of reflections in W . A Coxeter group (W, S) is
·

reducible if there is a nontrivial partition S = S1 ∪ S2 such that W = hS1 i × hS2 i
(it is a general fact that every subgroup WI generated by a subset I ⊆ S, or
even every subgroup W ′ ⊆ W generated by a set of reflections, is again a Coxeter
group; see [23]). Otherwise it is irreducible. Every Coxeter group is isomorphic to
a finite direct product of irreducible ones, in an essentially unique way. For more
on Coxeter groups we refer the reader to [12] or [32].
Finite irreducible Coxeter groups are classified in four infinite families (An ,
n ≥ 3), (Bn , n ≥ 3), (Dn , n ≥ 4), (I2 (m), m ≥ 5) and six exceptional groups E6 ,
E7 , E8 , F4 , H3 , H4 .
Given a (not necessarily finite) Coxeter system (W, S), on defines the Artin-Tits
group B(W ) attached to (W, S) as the group generated by a copy S = {s | s ∈ S}
of S, whose elements are only subject to the braid relations of W . That is, the
only relations are
st
· ·}· = ts
· ·}· ,
| {z
| {z
ms,t factors

ms,t factors

for all s, t ∈ S. As this presentation is positive, let B(W )+ denote the monoid
generated by the same presentation as B(W ). It is a general fact that B(W )+ ⊆
B(W ) (see [35], [33]). If W is finite, the group B(W ) (or W ) is said to be of
spherical type.
When W is finite, B(W )+ is a Garside monoid (see [21]), implying that B(W )
can be realized as the group of (left) fractions of B(W )+ . Garside structures are
central in the study of the word problem in braid groups. They provide normal
forms for the elements of B(W )+ , which can be used to define (and compute)
normal forms for the elements of B(W ). Garside structures are not unique in
general; in Section 3 below, we recall the definition of the dual braid monoids,
which provide alternative Garside structures on B(W ). We do not introduce all
the machinery of Garside monoids here since our purposes can be achieved without
it, but rather refer the reader to [21] for more on the topic.
For x ∈ W , define the positive lift x ∈ B(W ) of x as follows: choose a reduced expression s1 s2 · · · sk of x and set x := s1 s2 · · · sk . Since any two reduced
expressions of x can be related by a sequence of braid relations, the element x is
well-defined. If W is finite, in the Garside-theoretic language, the set {x | x ∈ W }
is the set of simple elements or simples of the classical braid monoid B(W )+ , that
is, the set of divisors of the Garside element ∆ (which is equal to w0 , where w0 is
the longest element of W ).
2.2. Coxeter elements and absolute order. In this section, we recall the definition and properties of Coxeter elements, absolute order and reflection subgroups.
The first definition below is borrowed from [2]:
Definition
2.1 (Coxeter elements). Let (W, S) be a Coxeter system. Let T =
S
−1 denote the set of reflections in W .
wSw
w∈W
(1) An element c ∈ W is a Coxeter element if there exists
S ′ = {s1 , . . . , sn } ⊆ T

6

THOMAS GOBET

such that c = s1 s2 · · · sn and S ′ is a simple system for W (i.e., (W, S ′ ) is a
Coxeter system). We denote by Cox(W, S) the set of Coxeter elements in
W.
(2) An element c ∈ W is a standard Coxeter element if it is the product of
all the elements of S in some order. We denote by Std(W, S) the set of
standard Coxeter elements in W . It is clear that Std(W, S) ⊆ Cox(W, S).
Remark 2.2. The first definition above might look independent of S, but it
does not just depend on W as abstract group: one requires to have fixed the
set of reflections T for W , and since the set T cannot be obtained just from the
abstract group W (that is, there are Coxeter groups W, W ′ which are isomorphic
as abstract groups, but not as Coxeter groups; see for instance [3, Section 2.3]
and the references therein), the easiest way to do it is to fix a simple system S
for W and define T as the set of conjugates of the elements of S as we did above.
Note that if S ′ ⊆ T is a simple system for W , then Cox(W, S) = Cox(W, S ′ ) (as an
immediate consequence of [15, Lemma 3.7]).
Every Coxeter element c = s1 s2 · · · sn has reflection length equal to n = |S|;
this can be seen for instance using the main result of [25].
Definition 2.3 (Absolute order). The absolute order ≤T on W is defined by
u ≤T v if and only if
ℓT (u) + ℓT (u−1 v) = ℓT (v),
where ℓT : W −→ Z≥0 is the length function with respect to the generating set T
of W and u, v ∈ W . We denote by RedT (u) the set of T -reduced expressions of u.
Definition
S 2.4 (Parabolic Coxeter elements). Let (W, S) be a Coxeter system.
Let T = w∈W wSw−1 be the set of reflections of W .
(1) An element w ∈ W is a parabolic Coxeter element if it exists a simple system S ′ = {s1 , s2 , . . . , sn } ⊆ T for W and m ≤ n such that w = s1 s2 · · · sm .
(2) An element w ∈ W is a prefix of a Coxeter element c ∈ Cox(W, S) if w ≤T c.
Remark 2.5. A parabolic Coxeter element is always a prefix of a Coxeter element
since in the notations of (1) above, we have s1 s2 · · · sm ≤T s1 s2 · · · sn . However the
converse is false in general (see for instance [31, Example 5.7]), but it holds if W
is finite (see [19, Corollary 3.6]).
2.3. Parabolic and reflection subgroups.
Definition 2.6 (Parabolic subgroup). A reflection subgroup W ′ ⊆ W is parabolic
if W ′ = hs1 , s2 , . . . , sm i, where s1 , . . . , sm is as in Definition 2.4 (1). That is,
if there is a set of reflections generating W ′ which can be extended to a simple
system S ′ for W . There is a more classical definition as follows: let I ⊆ S. Then
WI := hs | s ∈ Ii is a standard parabolic subgroup, and any conjugate of such a
group is a parabolic subgroup. The equivalence of the two definitions is false in
general (see [29, Example 2.2] for a counterexample), but it holds for finite groups
(and for a large family of infinite Coxeter groups called 2-spherical; see [3, Section
4]).
As mentioned above, every reflection subgroup W ′ ⊆ W of a Coxeter system
(W, S) is again a Coxeter group (see [23]). It comes equipped with a canonical set
of generators as a Coxeter group, which is defined as follows. Given y ∈ W , define
N (y) := {t ∈ T | ℓ(ty) < ℓ(y)}.

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

7

The elements of N (y) are the (left) inversions of y ∈ W and we have |N (y)| = ℓ(y).
Given a reflection subgroup W ′ ⊆ W , its canonical set of Coxeter generators is
given by (see [23, Theorem 3.3])
S ′ := {t ∈ W ′ ∩ T | N (t) ∩ W ′ = {t}}.
Morevoer, the reflections of W ′ (viewed as a Coxeter group) coincide with W ′ ∩ T .
Assume that (W, S) is finite. Let V be the geometric representation of (W, S).
Recall that it is a faithful representation V of W , preserving a symmetric bilinear
form (·, ·), in such a way that the elements of T act on V by geometric reflections
(see [32, Section 5.3]). To every t ∈ T corresponds a root αt ∈ V . Given x ∈ W we
denote by V x the set of fixed points of V by x. There is the following well-known
characterization of parabolic subgroups:
Proposition 2.7. Let (W, S) be a finite Coxeter system. A subgroup W ′ ⊆ W is
parabolic if and only if there is a subset E ⊆ V such that
W ′ = CW (E) := {w ∈ W | w(v) = v ∀v ∈ E}.
The subsets E can be chosen to be intersections of reflecting hyperplanes.
Remark 2.8. Note that in particular, if W is finite, then P (x) = CW (V x ) for all
x ∈ W.
Definition 2.9 (Parabolic closure). Let (W, S) be a finite Coxeter system. Let
x ∈ W . The parabolic closure P (x) of x is the smallest parabolic subgroup of
W containing x. This is well-defined since parabolic subgroups of finite Coxeter
groups are known to be stable by intersection (for infinite Coxeter groups, this is
true with the classical definition, but open with the definition of parabolic subgroups which we chose to use in this paper).
2.4. Noncrossing partitions. From now on, we assume (W, S) to be finite.
Definition 2.10 (Noncrossing partitions). For c ∈ Cox(W, S), we set
NC(W, c) := {x ∈ W | x ≤T c}
and call the elements of this set the c-noncrossing partitions.
The reason for calling these elements noncrossing partitions comes from the
fact that in type An , the poset (NC(W, c), ≤T ) is isomorphic to the lattice of
noncrossing partitions of the cycle c ordered by refinement (see [9] or Section 6.1.1
below). In general we have:
Theorem 2.11 (Bessis [5], Brady and Watt [13], Reading [37]). The partially
ordered set (NC(W, c), ≤T ) is a lattice.
If W is finite, then (NC(W, c), ≤T ) ∼
= (NC(W, c′ ), ≤T ) for all c, c′ ∈ Cox(W, S)
′
(if c and c are conjugate this is clear, but with the definition of Coxeter elements
which we adopted for this paper two Coxeter elements might not be conjugate.
One nevertheless still has the isomorphism of posets of noncrossing partitions,
see [39]).
The following result is due to Carter [16]:
Theorem 2.12 (Carter [16]). Let u, v ∈ W . Let u = t1 t2 · · · tk be an expression
of u in the generating set T of W .
(1) The expression t1 t2 · · · tk is T -reduced (i.e., k = ℓT (u)) if and only if the
roots αt1 , αt2 , . . . , αtk ∈ V are linearly independent. In this case, the reflection subgroup ht1 , t2 , . . . , tk i of W has rank k,

8

THOMAS GOBET

(2) We have ℓT (u) = dim V − dim V u = codim(V u ),
(3) We have u ≤T v ⇒ V v ⊆ V u ,
(4) If t ∈ T , then V v ⊆ V t ⇔ t ≤T v.
Note that V t is the reflecting hyperplane Ht of t. In general, the inclusion
V ⊆ V u for u, v ∈ T does not imply that u ≤T v: for instance, Coxeter elements
always have a trivial set of fixpoints, but there are element failing to be below a
given Coxeter element for the absolute order in general. The first statement in the
above Theorem is sometimes called “Carter’s Lemma”.
We recall some well-known facts about parabolic subgroups associated to noncrossing partitions. Parabolic subgroups can also be described as centralizers of
subspaces in the geometric representation V as recalled in Proposition 2.7 above.
One can associate to every x ∈ NC(W, c) its parabolic closure P (x). Below, we
show that it can also be defined as
v

P (x) = ht ∈ T | t ≤T xi
and that given x, y ∈ NC(W, c), we have x ≤T y if and only if P (x) ⊆ P (y).
Indeed, let w ∈ ht ∈ T | t ≤T xi. By point (3) of the Theorem above, we
have that V x ⊆ V w , implying that w ∈ CW (V x ). Conversely, let w ∈ CW (V x ).
Let t1 t2 · · · tk be a T -reduced decomposition of w. We have ti ≤T w for all i,
implying by point (3) of the above Theorem again that V x ⊆ V w ⊆ V ti for all
i. Using point (4) we get that ti ≤T x for all i, hence that ti ∈ ht ∈ T | t ≤T xi
for all i, which implies that w itself lies in ht ∈ T | t ≤T xi. This shows that
ht ∈ T | t ≤T xi = CW (V x ) = P (x). Now assume that x ≤T y. Then by point (2)
above we have V y ⊆ V x , hence P (x) = CW (V x ) ⊆ CW (V y ) = P (y). The converse
follows by the main result of [14].
Remark 2.13. By Theorem 2.12 (2), each Coxeter element has a trivial set of
fixed points in V . By point (4) of the same Theorem it implies that T ⊆ NC(W, c)
for all c ∈ Cox(W, S).
3. Dual braid monoids
Dual braid monoids provide alternative Garside structures on Artin-Tits groups
of spherical type. More precisely, a dual braid monoid attached to a finite Coxeter
group embeds into the corresponding Artin-Tits group and is isomorphic to its
group of (left) fraction. It was initially introduced by Birman, Ko and Lee [10]
in type An , by Bessis, Digne and Michel [8] in type Bn and by Bessis [5] for all
finite Coxeter groups. The idea is to take as generating set for W (resp. for the
dual braid monoid) the set T (resp. a copy of the set T ) of reflections. A choice
of standard Coxeter element c ∈ Std(W, S) is required to define the dual braid
monoid. We recall that all Coxeter systems are assumed to be finite.
We recall from Remark 2.13 that T ⊆ NC(W, c) for all c ∈ Cox(W, S).
Definition 3.1 (Dual braid monoid). Let c ∈ Std(W, S). The dual braid monoid
Bc∗ associated to W and c is defined by
Bc∗ := htc ∈ Tc | tc t′c = (tt′ t)c tc if tt′ ∈ NC(W, c)i.
We recall some properties of dual braid monoids; the reader is referred to [5] or
[19, Section 3] for more details and proofs. The monoid Bc∗ is a Garside monoid
with group of (left) fractions isomorphic to B(W ), in particular it embeds into
B(W ). The embedding ι : Bc∗ ֒→ B(W ) is hard to describe combinatorially; for
each s ∈ S we have ι(sc ) = s, but in the case where t ∈ T \S, there is no immediate

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

9

way to express ι(tc ) in the generators S ∪ S−1 of B(W ). One way it achieve this
purpose is to use the dual braid relations inductively. For instance, if W has type
A2 with Coxeter element c = s1 s2 , then we have (s1 )c (s2 )c = (s1 s2 s1 )c (s1 )c , hence
ι((s1 s2 s1 )c ) = s1 s2 s−1
1 . Another way is given by Proposition 3.2 below.
While noncrossing partitions can be defined for an arbitrary Coxeter element,
for dual braid monoids the Coxeter element is required to be standard (see [19,
Remark 5.11]). The set of simple elements or simples Div(c) of Bc∗ is in oneto-one correspondence with NC(W, c). If is defined as the set of elements in Bc∗
which (left-)divide the lift cc = (s1 )c (s2 )c · · · (sn )c of the Coxeter element c =
s1 s2 · · · sn . The element xc corresponding to x is built as follows: given a T reduced expression t1 t2 · · · tk of x, the element (t1 )c (t2 )c · · · (tk )c turns out to be
independent of the chosen T -reduced expression, and we denote it by xc (this
follows from the transitivity of the Hurwitz action on the reduced decompositions
of parabolic Coxeter elements, see [5]). We abuse notation and simply write xc
instead of ι(xc ). We want to find an efficient way of expressing xc in the classical
Artin generators of B(W ). For generators of Bc∗ , it can be done in the following
way [19, Proposition 3.13]:
Proposition 3.2. Let c = s1 s2 · · · sn ∈ Std(W, S). We have
−1 −1
Tc = {s1 s2 · · · si si+1 s−1
i · · · s2 s1 | 0 ≤ i ≤ 2|T |},

where the indices are taken modulo n.
However this does not give braid words of smallest possible length in general.
We prove a few Lemmatas which will be useful later on. Most of them are
well-known, but we provide proofs for completeness.
Lemma 3.3. Let I ⊆ S. Let c ∈ Std(W, S) and let cI denote the restriction of
c to the standard parabolic subgroup WI := hs | s ∈ Ii (obtained by deleting the
letters in a reduced expression of c which are not in I). Note that we have cI ≤T c.
(1) There is an embedding Bc∗I ⊆ Bc∗ induced by tcI 7→ tc , t ∈ T ∩ WI .
(2) Let x ∈ NC(WI , cI ) ⊆ NC(W, c). Then xc = xcI .
Proof. Since dual braid relations in Bc∗I are dual braid relations in Bc∗ (because
cI ≤T c), there is a map ϕI : Bc∗I −→ Bc∗ .
The reflection length of x in WI is equal to its reflection length in W and the
reflections in WI are given by TI := T ∩ WI . By Theorem 2.12, we have that every
T -reduced decomposition of x has all its reflections in WI . To show the second
part, it therefore suffices to show that for t ∈ TI , we have tcI = tc . This is true for
simple reflections, implying that
(cI )cI = (cI )c .
We have t ≤T cI by Remark 2.13, hence the result follows by the above equality and
the transitivity of the Hurwitz action on RedTI (cI ) (and its lift in the dual braid
monoid; see [19, Theorem 3.10, Corollary 3.12]): tcI can be obtained by a successive
application of dual braid relations to the reduced decomposition (s1 )c (s2 )c · · · (sk )c
of (cI )cI = (cI )c , which can be performed either in Bc∗I or in Bc∗ . This shows the
second part. It also shows that the composition
Bc∗I ֒→ B(WI ) ֒→ B(W )
is equal to the composition of ϕI with the embedding Bc∗ ֒→ B(W ), proving the
first claim.


10

THOMAS GOBET

Lemma 3.4. Let c ∈ Std(W, S) and let s ∈ S be initial in c (that is, c has an Sreduced expression beginning by s). Let x ∈ NC(W, c). Note that sxs ∈ NC(W, scs).
Then
(sxs)scs = s−1 xc s.
Proof. Again, it suffices to show the result in the case where x ∈ T . If x ∈ S, then
the claim is true: if x = s it is clear, while if x = s′ 6= s, we have that s appears
after s′ in scs since s is final in scs, hence that s′ s ≤T scs, implying that we have
a dual braid relation
(s′ )scs sscs = sscs (ss′ s)scs ,
and hence
(sxs)scs = (ss′ s)scs = s−1 s′ s = s−1 xc s.
The result for all t ∈ T follows by Hurwitz transitivity.



4. Coxeter sortable elements
From now on, unless explicitly stated otherwise, we will always assume (W, S)
to be finite. We recall from [36] the definition and basic properties of c-sortable elements. Fix an S-reduced decomposition s1 s2 · · · sn of a standard Coxeter element
c ∈ Std(W, S). Consider the semi-infinite word
c∞ = s1 s2 · · · sn |s1 s2 · · · sn |s1 s2 · · · sn | · · · .
Let w ∈ W . The c-sorting word for w is the lexicographically first S-reduced
expression of w appearing as a subword of c∞ . We write w = w1 w2 · · · wk , where
wi is the subword of the c-sorting word for w coming from the i-th copy of c in c∞
and k is maximal such that this subword is nonempty. Note that each wi defines
a subset of S, consisting of the letters in the word wi . We abuse notation and also
denote this set by wi .
Definition 4.1 (Coxeter sortable elements). We say that w is c-sortable if wk ⊆
wk−1 ⊆ · · · ⊆ w2 ⊆ w1 .
Example 4.2. Let W be of type A3 , S = {s1 , s2 , s3 } with s1 s3 = s3 s1 . Let
c = s3 s1 s2 . Then w = s3 s1 s2 |s3 s1 is c-sortable, with w1 = s3 s1 s2 , w2 = s3 s1 ⊆ w1 .
The element s2 s1 is not c-sortable since if it was, we would have s2 s1 = w1 , but
in c the letter s1 appears before s2 (and they do not commute).
We denote by Sortc (W ) the set of c-sortable elements. It is independent of the
reduced expression of the Coxeter element c which was chosen (any two reduced
expressions of c are related by commutation of letters, and the same holds for the
c-sorting words). We say that a simple reflection s ∈ S is initial in c if c has an
S-reduced expression beginning by s.
The following two Lemmatas, which are immediate consequences of the definition of c-sortable elements, are crucial in the theory of c-sortable elements. For
s ∈ S, we denote by W<s> the maximal parabolic subgroup of W generated by
S\{s}.
Lemma 4.3. Let s be initial in c. Let w ∈ W be such that ℓ(sw) > ℓ(w). Then
w ∈ Sortc (W ) ⇔ w ∈ Sortsc (W<s> ).
Lemma 4.4. the s Let s be initial in c. Let w ∈ W be such that ℓ(sw) < ℓ(w).
Then w ∈ Sortc (W ) ⇔ sw ∈ Sortscs (W ).

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

11

The two above Lemmatas allow one to argue by induction on the rank of W
and the length of c-sortable elements (without fixing a Coxeter element).
Reading defined a bijection Read : Sortc (W ) −→ NC(W, c) as follows. Consider
the c-sorting word si1 · · · siℓ for w. Put a total order on N (w) such that the j-th
element is si1 si2 · · · sij sij−1 · · · si1 . Set DR (w) := {s ∈ S | ℓ(ws) < ℓ(w)} and
Cov(w) := {wsw−1 | s ∈ DR (w)} ⊆ N (w).
The elements of Cov(w) are the cover reflections of w. Order the elements of
Cov(w) with respect to the total order on N (w) defined above, say t1 , . . . , tk , and
define an element x ∈ W as the product t1 t2 · · · tk .
Theorem 4.5 (Reading [36]). With the above notations, the assignment w 7→
x := Read(w) defines a bijection Sortc (W ) −→ NC(W, c). The word t1 t2 · · · tk is
T -reduced and {t1 , t2 , . . . , tk } is the set of canonical generators of the parabolic
subgroup P (x) ⊆ W .
We denote by Sc : NC(W, c) −→ Sortc (W ) the map which is the inverse of
the bijection Read. In Section 6, we will give an explicit description of Sc in the
classical types, using the combinatorial models of noncrossing partitions.
The following Lemma is the part which requires a case-by-case investigation.
The proof is postponed to Section 6:
Lemma 4.6. Let W be a finite Coxeter group, c ∈ W a Coxeter element and
s ∈ S be initial in c. Let x ∈ NC(W, c), y := x−1 c. Then
x−1 sx ∈ N (y) ⇔ x−1 sx ∈ N (Sc (y)).
Remark 4.7. Note that in the assumptions of the Lemma, we have x−1 sx ∈ N (y)
if and only if s ∈
/ N (x); indeed, since s is initial in c we have
s ∈ N (c) = N (xy) = N (x) + xN (y)x−1 ,
where + denotes symmetric difference.
5. Mikado braids and a closed formula for simple dual braids
The aim of this section is to prove the main result, namely Theorem 5.10,
assuming Lemma 4.6 (which will be proven by a case-by-case analysis in Section 6).
We begin by recalling the definition and properties of Mikado braids.
5.1. Mikado braids. Mikado braids appeared in work of Dehornoy [20] in type
An and in unpublished work of Dyer [24] for abritrary Coxeter groups. A detailed
study was initiated in [19], [28]. Mikado braids are elements of an Artin-Tits group
attached to an arbitrary Coxeter group. In this paper, we recall that we restrict
to the spherical type, where the definition is easier and has several equivalent
formulations (for a general definition see [28, Definition 3.5])
Lemma 5.1 (Dyer [24]). Let W be a finite Coxeter group. Let B(W ) be the
corresponding Artin-Tits group. Let x, y ∈ W . Define an element xN (y) of B(W )
as follows: choose a reduced expression s1 s2 · · · sk of x and set
xN (y) = sε11 sε22 · · · sεkk ,
where εi = −1 if sk sk−1 · · · si si+1 · · · sk−1 sk ∈ N (y) and εi = 1 otherwise. Then
xN (y) is well-defined.

12

THOMAS GOBET

For arbitrary W , the set N (y) in the above definition is replaced by any biclosed
set of roots (these sets are precisely inversion sets when the group is finite. In
general there are many more biclosed sets than inversion sets).
Definition 5.2. Let β ∈ B(W ). We say that β is a Mikado braid if there are
x, y ∈ W such that β = xN (y) .
Example 5.3. Let W be of type A3 , with set S of generators given by s1 , s2 , s3
(where s1 s3 = s3 s1 ). We claim that β := s2 s1 s−1
3 s2 is a Mikado braid. Let
y = s3 s2 . Then
N (y) = {s3 , s3 s2 s3 = s2 s3 s2 }.
Let x := s2 s1 s3 s2 . The expression s2 s1 s3 s2 is S-reduced. Setting i1 = 2, i2 =
1, i3 = 3, i4 = 2 we have si4 = s2 , si4 si3 si4 = s3 s2 s3 , si4 si3 si2 si3 si4 = s2 s1 s2 ,
si4 si3 si2 si1 si2 si3 si4 = s3 s2 s1 s2 s3 . Hence we get xN (y) = s2 s1 s−1
3 s2 = β, which
shows that β is Mikado.
Lemma 5.4 (Dyer). Let x, y ∈ W . Then
(1) We have (xy −1 )N (y) = xy−1 ,
(2) If y = e, then xN (y) = x.
Proof. For the first item see for instance [28, Lemma 3.3 (4)]. The second item
is an immediate consequence of the definition of Mikado braids and the fact that
N (e) = ∅.

Let B(W )+ be the positive braid monoid. Define a partial order ≤ on B(W )
by a ≤ b if and only if a−1 b ∈ B(W )+ . We have the following characterizations of
Mikado braids, which are borrowed from [24, Section 9], [19, Proposition 4.3], [28,
Lemma 3.3]:
Theorem 5.5. Let β ∈ B(W ). The following are equivalent
(1) The element β is a Mikado braid,
(2) There are x, y ∈ W such that β = x−1 y,
(3) There are x, y ∈ W such that β = xy−1 ,
(4) We have ∆−1 ≤ β ≤ ∆, where ∆ is the Garside element for the classical
Garside structure (i.e., ∆ is the positive lift of the longest element w0 ∈
W ).
Example 5.6. Let β = s1 s−1
3 s2 be as in Example 5.3. We wish to express β as
a quotient of two positive canonical lifts of elements of the group, as predicted by
the Theorem above. Using Example 5.3 and Lemma 5.4 we should have β = xy−1
with xy −1 = s2 s1 s3 s2 and y = s3 s2 , hence x = s2 s1 s3 s2 s3 s2 = s2 s1 s2 s3 . We
indeed have
−1
−1
−1
xy−1 = s2 s1 s2 s3 s−1
2 s3 = s2 s1 s3 s2 s3 s3 = β.
One of the interesting properties of Mikado braids is that their images in the
Iwahori-Hecke algebra of the Coxeter system have polynomials with nonnegative
coefficients as coordinates when expressed in the Kazhdan-Lusztig basis. The
proof of this result requires categorification techniques. This is one of the interesting representation theoretic features of Mikado braids. We briefly recall these
properties.
Let v be an indeterminate. Recall that the Iwahori-Hecke algebra H(W ) of
W is the Z[v ±1 ]-algebra generated by Ts , s ∈ S, satisfying the braid relations
of W and the quadratic relations Ts2 = (v −2 − 1)Ts + v −2 for all s ∈ S. It

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

13

follows from the quadratic relations that the Ts are invertible in H(W ) and one
has therefore a group homomorphism ϕ : B(W ) −→ H(W )× induced by s 7→ Ts .
For x ∈ W , with positive lift x ∈ B(W ), denote by Tx the element ϕ(x) ∈ H(W ).
It is well-known that {Tx }x∈W is a Z[v ±1 ]-linear basis of H(W ), called standard
basis. Let {Cw }w∈W be the Kazhdan-Lusztig C-basis (see [28] for the notation
and references). One has the following (conjectured by Dyer in [22]; see [26] for
the case of finite Weyl groups, [28] for the general case)
Theorem 5.7. Let W be a (not necessarily finite) Coxeter group. Let x, y ∈ W .
Then
X
ϕ(xy−1 ) = Tx Ty−1 ∈
Z≥0 [v ±1 ]Cw .
w∈W

Classifying braids which have an image which is positive in the Kazhdan-Lusztig
basis appears as an interesting question to us. If W is finite, we have no example
of a braid which is not a Mikado braid but satisfies this property.
5.2. Simple dual braids are Mikado braids. Let p : B(W ) ։ W denote
the canonical surjection induced by s 7→ s, s ∈ S. For all x, y ∈ W , we have
p(xN (y) ) = x. The following Theorem has been (conjectured for all finite W and)
shown by Digne and the author [19] for every irreducible Coxeter system except
for type Dn . Baumeister and the author [4] proved it in type Dn . Independently,
Licata and Queffelec [34] gave a completely different proof in types An , Dn and En .
In [19], [4], the proof requires topological realizations of Artin groups (in the classical types): Mikado braids are characterized topologically and the proof uses this
characterization. In [34], the proof uses homological properties of categorifications
of Mikado braids (by bounded complexes in a suitable homotopy category).
Mikado braids indeed seem to have remarkable properties in 2-braid groups:
in [28], it is shown that the Rouquier complex of a Mikado braid (attached to a
non necessarily finite Coxeter group) lies in the heart of the canonical t-structure
on the bounded homotopy category of Soergel bimodules (Theorem 5.7 in the
general case is a consequence of this property). In [34], Licata and Queffelec show
a similar property in a bounded homotopy category of projective modules over a
zigzag algebra, in types An , Dn and En .
Theorem 5.8. Let W be a finite Coxeter group, c ∈ Std(W, S), x ∈ NC(W, c).
The simple dual braid xc ∈ Bc∗ is a Mikado braid.
An immediate consequence of this Theorem and Theorems 5.7 and 5.5 is:
Corollary 5.9. Let W be a finite Coxeter group, c ∈ Std(W, S), x ∈ NC(W, c).
Then
X
ϕ(xc ) ∈
Z[v ±1 ]Cw .
w∈W

5.3. A closed formula for simple dual braids. Expressing simple dual braids
in the classical Artin generators is a fundamental problem. In light of Theorem 5.8,
given x ∈ NC(W, c), there is y ∈ W such that the simple dual braid xc is equal to
xN (y) . In principle, expressing simple dual braids in the classical Artin generators
requires an inductive application of dual braid relations, and no closed formula is
known (some of the proofs of Theorem 5.8 mentioned in Section 5.2 provide an
algorithm to write a simple dual braid as a Mikado braid, but no closed formula).
In general, there might be several y such that xc = xN (y) , but it is natural to
wonder if there is a natural one. The following Theorem, which is the main result

14

THOMAS GOBET

of this paper, gives an answer to this question, and also provides a new (entirely
combinatorial proof) of Theorem 5.8:
Theorem 5.10. Let W be a finite Coxeter group, c ∈ Std(W, S), x ∈ NC(W, c).
Let y = x−1 c be the right Kreweras complement of x. Then xc = xN (Sc (y)) .
In other words, the suitable element by which one has to twist x to get the simple
dual braid xc is the c-sortable element corresponding to the Kreweras complement
y of x. Note that it also shows that xc is actually obtained by lifting an (in fact,
any) S-reduced expression of x, hence that the length of xc in B(W ) (with respect
to S ∪ S−1 ) is equal to the length of its image x = p(xc ) in W , which is not clear
at all from the definition of dual braid monoids.
The rest of the section is devoted to proving Theorem 5.10, assuming Lemma 4.6
(which will be proven in Section 6 using a case-by-case argument). The strategy
is to take advantage of the nice properties of c-sortable elements given in Lemmatas 4.3 and 4.4. That is, the proof is by induction on the classical length of
Sc (y) and the rank of W , where we allow c to vary (i.e., the statement is proven simultaneously for all Coxeter elements). We start by proving the following Lemma:
Lemma 5.11. Let x ∈ NC(W, c). Let y = x−1 c. Let t ∈ T such that t ≤T x.
Then t ∈
/ N (Sc (y)).
Proof. We argue by induction on the classical length of Sc (y) and the rank of W .
Let s be initial in c. If W has rank 0 or 1 then the claim is obvious.
Firstly, assume that sSc (y) > Sc (y). By Lemma 4.3, it implies that Sc (y) ∈
W<s> and that Sc (y) is sc-sortable. It follows that sxy = sc with ℓT (sx)+ℓT (y) =
ℓT (sc). If t ≤T sx then the claim holds by induction on the rank of W . Hence
assume that t 6≤T sx. Since t ≤T x, we have that t fixes V x by Theorem 2.12.
Assume that t ∈ W<s> . Then t fixes L := V W<s> , which is a line. We have
that dim(V x ) = dim(V sx ) − 1. We claim that L ∩ V x = 0. Otherwise, we have
L ⊆ V x = V sx ∩ V s , implying that s fixes L = V W<s> , a contradiction because
L would be fixed by every element in W . Since sx fixes both L and V x , we have
that V sx = L ⊕ V x . It follows that t fixes V sx , hence by Theorem 2.12 again
that t ≤T sx, a contradiction. Hence t ∈
/ W<s> which implies that t ∈
/ N (Sc (y))
(because Sc (y) ∈ W<s> ).
Now assume that sSc (y) < Sc (y). We first consider the case where s is a cover
−1 (sS (y)) = ys (by
reflection of Sc (y). It implies that sSc (y) is scs-sortable and Sscs
c
Lemma 4.4 and [36, Lemma 6.5]). By induction on length, we have that for every
q ≤T sx,
q∈
/ N (Sscs (ys)) = N (sSc (y)) = N (Sc (y))\{s},
where the last equality holds because s is a cover reflection of Sc (y). Since s is a
cover reflection of Sc (y) we have s ≤T y, hence ys ≤T y and x ≤T sx. It implies
that t ≤T sx, hence (as we have seen above) that t ∈
/ N (Sc (y))\{s}. Since t ≤T x
and s 6≤T x we have t 6= s. Hence t ∈
/ N (Sc (y)).
We now assume that s is not a cover reflection of Sc (y). Then sSc (y) is scs−1 (sS (y)) = sys (by Lemma 4.4 and [36, Lemma 6.5]). We have
sortable and Sscs
c
scs = (sxs)(sys) and ℓT (sxs) + ℓT (sys) = ℓT (scs). By induction on length, we
have that for every q ≤T sxs,
q∈
/ N (sSc (y)) = sN (Sc (y))s\{s}.
We have t ≤T x, hence sts ≤T sxs, hence sts ∈
/ sN (Sc (y))s\{s}. It implies
that either t ∈
/ N (Sc (y)), in which case we are done, or t = s. But since t ≤T x, if

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

15

t = s we have that sx ∈ W<s> (see [36, Lemma 5.2] or use Carter’s Lemma) and
sxy = sc, implying that y ∈ W<s> . In particular, Sc (y) has all its cover reflections
in W<s> , implying that Sc (y) ∈ W<s> by [38, Lemma 2.24]. This contradicts
sSc (y) < Sc (y). Hence t 6= s, and t ∈
/ N (Sc (y)).

5.4. Proof of the main theorem.
Proof of Theorem 5.10. We argue by Cambrian recurrence, i.e., by induction on
the rank and length of Sc (y) (as in the proof of Lemma 5.11). If ℓ(y) = 0, then
x = c, hence without assumption on the rank of W we have that xN (Sc (y)) = x∅ =
c∅ = cc (note that the case where the rank of W is zero is enough to start the
recurrence). Assume that ℓ(Sc (y)) > 0. Let s be initial in c.
First case: sSc (y) > Sc (y). By Lemma 4.3, it implies that Sc (y) ∈ W<s> and that
Sc (y) is sc-sortable. We have Readsc (Sc (y)) = y ∈ W<s> (hence Ssc (y) = Sc (y))
and therefore sc = (sx)y with ℓT (sx) + ℓT (y) = ℓT (sc). By induction on the rank
of W we get that
(sx)sc = (sx)N (Ssc (y)) .
Note that Ssc (y) = Sc (y). Since sx ∈ W<s> we have (sx)sc = (sx)c by Lemma 3.3
(2). We have sx ≤T x which implies that xc = sc (sx)c = s(sx)c . Hence to
prove that xc = xN (Sc (y) , it suffices to show that xN (Sc (y)) = s(sx)N (Sc (y)) . Since
sx ∈ W<s> we have x > sx. Choosing a reduced expression of x beginning by s we
get that xN (Sc (y)) = sε (sx)N (Sc (y)) , where ε = 1 if and only if x−1 sx ∈
/ N (Sc (y)).
But since sx ∈ W<s> , we have x−1 sx ∈
/ W<s> , hence x−1 sx ∈
/ N (Sc (y)) since
Sc (y) ∈ W<s> . This concludes in this case.
Second case: sSc (y) < Sc (y) and s is a cover reflection of Sc (y). By
−1 (sS (y)) =
Lemma 4.4, it implies that sSc (y) is scs-sortable. We have that Sscs
c
ys ≤T y (see [36, Lemma 6.5] and its proof). We have scs = (sx)(ys) with
ℓT (scs) = ℓT (sx) + ℓT (ys). Note that x ≤T sx ≤T scs since ys ≤T y. We then
have sxs ≤T xs ≤T c which, by [36, Lemma 5.2], implies that sxs ∈ W<s> . By
induction on length we have that
(5.12)

(sx)N (sSc (y)) = (sx)N (Sscs (ys)) = (sx)scs .

We have to show that xN (Sc (y)) = xc . Since s is initial in c and sxs ∈ W<s> , by
Lemmatas 3.3 and 3.4 we obtain
(5.13)

s−1 xc s = (sxs)scs = (sxs)sc = (sxs)c .

Moreover, since sxs ≤T sx ≤T scs we have that (sx)scs = (sxs)scs s. Recall that
sxs ∈ W<s> , hence sxs < sx, xs. If x < sx or x < xs, then x = sxs by the
exchange lemma.
Firstly, assume that x < sx (and hence x = sxs). Note that since s is a
cover reflection of Sc (y), we have N (sSc (y)) = N (Sc (y))\{s}. It follows that
(sx)N (sSc (y)) = (xs)N (sSc (y)) = xN (Sc (y)) s. This concludes because in that case
using also (5.12) and (5.13) we have
xc = (sxs)c = (sxs)scs = (sx)scs s−1 = (sx)N (sSc (y)) s−1 = xN (Sc (y)) .
Now assume that sx, xs < x. We have that x ≤T sx, hence x−1 sx ≤T sx.
By Lemma 5.11 it implies that x−1 sx ∈
/ N (sSc (y)) (we apply the Lemma with
scs = (sx)(ys)). It follows that s(sx)N (sSc (y)) = xN (sSc (y) . Lemma 3.4 then yields
(5.14)

xc = s(sxs)scs s−1 = s(sx)scs s−1 s−1 .

16

THOMAS GOBET

By induction and (5.14) we get
xc = xN (sSc (y)) s−2 = (xs)N (Sc (y)) ss−2 = (xs)N (Sc (y) s−1 = xN (Sc (y)) ,
where in the second and last equality we used that xs < x and N (sSc (y)) =
N (Sc (y))\{s} (which implies that t ∈ N (Sc (y))\{s} ⇔ sts ∈ N (Sc (y))\{s}).
This concludes in that case.
Third case: sSc (y) < Sc (y) and s is not a cover reflection of Sc (y). It
−1 (sS (y)) = sys
implies that sSc (y) is scs-sortable by Lemma 4.4. We have that Sscs
c
−1
(see [36, Lemma 6.5]). Since (sxs)scs = s xc s, by induction on the length it
suffices to show that xN (Sc (y)) = s(sxs)N (sSc (y)) s−1 .
Note that (sxs)N (sSc (y)) = (sx)N (Sc (y)) s (this can be seen by a direct computation using the definition of Mikado braids and distinguishing the cases sx < sxs
and sxs < sx). Hence it suffices to show that s(sx)N (Sc (y)) = xN (Sc (y)) . If
sx < x, then s ∈ N (x) and by Lemma 4.6 together with Remark 4.7 we have
that x−1 sx ∈
/ N (Sc (y)). It follows that xN (Sc (y)) = s(sx)N (Sc (y)) . If sx > x, then
s∈
/ N (x) and by Lemma 4.6 and Remark 4.7 we have that x−1 sx ∈ N (Sc (y)). It
follows that (sx)N (Sc (y)) = s−1 xN (Sc (y)) . Hence in both cases (x < sx and x > sx)
we get that s(sx)N (Sc (y)) = xN (Sc (y)) , which concludes in this case.
This completes the proof of Theorem 5.10.

6. Bijections between noncrossing partitions and c-sortable
elements
The aim of this section is to give an explicit description of the inverse Sc of
Reading’s bijection Read from noncrossing partitions to c-sortable elements (in
the classical and dihedral types), and use it to prove Lemma 4.6. We study each
type in a different section. Types An and Dn are treated using the noncrossing
partition models, while for type Bn one can use the realization of the Coxeter group
as the subgroup of a Coxeter group W ′ of type A2n−1 consisting of those elements
which are fixed by the automorphism of W ′ induced by the automorphism of the
type A2n−1 Dynkin diagram.
6.1. Type An .
6.1.1. Graphical noncrossing partitions. We identify W with the symmetric group
Sn+1 and S with the set of simple transpositions. We denote by si the simple transposition (i, i + 1), i = 1, . . . , n. Let c ∈ Std(Sn+1 ). The elements of
NC(Sn+1 , c) can be represented by disjoint unions of polygons with vertices on a
circle labeled by [n + 1] := {1, . . . , n + 1}. Every Coxeter element is an (n + 1)cycle. For c = (i1 , i2 , . . . , in+1 ), the labeling of the circle is given (in clockwise
order) by i1 i2 · · · in+1 . We call it the c-labeling. Assuming that i1 = 1, ik = n + 1,
one has that c lies in Std(Sn+1 ) if and only if the sequence i1 i2 · · · ik is increasing
and the sequence ik · · · in in+1 is decreasing (see for instance [30, Lemma 8.2]). We
set Rc := {i1 , i2 , . . . , ik }, Lc := {ik , ik+1 , . . . , in+1 , i1 }. An example is given in
Figure 1 below. To every cycle in the decomposition of x ∈ NC(Sn+1 , c) into a
product of disjoint cycles, one associates the polygon obtained as the convex hull of
the set of points lying in the support of the cycle (we identify the points with their
labels; polygons can be reduced to a line segment or a point). We denote the set of
polygons of x by Pol(x) and identify a polygon with the set of integers labeling its
vertices. In the obtained diagram, all the polygons are disjoint, equivalently the
partition defined by the cycle decomposition of x is noncrossing for the c-labeling

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

17

(see [9] for more details). A reflection (i, j) lies in the parabolic subgroup P (x) if
and only if the line segment ij is an edge or a diagonal of a polygon P ∈ Pol(x),
that is, if and only if there is P ∈ Pol(x) with i, j ∈ P , while it is a canonical
generator of P (x) if and only if i, j ∈ P with no i < k < j such that k ∈ P .
It turns out to be convenient for some proofs to slightly modify the graphical
representation in the following way: let c = (i1 , . . . , in+1 ) ∈ Std(Sn+1 ) with i1 = 1,
ik = n + 1. Instead of drawing the points on the circle such that the length of the
segment between any two successive points is constant, we draw the point with
label 1 at the top of the circle, the point with label n + 1 at the bottom, the points
with label in ik · · · in in+1 on the left and the points with label in i1 i2 · · · ik on the
right, each point having a specific height depending on its label. More precisely,
if i, j ∈ [n + 1], i < j, then the point i is higher than the point j (as done in
the right picture of Figure 1). Also, when representing a noncrossing partition we
may use curvilinear polygons instead or regular polygons for convenience (as in
Figure 2), but with the convention that every edge of a polygon should be either
strictly increasing or decreasing.
1

b

1
b

2

b

2
b

3
b

3

b

b

4

4
b

5
b

b

5

b

6

6
b

Figure 1. The c-labeling for c = s1 s3 s5 s4 s2 = (1, 2, 4, 6, 5, 3) ∈ Std(Sn+1 ).
We have Lc = {1, 3, 5, 6}, Rc = {1, 2, 4, 6}.
1
b

1
b

2
b

b

3
b

3

b

4
b

4

5
b

b

2
b

6
b

b

5
6

Figure 2. Conventions on the graphical representations of c-noncrossing
partitions. On the left: (1, 3, 6)(2, 5) ∈ NC(S6 , s2 s1 s3 s5 s4 ); on the right:
(1, 2, 3, 6)(4, 5) ∈ NC(S6 , s1 s2 s3 s4 s5 ).
6.1.2. Explicit description of the map from noncrossing partitions to c-sortable
elements.
Definition 6.1 (Relative positions of polygons). Let P, Q be two distinct polygons
of x. We say that P is strictly at the left of Q if there is a horizontal line L
intersecting both Q and P and L ∩ P is at the left of L ∩ Q. In this situation we
also say that Q is strictly at the right of P . There might be several horizontal lines
intersecting both P and Q non trivially, but it is clear that the intersections with
horizontal lines will always appear in the same order. We say that P and Q are
fully disjoint if none of them lies strictly at the right of the other. We say that P

18

THOMAS GOBET

is at the left of Q if either it is strictly at the left of Q, or they are fully disjoint
(and similarly Q lies at the right of P ). Note that given any two distinct polygons,
there is always one of them lying at the left of the other.
Note that determining the relative position of two polygons can be done by just
looking at the relative position of the two diagonals joining the smallest to the
biggest index of each polygon, instead of considering the whole polygons.
We define a total order ≺ on the set Pol(x) of polygons of x ∈ NC(Sn+1 , c). In
the graphical representation of x, let P ∈ Pol(x) be the unique polygon such that
(1) P has no polygon lying strictly at its right (i.e., any horizontal line crossing
P crosses no polygon at the right of P ),
(2) max(P ) is minimal among all polygons satisfying property (1).
Then P appears first in the total order. We then remove P (together with
all its vertices) from the graphical representation. The second polygon Q in the
total order is the unique polygon among the remaining ones such that there is no
polygon (among the remaining ones) lying strictly at the right of Q and max(Q)
is minimal for this property, and so on.
We use this order to define a permutation Sc (x) ∈ Sn+1 . If P is the first
polygon in the order and P = {d1 > d2 > · · · > dk }, we define Sc (x) on the subset
{1, 2, . . . , k} by 1 7→ d1 , 2 7→ d2 , . . . , k 7→ dk . If Q is the second polygon in the
order and Q = {e1 > e2 > · · · > eℓ }, we define Sc (x) on the subset {k+1, . . . , k+ℓ}
by k + 1 7→ e1 , k + 2 7→ e2 , . . . , k + ℓ 7→ eℓ }, and so on.
Example 6.2. Let c = s2 s1 s3 s5 s4 . Let (1, 3, 6)(2, 5) ∈ NC(S6 , c) (the graphical
representation is given in the left picture of Figure 2). The only polygon with no
other polygon strictly at its right is {4}. After removing it, the only polygon with
no other polygon strictly at its right is {6, 3, 1}. Hence the total order on the set
of polygons of x is
{4} ≺ {6, 3, 1} ≺ {5, 2}.
It follows that
Sc (x) = (1, 4)(2, 6) = s2 s1 s3 s5 s4 |s2 s1 s3 s5 |s2 .
The reduced expression above shows that Sc (x) is c-sortable. This is a general
fact, proven in Theorem 6.3 below.
Note that if Q is strictly at the right of P , then we necessarily have Q ≺ P . It
can happen that P and Q are fully disjoint, with j < k for all j ∈ P and k ∈ Q,
but nevertheless Q ≺ P . This is, me may have a sequence Q1 , . . . , Qm of pairwise
distinct polygons of x with Q strictly at the right of Q1 , Q1 strictly at the right
of Q2 , . . . , Qm strictly at the right of P , but P and Q fully disjoint.
Theorem 6.3. Let x ∈ NC(Sn+1 , c). The element Sc (x) ∈ Sn+1 is c-sortable and
we have Read(Sc (x)) = x. That is, we have Sc = Read−1 .
Proof. Rather than using the definition of c-sortable elements, we make use of their
characterization as a permutation: in [36, Theorem 4.12], Reading shows that a
permutation in Sn+1 is c-sortable if and only if its line notation avoids the pattern
jki for all i < j < k such that j ∈ Lc and avoids the pattern kij for all i < j < k
such that j ∈ Rc .
Let i < j < k and assume that j ∈ Lc . Firstly, we assume that i ∈ P ∈ Pol(x)
with P 6= Q, where Q ∈ Pol(x) is the polygon containing j. If P ≺ Q then in the
line notation of Sc (x) we have that i appears before j hence Sc (x) is jki-avoiding.

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

19

Hence assume that Q ≺ P . If k ∈ P , then the edge ik of P would lie strictly at
the right of Q since j ∈ Q and i < j < k, contradicting Q ≺ P . If k ∈ Q, then by
definition of Sc (x) we have that k appears before j in the line notation of Sc (x),
hence that Sc (x) is jik-avoiding. We can therefore assume that k ∈ R ∈ Pol(x)
for some R 6= P, Q. If R ≺ Q then k appears before j, in which case we are
done. So we can assume that Q ≺ R. Since Q ≺ R, P , it means that after having
removed the polygon Q in the order ≺, there can be no polygon intersecting the
horizontal line j (because j ∈ Q ∩ Lc : by definition of ≺, when removing Q there
can be no polygon strictly at the right of Q, whence the claim). It implies that
P ⊆ {1, . . . , j − 1} and R ⊆ {j + 1, . . . , n + 1}. Together with the fact that after
removing Q, no polygon can cross the line j, we get that P ≺ R, which implies
that k appears after i in the line notation of Sc (x), hence that it is jki-avoiding.
Now if P = Q, then the indices appearing between j and i in the line notation for
Sc (x) are all the vertices m ∈ P such that i < m < j, therefore k cannot appear.
Hence Sc (x) is jki-avoiding. If j ∈ Rc , the proof that Sc (x) is kij-avoiding is
similar. This proves that Sc (x) is c-sortable.
We now prove that Sc is the inverse of Read−1 . Recall that the map Read
sends a c-sortable element y to the product of its cover reflections in a suitable
order. In the line notation π1 π2 · · · πn+1 of a permutation y ∈ Sn+1 , the cover
reflections are the transpositions (πi , πi+1 ) such that πi+1 < πi . By defintion
of the element Sc (x), we have that the cover reflections of Sc (x) are precisely the
transpositions (i, j) such that i and j are consecutive vertices of a common polygon
of x: indeed, given a polygon P = {d1 > d2 > · · · > dk }, there is r ∈ [n + 1] such
that Sc (x)(r + i − 1) = di for all i = 1, . . . , k, implying that (di , di+1 ) is a cover
reflection of Sc (x) for all i = 1, . . . , k − 1. The element Sc (x) has no other cover
reflection since if P ≺ Q are consecutive in the order which we put on polygons,
then min P < max Q by definition of the order, in particular in the line notation
of Sc (x) the index following dk has to be bigger than dk . It follows that the
cover reflections of Sc (x) are precisely the canonical generators of the parabolic
subgroup associated to the noncrossing partition x, which using Theorem 4.5 and
the remarks preceding Remark 2.8 proves that x = Read(Sc (x)).

The fact that Sc (x) is c-sortable can also be proven using Lemmatas 4.3 and 4.4.
In type Dn we will define Sc similarly and prove this fact using these Lemmatas.
Before proving Lemma 4.6 we show
Lemma 6.4. Let c be a Coxeter element and let s = si be initial in c (that is,
i ∈ Lc , i + 1 ∈ Rc ). Let j = c−1 (i), k = c−1 (i + 1). Assume that j ∈ P1 , k ∈ P2 ,
with P1 6= P2 . Then P2 ≺ P1 .
Proof. If ℓ := min(P1 ) < k, then the segment jℓ is strictly at the left of P2 (since
k ∈ Rc ) implying that P2 ≺ P1 . Similarly if max(P2 ) > j we have P2 ≺ P1 . Hence
we can assume that min(P1 ) > k and max(P2 ) < j. In this situation, if P1 and
P2 are not fully disjoint then we necessarily have that P2 is strictly at the right
of P1 implying P2 ≺ P1 again (looking at Figure 3 is helpful to note this fact: it
follows from the fact that {k + 1, . . . , i} ⊆ Lc and {i + 1, . . . , j − 1} ⊆ Rc ). We can
therefore assume that P2 and P1 are fully disjoint. Moreover since all indices in
P2 are strictly smaller than those in P1 (because of fully disjointness and k ∈ P2 ,
j ∈ P1 with k < j), we have P1 ≺ P2 only if there is a sequence Q1 , . . . , Qm of
polygons of x with Q1 strictly at the left of P1 , Qi strictly at the left of Qi−1 for

20

THOMAS GOBET

all i and P2 strictly at the left of Qm . Inspection of Figure 3 again shows that this
situation cannot appear.


b

...

b

k ∈ P2
b

i
b

b
b

j ∈ P1

b

b

i+1
...

Figure 3. A picture for the proof of Lemma 6.4. Note that by definition of
j and k, there are no points on the circle between j and i as well as between
k and i + 1.
We now prove Lemma 4.6 in type An :
Proof of 4.6 in type An . We reformulate the lemma to drop any reference to x. We
have x−1 sx = (x−1 (i), x−1 (i + 1)). Note that since xy = c we have x−1 (i) = y(j),
x−1 (i + 1) = y(k), where j precedes i on the circle and k precedes i + 1. Assume
that x−1 (i) < x−1 (i + 1). Since k < j it implies that x−1 sx ∈ N (y), hence we have
to show that x−1 sx ∈ N (Sc (y)), that is, that Sc−1 (y)(y(j)) > Sc−1 (y)(y(k)). If
x−1 (i) > x−1 (i + 1), then x−1 sx ∈
/ N (y), hence we have to show that Sc−1 (y(j)) >
−1
Sc (y(k)). What we have just proven is that it suffices to show that
Sc−1 (y)(y(j)) > Sc−1 (y)(y(k))
to establish the Lemma.
Let P1 be the polygon containing j and P2 be the one containing k. Note that
y(j) ∈ P1 , y(k) ∈ P2 . If P1 = P2 , then jk is a diagonal of P1 = P2 , in particular
we have y(j) < y(k) (since j ∈ Lc , k ∈ Rc , k < j, hence y(j) ≤ i, y(k) ≥ i + 1).
Since y(j), y(k) ∈ P1 = P2 , by definition of Sc (y) it follows that Sc−1 (y(j)) >
Sc−1 (y)(y(k)), which concludes in this case. Hence assume that P1 6= P2 . Then by
Lemma 6.4 we have P2 ≺ P1 , hence Sc−1 (y)(y(j)) > Sc−1 (y)(y(k)) by definition of
Sc .

6.2. Type Bn . Let W be a Coxeter system of type A2n−1 and let Γ be the automorphism of W induced by the automorphism of the Dynkin diagram which
exchanges si and s2n−i for all i = 1, . . . , 2n − 1. Then W Γ is a Coxeter group of
type Bn (see for instance [19, Section 6.1] and the references therein). Its generators as a Coxeter group are given by t0 = sn , t1 = sn−1 sn+1 , . . . , tn−1 = s1 s2n−1 .
For convenience we see W as the symmetric group on {−n, . . . , −1, 1, . . . , n}; in
this description we have t0 = (1, −1), ti = (i, i+1)(−i, −i−1), ∀ i ∈ {1, . . . , n−1},
and W Γ is the subgroup of signed permutations, that is, of elements w ∈ W such
that w(−i) = −w(i) for all i = 1, . . . , n. The set of reflections in WBn is given by
T := TBn := {(i, −i) | i = 1, . . . , n} ∪ {(i, j)(−i, −j) | i 6= ±j and i, j = 1, . . . , n}.
Given w ∈ W Γ ⊆ W , we denote by N A (w) (resp. N B (w)) the inversion set of w
in W (resp. W Γ ). For w ∈ W Γ and i ∈ {1, . . . , n}, we have (i, −i) ∈ N A (w) ⇔
(i, −i) ∈ N B (w), while for i, j ∈ {1, . . . , n} with i 6= ±j we have (i, j)(−i, −j) ∈

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

21

N B (w) ⇔ (i, j) ∈ N A (w) ⇔ (−i, −j) ∈ N A (w) (see for instance [11, Section 8.1]).
The same equivalences hold if we replace inversion sets by sets of left or right
descents and reflections by simple reflections.
The standard Coxeter elements in W Γ are the Coxeter elements in W which
are fixed by Γ. Let c be such a Coxeter element. Then NC(W Γ , c) = NC(W, c)Γ ,
in particular noncrossing partitions of type Bn can be graphically represented by
noncrossing partitions of type A2n−1 for the c-labeling, which are stable by a half
turn (see for instance [19, Section 6.3]).
Lemma 6.5. We have Sort(W Γ , c) = Sort(W, c)Γ .
Proof. By definition of c-sortability, we have that Sort(W Γ , c) ⊆ Sort(W, c)Γ . Conversely, let w ∈ Sort(W, c)Γ and let w = w1 w2 · · · wk , where wi is the subexpression
of the i-th copy of c in the c-sorting word for w. We want to show that Γ(wi ) = wi
for all i. By induction on k it suffices to show that Γ(w1 ) = w1 . if Γ(w1 ) 6= w1 , then
there is an i such that si appears in w1 but s2n−i does not (recall that each simple
reflection can occur at most once in w1 ). By definition of c-sortability, it implies
that s2n−i appears in no wi , hence that there is a reduced expression of w in which
si appears but s2n−i does not, contradicting Γ(w) = w (since the simple reflections
occuring in any two reduced decompositions are the same). Hence Γ(wi ) = wi for
all i. It follows that w ∈ Sort(W Γ , c). Hence Sort(W Γ , c) = Sort(W, c)Γ .

Now the above equivalences on descent and inversion sets of types A and B
imply that for w ∈ Sort(W Γ , c) we have ReadA (w) = ReadB (w), where ReadA
(resp. ReadB ) denotes the map from c-sortable elements to noncrossing partitions
in type A (respectively in type B). As a consequence, the map ScB : NC(W Γ , c) −→
Sort(W Γ , c) defined as the inverse of ReadB coincides with the restriction of the
inverse ScA = Sc : NC(W, c) −→ Sort(W, c) of ReadA (described in Section 6.1.2)
to W Γ .
It is now easy to derive a proof of Lemma 4.6 in type Bn from the Lemma in
type An :
Proof of Lemma 4.6 in type Bn . Assume that s = t0 . Then x−1 sx = (i, −i) for
some i ∈ {1, . . . , n}. We have that s is initial in c viewed as a Coxeter element
of type A2n−1 . By the properties of inversion sets given above and Lemma 4.6 in
type An we have
x−1 sx ∈ N B (y) ⇔ x−1 sx ∈ N A (y) ⇔ x−1 sx ∈ N A (Sc (y)) ⇔ x−1 sx ∈ N B (Sc (y)),
which concludes the proof in that case. Now assume that s = ti = sn−i sn+i ,
i ∈ {1, . . . , n − 1}. We have that both sn−i and sn+i are initial in c viewed as a
Coxeter element of type A2n−1 . By the properties of inversion sets given above
and Lemma 4.6 in type An we have
x−1 sx ∈ N B (y) ⇔ x−1 sn−i x ∈ N A (y) ⇔ x−1 sn−i x ∈ N A (Sc (y)) ⇔ x−1 sx ∈ N B (Sc (y)),
which concludes the proof in that case.



6.3. Type Dn .
6.3.1. Graphical representations. The Coxeter group WDn of type Dn is realized
as an index two subgroup of the signed permutation group WBn ; a permutation
w ∈ WBn is in WDn if and only if |{i ∈ {1, 2, . . . , n} | w(i) < 0} is even. The
Coxeter generating set is given by s0 = (1, −2)(−1, 2), si = (i, i + 1)(−i, −i − 1)
for all i = 1, . . . , n − 1. Recall that that w(−i) = −w(i), for all i ∈ {1, . . . , n} and

22

THOMAS GOBET

all w ∈ WBn . In WBn , cycles of the shape (i1 , . . . , ir , −i1 , . . . , −ir ) are abbreviated
by [i1 , . . . ir ] and called balanced cycles, and those of type (i1 , . . . , ir )(−i1 , . . . , −ir )
by ((i1 , . . . , ir )) and called paired cycles. Every w ∈ WDn can be written as a
product of disjoint cycles in which there is an even number of balanced cycles
(see [1, Section 2]).
The set of reflections in WDn is
T := TDn := {(i, j)(−i, −j) | i, j ∈ {−n, . . . , n}, i 6= ±j}.
The standard Coxeter elements of type Dn are of the form
(i1 , −i1 )(i2 , . . . , in , −i2 , . . . , −in ),
where {i1 , . . . , in } = {1, . . . , n}, i1 ∈ {1, 2} and the sequence i2 · · · in is first increasing, then decreasing (see [4, Lemma 4.3]). If ik = n we set
Lc = {ik , ik+1 , . . . , in , −i2 , . . . , −ik }, Rc = −Lc .
The elements of NC(WDn , c) also admit noncrossing-like graphical representations.
The reference for this is mostly [1], but our conventions are those from [4, Section
5]. We briefly recall how it works and refer the reader to [4] for more details.
The circle is labelled as in type An with the sequence i2 , . . . , in , −i2 , . . . , −in but
there is one additional point at the center of the circle, with the two labels ±i1 .
As in type An , we put the points at different heights such that point i is higher
than point j if and only if i < j, with −n at the top of the circle and n at the
bottom. Then given x ∈ NC(WDn , c), we consider the cycle decomposition of x
inside WBn ⊆ WA2n−1 and associate to every (type A2n−1 ) cycle a polygon, given
by the convex hull of those points having their label in the support of the cycle.
If the cycle (i1 , −i1 ) appears in the decomposition, in fact in that case there must
be a polygon P such that P = −P , hence with the middle point labeled by ±i1
inside it. In that case we leave the middle point untouched. We often identify
polygons with their labels; in the case where P = −P , consider ±i1 as lying in
P (that is, in the case where we have two balanced cycles in x, then one must
be (i1 , −i1 ); we then consider theses two cycles as a single polygon). We denote
the set of polygons of x by Pol(x). Hence to each paired cycles are associated two
polygons P, −P , while if there are balanced cycles (in which case there are exactly
two of them), we consider them as a single polygon Q = −Q (and we call such a
polygon symmetric).
This gives a noncrossing diagram, i.e. the obtained polygons are all disjoint,
except possibly in two cases:
• The first case is if there is a polygon P ∈ Pol(x) with i1 ∈ P but −i1 ∈
/ P.
Since x is a signed permutation, we have that −P is also a polygon of x. In
that case the polygons P and −P have the middle point in common. Note
that we have to specify, in the graphical representation, whether i1 ∈ P or
i1 ∈ −P .
• The second case appears if x has a product of cycles of the form
(j, −j)(i1 , −i1 )
for some j 6= ±i1 . In that case, to avoid confusion with the graphical representation of the noncrossing partition ((j, i1 )) (or ((j, −i1 ))), we join the
point j to the point −j by two curves in such a way that the middle point
lies between the two curves (the cycle (j, −j) corresponds to a polygon P
with P = −P , hence this way of representing the situation should be seen

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

23

as a special case of the situation mentioned above when a factor (i1 , −i1 )
appears in the decomposition of x).
Conversely, every noncrossing diagram as above can be used to define an element of NC(WDn , c), by associating to a polygon P 6= −P , P = {m1 , . . . , mk }
(in clockwise order) the k-cycle (m1 , . . . , mk ) and to a polygon P = −P =
·

{m1 , . . . , mk } ∪ {i1 , −i1 } (where the mi ’s are read in clockwise order) the product
of cycles (i1 , −i1 )(m1 , . . . , mk ).
Examples are given in Figure 4 below and we refer to [4, Section 5.2] or [1] for
more details.
b

b
b
b
b

b

b

2

−2
b
b

b
b
b
b
b

b

−8
−7
−6
−5
−4
−3

b

−8
−7
−6
−5
−4
−3

b
b
b
b

−1
1

b

b

b

2

−2
b
b

3
4
5
6
7
8

b
b
b
b
b

−1
1
3
4
5
6
7
8

Figure 4. Examples of noncrossing partitions x1 = ((3, −8))((7, 5, −2)),
x2 = ((8, 7, 5))[4, 6, 3][2] of type Dn .

For our purposes, we need to slightly modify the graphical representation introduced above, as done in [4]. We proceed as follows: starting from a diagram
as above, we then split the middle point into two points with respective labels
i1 and −i1 , which we move on the vertical axis of the circle in such a way that
the condition on the height of the points stays satisfied (see Figure 5). Note that
the polygons might be replaced by curvilinear polygons to keep the noncrossing
property, and that in general there is not a unique way to split P and −P in the
case where P 6= −P and ±i1 ∈ P (see Figure 6). In all the cases, we require
that each curve corresponding to an edge of a curvilinear polygon is either strictly
increasing or decreasing.
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b

−8
−7
−6
−5
−4
−3
−2
−1
1
2
3
4
5
6
7
8

Figure 5. Splitting of the middle point. Here the noncrossing partition is
x1 = ((3, −8))((7, 5, −2)) as in the left picture of Figure 4.

24

THOMAS GOBET

6.3.2. Explicit description of the map from noncrossing partitions to c-sortable
elements. As in type An , we introduce a total order ≺ on the set Pol(x) of polygons
of x ∈ NC(WDn , c), in such a way that P ≺ Q if and only if −Q ≺ −P . We begin
by defining an order < on the set
{Q | Q ∈ Pol(x), Q = −Q} ∪ {P ∪ −P | P ∈ Pol(x), P 6= −P }.
Before doing it, we define a property of a pair P 6= −P of polygons of x (and
the restriction of ≺ to such a pair, which will be useful for the definition of ≺ on
the whole set Pol(x)):
Definition 6.6 (Special polygons). Let P ∈ Pol(x) with |P | ≥ 2 and P 6= −P .
We say that the pair {P, −P } is special if
(1) One of the two polygons has exactly one index in {1, 2} with all other
indices in {−1, . . . , −n}. Note that it can happen that both P and −P
satisfy this condition,
(2) There is no polygon lying between P and −P (meaning that if a horizontal
line crosses both P and −P , it crosses no polygon in between) and the
polygon among P and −P having the smallest index, say P , has at most
one vertex of −P which lies strictly at its right.
In this situation we set P ≺ −P .
Note that there can be at most one pair of special polygons.
Example 6.7. Let c = (−4, −3, −1, 4, 3, 1)(2, −2), x = ((−4, −3, 2)). Writing
P = {−4, −3, 2} we have that {P, −P } is special with P ≺ −P . Note that there
is not a unique way of graphically representing x in that case (see Figure 6).
Depending on how we represent the noncrossing partition, P is stricly at the right
of −P , or the opposite. Another example is given by x = ((−4, −2, 1)). In this last
example, P := {−4, −2, 1} appears strictly at the left of −P in the noncrossing
representation but we nevertheless have P ≺ −P . This is one of the reason why
we have to introduce special polygons: in situations where P 6= −P but the pair is
not special, in the case where P appears strictly at the right of −P , we will have
P ≺ −P (which is not the case in the last situation above with x = ((−4, −2, 1)),
where P ≺ −P but −P appears strictly at the right of P ).
b

b

−4
b

−4
b

−3

b

b

b
b

−2
b

−1
1

b

3
b

4

−1
1

b

2

b

−3

b

−2

2

b

3
b

4

Figure 6. Non unique graphical representation of the noncrossing partition
x = ((−4, −3, 2)).

The order < is defined as follows. We apply an inductive procedure similar
to the one defined in type An when we defined ≺, removing polygons or pairs of

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

25

polygons at each step. We distinguish three situations (note that we define relative
positions of polygons exactly as in type An , see Definition 6.1):
(1) Assume that x has no pair of special polygons. In the graphical representation of x, let P be the unique polygon such that P has no polygon lying
strictly at its right and max(P ) is minimal among the polygons satisfying
this property. Then P ∪−P appears first in the total order, and if P 6= −P
we set P ≺ −P . We then remove P ∪ −P and all its vertices from the
graphical representation.
(2) If there is a pair of special polygons {P, −P } with P ≺ −P and P has a
polygon Q 6= −P strictly at its right, then we do as in the first case. Note
that since there is at most one pair of special polygons, the pair which will
be removed in this case is not special since there is at least one polygon
which lies strictly at the right of P .
(3) If there is a special pair of polygons {P, −P } with P ≺ −P and there is no
polygon Q distinct from −P lying strictly at the right of P , then consider
the unique polygon Q in Pol(x)\{−P } having no polygon lying strictly at
its right and such that max(Q) minimal (note that we can have Q=P ). If
max(Q) < max(P ) then Q ∪ −Q appears first in the total order and we
set Q ≺ −Q (note that we cannot have Q = −Q), and we remove them as
well as their vertices from the graphical representation. Otherwise P ∪ −P
appears first in the total order, and we remove it as well.
We then go on inductively. Note that a polygon Q with Q = −Q is necessarily
the top element for <.
The order ≺ is then defined as follows. If there is no symmetric polygon in
Pol(x), label the polygons of x such that
(P1 ≺ −P1 ) < (P2 ≺ −P2 ) < · · · < (Pk ≺ −Pk ).
Then set
P1 ≺ P2 ≺ · · · ≺ Pk ≺ −Pk ≺ · · · ≺ −P2 ≺ −P1 .
If there is Q ∈ Pol(x) which is symmetric, then as noticed above Q has to be the
top element for <. Labeling the polygons of x such that
(P1 ≺ −P1 ) < (P2 ≺ −P2 ) < · · · < (Pk ≺ −Pk ) < Q,
we then set
P1 ≺ P2 ≺ · · · ≺ Pk ≺ Q ≺ −Pk ≺ · · · ≺ −P2 ≺ −P1 .
Example 6.8. Let x2 = ((8, 7, 5))[4, 6, 3][2] be as in Figure 4. We have
({−8, −7, −5} ≺ {8, 7, 5}) < ({−1} ≺ {1}) < {±2, ±3, ±4, ±6},
Hence the order ≺ is given by
{−8, −7, −5} ≺ {−1} ≺ {±2, ±3, ±4, ±6} ≺ {1} ≺ {8, 7, 5}.
We use the order ≺ to define a permutation Sc (x) ∈ WDn in a similar way as
we did in type An . We first define a permutation Sc (x)′ as follows: if P is first
in the total order ≺, then we order the vertices of P as {d1 > d2 > · · · > dk >
−dk > · · · > −d2 > −d1 } and define Sc (y) on the subset {−n, . . . , −n + k − 1} by
−n 7→ d1 , . . . , −n + k − 1 7→ dk . We then consider the next Q appearing in ≺, and
define Sc (x) in the same way on the subset {−n + k, . . . , −n + k + ℓ − 1}, and so
on inductively.
Note that since P ≺ Q if and only if −Q ≺ −P , the permutation Sc (x)′ is
signed, but in some cases it might not lie in WDn . If Sc (x)′ ∈ WDn then we

26

THOMAS GOBET

set Sc (x) := Sc (x)′ . If Sc (x)′ does not lie in WDn , then in the line notation
π−n · · · π−1 π1 · · · πn of the permutation Sc (x)′ , we swap the two centermost entries,
that is, the entries π1 and π−1 to get a new line notation and define Sc (x) ∈ WDn
as the unique permutation having this line notation.
Example 6.9. Let x1 = ((3, −8))((7, 5, −2)) be as in Figures 4 and 5. The total
order < is given by
±{1} < ±{4} < ±{6} < ±{8, −3} < ±{2, −5, −7}.
The first half of the order ≺ is given by
{−1} ≺ {4} ≺ {6} ≺ {8, −3} ≺ {−7, −5, 2}.
We have {−1} ≺ {1}, hence we set Sc (x1 )′ (−n) = −1, (and therefore Sc (x1 )′ (n) =
1). Going on inductively, we get (in the line notation) a permutation
Sc (x1 )′ = (−1)468(−3)2(−5)(−7)75(−2)3(−8)(−6)(−4)1.
We have that |{i ∈ {1, . . . , n} | Sc (x1 )′ (i) < 0}| = 4, hence the above permutation
is in WDn and we set Sc (x1 ) = Sc (x1 )′ .
Using the characterization of c-sortable elements in type Dn given by [36,
Lemma 4.11], we see that Sc (y) is c-sortable. Moreover its cover reflections are
given by ((5, 7)), ((−2, 5)), ((3, −8)) (they are obtained as follows: if we denote the
line notation of the permutation by π−n · · · π−1 π1 · · · πn , then the cover reflections
are precisely those ((πi , πi+1 )) such that πi+1 > πi , where i = 1, . . . , n − 1, and
((π−1 , π2 )) in the case where π2 < π−1 ), which implies that Read(Sc (x1 )) = x1 .
This is a general fact, proven in Theorem 6.11 below.
Remark 6.10. The following can be checked by a direct computation. If s = si ,
i ≥ 2, then s is initial in c if and only if i ∈ Lc , i + 1 ∈ Rc . If i1 = 2, then s0 is
initial in c if and only if −1 ∈ Lc , while s1 is initial if and only if 1 ∈ Lc . If i1 = 1,
then s0 is initial in c if and only if s1 is initial in c, which happens if and only if
−2 is in Lc .
Theorem 6.11. Let x ∈ NC(WDn , c). The element Sc (x) ∈ WDn is c-sortable and
we have Read(Sc (x)) = x. That is, we have Sc = Read−1 .
Proof. Let x ∈ NC(WDn , c) and let y = Read−1 (x). We show by Cambrian recurrence that Sc (Read(y)) = y, which concludes: note that here the induction is on
the rank of a Coxeter group of type Dn and the length of Coxeter sortable elements inside it, i.e., if y is c-sortable in W we will assume that Sc′ (Read(y ′ )) = y ′
for every c′ -sortable element y ′ ∈ W with ℓ(y ′ ) < ℓ(y) and for every sortable element y ′ in a standard parabolic subgroup W ′ of W of type Dk , k < n (with
D1 = A1 , D2 = A1 × A1 , D3 = A3 ). If y = 1 then the claim is trivial. If y = s ∈ S,
then x has two polygons P1 = {i, i + 1}, P2 = {−i, −i − 1} with P2 ≺ P1 in the
case where s = si for some i ≥ 1. We have Read(y) = y and it follows from the
definition of Sc (y) that Sc (y) = y, which shows the claim. If y = s0 , then we
have two polygons P1 = (−1, 2), P2 = (1, −2). The pair is special and we have
P2 ≺ P1 . The permutation which we obtain as Sc (y)′ is (−2, 1, 2, −1), but this is
not in WDn hence to get Sc (y) we permute the two centermost entries in the line
notation of Sc (y)′ . This yields Sc (y) = y = s0 . If W has type A1 × A1 (here we
use the same graphical model with one simple reflection being s0 and the other
one being s1 ), then it is again easy to check the claim directly.
Now assume that ℓ(y) > 0. Let s be initial in c.

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

27

First case: sy > y. By Lemma 4.3, it implies that y and Read(y) ∈ W<s>
and that y is sc-sortable. We have Readc (y) = Readsc (y). We want to show
that Sc (Read(y)) = y. If W<s> is of type Dn−1 , then s = sn−1 and by induction we have that Ssc (Readsc (y)) = y. Now Readsc (y) = Readc (y) and this
noncrossing partitions fixes −n. It follows that Sc (Readc (y)) is obtained from
Ssc (Readsc (y)) by extending the permutation by a trivial action on {−n, n} which
shows the claim. Now assume that s = si , i ∈ {3, . . . , n − 1}. It follows that
W<s> is a product of a Coxeter group W1 of type Dk for some k ≥ 3 and
a Coxeter group W2 of type A. In this situation y decomposes uniquely as a
product y = y1 y2 with yi ∈ Wi and each yi is sortable in the corresponding
factor for the restrictions (sc)1 and (sc)2 of sc to these factors. We have that
Readc (y) = Readsc (y) = Read(sc)1 (y1 )Read(sc)2 (y2 ) (with Read(sc)i (yi ) ∈ Wi ) and
it is not difficult to observe by construction of the maps Sc′ (for various c′ here) that
Sc (Read(sc)1 (y1 )Read(sc)2 (y2 )) = S(sc)1 (Read(sc)1 (y1 ))S(sc)2 (Read(sc)2 (y2 )), where
S(sc)2 coincides with the map which we defined in type A (here W2 is isomorphic
to its restriction to the W2 -stable subset {i + 1, . . . , n}, which is isomorphic to the
symmetric group Sn−i . We use this identification implicitly). Hence by induction
on the rank together with the type A situation we get Sc (Read(y)) = y1 y2 = y.
The case where s = s2 is similar but with a Coxeter group of type A1 × A1 insted
of a Coxeter group of type Dn . In the case where s = s1 (resp. s = s0 ), the map
Ssc coincides with the map which we defined on a Coxeter group of type An−1 (in
this group the subset {1, . . . , n} (resp. {−1, 2, . . . , n}) is stable by the action of
every permutation, the isomorphism with Sn is immediate).
Second case: sy < y and s is a cover reflection of y. This precisely means that
s ≤T Read(y) (by Theorem 4.5), hence that s corresponds to a symmetric pair of
edges or diagonals of either a symmetric polygon Q or a pair P 6= −P of polygons
of x = Read(y) (if Q = −Q and s = s0 or s1 , we also call diagonal a segment
joining a vertex of Q to one of the middle points). The element sy is scs-sortable
by Lemma 4.4 and by induction on length we have that Sscs (Readscs (sy)) = sy.
Note that that Readscs (sy) = Read(y)s by [36, Lemma 6.5]. Hence to prove the
claim it suffices to show that
sSscs(Read(y)s) = Sc (Read(y)).
Assume that s = si , i ≥ 2. Then i ∈ Lc , i + 1 ∈ Rc (see Remark 6.10). Assume
that (i, i + 1) is a diagonal of a polygon P with P 6= −P of x = Read(y). The
scs-noncrossing partition Read(y)s is given by splitting P into two polygons P1 =
{j ∈ P | j > i + 1} ∪ {i} and P2 = {j ∈ P | j < i} ∪ {i + 1} (see Figure 7). But
the labeling corresponding to scs is obtained from that of c by moving i to Rc and
i + 1 to Lc . Hence if we compare the total order on polygons of Read(y) to that of
Read(y)s, in the case where P ≺ −P we get that P is replaced by P1 ≺ P2 (and −P
consistently) while everything else is unchanged: every polygon which is removed
before (resp. after) P in Read(y) stays removed before P1 (resp. after P2 ) in the
same order, while there can be nothing removed in between. Now if −P ≺ P ,
then −P is replaced by (−P2 ) ≺ (−P1 ). Hence in both cases, P is replaced by
P1 ≺ P2 . Moreover, if P = {d1 > ... > dℓ > i + 1 > i > dℓ+1 > · · · > dm }, then the
line notations of Sc (Read(y))′ and of Sscs (Read(y)s)′ coincide except in the entries
corresponding to P (and −P ), where in Sc (Read(y))′ we have
d1 · · · dℓ (i + 1)idℓ+1 · · · dm

28

THOMAS GOBET

while for Sscs (Read(y)s)′ we have
d1 · · · dℓ i(i + 1)dℓ+1 · · · dm
(and consistently for −P ). This shows that sSscs(Read(y)s)′ = Sc (Read(y))′ , which
implies that sSscs(Read(y)s) = Sc (Read(y)). Now if (i, i + 1) is a diagonal of
Q = −Q, the proof is similar and left to the reader (note that in that case Q is
central in the total order ≺).
Now assume that s = s0 and assume in addition that i1 = 2 (we then have
−1 ∈ Lc by Remark 6.10). If s is a diagonal of a symmetric pair of polygons
P 6= −P , then P is split into two polygons P2 , P1 as in the above case and
one checks that we get the same as in the case s = si , i ≥ 2: P is replaced by
P1 ≺ P2 while everything stays unchanged everywhere else (in that case passing from c to scs moves ±1 to the middle while 2 is moved to Lc ). Assume
that s corresponds to a pair of diagonals of Q = −Q. Note that Q is central
in the total order ≺ on Pol(Read(y)). Writing the permutation corresponding
to Q as (−j1 , . . . , −jℓ , j1 , . . . , jℓ )(2, −2) with ji ≥ 1, j1 = 1, ji < ji+1 , in the
graphical representation of Read(y)s we have that the polygon Q is replaced by a
pair of symmetric polygons P, −P with P = {j2 , . . . , jℓ , −j1 = −1, −2}. Now
in the labeling corresponding to scs, the indices 1 and −2 get moved as described above which yields P ≺ −P (P is strictly at the right of −P and the
pair cannot be special). Moreover, in the total order ≺ on the polygons, nothing
gets changed for the other polygons which Read(y) and Read(y)s have in commmon. Hence if we compare Sc (Read(y))′ with Sscs (Read(y)s)′ , there is only a
difference in the entries corresponding to Q / P ∪ −P , in the 4 centermost entries which in the first case are 21(−1)(−2) while in the second case they are
(−1)(−2)21. This shows that sSscs (Read(y)s)′ = Sc (Read(y))′ , which implies that
sSscs(Read(y)s) = Sc (Read(y)), which is precisely what we wanted to show. The
case s = s1 , as well as the cases where i1 = 1 are similar and left to the reader.
Third case: sy < y and s is not a cover reflection of y. It means that
s∈
/ ≤T Read(y), but y, Read(y) ∈
/ W<s> . Assume that s = si , i ≥ 2. In that case
by [36, Lemma 6.5] we have that Readscs (sy) = sRead(y)s. Let s = si , i ≥ 2.
We have i ∈ Lc , i + 1 ∈ Rc by Remark 6.10. If i ∈ P ∈ Pol(Read(y)), then
i + 1 ∈ Q ∈ P ol(Read(y)) with Q 6= P (otherwise we would have s ≤T Read(y)).
Note that the fact that Read(y) ∈
/ W<s> forces at least one polygon to have an
index ≤ i and another index ≥ i + 1. When passing from Read(y) to sRead(y)s,
the polygon P is replaced by a polygon P where the index i is replaced by i + 1,
and Q is replaced by Q where i + 1 is replaced by i (and −Q, −P are replaced
by −Q, −P ). Since the labeling for scs is the same as for c except that i ∈ Rscs
and i + 1 ∈ Lscs , it is easy to check (by distinguishing several possible relative
configurations of polygons) that the total order ≺ on polygons of Read(y) and
sRead(y)s is the same except that P, Q are replaced by P , Q (The condition that
there must be at least one polygon with an index ≤ i and another one ≥ i + 1 has
to be used here to check this fact, otherwise it can be wrong that the order after
overlining ±P, ±Q stays the same; note that the cases P = −P or Q = −Q can
appear. See Figure 8, where one of the situations is treated). It follows that the
entries corresponding to Sc (Read(y))′ and to Sscs(sRead(y)s)′ are the same except
that i and i + 1 are exchanged, hence that sSc (Read(y)) = Sscs (sRead(y)s), which
is what we have to show.

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS
b

b
b
b
b

b

b

2

−2
b
b

b
b
b
b
b

b

−8
−7
−6
−5
−4
−3

b

−1
1
3
4
5
6
7
8

b
b
b
b

b

b

2

−2
b
b

b
b
b
b
b

b

−8
−7
−6
−5
−4
−3

b

−1
1
3
4
5
6
7
8

29
−8
−7
−6
−5
−4
−3

b
b
b
b
b

b

b

2

−2
b
b

b
b
b
b
b

Figure 7. Illustration for the second case in the proof of Theorem 6.11.
Here we have s = s5 = (5, 6)(−5, −6), P = {−4, 5, 6, 7, 8} is a polygon
of Read(y) (on the left), which is split into two polygons P1 = {5, 7, 8},
P2 = {−4, 6} of Read(y)s (viewed as scs-noncrossing partition, on the right).
The total orders ≺ on polygons is the same except that P is replaced by
P1 ≺ P2 (and −P consistently).
Now assume that i1 = 1 and s = s0 , which implies that −2 ∈ Lc (see Remark 6.10). Again, the situation is such that −1 ∈ P , 2 ∈ Q with Q 6= P
(otherwise s ≤T Read(y)). The condition Read(y) ∈
/ W<s> guarantees that there
must be at least one polygon containing both positive and negative indices. Assume that P 6= −P ; the case where P = −P is similar and left to the reader.
Note that Q 6= −Q, otherwise ±1 ∈ Q (which implies that P = Q). In sRead(y)s,
we have that 1 ∈ Lc while the middle indices are ±2. To get sRead(y)s from
Read(y), one replaces the polygon P by a polygon P with 2 instead of −1, while
Q is replaced by a polygon Q with −1 instead of 2 (and −Q, −P are replaced by
−Q, −P ). We have to show that sSc (Read(y)) = Sscs (sRead(y)s) and we proceed as in the previous case to compare the order ≺ on Read(y) with the order
≺ on sRead(y)s. In most of the cases, the order ≺ on polygons of Read(y) after
overlining P and Q coincides with the order ≺ on polygons of sRead(y)s, but in
some situations it may happen that it is not the case; but in these situations, the
only difference is that the polygon P is reduced to the index {−1}, hence it is
directly followed in ≺ by −P , while {−2} = −P is directly followed in ≺ by P
(see Figure 9 for an example). Hence in that case, the two centermost entries in
the line notation of either Sc (Read(y)) or Sscs(sRead(y)s) (which correspond to
the indices of ±P and ±P respectively) have to be exchanged to get an element in
WDn . We graphically represented two of the various possible situations in Figure 9
and 10 and leave it to the reader to check it in all the other situations since this
is elementary geometry, depending on which polygon (among ±P , ±Q or another
one) has both positive and negative indices. It follows that in the line notation for
Sscs (sRead(y)s)′ and Sc (Read(y))′ , we have the same entries (up to permutation
of the two centermost entries in the case where one of the two permutations is not
in WDn ) except that 1 and −2 (and −1 and 2) are exchanged. This shows that
sSc (Read(y)) = Sscs (sRead(y)s).
The case s = s1 as well as the cases i1 = 2, s = s0 or s = s1 are similar, and
left to the reader.

The following two technical Lemmatas are type Dn analogues of Lemma 6.4.

−1
1
3
4
5
6
7
8

30

THOMAS GOBET
b
b
b
b
b
b
b
b
b
b
b
b

P
b

b
b

Q

b

b

−8
−7
−6
−5
−4
−3
−2
−1
1
2
3
4
5
6
7
8

−8
−7
−6
−5
−4
b
−3
−2
b
−1
1
2
3
b
4
Q 5
6
7
8

b
b
b
b
b

b
b
b

P
b

b
b
b

Figure 8. Illustration for the third case in the proof of Theorem 6.11. Here
s = s5 = (5, 6)(−5, −6). The order on the polygons of Read(y) (on the
left) is given in Example 6.9. In the notation of the proof we have P =
{−2, 5, 7}, Q = {6}, P = {−2, 6, 7}, Q = {5}. The order ≺ on the polygons
of sRead(y)s (represented on the right) is the same as the order on the
polygons of Read(y) except that P is replaced by P and Q by Q (and −P ,
−Q consistently).
b
b
b
b
b
b
b

P
b
b
b

Q
b

b
b
b
b
b

−8
−7
−6
−5
−4
−3
−2
−1
1
2
3
4
5
6
7
8

b
b
b
b
b
b
b
b
b
b

P
b

Q
b

b
b
b
b

−8
−7
−6
−5
−4
−3
−2
−1
1
2
3
4
5
6
7
8

Figure 9. Illustration for the third case in the proof of Theorem 6.11 in the
case where s = s0 . The first half of the order on the polygons of Read(y) (on
the left) is given by {−5} ≺ {4} ≺ Q ≺ {−3, 7, 8} ≺ P , while the first half of
≺ for sRead(y)s (on the right) is given by {−5} ≺ {4} ≺ Q ≺ {−3, 7, 8} ≺
−P . The order is hence not the same after overlining since in one case in
the middle we have P ≺ −P while in the second case we get −P ≺ P , but
to obtain Sc (Read(y)) from the order, the two centermost entries in the line
notation of Sc (Read(y))′ , which precisely correspond to the two indices in
−P and P = {−1}, must be exchanged.
Lemma 6.12. Let c be a Coxeter element, i ∈ {2, · · · , n} such that i ∈ Lc ∪ {i1 },
i + 1 ∈ Rc . Let j = c−1 (i), k = c−1 (i + 1). Assume that j ∈ P1 , k ∈ P2 , with
P1 6= P2 . Then P2 ≺ P1 .
Proof. If P1 = −P1 , then the claim is clear since P1 appears in the middle in the
order ≺ and the condition k ∈ P2 ∩ Rc forces it to be strictly at the right of the
diagonal (−j)j ∈ P1 , hence P2 ≺ −P2 . If P2 = −P2 , then P2 appears in the
middle in < and the condition j ∈ P1 ∩ Lc together with the fact that there are
no vertices on the circle between i + 1 and k forces −P1 ≺ P1 . So we can assume
that Pi 6= −Pi for i = 1, 2.
Note that under these assumptions, P2 is at the right of P1 : if the smallest index
ℓ of P1 is smaller than k then it is clear since the diagonal ℓk ∈ P1 is strictly at
the left of P2 , and if not it follows from the fact that there are no indices on the

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS
b
b
b
b

Q
b

b
b

P
b
b
b

b
b
b
b
b
b

−8
−7
−6
−5
−4
−3
−2
−1
1
2
3
4
5
6
7
8

b
b
b

Q
b

b
b
b
b
b
b

P

b

b
b
b
b
b

31

−8
−7
−6
−5
−4
−3
−2
−1
1
2
3
4
5
6
7
8

Figure 10. Illustration for the third case in the proof of Theorem 6.11 in
the case where s = s0 . The first half of the order on the polygons of Read(y)
(on the left) is given by {−5} ≺ {−3} ≺ Q ≺ −P, (note that the pair
{P, −P } is special with −P ≺ P ) while the first half of ≺ for sRead(y)s (on
the right) is given by {−5} ≺ {−3} ≺ Q ≺ −P . The order is hence the same
after overlining.
circle between k and i + 1 as well as between j and i. If P1 ∪ −P1 < P2 ∪ −P2
with −P1 ≺ P1 then the result holds by definition of ≺. Hence assume that
P1 ∪ −P1 < P2 ∪ −P2 and P1 ≺ −P1 . By definition of ≺, it means that P1 is
at the right of {P1 , P2 , −P2 } (note that {P1 , −P1 } cannot be special because we
would have that P1 contains the miminal index among those of P1 ∪ −P1 , which
would had to be negative because −j ∈ −P1 , and as a consequence P1 would
lie strictly at the left of P2 ). We consider the line segment L = j min(P1 ). If
ℓ := min(P1 ) ∈ {i + 1, . . . , j − 1}, then the horizontal line containing the point ℓ
can intersect no polygon distinct from P1 since j ∈ P1 and there are no indices
between j and i on the circle. Hence P1 is fully disjoint from any polygon with an
index smaller than ℓ, implying that −P1 is fully disjoint from any polygon with
an index bigger than −ℓ, contradicting P1 ≺ −P1 . Hence we can assume that
ℓ := min(P1 ) ∈ {k + 1, . . . , i} ∪ {j}. Since P1 ≺ −P1 , when removing P1 ∪ −P1 in
the definition of < we must have a polygon Q which is strictly at the right of −P1
(otherwise P1 and −P1 would be fully disjoint and since 0 ≤ j ∈ P1 , we would have
−P1 ≺ P1 , a contradiction). This implies that −Q is strictly at the left of P1 . But
the configuration of the indices is such that either −Q ⊆ {min(P1 )+1, . . . , i} ⊆ Lc ,
in which case we have Q ∪ −Q < P1 ∪ −P1 (because Q is in Rc and strictly at the
right of −P1 ), a contradiction, or min(Q) > j, in which case we would again have
Q ∪ −Q < P1 ∪ −P1 . Hence we got contradictions in all the cases.
We can therefore assume that P2 ∪ −P2 < P1 ∪ −P1 . If P2 ≺ −P2 then the
result holds. Assume that −P2 ≺ P2 . This means that −P2 is at the right of
−P1 , hence by symmetry that P2 is at the left of P1 , which (since P2 is also at the
right of P1 ) implies that P1 and P2 are fully disjoint. It follows that −P2 cannot
be strictly at the right to P1 , because in that case −P2 would have an index
ℓ > k, hence the diagonal (−k)ℓ ∈ −P2 would be strictly at the left of k ∈ P2
contradicting −P2 ≺ P2 . Hence one can assume that P1 is fully disjoint from both
P2 and −P2 , and therefore by symmetry we have that −P1 is also disjoint from
both P2 and −P2 . Arguing similarly as in the first case one sees that it contradicts
P2 ∪ −P2 < P1 ∪ −P1 .

Lemma 6.13. Let c be a Coxeter element. Assume that we are in one of the
following situations
• We have i1 = 2, 1 ∈ Lc , j = c−1 (1) with j ∈ P1 , −2 ∈ P2 and P2 6= P1 ,

32

THOMAS GOBET

• We have i1 = 2, −1 ∈ Lc , j = c−1 (−1) with j ∈ P1 , −2 ∈ P2 and P2 6= P1 ,
• We have i1 = 1, −2 ∈ Lc , k = c−1 (2) with k ∈ P2 , −1 ∈ P1 and P2 6= P1 ,
• We have i1 = 1, −2 ∈ Lc , k = c−1 (2) with k ∈ P2 , 1 ∈ P1 and P2 6= P1 .
Then P2 ≺ P1 .
Proof. The proof is similar to the proof of Lemma 6.12. We only prove it in the first
situation. Note that P1 6= −P1 , otherwise we would have ±i1 = ±2 ∈ P1 hence
P2 = P1 . If P2 ∪ −P2 < P1 ∪ −P1 with P2 ≺ −P2 then the result holds. Hence
assume that P2 ∪ −P2 < P1 ∪ −P1 with −P2 ≺ P2 , and find a contradiction. Note
that P2 6= −P2 since a symmetric polygon is bigger than any other pair in the order
<. By assumption we have that −P2 is at the right of every polygon in {±P1 , P2 }
except possibly P2 in the case where {±P2 } is a special pair. In particular −P2
is at the right of −P1 , hence since −j ∈ Rc we have min(−P2 ) > −j. We show
that −P2 and −P1 are fully disjoint. If this is not the case, then −P1 is strictly
at the left of −P2 , which implies that P1 is strictly at the right of P2 . But this
is impossible: the configuration of the indices on the circle would then imply that
−1 ∈ P1 (note that no index < −1 can be in P1 since P1 is strictly at the right
of P2 and P1 does not cross −P1 ; moreover we cannot have P1 = −P1 since we
would have P1 = P2 ), hence that the segment j(−1) is in P1 , contradicting the fact
that −P2 is at the right of everything unless −P2 = P1 . But in that case the pair
{±P2 } is special with P2 ≺ −P2 = P1 , a contradiction. Hence −P2 and −P1 are
fully disjoint, and the same holds for P2 and P1 . Note that the configuration of the
indices is such that we necessarily have −P1 ≺ P1 . We then argue as in the proof
of Lemma 6.4 in type An : we choose a sequence of polygons Q1 , . . . , Qm with −P2
strictly at the right of Q1 , ..., Qm strictly at the right of −P1 ; such a sequence
necessarily exists since −P2 and −P1 are fully disjoint but P2 ∪ −P2 ≺ P1 ∪ −P1
(and −Pi ≺ Pi for i = 1, 2). But this implies that {P2 , −P2 } is special with
P2 ≺ −P2 , a contradiction.
Now assume that P1 ∪ −P1 < P2 ∪ −P2 . If P2 = −P2 then we have −P1 ≺ P1
hence we can assume that P2 6= −P2 . If −P1 ≺ P1 then there is nothing to prove.
Hence assume that P1 ≺ −P1 and find a contradiction. It implies that P1 is at
the right of everything (except possibly −P1 in the case where the pair is special).
If P1 = −P2 one sees easily that −P1 ≺ P1 (including in the case where the pair
is special since j, 2 ∈ P1 ). Hence we can assume that P1 6= ±P2 . We show that
P1 and −P2 are fully disjoint. If not, then we necessarily have min(P1 ) = −1,
otherwise P1 crosses −P1 (and recall that P1 6= −P1 ). But in that case we have
P2 = {−2} since 2, j ∈ P1 , which implies that P2 is at the right of all the other
polygons among {±P1 , −P2 } and strictly at the right of −P1 , which is the only one
with a smaller minimal index, hence P2 ∪ −P2 < P1 ∪ −P1 , a contradiction. Hence
we can assume that P1 and −P2 are fully disjoint, hence that −P1 and P2 are also
fully disjoint. In particular P1 and −P1 are fully disjoint. If −P1 and −P2 are
not fully disjoint, then necessarily −P1 lies at the right of −P2 . This contradicts
P1 ≺ −P1 . Hence we can assume that −P1 and P2 are also fully disjoint. We then
have that −P1 is fully disjoint from both P2 and −P2 , and the configuration of
the indices then again implies that −P1 ≺ P1 .

We now prove Lemma 4.6 in type Dn .
Proof of Lemma 4.6 in type Dn . If s = si with i ≥ 2, then the proof works exactly
as in type An . Hence assume that s = s1 . If i2 = 2 then we have 1 ∈ Lc (see

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

33

Remark 6.10). We have x−1 sx = (x−1 (1), x−1 (2)). Arguing again as in the type
An proof we see that we have to show that Sc (y)−1 (y(j)) > Sc−1 (y(−2)), where
j is the index preceding 1 on the circle in clockwise order (that is, j = c−1 (1)).
Let P1 be the polygon of y containing j (and hence y(j)) and P2 be the polygon
containing −2 (and hence also y(−2)). If P1 = P2 then j(−2) is a diagonal of
P1 and we necessarily have y(j) < y(−2), hence Sc (y)−1 (y(j)) > Sc−1 (y(−2)) by
definition of Sc . Hence assume that P1 6= P2 . To show the claim it suffices to see
that P2 ≺ P1 . This is given by the first point of Lemma 6.13 above. The other
cases are done similarly and lead to all the situations treated in Lemma 6.13.

6.4. Type I2 (m). Let W = hs, ti be a finite dihedral group of type I2 (m), m ≥ 3.
Then every element except the longest one has a unique reduced expression. Let
c = st. The c-sortable elements are precisely e, w0 , t and those elements among the
remaining ones having their reduced expression beginning by s. The map Read is
given by Read(e) = e, Read(t) = t, Read(w0 ) = st = c and

st
· ·}·
if 1 ≤ k ≤ m

2,

| {z

2k−1 factors
Read( st
· ·}· ) =
| {z
if m > k > m
ts
· ·}·

2.
| {z


k factors
2(m−k)+1 factors

It follows that Sc ( st
· · · s} ) =
| {z
k factors

st
· · · s}
| {z

, 1 ≤ k ≤ 2m − 3, Sc (t) = t, Sc (e) = e,

(k+1)/2 factors

Sc (st) = w0 .

Proof of Lemma 4.6 in type I2 (m). Let c = st. The claim holds if y = e, t, st.
· · · s} , and
Hence assume that y = st
· ·}· , 1 ≤ k ≤ 2m − 3. We have x = st
| {z
| {z
k factors

x−1 sx =

k+2 factors

· · · s}
st
· · · s} . Assume that 1 ≤ k ≤ m. In that case, the words y = st
| {z
| {z

2k+3 factors

and Sc (y) =

· · · s}
|st {z

k factors

are both reduced. The set of inversions of y is given

(k+1)/2 factors

· · · s} }. It
by {s, sts, . . . , |st {z
· · · s} } and that of Sc (y) is given by {s, sts, . . . , |st {z
2k−1 factors

k factors

follows that if 2k + 3 < 2m, then x−1 sx is neither an inversion of y nor of Sc (y).
If k = m − 1, then x−1 sx = s which is an inversion of both y and Sc (y). If
k = m, then x−1 sx = sts and since m ≥ 3 it follows that x−1 sx is an inversion
of both y and Sc (y). Now assume that m ≤ k ≤ 2m − 3. Setting k′ = 2m − k
st
· · · s}
we have 3 ≤ k′ ≤ m and in that case we get Sc (y = ts
· · · }t ) =
| {z
| {z
k ′ factors

and

x−1 sx

=

st
· · · s}
| {z

. Note that we have that 2(m −

m−(k ′ −1)/2 factors

k′ )

+ 3 < 2m since

2(m−k ′ )+3 factors

3 ≤ k′ . We have that x−1 sx is an inversion of Sc (y) if and only if 2(m − k′ ) + 3 ≤
2(m − (k′ − 1)/2) − 1 = 2m − k′ , which happens if and only if k′ ≥ 3, hence
always. Now totally order the reflections of W a follows: s, sts, ststs, . . . . The
inversions of y are the k′ last reflections in this order, while x−1 sx appears in
position m − k′ + 2. In particular since there are m reflections, we have that x−1 sx
is always an inversion of y in that case. Hence x−1 sx is an inversion of both y and
Sc (y) in that case, showing the claim.


34

THOMAS GOBET

6.5. Types E, F, H. Lemma 4.6 was checked by computer in these types, using
the CHEVIE package of GAP 3.
7. Questions
We conclude by giving a list of questions related to this work.
Question 7.1. Is there a uniform proof of Lemma 4.6 ? It would give a uniform
proof of Theorem 5.10.
Question 7.2. Is there a uniform description of the map Sc : NC(W, c) −→
Sortc (W ) ?
Question 7.3. Can Theorem 5.10 be extended to some Artin-Tits groups of nonspherical type admitting a dual (quasi-) Garside structure ? Such structures exist
en and C
en (for suitable choices of Coxeter elements, see [17], [18]) and for
in types A
universal Coxeter groups [6]. A theory of c-sortable elements for infinite Coxeter
groups was developed in [38]. Note that an extension to these types would imply
that simple dual braids have a positive Kazhdan-Lusztig expansion (Corollary 5.9),
which is not known in these types since it is not known that simple dual braids
are Mikado braids (Theorem 5.8; note that here, one has to use the definition of
Mikado braids for general Artin-Tits groups, which was not given in this paper).
Indeed, there is no known topological or homological characterization of Mikado
en , C
en or for universal groups, which could be used to prove
braids in types A
Theorem 5.8 (similarly as in either [19], [4] or [34]).
References
[1] C.A. Athanasiadis and V. Reiner, Noncrossing partitions for the group Dn , SIAM J. Discrete
Math. 18 (2004), no. 2, 397-417 (electronic).
[2] B. Baumeister, M. Dyer, C. Stump, and P. Wegener, A note on the transitive Hurwitz action
on decompositions of parabolic Coxeter elements, Proc. Amer. Math. Soc. Ser. B 1 (2014),
149-154.
[3] B. Baumeister, T. Gobet, K. Roberts, and P. Wegener, On the Hurwitz action in finite
Coxeter groups, Journal of Group Theory 20 (2017), no.1, 103-131.
[4] B. Baumeister and T. Gobet, Simple dual braids, noncrossing partitions and Mikado braids
of type Dn , Bulletin of the LMS 49 (2017), no.6, 1048-1065.
[5] D. Bessis, The dual braid monoid, Ann. Sci. École Norm. Sup. 36 (2003), 647-683
[6] D. Bessis, A dual braid monoid for the free group, J. Algebra 302 (2006), no. 1, 55-69.
[7] D. Bessis, Finite complex reflection arrangements are K(π, 1), Annals of Math. 181 (2015),
Issue 3, 809-904.
[8] D. Bessis, F. Digne, and J. Michel, Springer theory in braid groups and the Birman-Ko-Lee
monoid, Pacific J. Math. 205 (2002), 287–309.
[9] P. Biane, Some properties of crossings and partitions, Discrete Math. 175 (1997), no. 1-3,
41-53.
[10] J. Birman, K.H. Ko, and S.J. Lee, A New Approach to the Word and Conjugacy Problems
in the Braid Groups, Adv. in Math. 139 (1998), 322–353.
[11] A. Björner and F. Brenti, Combinatorics of Coxeter groups, GTM 231, Springer, 2005.
[12] N. Bourbaki, Groupes et algèbres de Lie, chapitres 4,5 et 6, Hermann (1968).
[13] T. Brady and C. Watt, Non-crossing partition lattices in finite real reflection groups, Trans.
Amer. Math. Soc. 360 (2008), no. 4, 1983-2005.
[14] T. Brady and C. Watt, A partial order on the orthogonal group, Comm. Algebra 30 (2002),
no. 8, 3749-3754.
[15] N. Brady, J.P. McCammond, B. Mühlherr, and W.D. Neumann, Rigidity of Coxeter Groups
and Artin Groups, Geometriae Dedicata 94 (2002), Issue 1, 91-109.
[16] R.W. Carter, Conjugacy Classes in the Weyl group, Compositio Math. 25 (1972), 1-59.
[17] F. Digne, Présentations duales des groupes de tresses de type affine Ã, Comment. Math.
Helv. 81 (2006), no. 1, 23-47.

DUAL GARSIDE STRUCTURES AND COXETER SORTABLE ELEMENTS

35

[18] F. Digne, A Garside presentation for Artin groups of type C̃n , Ann. Inst. Fourier 62 (2012),
no. 2, 641-666.
[19] F. Digne and T. Gobet, Dual braid monoids, Mikado braids and positivity in Hecke algebras,
Math. Z. 285 (2017), no. 1-2, 215-238.
[20] P. Dehornoy, Three-dimensional realizations of braids, J. London Math. Soc. 60 (1999),
108-132.
[21] P. Dehornoy, F. Digne, D. Krammer, E. Godelle, and J. Michel. Foundations of Garside
theory, Tracts in Mathematics 22, Europ. Math. Soc. (2015).
[22] M.J. Dyer, Hecke algebras and reflections in Coxeter groups, Ph. D. Thesis, University of
Sydney (1987).
[23] M.J. Dyer, Reflection subgroups of Coxeter systems, J. Algebra 135 (1990), Issue 1, 57-73.
[24] M.J.
Dyer,
Modules
for
the
dual
nil
Hecke
ring,
http://www3.nd.edu/~dyer/papers/nilhecke.pdf.
[25] M.J. Dyer, On minimal lengths of expressions of Coxeter group elements as products of
reflections, Proc. Amer. Math. Soc. 129 (2001), no. 9, 2591-2595.
[26] M.J. Dyer and G.I. Lehrer, On positivity in Hecke algebras, Geom. Ded. 25 (1990), 115-125.
[27] T. Gobet, Noncrossing partitions, fully commutative elements and bases of the TemperleyLieb algebra, J. Knot Theory Ramif. 26 (2016), 27 pp.
[28] T. Gobet, Twisted filtrations of Soergel bimodules and linear Rouquier complexes, J. Algebra
484 (2017), 275-309.
[29] T. Gobet, On cycle decompositions in Coxeter groups, Sém. Lothar. Comb. 78 B (2017),
Art. 45, 12 pp.
[30] T. Gobet and N. Williams, Noncrossing partitions and Bruhat order, European J. Combin.
53 (2016), 8-34.
[31] A. Hubery and H. Krause, A categorification of non-crossing partitions, J. Eur. Math. Soc.
(JEMS) 18 (2016), no. 10, 2273-2313.
[32] J. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics 29, Cambridge University Press (1990).
[33] L.T. Jensen, The 2-braid group and Garside normal form, Math. Z. 286 (2017), no. 1-2,
491-520.
[34] T. Licata and H. Queffelec, Braid groups of type ADE, Garside structures, and the categorified root lattice, preprint (2017), https://arxiv.org/pdf/1703.06011.pdf.
[35] L. Paris, Artin monoids inject in their groups, Comment. Math. Helv. 77 (2002), no. 3,
609-637.
[36] N. Reading, Clusters, Coxeter-sortable elements and noncrossing partitions, Trans. Amer.
Math. Soc. 359 (2007), no. 12, 5931-5958.
[37] N. Reading, Noncrossing partitions and the shard intersection order, J. Algebraic Combin.
33 (2011), no. 4, 483-530.
[38] N. Reading and D.E. Speyer, Sortable elements in infinite Coxeter groups, Trans. Amer.
Math. Soc. 363 (2011), no. 2, 699-761.
[39] V. Reiner, V. Ripoll, and C. Stump, On non-conjugate elements in well-generated reflection
groups, Math. Z. 285 (2017), no. 3-4, 1041-1062.
Thomas Gobet, School of Mathematics and Statistics F07, University of Sydney
NSW 2006, Australia.
E-mail address: thomas.gobet@sydney.edu.au

