Solving algorithmic problems in Baumslag-Solitar groups and their extensions using data compression

Abstract

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.

Diese Arbeit handelt von der Anwendung von Datenkompressionstechniken in der algorithmischen Gruppentheorie. Elemente der Baumslag-Solitar-Gruppen BS(p,q) können durch vergleichsweise kurze Wörter über den Erzeugern dargestellt werden, während deren kanonische Normalformen exponentiell länger sind. Dies führt dazu, dass Algorithmen zur Lösung des Wortproblems dieser Gruppen ihre Eingabe in sehr kompakter Form erhalten und daher besonders effizient arbeiten müssen, um polynomielle Zeit- und Platzschranken einzuhalten. Sollen solche Algorithmen dennoch Normalformen berechnen, so müssen sie diese ebenfalls exponentiell komprimieren. Im Falle der Baumslag-Solitar-Gruppen kann diese Kompression durch Verwendung binärer Zahlendarstellungen erfolgen.

Von Interesse ist auch die umgekehrte Problemstellung, eine kürzeste Darstellung eines gegebenen Gruppenelements - eine sogenannte Geodätische - zu finden. Mit Hilfe Geodätischer lassen sich beispielsweise Aussagen über das Wachstum in Gruppen treffen. In Kapitel 2 werden geodätische Normalformen für BS(p,q) definiert und Algorithmen vorgestellt, die diese in Polynomialzeit berechnen, sofern p ein Teiler von q ist. Für beliebige Werte p und q wird eine Teillösung für bestimmte Gruppenelemente, darunter die horozyklischen, vorgestellt. Experimentelle Ergebnisse auf der Grundlage der entwickelten Algorithmen legen nahe, dass die Wachstumsreihe der Gruppe BS(2,3) nicht rational ist.

In bestimmten Erweiterungen der Baumslag-Solitar-Gruppen, wie zum Beispiel der Baumslag-Gersten-Gruppe, ist der Längenunterschied zwischen Geodätischen und den zugehörigen kanonischen Normalformen durch eine nicht-elementare Funktion gegeben. Dies macht Standardverfahren zur Lösung des Wortproblems undurchführbar. Lange Zeit galt daher die Baumslag-Gersten-Gruppe BG(1,2) als Kandidat für eine Einrelatorgruppe mit sehr schwierigem Wortproblem. Vor Kurzem wurde jedoch eine Datenstruktur eingeführt, die Zahlen dieser Größenordnung handhabbar macht. Mit Hilfe dieser sogenannten „Power Circuits“ konnte gezeigt werden, dass das Wortproblem der Baumslag-Gersten-Gruppe BG(1,2) in polynomieller Zeit lösbar ist. In Kapitel 3 wird der zentrale Reduktionsalgorithmus für Power Circuits verbessert, wodurch die die obere Schranke für den Zeitaufwand dieses Problems von O(n^7) auf O(n^3) sinkt. Gleichzeitig werden Power Circuits dahingehend verallgemeinert, dass anstelle der Basis 2 beliebige Basen q>=2 zugelassen werden. Dies erlaubt es, das Wortproblem auch in den verallgemeinerten Baumslag-Gersten-Gruppen BG(1,q) effizient zu lösen.

In Kapitel 4 werden Power Circuits verwendet, um das Wortproblem der Higman-Gruppe H_4(1,2) zu lösen, einem amalgamierten Produkt von vier Kopien von BS(1,2). Es wird eine Zeitschranke von O(n^6) bewiesen. Wieder erlaubt die auf beliebige Basen verallgemeinerte Variante der Power Circuits, die Lösung auf eine größere Klasse von Gruppen H_4(1,q) auszudehnen. Der Algorithmus lässt sich sogar auf eine noch allgemeinere Klasse von Higman-Gruppen H_f(1,q) anwenden, bei denen eine beliebige Zahl f>=4 von Kopien von BS(1,q) amalgamiert werden. Der Zeitaufwand des Algorithmus bleibt in O(n^6), unabhängig von f.