arXiv:1803.02639v2 [] 8 Mar 2018

GARSIDE COMBINATORICS FOR THOMPSON’S MONOID F +
+
AND A HYBRID WITH THE BRAID MONOID B∞
PATRICK DEHORNOY AND EMILIE TESSON
Abstract. On the model of simple braids, defined to be the left divisors of
+
Garside’s elements ∆n in the monoid B∞
, we investigate simple elements in
+
+
Thompson’s monoid F and in a larger monoid H + that is a hybrid of B∞
and F + : in both cases, we count how many simple elements left divide the
right lcm of the first n − 1 atoms, and characterize their normal forms in terms
of forbidden factors. In the case of H + , a generalized Pascal triangle appears.

1. Introduction
Since the seminal work of F.A. Garside [18], as extended in [16] and [4], it is
known that Artin’s braid group Bn is a group of fractions for the monoid Bn+
of positive n-strand braids and that the now called Garside element ∆n plays a
prominent role in the study of Bn+ . In particular, the divisors of ∆n in Bn+ , called
simple braids, form a family of n! elements in one-to-one correspondence with the
permutations of {1, ..., n}, leading to a remarkable combinatorics now at the heart
of the algebraic study of Bn [1, 17], see [15, Chapter IX]. Subsequently, it was
realised that such a situation can be found in many different contexts of groups and
categories, always around a family of so-called simple elements resembling simple
braids, and leading to various combinatorics, like, for instance, the dual Garside
structure on Bn [3], whose combinatorics is that of noncrossing partitions.
Our aim in this paper is to investigate a Garside structure arising on Thompson’s
group F [28, 8] in connection with its submonoid F + generated by the standard
(infinite) sequence of generators, corresponding to the presentation
(1.1)

F + := hτ1 , τ2 , ... | τj τi = τi τj+1

for

j > i + 1i+ .

To explain the similarity with braids and the natural questions in this non-finitely
generated case, one should start from the infinite braid monoid

+
σj σi = σi σj
for j > i + 2
+
(1.2)
B∞ = σ1 , σ2 , ...
:
σj σi σj = σi σj σi for j = i + 1
in this case, Garside’s braid ∆n is the right lcm of the n − 1 first atoms σ1 , ..., σn−1
+
of B∞
(see Section 2.1 for a reminder about the terminology), and simple braids
+
are those braids that left divide at least one element ∆n in B∞
.
+
In the case of the monoid F , the atoms are the elements τi , and we shall see that
there exists for each n a well defined element ∆n that is, in F + , the right lcm of the
first n−1 atoms. Then we shall investigate the derived simple elements, namely the
elements of F + that left divide at least one element ∆n . The main results proved
1991 Mathematics Subject Classification. 05E15, 20M05, 20E22, 68Q42.
Key words and phrases. presented monoid; divisibility relation; simple elements; Thompson’s
group; braid group; normal form; Garside element; directed animal.
1

2

PATRICK DEHORNOY AND EMILIE TESSON

here are that, for every n, there exist 2n−1 simple elements left dividing ∆n in F + ,
in explicit one-to-one correspondence with the subsets of {1, ..., n − 1}, and that
simple elements form a Garside family in F + [15, Def. III.1.31], thus guaranteeing
the existence and properties of an associated greedy normal form in F + . These
results are established by combining the existence of a convergent rewrite system
on F + and the reversing technique [10, 12] for analyzing the divisibility relations
of a presented monoid.
The above results are technically easy, and we then switch to a combinatorially
more involved situation related to another monoid H + , which is a hybrid of the
+
braid monoid B∞
and the Thompson monoid F + . Various hybrids of the groups B∞
d of [5, 6, 11], which is
and F have already been considered, in particular the group BV
+
a group of fractions for a monoid, that is a Zappa-Szép product of F + and B∞
and,
therefore, inherits their Garside structures. Here we shall introduce and investigate
a new hydrid, which is not a product but rather a mixture of the initial monoids F +
+
and B∞
. Indeed, we consider
+

θj θi = θi θj+1
for j > i + 2
(1.3)
H + := θ1 , θ2 , ...
,
θj θi θj = θi θj θi+3 for j = i + 1
in which the length 2 relations are Thompson’s relations as in (1.1), whereas the
length 3 relations are directly reminiscent of braid relations of (1.2), but with a
shift of one index. Here, we investigate the basic properties of the monoid H + and,
specifically, the associated Garside combinatorics, if this makes sense. Actually, it
does: we shall see that, for every n, the atoms θ1 , ..., θn−1 admit a right lcm, again
denoted by ∆n , so that it is natural to investigate simple elements, defined to be
those that left divide some element ∆n . The main results proved here are that,
for every n, there exist 2 · 3n−2 simple elements left dividing ∆n in H + , with an
explicit description of a distinguished expression for each of them. As in the case
of F + , these results are established using a convergent rewrite system on H + and
the reversing technique; the proofs are more difficult than for F + and some of them
require delicate inductive arguments. We hope that the existence of this nontrivial
combinatorics will draw some attention to the monoid H + , and to the group H
presented by (1.3), which remains essentially mysterious.
The paper is divided into four sections after this introduction. In Section 2,
we investigate the monoid F + and the derived simple elements, providing a good
warm-up for the sequel. In Section 3, we establish various general properties of
the monoid H + , in particular the fact that it admits cancellation on both sides.
Next, in Section 4, we study the elements ∆n of H + and count their left divisors
by partitioning them into several families. Finally, in Section 5, we explicitly characterize the normal form (in the sense of some convergent rewrite system) of simple
elements of H + .
Acknowledgement. The authors thank Matthieu Picantin for having pointed at
the connection between the numbers Nk,ℓ of Section 4.3 and directed animals.
2. Thompson’s monoid F +
Here we study the case of Thompson’s monoid F + , an easy first step. It is
standard that (1.1) is a presentation of Thompson’s group F , and, as the relations
involve no inverse of the generators, it makes sense to introduce the associated
monoid F + and to consider the associated Garside combinatorics, if it exists.

+
GARSIDE COMBINATORICS FOR F + AND A HYBRID WITH B∞

3

The section is divided into four parts. In Section 2.1, we recall the standard
terminology for the divisibility relations in a monoid, extensively used throughout
the text. Next, in Section 2.2, we define a convergent rewrite system that selects
a distinguished expression for every element of F + . In Section 2.3, we recall basic
notions about word reversing, here in the new version of [14], and use them to
show that F + is cancellative and admits right lcms (least common right multiples).
Finally, in Section 2.4, we investigate the elements ∆n and describe their left divisors
explicitly.
2.1. The divisibility relations of a monoid. Let M be a monoid (possibly, in
particular, a free one, i.e., a monoid of words). For a, b in M , we say that a left
divides b in M , or, equivalently, that b is a right multiple of a, written a 4 b, if
ax = b holds for some x (of M ). If M is left cancellative (meaning that xa = xb
implies a = b) and 1 is the only invertible element in M , the relation 4 is a partial
ordering on M .
For a, b in M , we say that c is a right lcm (least common right multiple) of a
and b if a 4 c and b 4 c hold, and the conjunction of a 4 x and b 4 x implies c 4 x:
in other words, c is a lowest upper bound of a and b with respect to 4.
The symmetric notions of a right divisor and a left multiple are defined similarly,
replacing ax = b with xa = b. Finally, we say that a is a factor of b if xay = b
holds for some x, y.
An element a of M is said to be an atom if it admits no decomposition a = bc
with b 6= 1 and c 6= 1.
2.2. A normal form on F + . We begin our investigation of the monoid F + . We
recall that F + is defined by the presentation
F + := hτ1 , τ2 , ... | τj τi = τi τj+1

for

j > i + 1i+ ,

hereafter denoted by PF . We put T := {τi | i > 1}, write T ∗ for the free monoid
of all words in the alphabet T , and ≡ for the congruence on T ∗ generated by the
relations of PF . We use ε for the empty word. Our first tool for studying F +
consists in defining a unique normal form using a rewrite system on T ∗ .
Lemma 2.1. Let EF be the rewrite system on T ∗ defined by the rules
(2.1)

τi τj+1 → τj τi

for i > 1 and j > i + 1.

Then EF is convergent.
Proof. As is standard, see for instance [26], we shall check that EF is noetherian
and locally confluent. We write ⇒ for the one-step rewrite relation associated with
the rules of (2.1), that is, for the family of all pairs
(w1 τi τj+1 w2 , w1 τj τi w2 ) with j > i + 1,
and ⇒∗ for the reflexive–transitive closure of ⇒. For w in T ∗ , let ρ(w) be the sum of
the indices of the generators τi occurring in w. Then w ⇒ w′ implies ρ(w) > ρ(w′ ),
and, therefore, there is no proper infinite sequence for ⇒. So EF is noetherian.
Next, assume w ⇒ w′ and w ⇒ w′′ . By definition, w′ and w′′ are obtained
from w by replacing some length 2 factor τi τj+1 with the corresponding word τj τi .
For local confluence, the case of disjoint factors is trivial, and the critical case of

4

PATRICK DEHORNOY AND EMILIE TESSON

overlapping factors corresponds to w = τi τj+1 τk+2 with j > i + 1 and k > j + 1,
leading to w′ = τj τi τk+2 and w′′ = τi τk+1 τj+1 . One then obtains
τj τi τk+2 ⇒
2
⇒
τk τj τi ,
(2.2)
τi τj+1 τk+2
2
⇒
⇒
ττ
τ
i k+1 j+1

It follows that EF is locally confluent, hence convergent by Newman’s diamond
lemma [22].

For every word w of T ∗ , we shall denote by red(w) the unique EF -reduced word w′
satisfying w ⇒∗ w′ . By definition, the words w and red(w) represent the same
element of F + , and red(w) is the unique EF -reduced word in the equivalence class
of w in F + . Thus, Lemma 2.1 implies
Proposition 2.2. EF -reduced words provide a unique normal form for the elements
of the monoid F + .
It directly follows from the definition that a word of T ∗ is EF -reduced if, and only
if, it has no length 2 factor τi τj+1 with j > i + 1, which implies that, for every n,
the set of EF -reduced words lying in {τ1 , ..., τn }∗ is a regular language [17, 20].
2.3. Using word reversing. The second method for investigating the monoid F +
is word reversing [12], a distillation of an argument that ultimately stems from
Garside’s approach to braid monoids [18]. Here we shall describe reversing using
the new formalism of [14], which is specially convenient in the current case (and in
that of H + in Section 3.3). So we introduce reversing as a binary relation on pairs
of words connected with a particular type of van Kampen diagram.
Definition 2.3. [14] A reversing grid for a monoid presentation (S, R), or (S, R)grid, is a rectangular diagram consisting of finitely many matching S ∪ {ε}-labeled
pieces of the types
t
s1
with s, t, s1 , ..., sp , t1 , ..., tq in S
-s
and st1 ··· tq = ts1 ··· sp a relation of R,
tq s p
t1
s
- s

ε
ε,

s

t
s,

ε
ε,

ε

ε

ε

with s, t in S.

ε
ε
ε
t
∗
For u, v, u1 , v1 in S , we say that an (S, R)-grid Γ goes from (u, v) to (u1 , v1 ) if the
labels of the left and top edges of Γ form the words u and v, respectively, whereas
the labels of the right and bottom edges form the words u1 and v1 . We write
(u, v) yR (u1 , v1 ) if there exists a (S, R)-grid from (u, v) to (u1 , v1 ).
Example 2.4. Two typical PF -grids are
τ1
τ3
(2.3)

τ2

τ3

ε,

τ2
τ2

τ1
ε

ε,

τ1
ε
ε
τ1
witnessing for the relations (τ2 , τ1 τ3 ) y (ε, τ1 ) and (τ2 , τ2 τ1 ) y (ε, τ1 ), respectively—
we omit the index in y when there is no ambiguity. Note that, because all relations

+
GARSIDE COMBINATORICS FOR F + AND A HYBRID WITH B∞

5

of PF involve words of length 2, the pieces of the first type in Definition 2.3 are
squares: the right and bottom edges each consist of one single S-labeled arrow.
The following result is (a special case of a result) established in [14]. Below we
say that a monoid presentation (S, R) is homogeneous if every relation in R has the
form w = w′ with w, w′ of the same length, and right complemented if it contains
no relation s... = s... and at most one relation s... = t... for all s 6= t in S. On the
other hand, two (S, R)-grids Γ from (u, v) to (u1 , v1 ) and Γ′ from (u′ , v ′ ) to (u′1 , v1′ )
are equivalent if we have u′ ≡R u, v ′ ≡R v, u′1 ≡R u1 , and v1′ ≡R v1 , where ≡R is
the congruence on S ∗ generated by R—so that the monoid hS | Ri+ is S ∗ /≡R .
Lemma 2.5. [14, Propositions 1.12, 1.14, 1.16] Assume that (S, R) is a homogeneous right complemented monoid presentation and, for every s in S and every
relation w = w′ in R,
′
(♦) for every grid from (s, w), there is an equivalent grid from (s, w ),
and vice versa.
(i) Two words u, v of S ∗ represent the same element of the monoid hS | Ri+ if,
and only if, (u, v) y (ε, ε) holds.
(ii) The monoid hS | Ri+ is left cancellative.
(iii) Two elements a, b of hS | Ri+ represented by u and v in S ∗ admit a common
right multiple if, and only if, (u, v) yR (u1 , v1 ) holds for some u1 , v1 ; in this case,
the element represented by uv1 is a right lcm of a and b. In the special case when,
for all s 6= t in S, there exist s′ , t′ in S such that st′ = ts′ is a relation of R, there
always exist u1 , v1 as above, and any two elements of hS | Ri+ admit a right lcm.
Applying Lemma 2.5, we deduce:
Proposition 2.6. The monoid F + is left and right cancellative. Any two elements
of F + admit a right lcm. Any two elements of F + that admit a common left multiple
admit a left lcm.
Proof. In view of applying Lemma 2.5, we observe that the presentation PF is homogeneous (all relations are of the form w = w′ with w and w′ of length two), right
complemented with one relation τi ... = τj ... for all i, j, and that Condition (♦) holds
for every τi and every relation of PF . To this end, we consider all pairs (τi , τj τk+1 )
with k > j +1, and compare the reversing grids from (τi , τj τk+1 ) and from (τi , τk τj ):
the two grids of Example 2.4 are typical, corresponding to i = 2, j = 1, and k = 2,
and they are indeed equivalent, since both admit as output (ε, τ1 ). The number
of triples (i, j, k) to consider is infinite but only finitely many patterns may occur,
according to the position of i with respect to j and k. We skip the details, which
are fairly obvious. Having established (♦), we deduce from Lemma 2.5(ii) that
the monoid F + is left cancellative and from Lemma 2.5(iii) that any two elements
of F + admit a right lcm.
To study left multiples, we observe that the presentation PF is also left complemented (in the obvious sense), and consider the notion of a left reversing grid,
which is symmetric to the above notion of a right reversing grid (which amounts to
considering the opposed monoid). To this end, we replace each elementary diagram
tq
t1
t
s1

s

sp
t1

tq

of Definition 2.3 with its counterpart

s1

s for

sp
t

6

PATRICK DEHORNOY AND EMILIE TESSON

s
s1 ··· sp t = t1 ··· tq s in R and, similarly, replace s

ε
ε with ε

s. Then

ε
s
one easily checks that the counterpart of (♦) is satisfied and one deduces, by the
counterpart of Lemma 2.5(ii), that F + is right cancellative. Finally, the counterpart of Lemma 2.5(iii) implies that any two elements of F + that admit a common
left multiple admit a left lcm. However, two elements of F + need not always admit
a common left multiple: there is no relation ...τ1 = ...τ2 in PF , and, therefore, the
counterpart of Lemma 2.5(iii) implies that τ1 and τ2 admit no common left-multiple
in F + .

It follows from Proposition 2.6 and Ore’s classical theorem [23] that the monoid F +
embeds in its enveloping group, which is the group presented by PF , namely Thompson’s group F , and that the latter is a group of right fractions for F + , that is, every
element of F can be expressed as ab−1 with a, b in F + . The expression is unique
if, in addition, we require that the fraction be irreducible, meaning that a and b
admit no common right divisor.
Remark 2.7. As explained in [13], there exists a (more redundant) positive presentation PF∗ of the group F in terms of a family of generators τs∗ with s a finite
sequence of 0s and 1s such that τi coincides with τ1∗i−1 and that F is a group both
of left and right fractions for the monoid F +∗ defined by PF∗ . The latter admits left
and right lcms and is a sort of counterpart for the dual braid monoid of [3]. The
main relations in PF∗ correspond to the MacLane–Stasheff pentagon.
2.4. Garside combinatorics for F + . The monoid F + resembles the braid mon+
oid B∞
in that it is cancellative and admits right lcms and, therefore, it makes
sense to consider the counterpart of the Garside elements ∆n and their divisors.
As the presentation PF is homogeneous, the atoms of F + are the elements τi
+
, we shall consider the element ∆n that
with i > 1. So, exactly as in the case of B∞
is the right lcm of τ1 , ..., τn−1 —we might use a different notation, for instance ∆F
n,
but there will be no risk of ambiguity here. We start from an explicit expression.
Definition 2.8. We put ∆1 := ε, and, for n > 2, we put ∆n := τ1 τ3 τ5 ··· τ2n−3 .
We denote by ∆n the class of ∆n in F + .
It is clear that ∆n left divides ∆n+1 for each n, and one inductively checks that
the EF -normal form of ∆n is τn−1 τn−2 ··· τ2 τ1 .
Lemma 2.9. For every n > 2, the element ∆n is the right lcm of τ1 , ..., τn−1 . No
element τi with i > n left divides ∆n .
Proof. We prove using induction on n > 2 that ∆n is the right lcm of τ1 , ..., τn−1 .
The result is trivial for n = 2. Assume n > 3. A direct computation gives
(τn−1 , ∆n−1 ) y (τ2n−3 , ∆n−1 ).
By Lemma 2.5(iii), this implies that ∆n represents the right lcm of τn−1 and ∆n−1 .
By induction hypothesis, ∆n−1 is the right lcm of τ1 , ..., τn−2 , so ∆n is the right lcm
of τ1 , ..., τn−1 . On the other hand, for i > n, we find (τi , ∆n ) y (τi+n−1 , ∆n ), which
shows that the right lcm of τi and ∆n is not ∆n , so τi does not left divide ∆n . 
The main notion in Garside theory [15] is the notion of a simple element, defined
as the (left) divisors of the distinguished element(s) ∆.

+
GARSIDE COMBINATORICS FOR F + AND A HYBRID WITH B∞

7

Definition 2.10. An element a of F + is called simple if a 4 ∆n holds for some n.
Our aim is to understand the structure of simple elements of F + , typically to
characterize their normal forms. To this end, the key point will be the following
exhaustive description of the expressions of ∆n . Below, we write Sn for the group
of all permutations of {1, ..., n}, and si for the transposition (i, i + 1).
Lemma 2.11. The expressions of ∆n are the words wf with f in Sn−1 , where,
for p 6 n − 1, we put
fb(p) := #{i < f −1 (p) | f (i) > p} and fe(p) := 2f −1 (p) − 1 − fb(p),

and let wf be the word τfe(1) τfe(2) ··· τfe(n−1) .

Proof. We first establish the following technical result:
(2.4)

If f −1 (p) < f −1 (p + 1) (resp., >) holds, then so does fe(p) + 1 < fe(p + 1)
(resp., fe(p) > fe(p + 1)); applying a relation of PF to wf in position p
yields the word wsp f .

So assume f −1 (p + 1) = f −1 (p) + m with m > 1. The definition gives
fb(p + 1) = fb(p) + #{i | f −1 (p) < i < f −1 (p + 1) and f (i) > p + 1},

whence fb(p + 1) 6 fb(p) + m − 1 and, for there, fe(p + 1) > fe(p) + 2. Let g := sp f .
We find g −1 (p) = f −1 (p + 1), g −1 (p + 1) = f −1 (p), then b
g(p) = fb(p + 1) + 1 and
g(p + 1) = fb(p), because f −1 (p) contributes to gb(p) but not to fb(p + 1), and, finally,
b
g(p) = fe(p + 1) − 1 and ge(p + 1) = fe(p), with e
e
g(q) = fe(q) for q 6= p, p + 1. So wg is
the result of applying the rule τfe(p) τfe(p+1) → τfe(p+1)−1 τfe(p) to wf in position p.
On the other hand, for f −1 (p) = f −1 (p+1)+m with m > 1, we find fb(p) 6 fb(p+
1)+m, leading to fe(p) > fe(p+1)+1. For g := sp f , we find now, gb(p) = fb(p+1) and
g(p+1) = fb(p)−1, whence ge(p) = fe(p+1) and ge(p+1) = fe(p)+1, with ge(q) = fe(q)
b
for q 6= p, p+1. So wg is the result of applying the rule τfe(p) τfe(p+1) → τfe(p+1) τfe(p)+1
to wf in position p.
Now, (2.4) implies that the family W := {wf | f ∈ Sn−1 } is closed under ≡.
As the transpositions si generate Sn−1 , this family W is the ≡-equivalence class

of the word wid , which, by definition, is ∆n .
From there, a complete description of simple elements of F + follows:
Proposition 2.12. For every a in F + , the following are equivalent:
(i) The element a is simple, i.e., a left divides some element ∆n ;
(ii) The element a is a factor of some element ∆n ;
(iii) The normal form of a has the form τi1 ··· τiℓ with i1 > ··· > iℓ .
Moreover, a left divides ∆n if, and only if, nf(a) is τi1 ··· τiℓ with n > i1 > ··· > iℓ .
Proof. By definition, (i) implies (ii). Next, assume that a is a factor of ∆n , say
∆n = a1 aa2 . Let w1 , w, w2 be the normal forms of a1 , a, and a2 , respectively.
Then w1 ww2 is an expression of ∆n , so, by Lemma 2.11(ii), it is a word wf for
some permutation f . Moreover, because w is EF -reduced, no rule of EF may apply
to it: by (2.4), this implies that the indices of the generators τi in w make a
decreasing sequence. So (ii) implies (iii).
Assume now w = τi1 ··· τiℓ with i1 > ··· > iℓ . By inserting intermediate letters
when ip > ip+1 + 2, we obtain a word w′ that is the normal form of ∆i1 +1 . Then,

8

PATRICK DEHORNOY AND EMILIE TESSON

repeatedly applying to w′ some relations τi τj → τj τi+1 , we push the new letters to
the right starting with the last one and finishing with the first one. In this way, one
obtains a new expression of ∆i1 +1 that begins with w. So w is the normal form of
a prefix of ∆i1 +1 , hence of a simple element. Si (iii) implies (i).
For the last sentence, if a left divides ∆n , then so does the first generator of nf(a):
by Lemma 2.9, the latter cannot be τi with i > n. Conversely, the above proof of

(iii) ⇒ (i) shows that τi1 ··· τiℓ left divides ∆i1 +1 , hence ∆n for n > i1 .
Corollary 2.13. (i) For every n, the number of left divisors of ∆n in F + is 2n−1 .
(ii) Simple elements of F + make a Garside family in F + .
Proof. (i) By the last statement in Proposition 2.12, mapping a subset of {1, ..., n−1}
to the decreasing enumeration of the corresponding elements τi establishes a oneto-one correspondence between P({1, ..., n − 1}) and the left divisors of ∆n .
(ii) By definition, the family of simple elements in F + is closed under right lcm:
the conjunction of a 4 ∆n and b 4 ∆p implies that the right lcm of a and b left
divides ∆max(n,p) . On the other hand, a right divisor of a simple element must be a
factor of some ∆n , hence, by Proposition 2.12, it is simple. By [15, Coro. IV.2.29],
this implies that simple elements form a Garside family.

As simple elements form a Garside family, every element of F + admits a unique
greedy decomposition in terms of simple elements, namely a decomposition a1 , ..., ap
with a1 , ..., ap simple, ap 6= 1, and, for each i, the entry ai is the maximal simple left
divisor of ai ··· ap , [15, Prop. IV.1.20]. In the current case, the greedy decomposition
is directly connected with the EF -normal form: nf(a1 ), ..., nf(ap ) are the maximal
decreasing factors of nf(a). For instance, for nf(a) = τ4 τ3 τ2 τ3 τ1 τ1 τ2 , the greedy
decomposition has four entries, namely τ4 τ3 τ2 , τ3 τ1 , τ1 , and τ2 .
From there, all results involving greedy decompositions are valid in F + . However,
this Garside structure of F + is mostly trivial, exactly parallel to the case of the free
(∞)
commutative monoid Z>0 , where simple elements also correspond to finite subsets
of generators. In fact, the relations of PF are in essence a shifted version of the
commutation rules of a free commutative monoid.
3. The monoid H +
The previous results are elementary and easy, and we now switch to a combinatorially more intricate and interesting situation, connected with the new hybrid H +
+
between Thompson’s monoid F + and Artin’s braid monoid B∞
mentioned in the
introduction. Our aim will be to develop the same analysis as in the case of F + ,
namely understanding the structure of simple elements, defined as the left divisors
of the right lcms of atoms. To this end, we shall follow the same scheme as in Section 2 and use both a normal form associated with a rewrite system (Section 3.2)
and the reversing transformation associated with the presentation (Section 3.3).
3.1. Presentation and first properties. We recall that H + is the monoid defined by the explicit presentation called (1.3) in the introduction

+
θj θi = θi θj+1
for j > i + 2
H + := θ1 , θ2 , ...
,
θj θi θj = θi θj θi+3 for j = i + 1
hereafter denoted by PH . We put Θ := {θi | i > 1}, and write ≡ for the congruence
on Θ∗ generated by the relations of PH . For w a word of Θ∗ , we write [w] for

+
GARSIDE COMBINATORICS FOR F + AND A HYBRID WITH B∞

9

the ≡-class of w. The relations of PH should appear as a mixture of the Thompson
relations (as for length 2 relations), and of braid relations (as for length 3 relations).
We immediately see that PH is a homogeneous presentation, and we can refer
without ambiguity to the length |a| of an element a of H + , defined to be the
common length of all words of Θ∗ that represent a. We also observe that the
relations are invariant under shifting the indices of the θi s by +1, implying that
mapping θi to θi+1 for each i induces a well defined endomorphism of H + .
+
Unlike the case of B∞
, the family of generators occurring in a word is not
invariant under ≡: for instance, θ3 θ1 is equal to θ1 θ4 . However, we can easily
construct an upper bound on the indices of the generators possibly occurring in the
expressions of an element.
Lemma 3.1. Define the ceiling ⌈w⌉ of a nonempty word w = θi1 ··· θiℓ of Θ∗ by
(3.1)

⌈w⌉ := max{ip + ℓ − p | p = 1, ..., ℓ}.

Then ⌈w⌉ is invariant under ≡.
Proof. It suffices to consider the case of two words w, w′ deduced from one another by applying one relation of PH . For w = uθj θi v and w′ = uθi θj+1 v, with
j > i + 2, one finds ⌈w⌉ = max(⌈u⌉ + |v| + 2, j + 1 + |v|, ⌈v⌉) = ⌈w′ ⌉. Similarly, for
w = uθi θi+1 θi+3 v and w′ = uθi+1 θi θi+1 v, one obtains ⌈w⌉ = max(⌈u⌉ + |v| + 3, i +
3 + |v|, ⌈v⌉) = ⌈w′ ⌉.

For a in H + , we write ⌈a⌉ for the common value of ⌈w⌉ for w representing a. A
direct application is the following a priori nontrivial result:
Proposition 3.2. The word problem for PH is decidable.
Proof. For every word w in Θ∗ , the ≡-class of w is finite: indeed, w′ ≡ w implies
both |w′ | = |w| and ⌈w′ ⌉ = ⌈w⌉, and the number of words w′ satisfying these
conditions is bounded above by ⌈w⌉|w| . Therefore, starting from two words w, w′ ,
one can decide whether w′ ≡ w holds by saturating {w} with respect to the relations
of PH , eventually obtaining in finitely many steps an exhaustive enumeration of the
≡-class of w. Then one compares w′ with the elements of the list so constructed. 
Another property that directly follows from the presentation is the fact that the
monoid F + is a quotient of H + :
Proposition 3.3. The map π : θi 7→ τi induces a surjective homomorphism from
the monoid H + onto the Thompson monoid F + .
Proof. Let π ∗ be the extension of π into a homomorphism from the free monoid Θ∗
to the monoid F + . We claim that w ≡ w′ implies π ∗ (w) = π ∗ (w′ ). It is enough to
check this when w=w′ is a relation of PH . The case of length 2 relations is trivial,
as the latter are relations of PF . For length 3 relations, we find in F +
π ∗ (θi+1 θi θi+1 ) = τi+1 τi τi+1 = τi τi+2 τi+1 = τi τi+1 τi+3 = π ∗ (θi θi+1 θi+3 ).
So π ∗ induces a homomorphism from H + to F + . The latter is surjective since each
generator τi lies in the image.

The projection π from H + to F + provided by Proposition 3.3 is not injective:
θ2 θ1 and θ1 θ3 are distinct in H + since no relation of PH applies to the corresponding
words, but they both project to τ2 τ1 in F + .

10

PATRICK DEHORNOY AND EMILIE TESSON

3.2. A normal form on H + . Like in the case of F + , our first method for investigating the monoid H + is to construct a normal form using a rewrite system.
Lemma 3.4. Let EH be the rewrite system on Θ∗ defined by the rules
θi θj+1 → θj θi

(3.2)

for i > 1 and j > i + 2,

θi θi+1 θi+3 → θi+1 θi θi+1

(3.3)

for i > 1.

Then EH is convergent.
Proof. As in the case of EF , we show that EH is noetherian and locally confluent, and
appeal to Newman’s diamond lemma. Let π denote the homomorphism from Θ∗
on T ∗ that maps θi to τi for every i. Then, for every w in Θ∗ and every integer m,
(3.4)

w ⇒Hm w′

implies

π(w) ⇒p π(w′ ) for some p satisfying m 6 p 6 2m.

Indeed, up to applying π, (3.2) is a rule of EF , whereas, for (3.3), we find
π(θi θi+1 θi+3 ) = τi τi+1 τi+3 ⇒ τi τi+2 τi+1 ⇒ τi+1 τi τi+1 = π(θi+1 θi θi+1 ).
Then an infinite nontrivial sequence of EH -reductions would project to an infinite
nontrivial sequence of EF -reductions, so the noetherianity of EF implies that of EH .
We now check local confluence. As in Lemma 2.1, it is sufficient to consider the
critical cases where two rules overlap. As there are two types of rules, four patterns
are possible. Twice using (3.2) has already been seen (up to a change of letters)
in (2.2). The remaining three cases then correspond to the confluence diagrams
(3.5)

θi θi+1 θi+3 θi+4 θi+6

⇒H
⇒

(3.6)

θi θj+1 θj+2 θj+4

⇒

H

(3.7) θi θi+1 θi+3 θj+1

⇒H
⇒

H

H

5

H

⇒H

θi+1 θi θi+1 θi+4 θi+6 ⇒
5
θi θi+1 θi+4 θi+3 θi+4

θj θi θj+2 θj+4

⇒3
H

θi θj+2 θj+1 θj+2

θi+2 θi+1 θi+2 θi θi+1 ,

⇒H

3
⇒H

θj+1 θj θj+1 θi with j > i + 2,

θi+1 θi θi+1 θj+1 ⇒
3

θi θi+1 θj θi+3
which complete the verification.

H

3
⇒H

θj−2 θi+1 θi θi+1 with j > i + 5,


We deduce:
Proposition 3.5. EH -reduced words provide a unique normal form for the elements
of the monoid H + .
For a in H + , we shall denote by nf(a) the unique EH -reduced word that represents a. For w in Θ∗ , we denote by red(w) the unique EH -reduced word to which
w is EH -reducible. As in Section 2.2, we note that a Θ-word is EH -reduced if, and
only if, it contains no factor in a list of obstructions, here
(3.8)

O := {θi θj | j > i + 3} ∪ {θi θi+1 θi+3 | i > 1}.

This implies that, for every n, the family of all EF -reduced words lying in {θ1 , ..., θn }∗
is a regular language. The above characterization of EH -reduced words implies the
following useful properties:

+
GARSIDE COMBINATORICS FOR F + AND A HYBRID WITH B∞

11

Corollary 3.6. (i) Every factor of an EH -reduced word is EH -reduced.
(ii) A word w is EH -reduced if, and only if, all length 3 factors of w are.
(iii) If uv and vw are EH -reduced, then uvw is EH -reduced, except for:
- |v| = 0, u = u′ θi , and w = θj w′ with j > i + 3,
- |v| = 0, u = u′ θi , and w = θi+1 θi+3 w′ ,
- |v| = 0, u = u′ θi θi+1 , and w = θi+3 w′ ,
- |v| = 1, u = u′ θi , v = θi+1 , and w = θi+3 w′ .
Proof. Points (i) and (ii) directly follow from the characterization of EH -reduced
words, and so does the fact that uvw is not EH -reduced if one is in one of the four
listed cases. The point is, assuming that uvw is not EH -reduced, to prove that one
is necessarily in one of the listed cases. Now the assumption that uvw is not EH reduced means that at least one rule of EH can be applied, and, owing to (ii), the
assumption about uv and vw requires that v has length at most one. Considering
the various possibilities yields the four identified cases.

The next result shows that, if w is an EH -reduced word, then the EH -reduced
form of wθi is obtained by pushing θi to the left as much as possible:.
Lemma 3.7. If w is EH -reduced, then, for every i, we have red(wθi ) = w1 θi−|w2 | w2
for some decomposition (w1 , w2 ) of w.
Proof. We use induction on the length of w. For w empty, the result is obvious. So
assume |w| > 1. Then we have w = w′ θk for some k. As w′ θk is EH -reduced, the
possible rewritings of w′ θk θi necessarily involve the final letter θi .
For i 6 k + 1, no rule applies to w′ θk θi , so wθi is EH -reduced, and the result is
true for (w1 , w2 ) := (w, ε).
For i > k + 3, we have w′ θk θi ⇒H w′ θi−1 θk . Now w′ is EH -reduced and shorter
than w. Hence, by induction hypothesis, there exists a decomposition w′ = w1′ w2′
satisfying red(w′ θi−1 ) = w1′ θj w2′ with j = i − 1 − |w2′ |. Now w1′ θj w2′ is EH -reduced,
and so is w2′ θk as a factor of the EH -reduced word w1′ w2′ θk . By Corollary 3.6,
w1′ θj w2′ θk is EH -reduced, as we have j > k + 2 − |w2′ |. Hence, red(wθi ) is w1′ θj w2′ θk ,
and the result is true with (w1 , w2 ) := (w1′ , w2′ θk ).
There remains the case i = k + 2. For w′ = ε, we have wθi = θi−2 θi , which
is EH -reduced, and the result is true for (w1 , w2 ) := (w, ε). Otherwise, we write
w′ = w′′ θℓ . For ℓ 6= i − 3, we find wθi = w′′ θℓ θi−2 θi , which is EH -reduced as, by
assumption, w′′ θℓ θi−2 is EH -reduced. So the result is true for (w1 , w2 ) := (w, ε).
Finally, for ℓ = i − 3, we have w′′ θi−3 θi−2 θi ≡ w′′ θi−2 θi−3 θi−2 . As w′′ is EH reduced and shorter than w, the induction hypothesis gives a decomposition w′′ =
w1′′ w2′′ satisfying red(w′′ θi−2 ) = w1′′ θj w2′′ with j = i − 2 − |w2′′ |. It remains to
show that w1′′ θj w2′′ θi−3 θi−2 is EH -reduced. Now w1′′ θj w2′′ is EH -reduced, and so is
w2′′ θi−3 θi−2 , as a factor of the EH -reduced word w1′′ w2′′ θi−3 θi−2 . By Corollary 3.6,
w1′′ θj w2′′ θi−3 θi−2 is EH -reduced, and j = i − 2 − |w2′′ | holds. Therefore, red(wθi ) is
w1′′ θj w2′′ θi−3 θi−2 , and the result is true for (w1 , w2 ) := (w1′′ , w2′′ θi−3 θi−2 ).

We shall now apply the normal form provided by EH to studying right cancellativity in H + . At this point, we shall not obtain a complete answer, but only a
(surprising) connection between left and right cancellativity.
Proposition 3.8. If H + is left cancellative, then it is right cancellative as well.

12

PATRICK DEHORNOY AND EMILIE TESSON

Proof. We assume that H + is left cancellative, and aim at proving that any equality
aθi = bθi implies a = b. So assume aθi = bθi . Let u := nf(a) and v := nf(b). By
Lemma 3.7, there exist u1 , u2 , v1 , v2 satisfying
(3.9)

u = u1 u2

and red(uθi ) = u1 θj u2

with j = i − |u2 |,

(3.10)

v = v1 v2

and red(vθi ) = v1 θk v2

with k = i − |v2 |.

By assumption, we have aθi = bθi , hence red(uθi ) = red(vθi ), and, from there,
u1 θj u2 = v1 θk v2 . We consider the various possible cases.
Assume first j 6= k, say j < k. By (3.9) and (3.10), we obtain
|u2 | = i − j > i − k = |v2 |,

whence

|u1 | < |v1 |.

So u1 is a proper prefix of v1 , and v2 is a proper suffix of u2 . As u1 is a proper prefix
of v1 , the word u1 θj is a prefix of v1 , and there exists w satisfying v1 = u1 θj w. We
find u1 θj u2 = u1 θj wθk v2 , hence u2 = wθk v2 . Therefore, we have
u = u1 wθk v2 ,

v = u1 θj wv2 ,

and red(uθi ) = red(vθi ) = u1 θj wθk v2 .

The equality red(vθi ) = u1 θj wθk v2 implies vθi ≡ u1 θj wθk v2 , that is, u1 θj wv2 θi ≡
u1 θj wθk v2 . As H + is left cancellative, left cancelling u1 θj w yields v2 θi ≡ θk v2 .
By assumption, u1 is EH -reduced, hence, by Corollary 3.6(i), so is its suffix θk v2 .
The equivalence v2 θi ≡ θk v2 implies red(v2 θi ) = θk v2 , hence v2 θi ⇒H∗ θk v2 , whence
uθi = u1 wθk v2 θi ⇒H∗ u1 wθk θk v2 . Now, as a prefix of u, the word u1 wθk is EH reduced, whereas θk θk is EH -reduced by definition. By Corollary 3.6(iii), u1 wθk θk
is reduced. On the other hand, as a suffix of u1 , the word θk v2 is EH -reduced,
so, by Corollary 3.6(iii) again, θk θk v2 is EH -reduced. Finally, u1 wθk θk and θk θk w
are EH -reduced, hence, by Corollary 3.6(ii), u1 wθk θk v2 is EH -reduced. So the two
words u1 θj wθk v2 and u1 wθk θk v2 are EH -reduced, both equivalent to uθi . Hence
they must coincide: u1 wθk θk v2 = u1 θj wθk v2 holds. Deleting the prefix u1 and the
suffix θk v2 on both sides, we deduce
(3.11)

wθk = θj w.

An induction on |w| shows that the word equality (not equivalence) (3.11) is possible
only for j = k: for |w| > 2, a word w satisfying (3.11) must begin with θj and finish
with θk , leading to w = θj w′ θk with w′ satisfying w′ θk = θj w′ . But this contradicts
the assumption j 6= k.
So, the only possibility is j = k. Then (3.9) and (3.10) imply |u2 | = |v2 |, whence
u2 = v2 , and, from there, u1 = v1 and u = v, implying a = b.

Another application of the normal form in H + is a solution for the word problem
of the presentation PH that is much more efficient than the “stupid” solution of
Proposition 3.2: two words w, w′ represent the same element in H + if, and only if,
red(w)
and red(w′ ) coincide. It is easy to see that, from a word of length ℓ, at most

ℓ
2 rules can be applied, leading to a solution for the word problem whose overall
complexity is quadratic in ℓ. We do not go into details here.
3.3. Reversing for H + . Continuing as in Section 2.3 for F + , we now investigate
the (right) reversing relation associated with the presentation PH of H + , in view
of possibly establishing that it is left cancellative and admits right lcms.
For applying Lemma 2.5, the first step is to check Condition (♦).

+
GARSIDE COMBINATORICS FOR F + AND A HYBRID WITH B∞

13

Lemma 3.9. For every generator θi and for every relation w = w′ of PH , Condition (♦) is satisfied: for every PH -grid from (θi , w), there is an equivalent grid
from (θi , w′ ), and vice versa.
Proof. Because there exists exactly one relation of the form θi ... = θj ... in PH for
all i, j, a PH -grid is unique when it exists, so we only have to check that the involved
grids either exist and are equivalent, or they do not exist. As in the case of F + ,
there are infinitely many generators and relations, but only finitely many patterns
occur, according to the relative positions of the indices of the involved generators.
In the case of θi and the relation θj θj+1 θj+3 = θj+1 θj θj+1 , the only cases that do
not just result in shifting the indices are j = i + 1 and j = i − 2, for which we find
(for readability, we draw the diagrams for i = 1, j = 2, and for i = 3, j = 1)
θ2
θ1
(3.12)

θ1

θ3

θ5

θ4

θ1 θ

θ2
θ2

θ4

6

θ2
θ5

θ3

θ2

θ3

θ1

θ1
θ1

θ4

θ1

θ2

θ2

θ7

θ4

θ2

θ1
θ2

θ4

θ5

and we check θ2 θ4 θ5 θ7 ≡ θ2 θ5 θ4 θ5 ≡ θ4 θ2 θ4 θ5 , so the grids are equivalent, and
θ1

θ2

θ4

θ2
θ5

(3.13)

θ3

θ4

θ5

θ3
θ3

θ7
θ1

θ2

θ4

θ1

θ2

θ1

θ4 θ

θ5

θ5

θ2

θ3

2

θ6
θ1

θ5
θ7

θ2

and we check θ1 θ2 θ4 θ5 ≡ θ2 θ1 θ2 θ5 ≡ θ2 θ1 θ4 θ2 ≡ θ2 θ3 θ1 θ2 , so the grids are equivalent. Similarly, in the case of θi and a relation θj θk+1 = θk θj with k > j + 2, the
only nontrivial case is for i = j + 1 and k = j + 2, where we find (here for i = 2,
j = 1, and k = 3)
θ1

θ4
θ2

(3.14)

θ3

θ1

θ2

θ5

θ2
θ2

θ2

θ4

θ2

θ1

θ4
θ5
θ1

θ2

θ5

θ7

θ3
θ3

θ5

θ2
θ4

θ1

θ4
θ5

θ2

and we check θ1 θ2 θ5 θ7 ≡ θ1 θ4 θ2 θ7 ≡ θ3 θ1 θ2 θ7 ≡ θ3 θ1 θ6 θ2 ≡ θ3 θ5 θ1 θ2 , so the grids
are equivalent.

Lemma 3.9 shows that the presentation PH , which is homogeneous, is eligible
for Lemma 2.5. So, in particular, for all u, v in Θ∗ , we have the equivalence
(3.15)

u≡v

⇐⇒

(u, v) y (ε, ε),

that is, u and v represent the same element of H + if, and only if there exists a
PH -grid from (u, v) to (ε, ε). As an application, we deduce
Proposition 3.10. The monoid H + is left and right cancellative.

14

PATRICK DEHORNOY AND EMILIE TESSON

Proof. Lemma 2.5(ii) implies that H + is left cancellative. By Proposition 3.8, this
implies that H + is right cancellative as well.

As for common right multiples, owing to the fact that a PH -grid with a given
source is unique when it exists, Lemma 2.5(iii) directly implies:
Proposition 3.11. Two elements [u], [v] of H + admit a common right multiple
in H + if, and only if, there exists a PH -grid from (u, v); in this case, [u] and [v]
admit a right lcm, represented by uv1 with (u1 , v1 ) the output of the grid from (u, v).
Proposition 3.11 is optimal: there exist elements of H + without a common
right multiple, typically θ2 and θ1 θ3 . Indeed, if we try to construct a PH -grid
from (θ2 , θ1 θ3 ), we must start with
θ1
θ3
θ2
θ2
θ4
θ1
θ2
and the process cannot terminate, since the pending pattern (θ2 θ4 , θ3 ) is, up to a
symmetry, the image of (θ2 , θ1 θ3 ) under shifting the indices. By Proposition 3.11,
this is enough to conclude that θ2 and θ1 θ3 admit no common right multiple in H + .
Remark 3.12. In the above example, the non-existence of a common right multiple
is easily established, as constructing a PH -grid enters an explicit non-terminating
loop. The general question of the existence of a PH -grid from a given pair of words
is a priori difficult, and it is not clear whether it is algorithmically decidable. In fact,
it is, but this is nontrivial. The method consists in identifying an explicit family of
words Θ′ that is closed under reversing, in the sense that, if u and v belong to Θ′
and (u, v) y (u1 , v1 ) holds, then u1 and v1 lie in Θ′ . Then, one easily shows that,
if the existence of common multiples can be decided for pairs of words of Θ′ , it
can decided for arbitrary pairs of words. So the question is to find a convenient
family Θ′ and analyze the existence of PH -grids for words of Θ′ . In the case of PH ,
this program is successfully completed in [27] for Θ′ := Θ1 ∪ Θ2 ∪ {ε} with
(3.16)

Θ1 := {θi θi+2 θi+4 ··· θi+2k | i > 1, k > 0},

(3.17)

Θ2 := {θi θi+2 θi+4 ··· θi+2k θi+2k+1 | i > 1, k > 0},

Therefore the existence of common right multiples in H + is decidable.
Trying to apply the same approach to studying right cancellativity and left
multiples in H + fails. Indeed, one easily checks that the left diagram below is
a legitimate “left PH -grid” from (θ6 , θ2 θ1 θ2 ), whereas the right diagram shows that
constructing an equivalent left PH -grid from (θ6 , θ1 θ2 θ4 ) fails, since there is no
relation ...θ2 = ...θ3 in PH :
θ1

θ2

θ1

θ2

θ3

θ2
(3.18)

θ4

θ4
θ4

θ5

θ6

θ6

θ1

θ3
θ2

θ1

θ2

θ1

θ2

θ4

+
GARSIDE COMBINATORICS FOR F + AND A HYBRID WITH B∞

15

So the counterpart of Condition (♦) fails for θ6 and the relation θ1 θ2 θ4 = θ2 θ1 θ2 ,
and the counterpart of Lemma 2.5 cannot be appealed to. This says nothing
about H + , but just leaves the questions open. As for right cancellativity, the
question was solved using the normal form of Section 3.2. As for left multiples,
nothing is clear, in particular about the possible existence of left lcms. However,
what is clear is that, for instance, θi and θi+1 admit no common left multiple, since
their projections in F + do not.
4. Garside combinatorics for H +
We now show that the monoid H + admits interesting combinatorial properties
similar to those of F + , in connection with distinguished elements ∆n defined as
right lcms of atoms, and with the left divisors of the latter, called simple elements.
So our goal is to establish for H + results similar to those of Section 2.4. We shall see
that the results are indeed similar, but with more delicate and interesting proofs.
4.1. The elements ∆n and their divisors. The atoms of the monoid H + are
the elements θi with i > 1. On the shape of the braid and Thompson cases, we shall
introduce for every n a distinguished element of H + , again denoted ∆n , which is the
right lcm of the first n−1 atoms. As in Section 2, it will be convenient to start from
explicit word representatives. Moreover, in view of subsequent computations, we
shall simultaneously introduce, for every n, an element ∆n+0.5 that is intermediate
between ∆n and ∆n+1 .
Definition 4.1. We put ∆1 = ∆1.5 := ε, ∆2 := θ1 , and, for n > 2,
(4.1)

∆n := ∆n−1 θ3n−7 θ3n−5

and ∆n+0.5 := ∆n θ3n−4 .

We denote by ∆n (resp., ∆n+0.5 ) the class of ∆n (resp., ∆n+0.5 ) in H + .
So, by definition, the word ∆n (resp., ∆n+0.5 ) is the increasing enumeration
from 1 to 3n − 5 (resp., 3n − 4) of all generators θi with i 6= 0 mod 3. We immediately obtain for every n > 2
(4.2)

∆n 4 ∆n+0.5 4 ∆n+1 ,

where we recall 4 denotes the left divisibility relation. For n > 3, the word ∆n is
not EH -reduced; an easy induction gives the values
(4.3)

nf(∆n ) = θn−1 · θn−2 θn−1 · θn−3 θn−2 · ··· · θ2 θ3 · θ1 θ2 ,

(4.4)

nf(∆n+0.5 ) = θn−1 θn · θn−2 θn−1 · θn−3 θn−2 · ··· · θ2 θ3 · θ1 θ2 .

Note that (4.4) implies that ∆n+0.5 , which left divides ∆n+1.5 by (4.2), also right
divides it. It also implies, for n > 2, the equality
(4.5)

∆n = θn−1 ∆n−0.5 .

The first step in studying the element ∆n is to establish that it is indeed the
right lcm of the expected atoms.
Lemma 4.2. For every n > 2, the element ∆n is the right lcm of θ1 , ..., θn−1 . No
element θi with i > n left divides either ∆n or ∆n+0.5 .
Proof. We first prove using induction on n > 2 that ∆n is the right lcm of θ1 , ..., θn−1 .
The result is trivial for n > 2, so assume n > 3. A direct computation gives
(θn−1 , ∆n−1 ) y (θ3n−7 θ3n−5 , ∆n−0.5 ).

16

PATRICK DEHORNOY AND EMILIE TESSON

By Lemma 2.5(iii), this implies that ∆n represents the right lcm of θn−1 and ∆n−1 .
By induction hypothesis, ∆n−1 is the right lcm of θ1 , ..., θn−2 , so ∆n is the right
lcm of θ1 , ..., θn−1 . On the other hand, for i > n, similar computations give
(θi , ∆n+0.5 ) y (θi+2n−2 , ∆n+0.5 ),
showing that the right lcm of θn and ∆n+0.5 exists but is not ∆n+0.5 , so θi does
not left divide ∆n+0.5 . Hence, by (4.2), θi does not left divide ∆n either.

We already mentioned that θ1 and θ2 admit no common left multiple in H + : it
follows that ∆n cannot be a left lcm for θ1 , ..., θn−1 .
Definition 4.3. An element a of H + is called simple if a 4 ∆n holds for some n;
in this case, the least such n is called the index of a, denoted by ind(a). For n > 1
and ℓ > 0, we put
[
Σn,ℓ := {a ∈ H + | a 4 ∆n and |a| = ℓ}, and Σn :=
Σn,ℓ .
ℓ>0

For instance, Σ3 is the family of all left divisors of ∆3 ; one easily checks that
it consists of the six elements 1, θ1 , θ2 , θ1 θ2 , θ2 θ1 , and ∆3 . On the other hand,
Lemma 4.2 implies that Σn,1 is equal to {θ1 , ..., θn−1 } for every n.
As ∆n left divides ∆n+1 for every n, if a is simple, the values of n satisfying
a 4 ∆n make an interval [p, ∞[, and ind(a) is the number p. Thus, a 4 ∆n is
equivalent to ind(a) 6 n, and ind(a) = n is equivalent to the conjunction of a 4 ∆n
and a 64 ∆n−1 .
We shall subsequently need an upper bound for the ceiling of simple elements
(as introduced in Lemma 3.1). This can be deduced from Lemma 4.2.
Lemma 4.4. For a 4 ∆n+0.5 in H + with n > 2, one has
(4.6)

⌈a⌉ 6 n + |a| − 2.

Proof. Use induction on |a| > 1. For |a| = 1, Lemma 4.2 implies a = θi with
i 6 n − 1, whence ⌈a⌉ = i 6 n − 1 = n + |a| − 2.
Assume now |a| > 2, and write a = bθi . Then b 4 ∆n+0.5 holds as well, and the
induction hypothesis implies ⌈b⌉ 6 n + |a| − 3. Write bθi c = ∆n+0.5 . By definition,
the contribution of θi to the ceiling of ∆n+0.5 is i + |c|, i.e., i + 2n − |a| − 2. The
explicit definition of (4.1) gives ⌈∆n+0.5 ⌉ = 3n − 4, and we deduce i 6 n + |a| − 2,
whence, finally, ⌈a⌉ = ⌈bθi ⌉ = max(⌈b⌉ + 1, i) 6 n + |a| − 2.

4.2. Expressions of ∆n and ∆n+0.5 . Our aim is to analyze simple elements of H +
precisely. To this end, it will be crucial to control the various expressions of the
elements ∆n and ∆n+0.5 , and we establish here technical results in this direction.
Obtaining a complete description as in Lemma 2.11 seems hopeless, but it will be
sufficient to connect the expressions of ∆n with those of ∆n−0.5 (i.e., of ∆n−1 θ3n−7 ).
A similar connection will be stated between the expressions of ∆n−0.5 and ∆n−1.5
in Lemma 4.6 below.
Lemma 4.5. For n > 2, every expression of ∆n has the form w1 θk w2 with
w1 w2 ≡ ∆n−0.5 and k = n + |w1 | − 1; in this case, w1 θk ≡ θn−1 w1 holds.
Proof. The result is trivial for n = 2. We assume n > 3, and establish the existence of w1 and w2 for an expression w of ∆n using induction on the combinatorial distance d between ∆n and w, i.e., the minimal number of relations of PH
needed to transform ∆n to w. For d = 0, the result is trivial with w1 := ∆n−0.5

+
GARSIDE COMBINATORICS FOR F + AND A HYBRID WITH B∞

17

and w2 := ε. Assume now d > 1, and let w′ satisfying dist(∆n , w′ ) = p − 1 and
dist(w′ , w) = 1. Write w′ = u1 v ′ u2 , w = u1 vu2 with v ′ =v a relation of PH . By induction hypothesis, there exist w1′ , w2′ satisfying w′ = w1′ θk′ w2′ with w1′ w2′ ≡ ∆n−0.5
and k ′ := n + |w1′ | − 1.
We consider the various possibilities for the position of v ′ inside w′ . If u1 v ′ is a
prefix of w1′ , i.e., if we have w1′ = u1 v ′ u′′1 for some u′′1 , we find w′ = u1 v ′ u′′1 θk′ w2′ and
w = u1 vu′′1 θk′ w2′ . Now we have u1 vu′′1 w2′ ≡ u1 v ′ u′′1 w2′ = w1′ w2′ ≡ ∆n−0.5 , whence
the result with w1 := u1 vu′′1 , w2 := w2′ , and k := k ′ . The argument is similar if
v ′ u2 is a suffix of w2′ .
There remain the cases when θk′ occurs in v ′ , i.e., θk′ is involved in going from w′
to w. Assume first that v ′ =v is a length 2 relation. Then v ′ is either θi θj with
j > i + 3, or θi θj with j 6 i − 2. As θk′ occurs in v ′ in position either 1 or 2, four
cases are to be considered.
(i) θi is the last letter of w1′ and j = k ′ > i + 3 holds. Putting w1′ := w1′′ θi ,
we obtain w′ = w1′′ θi θk′ w2′ and w = w1′′ θk′ −1 θi w2′ = w1′′ θn+|w1′′ |−1 θi w2′ . Moreover,
w1′′ θi w2′ ≡ ∆n−0.5 holds, whence the result for w1 := w1′′ , w2 := θi w2′ , and k := k ′ −1.
(ii) θi is the last letter of w1′ and j = k ′ 6 i − 2 holds. This is impossible, because
a letter θi in this position would contribute i + 1 + |w2′ |, hence at least k ′ + 3 + |w2′ |,
i.e., 3n − 2, to the ceiling ⌈w′ ⌉, which is that of ∆n , namely 3n − 5.
(iii) θi is θk′ and θj is the first letter of w2′ , with j > i + 3. This is impossible
for the same ceiling reason as in (ii).
(iv) θi is θk′ and θj is the first letter of w2′ , with j 6 i − 2. This is similar to (i).
We now similarly handle the case when v ′ =v is a length 3 relation. Then v ′ is either
θi θi+1 θi+3 , or θi+1 θi θi+1 . This time, θk′ occurs in v ′ in position 1, 2, or 3, so six
cases are a priori possible.
(i) θi θi+1 is the final factor of w1′ , and i+3 = k ′ holds. Putting w1′ := w1′′ θk′ −3 θk′ −2 ,
we obtain w′ = w1′′ θk′ −3 θk′ −2 θk′ w2′ and w = w1′′ θk′ −2 θk′ −3 θk′ −2 w2′ . Moreover, we
find w1′′ θk′ −3 θk′ −2 w2′ ≡ ∆n−0.5 , whence the result for w1 := w1′′ , w2 := θk−3 θk−2 w2′ ,
and k := k ′ .
(ii), (iii) θi is the last letter of w1′ with i+1 = k ′ , and θi+3 is the first letter in w2′ ,
or we have i = k ′ and θi+1 θi+3 is a prefix of w2′ . These cases are impossible because
⌈w′ ⌉ = 3n−5 holds, whereas the letter θk′ +2 would contribute n+|w1′ |+1+|w2′ |−1 =
n + 2n − 3 − 1 = 3n − 4 to the ceiling of w′ .
(iv), (v) θi+1 θi is a suffix of w1′ and i + 1 = k holds, or θi+1 is the last letter
of w1′ and i = k holds and θi+1 is the first letter of w2′ . These cases are impossible
because θk+2 would contribute 3n − 3 to the ceiling of w′ .
(vi) θi θi+1 is a prefix of w2′ , with i + 1 = k ′ . Putting w2′ = θk′ −1 θk′ w2′′ , we
obtain w′ = w1′ θk′ θk′ −1 θk′ w2′′ and w = w1′ θk′ −1 θk′ θk′ +2 w2′′ . Moreover, we find
w1′ θk′ −1 θk′ w2′′ ≡ ∆n−0.5 , whence the result for w1 := w1′ θk′ −1 θk′ , w2 := w2′′ , and
k := k ′ + 2.
This completes the induction. For the final equivalence, we find, using (4.5),
w1 θk w2 ≡ ∆n ≡ θn−1 ∆n−0.5 ≡ θn−1 w1 w2 .
By right cancelling w2 , we deduce w1 θk ≡ θn−1 w1 .



We now state a similar result for the expressions of ∆n−0.5 . The latter is equal
to ∆n−1.5 θ3n−8 θ3n−7 and the two letters θ3n−8 and θ3n−7 can be moved left.

18

PATRICK DEHORNOY AND EMILIE TESSON

Lemma 4.6. For n > 3, every expression of ∆n−0.5 has the form w1 θk w2 θℓ w3 with
w1 w2 w3 ≡ ∆n−1.5 , k = n − 2 + |w1 |, and ℓ = n − 1 + |w1 w2 |; in this case, w1 θk w2 w3
represents ∆n−1 .
We skip the proof, which is entirely similar to that of Lemma 4.5—but with
more cases, as one has to take care of the positions of two letters.
Applying Lemmas 4.5 and 4.6, we can now easily establish various properties of
simple elements, paving the way for a partition of these elements in several families.
Lemma 4.7. (i) For n > 2, every left divisor of ∆n either left divides ∆n−0.5 , or
has the form aθk b with ab 4 ∆n−0.5 , k = n + |a| − 1, and aθk = θn−1 a.
(ii) For n > 2 and a 4 ∆n , the conditions a 4 ∆n−0.5 and θn−1 64 a are
equivalent.
(iii) For n > 3, every left divisor of ∆n−0.5 either left divides ∆n−1 , or has the
form θn−2 θn−1 a with a 4 ∆n−1.5 .
Proof. (i) If [w] 4 ∆n holds, then ∆n has an expression of form ww′ for some w′ .
By Lemma 4.5, we can write ww′ = w1 θk w2 with w1 w2 ≡ ∆n−0.5 . Then either w is
a prefix of w1 , and then we have [w] 4 ∆n−0.5 , or w has the form w1 θk w2′ with w2′
a prefix of w2 , and then we have [w] = [w1 ]θk [w2′ ] with [w1 ][w2′ ] = [w1 w2′ ] 4 ∆n−0.5 .
Moreover, w1 θk ≡ θn−1 w1 implies [w1 ]θk = θn−1 [w1 ].
(ii) Assume a 4 ∆n−0.5 . By Lemma 4.2, θn−1 does not left divide ∆n−0.5 , so, a
fortiori, θn−1 does not left divide a.
Conversely, assume a 4 ∆n and θn−1 64 a. By (i), there are two possibilities:
either we have a 4 ∆n−0.5 , as expected, or a can be decomposed as bθk c with
bc 4 ∆n−0.5 and bθk = θn−1 b, implying θn−1 4 a and contradicting the assumption.
So a 4 ∆n−0.5 is the only possibility.
(iii) If [w] 4 ∆n−0.5 holds, then ∆n−0.5 has an expression of form ww′ for
some w′ . By Lemma 4.6, we can write ww′ = w1 θk w2 θℓ w3 with w1 w2 w3 ≡ ∆n−1.5 ,
k = n − 2 + |w1 |, and ℓ = n − 1 + |w1 w2 |. Then three cases may arise. Either w is a
prefix of w1 , and then we have [w] 4 ∆n−1.5 , whence a fortiori [w] 4 ∆n−1 . Or w
is w1 θk w2′ for some prefix w2′ of w2 . By Lemma 4.6, we have [w] 4 ∆n−1 again. Or
w is w1 θk w2 θℓ w3′ for some prefix w3′ of w3 , say w3 = w3′ w3′′ . Applying (4.4), we find
ww3′′ ≡ ∆n−0.5 ≡ θn−2 θn−1 ∆n−1.5 ≡ θn−2 θn−1 w1 w2 w3′ w3′′ . Right cancelling w3′′ , we
deduce w ≡ θn−2 θn−1 w1 w2 w3′ , with w1 , w2 , w3′ satisfying [w1 w2 w3′ ] 4 ∆n−1.5 . 
4.3. Partitioning the sets Σn,ℓ . With the preparatory results of Section 4.2, it is
now easy to describe the simple elements of the monoid H + more precisely. To this
end, we introduce subfamilies of H + . We shall eventually see that these subfamilies
form a partition of the set Σn,ℓ of all length ℓ left divisors of ∆n .
Definition 4.8. For n > 2 and 0 6 ℓ 6 2n − 3, we put
(type 0) Σ0n,ℓ := {a | a 4 ∆n−1 and |a| = ℓ} for n > 2, ℓ > 0,
(type I)

ΣIn,ℓ := {θn−1 a | a 4 ∆n−1 and |a| = ℓ − 1} for n > 2, ℓ > 1,

1
(type II1 ) ΣII
n,ℓ := {θn−2 θn−1 a | a 4 ∆n−1.5 and |a| = ℓ − 2} for n > 3, ℓ > 2,
2
(type II2 ) ΣII
n,ℓ := {θn−1 θn−2 θn−1 a | θn−2 a 4 ∆n−1 and |a| = ℓ − 3} for n, ℓ > 3,

II2
1
completed with Σ0n,ℓ = ΣIn,ℓ = ΣII
n,ℓ = Σn,ℓ := ∅ for other values of n and ℓ.

The first step is to check that the above sets consist of left divisors of ∆n .

+
GARSIDE COMBINATORICS FOR F + AND A HYBRID WITH B∞

19

II2
1
Lemma 4.9. For all n, ℓ, the sets Σ0n,ℓ , ΣIn,ℓ , ΣII
n,ℓ et Σn,ℓ are included in Σn,ℓ .
II2
1
Proof. By definition, all elements of Σ0n,ℓ , ΣIn,ℓ , ΣII
n,ℓ , and Σn,ℓ have length ℓ, so
the point is to check that they left divide ∆n . As ∆n−1 left divides ∆n , the
result is obvious for Σ0n,ℓ . Next, a 4 ∆n−1 implies θn−1 a 4 θn−1 ∆n−1 , whence
θn−1 a 4 θn−1 ∆n−1 θ3n−7 = ∆n . So ΣIn,ℓ is included in Σn . Then, by (4.4), we have
∆n = θn−2 θn−1 ∆n−1.5 θ3n−5 , so a 4 ∆n−1.5 implies θn−2 θn−1 a 4 θn−2 θn−1 ∆n−1.5 ,
1
whence θn−2 θn−1 a 4 ∆n . So ΣII
n,ℓ is included in Σn . Finally, for b = θn−1 θn−2 θn−1 a
with θn−2 a 4 ∆n−1 , we have ∆n−1 = θn−2 ∆n−1.5 by (4.5), whence a 4 ∆n−1.5
by left cancelling θn−2 . A direct computation gives ∆n = θn−1 θn−2 θn−1 ∆n−1.5 , so
2
a 4 ∆n−1.5 implies b 4 θn−1 θn−2 θn−1 ∆n−1.5 = ∆n . So ΣII
n,ℓ is included in Σn . 
2
The second step consists in showing that the various sets Σ0n,ℓ , ..., ΣII
n,ℓ are pairwise disjoint. This is more delicate, in that it involves proving that certain words
are not equivalent. According to Lemma 2.5(i), this can be seen using PH -grids.

II2
1
Lemma 4.10. For all n, ℓ, the sets Σ0n,ℓ , ΣIn,ℓ , ΣII
n,ℓ , and Σn,ℓ are pairwise disjoint.
II2
1
Proof. To prove that Σ0n,ℓ is disjoint from ΣIn,ℓ , ΣII
n,ℓ , and Σn,ℓ , it suffices to prove
that no element of the latter three sets left divides ∆n−1 . Now, by definition, θn−1
2
left divides every element of ΣIn,ℓ and ΣII
n,ℓ , whereas, by Lemma 4.2, θn−1 does not
0
2
left divide ∆n−1 . So ΣIn,ℓ and ΣII
n,ℓ are disjoint from Σn,ℓ .
Next, a direct computation gives (θn−2 θn−1 , ∆n−1 ) y (θ3n−7 , ∆n−1.5 ), which,
by Lemma 2.5(i), proves θn−2 θn−1 64 ∆n−1 . As θn−2 θn−1 left divides every element
II1
0
1
of ΣII
n,ℓ , it follows that Σn,ℓ is disjoint from Σn,ℓ .
1
Assume now a ∈ ΣIn,ℓ ∩ ΣII
n,ℓ . Then, by definition, we have both θn−1 4 a and
a 4 θn−2 θn−1 ∆n−1.5 , whence θn−1 4 θn−2 θn−1 ∆n−1.5 . This is impossible: a direct
computation gives (θn−1 , θn−2 θn−1 ∆n−1.5 ) y (θ3n−10 , θn−1 θn−2 ∆n−1.5 ), which, by
1
Lemma 2.5(ii), proves θn−1 64 θn−2 θn−1 ∆n−1.5 . Hence ΣIn,ℓ and ΣII
n,ℓ are disjoint.
II2
I
Assume next a ∈ Σn,ℓ ∩ Σn,ℓ . We have both a = θn−1 b with b ∈ Σn−1,ℓ−1 ,
and a = θn−1 θn−2 θn−1 c with θn−2 c 4 ∆n−1 . By left cancelling θn−1 , we deduce
b = θn−2 θn−1 c, whence θn−2 θn−1 c 4 ∆n−1 and, a fortiori, θn−2 θn−1 4 ∆n−1 , what
2
we saw above is false. Hence ΣIn,ℓ and ΣII
n,ℓ are disjoint.
II2
1
Finally, assume a ∈ ΣII
n,ℓ ∩ Σn,ℓ . By definition, we have a = θn−2 θn−1 b =
θn−1 θn−2 θn−1 c with b 4 ∆n−1.5 and θn−2 c 4 ∆n−1 . As θn−1 θn−2 θn−1 is also
θn−2 θn−1 θn+1 , we deduce θn−2 θn−1 b = θn−2 θn−1 θn+1 c, whence b = θn+1 c by left
cancelling θn−2 θn−1 , and, from there, θn+1 4 b 4 ∆n−1.5 . Now, by Lemma 4.2,
II2
1
θn+1 does not left divide ∆n−1.5 . Hence ΣII

n,ℓ and Σn,ℓ are disjoint.

We are now ready to establish the expected partition result:
II2
1
Proposition 4.11. For all n, ℓ, the sets Σ0n,ℓ , ΣIn,ℓ , ΣII
n,ℓ , and Σn,ℓ form a partition
of Σn,ℓ .

Proof. Owing to Lemmas 4.9 and 4.10, the only point remaining to be proved is
II2
1
that every element of Σn,ℓ belongs to one of the sets Σ0n,ℓ , ΣIn,ℓ , ΣII
n,ℓ , Σn,ℓ . So
let a belong to Σn,ℓ . By Lemma 4.7(i), we have either a 4 ∆n−0.5 , or a = bθk c
with bc 4 ∆n−0.5 and bθk = θn−1 b. Assume first a 4 ∆n−0.5 . By Lemma 4.7(iii),
we have either a 4 ∆n−1 , whence a ∈ Σ0n,ℓ , or a = θn−2 θn−1 d with d 4 ∆n−1.5 ,
1
whence a ∈ ΣII
n,ℓ .

20

PATRICK DEHORNOY AND EMILIE TESSON

Assume now a = bθk c with bc 4 ∆n−0.5 and bθk = θn−1 b, whence a = θn−1 bc.
By Lemma 4.7(iii), we have either bc 4 ∆n−1 , whence a ∈ ΣIn,ℓ , or bc = θn−2 θn−1 d
with d 4 ∆n−1.5 . In the latter case, we find a = θn−1 θn−2 θn−1 d. Moreover,
2
d 4 ∆n−1.5 implies θn−2 d 4 θn−2 ∆n−1.5 = ∆n−1 , whence a ∈ ΣII

n,ℓ .
With the partition of Proposition 4.11, we can now count the left divisors of ∆n .
0
I
Lemma 4.12. For n > 3, let Fn,ℓ
be the identity map on Σn−1,ℓ , let Fn,ℓ
be
II
the map a 7→ θn−1 a on Σn−1,ℓ−1 , and let Fn,ℓ be the map on Σn−1,ℓ−2 defined
by F (a) := θn−2 θn−1 a if a 4 ∆n−1.5 holds, and F (a) := θn−1 θn−2 θn−1 b with
0
I
II
a = θn−2 b otherwise. Then Fn,ℓ
, Fn,ℓ
, and Fn,ℓ
respectively establish bijections

Σn−1,ℓ ↔ Σ0n,ℓ ,

Σn−1,ℓ−1 ↔ ΣIn,ℓ ,

and

II2
1
Σn−1,ℓ−2 ↔ ΣII
n,ℓ ∪ Σn,ℓ .

0
I
Proof. The result for Fn,ℓ
directly follows from the definition of Σ0n,ℓ . For Fn,ℓ
, it
I
+
follows from the definition of Σn,ℓ and the left cancellativity of H , which ensures
I
II
that Fn,ℓ
is injective. Finally, for Fn,ℓ
, put

X1 := {a ∈ Σn−1,ℓ−2 | a 4 ∆n−1.5 }

and X2 := {a ∈ Σn−1,ℓ−2 | a 64 ∆n−1.5 }.

+
II
1
It follows from the definition of ΣII
that Fn,ℓ
esn,ℓ and the left cancellativity of H
II1
tablishes a bijection from X1 to Σn,ℓ . On the other hand, for a in X1 , Lemma 4.7(ii)
implies θn−2 4 a, say a = θn−2 b, and then the left cancellativity of H + implies
II1
II2
II
2
that Fn,ℓ
establishes a bijection from X2 to ΣII
n,ℓ . As Σn,ℓ and Σn,ℓ are disjoint,
this completes the proof.


Lemma 4.12 immediately implies that, if we denote by Nn,ℓ the cardinal of Σn,ℓ ,
then the numbers Nn,ℓ are determined by the inductive rule
(4.7)

Nn,ℓ = Nn−1,ℓ + Nn−1,ℓ−1 + Nn−1,ℓ−2 ,

starting from the initial values N2,0 = N2,1 = 1. It follows that the numbers Nn,ℓ
appear in the generalized Pascal triangle in which each entry is the sum of the three
entries above it, starting from the row (1, 1), see Figure 1. An obvious induction
from (4.7) shows that Nn,ℓ is the coefficient of xℓ−1 in (1 + x)(1 + x + x2 )n−2 , that
Nn,ℓ = Nn,2n−3−ℓ holds for n − 1 6 ℓ 6 2n − 3, and that, for 0 6 ℓ 6 n − 2, the
number Nn,ℓ is the number of (compact-rooted) directed animals of size n − 1 with
n − 1 − ℓ source points, see [19, Table 1] and [24, sequence 005773]. In particular,
the highest value occurring in the n − 1st row of Figure 1 (the one that corresponds
to the divisors of ∆n ), namely Nn,n−2 and Nn,n−1 ,—that is, the sequence 1, 2, 5,
13, 35, ...—is the number of directed animals of size n − 1 with one source point.
Finding an explicit direct bijection between the divisors of ∆n in H + and size n − 1
directed animals [19, 29]—or, equivalently, “arbres guingois” or bicolored Motzkin
paths [2]—is a natural open question.
From (4.7) again, it is clear that the total number of left divisors of ∆n triples
when one goes from a row of the triangle to the next one, and, as ∆2 admits two
left divisors, we obtain
Proposition 4.13. For n > 2, the number of left divisors of ∆n in H + is 2 · 3n−2 .
P
P
The number of simple elements of index n is ℓ Nn,ℓ − ℓ Nn−1,ℓ , hence it is
4 · 3n−3 : so 2/3 of the left divisors of ∆n have index n, whereas 1/3 has index < n.

+
GARSIDE COMBINATORICS FOR F + AND A HYBRID WITH B∞

1

1

1

1

2

2

1

1

3

5

5

3

1

1

4

9

13

13

9

4

1

5

14

26

35

35

26

14

5

21

1

Figure 1. Generalized Pascal triangle generating the numbers Nn,ℓ :
each entry is the sum of the three entries above it: for instance, we
find N5,2 = 9 = 1 + 3 + 5 = N4,0 + N4,1 + N4,2 ; missing values are 0.
5. Normal form of simple elements
We complete the investigation of simple elements in H + by determining their normal form. In Section 2.4, we saw that normal elements of F + are those, whose normal form is a word in which the indices of the generators decrease, which amounts
to saying that a word is the normal form of a simple element if, and only if, it has
no factor θi θj with j > i. We shall establish below a similar result characterizing
the normal form of simple elements in terms of forbidden factors of length 2 and 3.
5.1. The key lemma. A direct inspection shows that the normal forms of the six
simple elements of index 6 3, i.e., of the six left divisors of ∆3 , are ε, θ1 , θ2 , θ1 θ2 ,
θ2 θ1 , and θ2 θ1 θ2 . The following result will then enable one to inductively determine
the normal form of a simple element according to its position in the partition of
Proposition 4.11.
Lemma 5.1. For every simple element a of index n > 4 in H + , there exists b of
index < n such that exactly one of the following holds:
(5.1)

(type I)

b 4 ∆n−1

and

nf(a) = θn−1 nf(b),

(5.2)

(type II1 )

b 4 ∆n−1.5

and

nf(a) = θn−2 θn−1 nf(b),

(5.3)

(type II2 )

θn−2 b 4 ∆n−1

and

nf(a) = θn−1 θn−2 θn−1 nf(b).

Proof. Let ℓ := |a|. By assumption, a belongs to Σn,ℓ \ Σn−1,ℓ . Then, by PropoII2
1
sition 4.11, a belongs to exactly one of ΣIn,ℓ , ΣII
n,ℓ , or Σn,ℓ . So there exists b such
that exactly one of the following holds:
(5.4)

(type I)

b 4 ∆n−1

and a = θn−1 b,

(5.5)

(type II1 )

b 4 ∆n−1.5

and a = θn−2 θn−1 b,

(5.6)

(type II2 )

θn−2 b 4 ∆n−1

and a = θn−1 θn−2 θn−1 b.

In the case of (5.4), we have b 4 ∆n−1 , so b is simple with ind(b) 6 n − 1. In the
case of (5.5), we have b 4 ∆n−1.5 4 ∆n−1.5 θ3n−8 = ∆n−1 , so, again, b is simple
with ind(b) 6 n − 1. Finally, in the case of (5.6), θn−2 b 4 ∆n−1 implies b 4 ∆n−1.5
by (4.5), whence b 4 ∆n−1 , so b is simple with ind(b) 6 n − 1. So, in every case, b is
simple with ind(b) < n = ind(a). Then, by definition of nf and by Proposition 4.2,
(5.7)

nf(b) is an EH -reduced word and its first letter is among θ1 , ..., θn−2 .

In the case of (5.4), (5.7) implies that θn−1 nf(b) is EH -reduced, hence it must
the normal form of θn−1 b, i.e., of a, and (5.1) is true. In the case of (5.5),

22

PATRICK DEHORNOY AND EMILIE TESSON

(5.7) implies that θn−2 θn−1 nf(b) is EH -reduced, hence it must the normal form
of θn−2 θn−1 b, i.e., of a, and (5.1) is true. Finally, in the case of (5.6), (5.7)
implies that θn−1 θn−2 θn−1 nf(b) is EH -reduced, hence it must the normal form
of θn−1 θn−2 θn−1 b, i.e., of a, and (5.1) is true.

An easy application of Lemma 5.1 is that, in addition to the obstructions of O,
certain factors cannot appear in the normal form of a simple element.
Lemma 5.2. Put
(5.8) OΣ := {θi2 | i > 1}∪{θi θi+2 | i > 1}∪{θi θi+1 θi | i > 1}∪{θi θi+1 θi+2 | i > 1}.
Then the normal form of a simple element of H + contains no factor in OΣ .
Proof. We prove the result for a simple element a using induction on the index n
of a. For n 6 3, a direct inspection of the six possible words gives the result.
Assume n > 4. By Lemma 5.1, there exists b simple of index <n such that exactly
one of (5.1), (5.2), or (5.3) holds. By induction hypothesis, the word nf(b) contains
no factor of OΣ , and we only have to check that the letters added to transform nf(b)
into nf(a) create no factor in OΣ . As the index of b is < n, Lemma 4.2 guarantees
that the first letter of nf(b) must be among θ1 , ..., θn−2 .
In the case of (5.1), nf(a) begins with θn−1 θj with 1 6 j 6 n − 2: this length 2
word is not in OΣ , and it is not the prefix of a word of OΣ either. Similarly, in the
case of (5.2), nf(a) begins with θn−2 θn−1 θj with 1 6 j 6 n − 3, and this length 3
word includes no factor in OΣ , nor can it contribute to a factor in OΣ . Finally,
in the case of (5.3), nf(a) begins with θn−1 θn−2 θn−1 θj with 1 6 j 6 n − 3, and,
again, this length 4 word includes no factor in OΣ , nor can it either contribute to
a factor in OΣ . So, in every case, the word nf(a) has no factor in OΣ .

We use Lemma 5.1 once more to establish a constraint about the first letter of
a normal word.
Lemma 5.3. If a 4 ∆n and θn−1 4 a hold, the first letter of nf(a) is θn−1 .
Proof. Assume a 4 ∆n and θn−1 4 a. So a is simple with ind(a) 6 n. If we had
ind(a) 6 n − 1, hence a 4 ∆n−1 , then θn−1 4 a would be impossible. So we must
have ind(a) = n. For n 6 3, a direct inspection of the six possible normal words
shows that the result is true. Otherwise, we apply Lemma 5.1. In the cases (5.1)
and (5.3), nf(a) explicitly begins with θn−1 . There remains the case of (5.2).
Assume a = θn−2 θn−1 b with b 4 ∆n−1.5 , let w represent b. By constructing a
PH -grid from (θn−1 , θn−2 θn−1 w), we see that θn−1 4 a is equivalent to θn+1 4 b,
hence it implies θn+1 4 b 4 ∆n−1.5 4 ∆n−1.5 θ3n−8 = ∆n−1 , which contradicts
Lemma 4.2. So θn−1 4 a excludes (5.2).

5.2. The normal form of simple elements. Our goal is now to establish that the
necessary condition of Lemma 5.2 is also sufficient, thus obtaining a combinatorial
characterization of the normal form of simple elements. We begin with a preliminary
observation about the indices of the generators θi that may appear in words with
no factor in OΣ .
Definition 5.4. We put ht(ε) := 0, and, for w nonempty in Θ∗ , we write ht(w) for
the largest i such that θi occurs in w.
Lemma 5.5. If θi v is EH -reduced with no factor in OΣ , then ht(v) 6 i + 1 holds.

+
GARSIDE COMBINATORICS FOR F + AND A HYBRID WITH B∞

23

Proof. We use induction on |v|. For |v| = 0, the result is vacuously true. Assume
|v| > 1, and write v = θj w. As θi v, i.e., θi θj w, is EH -reduced, it contains no factor
in O, hence j > i + 3 is excluded. On the other hand, as θi v has no factor in OΣ ,
the values j = i and j = i + 2 are impossible. So the only possible values for j are
1, ..., i − 1, and i + 1.
Assume first j 6 i − 1. As a factor of θi v, the word θj w is reduced with no
factor in OΣ . Then the induction hypothesis implies ht(w) 6 j + 1, whence ht(v) =
max(j, ht(w)) 6 j + 1 6 i + 1, as expected.
Assume now j = i+1. The result is true for |v| = 1: the word θi θi+1 has no factor
in OΣ and its height is i + 1. Assume now |v| > 2, and write v = θi+1 θk w. As v has
no factor in O, the values k > j + 3 = i + 4 are forbidden, and, as θi v has no factor
in OΣ , the values k = i, k = i + 1, and k = i + 2 are also excluded. So we must have
k 6 i − 1. As θk w is reduced with no factor in OΣ , the induction hypothesis implies
ht(w) 6 k + 1, whence ht(v) = max(i + 1, k, ht(w)) 6 max(i + 1, k + 1) = i + 1, as
expected.

Completing the characterization of the normal forms of simple elements then
relies on a long inductive argument.
Lemma 5.6. If u is a reduced word of Θ∗ with no factor in OΣ , then u is the
normal form of a simple element with index at most ht(u) + 1.
Proof. We will show using induction on m > 0 that, if u is an EH -reduced word
with no factor in OΣ and satisfying ht(u) = m, then [u] 4 ∆m+1 holds. This will
imply that [u] is simple with index 6 ht(u) + 1, giving the expected result when
m varies. So, herafter, we assume that u is EH -reduced, has no factor in OΣ , and
satisfies ht(u) = m; our aim is to establish [u] 4 ∆m+1 . As can be expected, the
various types of Proposition 4.11 will appear when we consider the possible cases.
For m = 0, the word u must be empty. We then find [u] = 1 4 ∆1 = ∆m+1 , as
expected. For m = 1, the only letter occurring in u is θ1 , so u is θ1ℓ for some ℓ > 1.
The assumption that u has no factor in OΣ requires ℓ = 1, whence u = θ1 . We
then find [u] = θ1 4 θ1 = ∆2 = ∆m+1 , as expected.
From now on, we assume m > 2. The word u cannot be empty, so it has a first
letter, say θi . By assumption, we have m = ht(u), hence i 6 m. On the other hand,
Lemma 5.5 implies ht(u) 6 i + 1, hence m 6 i + 1. Therefore, u must begin either
by θm , or by θm−1 .
Case 1. The first letter of u is θm−1 , say u = θm−1 v. The word v cannot be
empty, for otherwise we would have u = θm−1 and ht(u) = m − 1, contradicting the
assumption. Let θj be the first letter of v. By definition, we have j 6 ht(u) = m.
Moreover, u has no factor in OΣ , so j = m − 1 is impossible. On the other hand,
v, as a factor of u, is EH -reduced and has no factor in OΣ , so Lemma 5.5 implies
ht(v) 6 j + 1, and j 6 m − 2 would imply ht(u) 6 max(m − 1, ht(v)) 6 m − 1,
contradicting the assumption m = ht(u). So the only possibility is j = m, i.e., u
begins with θm−1 θm , say u = θm−1 θm w.
If w is the empty word, we have u = θm−1 θm . Applying (4.5) twice gives
∆m+1 = θm−1 θm ∆m−0.5 θ3m−2 , which implies [u] 4 ∆m+1 , as expected.
Assume now that w is nonempty, and let θk be its first letter. As w is a factor
of u, we must have k 6 m. As u, and its factor v, have no factor in OΣ , the values
k = m − 1 and k = m are impossible as they would respectively create some factor
2
θm−1 θm θm−1 and θm
. So, we necessarily have k < m − 1. Since w, as a factor of u,

24

PATRICK DEHORNOY AND EMILIE TESSON

is EH -reduced and has no factor in OΣ , Lemma 5.5 implies ht(w) 6 k + 1, whence
ht(w) 6 m − 1. The word w is EH -reduced with no factor in OΣ , so the induction
hypothesis implies [w] 4 ∆ht(w)+1 , hence a fortiori [w] 4 ∆m . Moreover, we know
that the first letter of w is not θm−1 . By Lemma 5.3, we deduce θm−1 64 [w], and
then, by Lemma 4.7(ii), [w] 4 ∆m−0.5 . By definition, this means that [u] belongs
1
to ΣII
m+1,|u| and, therefore, implies [u] 4 ∆m+1 , as expected.
Case 2. The first letter of u is θm , say u = θm v. If v is empty, we have u = θm ,
which has height m, and [u] = θm 4 ∆m+1 , as expected.
We now suppose v nonempty. Let θj be its first letter. The assumption ht(u) = m
implies j 6 m. As u has no factor in OΣ , the value j = m is impossible, since it
2
would create an initial factor θm
. So we have j 6 m − 1.
Subcase 2.1. We have j 6 m − 2. Then Lemma 5.5 implies ht(v) 6 m − 1.
Moreover, as a factor of u, the word v is EH -reduced and has no factor in OΣ .
The induction hypothesis then implies [v] 4 ∆ht(v)+1 , hence a fortiori [v] 4 ∆m .
Therefore, we have [u] = θm [v] with [v] 4 ∆m . This means that [u] lies in ΣIm+1,|u| ,
implying [u] 4 ∆m+1 , as expected.
Subcase 2.2. We have j = m − 1. Write v = θm−1 w, yielding u = θm θm−1 w.
If w is empty, we have u = θm θm−1 . Applying (4.5) twice gives the equality
∆m+1 = θm θm−1 ∆m−1 θ3n−7 θ3m−4 , whence [u] 4 ∆m+1 , as expected.
We assume now that w is nonempty, with first letter θk . The assumption
ht(u) = m implies k 6 m. Moreover, as u has no factor in OΣ , the value k = m − 1
2
.
is impossible, since it would create in position 2 a factor θm−1
Subsubcase 2.2.1. We have k 6 m − 2. As a factor of u, the word w is EH reduced and has no factor in OΣ , so Lemma 5.5 implies ht(w) 6 m − 1, whence
ht(v) = m − 1. As a factor of u, the word v is EH -reduced and has no factor in OΣ ,
so the induction hypothesis implies [v] 4 ∆ht(v)+1 , hence a fortiori [v] 4 ∆m . This
means that [u] lies in ΣIm+1,|u| and implies [u] 4 ∆m+1 , as expected.
Subsubcase 2.2.2. We have k = m. Write w = θm u′ , yielding u = θm θm−1 θm u′ .
If u′ is empty, we have u = θm θm−1 θm . A direct computation from (4.5) gives
∆m+1 = θm θm−1 θm ∆m−1 θ3n−7 , whence [u] 4 ∆m+1 , as expected.
We assume now that u′ is nonempty, with first letter θℓ . The assumption
ht(u) = m implies ℓ 6 m. The assumption that u has no factor in OΣ excludes
2
ℓ = m − 1 and ℓ = m, as these values would create factors θm−1 θm θm−1 or θm
in u.
′
Next, Lemma 5.5 implies ht(u ) 6 m − 1. Moreover, as a factor of u, the word u′ is
EH -reduced and has no factor in OΣ , so the induction hypothesis implies [u′ ] 4 ∆m .
By Lemma 5.3, if we had θm−1 4 [u′ ], the first letter of u′ should be θm−1 , contradicting ℓ 6 m − 2. Hence we have θm−1 64 [u′ ], whence [u′ ] 4 ∆m−0.5 by
Lemma 4.7. We then find θm−1 [u′ ] 4 θm−1 ∆m−0.5 = ∆m . Therefore, [u] has the
2
form θm θm−1 θm [u′ ] with θm−1 [u′ ] 4 ∆m . This means that [u] lies in ΣII
m+1,|u| and
implies [u] 4 ∆m+1 , as expected.
Thus, [u] 4 ∆m+1 holds in every possible case, and this completes the proof. 
Merging Lemmas 5.2 and 5.6, we finally obtain:
Proposition 5.7. A word of Θ∗ is the normal form of a simple element of H + if,
and only if, it contains no factor in O or OΣ .

+
GARSIDE COMBINATORICS FOR F + AND A HYBRID WITH B∞

25

Thus, the monoid H + gives rise to a Garside combinatorics that is quite similar
to that of the Thompson monoid F + . In both cases, we have a family of simple
elements that is filtered by the sequence (∆n )n>1 , with finitely many elements
below ∆n , namely 2n−1 in the case of F + and 2 · 3n−2 in the case of H + , and the
normal forms of simple elements are characterized in terms of finitely many types
of forbidden factors of length 2 or 3, namely the factors τi τj with j > i in the case
of F + , and the factors θi θj with j > i + 2 or j = i and the factors θi θi+1 θj with
j = i or j = i + 2 in the case of H + .
However, the parallel is not complete, as, in the case of H + , simple elements
do not form a Garside family. Indeed, the element θ2 θ4 is not simple, although
it right divides the simple element θ1 θ2 θ4 , i.e., ∆3 . It is easy to check that every
element of H + admits a greatest simple left divisor, namely its greatest common
left divisor with ∆n for n sufficiently large, and, from there, to show for every
element the existence of a greedy decomposition in terms of simple pieces, but
the decompositions so obtained fail to obey the good properties that make Garside
families interesting. In particular, the “domino rule” of [15, Prop. III.1.45], implying
that the elements of H + have no well defined degree in terms of simple elements.
The enveloping group of the monoid H + is the group H defined by the presentation PH . At this point, the most puzzling open problem about H + is
Question 5.8. Does the monoid H + embed in the group H?
The monoid H + is cancellative, but some pairs of elements of H + fail to admit a
common left multiple, or a common right multiple, and, therefore, contrary to F +
and F , the group H is not a group of (left or right) fractions for H + . As checking the
Malcev conditions [9] for H + seems problematic, a more realistic way for proving
that H + embeds in H could be to construct a faithful representation of H + in a
group of matrices. No such representation is known so far, but mapping θi to the
surjection Fi from Z>0 to itself defined by
Fi (k) := k for k 6 i + 1, Fi (i + 2) := i, and Fi (k) := k − 1 for k > i + 3
provides a representation ρ of H + that does not factor through F + . The images
of θ12 θ2 and θ1 θ2 θ3 under ρ coincide, so ρ is not faithful, but experiments reported
in [27] suggest that the polynomial deformation ρe of ρ that maps θi to the linear
transformation Fei defined by Fei (~x)k := xk for k 6 i, Fei (~x)k := xk−1 for k > i + 3,
plus
Fei (~x)i+1 := txi + (1 − t)xi+1

and Fei (~x)i+2 := (1 + t)xi − txi+1

could be faithful. The involved matrices are not invertible, so proving that ρe is
faithful would not solve Question 5.8 directly, but it could be a promising first step.
References
[1] S.I. Adyan, Fragments of the word Delta in a braid group, Mat. Zam. Acad. Sci. SSSR 36-1
(1984) 25–34; translated Math. Notes of the Acad. Sci. USSR; 36-1 (1984) 505–510.
[2] J. Bétréma & J.G. Penaud, Animaux et arbres guingois, Theor. Comp. Sci. 117 (1993) 67-89.
[3] J. Birman, K.H. Ko & S.J. Lee, A new approach to the word problem in the braid groups, Adv.
Math. 139-2 (1998) 322–353.
[4] E. Brieskorn & K. Saito, Artin-Gruppen und Coxeter-Gruppen, Invent. Math. 17 (1972) 245–
271.
[5] M. Brin, The algebra of strand splitting. I. A braided version of Thompson’s group V , J.
Group Th.; 10; 2007; 757–788.

26

PATRICK DEHORNOY AND EMILIE TESSON

[6] M. Brin, The algebra of strand splitting. II. A presentation for the braid group on one strand,
Intern. J. of Algebra and Computation 16 (2006) 203–219.
[7] M. Brin, On the Zappa-Szép product, Comm. in Algebra 33 (2005) 393–424.
[8] J.W. Cannon, W.J. Floyd, & W.R. Parry, Introductory notes on Richard Thompson’s groups,
Ens. Math. 42 (1996) 215–257.
[9] A.H. Clifford & G.B. Preston, The Algebraic Theory of Semigroups, volume 1, Math. surveys
vol.7, Amer. Math. Soc., (1967).
[10] P. Dehornoy, Groups with a complemented presentation, J. Pure Appl. Algebra 116 (1997)
115–137.
[11] P. Dehornoy, The group of parenthesized braids, Advances in Math. 205 (2006) 354–409.
[12] P. Dehornoy, The subword reversing method, Internat. J. Algebra Comput. 21 (2011) 71–118.
[13] P. Dehornoy, Tamari Lattices and the symmetric Thompson monoid, in: Associahedra,
Tamari lattices, and Related Structures, F.Mueller-Hoissen, J.Pallo, J.Stasheff, H.O.Walther
eds, Progress in Math. vol. 299, Birkhauser (2012), pp. 211-250.
[14] P. Dehornoy, A cancellativity criterion for presented monoids, arXiv:1802.04607.
[15] P. Dehornoy, with F. Digne, E. Godelle, D. Krammer, J. Michel, Foundations of Garside Theory, EMS Tracts in Mathematics, vol. 22 (2015).
[16] P. Deligne, Les immeubles des groupes de tresses généralisés, Invent. Math. 17 (1972) 273–
302.
[17] D. Epstein, with J. Cannon, D. Holt, S. Levy, M. Paterson & W. Thurston, Word Processing
in Groups, Jones & Bartlett Publ. (1992).
[18] F.A. Garside, The braid group and other groups, Quart. J. Math. Oxford 20-78 (1969) 235–
254.
[19] D. Gouyou-Beauchamps & G. Viennot, Equivalence of the two-dimensional directed animal
problem to a one-dimensional path problem, Adv. Appl. Math. 9 (1988) 334-357.
[20] D.F. Holt & S. Rees, Groups, languages and automata, London Math. Soc. Student Texts 88,
Cambridge Univ. Press (2017)
[21] R. McKenzie & R.J. Thompson, An elementary construction of unsolvable word problems in
group theory, in: Word Problems, W.W. Boone and al. eds, Studies in Logic and Foundations
of Mathematics, vol. 71, North Holland (1973), pp 457-478.
[22] M.H.A. Newman, On theories with a combinatorial definition of ”equivalence”, Ann. Math.
43 (1942) 223–243.
[23] Ø. Ore, Linear equations in non-commutative fields, Ann. Math. 34 (1933) 480–508.
[24] N. Sloane, foundator, A005773, The online encyclopedia of integer sequences;
https://oeis.org/.
[25] J. Szép, On factorisable, not simple groups, Acta Univ. Szeged. Sect. Sci. Math. 13 (1950)
239-241.
[26] Terese, Term Rewriting Systems, Vol. 55 of Cambridge Tracts in Theoretical Computer Science, Cambridge University Press (2003).
[27] E. Tesson, Un hybride du groupe de Thompson F et du groupe de tresses B∞ , Thèse université
de Caen (2018).
[28] R.J. Thompson, Tranformation structure of algebraic logic, PhD Thesis Univ. of Berkeley;
ProQuest LLC, Ann Arbor, MI (1979), 345 pages, MR2628711.
[29] G. Viennot, Problèmes combinatoires posés par la physique statistique, Séminaire Bourbaki
n 626, Astérisque 121-122 (1985) 225-246.
[30] G. Zappa, Sulla costruzione dei gruppi prodotto di due dati sottogruppi permutabili tra loro,
Atti Secondo Congresso Un. Mat. Ital., Bologna, Edizioni Cremonense, Rome (1942) pp.
119125.
Laboratoire de Mathématiques Nicolas Oresme UMR 6139, Université de Caen, 14032 Caen,
France
E-mail address: patrick.dehornoy@unicaen.fr
URL: dehornoy.users.lmno.cnrs.fr
Laboratoire de Mathématiques Nicolas Oresme UMR 6139, Université de Caen, 14032 Caen,
France

