Solving decision problems in finitely presented groups via generalized small cancellation theory

  • Simon Jurina

Student thesis: Doctoral Thesis (PhD)

Abstract

This thesis studies two decision problems for finitely presented groups. Using a standard RAM model of computation, in which the basic arithmetical operations on integers are assumed to take constant time, in Part I we develop an algorithm IsConjugate, which on input a (finite) presentation defining a hyperbolic group ๐บ, correctly decides whether ๐‘คโ‚ ฯต ๐‘‹* and ๐‘คโ‚‚ ฯต ๐‘‹* are conjugate in ๐บ, and if so, then for each ๐‘– ฯต {1,2}, returns a cyclically reduced word ๐‘Ÿแตข that is conjugate in ๐บ to ๐‘คแตข, and an ๐‘ฅ ฯต ๐‘‹* such that rโ‚‚= G ๐‘ฅ^{-1} r_1 x (hence if ๐‘คโ‚ and ๐‘คโ‚‚ are already cyclically reduced, then it returns an ๐‘ฅ ฯต ๐‘‹* such that ๐‘คโ‚‚=_G x^{-1} w_1 x). Moreover, IsConjugate can be constructed in polynomial-time in the input presentation < ๐‘‹ | ๐‘… >, and IsConjugate runs in time O((|๐‘คโ‚| + |๐‘คโ‚‚| min{|๐‘คโ‚|, |๐‘คโ‚‚|}).

IsConjugate has been implemented in the MAGMA software, and our experiments show that the run times agree with the worst-case time complexities. Thus, IsConjugate is the most efficient general practically implementable conjugacy problem solver for hyperbolic groups.

It is undecidable in general whether a given finitely presented group is hyperbolic. In Part II of this thesis, we present a polynomial-time procedure VerifyHypVertex which on input a finite presentation for a group G, returns true only if G is hyperbolic. VerifyHypVertex generalizes the methods from [34], and in particular succeeds on all presentations on which the implementation from [34] succeeds, and many additional presentations as well. The algorithms have been implemented in MAGMA, and the experiments show that they return a positive answer on many examples on which other comparable publicly available methods fail, such as KBMAG.
Date of Award13 Jun 2023
Original languageEnglish
Awarding Institution
  • University of St Andrews
SupervisorColva Roney-Dougal (Supervisor) & Peter Jephson Cameron (Supervisor)

Keywords

  • Hyperbolic groups
  • Geometric/Computational group theory
  • Decision problems
  • MAGMA
  • Pregroups
  • Van Kampen diagrams

Access Status

  • Full text open

Cite this

'