QUASIPOSITIVITY PROBLEM FOR 3-BRAIDS

S.Yu. Orevkov

Abstract. A braid is called quasipositive if it is a product of conjugates of standard generators of the braid group. We present an algorithm deciding if a given braid with three strings is quasipositive or not. The complexity (the time of work) of our algorithm is O(n^{k}) where n is the length of the word in standard generators representing the braid and k is the algebraic length of the braid. The algorithm is based on the Garside normal form.

The problem of quasipositivity in braid groups is motivated by the topology of plane real algebraic curves (16th Hilbert’s problem). In particular, our result can be interpreted as a classification of trigonal real pseudoholomorphic curves on rational ruled surfaces.

Let G be a group and X a fixed set of its elements which we shall call positive generators. An element g ∈ G is called X -quasipositive if g = ∏_{j} a_{j}x_{j}a_{j}^{−1} where a_{j} ∈ G and x_{j} ∈ X. We shall give a solution for the quasipositivity problem (i.e. we shall present an algorithm deciding if a given element is quasipositive or not) for a free group with any number of generators (Sect 1) and for the group of braids with three strings (the rest of the paper).

The complexity (the time of work) of our algorithm is O(n^{k+1}) where n is the length and k is the algebraic length (the exponent sum) of the word.

The result on the free group is not new (see Remark 1.3) but we present it here because our proof of this result serves as a model of the proof for 3-braids. The main ingredient of the proof is the Garside normal form of a braid.

The term ”quasipositive braid” was introduced by Lee Rudolph [5]. For us, the main motivation of the quasipositivity problem comes from the topology of plane real algebraic curves (see details in [2,3]). A necessary condition for existence of a real algebraic curve realizing a given isotopy type, is the quasipositivity of a certain braid. If one enlarge the class of real algebraic curves up to the class of real pseudoholomorphic curves, then this condition becomes necessary and sufficient. In particular, the result of this note can be interpreted as a classification of trigonal real pseudoholomorphic curves on rational ruled surfaces.

1. Quasipositivity problem in free group. Let X be any set and F_{X} be the free group generated by X. We shall call X -quasipositive elements just quasipositive. In the set of words composed of the characters ”[”, ”*”, ”]”, we define a subset of regular bracket structures (RBS) recursively: the empty word and the word * are RBS; if a and b are RBS then ab and [a] also are.

Typeset by AMS-TEX

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

Key words and phrases. Braid group, quasipositive braids.

Let X^{−1} = {x^{−1} | x ∈ X }. A word x_{1}x_{2} … x_{n} in x_{j} ∈ X ∪ X^{−1} is called quasipositive if there exist a RBS u_{1}u_{2} … u_{n} which agrees with w, i.e. such that

(1) if u_{j} = * then x_{j} ∈ X;

(2) if u_{j} is the bracket matching to u_{i} then x_{j} = x_{i}^{−1}.

Proposition 1.1. Any word representing a quasipositive element of F_{X}, is quasipositive.

Proof. By definition, any quasipositive element can be represented by a quasipositive word ∏ a_{j}x_{j}a_{j}^{−1}. If a word w is obtained by inserting xx^{−1} into a quasipositive word then w is also quasipositive (one should just insert ”[]” into the corresponding place of the RBS). It remains to prove that if a word w′ is obtained by removing xx^{−1} or x^{−1}x from a quasipositive word w then w′ is quasipositive.

Let w = x_{1} … x_{n}. Let u_{1} … u_{n} be the corresponding RBS and w′ is obtained from w by removing x_{i}x_{i+1} where either x_{i} = x and x_{i+1} = x^{−1}, or x_{i} = x^{−1} and x_{i+1} = x for some x ∈ X. Let us consider separately all the possibilities for the word u_{i}u_{i+1}.

Case 1. ”**”. Impossible because x and x^{−1} cannot belong both to X.

Case 2. ”*]” or ”*[” (the case of ”[*” and ”]*” is analogous). We have x_{i} = x ∈ X, x_{i+1} = x^{−1}. Let u_{j} be the bracket matching to u_{i+1}. Then we have x_{j} = x, and the word obtained from u_{1} … u_{n} by deleting u_{i}u_{i+1} and replacing u_{j} with ”*”, is an RBS which agrees with w′.

Case 3. ”[]” or ”][”. Deleting u_{i}u_{i+1} yields an RBS which agrees with w′. Case 4. ”[[” (the case of ”]]” is analogous). Let u_{j} = u_{k} = ] , j < k, be the

brackets matching to u_{i} and u_{i+1}. Removing u_{i}u_{i+1} and replacing u_{j} with ”[”, we obtain an RBS which agrees with w′.

To check that the obtained words are RBS, it is convenient to use the following criterion. A word in ”[”, ”*”, ”]” is an RBS if and only if the number of ”[” is equal to the number of ”]”, and for any initial subword, the number of ”[” is not less than the number of ”]”. □

Corollary 1.2. A word over the alphabet X ∪X^{−1} defines a quasipositive element if and only if after removing some positive generators one obtain a word representing the unit of the group F_{X}.

Remark 1.3. According to a result of Blank [4], the question of extendibility of an immersion S^{1} → R^{2} up to an immersion D^{2} → R^{2} (where D^{2} is a disk and S^{1} is its boundary) can be reduced to the quasipositivity problem in a free group. In [4], it is given an algorithm of recognizing quasipositive words, thus, our Proposition 1.1 is not a new result.

2. Garside normal form in the group of braids with three strings [1]. Let B_{3} = ⟨σ_{1}, σ_{2} | σ_{1}σ_{2}σ_{1} = σ_{2}σ_{1}σ_{2}⟩ be the group of braids with three strings. Let Δ be the Garside element: Δ = σ_{1}σ_{2}σ_{1}. Let 𝔯 : B_{3} → B_{3} be the automorphism σ_{1} ↦ σ_{2}, σ_{2} ↦ σ_{1}. It is easy to check that

Δβ = 𝔯(β)Δ,  β ∈ B_{3}.  (1)

Let 𝔞 be the homomorphism of B_{3} to the additive group of integers Z, such that 𝔞(σ_{1}) = 𝔞(σ_{2}) = 1, i.e. 𝔞(β) is the exponent sum (the algebraic length) of β.

Let B_{3}^{+} be the submonoid (recall that monoid is a semigroup with the unit element) of B_{3} generated by σ_{1}, σ_{2}. Elements of B_{3}^{+} are called positive braids. Let α, β ∈ B_{3}^{+}. Let us say that β is left (resp., right) divisible by α if there exists γ ∈ B_{3}^{+} such that β = αγ (resp., β = γα). A word in σ_{1}, σ_{2}, is called positive.

Lemma 2.1. (see [1; Theorem 4]). Two positive words are equal in B_{3} if and only if one of them can be obtained from the other by applying the relations σ_{1}σ_{2}σ_{1} = σ_{2}σ_{1}σ_{2}.

Lemma 2.2. A positive word is left or right divisible by Δ if and only if it contains the subword σ_{1}σ_{2}σ_{1} or σ_{2}σ_{1}σ_{2}.

Proof. If w contains such a subword then w = αΔβ = Δ 𝔯(α)β = α 𝔯(β)Δ by (1). Otherwise, by Lemma 2.1, the word w cannot be equal in B_{3} to any other positive word. □

Corollary 2.3. An element of B_{3}^{+} not divisible by Δ can be represented by a positive word in a unique way.

Definition. A Garside decomposition of a braid β ∈ B_{3} is its presentation

β = β_{+}Δ^{m},  β_{+} ∈ B_{3}^{+}.  (2)

If β_{+} is not divisible by Δ then the decomposition (2) is called the Garside normal form of β. In this case, m is called the power of β. By Corollary 2.3, the Garside normal form is uniquely defined.

To find a Garside decomposition, we replace each occurrence of σ_{1}^{−1} with σ_{2}σ_{1}Δ^{−1}, and σ_{2}^{−1} with σ_{1}σ_{2}Δ^{−1}, and then push all Δ^{−1} to the right using (1). To find further the Garside normal form, one should successively replace all subwords σ_{1}σ_{2}σ_{1} and σ_{2}σ_{1}σ_{2} with Δ, and push them to the right using (1).

3. Quasipositivity problem in the group of braids with three strings. A braid with three strings (an element of B_{3}) is called quasipositive if it is X -quasi-positive for X = {σ_{1}, σ_{2}}. It is clear that if a braid admits a decomposition (2) with a non-negative m then it is quasipositive. A criterion of the quasipositivity in the case of negative m is as follows.

Proposition 3.1. Let β = β_{+}Δ^{m} where β_{+} is a positive word (i.e. a word in σ_{1}, σ_{2}), and m ≤ 0. The braid β is quasipositive if and only if one can delete some letters from β_{+} so that the obtained word is equal in B_{3}^{+} to the word Δ^{−m}.

This proposition follows immediately from Proposition 3.3 below. It provides the following algorithm to decide if a given word in σ_{1}^{±1}, σ_{2}^{±1} represents a quasipositive braid. Let k be the algebraic length of the braid.

Algorithm 3.2.

(1) Compute the Garside normal form β_{+}Δ^{m} of the given braid β.

(2) Try to remove k letters from β_{+} in all possible ways, each time computing the Garside normal form of the obtained braid.

(3) If we obtain at least once the trivial braid on the step (2) then the braid β is quasipositive. Otherwise it is not.

It is clear that the complexity (the time of work) of this algorithm is O(n^{k+1}) where n is the length of the initial word. The rest of the section is devoted to the proof of Proposition 3.1.

In the set of words composed of the characters ”[”, ”|”, ”]”, ”*”, let us define a subset of regular bracket structures with delimiters (RBSD) recursively as follows: the empty word and the word ∗ are RBSD; if a and b are RBSD then ab and [a|b] also are. If a is an RBSD then its wight ℓ(a) is defined as the number of occurrences of the character ”|”. It is clear that any occurrence of one of the characters ”[”, ”|”, or ”]” into an RBSD w, uniquely determines the occurrences of the other two characters such that w = a[b|c]d where b, c, and ad are RBSD. Such a mutual occurrance of ”[”, ”|”, and ”]” is called a regular mutual occurrance.

Let us say that a positive word x_{1} … x_{n}, x_{j} ∈ {σ_{1}, σ_{2}}, agrees with an RBSD u_{1} … u_{n}, if for any regular mutual ocuurrance of u_{i} = [ , u_{j} = | , u_{k} = ] , into u_{1} … u_{n} = au_{i}bu_{j}cu_{k}d = a[b|c]d, we have either

x_{i} = σ_{1}, x_{j} = 𝔯^{ℓ(b)}(σ_{2}), x_{k} = 𝔯^{ℓ(bc)}(σ_{1}),

or

x_{i} = σ_{2}, x_{j} = 𝔯^{ℓ(b)}(σ_{1}), x_{k} = 𝔯^{ℓ(bc)}(σ_{2}),

Proposition 3.3. Let b = wΔ^{m} where w is a positive word and m ≤ 0. The braid b is quasipositive if and only if there exists an RBSD of the weight −m which agrees with w.

This statement easily follows from the results of Section 2 and the following lemma.

Lemma 3.4. Let w = x_{1} … x_{n} be a positive word which agrees with some RBSD of a non-zero weight. Suppose that w contains a subword x_{i}x_{i+1}x_{i+2} = σ_{1}σ_{2}σ_{1}. Then there exists an RBSD u_{1} … u_{n} of the same weight agreeing with w such that u_{i}u_{i+1}u_{i+2} = [|] .

Proof. In the RBSD agreeing with w, let us consider the subword v which corresponds to x_{i}x_{i+1}x_{i+2}. If v = ∗ ∗ ∗, then we replace v with [|] and we replace an arbitrary regular mutual occurrance … [ … | …] … with ⋯ ∗ ⋯ ∗ ⋯ ∗ · · ·.

If v intersects only with one regular mutual occurrance of [|] , then we replace v with [|] , and we replace with ∗ each element of this regular mutual occurrance which does not belong to v.

If v intersects with more than one regular mutual occurrance of [|] , then we shall consider separately all possibilities for v up to a symmetry:

1 *2 [1 [ … 2 | … 1 ] … 2 | … 1 ] ⟶ 1 [2 |1 ] … 2 * … 1 [ … 2 | … 1 ]
1 [ … 1 *2 |1 [ … 2 | … 1 ] … 2 ] ⟶ 1 * … 1 [2 |1 ] … 2 [ … 1 | … 2 ]
2 [ … 1 | … 1 *2 ]1 [ … 2 | … 1 ] ⟶ 2 [ … 1 * … 1 [2 |1 ] … 2 | … 1 ]
1 [ … 2 [ … 1 | … 1 *2 ]1 | … 2 ] ⟶ 1 [ … 2 | … 1 ] … 1 [2 |1 ] … 2 *
2 [ … 1 | … 2 [ … 1 | … 1 *2 ]1 ] ⟶ 2 [ … 1 | … 2 ] … 1 * … 1 [2 |1 ]
2 [ … 1 |2 *1 [ … 2 | … 1 ] … 1 ] ⟶ 2 [ … 1 [2 |1 ] … 2 | … 1 ] … 1 *
1 [ … 2 | … 1 ]2 *1 [ … 2 | … 1 ] ⟶ 1 [ … 2 | … 1 [2 |1 ] … 2 ] … 1 *

1 [2 [1 [ … 2 | … 1 ] … 2 | … 1 ] … 2 | … 1 ] ⟶ 1 [2 |1 ] … 2 [ … 1 | … 2 ] … 1 [ … 2 | … 1 ]
2 [ … 1 |2 [1 [ … 2 | … 1 ] … 2 | … 1 ] … 2 ] ⟶ 2 [ … 1 [2 |1 ] … 2 | … 1 ] … 2 [ … 1 | … 2 ]
1 [ … 2 | … 1 ]2 [1 [ … 2 | … 1 ] … 2 | … 1 ] ⟶ 1 [ … 2 [ … 1 [2 |1 ] … 2 | … 1 ] … 2 | … 1 ]
2 [ … 1 [ … 2 | … 1 ]2 |1 [ … 2 | … 1 ] … 2 ] ⟶ 2 [ … 1 | … 2 ] … 1 [2 |1 ] … 2 [ … 1 | … 2 ]

1 [2 [1 | … 2 ] … 1 | … 2 ] ⟶ 1 [2 |1 ] … 2 [ … 1 | … 2 ]
2 [ … 1 |2 [1 | … 2 ] … 1 ] ⟶ 2 [ … 1 [2 |1 ] … 2 | … 1 ]
2 [ … 1 |2 ]1 [ … 2 | … 1 ] ⟶ 2 [ … 1 [2 |1 ] … 2 | … 1 ]

To simplify notation, we omit 𝔯^{ℓ(...)} in the above list of modifications and we write 1 and 2 instead of σ_{1} and σ_{2}. For example, the first line of the list should be understood as

{σ_{1} \atop *}{σ_{2} \atop [}{σ_{1} \atop [} a 𝔯^{ℓ(ã)}{( \atop |}σ_{2}) b 𝔯^{ℓ(ãb̃)}{( \atop ]}σ_{1}) c 𝔯^{ℓ(ãb̃c̃)}{( \atop |}σ_{2}) d 𝔯^{ℓ(ãb̃c̃d̃)}{( \atop ]}σ_{1})
↓
{σ_{1} \atop [}{σ_{2} \atop |}{σ_{1} \atop ]} a 𝔯^{ℓ(ã)}(*σ_{2}) b 𝔯^{ℓ(ãb̃)}{( \atop [}σ_{1}) c 𝔯^{ℓ(ãb̃c̃)}{( \atop |}σ_{2}) d 𝔯^{ℓ(ãb̃c̃d̃)}{( \atop ]}σ_{1}) ,

where a, b, c, d are arbitrary words in σ_{1}, σ_{2}, and ã, b̃, c̃, d̃ the corresponding RBSD (ã, b̃, c̃, d̃ are not changed under the modification). □

References

1. F.A. Garside, The braid group and other groups, Quart. J. Math. 20 (1969), 235–254.

2. S.Yu. Orevkov, Link theory and oval arrangements of real algebraic curves, Topology 38 (1999), 779–810.

3. S.Yu. Orevkov, Classification of Flexible M-curves of Degree 8 up to Isotopy, GAFA – Geom. and Funct. Anal. 12 (2002), 723–755.

4. V. Poenaru, Extension des immersions en codimension 1 (d’après Samuel Blank), Séminaire Bourbaki, 20e année 1967/68, exposé no. 342, 1-33.

5. L. Rudolph, Algebraic functions and closed braids, Topology 22 (1983), 191-202.

Laboratoire Emile Picard, UFR MIG, Univ. 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

Steklov Mathematical Institute, ul. Gubkina 8, Moscow, 119991 Russia