On algorithmic problems in Coxeter groups

V. N. Bezverkhnii ; N. B. Bezverkhnyaya ; I. V. Dobrynina ; O. V. Inchenko ; A. E. Ustyan

Čebyševskij sbornik, Tome 17 (2016) no. 4, pp. 23-50.

Résumé

The main algorithmic problems of group theory posed by M. Dehn are the problem of words, the problem of the conjugation of words for finitely presented groups, and the group's isomorphism problem. Among the works related to the study of the M. Dehn's problems, the most outstanding ones are the work of P. S. Novikov who proved the undecidability of the problem of words and the conjugacy problem for finitely presented groups as well as the undecidability of the problem of isomorphism of groups. In this regard, the main algorithmic problems and their various generalizations are studied in certain classes of groups. Coxeter groups were introduced by H. S. M. Coxeter: every reflection group is a Coxeter group if its generating elements are reflections with respect to hyperplanes limiting its fundamental polyhedron. H. S. M. Coxeter listed all the reflection groups in three-dimensional Euclidean space and proved that they are all Coxeter groups and every finite Coxeter group is isomorphic to some reflection group in the three-dimensional Euclidean space which elements have a common fixed point. In an algebraic aspect Coxeter groups are studied starting with works by J. Tits who solved the problem of words in certain Coxeter groups. The article describes the known results obtained in solving algorithmic problems in Coxeter groups; the main purpose of the paper is to analyze of the results of solving algorithmic problems in Coxeter groups that were obtained by members of the Tula algebraic school “Algorithmic problems of theory of the groups and semigroups” under the supervision of V. N. Bezverkhnii. It reviews assertions and theorems proved by the authors of the article for the various classes of Coxeter groups: Coxeter groups of large and extra-large types, Coxeter groups with a tree-structure, and Coxeter groups with $n$-angled structure. The basic approaches and methods of evidence among which the method of diagrams worked out by van Kampen, reopened by R. Lindon and refined by V. N. Bezverkhnii concerning the introduction of R-cancellations, special $R$-cancellations, special ring cancellations as well as method of graphs, method of types worked out by V. N. Bezverkhnii, method of special set of words designed by V. N. Bezverkhnii on the basis of the generalization of Nielsen method for free construction of groups. Classes of group considered in the article include all Coxeter groups which may be represented as generalized tree structures of Coxeter groups formed from Coxeter groups with tree structure with replacing some vertices of the corresponding tree-graph by Coxeter groups of large or extra-large types as well as Coxeter groups with $n$-angled structure.

Détail

Keywords: Coxeter group, algorithmic problems, diagrams.

Bibliographie

[1] Coxeter H. S. M., “Discrete groups generated by reflections”, Ann. Math., 35 (1934), 588–621 | DOI | MR

[2] Tits J., “Groupes simples et geometries associees”, Proc. Int. Congress Math. (Stocholm, 1962), 197–221 | MR | Zbl

[3] Schupp P., Coxeter Groups, 2-Completion, Perimeter Reduction and Subgroup Separability, 2002, 21 pp., arXiv: math.GR/0203020 | MR

[4] Appel K., Schupp P., “Artins groups and infinite Coxter groups”, Ivent. Math., 72 (1983), 201–220 | DOI | MR | Zbl

[5] Bezverkhnii V. N., “Solution of the conjugacy problem for words in Artin groups and Coxeter groups of large type”, Algorithmic problems of theory of groups and semigroups, TSPU, Tula, 1986, 26–61

[6] Kapovich I., Schup P., “Bounded rank subgroups of Coxeter groups, Artin groups and one-relator groups with torsion”, London Math. Soc., 88 (2004), 89–113 | DOI | MR | Zbl

[7] Bezverkhnii V. N., Dobrynina I. V., “Solution of the conjugacy problem for words in Coxeter groups of large type”, Chebyshevskii Sb., 4:1(5) (2003), 10–33

[8] Bezverkhnii V. N., Dobrynina I. V., “Solution of the generalized conjugacy problem for words in Coxeter groups of large type”, Diskr. Mat., 17:3 (2005), 123–145 | DOI | Zbl

[9] Bezverkhnii V. N., Dobrynina I. V., “On elements of finite order in Coxeter groups of large type”, Izvestia of Tula state University. Ser. Math. Mechanics. Informatics, 9:1 (2003), 13–22

[10] Bezverkhnii V. N., Dobrynina I. V., “Solution the problem of occurrence in a cyclic subgroup in the Coxeter groups of large type”, Izvestia of the Tula state University. Ser. Math. Mechanics. Informatics, 10:1 (2004), 23–37

[11] Bezverkhnii V. N., Dobrynina I. V., “Solution of the power conjugacy search problem in a cyclic subgroup in in Coxeter groups of large type”, Izvestia of the Tula state University. Ser. Math. Mechanics. Informatics, 10:1 (2004), 38–46

[12] Bezverkhnii V. N., Dobrynina I. V., “A solution of the power conjugacy problem for words in the Coxeter groups of extra large type”, Diskr. Mat., 20:3 (2008), 101–110 | DOI | Zbl

[13] Dobrynina I. V., “On subgroups in Coxeter groups of extra large type”, Chebyshevskii Sb., 9:1(25) (2008), 9–15

[14] Bezverkhnii V. N., Inchenko O. V., “Centralizer of elements of finite order of a finitely generated Coxeter group with a tree-structure”, Chebyshevskii Sb., 9:1(25) (2008), 17–28 | Zbl

[15] Inchenko O. V., “Problem of generalized conjugacy of words in Coxeter's groups with tree-structure”, Izvestia of Tula state University. Natural science, 2008, no. 2, 40–48

[16] Bezverkhnii V. N., “Solution of the problem of inclusion in some class of groups with one relation”, Algorithmic problems of theory of groups and semigroups, TSPU, Tula, 1986, 3–22

[17] Bezverkhnii V. N., “On the intersection subgroups $HNN$-groups”, Fundam. Prikl. Mat., 4:1 (1998), 199–222

[18] Bezverkhnii V. N., Inchenko O. V., “Problem of intersection of finite defined subgroups in Coxeter groups with tree-structure”, Izvestiya of Tula State University. Natural sciences, 2009, no. 2, 16–31

[19] Inchenko O. V., “On problem of intersection of the adjacency classes of finitely generated subgroups of Coxeter group with tree-structure”, Chebyshevskii Sb., 17:2(58) (2016), 146–162

[20] Bezverkhnii V. N., Inchenko O. V., “Conjugacy problem of subgroups in finitely generated Coxeter groups with tree-structure”, Chebyshevskii Sb., 11:3 (2010), 32–56 | Zbl

[21] Bezverkhnii V. N., “Solution of the problem of inclusion of subgroups in one class $HNN$-groups”, Algorithmic problems of theory of groups and semigroups, TSPU, Tula, 1981, 20–62

[22] Bezverkhnii V. N., Dobrynina I. V., “On freedom problem in Coxeter groups with tree-structure”, Izvestiya of Tula state University. Natural science, 2014, no. 1-1, 5–13

[23] Dobrynina I. V., “On normalizers in some Coxeter groups”, Chebyshevskii Sb., 17:2(58) (2016), 113–127 | Zbl

[24] Dobrynina I. V., “On construction of Normalizer of finitely generated subgroups in the Coxeter group with tree-structure”, Research in algebra, number theory, functional analysis and related issues, 2016, no. 8, 26–28

[25] Dobrynina I. V., Inchenko O. V., “On some problem in Coxeter groups with a tree structure”, Algorithmic problems in algebra and the theory of computation, International scientific conference dedicated to 75-th anniversary of D. I. Moldavanskii, IVGU, Ivanovo, 2015, 35–40

[26] Bezverkhnii V. N., Dobrynina I. V., “On construction of isolator of subgroup in some class of Coxeter groups”, Proceedings of the international conference on algebra, analysis and geometry, Kazan University, Kazan, 2016, 108–109 | Zbl

[27] Bezverkhnii V. N., Bezverkhnyaya N. B., “Problem of equality and conjugacy of words in a certain class of Artin groups and Coxeter”, Algorithmic problems in algebra and the theory of computation, International scientific conference dedicated to 75-th anniversary of D. I. Moldavanskii, IVGU, Ivanovo, 2015, 11–16

[28] Bezverkhnii V. N., Bezverkhnyaya N. B., “Problem of equality and conjugacy of words in Artin groups, Coxeter $n$-pointed structure”, Research in algebra, number theory, functional analysis and related issues, 2016, no. 8, 9–10

[29] Bezverkhnii V. N., Ustyan A. E., “Problem of power conjugation of the words in the Artin monoids of large type”, Algorithmic problems of theory of groups and semigroups, TSPU, Tula, 2001, 139–164

[30] Bezverkhnii V. N., Ustyan A. E., “Generalizations of theorems of Magnus and Greendlinger”, Chebyshevskii Sb., 14:3 (2013), 20–33