SOLUTION OF THE WORD PROBLEM

IN THE SINGULAR BRAID GROUP

S.Yu. Orevkov

Abstract. Singular braids are isotopy classes of smooth strings which are allowed to cross each other pairwise with distinct tangents. Under the usual multiplication of braids, they form a monoid. The singular braid group was introduced by Fenn-Keyman-Rourke as the quotient group of the singular braid monoid. We give a solution of the word problem for this group. It is obtained as a combination of the results by Fenn-Keyman-Rourke and some simple geometric considerations based on the mapping class interpretation of braids. Combined with Corran’s normal form for the singular braid monoid, our algorithm provides a computable normal form for the singular braid group.

1. Introduction. Let X be any set. Let us denote X × {1, …, n − 1} by X_{n}. We shall denote an element (x, i) of X_{n} by x_{i}. Let Σ_{n} = {σ_{1}, …, σ_{n−1}}. The singular braid group B_{n}(X)_{G} is the group generated by X_{n} ∪Σ_{n} and subject to the relations

σ_{i}σ_{j} = σ_{j}σ_{i}, σ_{i}x_{j} = x_{j}σ_{i}, x_{i}y_{j} = y_{j}x_{i},  |i − j| ≥ 2, x, y ∈ X; (1)
σ_{i}σ_{j}σ_{i} = σ_{j}σ_{i}σ_{j}, x_{i}σ_{j}σ_{i} = σ_{j}σ_{i}x_{j},  |i − j| = 1, x ∈ X;  (2)
σ_{i}x_{i} = x_{i}σ_{i}  x ∈ X.  (3)

In this paper we give a solution of the word problem for B_{n}(X)_{G}.

Let Σ_{n}^{−1} = {σ_{1}^{−1}, …, σ_{n−1}^{−1}}. The singular braid monoid B_{n}(X)_{M} is the monoid generated by X_{n} ∪ Σ_{n} ∪ Σ_{n}^{−1} and subject to the relations (1) – (3) and

σ_{i}σ_{i}^{−1} = σ_{i}^{−1}σ_{i} = 1.  (4)

When X = ∅, both B_{n}(X)_{G} and B_{n}(X)_{M} coincide with the usual braid group.

In the case when X is a one-element set {τ}, the singular braid monoid was introduces by Baez [1] and Birman [2]. Corran solved the word [3] and conjugacy [4] problems for this monoid (and for its natural generalization for any Artin group). She did it when X = {τ}, however the same proofs work for any X.

The singular braid group was introduced by Fenn, Keyman, and Rourke [7] (for X = {τ} but their arguments are valid for any X). They proved that B_{n}(X)_{M} embeds into B_{n}(X)_{G}. This result is derived in [7] from Theorem 1 formulated below.

Let X^{−1} = {x^{−1} | x ∈ X}. There is a natural homomorphism of monoids

ι : B_{n}(X ∪ X^{−1})_{M} → B_{n}(X)_{G}.

Typeset by AMS-TEX

2000 Mathematics Subject Classification Primary 20F36; Secondary 20F10, 57M25.

Key words and phrases. Singular braid group, word problem.

Definition 1. An element α ∈ B_{n}(X ∪ X^{−1})_{M} is called irreducible if it cannot be written as α = βx_{i}x_{i}^{−1}γ or α = βx_{i}^{−1}x_{i}γ.

Theorem 1. ([7; Corollary 3.3]). If α and β are irreducible elements of B_{n}(X ∪ X^{−1})_{M} and ι(α) = ι(β) then α = β.

Thus, due to Theorem 1, we can solve the word problem in B_{n}(X)_{G} as soon as we know a reduction algorithm, i.e. an algorithm which computes an irreducible word representing a given element of B_{n}(X)_{G}. Indeed, to compare two elements α and β of B_{n}(X)_{G}, we compute a reduced word γ, representing αβ^{−1}. If γ contains letters from X_{n} ∪ X_{n}^{−1} then γ ≠ 1, hence α ≠ β. Otherwise, we apply any of numerous known algorithms to decide if γ is trivial in the usual braid group. Moreover, combined with Corran’s normal form [3] for elements of B_{n}(X ∪X^{−1})_{M}, a reduction algorithm provides a computable normal form for elements of B_{n}(X)_{G}.

We shall give a reduction algorithm in Section 4. It is based on the life discs introduced in [7] and the ideas from [6]. Modified in Section 6 according to Dynnikov (see [5; Ch.III, 4.19–4.23]), this algorithm turns out to be of biquadratic time (quadratic time if one considers additions and comparings of integers as elementary operations).

2. Geometric singular braids. Let 𝔻 be the closed unit disc in ℂ and I = [−1, 1]. Let P_{n} = {p_{1}, …, p_{n}} ⊂ I, where p_{0} = −1 < p_{1} < ⋯ < p_{n} < p_{n+1} = 1.

A geometric X-braid (or geometric singular braid if X is not precised) α is a union of smooth closed curves (called strings) in the cylindre 𝔻 × [0, 1], such that:

(i ) The projection of any string onto [0, 1] is a diffeomorphism.

(ii ) α ∩ (𝔻 × {0}) = P_{n} × {0} and α ∩ (𝔻 × {1}) = P_{n} × {1}.

(iii ) Strings meet each other only pairwise and with distinct tangents at each crossing.

In fact, the condition (iii) implies that the number of crossings is finite. To each crossing is associated an element of X (its color). A disc 𝔻 × {t}, t ∈ [0, 1] will be called level. A union of levels 𝔻 × {t} for t ∈ [a, b] ⊂ [0, 1] will be called layer.

Two geometric X-braids α_{0} and α_{1} are called isotopic if there exists a smooth family {α_{t}}_{t∈[0,1]} of geometric X-braids relating α_{0} to α_{1}. The elements of the monoid B_{n}(X)_{M} are in one-to-one correspondence with the isotopy classes of geometric X-braids (see [1, 2, 7] for details). Under this correspondence, the generators σ_{i}, σ_{i}^{−1} and x_{i}, x ∈ X, correspond to geometric braids whose projections onto I × [0, 1], (z, t) ↦ (Re z, t), are as in Figure 1.

σ_{i}  σ_{i}^{−1}  x_{i} Figure 1

3. Life discs and youth discs. The following definition is taken from [7]. Let α be a geometric (X ∪X^{−1})-braid. A life disc for α is a disc D embedded in 𝔻×[0, 1] such that:

(i ) The interior of D is disjoint from α.

(ii ) The boundary of D lies on β and contains precisely two crossings q and q′

(called birth and death) colored by x and x^{−1} for some x ∈ X. (iii ) D is contained in the layer between the levels of q and q′ (inclusive). It

meets the levels of q and q′ precisely in q and q′ respectively and it meets each level strictly between q and q′ transversally in an arc.

Lemma 1. [7]. A geometric (X ∪ X^{−1})-braid is reduced if and only if there is no life disc for it. □

Let us define a youth disc (we are trying to keep the terminology style proposed by Fenn, Keyman, and Rourke) for a singular geometric braid α as a disc embedded in 𝔻 × [0, 1] which can be completed to a life disc of αβ for some singular geometric braid β. If D is a youth disc then the curve Γ = pr_{1}(D ∩ (𝔻 × {1})) is called the final curve of D where pr_{1} : 𝔻 × [0, 1] → 𝔻 is (z, t) ↦ z.

The following definitions are inspired by [6]. Let P_{n} and I be as in Section 2. Let Γ be an embedded curve in 𝔻 whose endpoints belong to P_{n} and no interior point belong to P_{n}. We shall say that Γ is transversal to I if it is either really transversal or it coincides with one of the segments [p_{i}, p_{i+1}]. Let curves Γ and Γ′ be transversal to I. They are called I-equivalent if they are isotopic via an ambient isotopy which is fixed on P_{n} and which preserves I.

Suppose that Γ is transversal to I. A component Δ of 𝔻 \ (Γ ∪ I) is calls a digon between Γ and I if Δ is homeomorphic to an open disc and is bounded by an open segment of Γ, an open segment of I \ P_{n}, and two points (any of which may, or may not, belong to P_{n}). We say that Γ is reduced if it is transversal to I and there is no digon between Γ and I. Let us say that a youth disc is reduced if its final curve is reduced.

It it easy to see that any curve Γ can be reduced by an isotopy which is the identity on P_{n} (see, e.g. [6]). When Γ = D ∩ (𝔻 × {1}) for a youth disc D, such an isotopy can be extended to a neighbourhood of 𝔻 × {1} up to an isotopy of D. Thus, we have

Lemma 2. If there exists a youth disc for a singular braid α, born at some crossing q, then there exist a reduced youth disc for α born at q. □

Lemma 3. Let D_{1} and D_{2} be two youth discs for the same geometric singular braid α born at the same crossing. Then their final curves are isotopic by an ambient isotopy which is fixed on P_{n}.

Proof. This can be proved by a kind of standard argument like ”Let us choose the maximal t such that D_{1} ∩ (𝔻 × {t}) and D_{2} ∩ (𝔻 × {t}) are isotopic and extend the isotopy a little bit further...”. One can also proceed as in [7; Sect.4, Case (3)]. □

Combining Lemmas 2 and 3, we get

Lemma 4. If there exists a youth disc for a singular braid α, born at some crossing q, then there exist a reduced youth disc for α born at q and its final curve is uniquely determined by α and q up to I-equivalency. □

4. Prolongation of youth discs. Let α be a geometric (X ∪ X^{−1})-braid and D a youth disc for it born at a crossing q of a color x^{ε}, ε = ±1. Suppose that D is reduced and let Γ be its final curve. Let β be a geometric braid representing a standard generator, i.e. β ∈ Σ ∪ Σ^{−1} ∪ X ∪ X^{−1}. The following lemma is simple and we omit its proof.

Lemma 5. (a). Let β = σ_{i}^{±1}. Then there exists a reduced youth disc for αβ born at q. Its final curve is obtained from Γ by the standard action of β by a diffeomorphism (see, e.g., [6]). (b). Suppose that β = y_{i}^{δ}, y ∈ X, δ = ±1. Then: (b1). A youth disc D′ for αβ born at q exists if and only if Γ ∩ [p_{i}, p_{i+1}] = ∅. In

this case the final curve of D′ is I-equivalent to Γ (b2). A life disc for αβ born at q exists if and only if Γ = [p_{i}, p_{i+1}], y = x and

δ = −ε.

Now we are ready to formulate the reduction algorithm. We consider one by one all the crossings and check for each of them if there exists a life disc born at it transforming the final curve of the youth disc according to Lemma 5. To make this algorithm to be very fast, in the next section we apply the idea due to Dynnikov.

5. Lamination coordinates of final curves. Let us denote by I^{∗} the union of I with all the segments [p_{i}, ±\sqrt{−1} ], i = 1, …, n. We define that Γ is transverse to I^{∗} and reduced with respect to I^{∗} in the same way as in Section 3 (no digons between Γ and I^{∗}). So, let Γ be reduced with respect to I^{∗}. We define the lamination coordinates of Γ as the sequence (c_{0}, a_{1}, b_{1}, c_{1}, a_{2}, b_{2}, c_{2}, …, a_{n}, b_{n}, c_{n}),

a_{i} = #(Γ∩]p_{i}, \sqrt{−1}[ ), b_{i} = #(Γ∩]p_{i}, −\sqrt{−1}[ ), c_{i} = #(Γ∩]p_{i}, p_{i+1}[ ).

If Γ = [p_{i}, p_{i+1}], we set c_{i} = −1. Let us set also a_{0} = b_{0} = a_{n+1} = b_{n+1} = 0.

Lemma 6. (Compare with Dynnikov’s formulas [5; III.4.20]). Let α be a singular braid and let (c_{0}, a_{1}, b_{1}, c_{1}, …, a_{n}, b_{n}, c_{n}) be the lamination coordinates of the final curve of some youth disc for α born at q. Then the lamination coordinates of the final curve of a youth disc for ασ_{i}^{ε}, ε = ±1, born at q, are (c′_{0}, a′_{1}, b′_{1}, c′_{1}, …, a′_{n}, b′_{n}, c′_{n}), where a′_{k} = a_{k}, b′_{k} = b_{k} for k ≠ i, i + 1, c′_{k} = c_{k} for k ≠ i − 1, i + 1, and the numbers c′_{i−1}, a′_{i}, b′_{i}, a′_{i+1}, b′_{i+1}, c′_{i+1} are defined as follows. If ε = 1 then

c′_{i−1} = max(c_{i−1} + b_{i+1}, c_{i} + b_{i−1}) − b_{i}, c′_{i+1} = max(c_{i} + a_{i+2}, c_{i+1} + a_{i}) − a_{i+1};

\{ \begin{matrix}a′_{i} = max(c′_{i−1} + a_{i}, c_{i} + a_{i−1}) − c_{i−1} \\ b′_{i+1} = max(c′_{i+1} + b_{i+1}, c_{i} + b_{i+2}) − c_{i+1} \end{matrix}  \{ \begin{matrix}a′_{i+1} = a_{i} \\ b′_{i} = b_{i+1} \end{matrix}

If ε = −1 then (we swap a and b)

c′_{i−1} = max(c_{i−1} + a_{i+1}, c_{i} + a_{i−1}) − a_{i}, c′_{i+1} = max(c_{i} + b_{i+2}, c_{i+1} + b_{i}) − b_{i+1};

\{ \begin{matrix}b′_{i} = max(c′_{i−1} + b_{i}, c_{i} + b_{i−1}) − c_{i−1} \\ a′_{i+1} = max(c′_{i+1} + a_{i+1}, c_{i} + a_{i+2}) − c_{i+1} \end{matrix}  \{ \begin{matrix}b′_{i+1} = b_{i} \\ a′_{i} = a_{i+1} \end{matrix}

6. The reduction algorithm. Let α = α_{0}u_{0}u_{1} ⋯ ∈ B_{n}(X ∪ X^{−1}) with u_{k} ∈ Σ ∪ Σ^{−1} ∪ X ∪ X^{−1} and u_{0} = x_{i}^{ε} for some x ∈ X, ε = ±1. We must check if there exists a life disc for α born at u_{0}. We shall compute the lamination coordinates and the endpoints p and q of the final curves of youth discs born at u_{0} (if they exist) successively for α_{0}u_{0}, α_{0}u_{0}u_{1}, etc., using Lemmas 5 and 6. For α_{0}u_{0}, we have p = p_{i}, q = p_{i+1}, c_{i} = −1 and all the other coordinates are zero. When we add u_{k} to our word, we do the following:

If u_{k} = σ_{j}^{±1}, we compute new coordinates (by Lemma 6) and new endpoints p, q (transposing p_{j} and p_{j+1}), and we pass to u_{k+1}.

If u_{k} = y_{j}^{δ} and c_{j} = −1, then we finish the computation and conclude that the life disc exists (if y = x and δ = −ε, in this case u_{k} is the death point) or does not exist (otherwise).

If u_{k} = y_{j}^{δ}, c_{j} = 0, and {p, q} ∩ {p_{j}, p_{j+1}} = ∅, we do nothing and pass to u_{k+1}.

If u_{k} = y_{j}^{δ}, c_{j} ≥ 0, and either c_{j} ≥ 1 or {p, q} ∩ {p_{j}, p_{j+1}} ≠ ∅, we finish the computation and conclude that the life disc does not exist.

Remark. In fact, the enpoints p, q are determined by the lamination coordinates. To find them, it suffices to find the two triples among (a_{i}, a_{i+1}, c_{i}) and (b_{i}, b_{i+1}, c_{i}), i = 0, …, n, for which the triangle inequality fails.

If we have treated all the u_{k}’s and the youth disc has survived, we conclude that the life disc does not exist.

If we found a life disc born at u_{0} and died at u_{k}, we just remove u_{0} and u_{k} from our word and continue the reduction. If there is no life disc, then the singular braid is reduced by Lemma 1.

References

1. J. Baez, Link invariants and perturbation theory, Lett. Math. Phys. 2 (1992), 41–51.

2. J. Birman, New points of view in knot theory, Bull. A.M.S. (N.S.) 28 (1993), 253–287.

3. R. Corran, A normal form for a class of monoids including the singular braid monoid, J. of Algebra 223 (2000), 256–282.

4. R. Corran, Conjugacy in singular Artin monoids, Preprint, 1999, http://www.maths.unsw.edu.au/ ruth/papers.html.

5. P. Dehornoy, Braids and self-distributivity, Progress in Math., vol. 192, Birkhäuser, 2000.

6. R. Fenn, M.T. Greene, D. Rolfsen, C. Rourke, B. Wiest, Ordering the braid groups, Pacific J. Math. 191 (1999), 49–74.

7. R. Fenn, E. Keyman, C. Rourke, The singular braid monoid embeds in a group, J. Knot Theory and Ramifications 7 (1998), 881–892.

Laboratoire E.Picard, UFR MIG, Université Paul Sabatier, 118 route de Narbonne, 31062 Toulouse, France

   E-mail address: orevkov@picard.ups-tlse.fr
   Personal web-page: http://picard.ups-tlse.fr/˜ orevkov