A normal form for a class of monoids including the singular braid monoids.

Ruth Corran ^{∗}

December 11, 1998

Abstract

The first part of this paper investigates a class of homogeneously presented monoids. Constructions which enable division and multiplication to be computed are described. The word problem and the division problem are solved, and a unique normal form is given for monoids in this class. The second part deals with the motivating examples of this class — the positive singular Artin monoids. Finally, the singular Artin monoids are introduced. The word and division problems are solved for all singular Artin monoids of finite type, including, for example, the singular braid monoids introduced by Baez and Birman.

1 Introduction and preliminaries

Baez [2] and Birman [3] introduced the singular braid monoids in 1992 and 1993. A solution to the word problem would seem to be a step towards determining the conjecture of Birman’s that the singular braid monoid embeds in the group algebra of the braid group (still unproved, to this author’s knowledge). Garside’s solution [6] to the word problem in the braid groups indicates an approach to the problem in singular braid monoids. The work of Brieskorn and Saito [4] extending this to arbitrary Artin groups, with special results for those of finite type, suggests the definition of singular Artin monoids. Their techniques could be adapted to work in this new class of monoids. Some of the terminology (such as a-chains) is taken from that paper. It turns out that the singular Artin monoids and positive Artin monoids are leading examples of this class so far investigated, although various single relation monoids can be constructed with the desired property.

∗Supported by an Australian Postgraduate Award.

A second motivation for finding solutions to the word and related problems lies in singular knot and link theory. Armand-Ugon et al [1] showed that an arbitrary representative of a singular knot or link with double or triple points may be deformed to a closed singular braid. Bernd Gemein [7] proved an extended Markov’s theorem for singular links: if β and γ are two singular braids whose closed braids are equivalent as singular links, then β and γ are related by a sequence of algebraic operations known as Markov’s moves. If you can solve the word, division and conjugacy problem in the singular braid monoid, then you can determine if two singular braids are related by a Markov move. In this paper we solve the first two of those problems. A solution to the conjugacy problem is the subject of a paper in preparation by this author. Singular link invariants are of interest in various fields, such as conformal field theory, Vassiliev invariants, and loop representations of quantum gravity (see [1] for more details).

Let A be a finite alphabet and R a finite subset of A^{∗} × A^{∗}. Elements of A may be referred to as letters, and elements of A^{∗} as words. Letterwise equality of words is denoted by ≡. Let

R^{Σ} := {(U, V) | (U, V) ∈ R or (V, U) ∈ R}.

If W ≡ Xρ_{1}Y and V ≡ Xρ_{2}Y where (ρ_{1}, ρ_{2}) ∈ R^{Σ} then we say that V and W differ by an elementary transformation. If there is a sequence of words W_{0}, …, W_{k} such that each pair W_{i} and W_{i+1} differ by an elementary transformation, then we say that W_{0} and W_{k} are equivalent, and write W_{0} ∼ W_{k}. In this case, we also say W_{0} and W_{k} differ by a transformation of length k. (The terminology transformation is according to [6] and [4]). The monoid presented by ⟨A | R⟩ is the set of equivalence classes under ∼.

A monoid presentation ⟨A | R⟩ is said to have the uniqueness property if whenever there are letters a and b and words U, V, X, Y over A such that both (aU, bV) ∈ R^{Σ} and (aX, bY) ∈ R^{Σ}, then X ≡ U and Y ≡ V. It is said to have the cancellative property if for all words U, V over A^{∗} with (aU, bV) ∈ R, a ≢ b. It is said to have the homogeneity property if whenever (U, V) is in R, U and V have the same length. It is said to have the reduction property if for all a, b in A and for all words X, Y in A^{∗}, aX ∼ bY implies there exist words U, V and W in A^{∗} such that X ∼ UW, Y ∼ V W and either (aU, bV) ∈ R^{Σ} or aU ≡ bV.

Lemma 1 Suppose that ⟨A | R⟩ has the cancellative and reduction properties. Whenever there are words A, V and W such that AV ∼ AW, then V ∼ W.

Proof. If aV ∼ aW for some letter a then, by the reduction property, there are words X_{1}, X_{2} and Y such that V ∼ X_{1}Y, W ∼ X_{2}Y and either (aX_{1}, aX_{2}) ∈ R^{Σ} or aX_{1} ≡ aX_{2}. By the cancellative property, the first possibility fails, so X_{1} ≡ X_{2} and V ∼ X_{1}Y ∼ W. If aUV ∼ aUW for some letter a and word U, then by the previous observation, UV ∼ UW, so by induction on the length of U, V ∼ W. □

In Sections 2 and 3, we analyse the properties of a monoid presentation with the uniqueness, cancellative, homogeneity and reduction properties. The previous lemma shows that any such monoid is left cancellative. Because of the homogeneity requirement, all equivalent words have the same length. We define ℓ(V) to be the length of V, and so if W ∼ V then ℓ(W) = ℓ(V).

Suppose V and W are words over A. We say that V divides W if there exists a word U such that W ∼ V U. We also say that W is a multiple of V. If W divides V and V divides W, then by homogeneity, V ∼ W. Given a set of words V_{i} where i runs over some indexing set I, a common multiple of {V_{i} | i ∈ I} is a word W such that every V_{i} divides W. A least common multiple is a common multiple which divides all other common multiples. If W and W′ are both least common multiples of {V_{i} | i ∈ I} then they divide one another and hence are equivalent. Thus, if a least common multiple exists, then it is unique up to equivalence.

2 Factorisation

Throughout this section we assume that ⟨A | R⟩ has the uniqueness, cancellative, homogeneity and reduction properties. Thus the monoid presented by ⟨A | R⟩ is left cancellative, by Lemma 1.

Let C be a word and a, b be letters. We say C is a simple a-chain with source a and target b if there are (possibly empty) words U and V such that (aU, CbV) is in R^{Σ}. Call C a compound a-chain if C ≡ C_{1} ⋯ C_{k} for simple chains C_{1}, …, C_{k} such that the source of C_{1} is a and the source of C_{i+1} is the target of C_{i} for i = 1, …, k − 1. In this case, the source and target of C are defined to be the source of C_{1} and the target of C_{k} respectively.

Lemma 2 Suppose C is an a-chain to b and W is a common multiple of a and C. Then W is a common multiple of a and Cb. In particular, a does not divide C.

Proof. There is a word D such that W ∼ CD. Write C ≡ C_{1} ⋯ C_{k} where each C_{i} is simple, and suppose that d is the target of C_{1}, so (aU, C_{1}dV) ∈ R^{Σ} for some words U and V. By the cancellative property, C_{1}d does not begin with a. However a does divide CD. By the reduction property, there is a word Z such that aUZ ∼ CD ∼ C_{1}dV Z. If k = 1 then b ≡ d and Cb ≡ C_{1}d divides CD. Otherwise, after cancelling, dX, and hence d, divides C_{2} ⋯ C_{k}D, so by induction C_{2} ⋯ C_{k}b divides C_{2} ⋯ C_{k}D, and whence Cb divides CD. This proves the first statement.

If a were to divide C, then C would be a common multiple of a and C, and so by the first statement, Cb would divide C. This contradicts homogeneity, and so a cannot divide C. □

A simple a-chain C with target b is imminent if there is a word U such that (aU, Cb) is in R^{Σ}. In this case define C^{+} :≡ aU.

Lemma 3 Suppose that C is a simple a-chain. Then C is imminent with target b precisely when a divides Cb. If C is a compound a-chain such that a divides Cb then b is the target of C.

Proof. If C is a simple imminent a-chain to b, then (aU, Cb) ∈ R^{Σ} for some U. Thus a divides aU ≡ C^{+} ∼ Cb. On the other hand, if a divides Cb, then by the reduction and uniqueness properties, there are words U and V such that (aU, CbV) ∈ R^{Σ} and CbV divides Cb. By homogeneity, V must be empty, making C imminent with target b.

Now suppose C ≡ C_{1} ⋯ C_{k−1}C_{k} where each C_{i} is a simple chain and such that a divides Cb. Suppose that d is the target of C_{k−1}, and hence the source of C_{k}. By Lemma 2, C_{1} ⋯ C_{k−1}C_{k}b is a common multiple of a and C_{1} ⋯ C_{k−1}d, so by cancellativity, d divides the C_{k}b. By the previous part, the d-chain C_{k} has target b, and hence b is the target of C. □

Letters a and b are said to be incomparable if for all words U and V, (aU, bV) ∉ R^{Σ}. If W is a word which begins with a then ^{a^{−1}}W denotes the word obtained by removing a from the beginning of W. For each letter a, we define an operator

K_{a} : A^{∗} ⟶ A^{∗} ˙∪ ∞

recursively. Let W be a word, and let

K_{a}(W) :≡ \{ \begin{matrix}W & if W is empty, begins with a or is a simple a-chain; or \\ ∞ & if a is incomparable with the first letter of W. \end{matrix}

Otherwise, write W ≡ CD where C and D are non-empty words, and C is the largest prefix of W which is a simple a-chain, with target b, say. The rest of the definition of K_{a}(W) is recursive on the lengths of W and D:

K_{a}(W) :≡ \{ \begin{matrix}∞ & if K_{b}(D) ≡ ∞; \\ CK_{b}(D) & if K_{b}(D) ≢ ∞ and \\ & K_{b}(D) does not begin with b; \\ C^{+} ^{b^{−1}}K_{b}(D) & if C is imminent and \\ & K_{b}(D) begins with b; or \\ K_{a}(Cb ^{b^{−1}}K_{b}(D)) & otherwise. \end{matrix}

If K_{a}(W) ≢ ∞ we will say K_{a}(W) is defined.

Lemma 4 If K_{a}(W) is defined then K_{a}(W) ∼ W and K_{a}(W) either is empty, begins with a or is an a-chain. Furthermore, if a and W have a common multiple then K_{a}(W) is defined. In particular, if a divides W then K_{a}(W) begins with a.

Proof. Suppose K_{a}(W) is defined. If W is empty, begins with a or is a simple a-chain then K_{a}(W) ≡ W and we are done.

Otherwise, write W ≡ CD where C is the longest prefix of W which is a simple a-chain. Let b denote the target of C. Since K_{a}(W) ≢ ∞ then K_{b}(D) ≢ ∞, so by induction on the length of D, K_{b}(D) ∼ D and K_{b}(D) is either empty, a b-chain or begins with b. If K_{b}(D) is empty or a b-chain then K_{a}(W) ≡ CK_{b}(D) which is an a-chain, and moreover K_{a}(W) ∼ CD ≡ W.

Otherwise K_{b}(D) begins with b. If C is imminent then K_{a}(W) ≡ C^{+} ^{b^{−1}}K_{b}(D) which begins with a, and moreover,

K_{a}(W) ∼ Cb ^{b^{−1}}K_{b}(D) ≡ CK_{b}(D) ∼ CD ≡ W.

Otherwise we have K_{b}(D) ∼ D, K_{b}(D) begins with b and C is not imminent; so

K_{a}(W) ≡ K_{a}(Cb ^{b^{−1}}K_{b}(D)).

Fortunately Cb is a simple a-chain of length greater than the length of C so by another induction, K_{a}(Cb ^{b^{−1}}K_{b}(D)) begins with a or is an a-chain, and

K_{a}(Cb ^{b^{−1}}K_{b}(D)) ∼ Cb ^{b^{−1}}K_{b}(D) ≡ CK_{b}(D) ∼ CD ≡ W.

This gives the first part of the lemma.

Now suppose that a and W have a common multiple. If W is empty, begins with a or is a simple a-chain then we are done.Otherwise, let U be a word such that a divides W U. By the reduction property the first letter of W is not incomparable with a. So W can be written W ≡ CD where C is the longest prefix of W which is a simple a-chain. Let b be the target of C. Since a divides CDU then by Lemma 2, Cb divides CDU, so by cancellation, b divides DU. Then by induction, K_{b}(D) ≢ ∞. If K_{b}(D) does not begin with b, or begins with b where C is imminent, then K_{a}(W) ≢ ∞, and we are done. Otherwise, K_{a}(W) ≡ K_{a}(Cb ^{b^{−1}}K_{b}(D)) and again applying induction on the length of Cb (a simple a-chain of length greater than that of C), because a and Cb ^{b^{−1}}K_{b}(D) ∼ W have a common multiple, K_{a}(Cb ^{b^{−1}}K_{b}(D)) ≢ ∞. This gives the second part of the lemma.

Finally suppose that a divides W. Then W is a common multiple of a and W, so K_{a}(W) is either an a-chain or begins with a. But Lemma 2 says an a-chain may not be divisible by a; thus K_{a}(W) (which is equivalent to W and hence divisible by a) is not an a-chain and hence must begin with a. □

Let V and W be words. If W is empty then define (V/W) ≡ V. Otherwise write W ≡ Ua for some word U and some letter a. We make the recursive definition:

(V/W) ≡ \{ \begin{matrix}∞ & if (V/U) ≡ ∞, or if \\ & K_{a}(V/U) does not begin with a; or \\ ^{a^{−1}}K_{a}(V/U) & otherwise. \end{matrix}

The following result gives a solution to the division problem in ⟨A | R⟩.

Lemma 5 The word W divides V precisely when (V/W) ≢ ∞, in which case V ∼ W (V/W).

Proof. If W is empty then the result clearly holds. So we may write W ≡ Ua for some word U and some letter a. Suppose W divides V, so there is a word X such that W X ≡ UaX ∼ V. By induction (V/U) ≢ ∞ and V ∼ U(V/U).

By cancellation, aX ∼ (V/U), so a divides (V/U). By Lemma 4, K_{a}(V/U) begins with a, so (V/W) ≢ ∞ and (V/W) ∼ X.

On the other hand, suppose (V/W) ≢ ∞. Then (V/U) ≢ ∞, and in fact K_{a}(V/U) has to begin with a. By induction V ∼ U(V/U), so

V ∼ U(V/U) ∼ UK_{a}(V/U) ∼ Ua ^{a^{−1}}K_{a}(V/U) ∼ W (V/W)

by the definition of (V/W), and so W divides V. □

There is a solution to the word problem for any homogeneous presentation obtained by listing all words of given length and then searching to determine equivalent words. The machinery described above leads to a more sophisticated solution to the word problem.

Corollary 6 Two words W and V are equivalent precisely when (V/W) is the empty word.

3 Common multiples and a normal form

Let a be a letter and W a word. The a-series of W is a series W_{0}^{a}, W_{1}^{a}, … over A^{∗} ˙∪ ∞ defined as follows. Set W_{0}^{a} :≡ K_{a}(W), so by Lemma 4, either W_{0}^{a} is empty, an a-chain, begins with a or is not defined. Then for i ≥ 1, define recursively

W_{i}^{a} :≡ \{ \begin{matrix}a & if W_{i−1}^{a} is empty; \\ W_{i−1}^{a} & if W_{i−1}^{a} begins with a; \\ K_{a}(W_{i−1}^{a}b) & if W_{i−1}^{a} is an a-chain to b; or \\ ∞ & otherwise. \end{matrix}

By Lemma 4, when it is defined W_{i}^{a} is either an a-chain or begins with a (or if i = 0, W_{i}^{a} may be empty). The a-series converges to a word W_{k}^{a} precisely when W_{k}^{a} begins with a. The following definition is intended to capture a notion of the limit of the a-series of W.

L(a, W) :≡ \{ \begin{matrix}W_{k}^{a} & if W_{k}^{a} ≡ W_{k+1}^{a}; or \\ ∞ & otherwise. \end{matrix}

The following two examples are included to illustrate various ways in which L(a, W) ≡ ∞. The first example exhibits two a-series with members which are not defined, and in the second example the a-series is always defined but consists of words of strictly increasing length. The presentations are shown in Section 4 and [4] respectively to have the reduction property, and they clearly have the uniqueness, cancellative and homogeneity properties.

Example 7 We consider what is known as the positive singular braid monoid on three strings, which is denoted S_{A_{2}}^{+} in Section 4. Let A = {a, a′, b, b′} and R = {(aba, bab), (a′ba, bab′), (b′ab, aba′), (aa′, a′a), (bb′, b′b)}. We first look at the a′-series of V ≡ b′. Since a′ and b′ are incomparable, K_{a′}(b′) is not defined and so V_{0}^{a′} ≡ ∞, so subsequently every member of the a′-series of V is not defined, giving L(a′, b′) ≡ ∞.

Now consider the a′-series of W ≡ bb′. Then W_{0}^{a′} ≡ K_{a}(b′) ≡ bb′, W_{1}^{a′} ≡ K_{a′}(bb′a) ≡ bK_{a}(b′a) ≡ bb′a, but W_{2}^{a′} ≡ K_{a′}(bb′ab) ≡ K_{a′}(baba′) ≡ ∞. Thus some members of the a′ series of W ≡ bb′ are defined, but L(a′, bb′) ≡ ∞.

Example 8 Consider now the a-series of W ≡ bc where A = {a, b, c} and R = {(aba, bab), (bcb, cbc), (cac, aca)}. Observe that for any k ≥ 1, U_{k} ≡ (bacbac)^{k} is an a-chain with target a. The a-series starts with W_{0}^{a} ≡ bc ≡ U_{0}bc, and then for all k ≥ 0,

\begin{aligned}W_{6k}^{a} & ≡ & U_{k}bc, & W_{6k+2}^{a} & ≡ & U_{k}baca, & W_{6k+4}^{a} & ≡ & U_{k}bacbab, \\ W_{6k+1}^{a} & ≡ & U_{k}bca, & W_{6k+3}^{a} & ≡ & U_{k}bacab, & W_{6k+5}^{a} & ≡ & U_{k}bacbabc, \end{aligned}

and so W_{6k+6}^{a} ≡ U_{k}bacbacbc ≡ U_{k+1}bc and so on. In this case, the a-series is always defined but never converges to a word, and so L(a, bc) ≡ ∞.

The following result characterises the situation when L(a, W) ≢ ∞.

Lemma 9 L(a, W) is defined precisely when a and W have a common multiple, in which case L(a, W) is a least common multiple of a and W and begins with a.

Proof. If W is empty then W_{0}^{a} ≡ W and W_{i}^{a} ≡ a for all i ≥ 1. Thus L(a, W) ≡ a, and so the result holds trivially. So we may suppose that W is nonempty.

Suppose that a and W have a common multiple M. By Lemma 4, W_{0}^{a} ≡ K_{a}(W) ∼ W is defined, and further, divides M. Since W is not empty, W_{0}^{a} either begins with a or is an a-chain, is a multiple of W and divides M. We will show that the same is true of all W_{i}^{a}, using induction on i. If W_{i}^{a} begins with a, then W_{j}^{a} ≡ W_{i}^{a} for all j ≥ i, and so we are done. Otherwise, W_{i}^{a} is an a-chain to b which is a multiple of W and divides M. So M is a common multiple of W_{i}^{a} and a, and thus by Lemma 2, M is a common multiple of W_{i}^{a}b and a. Now by the second statement of Lemma 4, W_{i+1}^{a} ≡ K_{a}(W_{i}^{a}b) is defined, and either begins with a or is an a-chain. Also M is a common multiple of W_{i+1}^{a} ∼ W_{i}^{a}b and a, and since W divides W_{i}^{a}, then W must also divide W_{i+1}^{a}. Thus we have shown that when a and W have a common multiple, every element of the a-series of W is defined, is a multiple of W, and divides M. Since elements of the a-series increase in length until an element begins with a, and since divisors of M cannot exceed M in length, eventually there is a first W_{k}^{a} which begins with a. Hence L(a, W) ≡ W_{k}^{a}. Furthermore, we have shown that L(a, W) divides every common multiple M of a and W, making it a least common multiple.

On the other hand, suppose L(a, W) ≢ ∞. Then there is a number k ≥ 0 such that the elements W_{0}^{a}, …, W_{k}^{a} of the a-series of W are defined, and W_{k}^{a} begins with a. If k = 0, then L(a, W) ≡ W_{0}^{a} ∼ W. If k > 0 then by the definition of the a-series, there are letters b_{1}, …, b_{k} which are targets of the a-chains W_{0}^{a}, …, W_{k−1}^{a} respectively, and for each i < k, W_{i}^{a}b_{i+1} ∼ W_{i+1}, so L(a, W) ≡ W_{k}^{a} ∼ W_{0}^{a}b_{1} ⋯ b_{k} ∼ W b_{1} ⋯ b_{k}. Hence L(a, W) is a common multiple of a and W. □

Let V and W be words. Define recursively:

L(V, W) :≡ \{ \begin{matrix}W & if V is empty; \\ aL(U, ^{a^{−1}}L(a, W)) & if V ≡ aU, L(a, W) ≢ ∞ and \\ & L(U, ^{a^{−1}}L(a, W)) ≢ ∞; or \\ ∞ & otherwise. \end{matrix}

Lemma 10 L(V, W) is defined precisely when V and W have a common multiple, in which case L(V, W) begins with V and is a least common multiple of V and W. Moreover, L(V, W) ≢ ∞ precisely when L(W, V) ≢ ∞, in which case L(V, W) ∼ L(W, V).

Proof. If V is empty then the first statement holds trivially. Suppose then that V ≡ aU for some letter a and word U.

Suppose that L(V, W) ≢ ∞. Then both L(a, W) and L(U, ^{a^{−1}}L(a, W)) are defined, so by Lemma 9 and induction, there are respectively least common multiples of a and W, and of U and ^{a^{−1}}L(a, W). Moreover, by induction, L(U, ^{a^{−1}}L(a, W)) begins with U, so L(V, W) begins with V. But aL(U, ^{a^{−1}}L(a, W)) ∼ a ^{a^{−1}}L(a, W)Q ∼ L(a, W)Q for some word Q. Thus W divides L(V, W), making L(V, W) a common multiple of V and W.

Suppose that V ≡ aU and W have a common multiple M ≡ aUN, say. Then M is a common multiple of a and W, so by Lemma 9, L(a, W) is defined, begins with a, and divides aUN. By cancellation, ^{a^{−1}}L(a, W) divides UN. Thus U and ^{a^{−1}}L(a, W) have a common multiple UN, and by induction, L(U, ^{a^{−1}}L(a, W)) is defined and divides UN. Certainly then L(V, W) is defined and L(V, W) ≡ aL(U, ^{a^{−1}}L(a, W)) divides aUN ≡ M. By the first part this also proves L(V, W) is a least common multiple of V and W.

Finally, by what we have just proved, L(V, W) ≢ ∞ if and only if V and W have a common multiple, which again is if and only if L(W, V) ≢ ∞. In this case, L(V, W) and L(W, V) divide one another, so by homogeneity are equivalent. □

Let V_{1}, …, V_{m} be words and let ε denote the empty word. Define recursively:

L(V_{1}, …, V_{m}) :≡ \{ \begin{matrix}ε & if m = 0, \\ V_{1} & if m = 1, \\ ∞ & if m ≥ 2 and L(V_{2}, …, V_{m}) ≡ ∞, \\ L(V_{1}, L(V_{2}, …, V_{m})) & if m ≥ 2 and L(V_{2}, …, V_{m}) ≢ ∞ . \end{matrix}

The following result follows by a simple induction on the previous lemma.

Lemma 11 L(V_{1}, …, V_{m}) is defined precisely when V_{1}, …, V_{m} have a common multiple, in which case L(V_{1}, …, V_{m}) begins with V_{1} and is a least common multiple of V_{1}, …, V_{m}. Moreover, for any permutation σ of {1, …, m}, L(V_{1}, …, V_{m}) ≢ ∞ if and only if L(V_{1σ}, …, V_{mσ}) ≢ ∞, in which case L(V_{1}, …, V_{m}) ∼ L(V_{1σ}, …, V_{mσ}). □

Corollary 12 Let Ω be a finite set of words. Then Ω has a common multiple if and only if it has a least common multiple. □

Since A is finite then an infinite subset of A^{∗} must have elements of arbitrary length. By homogeneity, a common multiple must be at least as long as any of the factors. So an infinite set of words can have no common multiples. On the other hand, the empty word divides every other word, so an arbitrary set Ω of words has a common divisor. If D denotes the set of all common divisors of Ω, then D is finite by the preceding discussion. Since every element of Ω is a common multiple of D, then by Corollary 12, D has a least common multiple, which is a greatest common divisor of Ω. Thus greatest common divisors always exist.

Define a total order < on A. For any nonempty subset I of A let Δ_{I} ≡ L(a_{1}, …, a_{k}) where a_{1} < ⋯ < a_{k} and I = {a_{1}, …, a_{k}}. Define Δ_{∅} ≡ ε. For a word W, let Λ(W) be the set of letters which divide W. This is calculable, as K_{a}(W) is calculable, and Λ(W) is just the set of a in A such that K_{a}(W) begins with a. Since W is a common multiple of Λ(W), Δ_{Λ(W)} is defined and (as it as a least common multiple), divides W. Thus (W/Δ_{Λ(W)}) is defined.

We are now in a position to define a normal form. Define an operator N : A^{∗} ⟶ A^{∗} recursively by

N(W) :≡ \{ \begin{matrix}W & if ℓ(W) ≤ 1 , and \\ Δ_{Λ(W)}N(W/Δ_{Λ(W)}) & otherwise. \end{matrix}

It is clear from this definition and Lemma 5 that N(W) ∼ W. The following theorem shows that N produces a unique representative for all words equivalent to W.

Theorem 13 For any two words V and W over A, V ∼ W if and only if N(V) ≡ N(W).

Proof. By the preceding remark, if N(V) ≡ N(W) then V ∼ N(V) ≡ N(W) ∼ W. Now suppose V ∼ W. We first notice that if ℓ(V) ≤ 1 then the result follows. Otherwise we have

N(V) ≡ Δ_{Λ(V)}N(V/Δ_{Λ(V)}) and N(W) ≡ Δ_{Λ(W)}N(W/Δ_{Λ(W)}).

Since V ∼ W then Λ(V) = Λ(W), and so Δ_{Λ(V)} ≡ Δ_{Λ(W)}. Cancellation gives (V/Δ_{Λ(V)}) ∼ (W/Δ_{Λ(W)}), so by induction N(V/Δ_{Λ(V)}) ≡ N(W/Δ_{Λ(W)}), and thus N(V) ≡ N(W). □

4 Positive singular Artin monoids

Let Γ_{M} be a labelled graph with n vertices in one to one correspondence with a finite indexing set I, and with edge labels from the set {3, 4, 5, …, ∞}. Let m_{ij} denote the label of the edge between nodes i and j, or set m_{ij} = 2 if there is no such edge. Let ⟨xy⟩^{m} denote the alternating product xyx ⋯ of length m. Let S = {σ_{i} | i ∈ I} and T = {τ_{i} | i ∈ I}. The positive singular Artin monoid of type M, denoted S_{M}^{+}, is the monoid generated by S∪T subject to the relations R listed below:

⟨σ_{a}σ_{b}⟩^{m_{ab}} = ⟨σ_{b}σ_{a}⟩^{m_{ab}} if m_{ab} < ∞,
τ_{a}⟨σ_{b}σ_{a}⟩^{m_{ab}−1} = \{ \begin{matrix}⟨σ_{b}σ_{a}⟩^{m_{ab}−1}τ_{b} if m_{ab} < ∞ and is odd, or \\ ⟨σ_{b}σ_{a}⟩^{m_{ab}−1}τ_{a} if m_{ab} < ∞ and is even, \end{matrix}
τ_{a}τ_{b} = τ_{b}τ_{a} if m_{ab} = 2, and
σ_{a}τ_{a} = τ_{a}σ_{a} for all a in I.

The relations of the first type involve only letters from S and are called the braid relations, and will be denoted R_{1}. Relations of the last three types will be denoted R_{2}, R_{3} and R_{4} respectively. It has been shown in [4] that the monoid generated by S and subject to the braid relations has the reduction property. In this section we show that positive singular Artin monoids have the reduction property. Inspection of the relations will assure the reader that the conditions for the uniqueness, cancellative and homogeneity properties are satisfied.

The monoid generated by S subject only to the relations R_{1} is called the positive Artin monoid of type M, and denoted G_{M}^{+}. Define : S∪T → S to be the identity on S and to map τ_{a} to σ_{a} for all a. Observe that if ρ_{1} = ρ_{2} is any relation from R then either ρ̂_{1} ≡ ρ̂_{2}, or ρ̂_{1} = ρ̂_{2} is a relation in R_{1}. Thus defines a (surjective) homomorphism from S_{M}^{+} to G_{M}^{+}. We will use the symbol ∼^{R_{1}} to indicate when two words over S are equivalent by the relations R_{1}. The relation ∼ is with respect to the alphabet S ∪ T and the relations R. Thus if X ∼ Y, then X̂ ∼^{R_{1}} Ŷ.

The Coxeter group of type M is the group generated by S subject to the relations R_{1} and the relations σ_{i}^{2} = 1 for all i ∈ I. If the Coxeter group of type M is finite, then M is said to be a finite type. It is the case (see, for example, [8], Chapter 2) that a Coxeter group is finite precisely when its graph is a finite disjoint union of the graphs shown in Figure 1. (When m_{ij} = 3, the edge label is suppressed).

Another way to write the relations of types R_{1}, R_{2} and R_{3} is by using the variables x and y to represent whatever combination of σ or τ is desired, and then

x_{a}⟨σ_{b}σ_{a}⟩^{m_{ab}−2}y_{e} = y_{b}⟨σ_{a}σ_{b}⟩^{m_{ab}−2}x_{d},

[figure: .; 2; .; Type; A_{n}; B_{n}; D_{n}; E_{6}; E_{8}; H_{4}; I_{2}(p); F_{4}; G_{2}; H_{3}; E_{7}; Coxeter Graph; 2; 2; 2; 1; 2; n; 1; 2; n; 1; 3; n; 1; 3; 4; 5; 6; 1; 3; 4; 5; 6; 7; 1; 3; 4; 5; 6; 7; 8; 1; 2; 3; 4; 1; 2; 1; 2; 3; 1; 2; 3; 4; 1; 2; 4; 3; 3; 4; p; 4; 6; 5; 5]

Figure 1: The irreducible Coxeter graphs of finite types.

where e = a and d = b if m_{ab} is odd, or e = b and d = a if m_{ab} is even, subject to the condition that if m_{ab} > 2 then at most one of x and y is τ.

For example if m_{ab} = 3 then the above becomes:

x_{a}σ_{b}y_{a} = y_{b}σ_{a}x_{b},

which yields the relations:

\begin{aligned}σ_{a}σ_{b}σ_{a} & = & σ_{b}σ_{a}σ_{b}, \\ τ_{a}σ_{b}σ_{a} & = & σ_{b}σ_{a}τ_{b} and \\ σ_{a}σ_{b}τ_{a} & = & τ_{b}σ_{a}σ_{b}, \end{aligned}

using all possible substitutions of τ and σ for x and y, except x = τ = y which is forbidden because m_{ab} = 3. Under this notation the reduction property translates to the statement below.

Lemma 14 Suppose that x_{a}X ∼ y_{b}Y for some words X and Y, with x_{a} and y_{b} elements of S ∪ T. If m_{ab} > 2 then at most one of x and y is τ. If x_{a} ≡ y_{b} then X ∼ Y. If x ≠ y but a = b then there is a word V such that X ∼ y_{b}V and Y ∼ x_{a}V. Otherwise there is a word V such that

X ∼ ⟨σ_{b}σ_{a}⟩^{m_{ab}−2}y_{e}V and Y ∼ ⟨σ_{a}σ_{b}⟩^{m_{ab}−2}x_{d}V,

where e = a and d = b if m_{ab} is odd, or e = b and d = a if m_{ab} is even.

Proof. The argument goes by induction on both the length of X and the length of the transformation from x_{a}X to y_{b}Y. If X is empty then the result holds trivially. If x_{a}X ≡ y_{b}Y then there is nothing to prove. If x_{a}X differs from y_{b}Y by an elementary transformation then the lemma holds.

Suppose then that the result is true for words of length less than ℓ(X), and for words of length equal to X which differ by a transformation of length at most t. The following result is a corollary of the reduction lemma restricted to words for which we assume the lemma holds:

Intermediate Lemma. Suppose ℓ(Z) ≤ ℓ(X). Then (a) if Z ∼ MW ∼ MU then W ∼ U;

(b) if u is a letter such that Z ∼ uU ∼ MW and (uv, vu) ∈ R^{Σ} or u ≡ v for all letters v appearing in the word M, then either u appears in M (and so divides it), or there is a word V such that U ∼ MV and W ∼ uV; and

(c) if Z ∼ τ_{i}W ∼ τ_{j}V where i ≠ j then m_{ij} = 2.

Now suppose that x_{a}X differs from y_{b}Y by a transformation of length t+1. Thus there is a letter z_{c} and a word Z such that x_{a}X differs from z_{c}Z by an elementary transformation and z_{c}Z and y_{b}Y differ by a tranformation of length t. Thus the reduction property holds (by assumption) for x_{a}X ∼ z_{c}Z and z_{c}Z ∼ y_{b}Y.

There are six main cases. The reduction property will be frequently applied without comment whenever permitted by induction.

\underline{Case I.} Suppose x_{a}, y_{b} and z_{b} are not distinct. If x_{a} ≡ z_{c} or y_{b} ≡ z_{c} then application of the reduction property gives X ∼ Z or Y ∼ Z respectively. By transitivity of the relation ∼, the result holds.

Now suppose x_{a} ≡ y_{b}, but that these are both distinct from z_{c}. So x_{a}X ∼ z_{c}Z by an elementary transformation, and z_{c}Z ∼ x_{a}Y by a transformation of length t. Applying the reduction property to x_{a}X ∼ z_{c}Z, there are words W_{1}, W_{2} and W such that

(x_{a}W_{1}, z_{c}W_{2}) ∈ R^{Σ}, X ∼ W_{1}W and Z ∼ W_{2}W.

By the uniqueness property, the pairs (x_{a}W_{1}, z_{c}W_{2}) and (z_{c}W_{2}, x_{a}W_{1}) are the only ones in R^{Σ} beginning with the letters x_{a} and z_{c}. So applying the reduction property to z_{c}Z ∼ x_{a}Y (≡ y_{b}Y), there is a word W′ with Z ∼ W_{2}W′ and Y ∼ W_{1}W′. So Z ∼ W_{2}W ∼ W_{2}W′. By the cancellation part of the Intermediate Lemma, W ∼ W′. Thus X ∼ W_{1}W ∼ W_{1}W′ ∼ Y, as required.

\underline{Case II.} Here we consider when x_{a}, z_{c} and y_{b} are distinct, and (x_{a}z_{c}, z_{c}x_{a}), (y_{b}z_{c}, z_{c}y_{b}) ∈ R^{Σ}. Applying the reduction property, there are words W and W′ such that

X ∼ z_{c}W, Z ∼ x_{a}W ∼ y_{b}W′ and Y ∼ z_{c}W′.

Now we can use induction on the length of Z. So there are words W_{1}, W_{2} and U such that

(x_{a}W_{1}, y_{b}W_{2}) ∈ R^{Σ}, W ∼ W_{1}U and Y ∼ W_{2}U.

Inspection of the relations R indicates that all letters in W_{1} and W_{2} must have subscript a or b. Thus z_{c} commutes with W_{1} and W_{2}, and so X ∼ z_{c}W ∼ z_{c}W_{1}U ∼ W_{1}z_{c}U and Y ∼ z_{c}W′ ∼ z_{c}W_{2}U ∼ W_{2}z_{c}U. Setting V ≡ z_{c}U, we have shown that there are words W_{1}, W_{2} and V such that X ∼ W_{1}V, Y ∼ W_{2}V and (x_{a}W_{1}, y_{b}W_{2}) ∈ R^{Σ}, as required.

\underline{Case III.} In this case we consider when x_{a}, y_{b} and z_{c} are distinct, but a, b and c are not distinct. There are three main subcases.

(1) The first case considered is when a = b. For x_{a} and y_{b} to be distinct, then one of x and y is σ and the other τ. If m_{ac} = 2, then (x_{a}z_{c}, z_{c}x_{a}) and (y_{a}z_{c}, z_{c}y_{a}) are in R^{Σ}, which was already covered in Case II.

So suppose m_{ac} > 2. We know one of x and y is τ, so by application of the reduction property z must be σ. Moreover, there are words W and U such that

\begin{matrix}X ∼ ⟨σ_{c}σ_{a}⟩^{m_{ac}−1}W, Z ∼ ⟨σ_{a}σ_{c}⟩^{m_{ac}−2}x_{d}W, & and \\ Z ∼ ⟨σ_{a}σ_{c}⟩^{m_{ac}−2}y_{d}U, Y ∼ ⟨σ_{c}σ_{a}⟩^{m_{ac}−1}U, \end{matrix}

where d = a if m_{ac} is even, and c otherwise. Now by induction on the length of Z, we can cancel ⟨σ_{a}σ_{c}⟩^{m_{ac}−2}, giving x_{d}W ∼ y_{d}U. Because U is shorter than X, there is a word V such that W ∼ y_{d}V and U ∼ x_{d}V. Then

\begin{matrix}X ∼ ⟨σ_{c}σ_{a}⟩^{m_{ac}−1}W ∼ ⟨σ_{c}σ_{a}⟩^{m_{ac}−1}y_{d}V ∼ y_{a}⟨σ_{c}σ_{a}⟩^{m_{ac}−1}V, & and \\ Y ∼ ⟨σ_{c}σ_{a}⟩^{m_{ac}−1}U ∼ ⟨σ_{c}σ_{a}⟩^{m_{ac}−1}x_{d}V ∼ x_{a}⟨σ_{c}σ_{a}⟩^{m_{ac}−1}V. \end{matrix}

(2) The second case is when a = c. So at most one of x and z is τ. If m_{ab} = 2 then (x_{a}z_{a}, z_{a}x_{a}) and (y_{b}z_{a}, z_{a}y_{b}) are in R^{Σ}, which was already covered in Case II.

So suppose that m_{ab} > 2. By the reduction property for z_{a}Z ∼ y_{b}Y, at most one of z and y is τ, and moreover there is a word U such that

Z ∼ ⟨σ_{b}σ_{a}⟩^{m_{ab}−2}y_{d}U, and Y ∼ ⟨σ_{a}σ_{b}⟩^{m_{ab}−2}z_{e}U,

where d ≡ a if m_{ab} is odd, and b otherwise, and e ≡ b if m_{ab} is odd, and a otherwise. Further, there is a word W such that X ∼ z_{a}W and Z ∼ x_{a}W. Thus x_{a}W ∼ ⟨σ_{b}σ_{a}⟩^{m_{ab}−2}y_{d}U, so by induction there is a word V_{1} such that

W ∼ ⟨σ_{a}σ_{b}⟩^{m_{ab}−1}V_{1} and ⟨σ_{a}σ_{b}⟩^{m_{ab}−3}y_{d}U ∼ ⟨σ_{a}σ_{b}⟩^{m_{ab}−2}x_{e}V_{1},

and cancelling from the left, we get y_{d}U ∼ σ_{d}x_{e}V_{1}.

First, suppose that y is τ. So z must be σ, and to preserve distinctness, x must be τ also. So y_{d}U ∼ σ_{d}x_{e}V_{1} implies there is a word V_{2} such that U ∼ σ_{d}V_{2} and x_{e}V_{1} ∼ y_{d}V_{2}. But since m_{ab} > 2 and {x_{e}, y_{d}} = {τ_{a}, τ_{b}}, there are no relations (x_{e}W_{1}, y_{d}W_{2}) in R^{Σ}, contradicting the reduction property applied to x_{e}V_{1} ∼ y_{d}V_{2}. So y cannot be τ.

Hence y must be σ. Cancelling gives U ∼ x_{e}V_{1}. So

\begin{matrix}X ∼ z_{a}⟨σ_{b}σ_{a}⟩^{m_{ab}−1}V_{1} ∼ ⟨σ_{b}σ_{a}⟩^{m_{ab}−1}z_{e}V_{1} ∼ ⟨σ_{b}σ_{a}⟩^{m_{ab}−2}y_{d}z_{e}V_{1}, & and \\ Y ∼ ⟨σ_{a}σ_{b}⟩^{m_{ab}−2}z_{e}U ∼ ⟨σ_{a}σ_{b}⟩^{m_{ab}−2}z_{e}x_{e}V_{1} ∼ ⟨σ_{a}σ_{b}⟩^{m_{ab}−2}x_{e}z_{e}V_{1}, \end{matrix}

and we are done.

(3) The final subcase of Case III is when b = c. This can be done by the same argument as part (2), swapping a with b and x with y.

Completion of these three cases leaves us only with the cases when a, b and c are all distinct. By the comment at 2.2 of [4], if the subgraph Γ_{M}{a, b, c} of Γ_{M} consisting of the vertices a, b and c and any edges joining them does not define a finite Coxeter group, then there are no words X′, Y′ and Z′ such that σ_{a}X′ ∼^{R_{1}} σ_{c}Z′ ∼^{R_{1}} σ_{b}Y′. Since our assumption is that x_{a}X ∼ z_{c}Z ∼ y_{b}Y, then by application of the homomorphism , σ_{a}X̂ ∼^{R_{1}} σ_{c}Ẑ ∼^{R_{1}} σ_{b}Ŷ. Thus Γ_{M}{a, b, c} is a graph with 3 vertices which must define a finite Coxeter group. By inspecting Figure 1, we need only consider when {m_{ab}, m_{ac}, m_{bc}} is either {2, 2, p} where p = 2, 3, 4 or 5, (some of which have already been considered in Case II), or {2, 3, q} where q = 3, 4 or 5.

\underline{Case IV.} Here we consider when m_{ac} = 2. The case when m_{bc} = 2 as well was covered in Case II, so we need only consider when m_{bc} > 2. Since there are no pairs of the form (τ_{b}W_{1}, τ_{c}W_{2}) for m_{bc} > 2 in R^{Σ}, at most one of y and z is τ. We consider the cases m_{ab} = 2, 3, 4 and 5 as separate subcases.

(1) Suppose m_{ab} = 2. There are words W and U such that X ∼ z_{c}W and Z ∼ x_{a}W; and Z ∼ ⟨σ_{b}σ_{c}⟩^{m_{bc}−2}y_{d}U and Y ∼ ⟨σ_{c}σ_{b}⟩^{m_{bc}−2}z_{e}U, where d = c if m_{bc} is odd, and b otherwise, and e = b if m_{bc} is odd, and c otherwise. Applying the Intermediate Lemma part (b) to the equation Z ∼ x_{a}W ∼ ⟨σ_{b}σ_{c}⟩^{m_{bc}−2}y_{d}U, there is a word V such that W ∼ ⟨σ_{b}σ_{c}⟩^{m_{bc}−2}y_{d}V and U ∼ x_{a}V. Then since m_{ab} = m_{ac} = 2, and at most one of y and z is τ,

\begin{matrix}X ∼ z_{c}⟨σ_{b}σ_{c}⟩^{m_{bc}−2}y_{d}V ∼ y_{b}⟨σ_{c}σ_{b}⟩^{m_{bc}−2}z_{e}V, & and \\ Y ∼ ⟨σ_{c}σ_{b}⟩^{m_{bc}−2}z_{e}x_{a}V ∼ x_{a}⟨σ_{c}σ_{b}⟩^{m_{bc}−2}z_{e}V. \end{matrix}

(2) In this case we consider when m_{ab} = 3. The situation that m_{bc} = 2 was completed in Case II. We consider the cases when m_{bc} = 3, 4 and 5 as separate subcases.

(a) Suppose m_{bc} = 3. Then at most one of z and y is τ. There are words W and U such that

X ∼ z_{c}W and Z ∼ x_{a}W, and Z ∼ σ_{b}y_{c}U and Y ∼ σ_{c}z_{b}U.

Since Z ∼ x_{a}W ∼ σ_{b}y_{c}U then there is a word V_{1} such that W ∼ σ_{b}σ_{a}V_{1} and y_{c}U ∼ σ_{a}x_{b}V_{1}. There is a word V_{2} such that U ∼ σ_{a}V_{2} and x_{b}V_{1} ∼ y_{c}V_{2}. By application of the reduction property to this last equation, firstly note that at most one of x and y can be τ (since m_{bc} > 2), and secondly, there is a word V_{3} such that V_{1} ∼ σ_{c}y_{b}V_{3} and V_{2} ∼ σ_{b}x_{c}V_{3}. Reconstructing X and Y we get X ∼ z_{c}W ∼ z_{c}σ_{b}σ_{a}σ_{c}y_{b}V_{3} and Y ∼ σ_{c}z_{b}U ∼ σ_{c}z_{b}σ_{a}σ_{b}x_{c}V_{3}. Straightforward application of the relations gives X ∼ σ_{b}y_{a}[σ_{c}σ_{b}z_{a}V_{3}] and Y ∼ σ_{a}x_{b}[σ_{c}σ_{b}z_{a}V_{3}], and we are done.

Cases (b) where m_{bc} = 4 and (c) where m_{bc} = 5 are similar but more complicated. The induction process is invoked seven times in case (b) and fourteen times in case (c). As in the above process, every step is forced.

(3) In this case we consider when m_{ab} = 4. This forces m_{bc} = 3. So at most one of y and z is τ, and moreover there are words W and U such that

X ∼ z_{c}W and Z ∼ x_{a}W ∼ σ_{b}y_{c}U and Y ∼ σ_{c}z_{b}U.

From successive applications of the reduction property, there are words V_{1}, V_{2}, V_{3} and V_{4} such that

W ∼ σ_{b}σ_{a}σ_{b}V_{1} and y_{c}U ∼ σ_{a}σ_{b}x_{a}V_{1},
U ∼ σ_{a}V_{2} and σ_{b}x_{a}V_{1} ∼ y_{c}V_{2},
x_{a}V_{1} ∼ σ_{c}y_{b}V_{3} and V_{2} ∼ σ_{b}σ_{c}V_{3},
V_{1} ∼ σ_{c}V_{4} and y_{b}V_{3} ∼ x_{a}V_{4}.

Since m_{ab} = 4, at most one of x and y is τ, and there is a word V_{5} such that

V_{3} ∼ σ_{a}σ_{b}x_{a}V_{5} and V_{4} ∼ σ_{b}σ_{a}y_{b}V_{5}.

Reconstructing X and Y we get

X ∼ z_{c}σ_{b}σ_{a}σ_{b}σ_{c}σ_{b}σ_{a}y_{b}V_{5} and Y ∼ σ_{c}z_{b}σ_{a}σ_{b}σ_{c}σ_{a}σ_{b}x_{a}V_{5}.

Application of the relations gives

X ∼ σ_{b}σ_{a}y_{b}[σ_{c}σ_{b}σ_{a}σ_{b}z_{c}V_{5}] and Y ∼ σ_{a}σ_{b}x_{a}[σ_{c}σ_{b}σ_{a}σ_{b}z_{c}V_{5}],

and we are done.

(4) This last subcase of Case IV considers when m_{ab} = 5. We only need consider m_{bc} = 3, since m_{bc} = 2 was covered in Case II. This subcase is very similar to the previous subcase (3), except that induction must be invoked eleven times (where above it was invoked six times).

\underline{Case V.} In this case we consider when m_{bc} = 2. This case proceeds identically to Case IV except for swapping a for b, and x for y.

\underline{Case VI.} The final case considers when both m_{ac} and m_{bc} are larger than 2, which forces m_{ab} = 2. At most one of x and z is τ, and at most one of y and z is τ. The three subcases when m_{ac} is 3, 4 and 5 are considered separately.

(1) We consider first when m_{ac} = 3. Within this subcase, the situations when m_{bc} = 3, 4 or 5 are considered separately.

(a) Suppose m_{bc} = 3. Then there are words W and U such that

X ∼ σ_{c}z_{a}W and Z ∼ σ_{a}x_{c}W ∼ σ_{b}y_{c}U and Y ∼ σ_{c}z_{b}U.

By successive applications of the reduction property, there are words V_{1}, V_{2}, and V_{3} such that

x_{c}W ∼ σ_{b}V_{1} and y_{c}U ∼ σ_{a}V_{1},
W ∼ σ_{b}σ_{c}V_{2} and V_{1} ∼ σ_{c}x_{b}V_{2},
U ∼ σ_{a}σ_{c}V_{3} and V_{1} ∼ σ_{c}y_{a}V_{3}.

Thus V_{1} ∼ σ_{c}x_{b}V_{2} ∼ σ_{c}y_{a}V_{3}. Cancelling gives x_{b}V_{2} ∼ y_{a}V_{3}. Hence there is a word V_{4} such that

V_{2} ∼ y_{a}V_{4} and V_{3} ∼ x_{b}V_{4}.

Now we can reconstruct X and Y to get X ∼ σ_{c}z_{a}σ_{b}σ_{c}y_{a}V_{4} and Y ∼ σ_{c}z_{b}σ_{a}σ_{c}x_{b}V_{4}. Applying the relations (noting that at most one of y and z is τ, and at most one of x and z is τ), we get X ∼ y_{b}[σ_{c}σ_{b}σ_{a}z_{c}V_{4}] and Y ∼ x_{a}[σ_{c}σ_{b}σ_{a}z_{c}V_{4}], and we are done.

Cases (b) and (c) where m_{bc} is 4 and 5 respectively are very similar, but the induction step must be invoked in these cases nine and eighteen times respectively.

(2) This subcase deals with m_{ac} = 4. Thus m_{bc} = 3. The argument here proceeds as for Case VI (1) (b), except for swapping a for b and x for y throughout.

(3) This subcase deals with m_{ac} = 5. Again, m_{bc} = 3. This can be argued as for Case VI (1) (c), except for swapping a for b and x for y throughout. □

Thus positive singular Artin monoids have the uniqueness, cancellation, homogeneity and reduction properties. The results of Sections 1 and 2 apply, so we can solve the word and divisibion problems in positive singular Artin monoids, and in the notation of Section 2, the operator defined recursively by N(W) ≡ Δ_{Λ(W)}N(W/Δ_{Λ(W)}) yields a unique normal form for words over S ∪ T.

To complete this section we include a few extensions of Sections 1 and 2 which are specific to positive singular Artin monoids which will be necessary in the following.

Lemma 15 Let C be a word over S. If C is a σ_{a}-chain to σ_{b} such that Cσ_{b} ∼ σ_{a}C, then Cτ_{b} ∼ τ_{a}C.

Proof. The proof is by induction on the length of C. If C is empty then a = b and the result holds trivially. Otherwise, write C ≡ σ_{c}V for some word V over S. So σ_{c}V σ_{b} ∼ σ_{a}σ_{c}V. The reduction property implies there is a word W such that σ_{c}V ∼ ⟨σ_{c}σ_{a}⟩^{m_{ac}−1}W. Since C is a σ_{a}-chain, it is not divisible by σ_{a}. Hence W cannot be divisible by σ_{d}, the target of ⟨σ_{c}σ_{a}⟩^{m_{ac}−1}. After substitution, Cσ_{b} ∼ σ_{a}C yields

⟨σ_{c}σ_{a}⟩^{m_{ac}−1}W σ_{b} ∼ σ_{a}⟨σ_{c}σ_{a}⟩^{m_{ac}−1}W ∼ ⟨σ_{c}σ_{a}⟩^{m_{ac}}W,

so cancelling gives σ_{d}W ∼ W σ_{b}. Since σ_{d} and W have a common multiple W σ_{b} then by Lemma 4, K_{σ_{d}}(W) ≢ ∞, and since σ_{d} does not divide W, then K_{σ_{d}}(W) must be a σ_{d}-chain. By the second part of Lemma 3, the target of K_{σ_{d}}(W) is σ_{b}. Thus W is equivalent to a σ_{d}-chain K_{σ_{d}}(W) to σ_{b}, and by the induction hypothesis, τ_{d}W ∼ W τ_{b}. Hence

τ_{a}C ∼ τ_{a}⟨σ_{c}σ_{a}⟩^{m_{ac}−1}W ∼ ⟨σ_{c}σ_{a}⟩^{m_{ac}−1}τ_{d}W ∼ ⟨σ_{c}σ_{a}⟩^{m_{ac}−1}W τ_{b} ∼ Cτ_{b}.

□

The final results in this section are about the positive Artin monoid, which is the monoid generated by S subject only to the braid relations (those denoted R_{1}). Suppose that W and V are words over S such that W ∼ V. Since the only relations involving only letters from S are the braid relations, it must be that W ∼^{R_{1}} V. This shows that G_{M}^{+}, the positive Artin monoid of type M, embeds in S_{M}^{+}. This enables us to use many of the results obtained in [4] about words over S. For example, it is shown there that when M is of finite type, L(V_{1}, …, V_{m}) ≢ ∞ for arbitrary words V_{1}, …, V_{m} over S. In particular, Δ_{I} ≢ ∞ for all I ⊆ S. On the other hand, if M is not of finite type, then S has no common multiple (a corollary of [4] 2.2) and so Δ_{S} ≡ ∞.

For the rest of this section we suppose that M is of finite type. The fundamental element Δ of type M is defined to be Δ_{S}. Recall that Δ_{S} is the word L(σ_{a_{1}}, …, σ_{a_{n}}) where σ_{a_{1}} < ⋯ < σ_{a_{n}} for a fixed total order < on S and where S = {σ_{a_{1}}, …, σ_{a_{n}}}. We list below some properties of the fundamental element observed in [4]. The operator rev takes a word and writes it in reverse order.

Remark 16 The following list of properties of the fundamental element is a distillation of results of [4], Sections 5 and 8.

1. Δ is a word over S,

2. Δ is both a left and right least common multiple of S,

3. revΔ ∼ Δ,

4. There is a uniquely determined involutionary automorphism φ of S^{∗} (the free monoid on S), with the properties that

(a) φ permutes S, and

(b) for all words W over S, W Δ ∼^{R_{1}} Δφ(W).

5. The centre of the positive Artin monoid is infinite cyclic for all finite types, and the word Δ represents the generator of the centre of the positive Artin monoid for all finite types except types A_{n} for n ≥ 2, D_{2k+1}, E_{6} and I_{2}(2q + 1), in which cases Δ^{2} represents the generator of the centre.

We extend φ to an automorphism φ̃ of (S ∪ T)^{∗} by defining

φ̃(σ_{i}) ≡ φ(σ_{i}), and
φ̃(τ_{i}) ≡ τ_{j}  where φ(σ_{i}) = σ_{j}.

It is straightforward to check that whenever (ρ_{1}, ρ_{2}) is in R, then φ̃(ρ_{1}) ∼ φ̃(ρ_{2}). Thus if W ∼ V in S_{M}^{+}, then φ̃(W) ∼ φ̃(V). Furthermore, φ̃ permutes T as well as S.

Lemma 17 For each a ∈ I, both σ_{a}Δ ∼ Δφ̃(σ_{a}) and τ_{a}Δ ∼ Δφ̃(τ_{a}). So for all words W over S ∪ T, W Δ ∼ Δφ̃(W). Moreover, Δ represents the generator of the centre of the positive Artin monoid for all finite types except types A_{n} for n ≥ 2, D_{2k+1}, E_{6} and I_{2}(2q + 1), in which cases Δ^{2} represents the generator of the centre.

Proof. Consider any i. By Property 4 above, σ_{i}Δ ∼ Δφ(σ_{i}), so σ_{i}Δ ∼ Δφ̃(σ_{i}). Suppose σ_{k} ∼ φ̃(σ_{i}). Thus σ_{i}Δ ∼ Δσ_{k}. Let p be the largest integer such that Δ ∼ σ_{i}^{p}W for some word W. Then σ_{i}^{p+1}W ∼ σ_{i}^{p}W σ_{k}, so by cancelling, σ_{i}W ∼ W σ_{k}. Since W and σ_{i} have a common multiple then C ≡ K_{σ_{i}}(W) is defined, and since σ_{i} does not divide W (by maximality of p), C is a σ_{i}-chain. By the second statement of Lemma 3, C has target σ_{k}. By Lemma 15, τ_{i}C ∼ Cτ_{k}. Thus

τ_{i}Δ ∼ τ_{i}σ_{i}^{p}C ∼ σ_{i}^{p}τ_{i}C ∼ σ_{i}^{p}Cτ_{k} ∼ Δτ_{k}.

Thus τ_{i}Δ ∼ Δφ̃(τ_{i}). The last statement is immediate from the others. □

5 Singular Artin monoids

Given a labelled graph Γ_{M} as described in the previous section, with vertices in correspondence with a finite indexing set I, let S^{−1} = {σ_{i}^{−1} | i ∈ I}, the set of formal inverses of S. Then the singular Artin monoid of type M, denoted S_{M}, is the monoid generated by S∪S^{−1}∪T and subject to the relations R and the free group relations:

σ_{i}σ_{i}^{−1} = σ_{i}^{−1}σ_{i} = 1 for each i in I.

If W and V are words over S∪S^{−1}∪T which are equivalent under the relations R and the free group relations then write W ≈ V. When X ≡ σ_{a_{1}} ⋯ σ_{a_{k}} is a word over S, we will denote by X^{−1} the word σ_{a_{k}}^{−1} ⋯ σ_{a_{1}}^{−1}. Then XX^{−1} ≈ X^{−1}X ≈ 1.

The special case when I = {1, 2, …, n}, m_{ij} = 3 when |i − j| = 1 and m_{ij} = 2 when |i − j| ≥ 1, is the singular Artin monoid of type A_{n}, and was introduced in [2] and [3] as the singular braid monoid on n + 1 strings. In this section we solve the word and division problems in the singular Artin monoids of finite type, which includes the singular braid monoid. In these types, the fundamental element exists and plays a significant role. For the rest of this section we suppose that M is of finite type.

Let ζ be a word representing the generator of the centre of the positive singular Artin monoid — either Δ or Δ^{2} by Lemma 17. Now ζx ∼ xζ for all x in S ∪ T. Thus

σ_{a}^{−1}ζ ≈ σ_{a}^{−1}ζσ_{a}σ_{a}^{−1} ≈ σ_{a}^{−1}σ_{a}ζσ_{a}^{−1} ≈ ζσ_{a}^{−1}.

Thus ζ represents a central element in S_{M}. Clearly, by similar reasoning, ζ^{−1} represents a central element in S_{M}. Since ζ is divisible by all elements of S, ζ_{a} ≡ ^{σ_{a}^{−1}}K_{σ_{a}}(ζ) is defined. Centrality yields σ_{a}ζ_{a}σ_{a} ∼ ζσ_{a} ∼ σ_{a}ζ ∼ σ_{a}^{2}ζ_{a}, and cancelling σ_{a} then gives ζ_{a}σ_{a} ∼ ζ ∼ σ_{a}ζ_{a}.

Let W be a word over S∪S^{−1}∪T. There are words U_{i} over S ∪ T such that W ≡ U_{0}σ_{a_{1}}^{−1}U_{1}σ_{a_{2}}^{−1}U_{2} ⋯ U_{k−1}σ_{a_{k}}^{−1}U_{k}. Then define

θ_{1}(W) ≡ U_{0}ζ_{a_{1}}U_{1}ζ_{a_{2}}U_{2} ⋯ U_{k−1}ζ_{a_{k}}U_{k}, and θ_{2}(W) = k.

So θ_{2} counts the number of occurrences of letters from S^{−1} in W, and θ_{1} replaces each with a corresponding ζ_{a}. Thus θ_{1}(W) is always a word over S ∪ T, and θ_{1} acts as the identity on words over S ∪ T. Moreover, for any words X and Y, θ_{1}(XY) ≡ θ_{1}(X)θ_{1}(Y), and

ζ^{−θ_{2}(W)}θ_{1}(W) ≡ ζ^{−θ_{2}(W)}U_{0}ζ_{a_{1}}U_{1}ζ_{a_{2}}U_{2} ⋯ U_{k−1}ζ_{a_{k}}U_{k},
≈ U_{0}ζ^{−1}ζ_{a_{1}}U_{1}ζ^{−1}ζ_{a_{2}}U_{2} ⋯ U_{k−1}ζ^{−1}ζ_{a_{k}}U_{k}, by centrality,
≈ U_{0}σ_{a_{1}}^{−1}U_{1}σ_{a_{2}}^{−1}U_{2} ⋯ U_{k−1}σ_{a_{k}}^{−1}U_{k},
≡ W.

Recall that two words V and W are said to differ by an elementary transformation if there are words X and Y and a relation (ρ_{1}, ρ_{2}) ∈ R^{Σ} such that V ≡ Xρ_{1}Y and W ≡ Xρ_{2}Y. We say that a word V is obtained from W by a trivial insertion if there are words X and Y and a letter x ∈ S ∪ S^{−1}, such that W ≡ XY and V ≡ Xxx^{−1}Y. In this case we also say W is obtained from V by a trivial deletion.

Lemma 18 Suppose that W and V are words over S ∪S^{−1} ∪T. If W and V differ by an elementary transformation then θ_{1}(W) ∼ θ_{1}(V). If V is obtained from W by a trivial insertion then ζθ_{1}(W) ∼ θ_{1}(V).

Proof. If W ≡ Xρ_{1}Y and V ≡ Xρ_{2}Y where (ρ_{1}, ρ_{2}) ∈ R^{Σ}, then θ_{1}(W) ≡ θ_{1}(X)ρ_{1}θ_{1}(Y) ∼ θ_{1}(X)ρ_{2}θ_{1}(Y) ≡ θ_{1}(V).

If W ≡ XY, V ≡ Xσ_{a}σ_{a}^{−1}Y and U ≡ Xσ_{a}^{−1}σ_{a}Y, for some a ∈ I and some words X and Y, then θ_{1}(V) ≡ θ_{1}(X)σ_{a}ζ_{a}θ_{1}(Y) ∼ θ_{1}(X)ζθ_{1}(Y) ∼ ζθ_{1}(X)θ_{1}(Y) ≡ ζθ_{1}(W), and similarly θ_{1}(U) ∼ ζθ_{1}(W). □

The proof of the following theorem is adapted from the proof in [5] that the positive braid monoid embeds in the braid group.

Theorem 19 Let W and W′ be words over S ∪ T. Then W ≈ W′ if and only if W ∼ W′.

Proof. It is clear that if W ∼ W′ then W ≈ W′. So suppose W and W′ are words over S ∪ T such that W ≈ W′. Then there is a sequence W_{1}, …, W_{k} of words over S∪S^{−1}∪T such that W ≡ W_{1} ≈ W_{2} ≈ ⋯ ≈ W_{k} ≡ W′ and W_{i+1} is obtained from W_{i} by an elementary transformation or by insertion or deletion of σ_{a}σ_{a}^{−1} or σ_{a}^{−1}σ_{a} for some a in I.

Let p = max {θ_{2}(W_{i}) | i = 1, …, k}. For each i = 1, …, k define

V_{i} ≡ ζ^{p−θ_{2}(W_{i})}θ_{1}(W_{i}).

Each V_{i} is a word over S ∪ T, and V_{i} ≈ ζ^{p}ζ^{−θ_{2}(W_{i})}θ_{1}(W_{i}) ≈ ζ^{p}W_{i}. If W_{i+1} is obtained from W_{i} by an elementary transformation, then by the previous result, V_{i} ∼ V_{i+1}. If W_{i+1} is obtained from W_{i} by a trivial insertion, then θ_{2}(W_{i+1}) = θ_{2}(W_{i}) + 1 ≤ p, so

V_{i} ≡ ζ^{p−θ_{2}(W_{i})}θ_{1}(W_{i}) ≡ ζ^{p−θ_{2}(W_{i+1})}ζθ_{1}(W_{i}) ∼ ζ^{p−θ_{2}(W_{i+1})}θ_{1}(W_{i+1}) ≡ V_{i+1}

by an application of Lemma 18. Swapping i+1 and i in this argument yields the case when W_{i+1} is obtained from W_{i} by a trivial deletion. In all cases, V_{i} ∼ V_{i+1}.

Thus we have V_{1} ∼ V_{k}. But W and W′ have no letters from S^{−1}, so V_{1} ≡ ζ^{p}W_{1} ≡ ζ^{p}W and V_{k} ≡ ζ^{p}W_{k} ≡ ζ^{p}W′. Hence ζ^{p}W ∼ ζ^{p}W′, and cancelling ζ^{p} from the left yields W ∼ W′. □

Corollary 20 The positive singular Artin monoid of any finite type embeds in its corresponding singular Artin monoid. □

We can now construct a unique normal form for elements of the singular Artin monoid. Let q(W) be the largest integer such that (θ_{1}(W)/Δ^{q(W)}) is defined. Since 0 ≤ q(W) ≤ ℓ(θ_{1}(W)) this is calculable. Let p(W) be the integer such that Δ^{p(W)} ≈ ζ^{−θ_{2}(W)}Δ^{q(W)}. (This number depends on whether ζ is Δ or Δ^{2}, which in turn depends on the type). Thus W ≈ Δ^{p(W)}(θ_{1}(W)/Δ^{q(W)}).

Lemma 21 If W ≈ V then p(W) = p(V). Moreover, p(W) ≥ 0 precisely when W ≈ W′ for some word W′ over S ∪ T.

Proof. Suppose W ≈ V for arbitrary words W and V, and that k = θ_{2}(W)− θ_{2}(V) ≥ 0. Then

θ_{1}(W) ≈ ζ^{θ_{2}(W)}W ≈ ζ^{θ_{2}(W)}V ≡ ζ^{k}ζ^{θ_{2}(V)}V ≈ ζ^{k}θ_{1}(V).

Thus by Theorem 19, θ_{1}(W) ∼ ζ^{k}θ_{1}(V). Hence Δ^{q(W)} ≡ ζ^{k}Δ^{q(V)}, so

Δ^{p(W)} ≈ ζ^{−θ_{2}(W)}Δ^{q(W)} ≈ ζ^{−θ_{2}(W)}ζ^{k}Δ^{q(V)} ≈ ζ^{−θ_{2}(V)}Δ^{q(V)} ≈ Δ^{p(V)}.

This implies that Δ^{p(W)} ∼ Δ^{p(V)}, and hence that p(W) = p(V).

If W′ is a word over S ∪T then θ_{2}(W′) = 0 so p(W′) is non negative, so by the first part, W ≈ W′ implies p(W) is non negative. Finally, if p(W) ≥ 0, then W ≈ Δ^{p(W)}(θ_{1}(W)/Δ^{q(W)}), which is a word over S ∪ T. □

It was observed above that W ≈ Δ^{p(W)}(θ_{1}(W)/Δ^{q(W)}) for any word W over S ∪ S^{−1} ∪ T. Recall that the operator N defined in Section 3 acts on words over S ∪ T, so since (θ_{1}(W)/Δ^{q(W)}) is a word over S ∪ T, we can use the above formulation to extend N in order to act on arbitrary words W over S ∪ S^{−1} ∪ T. Define

N̄(W) ≡ \{ \begin{matrix}N(Δ^{p(W)}(θ_{1}(W)/Δ^{q(W)})) & if p(W) ≥ 0; or \\ Δ^{p(W)}N(θ_{1}(W)/Δ^{q(W)}) & otherwise. \end{matrix}

Observe that whenever W ≈ W′ for some word W′ over S ∪T, this definition yields the normal form for W′ as defined in Section 3.

Theorem 22 Let V and W be words over S ∪ S^{−1} ∪ T. Then V ≈ W precisely when N̄(V) ≡ N̄(W).

Proof. By the definition of N̄, and the fact that for words W′ over S ∪ T, N(W′) ∼ W′, we have that

N̄(W) ≈ ζ^{−θ_{2}(W)}Δ^{q(W)}(θ_{1}(W)/Δ^{q(W)}) ≈ ζ^{−θ_{2}(W)}θ_{1}(W) ≈ W.

So if N̄(V) ≡ N̄(W) then V ≈ W. On the other hand, suppose V ≈ W, and so p(V) = p(W) = p by Lemma 21. If p ≥ 0 then N̄(V) ≡ N(W′) ≡ N̄(W) for some word W′ over S ∪ T. Otherwise, N̄(V) ≈ V ≈ W ≈ N̄(W), so Δ^{p}N(θ_{1}(V)/Δ^{q(V)}) ≈ Δ^{p}N(θ_{1}(W)/Δ^{q(W)}). But (θ_{1}(V)/Δ^{q(V)}) and (θ_{1}(W)/Δ^{q(W)}) are words over S∪T, so by Theorem 19, N(θ_{1}(V)/Δ^{q(V)}) ∼ N(θ_{1}(W)/Δ^{q(W)}), then by Theorem 13, N(θ_{1}(V)/Δ^{q(V)}) ≡ N(θ_{1}(W)/Δ^{q(W)}). Thus N̄(V) ≡ Δ^{p}N(θ_{1}(V)/Δ^{q(V)}) ≡ Δ^{p}N(θ_{1}(W)/Δ^{q(W)}) ≡ N̄(W). □

Due to the addition of the free group relations, S_{M} does not have a homogeneous presentation. Thus the naive solution to the word problem via enumeration and searching described at the end of Section 2 will not work here, and we believe that the results in this paper give the only known solution to the word problem for singular Artin monoids, including the singular braid monoids. The following result solves the division problem in S_{M}.

Theorem 23 Let V and W be words over S ∪ S^{−1} ∪ T. Then V divides W in the singular Artin monoid precisely when M ≡ L(θ_{1}(W), θ_{1}(V)) ≢ ∞ and (M/θ_{1}(W)) is a word over S.

Proof. Suppose there is a word U such that W ≈ V U. Then ζ^{−θ_{2}(W)}θ_{1}(W) ≈ ζ^{−θ_{2}(V)}θ_{1}(V)ζ^{−θ_{2}(U)}θ_{1}(U) and so by centrality and Theorem 19,

θ_{1}(W)ζ^{θ_{2}(V)+θ_{2}(U)} ∼ θ_{1}(V)θ_{1}(U)ζ^{θ_{2}(W)}.

Hence θ_{1}(W) and θ_{1}(V) have a common multiple, and so by Lemma 10, M ≡ L(θ_{1}(W), θ_{1}(V)) ≢ ∞, and M is a least common multiple, so it must divide θ_{1}(W)ζ^{θ_{2}(V)+θ_{2}(U)}. Thus (M/θ_{1}(W)) must divide ζ^{θ_{2}(V)+θ_{2}(U)}, and consequently is a word over S.

On the other hand, suppose M ≡ L(θ_{1}(W), θ_{1}(V)) ≢ ∞ and X ≡ (M/θ_{1}(W)) is a word over S. Then

W ≈ ζ^{−θ_{2}(W)}θ_{1}(W) ≈ ζ^{−θ_{2}(W)}θ_{1}(W)XX^{−1} ≈ ζ^{−θ_{2}(W)}MX^{−1}

≈ ζ^{−θ_{2}(W)}θ_{1}(V)Y X^{−1} because M ∼ θ_{1}(V)Y for some Y over S ∪ T,

≈ ζ^{−θ_{2}(V)}θ_{1}(V)Y X^{−1}ζ^{θ_{2}(V)−θ_{2}(W)} ≈ V U

where U ≡ Y X^{−1}ζ^{θ_{2}(V)−θ_{2}(W)}. □

References

[1] D. Armand-Ugon, R. Gambini & P. Mora, Intersecting braids and intersecting knot theory, J. Knot Theory Ramifications, 4 (1995),no.1, 1 - 12.

[2] J. Baez, Link invariants and perturbation theory, Lett. Math. Phys. 2 (1992), 43 - 51.

[3] Joan Birman, New points of view in knot theory, Bull. AMS (1993), 253 - 287.

[4] E. Brieskorn & K. Saito, Artin-Gruppen und Coxeter-Gruppen, Inventiones Math. 17, 245 - 271, (1972).

[5] D. Epstein et al., Word processing in groups, Jones and Bartlett, 1992.

[6] F. A. Garside, The braid group and other groups, Quart. J. Math. Oxford (2), 20 (1969), 235 - 254.

[7] B. Gemein, Singular braids and Markov’s theorem, J. Knot Theory Ramifications, 6 (1997),no.4, 441 - 454.

[8] James E. Humphreys, Reflection groups and Coxeter groups, Cambridge studies in advanced mathematics 29, Cambridge University Press, 1990.