A new algorithm for solving the word problem in braid groups (Q1604340): Difference between revisions

Artin's braid group \(B_n\) is the group presented in generators \(\sigma_1,\dots,\sigma_{n-1}\) by the defining relations \(\sigma_i\sigma_j=\sigma_j\sigma_i\) for \(i+1<j\), and \(\sigma_i\sigma_{i+1}\sigma_i=\sigma_{i+1}\sigma_i\sigma_{i+1}\) for \(i<n-1\). The word problem in \(B_n\) is solvable; the first algorithm was given by \textit{F.~A. Garside} [Q. J. Math., Oxf. II. Ser. 20, 235-254 (1969; Zbl 0194.03303)]. Since then many other algorithms were found; they were based on a suitable choice of generators in \(B_n\) and transforming a given braid to a certain normal form in those generators. The fastest known algorithm is of complexity \(O(nl^2)\), where \(l\) is the length of the braid word. The authors suggest a new algorithm for solving the word problem in \(B_n\) based on the topological definition of \(B_n\), due to \textit{B.~Moishezon} and \textit{M.~Teicher} [Contemp.~Math. 78, 425-455 (1988; Zbl 0674.14019)]. Let \(D\) be a closed disk, \(K\) a set of \(n\) points inside \(D\), and \(u\in\partial D\). The fundamental group \(G=\pi_1(D\setminus K,u)\) is known to be a free group with \(n\) generators. Any diffeomorphism of \(D\), which is the identity on \(\partial G\) and setwise fixes \(K\), induces an automorphism of \(G\), and the group \(\mathcal B\) of all such diffeomorphisms acts on \(G\) by automorphisms. Let \(B_n[D,K]\) be the group \(\mathcal B\) modulo the kernel of the action. Moishezon and Teicher proved that \(B_n[D,K]\simeq B_n\), constructing \(n-1\) generators in \(B_n[D,K]\) which witness the isomorphism. The free bases of \(G\), which arise from the \(n\)-tuples of loops of a certain type, play a special role and are called geometric bases. The group \(B_n(D,K)\) regularly acts on the geometric bases of \(G\). In order to determine whether two words are equal in \(B_n[D,K]\), one needs to check whether their actions on the elements of a chosen geometric basis are identical. To make the checking procedure efficient, the authors produce a computerized presentation of geometric bases, and two algorithms: for computing the action, and for reducing a presentation into a unique form. This gives a solution of the word problem in the braid group. The authors note that their algorithm, although not better in complexity, is faster in comparison with known algorithms for short braid words, and is almost independent of the number of strings in the braids.