Beschreibung
Die Dehn-Funktion beschreibt, wie schwer es ist, das Wortproblem (Gruppe) durch Brute-Force Methoden zu lösen.
Definition
Die Dehn-Funktion gibt an, wie viele Relatoren, man maximal zusammensetzen muss, um ein Wort der Länge zu bekommen.
Eigenschaften
Für eine Endlich Präsentierbare Gruppe mit der Dehnfunktion ist folgendes äquivalent:
- Es gibt einen Algorithmus, der ausgibt, ob ein Wort des Alphabets die Identität ist
- Es gibt eine berechenbare Funktion , sodass
- ist berechenbar
Zusammenhang mit Isoperimetrie
Die Dehnfunktion gibt die maximale Zahl an Relatoren an, aus denen ein Element einer festen Länge erzeugt sein kann. Als solches ist es verwandt mit dem Problem, den größten Flächeninhalt zu einem gegebenem Umfang zu suchen. Man kann es also als ein Isoperimetrisches Problem betrachten.
Als Objekt, dessen “Fläche” wir maximieren wollen, verwenden wir den Cayley-2-Complex
Beispiele
Dehn-Funktion endlicher Gruppen
Die Dehnfunktion endlicher Gruppen ist kleiner als für ein .
Dehnfunktion von
Die Dehnfunktion von hat die Schranken
Dehnfunktion endlich erzeugter abelscher Gruppen
Die Dehnfunktion von endlich erzeugten Abelsche Gruppe hat die Schranken: