Conjugacy in Garside groups. III: Periodic braids. (English) Zbl 1165.20031

Summary: An element in Artin’s braid group \(B_n\) is said to be periodic if some power of it lies in the center of \(B_n\). In this paper we prove that all previously known algorithms for solving the conjugacy search problem in \(B_n\) are exponential in the braid index \(n\) for the special case of periodic braids. We overcome this difficulty by putting to work several known isomorphisms between Garside structures in the braid group \(B_n\) and other Garside groups. This allows us to obtain a polynomial solution to the original problem in the spirit of the previously known algorithms.
This paper is the third in a series of papers by the same authors about the conjugacy problem in Garside groups [for part II cf. Groups Geom. Dyn. 2, No. 1, 13-61 (2008; Zbl 1163.20023)]. They have a unified goal: the development of a polynomial algorithm for the conjugacy decision and search problems in \(B_n\), which generalizes to other Garside groups whenever possible. It is our hope that the methods introduced here will allow the generalization of the results in this paper to all Artin-Tits groups of spherical type.


20F36 Braid groups; Artin groups
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20E45 Conjugacy classes for groups
20F05 Generators, relations, and presentations of groups
68W30 Symbolic computation and algebraic computation


Zbl 1163.20023


Full Text: DOI arXiv Link


[1] Artin, E., Theorie der Zöpfe, Abh. Math. Sem. Hamburg, 4, 47-72 (1925) · JFM 51.0450.01
[2] Bessis, D., The dual braid monoid, Ann. Sci. École Norm. Sup. (4), 36, 5, 647-683 (2003) · Zbl 1064.20039
[3] Bessis, D.; Digne, F.; Michel, J., Springer theory in braid groups and the Birman-Ko-Lee monoid, Pacific J. Math., 205, 287-310 (2002) · Zbl 1056.20023
[4] Birman, J.; Ko, K. Y.; Lee, S. J., A new approach to the word and conjugacy problems in the braid groups, Adv. Math., 139, 2, 322-353 (1998) · Zbl 0937.20016
[5] Birman, J.; Ko, K. Y.; Lee, S. J., The infimum, supremum and geodesic length of a braid conjugacy class, Adv. Math., 164, 1, 41-56 (2001) · Zbl 1063.20039
[6] Birman, J.; Gebhardt, V.; González-Meneses, J., Conjugacy in Garside groups I: Cycling, powers and rigidity, Groups, Geometry and Dynamics, in press, arXiv: · Zbl 1160.20026
[7] Birman, J.; Gebhardt, V.; González-Meneses, J., Conjugacy in Garside groups II: Structure of the ultra summit set, Groups, Geometry and Dynamics, in press, arXiv: · Zbl 1163.20023
[8] Bosma, W.; Cannon, J.; Playoust, C., The MAGMA algebra system I: The user language, J. Symbolic Comput., 24, 235-265 (1997), see also the Magma homepage at · Zbl 0898.68039
[9] Bourbaki, N., Lie Groups and Lie Algebras (2002), Springer-Verlag: Springer-Verlag Berlin, (Chapters 4-6)
[10] Brieskorn, E., Die Fundamentalgruppe des Raumes der regulären Orbits einer endlichen komplexen Spiegelungsgruppe, Invent. Math., 12, 57-61 (1971) · Zbl 0204.56502
[11] Constantin, A.; Kolev, B., The theorem of Kerékjártó on periodic homeomorphisms of the disc and the sphere, Enseign. Math. (2), 40, 193-204 (1994) · Zbl 0852.57012
[12] Coxeter, H. S.M., Discrete groups generated by reflections, Ann. of Math. (2), 35, 3, 588-621 (1934) · Zbl 0010.01101
[13] Crisp, J., Injective maps between Artin groups, (Geometric Group Theory Down Under. Geometric Group Theory Down Under, Canberra, 1996 (1999), de Gruyter: de Gruyter Berlin), 119-137 · Zbl 1001.20034
[14] Dehornoy, P.; Paris, L., Gaussian groups and Garside groups, two generalizations of Artin groups, Proc. London Math. Soc., 79, 3, 569-604 (1999) · Zbl 1030.20021
[15] Digne, F.; Michel, J., Endomorphisms of Deligne-Lusztig varieties, Nagoya Math. J., 183, 35-103 (2006) · Zbl 1119.20008
[16] Eilenberg, S., Sur les transformations périodiques de la surface de la sphère, Fund. Math., 22, 28-41 (1934) · JFM 60.1228.02
[17] ElRifai, E.; Morton, H., Algorithms for positive braids, Q. J. Math. Oxford (2), 45, 180, 479-497 (1994) · Zbl 0839.20051
[18] Epstein, D.; Cannon, J.; Holt, F.; Levy, S.; Patterson, M.; Thurston, W., Word Processing in Groups (1992), Jones and Bartlett: Jones and Bartlett Boston, MA · Zbl 0764.20017
[19] Garside, F., The braid group and other groups, Q. J. Math. Oxford, 20, 235-254 (1969) · Zbl 0194.03303
[20] Gebhardt, V., A new approach to the conjugacy problem in Garside groups, J. Algebra, 292, 1, 282-302 (2005) · Zbl 1105.20032
[21] González-Meneses, J., The \(n\) th root of a braid is unique up to conjugacy, Algebr. Geom. Topol., 3, 1103-1118 (2003) · Zbl 1063.20041
[22] Kerckhoff, S. P., The Nielsen realization problem, Ann. of Math. (2), 117, 2, 235-265 (1983) · Zbl 0528.57008
[23] de Kerékjártó, B., Über die periodischen Transformationen der Kreisscheibe und der Kugelfläche, Math. Ann., 80, 3-7 (1919) · JFM 47.0526.05
[24] Lee, E.-K.; Lee, S. J., Conjugacy classes of periodic braids, preprint, arXiv:
[25] Morton, H.; Hadji, R., Conjugacy for positive periodic permutation braids, Fund. Math., 188, 155-166 (2005) · Zbl 1086.57007
[26] Magnus, W.; Karass, A.; Solitar, D., Combinatorial Group Theory (1966), John Wiley and Sons, Dover
[27] Reiner, V., Non-crossing partitions for classical reflection groups, Discrete Math., 177, 195-222 (1997) · Zbl 0892.06001
[28] Shi, J.-Y., The enumeration of Coxeter elements, J. Algebraic Combin., 6, 2, 161-171 (1997) · Zbl 0871.05030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.