zbMATH — the first resource for mathematics

Polynomial-time proofs that groups are hyperbolic. (English) Zbl 07312489
Summary: It is undecidable in general whether a given finitely presented group is word hyperbolic. We use the concept of pregroups, introduced by Stallings (1971), to define a new class of van Kampen diagrams, which represent groups as quotients of virtually free groups. We then present a polynomial-time procedure that analyses these diagrams, and either returns an explicit linear Dehn function for the presentation, or returns , together with its reasons for failure. Furthermore, if our procedure succeeds we are often able to produce in polynomial time a word problem solver for the presentation that runs in linear time. Our algorithms have been implemented, and when successful they are many orders of magnitude faster than KBMAG, the only comparable publicly available software.
20F Special aspects of infinite or finite groups
57M General low-dimensional topology
53C Global differential geometry
AUTOMATA; GAP; kbmag; Magma
Full Text: DOI
[1] Alonso, J.; Brady, T.; Cooper, D.; Ferlini, V.; Lustig, M.; Mihalik, M.; Shapiro, M.; Short, H., Notes on word-hyperbolic groups, (Ghys, E.; Haefliger, A.; Verjovsky, A., Proceedings of the Conference Group Theory from a Geometric Viewpoint. Proceedings of the Conference Group Theory from a Geometric Viewpoint, held in I.C.T.P, Trieste, March 1990 (1991), World Scientific: World Scientific Singapore) · Zbl 0849.20023
[2] Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system. I. The user language, J. Symb. Comput., 24, 235-265 (1997) · Zbl 0898.68039
[3] Chalk, C., Fibonacci groups, \(F(2, n)\), are hyperbolic for n odd and \(n \geq 11 (2020)\)
[4] Domanski, B.; Anshell, M., The complexity of Dehn’s algorithm for word problems in groups, J. Algebra, 6, 543-549 (1985) · Zbl 0591.20037
[5] Epstein, D. B.A.; Holt, D. F., Computation in word-hyperbolic groups, Int. J. Algebra Comput., 11, 467-487 (2001) · Zbl 1024.20039
[6] The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.10.1 (2019)
[7] Gersten, S. M.; Short, H., Small cancellation theory and automatic groups, Invent. Math., 102, 2, 305-334 (1990) · Zbl 0714.20016
[8] Havas, G.; Holt, D. F., On Coxeter’s families of group presentations, J. Algebra, 324, 5, 1076-1082 (2010) · Zbl 1204.20039
[9] Helling, H.; Kim, A. C.; Mennicke, J. L., A geometric study of Fibonacci groups, J. Lie Theory, 8, 1, 1-23 (1998) · Zbl 0896.20026
[10] Hoare, A. H.M., Pregroups and length functions, Math. Proc. Camb. Philos. Soc., 104, 1, 21-30 (1988) · Zbl 0667.20020
[11] Holt, D. F., KBMAG - Knuth-Bendix in monoids and automatic groups, software package (1995), Available from
[12] Holt, D. F., The Warwick automatic groups software, (Baumslag, Gilbert; etal., Geometrical and Computational Perspectives on Infinite Groups. Geometrical and Computational Perspectives on Infinite Groups, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 25 (1996)), 69-82 · Zbl 0932.20037
[13] Holt, Derek F.; Eick, Bettina; O’Brien, Eamonn A., Handbook of Computational Group Theory, Discrete Mathematics and Its Applications (Boca Raton) (2005), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton, FL · Zbl 1091.20001
[14] Holt, D. F.; Rees, S.; Röver, C. E., Groups, Languages and Automata, London Mathematical Society Student Texts, vol. 88 (2017), Cambridge University Press · Zbl 06691444
[15] Johnson, D. B., Efficient algorithms for shortest paths in sparse networks, J. ACM, 24, 1, 1-13 (1977) · Zbl 0343.68028
[16] Lyndon, R. C.; Schupp, P. E., Combinatorial Group Theory (1977), Springer-Verlag · Zbl 0368.20023
[17] Lysenok, I. G., An approach to the study of finitely presented groups based on the notion of discrete curvature, Math.l Notes, 103, 4, 568-575 (2018)
[18] Martin, A., Complexes of groups and geometric small cancelation over graphs of groups, Bull. Soc. Math. Fr., 145, 193-223 (2017) · Zbl 1446.20066
[19] Papasoglu, P., Strongly geodesically automatic groups are hyperbolic, Invent. Math., 121, 2, 323-334 (1995) · Zbl 0834.20040
[20] Rimlinger, F., Pregroups and Bass-Serre theory, Mem. Am. Math. Soc., 65, 361 (1987) · Zbl 0633.20014
[21] Serre, J.-P., Trees (2003), Springer
[22] Stallings, J. R., Group Theory and Three-Dimensional Manifolds (1971), Yale University Press: Yale University Press New Haven, Conn
[23] Weiss, U., On biautomaticity of non-homogenous small-cancellation groups, Int. J. Algebra Comput., 17, 4, 797-820 (2007) · Zbl 1168.20017
[24] Wilson, Robin J., Introduction to Graph Theory (2010), Prentice Hall · Zbl 0249.05101
[25] Żuk, A., Property (T) and Kazhdan constants for discrete groups, Geom. Funct. Anal., 13, 643-670 (2003) · Zbl 1036.22004
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.