Polynomial-time proofs that groups are hyperbolic. (May 2021)

• Record Type: Journal Article
• Authors: Holt, Derek; Linton, Stephen; Neunhöffer, Max; Parker, Richard; Pfeiffer, Markus; Roney-Dougal, Colva M.
• Is Part Of: Journal of symbolic computation. Volume 104(2021)
• Page Start: 419
• Page End: 475
• Publication Date: 2021-05
• Subjects: Hyperbolic groups -- Word problem -- van Kampen diagrams -- Curvature; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2020.08.003
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: 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 fail, 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.