On the complexity of conjugacy in amalgamated products and HNN extensions

Abstract

This thesis deals with the conjugacy problem in classes of groups which can be written as HNN extension or amalgamated product. The conjugacy problem is one of the fundamental problems in algorithmic group theory which were introduced by Max Dehn in 1911. It poses the question whether two group elements given as words over a fixed set of generators are conjugate. Thus, it is a generalization of the word problem, which asks whether some input word represents the identity. Both, word and conjugacy problem, are undecidable in general.

In this thesis, we consider not only decidability, but also complexity of conjugacy. We consider fundamental groups of finite graphs of groups as defined by Serre - a generalization of both HNN extensions and amalgamated products. Another crucial concept for us are strongly generic algorithms - a formalization of algorithms which work for "most" inputs. The following are our main results:

The elements of an HNN extension which cannot be conjugated into the base group form a strongly generic set if and only if both inclusions of the associated subgroup into the base group are not surjective. For amalgamated products we prove an analogous result.

Following a construction by Stillwell, we derive some undecidability results for the conjugacy problem in HNN extensions with free (abelian) base groups. Next, we show that conjugacy is decidable if all associated subgroups are cyclic or if the base group is abelian and there is only one stable letter. Moreover, in a fundamental group of a graph of groups with free abelian vertex groups, conjugacy is strongly generically in P.

Moreover, we consider the case where all edge groups are finite: If conjugacy can be decided in time T(N) in the vertex groups, then it can be decided in time O(log N * T(N)) in the fundamental group under some reasonable assumptions on T (here, N is the length of the input). We also derive some basic transfer results for circuit complexity in the same class of groups.

Furthermore, we examine the conjugacy problem of generalized Baumslag-Solitar groups. Our main results are: the conjugacy problem in solvable Baumslag-Solitar groups is TC0-complete, and in arbitrary generalized Baumslag-Solitar groups it can be decided in LOGDCFL. The uniform conjugacy problem for generalized Baumslag-Solitar groups is hard for EXPSPACE.

Finally, we deal with the conjugacy problem in the Baumslag group, an HNN extension of the Baumslag-Solitar group BS12. The Baumslag group has a non-elementary Dehn function, and thus, for a long time, it was considered to have a very hard word problem, until Miaskikov, Ushakov, and Won showed that the word problem, indeed, is in P by introducing a new data structure, the so-called power circuits. We follow their approach and show that the conjugacy problem is strongly generically in P. We conjecture that there is no polynomial time algorithm which works for all inputs, because the divisibility problem in power circuits can be reduced to this conjugacy problem. Also, we prove that the comparison problem in power circuits is complete for P under logspace reductions.

Diese Arbeit beschäftigt sich mit dem Konjugationsproblem in Gruppen, die sich als HNN-Erweiterung oder amalgamiertes Produkt schreiben lassen. Das Konjugationsproblem ist eines der fundamentalen Probleme der algorithmischen Gruppentheorie, die 1911 von Max Dehn eingeführt wurden. Es ist die Frage, ob zwei Wörter über den Erzeugern der Gruppe in der Gruppe zueinander konjugiert sind. Damit ist es eine Verallgemeinerung des Wortproblems, bei dem für ein Eingabewort festgestellt werden soll, ob es die Identität darstellt. Sowohl das Wort- als auch das Konjugationsproblem sind im Allgemeinen unentscheidbar.

In dieser Arbeit werden verschiedene Komplexitätsmaße verwendet, um die Komplexität von Wort- und Konjugationsproblem in HNN-Erweiterung und amalgamierten Produkten - und allgemeiner in Fundamentalgruppen von Graphen von Gruppen - zu analysieren. Die Arbeit ist wie folgt aufgebaut: Zuerst wird eine kurze Einführung in die Bass-Serre-Theorie gegeben. Danach wird der Begriff der Mittelbarkeit ("Amenability") sowie dessen Zusammenhang zu generischen Algorithmen untersucht. Es wird gezeigt, dass unter gewissen Voraussetzungen die Elemente einer Fundamentalgruppe, die nicht in eine der Knotengruppen hinein konjugiert werden können, eine stark generische Menge bilden (stark generisch bedeutet, dass der Anteil der Wörter, die nicht in der Menge sind, exponentiell mit der Länge abnimmt). Da in vielen Fällen effiziente Algorithmen zur Lösung des Konjugationsproblems eben für jene Elemente existieren, ist in diesen Fällen das Konjugationsproblem stark generisch effizient lösbar.

Die folgenden Kapitel beschäftigen sich mit Algorithmen für das Konjugationsproblem: Zunächst werden Fundamentalgruppen von Graphen von Gruppen mit freien bzw. frei abelschen Knotengruppen untersucht. Zunächst werden Unentscheidbarkeitsresultate von Miller verallgemeinert und dabei auch HNN-Erweiterungen frei abelscher Gruppen betrachtet. Andererseits stellt es sich heraus, dass mit nur einem "stable letter" das Konjugationsproblem in einer HNN-Erweiterung einer frei abelschen Gruppe in jedem Fall entscheidbar ist. Ferner ist das Konjugationsproblem in beliebigen Fundamentalgruppen von Graphen von Gruppen mit frei abelschen Knotengruppen stark generisch in P; wenn alle Kantengruppen zyklisch sind, ist es stets entscheidbar.

Wie die Unentscheidbarkeitsresultate zeigen, kann im Allgemeinen von der Entscheidbarkeit des Konjugationsproblems in den Knotengruppen nicht auf die Entscheidbarkeit in der Fundamentalgruppe geschlossen werden. Wie einfach zu sehen ist, ändert sich diese Situation, wenn man sich auf endliche Kantengruppen beschränkt. Um diese Beobachtung zu verfeinern, wird gezeigt, dass der Mehraufwand für das Wort- und Konjugationsproblem in der Fundamentalgruppe gegenüber den Knotengruppen maximal logarithmisch ist. Ferner ist das Konjugationsproblem der Fundamentalgruppe in NC^(i+1), falls die Konjugationsprobleme der Knotengruppen in NC^i sind.

Danach werden verallgemeinerte Baumslag-Solitar-Gruppen behandelt. Diese sind Fundamentalgruppen endlicher Graphen von Gruppen mit unendlichen zyklischen Knoten- und Kantengruppen. Zuerst werden die auflösbaren Baumslag-Solitar-Gruppen betrachtet, deren Konjugationsproblem TC0-vollständig ist. Sowohl das Wort- als auch das Konjugationsproblem verallgemeinerter Baumslag-Solitar-Gruppen ist in LOGDCFL. Betrachtet man den Graph von Gruppen allerdings als Teil der Eingabe, wandelt sich das Bild: In diesem Fall ist das Konjugationsproblem EXPSPACE-hart.

Schlussendlich geht um die Baumslag-(Gersten-)Gruppe, eine HNN-Erweiterung der Baumslag-Solitar-Gruppe BS12. Die Baumslag-Gruppe galt lange Zeit als ein mögliches Beispiel einer Gruppe mit nicht in Elementarzeit lösbarem Wortproblem, bis Miaskikov, Ushakov und Won zeigten, dass das Wortproblem tatsächlich in Polynomialzeit lösbar ist. Der Beweis beruht auf einer neuen Datenstruktur, den sogenannten Power Circuits, die in der Lage sind, extrem große Zahlen in komprimierter Form zu speichern. Mithilfe von Power Circuits kann auch gezeigt werden, dass das Konjugationsproblem der Baumslag-Gruppe stark generisch in P ist. Allerdings gibt es Eingaben, für die kein Polynomialzeitalgorithmus bekannt ist. Um das Konjugationsproblem für diese Eingaben effizient zu lösen, müsste man das Teilbarkeitsproblem für Power Circuits effizient lösen können. Allerdings kann dies nich durch Modulo-Rechnen geschehen, da dies zu einem nicht-elementaren Wachstum der Power Circuits führt. Es ein offenes Problem, ob es einen Polynomialzeitalgorithmus gibt, der das Konjugationsproblem der Baumslag-Gruppe für alle Eingaben löst.