arXiv:1606.08995v4 [] 31 Jan 2017

MULTIFRACTION REDUCTION II: CONJECTURES FOR ARTIN-TITS
GROUPS
PATRICK DEHORNOY

Abstract. Multifraction reduction is a new approach to the word problem for Artin-Tits
groups and, more generally, for the enveloping group of a monoid in which any two elements
admit a greatest common divisor. This approach is based on a rewrite system (“reduction”)
that extends free group reduction. In this paper, we show that assuming that reduction
satisfies a weak form of convergence called semi-convergence is sufficient for solving the word
problem for the enveloping group, and we connect semi-convergence with other conditions
involving reduction. We conjecture that these properties are valid for all Artin-Tits monoids,
and provide partial results and numerical evidence supporting such conjectures.

1. Introduction
Artin-Tits groups are those groups that admit a positive presentation with at most one
relation s... = t... for each pair of generators s, t and, in this case, the relation has the form
stst... = tsts..., both sides of the same length [4, 23]. It is still unknown whether the word
problem is decidable for all Artin–Tits groups as, at the moment, decidability was established
for particular families only: braid groups (E. Artin [3] in 1947), spherical type (P. Deligne [20]
and E. Brieskorn–K. Saito [5] in 1972), large type (K.I. Appel–P.E. Schupp [2] in 1983), trianglefree (S. Pride [29] in 1986), FC type (J. Altobelli [1] and A. Chermak [7] in 1998). Later on,
some of these groups were proved to be biautomatic or automatic [22, 6].
This paper, which follows [13] but is self-contained, continues the investigation of multifraction reduction, a new approach to the word problem for Artin-Tits groups and, more generally,
for the enveloping group U(M ) of a cancellative monoid M in which any two elements admit a
left and a right greatest common divisor (“gcd-monoid”). This approach is based on a certain
algebraic rewrite system, called reduction, which unifies and (properly) extends all previous
rewrite systems based on exploiting the Garside structure of Artin–Tits monoids [9, 30, 27].
It is proved in [13] that, if the monoid M satisfies various properties involving the divisibility
relations, all true in every Artin–Tits monoid, together with an additional assumption called
the 3-Ore condition, then reduction is convergent and every element of the enveloping group
of M admits a unique representation by an irreducible multifraction, directly extending the
classical result by Ø. Ore about representation by irreducible fractions.
In the current paper, we address the case of a general gcd-monoid, when the 3-Ore condition
is not assumed. In this case, reduction is not convergent, and there is no unique representation
of the elements of the group U(M ) by irreducible multifractions. However, we introduce a
new, weaker condition called semi-convergence, and prove that most of the applications of the
convergence of reduction can be derived from its semi-convergence, in particular a solution of
the word problem for U(M ) whenever convenient finiteness conditions are satisfied. This makes
the following conjecture crucial:
Conjecture A. Reduction is semi-convergent for every Artin-Tits monoid.
1991 Mathematics Subject Classification. 20F36, 20F10, 20M05, 68Q42, 18B40.
Key words and phrases. Artin-Tits monoid; Artin-Tits group; gcd-monoid; enveloping group; word problem; multifraction; reduction; semi-convergence; cross-confluence; tame reduction; van Kampen diagram;
embeddability.
1

2

PATRICK DEHORNOY

A proof of Conjecture A would imply the decidability of the word problem for every ArtinTits group. The reasons for believing in Conjecture A are multiple. One abstract reason is that
reduction is really specific and uses both the whole Garside structure of Artin–Tits monoids and,
for the finiteness of the set of basic elements, some highly nontrivial properties of the associated
Coxeter groups [15, 21]: this may be seen as more promising than a generic approach based
on, say, a “blind” Knuth–Bendix completion. Next, we state several related conjectures (“B”,
“C”, “Cunif ”), of which some partial cases are proven and which suggest the existence of a
rich rigid structure. Another reason is the existence of massive computer tests supporting all
the conjectures and, at the same time, efficiently discarding wrong variations and dead-ends.
Finally, the existence of a proof in the special case of FC type is a positive point. In the same
direction, a weak version of Conjecture A (sufficient for solving the word problem) was recently
established for all Artin–Tits groups of sufficiently large type [18]: although saying nothing
about A itself, this shows that reduction is relevant for a new family of Artin–Tits groups.
We present below a state-of-the-art description of the known results involving multifraction
reduction, and report about computer experiments supporting Conjecture A and its variants.
The paper is organized as follows. We gather in Section 2 the needed prerequisites about
multifractions, gcd-monoids, and reduction. Semi-convergence and Conjecture A are introduced
in Section 3, and their consequences are established. In Section 4, we analyze specific cases of
reduction, namely divisions and their extensions, tame reductions. This leads to a new property,
stated as Conjecture B, which is stronger than Conjecture A but easier to experimentally check
and maybe to establish. Then, we introduce in Section 5 cross-confluence, a new property
of reduction that involves both reduction and a symmetric counterpart of it. This leads to
Conjecture C and its uniform version Cunif , again stronger than Conjecture A but possibly
more accessible. In Section 6, we analyze the case of small depth multifractions. We prove in
particular that semi-convergence for multifractions of depth 2 is equivalent to M embedding
into its enveloping group, and semi-convergence for multifractions of depth 4 is equivalent to a
unique decomposition property for fractions in U(M ). Finally, we gather in Section 7 reports
about computer experiments and a few comments about further possible developments.
Acknowledgments. The author thanks Friedrich Wehrung for many discussions about the
content of this paper. In particular, the notion of a lcm-expansion mentioned in Sec. 7.1
appeared during our joint work of interval monoids [19]. The author also thanks both the
editor and the referee, whose many suggestions certainly improved the exposition significantly.
2. Multifraction reduction
In this introductory section, we recall the notions of a multifraction and of a gcd-monoid, as
well as the definition of multifraction reduction [13].
2.1. Multifractions. If M is a monoid, we denote by U(M ) and ι the enveloping group of M
and the canonical morphism from M to U(M ), characterized by the universal property that
every morphism from M to a group factors through ι. By definition, every element g of U(M )
can be expressed as
(2.1)

ι(a1 )ι(a2 )−1 ι(a3 )ι(a4 )−1 ···

or

ι(a1 )−1 ι(a2 )ι(a3 )−1 ι(a4 )···,

with a1 , ..., an in M . We shall investigate U(M ) using such expressions. In [13], without loss of
generality, we only considered, expressions (2.1) where the first term ι(a1 ) is positive (possibly
trivial, that is, equal to 1). Here, in particular in view of Section 5, we skip that condition, and
allow for both signs in the first entry.
Definition 2.2. Let M be a monoid. Let M be a disjoint copy of M ; call the elements of M
(resp., M ) positive (resp., negative). For n > 1, a positive (resp., negative) n-multifraction
on M is a finite sequence (a1 , ..., an ) with entries in M ∪ M , alternating signs, and a1 in M

MULTIFRACTION REDUCTION II

3

(resp., M ). The set of all multifractions (resp., all positive multifractions) completed with the
empty sequence ∅ is denoted by FM± (resp., FM ). A multiplication is defined by


for an and b1 in M ,
(a1 , ..., an−1 , an b1 , b2 , ..., bp )
(a1 , ..., an ) · (b1 , ..., bp ) = (a1 , ..., an−1 , b1 an , b2 , ..., bp )
for an and b1 in M ,


(a1 , ..., an , b1 , ..., bp )
otherwise,

extended with a · ∅ = ∅ · a = a for every a.

We use a, b, ... as generic symbols for multifractions, and ai for the ith entry of a counted
from 1. For a in FM± , the length of a (number of entries) is called its depth, written kak. We
identify an element a of M with the depth one positive multifraction (a). Multfractions will
play the role of iterated fractions, and the following convention is then convenient:
Notation 2.3. For a1 , ..., an in M , we put
(2.4)

a1 /···/an := (a1 , a2 , a3 , a4 , ...)

and /a1 /···/an := (a1 , a2 , a3 , a4 , ...).

We say that i is positive (resp., negative) in a if ai (resp., ai ) occurs in the expansion of a.
With this convention, we recover the notation of [13], where only positive multifractions
are considered and M remains hidden. Multifractions are adequately illustrated by associating
with every element a of M an arrow labeled a, concatenating arrows to represent the product
in M , and associating with every multifraction the path made of (the arrows of) the successive
entries with alternating orientations. The rules for the multiplication of a and b can be read in
the following diagrams:
an
b1
an b 1
- n positive in a, 1 positive in b:
·
=
an
b1
an b 1
- n positive in a, 1 negative in b:
·
=
an
b1
an b 1
- n negative in a, 1 positive in b:
·
=
a
b
b 1 an
n
1
- n negative in a, 1 negative in b:
·
=
Proposition 2.5. (i) The set FM± equipped with · and ∅ is a monoid generated by M ∪ M ,
and FM is the submonoid of FM± generated by M ∪ {1/a | a ∈ M }. The family of depth one
multifractions is a submonoid isomorphic to M .
(ii) Let ≃± be the congruence on FM± generated by (1, ∅) and the pairs (a/a, ∅) and (/a/a, ∅)
with a in M . For a in FM± , let ι(a) be the ≃± -class of a. Then the group U(M ) is (isomorphic
to) FM± /≃± and, for all a1 , ..., an in M , we have
(2.6)

ι(a1 /···/an ) = ι(a1 )ι(a2 )−1 ι(a3 )···,

ι(/a1 /···/an ) = ι(a1 )−1 ι(a2 )ι(a3 )−1 ···.

(iii) The restriction of ≃± to FM is the congruence ≃ generated by (1, ∅) and the pairs
(a/a, ∅) and (1/a/a, ∅) with a in M . The group U(M ) is also isomorphic to FM /≃. The
translation a 7→ 1 · a maps FM± onto FM and, for all a, b in FM± , the relation a ≃± b is equivalent
to 1 · a ≃ 1 · b.
Proof. The argument is similar to the proof of [13, Proposition 2.4], and we only point the
differences due to using signed multifractions. For (i), associativity is checked directly, and the
generating subsets for FM± and FM follow from the equalities
a1 /···/an = a1 · a2 · a3 · a4 · ··· = a1 · 1/a2 · a3 · 1/a4 · ··· :

(2.7)
±

both hold in FM , and the second only involves positive multifractions.
For (ii) and (iii), for every a in FM± , the definition of ≃± implies ι(a) = ι(a)−1 and, writing
+
ι (a) for the ≃-class of a, that of ≃ implies ι+ (1/a) = ι+ (a)−1 . Hence both FM± /≃± and FM /≃
are groups generated by M . One easily checks that the latter groups satisfy the universal
property defining U(M ), and are therefore isomorphic to U(M ). Then (2.6) directly follows
from (2.7).
Next, for every a in FM± , the product 1 · a belongs to FM . Then, for a, b in FM± , write a ≈ b
for 1 · a ≃ 1 · b. By considering all sign combinations and using relations like 1/ab ≃ 1/b · 1/a,

4

PATRICK DEHORNOY

one checks that ≈ is a congruence on FM± , and it contains the pairs (1, ∅), (a/a, ∅), and
(/a/a, ∅) that generate ≃± , as one finds for instance 1 · /a/a = 1/a/a ≃ ∅ = 1 · ∅. Hence ≈
includes ≃± . In the other direction, ≃± contains pairs that generate ≃ and, being compatible
with multiplication in FM± , it is in particular compatible with multiplication in FM . So ≃ is
included in ≃± , and a ≃± b implies 1 · a ≃ 1 · b since 1 is invertible mod ≃± . Hence, ≃± is
included in ≈ and, finally, ≃± and ≈ coincide, which means that, for all a, b in FM± , we have
(2.8)

a ≃± b

⇐⇒

1 · a ≃ 1 · b.

For a positive, we have 1 · a = a, so (2.8) implies in particular that ≃ is the restriction of ≃±
to FM , and the rest follows easily.

Hereafter, we identify U(M ) with FM± /≃± and FM /≃. This representation is redundant in
that, for every a in M , the inverse ι(a)−1 of ι(a) is represented both by the depth 1 negative
multifraction /a and the depth 2 positive multifraction 1/a.
We conclude this introduction with some terminology that will be used frequently:
Definition 2.9. A multifraction a is called unital if a ≃± 1 holds, i.e., if a represents 1 in the
group U(M ). It is called trivial if all entries are equal to 1 or 1. For n > 0, we write 1n for
1/···/1, n terms; for n < 0, we write 1n for /1/1/···/1, |n| terms; in practice, we shall often
omit the index and write 1 for a trivial multifraction.
2.2. Gcd-monoids. The reduction process we investigate requires that the ground monoid is
a gcd-monoid. We recall the basic definitions, referring to [13] (and [16]) for more details.
Let M be a monoid. For a, b in M , we say that a left divides b or, equivalently, that b is
a right multiple of a, written a 6 b, if ax = b holds for some x in M . If M is a cancellative
monoid and 1 is the only invertible element in M , the left divisibility relation is a partial order
on M . In this case, when they exist, the greatest common 6-lower bound of two elements a, b
is called their left gcd, denoted by a ∧ b, and their least common 6-upper bound is called their
right lcm, denoted by a ∨ b.
Symmetrically, we say that a right divides b or, equivalently, that b is a left multiple of a,
e b, if xa = b holds for some x. Under the same hypotheses, 6
e is a partial order
written a 6
e and ∨
e.
on M , with the derived right gcd and left lcm written ∧

Definition 2.10. We say that M is a gcd-monoid if M is a cancellative monoid, 1 is the only
invertible element in M , and any two elements of M admit a left gcd and a right gcd.

Typical examples of gcd-monoids are Artin-Tits monoids. Many more examples are known.
In particular, every Garside or preGarside monoid [11, 16, 25] is a gcd-monoid.
Standard arguments [13, Lemma 2.15] show that a gcd-monoid admits conditional right and
left lcms: it need not be true that any two elements admit a right lcm, but any two elements
that admit a common right multiple admit a right lcm, and similarly on the left.
The gcd and lcm operations of a gcd-monoid are connected in several ways with the product.
We refer to [16, section II.2] for the (easy) proof of the rule for an iterated lcm:
Lemma 2.11. If M is a gcd-monoid and a, b, c belong to M , then a ∨ bc exists if and only if
a ∨ b and a′ ∨ c do, where a′ is defined by a ∨ b = ba′ , and then we have
(2.12)

a ∨ bc = a · b′ c′ = bc · a′′ .

with a ∨ b = ba′ = ab′ and a′ ∨ c = a′ c′ = ca′′ .
This implies in particular that a 6 bc holds if and only if a ∨ b exists and a′ 6 c holds, with a′
defined by a ∨ b = ba′ .
Lemma 2.13. If M is a gcd-monoid and a, b, a′ , b′ , c belong to M and satisfy ab′ = ba′ , then
a ∧ b = a′ ∧ c = 1 implies a ∧ bc = 1.
Proof. Assume x 6 a and x 6 bc. By Lemma 2.11, b ∨ x must exist and, writing b ∨ x = bx′ , we
must have x′ 6 c. On the other hand, x 6 a implies x 6 ab′ = ba′ . So ba′ is a common right

MULTIFRACTION REDUCTION II

5

multiple of b and x, hence it is a right multiple of their right lcm bx′ . As M is left cancellative,
bx′ 6 ba′ implies x′ 6 a′ . Hence x′ left divides both a′ and c, and a′ ∧ c = 1 implies x′ = 1,
whence x 6 b. Then x left divides both a and b, and a∧b = 1 implies x = 1, hence a∧bc = 1. 
We shall also need the notion of a noetherian monoid. If M is a gcd-monoid, we use < for
the proper version of left divisibility: a < b holds if we have b = ax for some non-invertible x,
e vs. 6.
e
i.e., for x 6= 1, and similarly for <

e are well-founded,
Definition 2.14. A monoid M is called noetherian if the relations < and <
e
i.e., every nonempty subset of M has a <-minimal element and a <-minimal
element.

Note that a monoid hS | Ri+ is noetherian whenever each relation in R is homogeneous, i.e.,
it has the form u = v with u, v of the same length: indeed, a < b implies that any word in S
representing a is shorter than any word representing b, and an infinite <-descending sequence
cannot exist. Artin-Tits monoids are typical examples.

2.3. Reduction of multifractions. Introduced in [13], our tool for investigating the congruence ≃± on FM± is reduction, a family of partial depth-preserving transformations that, when
defined, map a multifraction to a ≃± -equivalent multifraction. These transformations are written as an action on the right: when defined, a • R is the result of applying R to a.
Definition 2.15. If M is a gcd-monoid and a, b lie in FM± , then, for i > 1 and x in M , we
declare that b = a • Ri,x holds if we have kbk = kak, bk = ak for k 6= i − 1, i, i + 1, and there
exists x′ (necessarily unique) satisfying
for
for
for
for

i=1
i=1
i>2
i>2

positive in a:
negative in a:
positive in a:
negative in a:

bi−1
bi−1

b i x = ai ,
xbi = ai ,
e ai ,
= x′ ai−1 , bi x = x′ ai = x ∨
= ai−1 x′ , xbi = ai x′ = x ∨ ai ,

bi+1 x = ai+1 ,
xbi+1 = ai+1 ,
bi+1 x = ai+1 ,
xbi+1 = ai+1 .

We write a ⇒ b if a • Ri,x holds for some i and some x 6= 1, and use ⇒∗ for the reflexive–
±
transitive closure of ⇒. The rewrite system RM
so obtained on FM± is called reduction, and
its restriction to FM (positive multifractions) is denoted by RM . A multifraction a is called
R-reducible if a ⇒ b holds for at least one b, and R-irreducible otherwise.
The system RM is the one investigated in [13], where only positive multifractions are consid±
ered: the only difference between [13, Def. 3.4] and Def. 2.15 is the adjunction in RM
of a rule for
the reduction at level 1 of a negative multifraction. As Ri,x preserves the sign of multifractions,
no specific notation is needed for the restriction of Ri,x to positive multifractions.
±
The reduction systems RM and RM
extend free reduction (deletion of factors x−1 x or xx−1 ):
applying Ri,x to a consists in removing x from ai+1 and pushing it through ai using an lcm
operation, see Figure 1. A multifraction a is eligible for R1,x if and only if x divides both a1
and a2 , on the side coherent with their signs, and, eligible for Ri,x with i > 2 if and only if x
divides ai+1 and admits a common multiple with ai , on the due side again.
ai

ai−1
...

x′
bi−1

⇐
bi

...

x
bi+1

ai

ai−1

ai+1

x′
bi−1

⇐
bi

ai+1
...

x
bi+1

Figure 1. The reduction rule Ri,x : starting from a (grey), we extract x from ai+1 ,
push it through ai by taking the lcm of x and ai (indicated by the small round arc),
and incorporate the remainder x′ in ai−1 to obtain b = a • Ri,x (colored). The left
hand side diagram corresponds to the case when i is negative in a, i.e., ai is crossed
negatively, the right hand one to the case when i is positive in a, i.e., ai is crossed
positively, with opposite orientations of the arrows.

6

PATRICK DEHORNOY

e 2 , here written
Example 2.16. Let M be the Artin-Tits monoid of type A
ha, b, c | aba = bab, bcb = cbc, cac = acai+ ,

and let a := 1/c/aba. Then a is eligible for R2,a and R2,b , since a and b left divide aba and admit
a common right multiple with c. We find a • R2,a = ac/ca/ba and a • R2,b = bc/cb/ab. The
latter are eligible for no reduction R1,x , since ac and ca (resp., bc and cb) admit no nontrivial
common right divisor, and for no reduction R2,x , since the only nontrivial left divisors of ba
(resp., ab) are b and ba (resp., a and ab), which admit no common right multiple with ca (resp.,
ac). Hence these multifractions are R-irreducible.
We now state the basic properties of reduction needed below. They directly extend those
established for positive multifractions in [13]. Verifying them in the general case is easy.
Lemma 2.17. Assume that M be a gcd-monoid.
(i) The relation ⇒∗ is included in ≃± , i.e., a ⇒∗ b implies a ≃± b.
(ii) The relation ⇒∗ is compatible with the multiplication of FM± .
(iii) For all a, b and p, q, the relation a ⇒∗ b is equivalent to 1p · a · 1q ⇒∗ 1p · b · 1q .
Proof. (i) It directly follows from the definition (and from Fig. 1) that b = a • Ri,x implies
ι(ai−1 )ι(ai )−1 ι(ai+1 ) = ι(bi−1 )ι(bi )−1 ι(bi+1 )
(resp., ι(ai−1 )−1 ι(ai )ι(ai+1 )−1 = ι(bi−1 )−1 ι(bi )ι(bi+1 )−1 ) for i negative (resp., positive) in a.
(ii) Assume b = a • Ri,x , and let c be an r-multifraction. If the signs of r in c and 1 in a are
different, then c · a is the concatenation of c and a, similarly c · b is the concatenation of c and b,
and c · b = (c · a) • Ri+r,x trivially holds.
If r is positive in c and 1 is positive in a, we have c · a = c1 /···/cr−1 /cr a1 /a2 /··· and
c · b = c1 /···/cr−1 /cr b1 /b2 /···, and we obtain c · b = (c · a) • Ri+r−1,x : the point is that, if x
both right divides a1 and a2 , it a fortiori right divides cr a1 and a2 .
Finally, assume that r negative in c and 1 is negative in a. Then we find c·a = c1 /···/a1 cr /a2 /···
and c · b = c1 /···/b1 cr /b2 /···: the argument is the same as above, mutatis mutandis: the assumption that a • R1,x is defined means that x both left divides a1 and a2 , which implies that it a
fortiori left divides a1 cr and a2 . Hence (c·a)•Ri+r−1,x is defined and we find c·b = (c·a)•Ri+r−1,x
again. This completes compatibility with left multiplication.
The compatibility on the right is similar: adding extra entries cannot destroy the eligibility
for reduction. Let n = kak. Everything is trivial for i < n − 1, so we assume i = n − 1. If the
signs of n in a and of 1 in c are different, the multiplication is a concatenation, and we obtain
b · c = (a · c) • Rn−1,x trivially. If n is positive in a and 1 is positive in c, the argument is the
same as for Rn−1,x . Finally, assume that n is negative in a and 1 is negative in c. Then we
find a · c = a1 /···/an−1 /c1 an /c2 /··· and b · c = b1 /···/bn−1 /c1 bn /c2 /···. The assumption that
e an−1 exists and x right divides an , which implies that it a
a • Rn−1,x is defined means that x ∨
fortiori right divides c1 an . Hence (a · c) • Rn−1,x is defined, yielding b · c = (a · c) • Rn−1,x again.
Thus reduction is compatible with multiplication on the right.
(iii) That a ⇒ b implies 1p · a · 1q ⇒ 1p · b · 1q follows from (ii) directly. Conversely, assume
1p · b · 1q = (1p · a • 1q ) • Ri,x with x 6= 1. Let n = kak = kbk, and assume that the entries of a
occur in 1p · b · 1q from r + 1 to r + n (with r = p or r = p − 1 according to the sign of p in 1p
and that of 1 in a). Then we necessarily have r + 1 6 i < r + n. Indeed, i < r and i > r + n
are impossible, since the (i + 1)st entry of 1p · a · 1q is trivial. Moreover, in the case i = r + 1,
the element x necessarily divides a1 , since, otherwise, the rth entry of 1p · b · 1q could not be
trivial. Hence, a • Ri,x is defined, and it must be equal to b.

Finally, we have a simple sufficient condition for termination.
±
Lemma 2.18. [13, Proposition 3.13] If M is a noetherian gcd-monoid, then RM
is terminating:
every sequence of reductions leads in finitely many steps to an R-irreducible multifraction.

MULTIFRACTION REDUCTION II

7

We skip the proof, which is exactly the same in the signed case as in the positive case, and
consists in observing that a ⇒ b forces b to be strictly smaller than a for some antilexicographical
ordering on FM± (comparing multifractions starting from the highest entry).
±
2.4. The convergent case. The rewrite system RM
(as any rewrite system) is called convergent if every element, here every multifraction a, admits a unique R-irreducible reduct, usually
denoted by red(a). The main technical result of [13] is

Proposition 2.19. If M is a noetherian gcd-monoid satisfying the 3-Ore condition:
If three elements of M pairwise admit a common right (resp. left) multiple,
(2.20)
then they admit a common right (resp. left) multiple,
±
then RM
is convergent.

When a monoid M is eligible for Proposition 2.19, one easily deduces that two multifractions a, b represent the same element of U(M ) if and only if red(a) · 1p = red(b) · 1q holds
for some p, q and, from there, that the monoid M embeds in its enveloping group U(M ) and
b ± is
b
every element of U(M ) is represented by a unique R-irreducible
multifraction, where R
M
±
obtained from RM by adding a rule that removes trivial final entries. It is also proved in [13]
that, under mild additional finiteness assumptions on M (see Section 3 below), the relation ⇒∗
on M is decidable and, from there, so is the word problem for U(M ) when the 3-Ore condition
is satisfied.
The above results are relevant for a number of gcd-monoids. We recall that an Artin-Tits
monoid M = hS | Ri+ is said to be of spherical type if the Coxeter group obtained by adding
to (S, R) the relation s2 = 1 for each s in S is finite [5]. And M is said to be of type FC if,
for every subfamily S ′ of S such that, for all s, t in S ′ , there is a relation s... = t... in R, the
submonoid of M generated by S ′ is spherical [1, 24].
Proposition 2.21. [13, Proposition 6.5] An Artin-Tits monoid satisfies the 3-Ore condition if
and only if it is of type FC.
However, a number of Artin-Tits monoids fail to be of type FC and therefore are not eligible
e 2 considered in Example 2.16. So we are
for Proposition 2.19, typically the monoid of type A
left with the question of either weakening the assumptions for Proposition 2.19, or using a
conclusion weaker than convergence.
3. Semi-convergence
After showing in Subsection 3.1 that the 3-Ore assumption cannot be weakened when proving
±
±
the convergence of RM
, we introduce in Subsection 3.2 a new property of RM
called semiconvergence, which, as the name suggests, is weaker than convergence. We conjecture that,
±
for every Artin-Tits monoid, the system RM
is semi-convergent (“Conjecture A”). We prove
±
in Subsection 3.3 that most of the consequences known to follow from the convergence of RM
follow from its semi-convergence, in particular in terms of controlling the group U(M ) from
inside the monoid M and solving its word problem. Finally, we describe in Subsection 3.4
several variants of semi-convergence.
3.1. The strength of the 3-Ore condition. A first attempt for improving Proposition 2.19
±
could be to establish the convergence of RM
from an assumption weaker than the 3-Ore condition. This approach fails, as the latter turns out to be not only sufficient, but also necessary.
Hereafter we say that a monoid M satifies the right (resp., left) 3-Ore condition when (2.20) is
valid for right (resp., left) multiples. First, we recall
Lemma 3.1. [13, Lemma 2.12] If M is a gcd-monoid, and a, b, c, d are elements of M satisfying
e d = 1.
ad = bc, then ad is the right lcm of a and b if and only if c and d satisfy c ∧

Proposition 3.2. Let M be a gcd-monoid.
(i) If RM is convergent, then M satisfies the right 3-Ore condition.
±
(ii) If RM
is convergent, then M satisfies the 3-Ore condition.

8

PATRICK DEHORNOY

Proof. (i) Assume that x, y, z belong to M and pairwise admit common right multiples, hence
right lcms. Write
x ∨ y = xy ′ = yx′ ,

y ∨ z = yz ′ = zy ′′ ,

x ∨ z = xz ′′ = zx′′ .

Let a := 1/x/y ∨ z. As in Example 2.16, we find
b = a • R2,y = y ′ /x′ /z ′

and c = a • R2,z = z ′′ /x′′ /y ′′ .

The assumption that RM is convergent implies that b and c both reduce to d := red(a). By
construction, d is of depth 3, and d3 must be a common right divisor of b3 and c3 , which are z ′
e y ′′ = 1, whence d3 = 1. Therefore, there exist d1 and d2
and y ′′ . Now, Lemma 3.1 implies z ′ ∧
∗
in M satisfying 1/x/y ∨ z ⇒ d1 /d2 /1. By Lemma 2.17, we deduce 1/x/y ∨ z ≃± d1 /d2 /1,
hence, by (2.6), x−1 (y ∨ z) = d1 d−1
in U(M ). This implies xd1 = (y ∨ z)d2 in U(M ), hence
2
in M , since the assumption that RM is convergent implies that M embeds in U(M ). It follows
that x and y ∨ z admit a common right multiple, hence that x, y, and z admit a common right
multiple. Hence M satisfies the right 3-Ore condition.
(ii) The argument is symmetric, with negative multifractions. Assume that x, y, z belong
to M and pairwise admit common left multiples, hence left lcms. Write
e y = y ′ x = x′ y,
x∨

e z = z ′ y = y ′′ z,
y∨

Let a := /1/x/y ∨ z, in FM± \ FM . Then we have
b = a • R2,y = /y ′ /x′ /z ′

e z = z ′′ x = x′′ z.
x∨

and c = a • R2,z = /z ′′ /x′′ /y ′′ .

±
The assumption that RM
is convergent implies that b and c admit a common R-reduct, say d.
By construction, d is of depth 3, and d3 must be a common left divisor of b3 and c3 , which are
z ′ and y ′′ . By the symmetric counterpart of Lemma 3.1, we have z ′ ∨ y ′′ = 1, whence d3 = 1.
e ∗ /d1 /d2 /1. By Lemma 2.17, we deduce
Therefore, there exist d1 and d2 in M satisfying a ⇒
±
−1
e z ≃ /d1 /d2 /1, hence, by (2.6), x(y ∨
e z) = d−1
e
/1/x/y ∨
1 d2 in U(M ), whence d1 x = d2 (y ∨ z)
e z admit a common left multiple, hence that
in U(M ), hence in M . This shows that x and y ∨
x, y, and z admit a common left multiple. Hence M satisfies the left 3-Ore condition.


Note that the argument for (i) cannot be used for (ii), because one should start with a :=
e z and then we know nothing about the first entry(ies) of red(a).
1/1/x/y ∨
In principle, the right 3-Ore condition is slightly weaker than the full 3-Ore condition, and
±
the convergence of RM might be weaker than that of RM
. However, when M is an Artin-Tits
monoid, all the above conditions are equivalent to M being of type FC and, therefore, none is
weaker. So it seems hopeless to improve Proposition 2.19.

3.2. Semi-convergence. We are thus led to explore the other way, namely obtaining useful
±
information about U(M ) from a property weaker than the convergence of RM or RM
. This is
the approach we develop in the rest of this paper.
When the system RM is not convergent, a ≃-class may contain several R-irreducible multifractions, and there is no distinguished one: in Example 2.16, the automorphism that exchanges a and b exchanges the two R-irreducible reducts of a, making them indiscernible.
However, a direct consequence of convergence is
±
Lemma 3.3. If M is a gcd-monoid and RM
is convergent, then, for every a in FM± ,

(3.4)

If a is unital, then a ⇒∗ 1 holds.

±
Indeed, if RM
is convergent, a ≃± 1 implies (and, in fact, is equivalent to) red(a) = red(1),
hence red(a) = 1, since 1 is R-irreducible. Note that, by Lemma 2.17(i), the converse implication of (3.4) is always true: a ⇒∗ 1 implies that a and 1 represent the same element of U(M ),
hence that a represents 1.
±
When RM
is not convergent, (3.4) still makes sense, and it is a priori a (much) weaker
condition than convergence. This is the condition we shall investigate below:

MULTIFRACTION REDUCTION II

9

±
Definition 3.5. If M is a gcd-monoid, we say that RM
(resp., RM ) is semi-convergent if (3.4)
±
holds for every a in FM (resp., in FM ).
±
Thus Lemma 3.3 states that RM
is semi-convergent whenever it is convergent. By Propo±
sition 2.21, RM and RM are semi-convergent for every Artin-Tits monoid M of type FC. But,
as can be expected, semi-convergence is strictly weaker than convergence. We refer to [19] for
±
the construction of monoids for which RM
is semi-convergent but not convergent.
The main conjecture we propose is:

Conjecture A. For every Artin-Tits monoid M , the system RM is semi-convergent.
We shall report in Section 7 about experimental data supporting Conjecture A. For the
moment, we just mention one example illustrating its predictions.
e 2 . We saw in Example 2.16 that
Example 3.6. Let M be the Artin-Tits monoid of type A
±
RM
is not convergent: a = 1/c/aba admits the two distinct irreducible reducts ac/ca/ba and
bc/cb/ab. When we multiply the former by the inverse of the latter (see Subsection 3.3 below),
we obtain the 6-multifraction b = ac/ca/ba/ab/cb/bc which, by construction, is unital. Then
Conjecture A predicts that b must reduce to 1. This is indeed the case: we find
b • R3,ab R4,cb R5,bc R1,ac R2,cbc R3,bc R1,bc = 1
(as well as b • R5,bc R3,ac R1,ac R3,b R4,c R2,c = 1: the reduction sequence is not unique).
More generally, we can observe that, for every gcd-monoid M , if a′ and a′′ are two reducts of
an n-multifraction a, then the 2n-multifraction b obtained by concatenating a′ and the inverse
of a′′ is always reducible whenever a′′ is nontrivial: by construction, we have bn = a′n and
bn+1 = a′′n . An obvious induction shows that a ⇒∗ a′ implies that a′n divides an (on the left or
on the right, according to the sign of n in a) and, similarly, a′′n divides an . Hence bn and bn+1
admit a common multiple and, therefore, b is eligible for some reduction Rn,x with x 6= 1
whenever bn+1 , i.e., a′′n , is not 1. Finally, if a′′n = 1 holds, then b is eligible for R2n−m,a′′m , where
m is the largest index such that a′′m is nontrivial.
3.3. Applications of semi-convergence. Most of the consequences of convergence already
follow from semi-convergence—whence the interest of Conjecture A. We successively consider
the possibility of controlling the congruence ≃± , the decidability of the word problem, and what
is called Property H.
Controlling ≃± . In order to investigate ≃± without convergence, we introduce a new operation
on multifractions to represent inverses.
e = ∅, and, for every n-multifraction a,
Notation 3.7. We put ∅
(
/an /···/a1 if n is positive in a,
(3.8)
e
a :=
an /···/a1
if n is negative in a.

Lemma 3.9. (i) For all multifractions a, b, we have ag
· b = eb · e
a.
a) = ι(1 · e
a) = ι(a)−1 .
(ii) For every multifraction a, we have ι(e

Proof. (i) If a written as a sequence in M ∪ M is (x1 , ..., xn ), then e
a is (xn , ..., x1 ) (where we
· b = eb · e
a directly follows from the definition of the product.
put a = a for a in M ), and then ag
Point (ii) comes from (2.6).


Lemma 3.9(ii) says that, if a represents an element g of U(M ), then both e
a and 1 · e
a represent g −1 . By definition, ke
ak = kak always holds, and the operation e on FM± is involutive.
a is posHowever, this operation does not restrict to FM : if a is a positive multifraction, then e
itive if and only if kak is even. In order to represent inverses inside FM , one can compose e
with a left translation by 1, thus representing the inverse of a by 1 · e
a. The inconvenience is
that involutivity is lost: for kak odd and b = 1 · e
a, we find 1 · eb = 1 · a 6= a.

10

PATRICK DEHORNOY

Lemma 3.10. If M is a gcd-monoid and RM is semi-convergent, then a ≃± b is equivalent
to 1 · a · eb ⇒∗ 1 for all a, b in FM± .

Proof. As we have 1 ≃± ∅ and b · eb ≃± ∅ by Lemma 3.9, a ≃± b is equivalent to 1 · a · eb ≃± ∅,
hence, by (2.6), to 1 · a · eb being unital, i.e., to ι(1 · a · eb) = 1. By construction, 1 · a · eb lies in FM .
So, if RM is semi-convergent, ι(1 · a · eb) = 1 is equivalent to 1 · a · eb ⇒∗ 1.

As a direct application, we obtain

Proposition 3.11. If M is a gcd-monoid and RM is semi-convergent, then M embeds in its
enveloping group U(M ).
Proof. Assume a, b ∈ M and ι(a) = ι(b), i.e., a ≃± b. By Lemma 3.10, we must have a · eb ⇒∗ 1,
which is a/b ⇒∗ 1/1. By definition of reduction, this means that there exists x in M satisfying
a/b • R1,x = 1/1. This implies a = b ( = x ).

The word problem for U(M ). If S is any set, we denote by S ∗ the free monoid of all words in S,
using ε for the empty word. For representing group elements, we consider words in S ∪ S, where
S is a disjoint copy of S consisting of one letter s for each letter s of S, due to represent s−1 . If
w is a word in S ∪ S, we denote by w the signed word obtained from w by exchanging s and s
and reversing the order of letters. If M is a monoid, S is included in M , and w is a word in S,
we denote by [w]+ the evaluation of w in M . We extend this notation to words in S ∪ S by
defining [w]+ to be the multifraction [w1 ]+ /···/[wn ]+ , where (w1 , ..., wn ) is the unique sequence
of words in S such that w can be decomposed as w1 w2 w3 w4 ··· with wi 6= ε for 1 < i 6 n.
Lemma 3.12. [13, Lemma 2.5] For every monoid M , every generating family S of M , and
every word w in S ∪ S, the following are equivalent:
(i) The word w represents 1 in U(M );
(ii) The multifraction [w]+ satisfies [w]+ ≃± 1 in FM± .
Thus solving the word problem for the group U(M ) with respect to the generating set S
amounts to deciding the relation [w]+ ≃± 1, which takes place in FM± , hence essentially inside M ,
as opposed to U(M ).
A few more definitions are needed. First, a gcd-monoid M is called strongly noetherian if
there exists a map λ : M → N satisfying, for all a, b in M ,
(3.13)

λ(ab) > λ(a) + λ(b),

and λ(a) > 0 for a 6= 1.

This condition is stronger than noetherianity, but it still follows from the existence of a presentation by homogeneous relations (same length on both sides): in this case, the word length
induces a map λ as in (3.13). So every Artin-Tits monoid is strongly noetherian.
Next, we need the notion of a basic element. Noetherianity implies the existence of atoms,
namely elements that cannot be expressed as the product of two non-invertible elements. One
shows [16, Corollary II.2.59] that, if M is a noetherian gcd-monoid, then a subfamily S of M
generates M if and only if it contains all atoms of M .
Definition 3.14. [11] If M is a noetherian gcd-monoid, an element a of M is called right basic
if it belongs to the smallest family X that contains the atoms of M and is such that, if a, b
belong to X and a ∨ b exists, then the element a′ defined by a ∨ b = ba′ still belongs to X.
Left-basic elements are defined symmetrically. We say that a is basic if it is right or left basic.
Note that, in the above definition, nothing is required when a ∨ b does not exist. The key
technical result is as follows:
Lemma 3.15. [13, Prop 3.27] If M is a strongly noetherian gcd-monoid with finitely many
basic elements and atom set S, then the relation [w]+ ⇒∗ 1 on (S ∪ S)∗ is decidable.
This result is not trivial, because deciding whether a multifraction is eligible for some reduction requires to decide whether two elements of the ground monoid admit a common multiple,

MULTIFRACTION REDUCTION II

11

and this is the point, where the finiteness of the number of basic elements occurs crucially, as
it provides an a priori upper bound on the size of this possible common multiple. Then, we
immediately deduce:
Proposition 3.16. If M is a strongly noetherian gcd-monoid with finitely many basic elements
and RM is semi-convergent, then the word problem for U(M ) is decidable.
Proof. Let S be the atom set of M . By Lemma 3.15, the relation [w]+ ⇒∗ 1 on words in S ∪ S
is decidable. By (3.4) (and by Lemma 2.17(i)), [w]+ ⇒∗ 1 is equivalent to [w]+ ≃± 1. Finally,
by Lemma 3.12, [w]+ ≃± 1 is equivalent to w representing 1 in U(M ). Hence the latter relation
is decidable.

Note that, because the multifraction [w]+ is always defined to be positive, we only need
semi-convergence for RM in the above argument.
In the particular case of Artin-Tits monoids, we deduce
Corollary 3.17. If Conjecture A is true, then the word problem for every Artin-Tits group is
decidable.
Proof. Let M be an Artin-Tits monoid. We noted that M is a gcd-monoid [5], and that it is
strongly noetherian. Next, M has finitely many basic elements: this follows from (and, actually,
is equivalent to) the result that every Artin-Tits monoid has a finite Garside family [15, 21].
Hence M is eligible for Proposition 3.16.

Let us conclude with algorithmic complexity. Lemma 3.15 says nothing about the complexity
of reduction. We show now the existence of an upper bound for the number of reductions.
Lemma 3.18. If M is a strongly noetherian gcd-monoid with finitely many basic elements,
then the number of reduction steps from an n-multifraction a is at most Fn (λ(a1 ), ..., λ(an )),
where λ satisfies (3.13), C is the maximum of λ(a) + 1 for a basic in M , and Fn is inductively
defined by F1 (x) = x + 2 and Fn (x1 , ..., xn ) = (x1 + 1)C Fn−1 (x2 ,... ,xn) .
Proof. An easy induction shows that the function Fn is increasing with respect to each variable
and, for every 1 6 i < n, it satisfies the inequality
(3.19)

Fn (Cx1 , ..., Cxi , xi+1 − 1, xi+2 , ..., xn ) < Fn (x1 , ..., xn ).

For a an n-multifraction, write T (a) for the maximal number of reduction steps from a and λ(a)
for (λ(a1 ), ..., λ(an )). We prove using induction on ⇒ the inequality T (a) 6 Fn (λ(a)) for every
n-multifraction a. Assume a • Ri,x = b with x an atom of M (what can assumed without loss
of generality). We compare the sequences λ(a) and λ(b). By definition, bi+1 is a proper divisor
of ai+1 , which implies λ(bi+1 ) < λ(ai+1 ). Next, ai is the product of at most λ(ai ) basic elements
of M , hence so is bi , implying λ(bi ) 6 Cλ(ai ). Finally, ai−1 is the product of at most λ(ai−1 )
basic elements of M , hence bi−1 is the product of at most λ(ai−1 ) + 1 basic elements, implying
λ(bi−1 ) 6 Cλ(ai−1 ). Then the induction hypothesis implies T (b) 6 Fn (b), so, plugging the
upper bounds for bi , and using that Fn is increasing and (3.19), we find
T (b) 6 Fn (Cλ(a1 ), ..., Cλ(ai ), λ(ai+1 )−1, λ(ai+2 ), ..., λ(an )) < Fn (λ(a1 ), ..., λ(an )) = Fn (λ(a)),
and T (a) 6 T (b) + 1 implies T (b) 6 Fn (b).



The upper bound of Lemma 3.18 is not polynomial (very far from statistical data, which
suggest a quadratic bound), but it is not very high either in the hierarchy of fast growing
functions (it is “primitive recursive”). From there, one can easily deduce a similar upper bound
(tower of exponentials) for the word problem for U(M ) when RM is semi-convergent.

12

PATRICK DEHORNOY

Property H. One says [12, 17, 26] that Property H is true for a presentation (S, R) of a monoid M
if a word w in S ∪ S represents 1 in U(M ) if and only if the empty word can be obtained
from w using special transformations, namely positive and negative equivalence and left and
right reversing. Positive equivalence means replacing a positive factor of w (no letter s) with an
R-equivalent word, negative equivalence means replacing the inverse of a positive factor with
the inverse of an R-equivalent word, whereas right reversing consists in deleting some length
two factor ss or replacing some length two factor st with vu such that sv = tu is a relation
of R, and left reversing consists in deleting some length two factor ss or replacing some length
two factor st with uv such that vs = ut is a relation of R. Roughly speaking, Property H
says that a word representing 1 can be transformed into the empty word without introducing
new trivial factors ss or ss, a situation directly reminiscent of Dehn’s algorithm for hyperbolic
groups, see [17, Section 1.2].
Say that a presentation (S, R) of a monoid M is a right lcm presentation if R consists of
one relation su = tv for each pair of generators s, t that admit a common right multiple, with
su and tv representing s ∨ t. The standard presentation of an Artin-Tits monoid is a right lcm
presentation, and, symmetrically, a left lcm presentation.
Proposition 3.20. If M is a gcd-monoid and RM is semi-convergent, Property H is true for
every presentation of M that is an lcm presentation on both sides.
The point is that applying a rule Ri,x to a multifraction [w]+ can be decomposed into a
sequence of special transformations as defined above. The argument is the same as in the case
±
when RM
is convergent [13, Proposition 5.19], and we do not repeat it.
Thus Conjecture A would imply the statement conjectured in [12]:
Corollary 3.21. If Conjecture A is true, Property H is true for every Artin-Tits presentation.
3.4. Alternative forms. Here we mention several variants of semi-convergence.
±
Proposition 3.22. If M is a noetherian gcd-monoid, then RM
(resp., RM ) is semi-convergent
±
if and only if for every a in FM (resp., FM ),

(3.23)

If a is unital, then a is either trivial or reducible.

±
Proof. Assume that RM
is semi-convergent, and let a be a nontrivial unital multifraction in FM± .
∗
By definition, a ⇒ 1 holds. As a is nontrivial, the reduction requires at least one step, so a
cannot be R-irreducible. Hence, (3.23) is satisfied.
±
Conversely, assume (3.23). As M is noetherian, the rewrite system RM
is terminating, i.e.,
the relation ⇒ admits no infinite descending sequence. Hence we can use induction on ⇒ to
establish (3.4). So let a be a unital multifraction in FM± . If a is ⇒-minimal, i.e., if a is Rirreducible, then, by (3.23), a must be trivial, i.e., we have a = 1, whence a ⇒∗ 1. Otherwise,
a is R-reducible, so there exist i, x such that b = a • Ri,x is defined. By construction, b is ≃± equivalent to a, hence it is unital. By the induction hypothesis, we have b ⇒∗ 1. By transitivity
±
of ⇒∗ , we deduce a ⇒∗ 1. Hence RM
is semi-convergent.
The proof is similar for RM .


Condition (3.23) can be restricted to more special unital multifractions.
Definition 3.24. Call a multifraction a prime if, for every i that is positive (resp., negative)
in a, the entries ai and ai+1 admit no nontrivial common right (resp., left) divisor.
Since dividing adjacent entries by a common factor is a particular case of reduction, an
R-irreducible multifraction must be prime. The converse need not be true: for instance, the
6-multifraction b of Example 3.6 is prime, and it is R-reducible.
±
Proposition 3.25. If M is a noetherian gcd-monoid, then RM
(resp., RM ) is semi-convergent
±
if and only if for every a in FM (resp., FM ),

(3.26)

If a is unital and prime, then a is either trivial or reducible.

MULTIFRACTION REDUCTION II

13

Proof. By Proposition 3.22, the condition is necessary, since (3.26) is subsumed by (3.23).
For the converse implication, assume (3.26). As for Proposition 3.22, we establish (3.4) using
induction on ⇒. Let a be a unital multifraction in FM± . If a is R-irreducible, then it must be
prime, for, otherwise, it is eligible for at least one division, which is a special case of reduction.
Hence, a must be 1 by (3.26). Otherwise, a is R-reducible, there exist i, x such that b = a • Ri,x is
±
is semi-convergent.
defined, the induction hypothesis implies b ⇒∗ 1, hence a ⇒∗ 1. Hence RM
The proof for RM is similar.

Corollary 3.27. Conjecture A is true if and only if (3.26) holds for every Artin-Tits monoid M
and every a in FM .
We turn to another approach. Whenever the ground monoid M is noetherian, the rewrite
±
systems RM
and RM are terminating, hence they are convergent if and only if they are confluent,
meaning that
(3.28)

If we have a ⇒∗ b and a ⇒∗ c, there exists d satisfying b ⇒∗ d and c ⇒∗ d

(“diamond property”). We now observe that semi-convergence is equivalent to a weak form of
confluence involving the unit multifractions 1.
±
Proposition 3.29. If M is a gcd-monoid, then RM
(resp., RM ) is semi-convergent if and only
±
if for every a in FM (resp., FM ),

(3.30)

The conjunction of a ⇒∗ b and a ⇒∗ 1 implies b ⇒∗ 1.

Relation (3.30) can be called 1-confluence for a, since it corresponds to the special case c = 1
of (3.28): indeed, (3.28) with c = 1 claims the existence of d satisfying b ⇒∗ d and 1 ⇒∗ d, and,
as 1 is R-irreducible, we must have d = 1, whence b ⇒∗ 1, as asserted in (3.30). In order to
establish Proposition 3.29, we need an auxiliary result, which connects ≃± with the symmetric
closure of ⇒∗ and is a sort of converse for Lemma 2.17.
Lemma 3.31. If M is a gcd-monoid and a, b belong to FM± , then a ≃± b holds if and only if
there exist a finite sequence c0 , ..., c2r in FM± and p, q in Z satisfying
(3.32)

a · 1p = c0 ⇒∗ c1 ∗⇐ c2 ⇒∗ ···

∗

⇐ c2r = b · 1q .

b ∗ b if a· ⇒∗ b · 1p holds for some p. By Lemma 2.17, a ⇒∗ b
Proof. For a, b in FM± , write a ⇒
∗
b ∗ is transitive. It is also compatible with
implies a · 1r ⇒ b · 1r and, therefore, the relation ⇒
multiplication: on the left, this follows from Lemma 2.17 directly. On the right, a ⇒∗ b · 1p
implies a · c ⇒∗ b · 1p · c for every c, and we observe that 1p · c ⇒∗ c · 1p always holds. Hence, the
b ∗ is a congruence on FM± . As we have 1 ⇒∗ ∅ · 1, a/a ⇒∗ ∅ · 12 and
symmetric closure ≈ of ⇒
∗
/a/a ⇒ ∅ · 1−2 for every a in M , the congruence ≈ contains pairs that generate ≃± . Hence
b ∗ and its inverse connecting a to b. Taking the
a ≃± b implies the existence of a zigzag in ⇒
maximum of |r| for 1r occurring in the zigzag, one obtains (3.32).

±
Proof of Proposition 3.29. Assume that RM
is semi-convergent, and we have a ⇒∗ b and a ⇒∗ 1.
±
is semi-convergent, this
By Lemma 2.17, we have a ≃± b and a ≃± 1, hence b ≃± 1. As RM
±
implies b ⇒∗ 1. So (3.30) is satisfied, and RM is 1-confluent.
±
Conversely, assume that RM
is 1-confluent. We first show using induction on k that, when
0
∗ 1 ∗
2
we have a zigzag c ⇒ c ⇐ c ⇒∗ c3 ∗⇐ c4 ⇒∗ ···, then c0 = 1 implies ck ⇒∗ 1 for every k.
For k = 0, this is the assumption. For k even non-zero, we obtain ck ⇒∗ ck−1 ⇒∗ 1 using the
induction hypothesis, whence ck ⇒∗ 1 by transitivity of ⇒∗ . For k odd, we have ck−1 ⇒∗ 1 by
the induction hypothesis and ck−1 ⇒∗ ck , whence ck ⇒∗ 1 by 1-confluence.
Now assume that a is unital. Lemma 3.31 provides p, q, r and c0 , ..., c2r satisfying

1p = c0 ⇒∗ c1 ∗⇐ c2 ⇒∗ ···

∗

⇐ c2r = a · 1q .

±
As shown above, we deduce a · 1q ⇒∗ 1, whence a ⇒∗ 1 by Lemma 2.17. Hence RM
is semiconvergent.
Once again, the proof for FM is the same.


14

PATRICK DEHORNOY

Corollary 3.33. Conjecture A is true if and only if (3.30) holds for every Artin-Tits monoid M
and every a in FM .
Proposition 3.29 is important for testing Conjecture A, because it shows that, if a ⇒∗ 1
holds, then every sequence of reductions from a inevitably leads to 1. In other words, any
reduction strategy may be applied without loss of generality.
4. Divisions and tame reductions
When reduction is not convergent, it is not confluent either, and a multifraction may admit
several reducts with no subsequent common reduct. However, by restricting to particular
reductions, we can retrieve a (weak) form of confluence and let distinguished reducts appear.
This is the approach we explore in this section. We start in Subsection 4.1 with divisions,
which are particular reductions with good, but too weak properties. Then, in Subsection 4.2,
we extend divisions into what we call tame reductions, which are those reductions that, in
a sense, exclude no subsequent opportunities. Extending the example of divisions to tame
reductions leads us in Subsection 4.3 to the natural notion of a maximal tame reduction and
to Conjecture B about tame reductions from unital multifractions, which is stronger but more
precise than Conjecture A.
We feel that the many technical details, examples, and counter-examples appearing in this
section and the next one are important, because they illustrate how subtle the mechanism of
reduction is. Skipping such details would induce a superficial view and misleadingly suggest
that things are more simple than they really are, possibly leading to naive attempts with no
chance of success.
4.1. Divisions. Divisions are the most direct counterparts of free reductions in free monoids.
They are the special cases of reduction when no remainder appears. No confluence result can be
expected for divisions in a non-free monoid, but we shall see in Proposition 4.4, the main result
of this subsection, that, for every multifraction a, there exists a unique, well-defined maximal
reduct ∂a accessible from a by divisions.
Following the model of reductions, we first fix notation for divisions.
Definition 4.1. If M is a gcd-monoid and a, b belong to FM± , we declare that b = a • Di,x holds
if we have b = a • Ri,x and, in addition, x right (resp., left) divides ai if i is positive (resp.,
±
negative) in a. We use DM
for the family of all Di,x with x 6= 1, write a ⇒div b if some rule
±
∗
for the reflexive–transitive closure of ⇒div .
of DM maps a to b, and ⇒div
So a • Di,x is defined if and only if x divides ai and ai+1 on the due side, and applying Di,x
means dividing ai and ai+1 by x. By definition, a is D-irreducible if and only if it is prime
(Definition 3.24), i.e., the gcds of adjacent entries (on the relevant side) are trivial.
±
Except in degenerated cases, e.g., free monoids, the system DM
is not convergent: typically,
+
for M = ha, b | aba = babi (Artin’s 3-strand braid monoid) and a = a/aba/b, we find
a • D2,b = a/ab/1 and a • D1,a = 1/ab/b, with no further division, and confluence can be
restored only at the expense of applying some reduction Ri,x , here a • D2,b = a • D1,a R2,b .
However, we shall see now that, for every multifraction a, there exists a unique, well-defined
maximal R-reduct of a that can be obtained using divisions.
The first step is to observe that, for each level i, there is always a maximal division at level i,
namely dividing by the gcd of the ith and (i + 1)st entries (on the due side). Indeed, assuming
for instance i positive in a, the multifraction a • Di,x is defined if and only if x right divides
e ai+1 .
both ai and ai+1 , hence if and only if x right divides the right gcd ai ∧
Notation 4.2. If M is a gcd-monoid and a is a multifraction on M , then, for i < kak, we write
a • Dimax for a • Di,x with x the gcd of ai and ai+1 on the due side.
Next, we observe that, contrary to general irreducibility, (local) primeness is robust, in that,
once obtained, it cannot be destroyed by subsequent divisions:

MULTIFRACTION REDUCTION II

15

Lemma 4.3. Say that a multifraction a is j-prime if a • Dj,y is defined for no y 6= 1. If a is
j-prime, then so is a • Di,x for all i, x.
Proof. Assume for instance j positive in a, and let b = a • Di,x . We have either bj = aj (for
i < j − 1 and i > j) or bj 6 aj (for i = j − 1); similarly, we have either bj+1 = aj+1 (for i < j
e ai+1 = 1
and i > j + 1) or bj+1 6 aj+1 (for i = j + 1). Hence, in all cases, the assumption ai ∧
e
implies bi ∧ bi+1 = 1.


Hence, if we start with a multifraction a and apply, in any order, maximal divisions Dimax in
such a way that every level between 1 and kak − 1 is visited at least one, we always finish with
a prime multifraction. The latter may depend on the order of the divisions, but we shall now
see that there exists a preferred choice.
Proposition 4.4. Let M be a gcd-monoid. For every n-multifraction a on M , put
max
max
∂a := a • Dn−1
Dn−2
···D1max .

(4.5)

Then, ∂a is prime, and, for every multifraction b on M ,
∗
a ⇒div
b

(4.6)

implies

∗
b ⇒div
∂b ⇒∗ ∂a.

Thus ∂a is a reduct of every multifraction obtained from a using division. The proof of
Proposition 4.4 is nontrivial and requires to precisely control the way divisions and reductions
can be commuted. We begin with a confluence result. By [13, Lemma 4.6], there always exists
a confluence solution for any two reductions at level i and i + 1. This applies of course when
one of the reductions is a division, but, in that case, we can say more.
Lemma 4.7. Assume that both a • Ri+1,x and a • Di,y are defined. Then we have a • Ri+1,x Di,z =
a • Di,y Ri+1,x , where z is determined by the equalities ai = ay, x ∨ a = av, and vz = v ∨ y
e a = va, and zv = v ∨
e y) for i positive (resp., negative) in a. Moreover, if y
(resp., ai = ya, x ∨
is maximal for a (i.e., y is the gcd of ai and ai+1 ), then z is maximal for a • Ri+1,x .
Proof. (Figure 2) Assume that i is positive in a, so ai+1 is negative in a. Put b := a • Ri+1,x
and c := a • Di,y . By definition, there exists x′ satisfying
bi−1 = ai−1 , bi = ai x′ , xbi+1 = ai+1 x′ = x ∨ ai+1 , xbi+2 = ai+2 ,
ci−1 = ai−1 , ci y = ai , ci y = ai , ci+2 = ai+2 .
As ai+1 is ci+1 y, Lemma 2.11 implies the existence of u, v, and z satisfying
(4.8)

bi+1 = uz

with

ci+1 v = xu = x ∨ ci+1

and yx′ = vz = y ∨ v.

By construction, we have bi = ai x′ = ci yx′ = ci vz, which shows that z right divides both bi
and bi+1 . Hence d := b • Di,z is defined, and we have
(4.9)

di−1 = ai−1 ,

di = cv ,

di+1 = u,

di+2 = bi+2 .

On the other hand, by assumption, x left divides ci+2 , which is ai+2 , and x and ci+1 admit a
common right multiple, namely their right lcm xu. Hence, c • Ri,x is defined, and comparing
with (4.9) directly yields the expected equality c • Ri,x = b • Di,z .
e ai+1 .
It remains to prove that, if y is maximal for a, then z is maximal for b. So assume y = ai ∧
e
We deduce ci ∧ ci+1 = 1. On the other hand, by Lemma 3.1, the assumption ci+1 v = ci+1 ∨ x
e v = 1. Then (the symmetric counterpart of) Lemma 2.13 implies ci v ∧
e u = 1, whence
implies u ∧
e
bi ∧ bi+1 = z.

A symmetric argument applies when i is negative in a.

Next, we observe that reduction and division commute when performed at distant levels: the
result is easy for very distant levels, slightly more delicate when the levels are closer.
Lemma 4.10. Assume b = a • Ri,x , and j 6= i, i + 1, i − 2 (resp., j = i − 2). Put a′ := a • Djmax
max
and b′ := b • Djmax . Then we have b′ = a′ • Ri,x (resp., b′ = a′ • Ri,x Di−2
).

16

PATRICK DEHORNOY

ai+2
bi+2

x
ci

ci+1 a

v

y
ai−1

ai

u
bi+1
z

x′

bi
Figure 2. Proof of Lemma 4.7: if a is eligible both for Ri+1,x and Di,y , we can
start with either and converge to the colored path.

Proof. For j 6 i−3 or j > i+2, the reduction Ri,x does not change the jth and (j +1)st entries,
so the greatest division at level j remains the same, and commutation is straightforward. For
j = i − 1, Lemma 4.7 gives b′ = a′ • Ri,x .
Assume j = i − 2. Then the reduction Ri,x does not change the jth entry, but it possibly
increases the (j + 1)st entry. So, if Dj,y is the maximal j-division for a, then Dj,y applies
to b, but it need not be the maximal j-division for b. Expanding the definitions, we obtain the
commutation relation a • Ri,x Dj,y = a • Dj,y Ri,x , meaning b • Dj,y = a′ • Ri,x , together with
max
, as expected.

b′ = (b • Dj,y )Djmax , whence b′ = a′ • Ri,x Di−2
The last preliminary result, needed for the end of the proof of Proposition 4.4, connects ∂a
and ∂b in the (very special) case when b is an elementary reduct of a and a is prime at every
sufficiently large level.
Lemma 4.11. If a and b are j-prime for j > i, then b = a • Ri+1,x implies ∂a ⇒∗ ∂b.
max
max
Proof. By assumption, we have ∂a = a • Di−1
···D1max and ∂b = b • Di−1
···D1max . Put ai := a,
i
j
j+1
j
j+1
max
max
• D
,b =b
• D
for j decreasing from i − 1 to 1,
b := b and, inductively, a = a
j
j
1
1
yielding ∂a = a and ∂b = b . We prove using induction on j decreasing from i to 1 that, for
every y, there exist x0 , x1 , ..., xk with i−2k > j satisfying bj = aj • Ri+1,x0 Ri−1,x1 ···Rx−2k+1,xk .
By assumption, the property is true for j = i, with k = 0 and x0 = x. Assume i > j > 1. By
induction hypothesis, we have bj+1 = aj+1 • Ri+1,x0 Ri−1,x1 ···Ri−2k+1,xk for some x0 , ..., xk with
i−2k > j+1. By repeated applications of Lemma 4.10, we deduce that each reduction Ri−2ℓ+1,xℓ
commutes with Djmax , except the last one in the case i − 2k = j + 2, in which case Lemma 4.10
prescribes to add one more reduction (a division) Ri−2k−1,xk+1 . In this way, we obtain either
bj = aj • Ri+1,x0 Ri−1,x1 ···Ri−2k+1,xk , or bj = aj • Ri+1,x0 Ri−1,x1 ···Ri−2k+1,xk Ri−2k−1,xk+1 , and
the induction continues.


We can now complete the argument for Proposition 4.4. The proof that ∂a is prime is easy,
but that of the relation (4.4) is more delicate.
max
Proof of Proposition 4.4. It follows from the definition that a • Dn−1
is (n − 1)-prime, then that
max
max
a • Dn−1 Dn−2 is (n − 1)- and (n − 2)-prime, etc., hence that ∂a is i-prime for 1 6 i < n, hence
it is prime.
∗
b implies ∂b ⇒∗ ∂a. For an induction, it is
We now establish (4.6), i.e., prove that a ⇒div
∗
sufficient to prove that a ⇒div b implies ∂b ⇒ ∂a. So, we assume b = a • Di,z , and aim at
∗
∂a. Put kak = n. By definition, ∂a and ∂b are obtained by performing n − 1
proving ∂b ⇒div
successive divisions, and we shall establish a step-by-step connection summarized in Figure 3.
Put an := a, bn := b, and let ai (resp., bi ) be obtained from ai+1 (resp., bi+1 ) by applying Dimax ,
so that we finally have ∂a = a1 and ∂b = b1 . We assume that i is positive in a.
Consider first j > i + 2. Applying Lemma 4.10, we inductively obtain bj = aj • Di,z , implying
the commutativity of the n − i − 2 left hand squares in the diagram of Figure 3.

MULTIFRACTION REDUCTION II

17

Now let x = ai+1 ∧ ai+2 . By definition, we have ai+1 = ai+2 • Di+1,x . By Lemma 4.7, there
exists c and z ′ satisfying c = ai+2 • Di+1,x Di,z′ = ai+2 • Di,z Ri+1,x , which reads c = ai+1 Di,z′ =
bi+2 • Ri+1,x .
Next, c is obtained from ai+1 by some i-division, whereas ai is obtained from ai+1 by the
maximal i-division, hence ai must be obtained from c by some further i-division, namely the
maximal i-division for c. So, ai = c • Dimax holds.
On the other hand, bi+1 is obtained from bi+2 by the maximal (i + 1)-division, namely Di+1,y
with y = bi+1 ∧ bi+2 . As we have x = ai+2 ∧ ai+2 and bi+2 = ai+2 , the relation bi+1 6 ai+1
implies y 6 x, say x = yx′ . If follows that reducing x at level i + 1 in bi+2 amounts to first
dividing by y and then reducing x′ , i.e., we have b • Ri+1,x = b • Di+1,y Ri+1,x′ = bi+1 • Ri+1,x′ .
Now, two reductions apply to bi+1 , namely Ri+1,x′ , which leads to c, and Dimax , which is,
say, Di+1,y and leads to bi . Applying Lemma 4.7 again, we obtain the existence of y ′ satisfying
bi+1 • Ri+1,x′ Di,y′ = bi+1 • Di,y Ri+1,x′ , which boils down to c • Di,y′ = bi • Ri+1,x′ . Moreover, as
Di,y is the maximal i-division applying to bi+1 , Lemma 4.7 implies that Di,y′ is the maximal
i-division applying to c. We obtained above ai = c • Dimax , so we deduce ai = bi • Ri+1,x′ .
From there, we are in position for applying Lemma 4.11 (with a and b interchanged): we have
ai = bi • Ri+1,x′ , and, by construction, ai and bi are j-prime for every j > i. Then Lemma 4.11

ensures b1 ⇒∗ a1 , which is ∂b ⇒∗ ∂a.
an

max
Dn−1

an−1

Di,z
b

n
max
Dn−1

ai+2

Di,z
b

n−1

max
Di+1

ai+1

Di,z
b

Dimax

ai

Di,z′

i+2

c

Ri+1,x

Dimax

a

i

Ri+1,x′
b

i+2

i+1

max
Di+1

b

Dimax

max
Di−1

ai−1

Ri+1,x′
b

i
max
Di−1

a2

D1max

Lemma 4.11
b

i−1

b

2

D1max

∂a
∗
∂b

Figure 3. Comparing the computations of ∂a and ∂(a • Di,x ).
Let us denote by Irr(a) the family of all R-irreducible reducts of a. The failure of confluence
means that Irr(a) may content more than one element, and controlling Irr(a) is one of the main
challenges in the current approach. As, for every multifraction a, we have now a distinguished
∗
reduct ∂a, a natural task is to compare Irr(∂a) with Irr(a). By definition, a ⇒div
∂a implies
∗
Irr(∂a) ⊆ Irr(a), and, by Proposition 4.4, a ⇒div b implies b ⇒ ∂a, whence Irr(∂a) ⊆ Irr(∂b).
The next examples show these easy inclusions are the best we can expect in general.
e 2 , let a = ab/aba/aca. Then one finds
Example 4.12. In the Artin-Tits monoid of type A
Irr(a) = {a1 , a2 }, with a1 = a • D2,a = ab/ba/ca and a2 = a • D1,ab R2,c = cb/bc/ac. Now,
we obtain ∂a = a1 , whence Irr(∂a) = {a1 }: so, by performing divisions, we lost one of the
irreducible reducts of a. On the other hand, for b = a • D1,ab = 1/b/aca, we find ∂b = b and
Irr(∂b) = Irr(b) = {a1 , a2 } = Irr(a): so a ⇒div b does not imply Irr(∂b) ⊆ Irr(∂a).
Remark 4.13. The order of divisions is important in the definition of ∂a and, even at the
expense of using reductions instead of divisions, we cannot start from low levels in general.
Indeed, for kak = 3, Lemma 4.7 implies ∂a = a • R1,x1 R2,x2 , with xi the (relevant) gcd of ai
Q
and ai+1 , but this expression of ∂a as a • i=kak−1
Ri,xi with xi gcd of ai and ai+1 does not work
i=1
for kak > 4: for instance, for a := a/a/a/a, one finds a • R1,x1 R2,x2 R3,x3 = a/a/1/1 6= ∂a = 1.
4.2. Tame reductions. What motivates studying divisions specifically is that the latter satisfy
a form of confluence: by Lemma 4.7 and the results of [13], if a multifraction a is eligible for a
division Di,x and for another reduction Rj,y , a common reduct for a • Di,x and a • Rj,y always
exists. Moreover, we saw in Proposition 4.4 that there always exists a maximal div-reduct
with good compatibility properties of the associated operator ∂. However, because many prime

18

PATRICK DEHORNOY

multifractions are not irreducible, and, in particular, many prime unital multifractions are not
trivial, it is hopeless to analyze reduction in terms of divisions exclusively, making it natural to
try to extend the family of divisions so as to preserve its main property, namely “guaranteed
confluence”. This leads to tame reductions, and the main result here is that, exactly as in
the case of divisions, there exists for each multifraction a and each level i a maximal tame
i-reduction applying to a.
Definition 4.14. If a is a multifraction, we say that x is an i-reducer for a if a • Ri,x is defined;
we then say that an i-reducer x is tame for a if, for all j, y such that a • Rj,y is defined, a • Ri,x
and a • Rj,y admit a common reduct; otherwise, x is called wild for a.
Thus x is a tame i-reducer for a if reducing x in a leaves all possibilities for further reductions
open, whereas reducing a wild i-reducer excludes at least one subsequent confluence.
±
Example 4.15. If M is a gcd-monoid satisfying the 3-Ore condition, the system RM
is confluent
and, therefore, every reducer is tame for every multifraction it applies to. By contrast, in the
e 2 , for a = 1/c/aba, both a and b are 2-reducers for a, but a • R2,a and
Artin-Tits of type A
a • R2,b admit no common reduct, hence a and b are wild 2-reducers for a.

To prove the existence of the maximal tame i-reducer in Proposition 4.18 below, we shall
use convenient characterizations of tame reducers established in Lemmas 4.16 and 4.17.

Lemma 4.16. If M is a gcd-monoid, a is a multifraction on M , and a • Ri,x is defined, then
x is a tame i-reducer for a if and only if for i positive (resp., negative) in a, the elements x, y,
and ai admit a common right (resp., left) multiple whenever a • Ri,y is defined.
Proof. Assume that x is a tame i-reducer for a, and let y be an i-reducer for a. By definition,
a • Ri,x and a • Ri,y admit a common reduct, which is necessarily of the form a • Ri,z for some z.
Then there exist u, v satisfying
a • Ri,z = (a • Ri,x ) • Ri,u = (a • Ri,y ) • Ri,v .
Assuming i negative in a, we deduce z = xu = yv. Hence z is a right multiple of x ∨ y and,
therefore, a • Ri,x∨y is defined as well, implying that ai , x, and y admit a common right multiple.
The argument is symmetric when i is positive in a.
Conversely, assume that x is an i-reducer for a and, for every i-reducer y, the elements ai ,
x, and y admit a common multiple, say a common right multiple, assuming that i is negative
in a. Then x ∨ y left divides ai+1 since x and y do, and ai and x ∨ y admit a common right
multiple. Hence a • Ri,x∨y is defined. Then, writing x ∨ y = xy ′ = yx′ , we have
a • Ri,x∨y = (a • Ri,x ) • Ri,y′ = (a • Rj,y ) • Ri,x′ ,
which shows that a • Ri,x and a • Ri,y admit a common reduct. On the other hand, for j 6= i,
Lemmas 4.18 and 4.19 from [13] imply that a • Ri,x and a • Rj,y always admit a common reduct.
Therefore, x is a tame i-reducer for a.

If M is a noetherian gcd-monoid, every nonempty family X of left divisors of an element a
necessarily admits <-maximal elements, i.e., elements z such that there is no x with z < x in
e
the family: take z so that z −1 a is <-minimal
in {x−1 a | x ∈ X}. Hence, in particular, for every
multifraction a and every level i, there exist maximal i-reducers for a.
Lemma 4.17. If M is a noetherian gcd-monoid and a is a multifraction on M , an i-reducer x
for a is tame if and only if x divides every maximal i-reducer for a.

Proof. Assume that x is a tame i-reducer for a, and y is a maximal i-reducer for a. By
Lemma 4.16, ai , x, and y admit a common multiple, hence an lcm, and, therefore, the lcm of x
and y is again an i-reducer for a. The assumption that y is maximal implies that this lcm is y,
i.e., that x divides y (on the due side).
Conversely, assume that x is an i-reducer for a that divides every maximal i-reducer. Let y
be an arbitrary i-reducer for a. As M is noetherian, y divides at least one maximal i-reducer,

MULTIFRACTION REDUCTION II

19

say z. By assumption, x divides z, hence so does the lcm of x and y. Since z is an i-reducer
for a, so is its divisor the lcm of x and y and, therefore, a • Ri,x and a • Ri,y admit a common

reduct. Hence x is tame for a.
Proposition 4.18. If M is a noetherian gcd-monoid and a is a multifraction on M , then, for
every i < kak, there exists a unique greatest tame i-reducer for a, namely the gcd of all maximal
i-reducers for a. The latter is a multiple of the gcd of ai and ai+1 .
Proof. Let z be the gcd (on the relevant side) of all maximal i-reducers for a. Then z, and
every divisor x of z, divides every maximal i-reducer for a, hence, by Lemma 4.17, it is a tame
i-reducer for a.
Conversely, if x is a tame i-reducer for a, then, by Lemma 4.17, x divides every maximal
i-reducer for a, hence it divides their gcd z. Hence z is the greatest tame i-reducer for a.
Finally, assume that x divides ai and ai+1 . Then a • Di,x , hence a fortiori a • Ri,x is defined,
so x is an i-reducer for a. Let y be any i-reducer for a. Then the lcm of ai and y is a common
multiple of ai , x, and y. Hence, by Lemma 4.16, x is a tame i-reducer for a. This applies in
particular when x is the gcd of ai and ai+1 .

On the shape of what we did with divisions, we introduce
Definition 4.19. If M is a noetherian gcd-monoid and a is a multifraction on M , then, for
i < kak, the unique element x whose existence is stated in Proposition 4.18 is called the greatest
tame i-reducer for a; we then write a • Rimax for a • Ri,x .
Example 4.20. When M satisfies the 3-Ore condition, every reducer is tame, and a • Rimax
coincides with the maximal i-reduct of a, as used in [13, Section 6]. Otherwise, wild reducers
e 2,
may exist and a • Rimax need not be a maximal i-reduct of a: in the Artin-Tits monoid of type A
for a = 1/c/aba, we have a • R2max = a, since there is no nontrivial tame 2-reducer.

By definition, the greatest tame i-reducer for a only depends on the entries ai and ai+1 ,
and on the sign of i in a. By Lemma 4.17, it can be computed easily as a gcd of maximal
reducers. Note that the greatest tame i-reducer for a may be strictly larger than the gcd of ai
e 2 , there exist two maximal 2-reducers
and ai+1 : for instance, in the Artin-Tits monoid of type A
for a := 1/a/cabab, namely caa and cab, both wild, and the greatest tame 2-reducer is their
left gcd ca, a proper multiple of the left gcd of a and cabab, which is 1.
If M is a noetherian gcd-monoid, starting from an arbitrary multifraction a and repeatedly
performing (maximal) tame reductions leads in finitely many steps to a ≃± -equivalent multifraction that is tame-irreducible, meaning eligible for no tame reduction. By Proposition 4.18,
a division is always tame, so a tame-irreducible multifraction is prime. Adapting the proof of
Proposition 3.25 yields:
±
Proposition 4.21. If M is a noetherian gcd-monoid, then RM
(resp., RM ) is semi-convergent
±
if and only if, for every a in FM (resp., FM ),

(4.22)

If a is unital and tame-irreducible, then a is either trivial or reducible.

Corollary 4.23. Conjecture A is true if and only if (4.22) holds for every Artin-Tits monoid M
and every a in FM .
The above results suggest to investigate tame-irreducible multifractions more closely. By
definition, only wild reductions may apply to a tame-irreducible multifraction. A possible
approach for establishing (4.22) could be to study the irreducible reducts of tame-irreducible
multifractions. It happens frequently that, if a is tame-irreducible and admits several (wild)
reducts a1 , ..., am , then the reducts of the various ak s are pairwise disjoint, as if every such
reduct kept a trace of ak . If true, such a property might lead to a proof of Conjecture A using
Corollary 4.23 and arguments similar to those alluded to in the proof of Proposition 7.3. But
e 2,
the assumption is not readily correct. Indeed, always in the Artin-Tits monoid of type A
the 6-multifraction a := 1/c/aba/bc/a/bcb is tame-irreducible, it admits four wild reducers,

20

PATRICK DEHORNOY

namely a and b at level 2, and b and c at level 5, and the associated 2-reducts of a admit a
common reduct
(a • R2,a ) • R5,c R3,b R1,ac R2,b R3,c = bc/accb/ca/ab/ca/cb = (a • R2,b ) • R5,c R3,cb .
However, in this example, there is no confluence for the 5-reducts, and, more generally, we have
no example where the highest level wild reducts of a tame-irreducible multifraction admit a
common reduct.
4.3. The operator redt and Conjecture B. Our main claim in this section is that, for every
multifraction a, there exists a distinguished tame reduct of a, denoted redt (a), that can be
computed easily, and that should be 1 whenever a is unital: this is what we call Conjecture B.
Just mimicking the approach of Section 4.1 and trying to identify a unique maximal tame
reduct on the shape of ∂a cannot work, because the tame reducts of a multifraction need
e 2 again, a and b are tame 4-reducers
not admit a common reduct: in the context of type A
for a := 1/c/1/1/aba, but a • R4,a and a • R4,b admit no common reduct (by the way, in this
case, the two irreducible reducts of a can be reached using tame reductions only, respectively
R4,a R2,a R4,ba and R4,b R2,b R4,ab .
However, it is shown in [13, Section 6] that, if M is a noetherian gcd-monoid satisfying
the 3-Ore condition, hence in a case when all reductions are tame, there exists, for each n, a
universal sequence of levels U (n) such that, starting with any n-multifraction a and applying
the maximal (tame) reduction at the successive levels prescribed by U (n) inevitably leads to
the unique R-irreducible reduct red(a) of a. It is then natural to copy the recipe in the general
case, and to introduce:
Definition 4.24. If M is a noetherian gcd-monoid, then, for every depth n multifraction a
max
on M , we put redt (a) := a • RU(n)
, where U (n) is empty for n = 0, 1 and is (1, 2, ..., n − 1)
···Rimax
.
followed by U (n − 2) for n > 2, and, for i = (i1 , ..., iℓ ), we write a • Rimax for a • Rimax
1
ℓ
Thus, by [13, Proposition 6.7], if M is a noetherian gcd-monoid satisfying the 3-Ore condition,
red(a) = redt (a) holds for every a in FM . In this case, b ⇒∗ redt (a) holds for every reduct b of a,
and redt (a) is always R-irreducible. It is easy to see that, in the general case, these properties
do not extend to arbitrary (namely, not necessarily unital) multifractions.
e 2 , let a := 1/c/aba. Then U (3) = (1, 2)
Example 4.25. In the Artin-Tits monoid of type A
leads to redt (a) = a • R1max R2max = a, since 1 and c have no nontrivial common divisor, and
there is no tame 2-reducer for a. On the other hand, both a and b are 2-reducers for a, and
neither a • R2,a ⇒∗ redt (a) nor a • R2,b ⇒∗ redt (a) holds.
Next, let b := ac/aca/aba. We find redt (b) = b • D1,ac = 1/c/aba, to be compared with
∗ ′
b does not imply b′ ⇒∗ redt (b).
∂b = b • D2,a = ac/ca/ba. Then ∂b ⇒∗ redt (b) fails, so b ⇒div
Finally, let c := 1/c/aba/cb. We find redt (c) = c • D3,b = 1/c/ba/c, which is not irreducible,
nor even tame-irreducible: we have red2t (c) = redt (c) • R2,b R3,c = bc/cb/a/c.
However, these negative facts say nothing about tame reductions starting from a unital
multifraction, and, in spite of many tries, no counter-example was ever found so far to:
Conjecture B. If M is an Artin-Tits monoid, then redt (a) = 1 holds for every unital multifraction a in FM .
By definition, a ⇒∗ redt (a) holds, so redt (a) = 1 is a strengthening of a ⇒∗ 1 in which we
assert not only that a reduces to 1 but also that it goes to 1 in some prescribed way. Thus:
Fact 4.26. Conjecture B implies Conjecture A.
Although Conjecture B is more demanding than Conjecture A, it might be easier to establish
(or to contradict), as it predicts a definite equality rather than an existential statement. As
recalled above, [13, Proposition 6.7] implies that Conjecture B is true for every Artin-Tits
monoid of FC type. On the other hand, an example of a gcd-monoid (but not an Artin–Tits
one) for which (the counterpart of) Conjecture A is true but (that of) Conjecture B is false is
given in [19].

MULTIFRACTION REDUCTION II

21

5. Cross-confluence
Besides tame reductions and Conjecture B of Section 4, we now develop another approach to
e of R. The
Conjecture A, involving both the reduction system R and a symmetric counterpart R
properties of reduction and its counterpart are just symmetric, but interesting features appear
when both are used simultaneously, in particular what we call cross-confluence, a completely
novel property to the best of our knowledge. We are then led to a new statement, Conjecture C,
which would imply Conjecture A and, from there, the decidability of the word problem.
The section comprises four subsections. First, right reduction, the symmetric counterpart of
(left) reduction, is introduced in Subsection 5.1, and its basic properties are established. Next,
cross-conflence, which combines reduction and its counterpart, is introduced in Subsection 5.2,
and partial results are established. Then Conjecture C and its uniform version Cunif are stated
and discussed in Subsection 5.3. Finally, we briefly study in an Appendix the termination of
the joint system obtained by merging left and right reduction, a natural topic with nontrivial
results, but not directly connected so far to our main conjectures.
5.1. Right reduction. By definition, the reduction rule Ri,x of Definition 2.15 consists in
pushing a factor x to the left (small index entries) in the multifraction it is applied to: for
this reason, we shall call it a left reduction. From now on, we shall also consider symmetric
counterparts, naturally called right reductions, where elements are pushed to the right.
Definition 5.1. If M is a gcd-monoid and a, b lie in FM± , then, for i > 1 and x in M , we declare
ei,x holds if we have kbk = kak, bk = ak for k 6= i − 1, i, i + 1, and there exists x′
that b = a • R
(necessarily unique) satisfying
for
for
for
for

i < kak
i < kak
i = kak
i = kak

positive in a:
negative in a:
positive in a:
negative in a:

xbi−1 = ai−1 , xbi = ai x′ = x ∨ ai , bi+1 = ai+1 x′ ,
e ai , bi+1 = x′ ai+1 ,
bi−1 x = ai−1 , bi x = x′ ai = x ∨
xbi−1 = ai−1 ,
xbi = ai ,
bi−1 x = ai−1 ,
b i x = ai .

ei,x holds for some i and some x 6= 1, and use ⇒
e b if a • R
e ∗ for the reflexive–
We write a ⇒
±
±
eM so obtained on FM is called right reduction,
transitive closure of ⇒.
e The rewrite system R
eM .
and its restriction to FM (positive multifractions) is denoted by R

ei,x is symmetric of that of Ri,x : one extracts x from ai−1 , lets it cross ai
The action of R
using an lcm, and incorporates the resulting remainder in ai+1 , thus carrying x from level i − 1
en,x for n = kak is adapted to
to level i + 1, see Figure 4. As in the case of R1,x , the action of R
avoid creating a (n + 1)st entry.
Ri,x :
...

ei,x :
R

ai

ai−1
x′

⇐

...

x

ai

ai−1

ai+1

x′

⇐

ai+1
...

x

bi−1

bi

bi+1

bi−1

bi

bi+1

ai−1

ai

ai+1

ai−1

ai

ai+1

...

x
bi−1

⇒
bi

...

x′
bi+1

x
bi−1

⇒
bi

...

x′
bi+1

ei,x : in the
Figure 4. Comparing the left reduction Ri,x and the right reduction R
first case (top), one pushes the factor x from ai+1 to ai−1 through ai , in the second
case (bottom), one pushes x from ai−1 to ai+1 through ai .

22

PATRICK DEHORNOY

Remark 5.2. Right reduction is not an inverse of left reduction: when the reduced factor x
crosses (in one direction or the other) the entry ai , using the lcm operation cancels common
ei,x amount to dividing by x and,
factors. Typically, if x divides ai , then both Ri,x and R
therefore, their actions coincide. See Remark 5.26 for more on this.

The rest of this subsection is devoted to the basic properties of right reduction and their
connection with those of left reduction, in particular with respect to convergence and semiconvergence. As can be expected, the convenient tool is an operation exchanging left and right
reduction, in this case the duality map e of Notation 3.7.
Lemma 5.3. If M is a gcd-monoid, then, for all a, b in FM± ,
(5.4)

a ⇒ b is equivalent to e
a ⇒
e eb.

Proof. Comparing the definitions shows that, if a and b have depth n, then b = a • Ri,x is
en+1−i,x , whence (5.4).
a•R

equivalent to eb = e

The following properties of right reduction follow almost directly from their counterpart
involving left reduction. The only point requiring some care is the lack of involutivity of e,
itself resulting from the lack of surjectivity of the map a 7→ 1 · a.

Lemma 5.5. Assume that M is a gcd-monoid.
e ∗ b implies a ≃± b.
(i) The relation ⇒
e ∗ is included in ≃± , i.e., a ⇒
∗
(ii) The relation ⇒
e is compatible with the multiplication of FM± .
e ∗ b is equivalent to 1p · a · 1q ⇒
e ∗ 1p · b · 1q .
(iii) For all a, b and p, q, the relation a ⇒
(iv) If a, b belong to FM , then a ⇒ b is equivalent to 1 · e
a ⇒
e 1 · eb, and a ⇒
e b is equivalent
e
to 1 · e
a ⇒ 1 · b.

Proof. (i) By (5.4), a ⇒
e ∗ b implies e
a ⇒∗ eb, whence ι(e
a) = ι(eb) by Lemma 2.17(i), hence
±
ι(a) = ι(b) by Lemma 3.9, i.e., a ≃ b.
(ii) For all c, d, the relation a ⇒
e ∗ b implies e
a ⇒∗ eb, whence e
d·e
a ·ec ⇒∗ e
d·eb·ec by Lemma 2.17(ii),
∗
which is (c · a · d)e ⇒ (c · b · d)e by Lemma 3.9, and finally c · a · d ⇒∗ c · b · d by (5.4) again.
(iii) Using duality as above, the result follows now from Lemma 2.17(iii).
(iv) By (5.4), a ⇒ b is equivalent to e
a ⇒
e eb, hence, by (iii), it is also equivalent to 1 · a ⇒ 1 · b.
Similarly, by (5.4) again, a ⇒
e b is equivalent to e
a ⇒ eb, hence, by Lemma 2.17, it is also

equivalent to 1 · e
a ⇒ 1 · eb.

By (5.4), an infinite sequence of right reductions would provide an infinite sequence of left
±
±
eM
reductions, and vice versa, so R
is terminating if and only if RM
is. Comparing irreducible
elements is straightforward:

Lemma 5.6. If M is a gcd-monoid, a multifraction a is R-irreducible if and only if e
a is
e
e
R-irreducible.
For a positive with kak even, a is R-irreducible
if and only if e
a is R-irreducible.

e
e b. By (5.4), we deduce a = e
a ⇒ eb, hence a is not R-irreducible. So a
Proof. Assume e
a ⇒
e
being R-irreducible implies that e
a is R-irreducible.
Conversely, assume e
a ⇒ b. By (5.4), we
e
e
e
e
deduce a = e
a ⇒
e b, hence a is not R-irreducible. So a being R-irreducible implies that e
a is
R-irreducible. For the second equivalence, use the involutivity of e on positive multifractions
of even depth (but we claim nothing for positive multifractions of odd length).

Using the above technical results, we can compare convergence and semi-convergence for left
and right reduction. Below, observe the difference between (i) and (ii), which involve only one
direction but multifractions of both signs, and (iii), which only involves positive multifractions
and requires using both left and right reductions. This distinction is one of the reasons for
considering both positive and negative multifractions in this paper (contrary to [13]).

MULTIFRACTION REDUCTION II

23

Proposition 5.7. For every gcd-monoid M , the following are equivalent:
±
(i) The system RM
is convergent (resp., semi-convergent);
±
eM
(ii) The system R
is convergent (resp., semi-convergent);
eM are convergent (resp., semi-convergent).
(iii) The systems RM and R

±
Proof. We begin with convergence. Assume that RM
is convergent. Let a belong to FM± . Let
a). By definition, we have e
a ⇒∗ b. Then, by Lemmas 5.5 and 5.6, we have a ⇒
e ∗ eb
b = red(e
e
e
and eb is R-irreducible.
Assume that c is R-irreducible
and a ⇒
e ∗ c holds. By Lemmas 5.5
±
∗
and 5.6 again, we deduce e
a ⇒ ec and ec is R-irreducible. The assumption that RM
is convergent
±
e
e
eM
implies ec = b, whence c = eb. Hence eb is the only R-irreducible
R-reduct
of a. Therefore, R
is convergent, and (i) implies (ii). The converse implication is proved in the same way, so (i) is
equivalent to (ii).
e
Since all R-reducts and R-reducts
of a positive multifraction are positive, it is clear that (i)
eM is convergent. Conversely, assume that
implies that RM is convergent, and (ii) implies that R
e
both RM and RM are convergent. Let a be an arbitrary multifraction on M . Assume first that
a is positive. Let b be the unique R-irreducible reduct of a. Assume now that a is negative.
e
e
Then e
a is positive. Let b be the unique R-irreducible
R-reduct
of e
a. By Lemmas 5.5 and 5.6, eb
∗
is R-irreducible, and a ⇒ b holds. Now assume that c is R-irreducible and a ⇒∗ c holds. Then
eM is convergent, we deduce ec = b,
ec is R-irreducible and e
a ⇒
e ∗ ec holds. As e
a is positive and R
±
whence c = eb. Hence RM is convergent, and (iii) implies (i). This completes the argument for
convergence.
±
Assume now that RM
is semi-convergent. Let a be a unital multifraction. By Lemma 2.17, e
a
±
∗ e
∗
e
is unital as well, hence we must have e
a ⇒ 1, which, by (5.4), implies a ⇒
e 1 = 1. Hence RM is
semi-convergent. The converse implication is similar, so (i) and (ii) are equivalent in this case as
eM
well. On the other hand, (i) and (ii) clearly imply (iii). Finally, assume that both RM and R
are semi-convergent. Let a be a unital multifraction. If a is positive, the assumption that RM is
eM
semi-convergent implies a ⇒∗ 1. If a is negative, then e
a is positive, and the assumption that R
∗
±
∗ e
is semi-convergent implies e
a ⇒
e 1, whence a ⇒ 1 = 1 by (5.4). Hence RM is semi-convergent.
So (iii) implies (i), which completes the argument for semi-convergence.


f
= (red(e
a))e.
In the convergent case, the above proof implies, with obvious notation, red(a)

Remark 5.8. It is shown in [13, Sec. 3] that, when left reduction is considered, trimming
final trivial entries essentially does not change reduction. This is not true for right reduction:
deleting trivial final entries can change the reducts, as deleting trivial initial entries does in the
case of left reduction.
5.2. The cross-confluence property. We now introduce our main new notion, a variant of
confluence that combines left and right reduction.
Definition 5.9. If M is a gcd-monoid, we say that RM is cross-confluent if, for all a, b, c in FM ,
(5.10)

e ∗ b and a ⇒
e ∗ c, there exists d satisfying b ⇒∗ d and c ⇒∗ d.
If we have a ⇒

So cross-confluence for RM means that left reduction provides a solution for the confluence
±
pairs of right reduction. We shall naturally say that RM
is cross-confluent if (5.10) holds for
±
eM is cross-confluent if right reduction provides
all a, b, c in FM . On the other hand, we say that R
a solution for the confluence pairs of left reduction, that is, if
(5.11)

e ∗ d and c ⇒
e ∗ d.
If we have a ⇒∗ b and a ⇒∗ c, there exists d satisfying b ⇒

±
eM
is cross-confluent if (5.11) holds for all a, b, c in FM± .
holds for all a, b, c in FM . Finally, R

Remark 5.12. The definition of cross-confluence involves both left and right reduction. But,
owing to the equivalence (5.4), it can alternatively be stated as a property involving left reduc±
tion exclusively. Indeed, in the case of RM
, cross-confluence is equivalent to
(5.13)

a ⇒∗ ec, there exists d satisfying b ⇒∗ d and c ⇒∗ d,
If we have e
a ⇒∗ eb and e

24

PATRICK DEHORNOY

±
eM
and similarly for R
. In the case of RM , when we restrict to positive multifractions, we also
have an alternative statement involving ⇒∗ exclusively, but it takes the less symmetric form

(5.14)

a ⇒∗ 1 · ec,
If we have 1 · e
a ⇒∗ 1 · eb and 1 · e
there exists d satisfying b ⇒∗ d and c ⇒∗ d,

because the e operation is not involutive in this case.

e ± and that of their positive
Using duality, we obtain for the cross-confluences of R± and R
versions the same connection as in the case of convergence and semi-convergence:
Proposition 5.15. For every gcd-monoid M , the following are equivalent:
±
(i) The system RM
is cross-confluent;
±
eM
(ii) The system R
is cross-confluent;
eM are cross-confluent.
(iii) The systems RM and R

±
Proof. Assume that RM
is cross-confluent. Applying (5.10) to e
a, eb, and ec and using (5.4), we
±
e
deduce (5.11), so RM is also cross-confluent. Doing the same from (5.11) returns to (5.10). So
(i) and (ii) are equivalent.
±
e
Next, all R- and R-reducts
of a positive multifraction are positive, so, if RM
is cross±
e
confluent, its retriction to FM is also cross-confluent. Similarly, if RM is cross-confluent, its
eM
retriction to FM is cross-confluent. Hence (i) implies (iii). Finally, assume that RM and R
∗
∗
±
are cross-confluent, and a, b, c belong to FM and satisfy a ⇒
e b and a ⇒
e c. If a, hence b
and c as well, are positive, the assumption that RM is cross-confluent implies the existence of d
satisfying (5.10). Assume now that a, hence b and c, are negative. Then e
a, eb, ec are positive, and
∗ e
∗
eM is cross-confluent implies the existence
we have e
a ⇒ b and e
a ⇒ ec. The assumption that R
of d satisfying eb ⇒
e ∗ d and ec ⇒
e ∗ d. By (5.4), we deduce b ⇒∗ e
d and c ⇒∗ e
d. So (5.10) holds,
±
RM is cross-confluent, and (iii) implies (i).


In view of our main purpose, namely establishing the semi-convergence of (left) reduction,
the main result is the following connection, which locates cross-confluence as an intermediate
between convergence and semi-convergence:
Proposition 5.16. Assume that M is a noetherian gcd-monoid.
±
±
(i) If RM
is convergent, then RM
is cross-confluent.
±
±
(ii) If RM is cross-confluent, then RM
is semi-convergent.
(iii) Mutatis mutandis, the same implications hold for RM .
We begin with an auxiliary result:

Lemma 5.17. Assume that M is a gcd-monoid.
±
e ∗ 1 are
is cross-confluent, then, for every a in FM± , the relations a ⇒∗ 1 and a ⇒
(i) If RM
equivalent.
(ii) If RM is cross-confluent, then, for every a in FM , the relation a ⇒
e ∗ 1 implies a ⇒∗ 1.

±
implies
Proof. (i) Assume a ∈ FM± and a ⇒∗ 1. By Proposition 5.15, the cross-confluence of RM
±
∗
eM . By definition, we also have a ⇒ a. Then (5.11) implies the existence of d satisfying
that of R
e
e ∗ d and a ⇒
e ∗ d. By definition, 1 is R-irreducible,
so 1 ⇒
e ∗ d implies d = 1, whence a ⇒
e ∗ 1.
1 ⇒
∗
∗
Conversely, assume a ⇒
e 1. We have a ⇒
e a, and (5.10) implies the existence of d satisfying
a ⇒∗ d and 1 ⇒∗ d, whence d = 1, and a ⇒∗ 1.
(ii) When a lies in FM , the latter argument remains valid, and it shows again that a ⇒
e∗ 1
∗
implies a ⇒ 1. (By contrast, the former argument need not extend, as there is a priori no
eM .)
reason why the cross-confluence of RM should imply that of R


Proof of Proposition 5.16. (i) Let a belong to FM± , and assume a ⇒
e ∗ b and a ⇒
e ∗ c. By
±
±
∗
∗
Lemma 5.5, we have a ≃ b ≃ c, whence b ⇒ d and c ⇒ d, where d is the (unique)
R-irreducible reduct of a. Hence (5.10) is satisfied.

MULTIFRACTION REDUCTION II

25

±
(ii) Assume that RM
is cross-confluent, and we have a ⇒∗ 1 and a ⇒∗ b for some a in FM± .
±
By (5.11), which is valid since, by Proposition 5.15, the cross-confluence of RM
implies that
±
∗
∗
eM , there exists d satisfying b ⇒
e
of R
e d and 1 ⇒
e d. Since 1 is R-irreducible,
we must have
±
e ∗ 1. By Lemma 5.17, we deduce b ⇒∗ 1. Hence RM
is 1-confluent and,
d = 1, whence b ⇒
therefore, by Proposition 3.29, it is semi-convergent.
(iii) For (i), the argument is the same in the case a ∈ FM . For (ii), assume that RM is
cross-confluent, and we have a ⇒∗ 1 and a ⇒∗ b for some a in FM . By Lemma 5.5(iv), we have
1·e
a ⇒
e ∗ 1 · 1 = 1 and 1 · a ⇒
e ∗ 1 · b, and 1 · e
a is positive. As RM is cross-confluent, we deduce the
∗
e
existence of d satisfying 1 ⇒ d and 1 · b ⇒∗ d. As 1 is R-irreducible, we have d = 1, whence
1 · eb ⇒∗ 1, and, by Lemma 5.5(iv) again, b ⇒
e ∗ 1. By Lemma 5.17(ii), we deduce b ⇒∗ 1. Hence
RM is 1-confluent and, by Proposition 3.29, it is semi-convergent.


5.3. Conjectures C and Cunif . We thus arrive at what we think is the main conjecture in
this paper:
Conjecture C. For every Artin-Tits monoid M , the system RM is cross-confluent.

By Proposition 5.16, Conjecture C implies Conjecture A, whence the decidability of the
word problem of the group, and it is true for every Artin–Tits monoid of type FC. Note that
Conjecture C is different from Conjectures A and B in that it predicts something for all
multifractions, not only for unital ones. So, in a sense, it is a more structural property, which
we think is interesting independently of any application.
No proof of Conjecture C is in view so far in the general case, but we now observe that local
cross-confluence, namely cross-confluence with single reduction steps on the left, is always true.
Proposition 5.18. If M is a gcd-monoid, then, for all a, b, c in FM± ,
(5.19)
(5.20)

If we have a ⇒
e b and a ⇒
e c, there exists d satisfying b ⇒∗ d and c ⇒∗ d.
If we have a ⇒ b and a ⇒ c, there exists d satisfying b ⇒
e ∗ d and c ⇒
e ∗ d.

The proof relies on the following preparatory result:

Lemma 5.21. Assume that M is a gcd-monoid and a is a multifraction on M such that a • Ri,x
b be defined by ai x′ = ai ∨ x and
is defined. If i is negative (resp., positive) in a, let x′ and x
′
e
e
x
b = ai ∧ x (resp., x ai = ai ∨ x and x
b = ai ∧ x). Then, we have
ei,x′ = a • Di,bx .
(5.22)
a • Ri,x R
Proof. (Figure 5) Let a′ = a • Ri,x . Assuming i negative in a, we have

(5.23)

a′i−1 = ai−1 x′ ,

xa′i = ai x′ = ai ∨ x,

xa′i+1 = ai+1 .

By construction, x′ right divides a′i−1 , and x′ and a′i admit a common left multiple, namely ai x′ .
ei,x′ is defined, and it is determined by
Hence a′′ = a′ • R
(5.24)

a′′i−1 x′ = a′i−1 ,

e x′ ,
a′′i x′ = x′′ a′i = a′i ∨

a′′i+1 = x′′ a′i+1 .

By definition, the left lcm x′′ a′i of x′ and a′i left divides their common left multiple xa′i , which
implies the existence of x
b satisfying x = x
bx′′ , and, from there, ai x′ = xa′i = x
bx′′ a′i = x
ba′′i x′ ,
′′
′′
′′
ba′′i+1 =
bai = ai , and x
whence ai = x
bai . Merging (5.23) and (5.24), we deduce ai−1 = ai−1 , x
′′
ai+1 , which shows that a is obtained from a by left dividing the ith and (i + 1)st entries by x
b,
i.e., by applying the division Di,bx .

The argument is symmetric when i is positive in a.
ei,x is defined, a symmetric argument gives
When a • R

(5.25)

ei,x Ri,x′ = a • Di−1,bx ,
a•R

e x and x
e x (resp., ai x′ = ai ∨ x and
where x′ and x
b are now defined by x′ ai = ai ∨
b = ai ∧
x
b = ai ∧ x) if i is negative (resp., positive) in a. The index of the division is shifted (i − 1
ei+1,x .
instead of i) relatively to (5.22), because, as a set of pairs, Di,x is included in R
We can now complete the argument for Proposition 5.18.

26

PATRICK DEHORNOY

ai

ai−1
x′
a′i−1

a′′i

x
b

x′′
a′i

ai+1
x
a′i+1

ei,x′
Figure 5. Composing the left reduction Ri,x and the inverse right reduction R
amounts to performing the division Di,bx where x
b is the gcd of ai and x.

ei,x and c = a • R
ej,y . By Lemma 5.21, we have
Proof of Proposition 5.18. Assume b = a • R
b • Ri,x′ = a • Di,bx

and c′ • Rj,y′ = a • Dj,by

for some x′ , x
b and y ′ , yb. By Proposition 4.4, ∂a is a common reduct of all multifractions obtained
from a by a division, hence in particular of a • Di,x′′ and a • Dj,y′′ . Thus b ⇒∗ ∂a and c ⇒∗ ∂b
hold, hence (5.19) is satisfied with d = ∂a.

The proof of (5.20) is symmetric, using (5.25) instead of (5.22), and d = ∂a again.

In the case of a single rewrite system, local confluence implies confluence whenever the system
is terminating (by Berman’s well known diamond lemma). There is no hope of a similar result
e is not terminating in general—see (5.30) below—and
here, both because the union of R and R
because, in the definition of cross-confluence, the arrows ⇒ and ⇒
e are not in a position for a
natural induction.

Remark 5.26. Right reduction is close to being an inverse of left reduction. Indeed, provided
the ground monoid is noetherian, every reduction is a product of atomic reductions, namely
ei,x with x an atom. Now, if x is an atom, the gcd of x and ai
reductions of the form Ri,x or R
is either ai , meaning that x divides ai , or 1. In the former case, a • Ri,x is a • Di,x , whereas,
ei,x′ , i.e., left reducing x in a is the inverse
in the latter, Lemma 5.21 implies a = (a • Ri,x ) • R
′
of right reducing x . Thus, writing D for the family of divisions and Rat for that of atomic left
−1
e is generated by D ∪ Rat
reductions, R is generated by D ∪ Rat , whereas R
. By Lemma 4.7 and
the results of [13], confluence between D and Rat is always true, whereas confluence between Rat
−1
and Rat
is trivial. Therefore, one might hope that cross-confluence diagrams can always be
constructed by assembling the various types of elementary confluence diamonds. This is not
true: using a tedious case-by-case argument, one can indeed establish cross-confluence in the
case when, in (5.10), b and c are obtained from a by two atomic reduction steps, but there is no
hope to go very far in this direction, both because of the counter-examples of Example 5.27, and
because, in any case, cross-confluence cannot be true for an arbitrary noetherian gcd-monoid,
since there exist such monoids for which the counterparts of Conjectures A and C fail [19]:
if true, cross-confluence has to be a specific property of Artin–Tits monoids, or at least of a
restricted family of gcd-monoids.
The following examples are given to show that naive attempts to extend the local crossconfluence result of Proposition 5.18 are due to fail.
Example 5.27. Proposition 5.18 shows that, if b is obtained by applying one right reductions
to a, then applying one well chosen left reduction to b provides a multifraction c obtained by
one division from a. The result fails when 1 is replaced by k > 2. Indeed, in the Artin-Tits
e5,b = 1/1/ca/cb/1, (which is
e3,a R
e 2 , consider a = 1/a/ca/cb/b and b = a • R
monoid of type A
e
R-irreducible).
The only way to left reduce b is to start with R1,ca , leading to c = ca/1/cb/1,
not reachable from a by two, or any number, of divisions.
In the above case, we have c = a • R4,b R2,cac , and therefore there is no contradiction with the
weaker conclusion that c is obtained both from a by applying k left reductions. The following
example (with k = 3) shows that this is not true either. Indeed, consider a = ca/cb/bc/ba and
e4,a = 1/1/ac/ab. As predicted by Conjecture C, a and b admit common left
e2,ca R
e3,bc R
b = a•R
reducts, but the latter are c and c • D2,c , with c = ac/cab/c/1 = a • R2,b R3,a D2,a R3,b D1,aa D2,b ,
not reachable from a using less than six left reductions. What is surprising here is that, if we

MULTIFRACTION REDUCTION II

27

e2,ca = 1/1/aca/aba, then b′ left reduces to a, whereas b = b′ • D3,a only left
e3,bc R
put b′ := a • R
reduces to c, very far from a: one single division may change left reducts completely.

We conclude with one more conjecture. The conjunction of Propositions 4.4 and 5.18 shows
not only that any two right reducts b, c of a multifraction a admit a common left reduct d, but
even that there exists d only depending on a, namely ∂a, that witnesses for all elementary right
reducts of a simultaneously. This suggests to consider a strong version of cross-confluence:
Definition 5.28. If M is a gcd-monoid, we say that RM is uniformly cross-confluent if there
exists a map ∇ from FM to itself such that, for every a in FM , the relation b ⇒∗ ∇a holds for
every right reduct b of a.
In the case when reduction is convergent, defining ∇a = red(a) provides a convenient witness, and therefore the conclusion of Proposition 5.16 can be strengthened to uniform crossconfluence. We propose:
Conjecture Cunif . For every Artin-Tits monoid M , the system RM is uniformly cross-confluent.

By the above observation, Conjecture Cunif is true for every Artin–Tits monoid of type FC,
and no counter-example could be found so far in any other type. It implies Conjecture C and,
therefore, Conjecture A, but it is more demanding. However, if an explicit definition of ∇a
could be found, one can reasonably hope that the proof of Conjecture Cunif would then reduce
to a series of verifications. But, here again, naive attempts fail: two natural candidates for ∇a
could be either redt (a) (which works in the convergent case), or (if it always exists) a maximal
common ancestor of all irreducible reducts in the tree of all left reducts of a, but the example
of Figure 6 shows that neither of these choices works in every case.
Appendix: Mixed termination. Although it is not directly connected with cross-confluence,
we mention here one further result involving both left and right reduction. First, we know
that, in a noetherian context, (left) reduction is terminating, meaning that there is no infinite
sequence of reductions. It turns out that a stronger finiteness result holds:
Proposition 5.29. If M is a finitely generated noetherian gcd-monoid, then every multifraction a on M admits only finitely many left reducts, and finitely many right reducts.
Proof. As M is noetherian and contains no nontrivial invertible element, a subfamily of M
is generating if and only if it contains all atoms. Hence, the assumption that M is finitely
generated implies that the atom set A of M is finite. Let a belong to FM± . We construct a
tree Ta , whose nodes are pairs (b, s), where b is a left reduct of a and s is a finite sequence
in A × N: the root of Ta is (a, ε), and, using ⌢ for concatenation, the sons of (b, s) are all
pairs (b • Ri,x , s⌢ (i, x)) such that b • Ri,x is defined. As A is finite, for every multifraction b,
the number of pairs (i, x) with x in A and b • Ri,x defined is finite. Hence each node in Ta has
finitely many immediate successors. On the other hand, the assumption that M is noetherian
±
implies that RM
is terminating and, therefore, the tree Ta has no infinite branch. Hence, by
König’s lemma, Ta is finite. As every left reduct of a appears (maybe more than once) in Ta ,
the number of such reducts is finite.
The argument for right reducts is symmetric.

Thus, it makes sense to wonder whether, starting from a multifraction a, the family of
all multifractions that can be obtained from a using left and right reduction is finite. The
argument for Proposition 5.29 does not extend, because the well-orders witnessing for the
termination of left and right reductions are not the same, and it is easy to see that the result
e 2 , we find
itself fails in general: starting from a := 1/a/bc/1 in the Artin-Tits of type A
e
a • R2,b R3,a = ba/b/ca/ac, whence, repeating three times,
(5.30)

e3,c = bacbac/a/bc/acbacb = bacbac · a · acbacb.
e3,b R2,a R
e3,a R2,c R
a • R2,b R

e3,c )p make for p > 0 an infinite none3,b R2,a R
e3,a R2,c R
Hence the multifractions a • (R2,b R
e
terminating (and non-periodic) sequence with respect to R ∪ R.

28

PATRICK DEHORNOY

a9 : /cbac/bcbb/aca

R2,bc

a12 : /ac/caba/acaab
D3,b
D3,c

e2,a
R

R2,ca
e2,a
R

D2,c
a13 : /ac/cba/acaa

a11 : a/c/ba/acaab

a1 : a/bac/bb/aca

D3,a

a10 : /bac/bcb/aca D
2,b

e3,a
R
a14 : /ac/cb/aca

R3,ab
D2,b
R3,c

e2,a
R

R2,c

R3,a
a2 : a/ac/b/aca

D3,c
e3,b
R

R3,c

R3,c

a3 : a/bcbac/ccb/ca

D1,a
a4 : a/babac/aab/ac

D2,c
a5 : /cbac/ccb/ca
a6 : a/bcac/cb/ca
D2,c
a7 : /bac/cb/ca

D1,a

R3,a
D2,a

a8 : a/baac/ab/ac

Figure 6. Left and right reducts of a1 := a/bac/bb/aca in the Artin-Tits monoid of
e 2 : there are 8 left reducts (in grey), among which a7 and a8 are R-irreducible,
type A
e
and 10 right reducts (dashed lines), among which a14 is R-irreducible.
Plain (resp.,
dashed) arrows correspond to left (resp., right) reductions that are not divisions,
double arrows correspond to divisions (which are both left and right reductions); all
left reductions decrease the distance to the bottom. As Conjecture Cunif predicts,
there exists a common left reduct for all right reducts: in this case, there is only one,
namely a7 , and it is neither redt (a1 ) nor the maximal common ancestor of a7 and a8 ,
both equal to a2 .

By contrast, let us mention without detailed proof a finiteness result valid whenever the
ground monoid M is a Garside monoid [11, 16], i.e., a strongly noetherian gcd-monoid possessing
in addition an element ∆ (“Garside element”) whose left and right divisors coincide, generate M ,
and are finite in number.
Proposition 5.31. If M is a Garside monoid, then, for every multifraction a on M , the family
e
of all (R ∪ R)-reducts
of a is finite.

Proof (sketch). Let ∆ be a Garside element in M and let a be a multifraction on M . Then
there exists a positive integer d such that the path associated with a can be drawn in the finite
fragment of the Cayley graph of M made of the divisors of ∆d : this is the notion of a path “drawn
in Div(∆d )” as considered in [10]. Then the family of all paths drawn in Div(∆d ) is closed under
the special transformations alluded to in Subsection 3.3, and, therefore, all multifractions that
e are drawn in the same finite fragment Div(∆d ) of the
can be derived from a using ⇒ and ⇒
Cayley graph. As we consider multifractions with a fixed depth, only finitely many of them can
be drawn in a finite fragment of a Cayley graph.

The argument extends to every Artin-Tits monoid M of type FC, replacing the finite family
of divisors of the Garside element ∆ with the union of the finitely many finite families of divisors
of the Garside elements ∆I , where I is a family of atoms of M that generates a spherical type
submonoid of M .

MULTIFRACTION REDUCTION II

29

6. Finite approximations
±

The semi-convergence of RM and Conjectures A, B, and C, involve multifractions of arbitrary depth. Further results appear in the particular case of small depth multifractions. The
cases of depth 2 and, more interestingly, of depth 4 are addressed in Subsections 6.1 and 6.2,
where connections with the embeddability in the group and the uniqueness of fractional decompositions, respectively, are established. An application of the latter to partial orderings of
the group is established in Subsection 6.3. Finally, we describe in Subsection 6.4 a connection
between Conjecture B and van Kampen diagrams for unital n-multifractions.
±
6.1. The n-semi-convergence property. The rewrite system RM
has been called semiconvergent if (3.4) holds for every multifraction on M , i.e., if a being unital implies a ⇒∗ 1.
±
Definition 6.1. If M is a gcd-monoid, we say that RM
(resp., RM ) is n-semi-convergent if (3.4)
±
holds for every n-multifraction a in FM (resp., FM ).

Accordingly, we shall use Conjecture An for the restriction of Conjecture A to depth n
±
multifractions, and similarly for B and C. Some easy connections exist. Of course, if RM
is
n-semi-convergent, then so is its subsystem RM .
±
Lemma 6.2. If M is a gcd-monoid and RM
(resp., RM ) is n-semi-convergent, it is p-semiconvergent for p < n.

Proof. Let a be a nontrivial unital p-multifraction, with p < n. There exists r (equal to n − p
±
or n − p + 1) such that a · 1r has width n, and it is also nontrivial and unital. As RM
is
±
∗
∗
is
n-semi-convergent, we have a · 1r ⇒ 1, which implies a ⇒ 1 by Lemma 2.17(iii). So RM
p-semi-convergent.

On the other hand, by repeating the proof of Proposition 3.22, we obtain
±
Lemma 6.3. If M is a noetherian gcd-monoid, then RM
(resp., RM ) is n-semi-convergent if
and only if (3.23) holds for every n-multifraction a in FM± (resp., FM ), i.e., if a is unital, then
it is either trivial or reducible.

We now address the cases of small depth. The case of depth one is essentially trivial, in
that it follows from a sufficiently strong form of noetherinity and does not really involve the
algebraic properties of the monoid:
Proposition 6.4. Assume that M is a gcd-monoid that admits a length function, namely a
map λ : M → N satisfying, for all a, b in M ,
(6.5)

λ(ab) = λ(a) + λ(b),

and

λ(a) > 0 for a 6= 1.

±

Then the system RM is 1-semi-convergent.
Condition (6.5) is strong noetherianity (3.13) with > replaced by =. It holds in every ArtinTits monoid and, more generally, in every monoid with a homogeneous presentation.
P
P
Proof. Extend the map λ to FM± by λ(a) := i positive in a λ(ai ) − i negative in a λ(ai ). Then λ
is a homomorphism from the monoid FM± to (N, +), and, for every a in M , we have λ(a/a) =
λ(/a/a) = λ(1) = λ(∅) = 0. By Proposition 2.5, the latter pairs generate ≃± as a congruence,
hence λ is invariant under ≃± . Then a 6= 1 implies λ(a) 6= λ(1), whence a 6≃± 1. Hence the only
±
unital 1-multifraction is 1, and RM
is 1-semi-convergent.

The cases of depths 2 and 3 turn out to be directly connected with the embeddability of the
considered monoid in its enveloping group.
Proposition 6.6. If M is a gcd-monoid, the following are equivalent:
(i) The system RM is 2-semi-convergent.
±
(ii) The system RM
is 2-semi-convergent.
±
is 3-semi-convergent.
(iii) The system RM
(iv) The monoid M embeds in U(M ).

30

PATRICK DEHORNOY

Proof. Assume that RM is 2-semi-convergent. Let a, b two elements of M satisfying ι(a) = ι(b).
By (2.6), we have a/b ≃± 1. The assumption that RM is 2-semi-convergent implies a/b ⇒∗ 1.
By definition, this means that there exists x in M satisfying a = x = b, whence a = b. So M
embeds in U(M ). Hence (i) implies (iv).
Clearly (ii) implies (i), and (iii) implies (ii) by Lemma 6.2.
Finally, assume that M embeds in U(M ), and let a be a positive nontrivial unital 3multifraction. By assumption, we have a ≃± 1, whence ι(a1 )ι(a2 )−1 ι(a3 ) = 1 in U(M ) by (2.6),
and, therefore, ι(a2 ) = ι(a3 )ι(a1 ) = ι(a3 a1 ) in U(M ). As M embeds in U(M ), this implies
a2 = a3 a1 in M . Then a has the form a1 /a3 a1 /a3 , implying a • D1,a1 D2,a3 = 1/1/1. Thus
RM is 3-semi-convergent. The argument is the same for a negative 3-multifraction a, finding
±
is
now ι(a1 )−1 ι(a2 )ι(a3 )−1 = 1, whence a2 = a1 a3 , and a • D1,a1 D2,a3 = /1/1/1. Hence RM
3-semi-convergent. So (iv) implies (iii).

±
Corollary 6.7. For every Artin-Tits monoid M , the system RM
is n-semi-convergent for
n 6 3.
±
Proof. By Lemma 6.2, RM
is 1-semi-convergent. Next, it is known [28] that M embeds
±
into U(M ). Hence, by Proposition 6.6, RM
is 2- and 3-semi-convergent.


In other words, Conjecture An is true for n 6 3.
6.2. Multifractions of depth 4. We now address 4-semi-convergence, which turns out to give
rise to interesting phenomena. We begin with preliminary results about unital multifractions
that are in some sense the simplest ones.
Definition 6.8. If M is a monoid and a is an n-multifraction on M ,
with n even, we say that (x1 , ..., xn ) is a central cross for a if we have
(
xi xi+1 for i positive in a,
ai =
xi+1 xi for i negative in a,

a2

a3

x2
x1

x3
x4

a1
a4
with the convention xn+1 = x1 .
The diagram of Definition 6.8 shows that a multifraction that admits a central cross is unital:
if (x1 , ..., xn ) is a central cross for a positive multifraction a, we find
ι(a) = ι(x1 x2 ) ι(x3 x2 )−1 ι(x3 x4 ) ··· (x1 xn )−1 = 1,

and similarly when a is negative. It follows from the definition that a sequence (x1 , ..., xn )
is a central cross for a positive multifraction a if and only if (x2 , ..., xn , x1 ) is a central cross
for /a2 /···/an /a1 . So, we immediately obtain
Lemma 6.9. For every monoid M and every even n, a positive n-multifraction a admits a
central cross if and only if the negative multifraction /a2 /···/an /a1 does.
Multifractions with a central cross always behave nicely in terms of reduction:
Lemma 6.10. If M is a gcd-monoid and a is a multifraction on M that admits a central cross,
then redt (a) = 1 holds.
Proof. We prove the result using induction on n > 2 even, and assuming a positive. Assume
that (x1 , ..., xn ) is a central cross for a. For n = 2, the assumption boils down to a1 = a2 = x1 x2 ,
e x3 , with
directly implying a • R1max = 1/1. Assume n > 4 and, say, a positive. Let x := x1 ∧
e a2 = xx2 , whence a • R1max = x′1 /x′3 /a3 /···/an . As
x1 = x′1 x and x3 = x′3 x. Then we have a1 ∧
a3 = x3 x4 expands into a3 = x′3 xx4 , this can be rewritten as a • R1max = x′1 /x′3 /x′3 xx4 /···/an .
We deduce
(6.11)

a • R1max R2max = x′1 xx4 /1/1/a4/···/an = x1 x4 /1/1/a4/···/an

with a4 = x1 x4 for n = 4, and a4 = x5 x4 for n > 6. In every case, the subsequent action
max
of R3max ···Rn−1
is to push a4 , then a5 , etc. until an , through 1/1, leading to
(6.12)

max
a • R1max ···Rn−1
= x1 x4 /a4 /···/an /1/1.

MULTIFRACTION REDUCTION II

31

For n = 4, (6.12) reads a • R1max R2max R3max = x1 x4 /x1 x4 /1/1, and a further application of R1max
yields 1. For n > 6, the assumption that (x1 , ..., xn ) is a central cross for a implies that
(x1 , x4 , ..., xn ) is a central cross for the (n − 2)-multifraction x1 x4 /a4 /···/an . The induction
hypothesis for the latter gives redt (x1 x4 /a4 /···/an ) = 1, which expands into
max
= 1n−2 .
x1 x4 /a4 /···/an • RU(n−2)

(6.13)

max
By Lemma 2.17(iii), (6.13) implies x1 x4 /a4 /···/an /1/1 • RU(n−2)
= 1n . Merging with (6.12),
max
max
max
we deduce a • R1 ··· n−1 RU(n−2) = 1n , which is a • RU(n) = 1n , i.e., redt (a) = 1.
The argument is similar when a is negative.


We now concentrate on 4-multifractions. A sort of transitivity of central crosses holds.
Lemma 6.14. Assume that M is a gcd-monoid, a, b are 4-multifractions admitting a central
cross, and c1 a4 = c4 b1 and c2 a3 = c3 b2 holds. Then c1 a1 /c2 a2 /c3 b3 /c4 b4 admits a central cross.
In particular, a1 /a2 /b3 /b4 admits a central cross for a4 = b1 and a3 = b2 .
Proof. (Figure 7) Let (x1 , ..., x4 ) and (y1 , ..., y4 ) be central crosses for a and b, respectively.
By assumption, we have c2 x3 x4 = c2 a3 = c3 b2 = c3 y3 y2 , so x4 and y2 admit a common left
e y2 = xx4 = yy2 , and there exists z3 satisfying c2 a3 = z3 xx4 = z3 yy2 = c3 b2 .
multiple, say x4 ∨
Then a3 = x3 x4 and b2 = y3 y2 respectively imply
(6.15)

c2 x3 = z3 x

and

c3 y3 = z3 y.

Arguing similarly from c1 x1 x4 = c1 a4 = c4 b1 = c4 y1 y2 , we deduce the existence of z1 satisfying
c1 a4 = z1 xx4 = z1 yy2 = c4 b1 , leading to
(6.16)

c1 x1 = z1 x

and

c4 y1 = z1 y.

Then (z1 , xx2 , z3 , yy4 ) is a central cross for c1 a1 /c2 a2 /c3 b3 /c4 b4 .
c2
a2

a3

x3
x

x2

x4

c3
z3

b2
y2

x
a1

x1



y

y3

b3
y4

y
a4

z1 b1

y1

b4

c1
c4
Figure 7. Transitivity of the existence of a central cross.
We deduce that reduction preserves the existence of a central cross in both directions.
Lemma 6.17. Assume that M is a gcd-monoid and a, b are 4-multifractions on M satisfying
a ⇒∗ b. Then a admits a central cross if and only if b does.
Proof. It is enough to prove the result for a ⇒ b, say b = a • Ri,x . Assume that a is positive
and (x1 , ..., x4 ) is a central cross for a. Our aim is to construct a central cross for b from that
for a. Consider the case i = 2, see Figure 8. Let a2 x′ = x ∨ a2 . By definition, we have
(6.18)

b1 = a1 x′ ,

xb2 = a2 x′ ,

xb3 = a3 ,

b 4 = a4 .

By assumption, x and x3 admit a common right multiple, namely a3 , hence they admit a right
lcm, say x ∨ x3 = xy3 = x3 y. We have xb2 = a2 x′ = x3 (x2 x′ ), hence the right lcm of x and x3
left divides xb2 , i.e., we have xy3 6 xb2 , whence y3 6 b2 , say b2 = y3 y2 .
Next, we have x3 x2 x′ = a2 x′ = xb2 = xy3 y2 = x3 yy2 , whence x2 x′ = yy2 by left cancelling x3 . Put y1 = x1 y. We find b1 = a1 x′ = x1 x2 x′ = x1 yy2 = y1 y2 .

32

PATRICK DEHORNOY

On the other hand, by assumption, as both x and x3 left divide a3 , their right lcm x3 y left
divide a3 , which is x3 x4 . So we have x3 y 6 x3 x4 , whence y 6 y4 , say x4 = yy4 . Then we find
xb3 = a3 = x3 x4 = x3 yy4 = xy3 y4 , whence b3 = y3 y4 .
Finally, we have b4 = a4 = x1 x4 = x1 yy4 = y1 y4 . So (y1 , ..., y4 ) is a central cross for b.
The argument for i = 3 is similar, mutatis mutandis, and so is the one for i = 1: in this case,
the counterpart of x′ is trivial, which changes nothing. Finally, the case when a is negative is
treated symmetrically. So b admits a central cross whenever a does.
For the other direction, assume again that a and b are positive, and that (y1 , ..., y4 ) is a
central cross for b. Assume again i = 2, and (6.18). The equality xb2 = a2 x implies that
(a1 , 1, a2 , x′ ) is a central cross for a1 /a2 /xb2 /b1 . On the other hand, (y1 , y2 , xy3 , y4 ) is a central
cross for b1 /xb2 /a3 /a4 . So both a1 /a2 /xb2 /b1 and b1 /xb2 /a3 /a4 admit a central cross. By
Lemma 6.14, this implies that a1 /a2 /a3 /a4 admits a central cross. So a admits a central cross
whenever b does.

The above proof does not use the assumption that xb2 is the lcm of x and a2 , but only
the fact that the equalities of (6.18) hold for some x, x′ , which is the case, in particular, for
ei,x′ . So it also shows that every right reduct of a 4-multifraction with a central cross
b = a•R
admits a central cross, and conversely.
a2

a3

x

x3
b2

b3
y3 x4

x2
x′

y
a1

y2
b1 x
1

y4
y1

a4 = b 4

Figure 8. Construction of a central cross for a • Ri,x starting from one for a.
We deduce a complete description of the 4-multifractions that reduce to 1:
Proposition 6.19. If M is a gcd-monoid, then, for every 4-multifraction a on M , the following
are equivalent:
(i) The relation a ⇒∗ 1 holds.
(ii) The relation redt (a) = 1 holds.
(iii) The multifraction a admits a central cross.
Proof. The 4-multifractions 1/1/1/1 and /1/1/1/1 both admit the central cross (1, 1, 1, 1).
Hence, by Lemma 6.17, every 4-multifraction satisfying a ⇒∗ 1/1/1/1 or a ⇒∗ /1/1/1/1 admits
a central cross as well. Hence (i) implies (iii).
Next, Lemma 6.10 says that redt (a) = 1 holds for every multifraction a that admits a central
cross, so (iii) implies (ii).
Finally, (ii) implies (i) by definition.

±
We return to the study of n-semi-convergence for RM
, here for n = 4, 5.

Proposition 6.20. If M is a gcd-monoid, the following are equivalent:
(i) The system RM is 4-semi-convergent.
±
(ii) The system RM
is 4-semi-convergent.
±
(iii) The system RM
is 5-semi-convergent.
(iv) Every unital 4-multifraction in FM admits a central cross.

MULTIFRACTION REDUCTION II

33

Proof. Assume that RM is 4-semi-convergent. Let a be a unital positive 4-multifraction. As
RM is 4-semi-convergent, we have a ⇒∗ 1. By Proposition 6.19, we deduce that a admits a
central cross. Hence (i) implies (iv).
By definition, (ii) implies (i), and, by Lemma 6.2, (iii) implies (ii).
Finally, assume (iv), and let a be a unital 5-multifraction on M . Assume first that a is
positive. Then the positive 4-multifraction a5 a1 /a2 /a3 /a4 is unital as well, hence, by assumption, it admits a central cross (x1 , ..., x4 ), which expands into a = a1 /x3 x2 /x3 x4 /x1 x4 /a5 with
a5 a1 = x1 x2 . Then we obtain
a ⇒∗ a1 /x2 /1/x1 /a5

via D2,x3 D3,x4

∗

via R3,x1 R4,a5

∗

via D1,a1 D2,a5 .

⇒ a1 /x1 x2 /a5 /1/1 = a1 /a5 a1 /a5 /1/1
⇒ 1/1/1/1/1

If a is negative, then a2 /a3 /a4 /a1 a5 is unital and positive, hence admits a central cross by
assumption, leading to a = /a1 /x1 x2 /x3 x2 /x3 x4 /a5 with a1 a5 = x1 x4 , and to a ⇒∗ 1, this
time via D2,x2 D3,x3 R3,x4 R4,a5 D1,a1 D2,a5 . Thus, every unital 5-multifraction on M reduces
±
is 5-semi-convergent. So (iv) implies (iii).

to 1, and RM
We now establish alternative forms for the point (iv) in Proposition 6.20, connected with the
uniqueness of the expression by irreducible fractions.
Proposition 6.21. For every gcd-monoid M , the following are equivalent:
(i) Every unital 4-multifraction in FM admits a central cross.
(ii) For all a, b, c, d in M satisfying ι(a/b) = ι(c/d), there exist x, y in M satisfying
(6.22)

e b),
a = x(a ∧

e b),
b = y(a ∧

e d),
c = x(c ∧

e d).
d = y(c ∧

e b = 1 satisfy a 6 c and b 6 d.
(iii) All a, b, c, d in M satisfying ι(a/b) = ι(c/d) and a ∧
e b = c∧
e d = 1 satisfy a = c and b = d.
(iv) All a, b, c, d in M satisfying ι(a/b) = ι(c/d) and a ∧
e b = b ∧ c = 1 and ι(a/b/c) ∈ ι(M ) satisfy b = 1.
(v) All a, b, c in M satisfying a ∧

Before establishing Proposition 6.21, we begin with two characterizations of 4-multifractions
with a central cross:
Lemma 6.23. If M is a gcd-monoid, a positive 4-multifraction a on M admits a central cross
if and only if there exist x, y in M satisfying
(6.24)

e a2 ),
a1 = x(a1 ∧
′

′

e a2 ),
a2 = y(a1 ∧

if and only if there exist x , y in M satisfying
(6.25)

e a4 )x′ ,
a1 = (a1 ∧

e a3 )x′ ,
a2 = (a2 ∧

e a4 ),
a3 = y(a3 ∧

e a3 )y ′ ,
a3 = (a2 ∧

e a4 ),
a4 = x(a3 ∧

e a4 )y ′ .
a4 = (a1 ∧

e x3 )
Proof. Assume that a is positive and (x1 , ..., x4 ) is a central cross for a. Write x1 = x(x1 ∧
e x3 ). Then we have x ∧
e y = 1, and a1 = x(x1 ∧
e x3 )x2 , a2 = y(x1 ∧
e x3 )x2 ,
and x3 = y(x1 ∧
e a2 = (x1 ∧
e x3 )x2 , and a1 = x(a1 ∧
e a2 ), a2 = y(a1 ∧
e a2 ). On the other hand, we
whence a1 ∧
e x3 )x4 , a4 = x1 x4 = x(x1 ∧
e x3 )x4 , whence a3 ∧
e a4 = (x1 ∧
e x3 )x4 ,
also find a3 = x3 x4 = y(x1 ∧
e a4 ), d = x(a3 ∧
e a4 ). So we found x, y satisfying (6.24).
and a3 = y(a3 ∧
The proof for (6.25) is similar, writing x2 = (x2 ∧ x4 )x′ and x4 = (x2 ∧ x4 )y ′ and deducing
a1 ∧ a4 = x1 (x2 ∧ x4 ) and a2 ∧ a3 = x3 (x2 ∧ x4 ).
e a2 , y, a3 ∧
e a4 ) is a central cross for a,
In the other direction, if (6.24) is satisfied, (x, a1 ∧
whereas, if (6.25) is satisfied, so is (a1 ∧ a4 , x′ , a2 ∧ a3 , y).


Proof of Proposition 6.21. If ι(a/b) = ι(c/d) holds, the 4-multifraction a/b/d/c is unital, hence
it admits a central cross if (i) is true. In this case, Lemma 6.23 gives (6.22). So (i) implies (ii).
e b = 1 gives a = x and b = y, whence a 6 c and b 6 d. If,
Next, applying (ii) in the case a ∧
e d = 1, we similarly obtain c 6 a and d 6 b, whence a = c and b = d. So
in addition, we have c ∧
(ii) implies (iii) and (iv). On the other hand, (iv) implies (iii). Indeed, assume ι(a/b) = ι(c/d)
e b = 1. Let e = c ∧
e d, with c = c′ e and c = d′ e. Then we have c′ ∧
e d′ = 1 and
with a ∧
′
′
′
′
ι(a/b) = ι(c /d ). Then (iv) implies a = c 6 c and b = d 6 d.

34

PATRICK DEHORNOY

e b = b ∧ c = 1 and ι(a/b/c) = ι(d) for some d in M . Then
Now, let a, b, c in M satisfy a ∧
ι(a/b) = ι(d/c) holds so, if (ii) holds, we have a 6 d and b 6 c. Then the assumption b ∧ c = 1
implies b = 1. So (iii) implies (v).
Finally, assume that a is a unital 4-multifraction in FM . Write a2 = xa′2 and a3 = xa′3 with
e a′2 ,
x = a2 ∧ a3 , so that a′2 ∧ a′3 = 1 holds. Next, write a1 = a′1 y and a′2 = a′′2 with y = a1 ∧
′ e ′′
′
′′
′
′
′
so that a1 ∧ a2 = 1 holds. Then we have ι(a1 /a2 /a3 ) = ι(a1 /a2 /a3 ) = ι(a1 /a2 /a3 ), and the
assumption ι(a) = 1 implies ι(a1 /a2 /a3 ) = ι(a4 ) ∈ ι(M ). Hence ι(a′1 /a′′2 /a′3 ) lies in ι(M ) with
e a′′2 = 1 and a′2 ∧ a′3 = 1, whence a fortiori a′′2 ∧ a′3 = 1. If (v) is true, we deduce a′′2 = 1.
a′1 ∧
This means that (a′1 , y, x, a′3 ) is a central cross for a. So (v) implies (i).

Putting things together, we obtain:

Corollary 6.26. Conjectures A4 and B4 are equivalent, and they are equivalent to the property
that, for every Artin-Tits monoid M , every element of U(M ) of the form ab−1 with a, b in M
e b = 1.
admits only one such expression with a ∧

Proof. Let M be an Artin-Tits monoid and a be a unital 4-multifraction on M . By Proposition 6.19, a ⇒∗ 1 implies redt (a) = 1, so Conjecture A4 implies Conjecture B4 . On the other
hand, by Proposition 6.19 again, the property “a unital implies a ⇒∗ 1” is equivalent to “ a
unital implies a admits a central cross” and, by Proposition 6.21, the latter is equivalent to the
uniqueness of fractional decompositions.


6.3. An application to partial orderings on U(M ). If M is a Garside monoid, it is
known [16, Sec. II.3.2] that the left and right divisibility relations of M can be extended into
e h) for
well-defined partial orders on the enveloping group U(M ) by declaring g 6 h (resp., g 6
g −1 h ∈ M (resp., gh−1 ∈ M ). The construction extends to every gcd-monoid, and we show
±
that lattice properties are preserved whenever RM
is 4-semi-convergent.
Proposition 6.27. (i) If M is a gcd-monoid that embeds into U(M ), then declaring g 6 h for
g −1 h ∈ ι(M ) provides a partial order on U(M ) that extends left divisibility on M .
±
(ii) If RM
is 4-semi-convergent, any two elements of U(M ) that admit a common 6-lower
bound (resp., a common 6-upper bound) admit a greatest one (resp., a lowest one).
Proof. (i) We identify M with its image under ι. As M is a semigroup in U(M ), the relation 6
is transitive on U(M ), and it is antisymmetric, as 1 is the only invertible element of M . Hence
6 is a partial order on U(M ). By definition, it extends left divisibility on M .
(ii) Assume that g and h admit a common 6-lower bound f (see Figure 9 left). This means
that we have g = f x and h = f y for some x, y in M . Let f0 := f (x ∧ y). Write x = (x ∧ y)x0 ,
y = (x ∧ y)y0 . Then we have g = f0 x0 and h = f0 y0 , whence f0 6 g and f0 6 h. Now
assume that f1 is any common 6-lower bound of g and h, say g = f1 x1 and h = f1 y1 . In the
−1
group U(M ), we have x0 x−1
1 = y0 y1 . Hence, the 4-multifraction x0 /x1 /y1 /y0 is unital, so, by
assumption, it admits a central cross. Then Lemma 6.23 provides x′ , y ′ satisfying
x0 = (x0 ∧ y0 )x′ ,

x1 = (x1 ∧ y1 )x′ ,

y1 = (x1 ∧ y1 )y ′ ,

y0 = (x0 ∧ y0 )y ′ .

By definition of f0 , we have x0 ∧ y0 = 1, whence x′ = x0 and y ′ = y0 , and, from there,
f1 (x1 ∧ y1 ) = f0 , hence f1 6 f0 , in U(M ). So f0 is a greatest 6-lower bound for g and h.
The argument for lowest 6-upper bound is symmetric. Assume that g and h admit a common
e y) and y = y0 (x ∧
e y).
6-upper bound f (see Figure 9 right). Write f = gx = hy, then x = x0 (x ∧
e
e
Put f0 := gx0 . We have f0 (x ∧ y) = f = hy = hy0 (x ∧ y), whence hy0 = f0 . So f0 is a common
6-upper bound of g and h. Now assume that f1 is any common 6-upper bound of g and h,
say f1 = g1 x1 = hy1 . In U(M ), we have x0 y0−1 = x1 y1−1 , i.e., the 4-multifraction x0 /y0 /y1 /x1
is unital, hence it admits a central cross. Then Lemma 6.23 provides x, y satisfying
e y0 ),
x0 = x(x0 ∧

e y0 ),
y0 = y(x0 ∧

e y1 ),
x1 = x(x1 ∧

e y1 ).
y1 = y(x1 ∧

e y0 = 1, whence x = x0 and y = y0 , leading in U(M ) to
The definition of f0 gives x0 ∧
e y1 ) = f1 , hence f0 6 f1 . So f0 is a lowest 6-upper bound for g and h.
f0 (x1 ∧


MULTIFRACTION REDUCTION II

f

y

x∧

f1

y f
0
x0

x

y0

∧y

0

x0

′

x
g

h

x1
g

′

x1

y
∧y

y1

y1
x1 e
∧y
1

h

x

x0

1

x1

35

y
x0 e
∧y
0
x

f1

y0
f0

x∧
e

y

y
f

Figure 9. Conditional lattice property for the poset (U(M ), 6): greatest lower
bound on the left, lowest upper bound on the right.
Of course, we have a symmetric extension for the right divisibility relation.
Question 6.28. Is the assumption that M embeds in U(M ) sufficient to ensure that conditional
greatest lower bounds and lowest upper bounds for 6 exist in U(M )?
6.4. Depth 6 and beyond. The results established in the case of 4-multifractions do not
extend to depth 6 and beyond. In particular, unital 6-multifractions need not admit a central
e 2 , let a := aba/aca/cac/cbc/bcb/bab and b :=
cross: in the Artin-Tits monoid of type A
ab/ac/ca/cb/bc/ba. We have a ⇒ b ⇒∗ 1, and a admits a central cross, but b does not, as it
is prime. So the counterparts of Lemma 6.17 and Proposition 6.19 fail. However, we shall see
now that, for every n, Conjecture Bn implies a geometrical property of van Kampen diagrams
that directly extends Prop 6.19.
What the latter says is that, if we define (Γ4 , ∗) to be the pointed
graph on the right, then, for every 4-multifraction a that reduces to 1,
there exists an M -labeling of the edges of Γ4 such that the outer labels
from ∗ are a1 , ..., a4 and the labels in each triangle induce equalities in M .
∗
If (Γ, ∗) is a finite, simply connected pointed graph, let us say that a multifraction a on a
monoid M admits a van Kampen diagram of shape Γ if there is an M -labeling of Γ such that
the outer labels from ∗ are a1 , ..., an and the labels in each triangle induce equalities in M .
This notion is a mild extension of the usual one: if S is any generating set for M , then
replacing the elements of M with words in S and equalities with word equivalence provides a
van Kampen diagram in the usual sense for the word in S ∪ S then associated with a. Then,
Proposition 6.19 says that every 4-multifraction reducing to 1 admits a van Kampen diagram
of shape Γ4 . Conjecture B predicts similar results for every depth.
Definition 6.29. For n > 6 even, let (Γn , ∗) be the graph obtained by appending n−2 adjacent
copies of Γ4 around (Γn−2 , ∗) starting from ∗, with alternating orientations, and connecting the
last copy of (Γ4 , ∗) with the first one, see Figure 10.
Proposition 6.30. Let M be an Artin-Tits monoid. If Conjecture B is true, then every unital
n-multifraction on M (with n even) admits a van Kampen diagram of shape Γn , see Figure 10.
max
= 1.
Proof. Let a be a unital n-multifraction on M . Conjecture B predicts the equality a • RU(n)
We shall see that the latter (and, more generally, any equality of the form a • RU(n),x = 1, with
x maximal or not) implies that a admits a van Kampen diagram of shape Γn . In view on
an induction, assume a • R1,x1 ···Rn−1,xn−1 = b · 12 , for some (necessarily unital) (n − 2)multifraction b. Let a0 := a and, inductively, ai := ai−1 • Ri,xi . We start from a loop of
edges with alternating orientations labeled a0 . Then we inductively complete the graph using
n − 1 steps of the type
aii
aii
aii−1
aii−1
ai
ai

i+1

or

xi
ai+1
i−1

ai+1
i

i+1

ai+1
i+1

xi
ai+1
i−1

ai+1
i

ai+1
i+1

36

PATRICK DEHORNOY

ac
aca

ca
ca
1

ab

ba

1

bc bc

c

ba

b

cb

ba ba

1

c

a

a

ac

ab

cb

ab

1 cb

1

1

bc

bc

1
ab
ab

cb
cb

∗
∗
Figure 10. The graph Γ6 : on the left, the naked graph, with four juxtaposed
copies of Γ4 around one (colored) copy of Γ4 ; it has fourteen vertices, namely four
springs (one inner), five wells (two inner), and five 4-prongs; on the right, for M
e 2 , the M -labeling of Γ6 that results from the first
the Artin-Tits monoid of type A
reduction in Example 3.6; it provides a van Kampen diagram for the 6-multifraction
ab/ba/ca/ac/bc/ab. Conjecture B predicts that every 6-multifraction representing 1
in an Artin-Tits monoid admits a van Kampen diagram of shape Γ6 .

according to the sign of i in a. Because the final two entries of an−1 are trivial, the last two
n−1
steps take a simpler form: ann−1 = 1 is equivalent to an = xn−1 , whereas an−1
= 1 is equivalent
−1
e an .
to xn−2 an−1 6
a4
a5
We thus obtain an M -labeling of an annux
4
x3
lar graph made of n − 2 copies of Γ4 , whose
outer boundary is labeled a, and whose ina3
a6
x5
ner boundary is labeled b, see the diagram
x2
b4
b3
on the right, here in the case going from 8
b2
b5
to 6. Then we repeat the process with b,
x6
a
a7
2
etc., until a 4-multifraction is reached, and
b1
b6
x1
we conclude using Proposition 6.19. This
construction exactly corresponds to the ina8 = x7
a1
ductive definition of Γn .

It is well-known that, if a multifraction represents 1 in a group, then it admits a van Kampen
diagram in the sense defined above. What is remarkable here is the existence of one single
universal shape, with prescribed springs, wells, and 4-prongs, that works for every unital nmultifraction at the same time.
Finally, one may wonder whether some counterparts of Lemma 6.10 and 6.17 might hold
with Γn replacing Γ4 : maybe they do, but the natural argument for proving them requires that
the ground monoid satisfies the 3-Ore condition, in which case it is known that every unital
n-multifraction admits a van Kampen diagram of shape Γn , thus making the results trivial.
7. Miscellanea
The main three properties addressed in this paper are Conjectures A, B, and C (together
with the uniform version Cunif of the latter), which involve arbitrary Artin-Tits monoids, and
are known to be true for those of FC type. Testing these statements with a computer is easy,
and we report about experiments that, alltogether, support the conjectures and provide some
experimental evidence. The involved program is available at [14], and the experiments are easy
to repeat and confirm.
We begin with a few remarks about implementation options (Subsection 7.1), then report
about the obtained data (Subsection 7.2). Finally, we conclude with a few hints about further
properties of reduction, including several counter-examples (Subsection 7.3).

MULTIFRACTION REDUCTION II

37

7.1. Implementation options.
±
Choice of the monoid. We are interested in Artin-Tits monoids M such that RM
is not convergent, hence not of FC type. It is natural to look for monoids with a maximal convergence
defect, meaning that the proportion of multifractions with more than one irreducible reduct is
e 2 , and,
maximal. As can be expected, the ratio is maximal for the Artin-Tits monoid of type A
more generally, those with all relations of length 3 exactly: as divergent reducts may arise only
with counter-examples to the 3-Ore property, it is natural that this happens more frequently
e 2 and, more generwhen all atoms give rise to such counter-examples. Another advantage of A
ally, Kn,3 , the Artin-Tits monoid whose Dynkin diagram is the complete graph with n vertices
and all edges labeled 3, is the existence of an explicit description of basic elements (namely 1,
atoms, and products of two distinct atoms) providing a better efficiency (and 100% correctness
with no termination problem) for the implementation of the monoid operations (equality, lcms,
e 2 , considered as the critical type (but any
gcds, etc). Therefore, we mostly concentrated on A
other choice is possible with [14]).

Generation of random multifractions. Exhaustively enumerating multifractions up to a given
length (sum of the lengths of the entries) is difficult, as, even in the case of 3 atoms, there
are more than 2.6 × 109 multifractions of length up to 12. Therefore it is more realistic to use
samples of random multifractions. Generating random elements of the monoid and, from there,
random multifractions, is easy via random words in the atom alphabet (with a bias due to the
relations).
Generating random unital multifractions is more delicate. As the density of unital multifractions is negligible, generating random multifractions and selecting those that are unital is not a
e2
good option (in addition, it requires a prior solution to the word problem, which exists for A
but not in general). Two methods have been used. The first one (“brownian motion”) is to
follow the definition of ≃, thus starting with an empty word and randomly adding or deleting
pairs s/s and applying the Artin-Tits relations. Inserting right and left reversing steps (the
special transformations of Property H, see Subsection 3.3) improves the efficiency.
The second method (“lcm-expansions”) consists in starting from a multifraction that admits
a random central cross, hence is unital of a very special type, and deriving new, more generic,
unital multifractions as follows:
Definition 7.1. (Figure 11) If M is a gcd-monoid and a is a unital n-multifraction on M , with
n even, we say that b is an lcm-expansion of a if kbk = kak holds and, for each i, there exist
decompositions ai = a′i a′′i , bi = b′i b′′i satisfying a′i b′′i−1 = a′i+1 b′′i = a′i ∨ a′i+1 for i negative in a,
e a′′i+1 for i positive in a, with indices modulo n, i.e., n + 1 means 1.
and b′i−1 a′′i = b′i a′′i+1 = a′′i ∨
...
...

b′i−2

bi−2

b′′i−2

a′′i−1 a′i−1
ai−1

b′′i−1

bi−1

a′i
ai

bi

b′i−1

b′i

a′′i

a′′i+1 a′i+1
ai−1

b′′i

b′′i+1

bi+1

a′i+2

b′i+1

a′′i+2
ai

...
...

Figure 11. Lcm-expansion, here for i positive in a; the shift of the indices for b
ensures that b has the same sign as a. Note the symmetry: starting with right divisors
leads to the same notion.
For b an lcm-expansion of a, one reads on Figure 11 the equality ι(b) = ι(a′1 b′′n )−1 ι(a)ι(a′1 b′′n ),
hence lcm-expansion preserves unitality. Constructing lcm-expansions of a is easy: with the
notation of Definition 7.1, once a left divisor a′i of ai is chosen for each i, all the remaining
elements a′′i , b′i , b′′i are determined, and then so is b (but the choice leads to an lcm-expansion
only if the lcms exist). The advantage is that the depth is controlled (which is more difficult with
brownian motion), the inconvenience is that there is no guarantee that generic multifractions
are obtained (but the expansion procedure can be iterated).

38

PATRICK DEHORNOY

Maximal vs. atomic reduction steps. Implementing reduction is straightforward, once the lattice
operations of the monoid are available. As a composition of i-reductions is again an i-reduction,
one might think of restricting to maximal reduction steps, i.e., considering reducts a • Ri,x where
x is a maximal i-reducer for a. This is not a good option, as some reducts may be missed:
e 2 , let a = ab/ba/ca/bcbc. The only maximal
Example 7.2. In the Artin-Tits monoid of type A
reductions from a are R3,cc followed by D1,ab , leading to the unique irreducible 1/ab/ca/cb.
However, one also finds a • R3,c D1,ab R2,c R3,b = cb/abbc/ba/bc, a second irreducible reduct
of a not reachable by maximal steps.
This however does not contradict the following (surprising?) result:
Proposition 7.3. If M is a strongly noetherian gcd-monoid, and b, c are irreducible reducts
of some multifraction, then there exists a finite sequence of maximal reductions and inverses of
maximal reductions connecting b to c.
Proof (sketch). Write b ⊲⊳ c when there exists a sequence as in the statement. Using induction
on the ordinal λ(a), where λ satisfies (3.13), one proves the following general criterion: If ⊲⊳ is an
equivalence relation on FM± such that, for every multifraction a that is i-prime and j-irreducible
for j 6= i and every 1-reduct a′ of a, there exists a irreducible reduct b of a′ satisfying a ⊲⊳ b,
then, for every a in FM± , any two irreducible reducts of a are ⊲⊳-equivalent.

7.2. Experimental data.
Conjectures A and B. Testing the two of them is essentially the same thing: one generates a
random unital multifraction a, and one checks a ⇒∗ 1 in the former case, redt (a) = 1 is the
latter. Because semi-convergence implies 1-confluence, one can fix any reduction strategy for
checking a ⇒∗ 1, for instance looking at each step for the smallest level i and the first atom x
such that Ri,x applies. Although computing redt is slightly slower, as, at each step, all i-reducers
have to be determined in order to take their gcds, both computations are fast. Precise numbers
e 2 or K4,3 , the typical order of magnitude is 5 × 104
are not really significant here; in type A
4
(resp., 1.5 × 10 ) random unital multifractions of length 20 and depth 4 (resp., length 40 and
e 3 , or C
e 2 ), efficiency is diminished by
depth 6) per hour of computation. In other types (e.g., A
a factor 10 approximately.
No counter-example to Conjecture A or B was ever found. As the density of visited (unital)
multifractions becomes negligible when the length grows, the significance of such data is questionable. However, it may be noticed that, for the many properties considered in this paper
and discarded by counter-examples, the length of the latter (all found by random search) is
never more than 12 or so: this does not say anything about a possible counter-example to
Conjecture A or B but, at the least, this shows that the considered lengths are not ridiculous.
Conjecture A4 . For the special case of Conjecture A4 (and of Conjecture B4 , which, by Corollary 6.26, is equivalent), an exhaustive search makes sense, by systematically considering all
possibilities for the central cross (up to a certain length).
e 2 , Conjecture A4 is true for all lcm-expansions
Fact 7.4. For the Artin-Tits monoid of type A
of all multifractions that admits a central cross with entries of length at most 2.

By contrast, the procedure applied to the monoid MC,4 of [19, Proposition 6.9] duly finds a
counter-example, namely an irreducible lcm-expansion of a 4-multifraction with a central cross
(with rays of length 1). What seems to discard a similar counter-example in an Artin-Tits
monoid is the fact that Artin-Tits relations preserve the atoms occurring in an element (the
“support”), but, even for this weak form of Conjecture A4 , we have no proof so far.
Conjectures C and Cunif . Testing these conjectures is easier in that it involves arbitrary, not
necessarily unital multifractions, but it is more difficult in that it requires to determine all
right reducts of a multifraction a and then, for each pair of them, to determine all their left
reducts. The complexity of constructing the tree Ta (as used in the proof of Proposition 5.29)

MULTIFRACTION REDUCTION II

39

and its right counterpart Tea increases quickly with the depth. Beyond depth 4, the total number
of reducts often becomes large (usually a few ones, but possibly several thousands), resulting
in a huge computation time. Typically, in the current version of the program, one can test
Conjecture Cunif for about 5 × 103 (resp., 4 × 103 ) random multifractions of length 20 (resp.,
length 30) and depth 3 per hour of computation. Going to depth 4 diminishes the speed by a
factor 50.
To overcome these bounds, we also tested (without size limitation) the following instance
of Conjecture C: starting with a multifraction a, the determine the (not necessarily distinct)
right reducts b1 , ..., b4 and left reducts c1 , ..., c4 of a obtained using the four natural strategies
(levels from bottom or top, atoms in lexicographical or antilexicographical order), and check
the property ∃k ∀j (bj ⇒∗ ck ), thus checking Conjecture C for {b1 , ..., b4 }. The cost is then
comparable as the one for Conjecture B, with about 5 × 104 (resp., 5 × 103 ) random tries for
length 20 (resp., 30) per hour of computation. The stronger conclusion ∀k ∀j (bj ⇒∗ ck ) is
almost always valid but, as in the case of Figure 6, exceptions occur.
7.3. Further questions. We point to a few natural questions involving reduction. Most of
them remain open, or gave rise to counter-examples.
Normal forms for reductions. Distinguished expressions for sequences of reductions could be
obtained by identifying skew commutation relations, typically of the form Ri,x Rj,y ⇛ Rj,y′ Ri,x′ ,
meaning that, if a • Ri,x Rj,y is defined, then so is a • Rj,y′ Ri,x′ and the results are equal.
Typically, one could try to push divisions to one side, so that all remaining steps are invertible.
This approach does not work well, as exceptions always appear. In the same vein, in view of
a possible induction and building on the universal scheme U (n) that works in the 3-Ore case,
one could conjecture that every reduction sequence is equivalent to one where the highest level
occurs only once, or that, if an n-multifraction a is i-irreducible for i < n − 1, then reducing a
can be done by a sequence of the form Rn−1,x1 Rn−3,x3 Rn−5,x5 ···. This need not be the case.
e 2 , let a = 1/ba/cb/ca/ab. Then a is i-irreducible
Example 7.5. In the Artin-Tits of type A
for i 6 3, but the only sequence from a to an irreducible reduct is R4,a R2,bc R3,a R4,b , discarding
the above two conjectures. Of course, Conjecture B is not contradicted, because a is not unital.
In the same direction, one can study local confluence between left reductions Ri,x and right
ej,y , with the hope of obtaining normal forms useful for cross-conflence. In almost
reductions R
all cases, there exists indeed local confluence solutions. However, the case j = i + 2 remains
problematic in general. Moreover, using local confluence for an induction is unclear, because
there is no common well-founded relation underlying both left and right reduction and, except
in type FC, a multifraction may admit infinitely many left-right reducts.
Homomorphisms. As reduction is constructed using multiplication and lcm operations, it is
preserved by morphisms preserving these operations, namely lcm-morphisms [8]: if φ is an lcmmorphism from a gcd-monoid M to a gcd-monoid M ′ , then a ⇒∗ b implies φ(a) ⇒∗ φ(b) for all
a, b in FM± . This however is not easy to use for, say, Conjecture A, because the implications
±
go in the wrong direction. If if we study the semi-convergence of RM
, mapping M to a gcd′
monoid M that satisfies the 3-Ore condition does not help: if a is unital in FM± , then φ(a) is
unital in FM±′ , so φ(a) ⇒∗ 1 holds, but deducing a ⇒∗ 1 is problematic. In the other direction,
if M ′ satisfies the 3-Ore condition and φ′ is an lcm-morphism from M ′ to M , then Imφ′ is
±
included in some part of M where the 3-Ore condition is satisfied, and knowing that RM
′ is
′
(semi)-convergent will not help for multifractions on M outside Imφ .
Morphisms (lcm-morphisms or not) might be useful for establishing particular properties,
like Conjecture A4 , i.e., the fact that every unital 4-multifraction admits a central cross. If M is
e 2 , one may think of using the classical embedding from M to the
the Artin-Tits monoid of type A
Artin-Tits group of type B3 , namely ha, b, c | abab = baba, bcb = cbc, ac = cai, that maps a
to a−1 b−1 cba, and b and c to themselves, but the image is not included in the monoid. A
probably better choice is to map M to the Artin-Tits monoid M ′ of type D4 , namely ha, b, c, d |

40

PATRICK DEHORNOY

ada = dad, bdb = dbd, cdc = dcdi+ , by φ(s) = ds for s = a, b, c. If a is a unital 4-multifraction
on M , then φ(a) admits a central cross in M ′ : to deduce that a admits a central cross in M ,
it suffices to show that at least one of the central crosses for φ(a) lies in Imφ. The problem is
that Imφ is not closed under right divisor in M ′ : for instance, φ(a) 6 φ(bac) holds in M ′ , but
a 6 bac fails in M .
By the way, the following natural question seems to be open:
Question 7.6 (F. Wehrung). Does the above morphism φ induce an embedding from the
e 2 into the Artin-Tits group of type D4 ?
Artin-Tits group of type A

Reduction graphs. Almost nothing is known about the structural properties of the graph formed
by the reducts of a multifraction, for instance their possible lattice properties: if we have a ⇒∗ b
and a ⇒∗ c and if b and c admit a common reduct, does there exist a common reduct d of b
and c such that every common reduct of b and c is a reduct of d? This is frequently true, but
not always:
e 2 , consider a = 1/a/bcb/bcb/a (which is
Example 7.7. In the Artin-Tits monoid of type A
unital). One finds b = a • R2,b = ba/ab/cb/bcb/a and c = a • R2,c = ca/ac/bc/bcb/a. Then b
and c admit the two symmetric maximal common reducts, namely
d′ = b • D3,b = c • R3,b D1,ca R2,b = ba/ab/c/bc/a,
d′′ = b • R3,c D1,ba R2,c = c • D3,c = ca/ac/b/cb/a,
and there is no common reduct d of b and c of which d′ and d′′ are reducts.
A possible conclusion in view of the long list of counter-examples described in this paper
could be that there is no hope for many further general properties of reduction, implying that
a possible proof of semi-convergence has to involve the specific properties of the ground monoid
in a deep way. In particular, a proof of Conjecture A, B, or C should require developing new
specific tools for Artin-Tits groups. The results of [19] may suggest approaches.
References
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]

J. Altobelli. The word problem for Artin groups of type FC. J. Pure Appl. Algebra, 129:1–22, 1998.
K.I. Appel and P.E. Schupp. Artin groups and infinite Coxeter groups. Invent. Math., 72:201–220 1983.
E. Artin. Theory of Braids. Ann. of Math., 48:101–126, 1947.
E. Brieskorn. Sur les groupe de tresses. In Séminaire Bourbaki 1971/72, volume 317 of Lectures Notes in
Math., pages 21–44. Springer, 1973.
E. Brieskorn and K. Saito. Artin-Gruppen und Coxeter-Gruppen. Invent. Math., 17:245–271, 1972.
R. Charney. Problems related to Artin Groups. Amer. Inst. of Math., Problems in Geometric Group Theory
wiki, http://people.brandeis.edu/∼charney/papers/Artin probs3.pdf, http://aimath.org/pggt.
A. Chermak. Locally non-spherical Artin groups. J. Algebra, 200:56–98, 1998.
J. Crisp. Injective maps between Artin groups. In Geom. Group Theory Down Under, pages 119–137. de
Gruyter, Berlin, 1999. (Canberra 1996).
P. Dehornoy. Preuve de la conjecture d’irréflexivité pour les structures distributives libres. C. R. Acad. Sci.
Paris, 314:333–336, 1992.
P. Dehornoy. A fast method for comparing braids. Adv. in Math., 125:200–235, 1997.
P. Dehornoy. Groupes de Garside. Ann. scient. Éc. Norm. Sup. 4e série, 35:267–306, 2002.
P. Dehornoy. The word reversing method. Intern. J. Alg. and Comput., 21:71–118, 2011.
P. Dehornoy. Multifraction reduction I: The 3-Ore condition and Artin–Tits groups of type FC. J. Comb.
Algebra, to appear, arXiv:1606.08991.
P. Dehornoy. MoKa. Executable MacOS/Docker binaries; www.math.unicaen.fr/∼dehornoy/programs.
P. Dehornoy, M. Dyer, and C. Hohlweg. Garside families in Artin–Tits monoids and low elements in Coxeter
groups. Comptes Rendus Math., 353:403–408, 2015.
P. Dehornoy, with F. Digne, E. Godelle, D. Krammer, and J. Michel. Foundations of Garside Theory.
Number 22 in EMS Tracts in Mathematics. Europ. Math. Soc., 2015.
P. Dehornoy and E. Godelle. A conjecture about Artin–Tits groups. J. Pure Appl. Algebra, 217:741–756,
2013.
P. Dehornoy, D. Holt, and S. Rees. Multifraction reduction IV: Padding and Artin–Tits groups of sufficiently
large type. arXiv:1701.06413.
P. Dehornoy and F. Wehrung. Multifraction reduction III: The case of interval monoids. J. Comb. Algebra,
to appear, arXiv:1606.09018.

MULTIFRACTION REDUCTION II

41

[20] P. Deligne. Les immeubles des groupes de tresses généralisés. Invent. Math., 17:273–302, 1972.
[21] M. Dyer and C. Hohlweg. Small roots, low elements, and the weak order in Coxeter groups. Advances in
Math., 301:769–784, 2016.
[22] D. Epstein, with J. Cannon, D. Holt, S. Levy, M. Paterson & W. Thurston. Word Processing in Groups
Jones & Bartlett Publ (1992).
[23] E. Godelle and L. Paris. Basic questions on Artin-Tits groups. Geometry, Combinatorics, and Topology,
pages 399–311, 2012.
[24] E. Godelle and L. Paris. K(π, 1) and word problems for infinite type Artin-Tits groups, and applications
to virtual braid groups. Math. Z., 272:1339–1364, 2012.
[25] E. Godelle and L. Paris. PreGarside monoids and groups, parabolicity, amalgamation, and FC property.
Int. J. Alg. Comput., 23:1431–1467, 2013.
[26] E. Godelle and S. Rees. Rewriting systems in sufficiently large Artin-Tits groups. arXiv:1511.02789.
[27] S. Hermiller and J. Meier. Artin groups, rewriting systems and three-manifolds. J. Pure Appl. Algebra,
36(2):141–156, 1999.
[28] L. Paris. Artin monoids embed in their groups. Comment. Math. Helv., 77(3):609–637, 2002.
[29] S.J. Pride. On Tits’ conjecture and other questions concerning Artin and generalized Artin groups. Invent.
Math., 86(2):347–356, 1986.
[30] K. Tatsuoka. An isoperimetric inequality for Artin groups of finite type. Trans. Amer. Math. Soc.,
339(2):537–551, 1993.
Laboratoire de Mathématiques Nicolas Oresme, CNRS UMR 6139, Université de Caen, 14032 Caen
cedex, France, and Institut Universitaire de France
E-mail address: patrick.dehornoy@unicaen.fr
URL: www.math.unicaen.fr/∼dehornoy

