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 Award | 13 Jun 2023 |
---|---|
Original language | English |
Awarding Institution |
|
Supervisor | Colva 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