arXiv:1802.04607v2 [math.GR] 7 Mar 2018

A CANCELLATIVITY CRITERION FOR PRESENTED MONOIDS
PATRICK DEHORNOY
Abstract. We establish a new, fairly general cancellativity criterion for a
presented monoid that properly extends the previously known criteria. It is
based on a new version of the word transformation called factor reversing,
and its specificity is to avoid any restriction on the number of relations in the
presentation. As an application, we deduce the cancellativity of some natural
extension of Artin’s braid monoid in which crossings are colored.

Establishing that a presented monoid (or semigroup) is cancellative is in general
a nontrivial task, see for instance [13]. If a distinguished expression (“normal form”)
has been identified for each element of the monoid, and if, for each element a of
the considered monoid M and every generator s of the considered presentation,
the normal form of a can be retrieved from that of sa and s, then one can indeed
conclude that sa = sb implies a = b. But, when no normal form is known, no
generic method is available. Adjan’s criterion based on the left graph [1, 15] is
useful, but, by definition, it applies only to presentations with (very) few defining
relations. Ultimately relying on Garside’s analysis of the braid monoids Bn+ [12],
the so-called reversing method [5, 8] provides a simple criterion, which proved to be
useful for many concrete presentations, typically those of all Artin–Tits monoids.
However, an intrinsic limitation of the method is that it only applies to monoid
presentations (S, R) that contain a limited number of relations, namely those such
that, for all s, t in S, there exists at most one relation of the form s... = t...
in R (“right-complemented” presentations). The aim of this paper is to extend the
previous criterion by developing a new approach that does not require any limitation
on the number of defining relations. The result we prove takes the following form:
Proposition. If (S, R) is a semigroup presentation such that
(i) there exists an ≡R -invariant map λ from S ∗ to ordinals satisfying λ(sw) > λ(w)
for all s in S and w in S ∗ , and
(ii) for every s in S, for every relation w=w′ in R, and for every (S, R)-grid
from (s, w), there exists an equivalent grid from (s, w′ ), and vice versa.
Then the monoid hS | Ri+ admits left cancellation.
In the above statement, ≡R refers to the congruence on the free monoid S ∗
generated by the relations of R, and an (S, R)-grid is a certain type of rectangular
van Kampen diagram specified in Definition 1.1 below. Note that Condition (i) in
the above statement is trivial when each relation in R consists of two words with
the same length (“homogeneous presentation”).
As an application, we deduce:
1991 Mathematics Subject Classification. 20B30, 20F55, 20F36.
Key words and phrases. semigroup presentation, van Kampen diagram, rewrite system, cancellativity, word problem, Garside monoid, group of fractions, monoid embeddability, Artin–Tits
groups.
1

2

PATRICK DEHORNOY

Proposition. For every n and every nonempty set C, the monoid
+

(b) (a)
(a) (b)
for |i − j| > 2
σi σj = σj σi
(a)
+
.
Bn,C
:= σi | i 6 n, a ∈ C
(c) (b) (a)
(a) (b) (c)
for |i − j| = 1
σi σj σi = σj σi σi
is left and right cancellative.
+
The monoid Bn,C
is an extension of Artin’s Bn+ of positive n-strand braids, and
it is a typical example of a monoid that is inaccessible to all previously known
+
methods. We shall see that the elements of Bn,C
admit a natural interpretation
+
and its enveloping
in terms of braids with C-colored crossings, and both Bn,C
group might be structures of independent interest. They are in particular directly
reminiscent of (but not identical to) the monoids investigated in [2].

1. Using reversing grids
As in [8], our cancellativity criterion is based on some word transformation called
factor (or subword) reversing, and on a criterion for establishing that the latter
is complete, meaning that it detects every word equivalence with respect to the
presentation. The specificity of the current paper is to extend the framework so as
to avoid any restriction on the number of relations in the presentation. This is done
by introducing the new notion of a reversing grid (Section 1.1), then establishing a
convenient completeness criterion (Section 1.2), and finally deducing the expected
cancellativity criterion an various other consequences (Section 1.3).
1.1. The notion of a reversing grid. If S is a nonempty set, we denote by S ∗ the
free monoid of all words in S, and use ε for the empty word. A monoid presentation
is a pair (S, R), where R is a list of (unordered) pairs of words of S ∗ ; as usual,
we write relations with an equality sign, thus writing w=w′ for {w, w′ }. We then
denote by hS | Ri+ the monoid presented by (S, R), that is, the monoid S ∗ /≡R ,
where ≡R is the congruence on S ∗ generated by R.
By a semigroup presentation we mean a monoid presentation (S, R) such that R
contains no relation of the form w=ε with w 6= ε (“ε-relation”). In this case, the
only invertible element in hS | Ri+ is the unit 1, represented by the empty word.
Our main subject of investigation is a certain binary relation (or rewrite system)
on S × S associated with (S, R) as follows.
Definition 1.1. If (S, R) is a monoid presentation, an (S, R)-grid is a rectangular
diagram consisting of finitely many matching S ∪ {ε}-labeled pieces of the types
t
s1

-s

sp

tq

t1
s
- s

with s, t, s1 , ..., sp , t1 , ..., tq in S
and st1 ··· tq = ts1 ··· sp a relation of R,
ε

ε,

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 . If there exists an
(S, R)-grid from (u, v) to (u1 , v1 ), we say that (u, v) is right R-reversible to (u1 , v1 ),

A CANCELLATIVITY CRITERION FOR PRESENTED MONOIDS

3

v
written (u, v) yR (u1 , v1 ) or, in a diagrammatic way, u

yR

u1; we then

v1

often skip R if there is no ambiguity.

Example 1.2. Consider the Artin presentation of the n-strand braid monoid
+

σi σj = σj σi
for |i − j| > 2
(1.1)
Bn+ := σ1 , ..., σn−1
.
σi σj σi = σj σi σj for |i − j| = 1
For n > 4, a typical grid for (1.1) is
σ2

σ3

σ1
(1.2)

σ3

σ1

σ1

σ1
σ2

σ2
σ2

σ2

σ3
σ2

σ3

σ1
σ2

σ1

σ2

ε ε
σ3
ε

σ1

ε
σ3

σ1

It contains eight squares, of which five correspond to relations of (1.1), and it goes
from (σ1 , σ2 σ3 σ2 ) to (σ1 σ2 σ3 , σ2 σ1 σ3 σ2 σ1 ), witnessesing for the right reversing relation
σ2 σ3 σ2
(σ1 , σ2 σ3 σ2 ) y (σ1 σ2 σ3 , σ2 σ1 σ3 σ2 σ1 ), alias σ1

σ1 σ2 σ3 .

y
σ2 σ1 σ3 σ2 σ1

In all five types of elementary pieces considered in Definition 1.1, the labels of the
two possible paths from the top-left vertex to the bottom-right vertex form words
that are ≡R -equivalent, i.e., represent the same element in the monoid hS | Ri+ .
An easy induction on the number of elementary pieces implies:
Lemma 1.3. For every monoid presentation (S, R), and for all words u, v, u1 , v1
in S ∗ , the relation (u, v) yR (u1 , v1 ) implies uv1 ≡R vu1 . In particular,
(1.3)

(u, v) yR (ε, ε)

implies

u ≡R v.

In other words, a reversing grid from (u, v) to (u1 , v1 ) is a special type of van
Kampen diagram witnessing for the ≡R -equivalence of the words uv1 and vu1 .
Remark 1.4. In literature [5, 6, 7, 11], reversing was described in terms of signed
S-words, defined to be words in a symmetrized alphabet S ∪ S with S consisting
of one copy s for each letter s of S. If w, w′ are signed S-word, one declares that
w yR w′ holds if one can go from w to w′ by a finite sequence of transformations,
each of which consists either in deleting some length two factor ss, or in replacing
some length two factor st with t1 ··· tq sp ··· s1 , where st1 ··· tq = ts1 ··· sp is a relation
of R. The connection with our current approach is easy: writing w for the word
obtained from w by exchanging s and s everywhere and reversing the order of letters,
the relation (u, v) yR (u1 , v1 ) of Definition 1.1 is equivalent to uv yR v1 u1 in the
sense of signed word reversing. The advantage of the current description is to make
it more visible that reversing only involves positive words and the presented monoid,
without connection with inverting the elements and moving to a group context. In
any case, the reversing grid is the fundamental object, and it seems more natural
to begin with it.

4

PATRICK DEHORNOY

One of the advantages of the current grid-based approach is to make the following
technical result almost straightforward:
Lemma 1.5. For every monoid presentation (S, R), and for all u, v ′ , v ′′ , u1 , v1
in S ∗ , the following are equivalent:
(i) The relation (u, v ′ v ′′ ) yR (u1 , v1 ) holds;
(ii) There exist u′ , v1′ , v1′′ in S ∗ satisfying (u, v ′ ) yR (u′ , v1′ ), (u′ , v ′′ ) yR (u1 , v1′′ ),
and v1 = v1′ v1′′ .
Proof. Assume that Γ is an (S, R)-grid from (u, v ′ v ′′ ) to (u1 , v1 ). By definition, Γ
is a juxtaposition of elementary diagrams as in Definition 1.1.
Grouping the diagrams that lie below v ′ on the one hand,
v′
v ′′
′′
′
and below v on the other hand, splits Γ into two grids Γ
y
u′ y
u1
and Γ′′ . By construction, the input of Γ′ is (u, v ′ ); call u
′ ′
′
its output (u , v1 ). Then, by construction, the input of Γ
v1′
v1′′
is (u′ , v ′′ ), and its output has the form (u1 , v1′′ ), with
v
1
v1 = v1′ v1′′ . So (i) implies (ii).
Conversely, concatenating a grid from (u, v ′ ) to (u′ , v1′ ) and a grid from (u′ , v ′′ )
to (u1 , v1′′ ) provides a grid from (u, v ′ v ′′ ) to (v1′ v1′′ , u1 ), so (ii) implies (i).

1.2. Completeness of reversing. A reversing grid is a van Kampen diagram of a
special type, namely one in which at most two edges (one horizontal, one vertical)
start from each node. If there exists an (S, R)-grid from (u, v) to (ε, ε), then, by
Lemma 1.3, the words u and v must be ≡R -equivalent. Conversely, if u and v are
≡R -equivalent words, there must exist a van Kampen diagram connecting u and v
but, in general, there is no reason why the latter could be chosen with the special
form of a reversing grid. We now consider the case when such a choice is possible.
Definition 1.6. We say that right reversing is complete for a monoid presentation (S, R) if the converse of (1.3) also holds, that is, if, for all u, v in S ∗ ,
(1.4)

(u, v) yR (ε, ε)

is equivalent to

u ≡R v.

This definition is theoretical, and our aim will be is to establish a practical criterion characterizing completeness of reversing. Two such criteria have already
appeared. A first criterion is described in [7], in terms of what is called the cube
condition: in principle, this criterion works for arbitrary presentations but, in practice, it can be used only for complemented presentations, namely presentations with
at most one relation s... = t... for each pair of generators (s, t). Another criterion
is described in [6], but, even in theory, it does not apply to presentations that are
not complemented. What we do below is to establish a new completeness criterion
that extends the one of [6] and works for every presentation, complemented or not.
The main point is that this new criterion, contrary to the cube condition, remains
tractable in the non-complemented case, i.e., without any restriction on the number
of relations in the considered presentation.
It follows from the definition of a reversing grid that reversing can be complete
only for semigroup presentations, that is, for presentations containing no ε-relation:
indeed, by definition, (w, ε) y (ε, ε) is impossible for w nonempty. So we shall hereafter restrict to semigroup presentations. We start from the following observation.
Lemma 1.7. Let (S, R) be a semigroup presentation. Say that two (S, R)-grids Γ, Γ′
are equivalent if the labels of the four edges of Γ form words that are ≡R -equivalent

A CANCELLATIVITY CRITERION FOR PRESENTED MONOIDS

5

to their counterparts in Γ′ . Then a sufficient condition for right reversing to be
complete for (S, R) is that, for all u, v in S ∗ ,
(♦∗ )

For every grid from (u, v), and for all u′ , v ′ satisfying u′ ≡R u and v ′ ≡R v,
there is an equivalent grid from (u′ , v ′ ).

Proof. Assume that (♦∗ ) holds for all u, v in S ∗ , and let u, u′ be ≡R -equivalent
words. A trivial induction on the length of u shows
u
that there exists a grid Γ from (u, u) to (ε, ε), as
s1
sℓ
shown on the right. Applying (♦∗ ) to Γ and to the
s1
ε ε
ε
equivalences u ≡R u and u ≡R u′ , we conclude that
′
′
ε
s
ℓ
there exists a grid Γ from (u, u ) that is equivalent
u
sℓ
ε
to Γ. Let (u′1 , v1′ ) be the output of Γ′ . Then, by
assumption, we have u′1 ≡R ε and v1′ ≡R ε. Because
sℓ
sℓ sℓ
ε
R contains no ε-relation, u′1 ≡R ε implies u′1 = ε,
ε
ε
and, similatly, v1′ ≡R ε implies v1′ = ε.
′
′
Then Γ witnesses that (u, u ) right-reverses to (ε, ε). Therefore, right reversing is
complete for (S, R).

As it stands, Lemma 1.7 does not provide a tractable criterion, because it involves arbitrary pairs of ≡R -equivalent words in S ∗ . We show now that, under
convenient finiteness assumptions (“noetherianity”), the most elementary instances
of compatibility are sufficient to deduce the full condition.
If M is a monoid and g, h belong to M , one says that g properly right-divides h,
written g ≺R h or h ≻R g, if h = h′ g holds for some non-invertible element h′ of M
(proper left-division ≺L would be defined symmetrically with g on the left).
Definition 1.8. A monoid M is called right noetherian if there is no no infinite
descending sequence with respect to proper right-divisibility relation in M , that is,
every sequence g0 ≻R g1 ≻R ... in M is finite.
Lemma 1.9. For every monoid M , the following are equivalent:
(i) The monoid M is right noetherian.
(ii) There exists a map λ from M to ordinals such that, for all g, g ′ in M ,
(1.5)

g ≻R g ′ implies λ(g) > λ(g ′ ).

(iii) There exists a map λ from M to ordinals satisfying, for all g, h in M ,
(1.6)

λ(gh) > λ(h) + λ(g), and λ(g) > 0 whenever g is non-invertible.

Proof. The equivalence of (i) and (ii) is standard: for ≻R to admit no infinite
descending sequence means that the relation ≻R is well-founded, and it is well
known that this amounts to the existence of a map to the ordinals that decreases
along ≻R .
Next, (iii) implies (ii): indeed, assuming g = hg ′ with h non-invertible and
applying (1.6), we obtain λ(g) > λ(g ′ ) + λ(h) > λ(g ′ ).
Finally, assume (i), whence (ii). As above, the relation ≻R is well founded, so,
by standard arguments, there exists a map λ : M → Ord inductively defined by
(
0
if g is invertible,
(1.7)
λ(g) :=
max{λ(f ) + 1 | f ≺R g} otherwise.
We claim that this particular function λ, which satisfies (1.5) by construction, also
satisfies (1.6). First, we observe that, if g is not invertible, then g ≻R 1 is true,

6

PATRICK DEHORNOY

so we must have λ(g) > λ(1) = 0. So the second assertion in (1.6) is true. Next,
we observe that, if g is invertible, then λ(gh) > λ(h) holds. Indeed, the inequality
is trivial for λ(h) = 0, and, otherwise, the sets {f | f ≺R h} and {f | f ≺R gh}
coincide, and we deduce
λ(gh) = max{λ(f ) + 1 | f ≺R gh} = max{λ(f ) + 1 | f ≺R h} = λ(h).
We prove now using induction on λ(g) that λ(gh) > λ(h) + λ(g) holds for every h
in M . Assume first λ(g) = 0. Then g must be invertible, and we established above
the equality λ(gh) = λ(h) = λ(h) + λ(g), as expected. Assume now λ(g) > 0. Then
g is not invertible and, by definition, we have λ(g) = max{λ(f ) + 1 | f ≺R g}. Let h
be an arbitrary element of M . Then gh is not invertible, and we obtain
λ(gh) = max{λ(f ) + 1 | f ≺R gh}

by definition

> max{λ(f h) + 1 | f ≺R g}

because f ≺R g implies f h ≺R gh

> max{λ(h) + λ(f ) + 1 | f ≺R g}

by induction hypothesis

= λ(h) + max{λ(f ) + 1 | f ≺R g}

by monotonicity of ordinal addition

= λ(h) + λ(g)

by definition.

Thus the first inequality in (1.6) is established, and (i) implies (iii).



Translating the previous result at the level of presentations, we can state:
Lemma 1.10. If (S, R) is a semigroup presentation, the monoid hS | Ri+ is right
noetherian if, and only if, the following equivalent conditions hold:
(1.8)
(1.9)

there exists an ≡R -invariant map λ from S ∗ to the ordinals
satisfying λ(sw) > λ(w) for all s in S and w in S ∗ ;
there exists an ≡R -invariant map λ from S ∗ to the ordinals
satisfying λ(uv) > λ(v) + λ(u) for all u, v in S ∗ , and λ(s) > 0 for s in S.

Thus, (1.8) provides a sufficient condition for right noetherianity, and then one
is ensured that the stronger condition (1.9) can be satisfied (possibly by another
map λ′ ). As already noted, in the case of a homogeneous presentation, i.e., one
where all relations have the form w=w with w, w′ of the same length, defining λ(w)
to be the length of w provides a map λ witnessing for (1.9).
The main technical result we shall establish is the following criterion for the
completeness of reversing:
Lemma 1.11. A semigroup presentation (S, R) satisfying (1.8) satisfies (♦∗ ) if,
and only if, for every element 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.
′
Proof. One implication is trivial: (♦) for s and w=w follows from applying (♦∗ )
to the words s and w with the equivalences s ≡R s and w′ ≡R w.
The point is to establish the converse implication. This will be done using two
nested inductions. First, we fix a map λ from S ∗ to ordinals satisfying (1.9), which
is possible by Lemma 1.10. By the properties of ordinal addition, we always have
(♦)

(1.10)

λ(u) 6 λ(uv),

λ(v) 6 λ(uv),

and λ(v) < λ(uv) for u nonempty.

If Γ is a (S, R)-grid from (u, v) to (u1 , v1 ), the parameter λ(uv1 ), which, by
Lemma 1.3, is also equal to λ(vu1 ), will be called the diagonal of Γ. Then, for α

A CANCELLATIVITY CRITERION FOR PRESENTED MONOIDS

7

an ordinal, we introduce the special case of Condition (♦∗ ) corresponding to grids
whose diagonal is at most α:
For every grid with diagonal 6 α from (u, v), and for all u′ , v ′ satisfying
u′ ≡R u and v ′ ≡R v, there is an equivalent grid from (u′ , v ′ ).

(♦α∗ )

Next, for w, w′ in S ∗ , we write distR (w, w′ ) for the combinatorial distance between w and w′ with respect to R, namely the minimal length of an R-derivation
from w to w′ if w and w′ are ≡R -equivalent, and ∞ otherwise. Then, for d a natural
number, we consider the special case of Condition (♦α∗ ) corresponding to distances
between the sources of the old and new grids bounded by d:
∗
(♦α,d
)

For every grid with diagonal 6 α from (u, v), and for all u′ , v ′ satisfying
distR (u, u′ ) + distR (v, v ′ ) 6 d, there is an equivalent grid from (u′ , v ′ ).

It should be clear that (♦∗ ) for two words u, v is equivalent to the conjunction
∗
of all (♦α,d
) for u, v. Using an induction on α and, for a given α, on d, we shall
∗
establish that, if (♦) is true for every s and every relation w=w′ of R, then (♦α,d
)
is true for all u, v.
Assume first α = 0. Assume that Γ is a grid with zero diagonal from (u, v)
to (u1 , v1 ), and u′ ≡R u and v ′ ≡R v hold. By construction, λ(w) = 0 implies
w = ε, so λ(uv1 ) = λ(vu1 ) = 0 requires u = v = u1 = v1 = ε. Next, the
assumption u′ ≡R ε implies u′ = ε = u, and v ′ ≡R v implies v ′ = ε = v. Then
choosing Γ′ := Γ provides the expected condition. So (♦0∗ ) is true for all u, v.
Assume now α > 0 and d = 0. Assume that Γ is a grid with diagonal 6 α
from (u, v) to (u1 , v1 ), and distR (u, u′ ) + distR (v, v ′ ) = 0 holds. By definition, we
have u′ = u and v ′ = v. Then choosing Γ′ := Γ provides the expected condition.
∗
) is true for all u, v and for every α.
So (♦α,0
Assume now α > 0 and d = 1. Assume that Γ is a grid with diagonal 6 α
from (u, v) to (u1 , v1 ), and distR (u, u′ ) + distR (v, v ′ ) = 1 holds. Up to a symmetry,
we may assume u′ = u and distR (v ′ , v) = 1. By definition, the latter relation means
that there exists a relation w=w′ in R and two words v0 , v2 satisfying v = v0 wv2
and v ′ = v0 w′ v2 . As v is the product v0 wv2 , repeated applications of Lemma 1.5
show that the assumption (u, v) yR (u1 , v1 ) implies the existence of u0 , u2 and v3 ,
v4 , and v5 satisfying v1 = v3 v4 v5 and
(u, v0 ) yR (u0 , v3 ),

(u0 , w) yR (u2 , v4 ),

and (u2 , v2 ) yR (u1 , v5 ),

corresponding to a decomposition of the grid Γ into the union of three grids

u

v0

v
w

v2

y

u0 y

u2 y

v3

v4
v1

v5

u1

8

PATRICK DEHORNOY

Assume first that the word u0 is empty. Then, necessarily, we have u1 = u2 = ε,
v4 = w, and v5 = v2 . Then the situation is as the left diagram below
v
w

v0
u

ε

y

v2
ε

y

v3

w
v1

y

v′
w′

v0
ε

u

v2

y

ε

v3

y

v2
ε

y

ε

v2

w′
v1′

∗
and the right diagram shows that (♦α,1
) is satisfied with u′1 := ε and v1′ := v3 w′ v2 .
Assume now that u0 is not empty. Then we write u0 = su3 with s in S. Splitting
the grid again, we obtain the existence of words u4 , ..., u7 and v6 , v7 such that the
situation is as in the left diagram below

v
w

v0
s
u

y

v3

v0

v2
u6

v6

u4 y
v7

u3 y

u5 y

u7

v4
v1

v5

y

v′
w′
s

u

u1

y

v3

y

v6′
u3 y
v4′
v1′

v2
u′4

y u′6

v7′
u′5 y u′7

u′1

v5′

We shall now establish the existence of words u′3 , ..., u′7 and v4′ , ..., v7′ such that the
right diagram above is a legitimate (S, R)-grid, with u′i ≡R ui and vj′ ≡R vj for
all i and j.
We begin with the top median square. By assumption, we have (s, w) yR
(u4 , v6 ) and w=w′ ∈ R. By (♦), there exist u′4 and v6′ satisfying
u′4 ≡R u4 ,

v6′ ≡R v6

and

(s, w′ ) yR (u′4 , v6′ ).

Consider now the bottom median square. Then u3 ≡R u3 is trivial, whereas
v6′ ≡R v6 and (u3 , v6 ) yR (u5 , v4 ) hold by construction. Moreover, (1.10) implies
λ(u3 v4 ) < λ(su3 v4 ) 6 λ(v0 su3 v4 ) 6 λ(v0 su3 v4 v5 ) = λ(uv1 ) 6 α,
whence β := λ(u3 v4 ) < α. By induction hypothesis, (♦β∗ ) is true for u3 and v6 , and
we deduce the existence of u′5 and v4′ satisfying
u′5 ≡R u5 ,

v4′ ≡R v4

and

(u3 , v6′ ) yR (u′5 , v4′ ).

We move to the top right square. Then v2 ≡R v2 is trivial, whereas u′4 ≡R u4
and (u4 , v2 ) yR (u6 , v7 ) hold by construction. Moreover, because w cannot be
empty, since R contains no ε-relation, (1.10) implies
λ(u4 v7 ) < λ(wu4 v7 ) 6 λ(v0 wu4 v7 ) 6 λ(v0 wu4 v7 u7 ) = λ(uv1 ) 6 α,
whence γ := λ(u4 v7 ) < α. By induction hypothesis, (♦γ∗ ) is true for u4 and v2 , and
we deduce the existence of u′6 and v7′ satisfying
u′6 ≡R u6 ,

v7′ ≡R v7

and

(u′4 , v2 ) yR (u′6 , v7′ ).

A CANCELLATIVITY CRITERION FOR PRESENTED MONOIDS

v7′

9

Finally, we consider the bottom right square. By construction, we have u′5 ≡R u5 ,
≡R v7 and (u5 , v7 ) yR (u7 , v5 ). Moreover, (1.10) implies
λ(u5 v5 ) 6 λ(v6 u5 v5 ) < λ(sv6 u5 v5 ) 6 λ(v0 sv6 u5 v5 ) = λ(uv1 ) 6 α,

whence δ := λ(u5 v5 ) < α. By induction hypothesis, (♦δ∗ ) is true for u5 and v7 , and
we deduce the existence of u′7 and v5′ satisfying
u′7 ≡R u7 ,

v5′ ≡R v5

and

(u′5 , v7′ ) yR (u′7 , v5′ ).

Put u′1 := u′6 u′7 and v1′ := v3 v4′ v5′ . Then u′1 ≡R u1 and v1′ ≡R v1 hold, and the
∗
right diagram below witnesses for (v, v ′ ) yR (u′1 , v1′ ). Thus (♦α,1
) is satisfied for u
∗
and v, which completes the case d = 1 in the induction for (♦α ).
Assume finally α > 0 and d > 2. Assume that Γ is a grid with diagonal 6 α
from (u, v) to (u1 , v1 ), and distR (u, u′ ) + distR (v, v ′ ) = d holds. We can find two
words u′′ , v ′′ satisfying
distR (u′′ , u) + distR (v ′′ , v) = d − 1

and distR (u′ , u′′ ) + distR (v ′ , v ′′ ) = 1.

∗
By assumption, we have λ(uv1 ) 6 α. By induction hypothesis, (♦α,d−1
) is true
′′ ′′
for u and v, so we deduce the existence of u1 , v1 satisfying

u′′1 ≡R u1 ,

v1′′ ≡R v1 ,

and (u′′ , v ′′ ) yR (u′′1 , v1′′ ).

Now u′′ ≡R u and v1′′ ≡R v1 imply λ(u′′ v1′′ ) = λ(uv1 ) 6 α. By induction hypothesis,
∗
) is true for u′′ and v ′′ , so we deduce the existence of u′1 , v1′ satisfying
(♦α,1
u′1 ≡R u′′1 ,

v1′ ≡R v1′′ ,

and (u′ , v ′ ) yR (u′1 , v1′ ).

By transitivity of ≡R , we have u′1 ≡R u1 and v1′ ≡R v1 , and we conclude that
∗
) is true for u and v. This completes the induction.

(♦α,d
1.3. Main results. We are now ready to state the main results of the paper and,
in particular, to establish the cancellativity criterion announced in the title.
First, summarizing the results established so far directly gives the following:
Proposition 1.12. Assume that a semigroup presentation (S, R) satisfies (1.8)—
which is true in particular if (S, R) is homogeneous—and (♦) for every s in S and
every relation w=w′ in R.
(i) For all u, v, u1 , v1 in S ∗ satisfying (u, v) yR (u1 , v1 ), and for all u′ , v ′ in S ∗
satisfying u′ ≡R u and v ′ ≡R v, there exist u′1 , v1′ satisfying (u′ , v ′ ) yR (u′1 , v1′ ),
with u′1 ≡R u1 and v1′ ≡R v1 .
(ii) For all u, v in S ∗ , the words u and v represent the same element of the
monoid hS | Ri+ if, and only if, (u, v) yR (ε, ε) holds.
Proof. Point (i) is Condition (♦∗ ) for u, v, and Lemma 1.11 states that the latter
holds whenever (1.8) holds and so does (♦) for every s in S and every relation w=w′
in R.
(ii) By Lemma 1.7, (i), that is, (♦∗ ) for all u, v, implies that reversing is complete
for (S, R), which, by definition, implies the equivalence of (ii).

Let us turn to left cancellability. Then completeness of right reversing is useful,
as it shows that, if there is no obvious counter-example to left cancellativity, then
there is no hidden counter-example either:
Lemma 1.13. If right reversing is complete for the presentation (S, R) and R
contains no relation of the form su = sv with s in S and u 6= v in S ∗ , then the
monoid hS | Ri+ admits left cancellation.

10

PATRICK DEHORNOY

Proof. It is enough to prove that, for all words u, v in S ∗ , every relation of the form
s
v
su ≡R sv with s in S implies u ≡R v. So assume su ≡R sv.
By completeness of right reversing, we deduce (su, sv) yR s
u1
ε
(ε, ε). By Lemma 1.5, a grid witnessing for (su, sv) yR (ε, ε)
v1
v2
decomposes into four grids, as shown on the right. The assumpu2
ε
tion about the presentation requires u = v = ε, which in turn u
1

1

implies u2 = u and v2 = v.
ε
ε
Then the bottom right square witnesses for (u, v) yR (ε, ε), which, by Lemma 1.3,
implies u ≡R v.

Putting things together, we deduce the practical cancellativity criterion that is
the main result of this paper, as stated in the preamble of the paper:
Proposition 1.14. Assume that a semigroup presentation (S, R) satisfies (1.8)—
which is true in particular if (S, R) is homogeneous—and (♦) for every s in S and
every relation w=w′ in R. Then a sufficient condition for the monoid hS | Ri+ to
be left cancellative is that there is no relation sw = sw′ with w 6= w′ in R.
Of course, a symmetric criterion exists for right cancellativity: right noetherianity is to be replaced with left noetherianity, meaning the non-existence of an infinite
descending sequence with respect to proper left divisibility, and right reversing grids
are to be replaced with their left counterparts, in which one starts from the bottom
and right edges and uses the relations to build a rectangular diagram in which the
output corresponds to the left and top edges. Note that a right reversing grid is
not a left reversing grid, in particular because “cancellation squares” are not the
s
ε
same: s

ε in a right reversing grid, to be compared with ε

ε
reversing grid.

s in a left
s

Remark 1.15. Contrary to Adjan’s cancellability criterion of [1, 15], the criterion
of Proposition 1.14 does not guarantee that the monoid embeds in its enveloping
group. For instance, consider the monoid M with presentation
(1.11)

ha, b, c, d, a′, b′ , c′ , d′ | ac = bd, ac′ = bd′ , a′ c = b′ di+ .

The monoid M fails to satisfy the first Malcev condition [4, Chapter 12] and,
therefore, it does not embed in its enveloping group. However, the presentation
of (1.11) is eligible for the cancellability criterion of Proposition 1.14—but not for
Adjan’s criterion, since (a, b) is a cycle in the left graph.
We conclude with one more application of completeness of right reversing, now
in terms of common (right) multiples.
Proposition 1.16. Assume that a semigroup presentation (S, R) satisfies (1.8)—
which is true in particular if (S, R) is homogeneous—and (♦) for every s in S
and every relation w=w′ in R. Then two elements a, b of hS | Ri+ respectively
represented by words u and v in S ∗ admit a common right multiple if, and only if,
there exists at least one (S, R)-grid from (u, v); in this case, every common right
multiple of a and b is a right multiple of an element represented by uv1 and by vu1
with u1 , v1 satisfying (u, v) yR (u1 , v1 ).

A CANCELLATIVITY CRITERION FOR PRESENTED MONOIDS

11

Proof. Assume that there exists a grid from (u, v), say (u, v) yR (u1 , v1 ). By
Lemma 1.3, this implies uv1 ≡R vu1 , which shows that the element of hS | Ri+
represented by uv1 and vu1 is a common right multiple of a and b.
v
u′
Conversely, assume that c is a common right multiple of a and b:
this means that there exist words u′ , v ′ such that c is repre- u
u1
ε
sented by uv ′ and vu′ , which therefore satisfy uv ′ ≡R vu′ . Unv2
der the assumptions, right reversing is complete for (S, R), so ′ v1
v
u
ε
′
′
2
(uv , vu ) yR (ε, ε) holds. Splitting a reversing grid in four
pieces as shown on the right, we see that there exists a grid
ε
ε
from (u, v), and that the equivalences u′ ≡R u1 v2 , v2 ≡R u2 , and v ′ ≡R v1 u2
are satisfied. The latter show that c is a right multiple of the element represented
by uv1 and vu1 .

Corollary 1.17. Assume that a semigroup presentation (S, R) satisfies the assumptions of Proposition 1.16 and, moreover, it is right complemented, i.e., if, for
all s, t in S, there is at most one relation s...=t... in R. Then two elements a, b
of hS | Ri+ respectively 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 and vu1 is a right lcm of a and b.
Proof. The assumption that (S, R) is right complemented implies that an (S, R)grid from (u, v) is unique when it exists. Thus, Proposition 1.16 says that every
common right multiple of a and b is a right multiple of the element represented
by uv1 . So the latter element, when it exists, is a right lcm of a and b.

Specializing even more, we finally obtain:
Corollary 1.18. Assume that a semigroup presentation (S, R) satisfies the assumptions of Proposition 1.16 and, moreover, for all s, t in S, the exist s′ , t′ in S
such that st′ =ts′ is a relation of R. Then any two elements of the monoid hS | Ri+
admit a right lcm.
Proof. The presentation is eligible for Corollary 1.17, so we know that any two elements with a common right multiple admit a right lcm. The additional assumption
about (S, R) guarantees that, for all words u, v in S ∗ , there exists one (S, R)-grid
from (u, v): indeed, obstructions arise when a relation s...=t... is missing, and when
the process never terminates because smaller and smaller arrows appear without
end. The assumption that there always exist a relation s...=t... discards the first
obstruction; the assumption that the relations involve words of length 6 2 discards
the second one. Thus, any two elements of the monoid hS | Ri+ admit a common
right multiple, hence a right lcm.

Remark 1.19. The cancellativity criterion of Proposition 1.14 subsumes the one
established in [6] in the case of a right complemented presentation. In such a case,
there exists at most one (R, S)-grid admitting a given source (u, v), and, therefore,
the output words can be seen as functions of u and v. Then, the cancellativity
criterion can be stated as a compatibility of the functions in question, called “complement”, with the equivalence relation ≡R . In our general case, the scheme of the
proof remains the same, but one needs to find a different formalism, which makes
the extension nontrivial. In [6], in addition to qualitative aspects, some quantitative results are established, and they can be extended to our current framework.

12

PATRICK DEHORNOY

Say that a semigroup presentation (S, R) has defect d if, for every s in S, every
relation w=w′ in R, and every (S, R)-grid Γ from (s, w), there exists an equivalent
(S, R)-grid Γ′ from (s, w′ ) such that the cumulated distances between the output
words of Γ and Γ′ is bounded above by d, and d is minimal with that property.
Then the inductive proof of Proposition 1.11 can be adapted to show that, if (S, R)
has finite defect d and Γ is a grid from (u, v), then, for all u′ ≡R u and v ′ ≡R v,
there exists an equivalent grid Γ′ from (u′ , v ′ ) such that the distance between the
outputs of Γ and Γ′ is bounded by an explicit function of the distance between their
inputs, actually a double exponential of base d. We do not go into details.
2. Applications to variants of braid monoids
As an application of the results of Section 1, we now establish that the monoids
of colored braids, which are extensions of the classical Artin braid monoids, admit
cancellation.
2.1. Braids with colored crossings. We mentioned in Example 1.2 that, for
n > 1, the standard n-strand monoid Bn+ is the monoid presented by (1.1). We
recall, for instance from [3] or [10], that, under interpreting σi as the elementary
crossing that exchanges the strands at positions i and i + 1 as in
1
σi :

2

i−1
···

i

i+1 i+2

n
···

the monoid Bn+ is the monoid of isotopy classes of positive n-strand braid diagrams.
We now consider an extension of the monoid Bn+ :
Definition 2.1. For n > 1 and C a nonempty set, the monoid of positive C-colored
braids is the monoid with presentation
+

(b) (a)
(a) (b)
for |i − j| > 2
σi σj = σj σi
(a)
+
.
(2.1) Bn,C := σi | i 6 n, a ∈ C
(c) (b) (a)
(a) (b) (c)
for |i − j| = 1
σi σj σi = σj σi σj
(a)

The idea is that the generator σi corresponds (as usual) to a crossing at positions i and i+1 with, in addition, an attached “color” a in C. The relations of (2.1)
are then natural if we imagine that the colors are connected with the names, or
initial positions, of the strands (as opposed to the current positions). Typically, we
may think of taking for C the set of all (unordered) pairs in {1, ..., n}, the mean(p,q)
being “the strands starting at positions p and q cross at
ing of the crossing σi
position i”, see Figure 1.
Of course, when the colour set C is a singleton, we can forget about colours, and
+
the monoid Bn,C
is simply the n-strand monoid—which is known to be cancellative
since Garside [12]. By contrast, for #C > 2 and n > 3, the presentation of (2.1) is
not complemented (for some generators s, t, there is more than one relation of the
type s... = t... in the presentation), and no simple criterion seems to apply. Here
we shall prove:
+
admits left and right cancellation.
Proposition 2.2. The monoid Bn,C

The proof consists of applying the criterion of Proposition 1.14, namely consid(a)
ering all generators σi and all relations w=w′ of (2.1), and checking that, for every
(a)
reversing grid built from σi and w, there exists an equivalent reversing grid built

A CANCELLATIVITY CRITERION FOR PRESENTED MONOIDS

p

q

r

p

q

13

r

(p,q)
σi

(q,r)

σi+1
(p,r)

σi+1

(p,r)

∼

σi

(q,r)

(p,q)

σi

σi+1
(p,q)

the meaning “the
Figure 1. Colored braid relation: if we give σi
strands starting at positions p and q cross at position i”, that is, if we
take into account the names (origins) of the strand that cross, then
the relations of (2.1) appear naturally.
(a)

from σi and w′ , and vice versa. We shall see that there are only two critical cases,
with all other cases either reducing to them or being trivial.
(a)

Lemma 2.3. Property (♦) holds for σ1

(b) (c) (d)

(d) (c) (b)

and the relation σ2 σ3 σ2 = σ3 σ2 σ3 .
(a)

(b) (c) (d)

Proof. We look at all possible grids from (σ1 , σ2 σ3 σ2 ), and exhibit for each of
(a) (d) (c) (b)
them an equivalent grid from (σ1 , σ3 σ2 σ3 ), and conversely. First, we see using
(a) (b) (c) (d)
the definition that the valid grids from (σ1 , σ2 σ3 σ2 ) are the following grids,
where e and f are arbitrary elements of the color set C:
(b)

(c)

σ2

(d)

σ3

σ2

(f)

(e)

(e)

σ1
(2.2)

(c)

σ1

σ3

(a)

σ1

(a)
σ2
(e)

(b)

σ2

σ1

∗
(f)

(f)

(d)

σ2

σ1

(e)

σ2

(f)

(d) ε
ε ε σ1

(a)

σ3
ε

σ2

σ3

(c)

σ3

σ1

∗

σ2

(a)

(a)

σ3
(d)

σ1

A priori, one might use different colors f, f ′ in the squares marked ∗, but f 6= f ′
(f)
(f ′)
leads to a grid that cannot be completed, since there is no relation σ2 ... = σ2 ...
in (2.1). Now, consider the following valid grid:
(d)

(c)

σ3

(b)

σ2

σ3
(f)

(2.3)

(a)

(f)

(b)

σ1

σ1

σ3

(a)

σ1

(e)

σ1

(d)

σ3

σ2

(a)
σ2
(f)

σ2

(c)

σ1

(a)

σ3
(e)

σ3

(b)

σ2

(f) (e) (a)

The right edges of (2.2) and (2.3) both yield the word σ1 σ2 σ3 . For the bottom
edges, using ≡ for the congruence generated by the relations of (2.1), we find
(d) (f) (c) (e) (b)

(d) (f) (e) (c) (b)

(e) (f) (d) (c) (b)

σ3 σ2 σ1 σ3 σ2 ≡ σ3 σ2 σ3 σ1 σ2 ≡ σ2 σ3 σ2 σ1 σ2
(e) (f) (b) (c) (d)

(e) (b) (f) (c) (d)

≡ σ2 σ3 σ1 σ2 σ1 ≡ σ2 σ1 σ3 σ2 σ1 ,

14

PATRICK DEHORNOY

which shows that (2.2) and (2.3) are equivalent grids.
(a)
(d) (c) (b)
Conversely, starting from σ1 and σ3 , σ2 σ3 , the only possible reversing grids
have the form of (2.3) for some e and f in C, and then (2.2) provides the expected
equivalent grid.

(a)

Lemma 2.4. Property (♦) holds for σ2

(b) (c)

(c) (b)

and the relation σ1 σ3 = σ3 σ1 .
(a)

(b) (c)

Proof. As in Lemma 2.3, we look at all reversing grids from (σ2 , σ1 σ3 ), and
(a) (c) (b)
exhibit an equivalent grid from (σ2 , σ3 σ1 ), and conversely. The grids from
(a) (b) (c)
(σ2 , σ1 σ3 ) are the following grids, with d, e, f arbitrary in C:
(b)

(c)

σ1

σ3

(e)

σ2

(d)
σ2

(e)

σ2

(d)

(c)

σ3

(a)

(2.4)

σ3

σ2

(f)

(a)

(d)

σ1

(b)

σ1

σ1

(a)

σ1

(e)

σ2

(a)

σ2
(f)

σ3

(c)

σ2

σ1

On the other hand, the following grid is also valid:
(c)

(b)

σ3

σ1

(e)

σ2

(f)
σ2

(e)

σ2

(f)

(b)

σ1

(a)

(2.5)

σ1

σ2

(d)

(a)

(f)

σ3

(c)

σ3

σ3

(a)

σ3

(e)

σ2

(a)

σ2
(d)

σ1

(b)

σ2

σ3

The right edges of (2.4) and (2.5) correspond to equivalent words, since we have
(e) (d) (f) (a)

(e) (f) (d) (a)

σ2 σ1 σ3 σ2 ≡ σ2 σ3 σ1 σ2 .
Similarly, we find for the bottom edges
(f) (c) (e) (d) (b)

(f) (d) (e) (c) (b)

(d) (f) (e) (b) (c)

(d) (b) (e) (f) (c)

σ3 σ2 σ1 σ2 σ3 ≡ σ3 σ1 σ2 σ1 σ3 ≡ σ1 σ3 σ2 σ3 σ1 ≡ σ1 σ2 σ3 σ2 σ1 .
Hence (2.4) and (2.5) are equivalent grids.
(a) (c) (b)
Conversely, the possible reversing grids from (σ2 , σ3 , σ1 ) have the form of (2.5)
for some f , e, and d in C, and then (2.4) provides the expected equivalent grid. 
(a)

and all relations of (2.1).

Lemma 2.5. Property (♦) holds for all σi
(a)

Proof. First consider the case of σi

(b) (c) (d)

and a relation σj σk σj
(a)

(d) (c) (b)

= σk σj σk with,

(b) (c) (d)

say, k = j + 1. For i 6 j − 2, every grid from (σi , σj σk σj ) is a commutation
(a)

(d) (c) (b)

grid and then there exists an equivalent grid from (σi , σk σj σk ) as shown below:
(b)

σj
(2.6)

(a)

(c)

σk

(a)

σi

σi
(b)

σj

(c)

σk

(d)

(d)

σj

(a)

σi

(d)

σj

σk
(a)

σi

(a)

(c)

σj

(a)

σi

σi
(d)

σk

(c)

σj

(b)

σk

(a)

σi

(b)

σk

(a)

σi

A CANCELLATIVITY CRITERION FOR PRESENTED MONOIDS
(a)

15

(d) (c) (b)

The case when we start with a grid from (σi , σk σj σk ) is similar.
The case i = j − 1 corresponds to Lemma 2.3 for i = 1, and the general case is
similar, since the relations of (2.1) are invariant under shifting the indices.
(a) (b) (c) (d)
Next, assume i = j. Then a grid from (σi , σj σk σj ) exists only for a = b, and
then it is as in the left hand diagram below, in which case the right hand diagram
provides an equivalent grid for e = c:
(c)
(d)
(b)
σj
σk
σk
(b)
(d)
(c)
σj
σj
σk
(e)
σj
ε σ(b) ε
k
ε
(a)
(a)
σ
(2.7) σi
i
ε
ε
ε
(a)
(a)
σk
σk
ε
ε
(c)
(d)
σk
σj
ε
ε
(e)
(d)
σk
σj
(d) (c) (b)

(a)

In the other direction, the only possible grids from (σi , σk σj σk ) correspond to
the right hand diagram in (2.7) with e = c and a = b, in which case the left diagram
provides the required equivalent grid.
The case i = j + 1 = k is symmetric to i = j. Similarly, the case i = j + 2 = k + 1
is symmetric to i = j − 1. Finally, the cases i > k + 2 are symmetric to i 6 j − 2.
(c) (b)
(b) (c)
(a)
We now consider the case of σi and a relation σj σk = σk σj with, say,
k > j + 2. The case i 6 j − 2 is similar to that of (2.6), with commutation grids.
(a) (b) (c)
Assume i = j − 1. Then the grids from (σi , σj σk ) are as on the left diagram
below, with d arbitrary in C, and the right diagram then provides the expected
(a) (c) (b)
equivalent grid from (σi , σk σj ):
(b)
(c)
(b)
(c)
σj
σk
σ
σ
j

(2.8)

k

(d)
σi

(a)

σi

(c)

σk

(a)

(a)

σj
(d)

σj

(d)

(d)

σi

(a)
σi

σi

(a)
σi

(a)

σj

σj

(b)

(c)

(c)

σi

σk

σk

(a)

(d)

(b)

σj

σi

(c) (b)

In the other direction, the only grids from (σi , σk σj ) are those shown in the
right diagram of (2.8) with d arbitrary in C, and the left diagram then provides
the expected equivalent grid.
The case i = j is almost trivial: grids may exist only for a = b, and then they
take the form
(b)
(b)
(c)
(c)
σj
σj
σk
σk
(2.9)

(a)

σi

ε
ε

ε
(c)

(a)

(a)

σi

σi
(c)

ε

ε

σk
σk
Next, assume j + 1 6 i 6 k − 1. If k = j + 2 holds, typically i = 2, j = 1,
k = 3, we are, up to a shifting of the indices, in the situation of Lemma 2.4, and
so (♦) is guaranteed. Otherwise, either i is adjacent to exactly one of j or k, and
the situation is that of (2.8), or i is at distance at least 2 from both j and k, and
the situation is that of (2.7). Finally, the cases of i = k, i = k + 1, and i > k + 2
are symmetric to those of (2.9), (2.8), and (2.7), respectively. Thus, all cases have
been successfully treated.

We can now easily complete the proof of Proposition 2.2:

16

PATRICK DEHORNOY

Proof of Proposition 2.2. The presentation (2.1) is eligible for the criterion of Proposition 1.14. Indeed, it contains no ε-relation, and all relations are of the form w=w′
+
with w, w′ of the same length. Hence the monoid Bn,C
is right noetherian. By
Proposition 1.14 and Lemma 2.5, right reversing is complete for (2.1). Hence, as
the presentation contains no relation contradicting left cancellation, the monoid
admits left cancellation. Finally, the symmetry of the relations guarantees that the
monoid is isomorphic to the opposed monoid, and, therefore, right cancellativity
automatically follows from left cancellativity.

Inspecting the proofs above shows that, in the worst cases, the combinatorial
distance between the outputs of the old and the new grids is at most 5, so, according
to the terminology sketched in Remark 1.19, the defect of the presentation (2.1) is 5,
which could be used to obtain explicit upper bounds on the number or reversing
steps needed to possibly establish the equivalence of words.
As mentioned in Remark 1.15, our current approach says nothing about the
embeddability of the involved monoid in a group. So the obvious question after
Proposition 2.2 is
+
Question 2.6. Does the monoid Bn,C
embed in its enveloping group, that is, in
the group defined by the presentation (2.1)?

A classical sufficient condition is provided by Ore’s theorem [14] stating in the
current context that a cancellative monoid M in which any two elements admit
a common right multiple embeds in its enveloping group, which, in addition, is
then a group of right fractions for M . This applies for instance to the monoid Bn+ .
+
admits no common multiple: for a 6= b,
However, for #C > 2, the monoid Bn,C
(a)

(b)

the elements σ1 and σ1 admit no common right (or left) multiple, since there is
(a) (b)
no valid reversing grid from (σ1 , σ1 ). In [9], the embeddability criterion of Ore’s
theorem is extended to cancellative monoids with no nontrivial invertible elements
that satisfy the following “3-Ore condition”:
any three elements of M which pairwise admit a common right multiple
(2.10)
admit a common right multiple, and similarly for left multiples,
provided any two elements of M admit a left and a right gcd, i.e., greatest lower
+
bounds with respect to left and right division. For #C > 2, the monoid Bn,C
(a)

(a)

does not admit gcds: for instance, for a 6= b, the elements σ1 and σ2 left divide
(a) (a) (a)
(a) (b) (a)
(a)
(a)
both σ1 σ2 σ1 and σ1 σ2 σ1 , but no common multiple of σ1 and σ2 left divides
the above elements. This leads to two new questions:
+
satisfy the 3-Ore condition (2.10)?
Question 2.7. Does the monoid Bn,C

Question 2.8. Is the 3-Ore condition (2.10) sufficient for implying the embeddability of a monoid in its enveloping group in the case of a cancellative monoid that
need not admit gcds?
+
2.2. A variant. In [2], the authors consider a variant of the monoid Bn,C
with the
same generators but with a restricted list of relations:

Definition 2.9. For n > 1 and C a nonempty set, the monoid of restricted positive
C-colored braids is the monoid with presentation
+

(b) (a)
(a) (b)
for |i − j| > 2
σi σj = σj σi
(a)
+
e
.
(2.11) Bn,C := σi | i 6 n, a ∈ C (a) (a) (b)
(b) (a) (a)
for |i − j| = 1
σi σj σi = σj σi σj

A CANCELLATIVITY CRITERION FOR PRESENTED MONOIDS

17

All relations of (2.11) are relations of (2.1), but, in the “Yang-Baxter” relations,
+
the median color must be equal to one of the extremal colors. Thus the monoid Bn,C
e+ . The authors of [2] ask whether the monoid B
e+
is a quotient of the monoid B
n,C
n,C
is cancellative. Frustratingly, the criterion of Proposition 1.14 cannot be applied:
Fact 2.10. Right reversing is not complete for the presentation (2.11).
(a)

(b) (c) (c)

(c) (c) (b)

Proof. Property (♦) fails for σ1 and the relation σ2 σ3 σ2 = σ3 σ2 σ3 . Indeed,
we have the following valid grid
(c)

(c)

σ3

(b)

σ2

σ3
(a)

(2.12)

(a)

(a)

(b)

σ1

σ1

σ3

(a)

σ1

(b)

σ1

(c)

(a)

σ3

σ2

(a)
σ2
(c)

σ2

(a)

σ3
(b)

σ1

(b)

σ3
(a)

σ2

(b) (c) (c)

and there may exist no equivalent grid from (σ1 , σ2 σ3 σ2 ). Indeed, according to
what was seen in the proof of Lemma 2.3, the only possible form for such a grid
would be
(b)

(c)

σ2

(c)

σ3

σ2

(y)

(x)
σ1

(2.13)

(c)

(x)
σ1

σ3

(a)
σ1

(x)

σ2

(b)

σ1

(y)

(x)

σ2

(c) ε
ε ε σ1

(a)

σ3
ε

(c)

σ2

(c)

σ1

(y)

σ3
σ3

(y)

σ2
σ2

(a)
σ2

σ1

(a)

(a)

σ3
(c)

σ1

(a) (b) (a)

(y) (x) (a)

with x ∈ {a, b} and y ∈ {a, c} ∩{x, c}. The equivalence of σ1 σ2 σ3 and σ1 σ2 σ3
would require in particular x = b. But, on the other hand, the equivalence class
(c) (a) (c) (b) (b)
of the word σ3 σ2 σ1 σ3 σ2 on the bottom edge of (2.12) with respect to the
congruence generated by the relations of (2.11) consists of two words only, namely
(c) (a) (c) (b) (b)
(c) (a) (b) (c) (b)
(b)
σ3 σ2 σ1 σ3 σ2 and σ3 σ2 σ3 σ1 σ2 , none of which begins with σ2 . Hence no
(a) (b) (c) (c)
(σ1 , σ2 σ3 σ2 )-grid may be equivalent to (2.12).

e+ is not cancellative,
The above negative result does not say that the monoid B
n,C
it just says that the criterion of Proposition 1.14 fails to apply. The proof of
Fact 2.10 provides an explicit example of a valid relation that cannot be checked
using reversing, namely
(2.14)

(b) (c) (c) (a) (b) (a)

(a) (c) (a) (c) (b) (b)

σ2 σ3 σ2 σ1 σ2 σ3 ≡ σ1 σ3 σ2 σ1 σ3 σ2 ,
(c)

whose only proof requires introducing an intermediate word beginning with σ3 , for
(c) (b) (b) (a) (b) (a)
instance σ3 σ2 σ3 σ1 σ2 σ3 . In other words, every van Kampen diagram witnessing for (2.14) must contain a vertex from which three edges start. By adding (2.14)
as a new (redundant) relation in the presentation, we can make the above relation
eligible for factor reversing, but new obstructions are likely to appear, and it is not

18

PATRICK DEHORNOY

clear why the completion procedure thus sketched should come to an end. Thus,
the following question is left open:
e+ admit cancellation? Does it embed in
Question 2.11. [2] Does the monoid B
n,C
its enveloping group?
References

[1] S.I. Adyan, On the embeddability of monoids, Soviet. Math. Dokl. 1-4 (1960) 819–820.
[2] A. Berenstein, J. Greenberg, and J.R. Li, Monomial braidings, in preparation,
http://www.wisdom.weizmann.ac.il/∼jianrong/mon braid fin.pdf.
[3] J. Birman, Braids, Links, and Mapping Class Groups, Annals of Math. Studies 82 Princeton
Univ. Press (1975).
[4] A.H. Clifford & G.B. Preston, The algebraic Theory of Semigroups, vol. 1, Amer. Math. Soc.
Surveys 7, (1961).
[5] P. Dehornoy, Groups with a complemented presentation, J. Pure Appl. Algebra 116 (1997)
115–137.
[6] P. Dehornoy, On completeness of word reversing, Discrete Math. 225 (2000) 93–119.
[7] P. Dehornoy, Complete positive group presentations, J. Algebra 268 (2003) 156–197.
[8] P. Dehornoy, The subword reversing method, Internat. J. Algebra Comput. 21 (2011) 71–118.
[9] P. Dehornoy, Multifraction reduction I: The 3-Ore case and Artin-Tits groups of type FC, J.
Comb. Algebra 1 (2017) 185–228.
[10] P. Dehornoy, with I. Dynnikov, D. Rolfsen, B. Wiest, Ordering Braids, Mathematical Surveys
and Monographs vol. 148, Amer. Math. Soc. (2008).
[11] P. Dehornoy & B. Wiest, On word reversing in braid groups, Int. J. Algebra Comput. 16(5)
(2006) 931–947.
[12] F.A. Garside, The braid group and other groups, Quart. J. Math. Oxford 20-78 (1969) 235–
254.
[13] R.C. Lyndon & P.E. Schupp, Combinatorial Group Theory, Springer-Verlag; 1977, reprinted
in 2001.
[14] Ø. Ore, Linear equations in non-commutative fields, Ann. of Math. 34 (1933) 480–508.
[15] J.H. Remmers, On the geometry of semigroup presentations, Adv. Math. 36 (1980) 283–296.
Laboratoire de Mathématiques Nicolas Oresme, UMR 6139 CNRS, Université de Caen,
14032 Caen, France
E-mail address: patrick.dehornoy@unicaen.fr
URL: dehornoy.users.lmno.cnrs.fr

