×

Computing subgroup presentations, using the coherence arguments of McCammond and Wise. (English) Zbl 1101.20022

Summary: We describe an algorithm which may be used to compute a finite presentation of a finitely generated subgroup of a finitely presented group \(G\), provided that \(G\) satisfies appropriate hypotheses. The algorithm is based on an algorithm of J. P. McCammond and D. T. Wise [Geom. Funct. Anal. 15, No. 4, 859-927 (2005; Zbl 1087.20024)], but is extended to cover a wider class of groups, including all those satisfying the path reduction or weak 2-cell reduction hypotheses of McCammond and Wise. The proofs of correctness of our algorithm emerge from McCammond and Wise’s own proofs that their hypotheses imply coherence of the groups satisfying them. We also demonstrate that the algorithm may be extended further to cover groups satisfying appropriate conditions on fans (strings of 2-cells) within disc diagrams. The core of this work originally appeared in the PhD thesis of the first author.

MSC:

20F05 Generators, relations, and presentations of groups
20-04 Software, source code, etc. for problems pertaining to group theory
20F06 Cancellation theory of groups; application of van Kampen diagrams
68W30 Symbolic computation and algebraic computation
20F65 Geometric group theory
57M07 Topological methods in group theory

Citations:

Zbl 1087.20024

Software:

GAP; GRAPE; kbmag; AUTOMATA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Birget, J.-C.; Margolis, S.; Meakin, J.; Weil, P., PSPACE-complete problems for subgroups of free groups and inverse finite automata, Theoret. Comput. Sci., 242, 247-281 (2000) · Zbl 0944.68100
[2] Clifford, A., Compact cores of coverings, Topology Appl., 97, 267-271 (1999) · Zbl 0940.57002
[3] Delgado, M.; Margolis, S.; Steinberg, B., Combinatorial group theory, inverse monoids, automata and global semigroup theory, Internat. J. Algebra Comput., 12, 179-211 (2002) · Zbl 1023.20021
[4] L. Markus Epstein, PhD thesis, Bar Ilan University, 2005; L. Markus Epstein, PhD thesis, Bar Ilan University, 2005
[5] Feighn, M.; Handel, M., Mapping tori of free group automorphisms are coherent, Ann. of Math. (2), 149, 1061-1077 (1999) · Zbl 0938.20022
[6] Ghani, N.; Heyworth, A., A rewriting alternative to Reidemeister-Schreier, (Rewriting Techniques and Applications. Rewriting Techniques and Applications, Lecture Notes in Comput. Sci., vol. 2706 (2003), Springer-Verlag: Springer-Verlag Berlin), 452-466 · Zbl 1038.68152
[7] Gitik, R.; Margolis, S.; Steinberg, B., On the Kurosh theorem and separability properties, J. Pure Appl. Algebra, 179, 87-97 (2003) · Zbl 1016.20017
[8] Holt, D. F., The Warwick automatic groups software, (Baumslag, G.; etal., Geometrical and Computational Perspectives on Infinite Groups. Geometrical and Computational Perspectives on Infinite Groups, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 25 (1996)), 69-82 · Zbl 0932.20037
[9] Holt, D. F.; Hurt, D. F., Computing automatic coset systems and subgroup presentations, J. Symbolic Comput., 27, 1-19 (1999) · Zbl 0930.20035
[10] Holt, D. F., KBMAG—Knuth-Bendix in monoids and automatic groups (1995), software package
[11] D.F. Hurt, The use of Knuth-Bendix methods and automatic coset systems for solving the generalized word problem and finding subgroups presentations, PhD thesis, University of Warwick, 1996; D.F. Hurt, The use of Knuth-Bendix methods and automatic coset systems for solving the generalized word problem and finding subgroups presentations, PhD thesis, University of Warwick, 1996
[12] Lyndon, R. C.; Schupp, P. E., Combinatorial Group Theory (1977), Springer-Verlag: Springer-Verlag Berlin · Zbl 0368.20023
[13] J.P. McCammond, private communication, 2005; J.P. McCammond, private communication, 2005
[14] McCammond, J. P.; Wise, D. T., Coherence, local quasiconvexity and the perimeter of 2-complexes, Geom. Funct. Anal., 15, 859-927 (2005) · Zbl 1087.20024
[15] J.P. McCammond, D.T. Wise, Windmills and extreme 2-cells, preprint; J.P. McCammond, D.T. Wise, Windmills and extreme 2-cells, preprint · Zbl 1238.57005
[16] McCammond, J. P.; Wise, D. T., Fans and ladders in small cancellation theory, Proc. London Math. Soc. (3), 84, 599-644 (2002) · Zbl 1022.20012
[17] O. Payne, Computing presentations of subgroups, PhD thesis, University of Newcastle upon Tyne, 2002; O. Payne, Computing presentations of subgroups, PhD thesis, University of Newcastle upon Tyne, 2002
[18] Rees, S.; Soicher, L. H., An algorithmic approach to fundamental groups and covers of combinatorial cell complexes, J. Symbolic Comput., 29, 59-77 (2000) · Zbl 0942.57002
[19] Reidemeister, K., Knoten und Gruppen, Abh. Math. Sem. Univ. Hamburg, 5, 7-23 (1927) · JFM 52.0578.04
[20] Schönert, M., GAP—Groups, Algorithms and Programming (1994), RWTH Aachen: Lehrstuhl D für Mathematik
[21] Schreier, O., Die Untergruppen der freien Gruppen, Abh. Math. Sem. Univ. Hamburg, 5, 161-183 (1927) · JFM 53.0110.01
[22] Scott, G. P., Finitely generated 3-manifold groups are finitely presented, J. London Math. Soc., 6, 437-440 (1973) · Zbl 0254.57003
[23] Sims, C. C., Computation With Finitely Presented Groups, Encyclopaedia Math., vol. 48 (1994), Cambridge Univ. Press · Zbl 0828.20001
[24] Soicher, L. H., GRAPE: A system for computing with graphs and groups, (DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11 (1993)), 287-291 · Zbl 0833.05071
[25] Stallings, J. R., Topology of finite graphs, Invent. Math., 71, 551-565 (1983) · Zbl 0521.20013
[26] Stallings, J. R.; Wolf, A. R., The Todd-Coxeter process, using graphs, (Combinatorial Group Theory and Topology. Combinatorial Group Theory and Topology, Alta, Utah, 1984 (1987), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ), 157-161 · Zbl 0619.20014
[27] Stillwell, J., Classical Topology and Combinatorial Group Theory (1993), Springer-Verlag: Springer-Verlag New York · Zbl 0774.57002
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.