Solving algorithmic problems in Baumslag-Solitar groups and their extensions using data compression
Jürn Laun · OPUS Publication Server of the University of Stuttgart (University of Stuttgart) · 2012
This thesis deals with algorithmic group theory and the application of data compression techniques in this area. Elements of the Baumslag-Solitar groups can be represented by comparatively short sequences of generators while their canonical normal forms are exponentially longer. As a consequence, algorithms that solve the word problem by computing such normal forms have to apply compression of the same order to their working data in order to satisfy polynomial time and space contraints. A common way to do this is to write numbers in binary. Going in the opposite direction, the problem of finding a shortest representation of a group element, a so-called geodesic, is also of interest. For example, geodesics can be used to make statements about growth inside groups. In Chapter 2, geodesic normal forms for the Baumslag-Solitar group BS(p,q) are defined and an algorithm is developed that computes them in polynomial time if p divides q. For arbitrary p and q, a partial solution is given which includes the horocyclic subgroup. Experimental results suggest that the horocyclic growth series of BS(2,3) is irrational. In some extensions of the Baumslag-Solitar groups, for example Higman's group and the Baumslag-Gersten group, the discrepancy between the lengths of geodesics and normal forms cannot even be described by an elementary function. This makes conventional approaches to the word problem infeasible. Recently, a data structure has been introduced that makes integers of this magnitude manageable. With the help of these so-called “power circuits”, the word problem for the Baumslag-Gersten group BG(1,2) has been proved to be polynomial-time solvable. In Chapter 3, the crucial reduction procedure for power circuits is improved, thereby decreasing the best known upper time bound for the word problem for BG(1,2) from O(n^7) to O(n^3). At the same time, power circuits are generalized so as to allow bases other than 2. This makes the data structure apt for the generalized Baumslag-Gersten groups BG(1,q) with q>=2. In Chapter 4, power circuits are used to solve the word problem for Higman's group H_4(1,2), an amalgamated product of four copies of BS(1,2). For this group, a time bound of O(n^6) is proved. Again, the generalized notion of power circuit allows an extension of the solution to a larger class of groups H_4(1,q). The algorithm also works for an even more generalized version H_f(1,q) of Higman's group, where an arbitrary number f>=4 of copies of BS(1,q) are amalgamated. The time complexity of the algorithm remains O(n^6) and does not depend on f.