Conjugacy in Garside groups. II: Structure of the ultra summit set. (English) Zbl 1163.20023

Summary: This paper is the second in a series in which the authors study the conjugacy decision problem (CDP) and the conjugacy search problem (CSP) in Garside groups.
The ultra summit set \(\text{USS}(X)\) of an element \(X\) in a Garside group \(G\) is a finite set of elements in \(G\), which is a complete invariant of the conjugacy class of \(X\) in \(G\). A fundamental question, if one wishes to find bounds on the size of \(\text{USS}(X)\), is to understand its structure. In this paper we introduce two new operations on elements \(Y\in\text{USS}(X)\), called ‘partial cycling’ and ‘partial twisted decycling’, and prove that if \(Y,Z\in\text{USS}(X)\), then \(Y\) and \(Z\) are related by sequences of partial cyclings and partial twisted decyclings. These operations are a concrete way to understand the minimal simple elements whose existence follows from the convexity property of ultra summit sets.
Using partial cycling and partial twisted decycling, we investigate the structure of a directed graph \(\Gamma_X\) determined by \(\text{USS}(X)\), and show that \(\Gamma_X\) can be decomposed into ‘black’ and ‘grey’ subgraphs. There are applications relating to the authors’ program for finding a polynomial solution to the CDP/CSP in the case of braids, which is outlined in the first paper of this series [ibid. 1, No. 3, 221-279 (2007; Zbl 1160.20026)]. A different application is to give a new algorithm for solving the CDP/CSP in Garside groups which is faster than all other known algorithms, even though its theoretical complexity is the same as that of the established algorithm using ultra summit sets. There are also applications to the theory of reductive groups.


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 1160.20026
Full Text: DOI arXiv


[1] D. Bessis, Finite complex reflection arrangements are K. ; 1/. Preprint, 2007. · Zbl 1372.20036
[2] M. Bestvina, Non-positively curved aspects of Artin groups of finite type. Geom. Topol. 3 (1999), 269-302. · Zbl 0998.20034
[3] J. S. Birman, V. Gebhardt and J. González-Meneses, Conjugacy in Garside groups I: cycling, powers and rigidity. Groups Geom. Dyn. 1 (2007), 221-279. · Zbl 1160.20026
[4] J. S. Birman, V. Gebhardt and J. González-Meneses, Conjugacy in Garside groups III: Periodic braids. J. Algebra 316 (2007), 746-776. · Zbl 1165.20031
[5] J. S. Birman, K. H. Ko, and S. J. Lee, A new approach to the word and conjugacy problems in the braid groups. Adv. Math. 139 (1998), 322-353. · Zbl 0937.20016
[6] J. S. Birman, K. H. Ko, and S. J. Lee, The infimum, supremum, and geodesic length of a braid conjugacy class. Adv. Math. 164 (2001), 41-56. · Zbl 1063.20039
[7] E. Brieskorn and K. Saito, Artin-Gruppen und Coxeter-Gruppen. Invent. Math. 17 (1972), 245-271. · Zbl 0243.20037
[8] R. Charney, Artin groups of finite type are biautomatic. Math. Ann. 292 (1992), 671-683. · Zbl 0736.57001
[9] R. Charney, J. Meier and K. Whittlesey, Bestvina’s normal form complex and the homology of Garside groups. Geom. Dedicata 105 (2004), 171-188. · Zbl 1064.20044
[10] A. Constantin and B. Kolev, The theorem of Kerékjártó on periodic homeomorphisms of the disc and the sphere. Enseign. Math. 40 (1994), 193-204. · Zbl 0852.57012
[11] P. Dehornoy and L. Paris, Gaussian groups and Garside groups, two generalisations of Artin groups. Proc. London Math. Soc. (3) 79 (1999), 569-604. · Zbl 1030.20021
[12] F. Digne and J. Michel, Endomorphisms of Deligne-Lusztig varieties. Nagoya Math. J. 183 (2006), 35-103. · Zbl 1119.20008
[13] S. Eilenberg, Sur les transformations périodiques de la surface de la sphère. Fund. Math. 22 (1934), 28-41. · Zbl 0008.37109
[14] E. Elrifai and H. Morton, Algorithms for positive braids. Quart. J. Math. Oxford Ser. (2) 45 (1994), 479-497. · Zbl 0839.20051
[15] D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson, and W. P. Thurston, Word processing in groups . Jones and Bartlett Publishers, Boston 1992. · Zbl 0764.20017
[16] N. Franco and J. González-Meneses, Conjugacy problem for braid groups and Garside groups. J. Algebra 266 (2003), 112-132. · Zbl 1043.20019
[17] F. Garside, The braid group and other groups. Quart. J. Math. Oxford Ser. (2) 20 (1969), 235-254. · Zbl 0194.03303
[18] V. Gebhardt, A new approach to the conjugacy problem in Garside groups. J. Algebra 292 (2005), 282-302. · Zbl 1105.20032
[19] J. González-Meneses, The nth root of a braid is unique up to conjugacy. Algebr. Geom. Topol. 3 (2003), 1103-1118. · Zbl 1063.20041
[20] B. von Kerékjártó, Über die periodischen Transformationen der Kreisscheibe und der Kugelfläche. Math. Ann. 80 (1919), 36-38. · JFM 47.0526.05
[21] J. Michel, A note on words in braid monoids. J. Algebra 215 (1999), 366-377. · Zbl 0937.20017
[22] W. Thurston, On the geometry and dynamics of diffeomorphisms of surfaces. Bull. Amer. Math. Soc. ( N.S.) 19 (1988), 417-431. · Zbl 0674.57008
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.