Polynomial braid combing

González-Meneses, Juan; Silvero, Marithania

doi:10.1090/mcom/3392

Polynomial braid combing
HTML articles powered by AMS MathViewer

by Juan González-Meneses and Marithania Silvero HTML | PDF

Math. Comp. 88 (2019), 2027-2045 Request permission

Abstract:

Braid combing is a procedure defined by Emil Artin to solve the word problem in braid groups. It is well known to have exponential complexity. In this paper, we use the theory of straight line programs to give a polynomial algorithm which performs braid combing. This procedure can be applied to braids on surfaces, providing the first algorithm (to our knowledge) which solves the word problem for braid groups on surfaces with boundary in polynomial time and space.

In the case of surfaces without boundary, braid combing needs to use a section from the fundamental group of the surface to the braid group. Such a section was shown to exist by Gonçalves and Guaschi, who also gave a geometric description. We propose an algebraically simpler section, which we describe explicitly in terms of generators of the braid group, and we show why the above procedure to comb braids in polynomial time does not work in this case.

References

E. Artin, Theory of braids, Ann. of Math. (2) 48 (1947), 101–126. MR 19087, DOI 10.2307/1969218
Valerij G. Bardakov and Paolo Bellingeri, On residual properties of pure braid groups of closed surfaces, Comm. Algebra 37 (2009), no. 5, 1481–1490. MR 2526317, DOI 10.1080/00927870802068664
Paolo Bellingeri, On presentations of surface braid groups, J. Algebra 274 (2004), no. 2, 543–563. MR 2043362, DOI 10.1016/j.jalgebra.2003.12.009
Paolo Bellingeri, Sylvain Gervais, and John Guaschi, Lower central series of Artin-Tits and surface braid groups, J. Algebra 319 (2008), no. 4, 1409–1427. MR 2383053, DOI 10.1016/j.jalgebra.2007.10.023
Joan S. Birman, On braid groups, Comm. Pure Appl. Math. 22 (1969), 41–72. MR 234447, DOI 10.1002/cpa.3160220104
Joan S. Birman, Braids, links, and mapping class groups, Annals of Mathematics Studies, No. 82, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1974. MR 0375281
Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. MR 1440179, DOI 10.1007/978-3-662-03338-8
Edward Fadell and James Van Buskirk, The braid groups of $E^{2}$ and $S^{2}$, Duke Math. J. 29 (1962), 243–257. MR 141128
L. Gasieniec, M. Karpinski, W. Plandowski, and W. Rytter. Efficient algorithms for Lempel-Ziv encoding. Proc. 4th Scandinavian Workshop on Algorithm Theory (SWAT 1–794), Lecture Notes in Comput. Sci. 1097, Springer-Verlag, Berlin 1996, 392-403.
Richard Gillette and James Van Buskirk, The word problem and consequences for the braid groups and mapping class groups of the $2$-sphere, Trans. Amer. Math. Soc. 131 (1968), 277–296. MR 231894, DOI 10.1090/S0002-9947-1968-0231894-7
D. L. Gonçalves and J. Guaschi, On the structure of surface pure braid groups, J. Pure Appl. Algebra 186 (2004), no. 2, 187–218. Corrected reprint of: “On the structure of surface pure braid groups” [J. Pure Appl. Algebra 182 (2003), no. 1, 33–64; MR1977999]. MR 2025598, DOI 10.1016/S0022-4049(03)00163-4
Daciberg Lima Gonçalves and John Guaschi, The braid groups of the projective plane and the Fadell-Neuwirth short exact sequence, Geom. Dedicata 130 (2007), 93–107. MR 2365780, DOI 10.1007/s10711-007-9207-z
Daciberg Lima Gonçalves and John Guaschi, Braid groups of non-orientable surfaces and the Fadell-Neuwirth short exact sequence, J. Pure Appl. Algebra 214 (2010), no. 5, 667–677. MR 2577674, DOI 10.1016/j.jpaa.2009.07.009
Juan González-Meneses, New presentations of surface braid groups, J. Knot Theory Ramifications 10 (2001), no. 3, 431–451. MR 1825967, DOI 10.1142/S0218216501000949
John Guaschi and Daniel Juan-Pineda, A survey of surface braid groups and the lower algebraic $K$-theory of their group rings, Handbook of group actions. Vol. II, Adv. Lect. Math. (ALM), vol. 32, Int. Press, Somerville, MA, 2015, pp. 23–75. MR 3382024
Pierre de la Harpe, An invitation to Coxeter groups, Group theory from a geometrical viewpoint (Trieste, 1990) World Sci. Publ., River Edge, NJ, 1991, pp. 193–253. MR 1170367
Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. MR 1867354
Markus Lohrey, Word problems on compressed words, Automata, languages and programming, Lecture Notes in Comput. Sci., vol. 3142, Springer, Berlin, 2004, pp. 906–918. MR 2161070, DOI 10.1007/978-3-540-27836-8_{7}6
Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89, Springer-Verlag, Berlin-New York, 1977. MR 0577064
Wojciech Plandowski, Testing equivalence of morphisms on context-free languages, Algorithms—ESA ’94 (Utrecht), Lecture Notes in Comput. Sci., vol. 855, Springer, Berlin, 1994, pp. 460–470. MR 1328862, DOI 10.1007/BFb0049431
Saul Schleimer, Polynomial-time word problems, Comment. Math. Helv. 83 (2008), no. 4, 741–765. MR 2442962, DOI 10.4171/CMH/142
G. P. Scott, Braid groups and the group of homeomorphisms of a surface, Proc. Cambridge Philos. Soc. 68 (1970), 605–617. MR 268889, DOI 10.1017/s0305004100076593