Algorithms for positive braids. (English) Zbl 0839.20051

Elrifai, Elsayed A.; Morton, H. R.

Q. J. Math., Oxf. II. Ser. 45, No. 180, 479-497 (1994).

The elements of the braid group \(B_n= \langle \sigma_1, \dots, \sigma_{n-1}\); \(\sigma_i \sigma_j= \sigma_j \sigma_i\) \((|i-j|>1)\), \(\sigma_i \sigma_j \sigma_i= \sigma_j \sigma_i \sigma_j\) \((|i-j|<1)\rangle\) which can be written as a word in positive powers of the generators \(\sigma_1, \dots, \sigma_{n-1}\) are called positive braids. For braids \(A\), \(B\) write \(A\leq B\) when \(B= C_1 AC_2\) for some positive braids \(C_1\), \(C_2\). The authors call a positive braid \(F\) a positive permutation braid if \(F\leq \Delta_n\), where \(\Delta_n= \sigma_1 \dots \sigma_{n-1} \sigma_1\dots \sigma_{n-2} \dots \sigma_1 \sigma_2 \sigma_1\). The authors study the properties of positive permutation braids. Particularly, they give two canonical forms for positive braids as products of positive permutation braids. This result enables the authors to simplify Garside’s solution of the word and conjugacy problems in \(B_n\). The authors also give algorithms deciding (given a positive braid \(F\) and integer \(k\)): 1) whether \(\Delta^k_n\leq F\); 2) whether \(F\leq \Delta^k_n\). It should be noted that similar results about positive permutation braids were obtained and the same canonical form was given in the papers of G. S. Makanin [Mat. Sb., Nov. Ser 86 (128), 171-179 (1971; Zbl 0229.20035)] and V. B. Styshnev [Izv. Akad. Nauk SSSR, Ser. Mat. 42, 1120-1131 (1978; Zbl 0402.20029)].

Reviewer: A.M.Akimenkov (Krasnogorsk)

MSC:

20F36	Braid groups; Artin groups
20F10	Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20F05	Generators, relations, and presentations of groups

Keywords:

braid groups; generators; positive braids; positive permutation braids; canonical forms; word problem; conjugacy problem