Stammbaum (Gruppentheorie)

In der algorithmischen Gruppentheorie versteht man unter einem Stammbaum einen gerichteten Baum zur Modellierung von sogenannten Vorgänger-Nachfolger-Relationen zwischen Isomorphieklassen endlicher p-Gruppen. Letztere sind endliche Gruppen mit einer Primzahlpotenz als Ordnung. Die Basis ist dabei eine feste Primzahl und der Exponent ist eine positive ganze Zahl. Die Knoten (auch Ecken oder Vertices genannt) des Stammbaums sind Isomorphieklassen endlicher -Gruppen. Die Kanten des Baums verbinden genau jene Paare von Knoten, die in der Vorgänger-Nachfolger-Beziehung stehen.

Eine endliche -Gruppe besitzt neben der Ordnung zwei weitere Invarianten, die Nilpotenzklasse (kurz Klasse) und die Koklasse . Es stellte sich heraus, dass gewisse Klassen von Stammbäumen, die sogenannten bereinigten oder gestutzten Koklassen-Bäume, deren unendlich viele Vertices eine gemeinsame Koklasse besitzen, ein sich periodisch wiederholendes endliches Muster aufweisen. Diese zwei entscheidenden Eigenschaften der Endlichkeit und Periodizität, die von M. du Sautoy und unabhängig von B. Eick und C. R. Leedham-Green bewiesen wurden, gestatten eine Charakterisierung sämtlicher Mitglieder des Baumes durch endlich viele parametrisierte Präsentationen. Folglich spielen Stammbäume eine fundamentale Rolle in der Klassifikation endlicher -Gruppen.

Mit Hilfe der Kerne und Ziele der Artinschen Verlagerungs-Homomorphismen können Stammbäume mit zusätzlicher Struktur ausgestattet werden, die neulich zu unerwarteten Erfolgen bei arithmetischen Anwendungen in der Klassenkörpertheorie führte, insbesondere bei der Bestimmung der exakten Länge von Klassenkörpertürmen.

Ein Stammbaum kann mit Hilfe des -Gruppen-Erzeugungs-Algorithmus (pGEA) konstruiert werden, ausgehend von einer vorgegebenen Anfangsgruppe, die als Wurzel des Baums angenommen wird. Der pGEA ist ein rekursiver Prozess für die Lösung dieses Problems der Konstruktion des Stammbaums einer gegebenen endlichen -Gruppe, welche die Wurzel des Baums bildet. Dieser Algorithmus ist im Softwarepaket ANUPQ (Australian National University P-Quotient) der Computer-Algebra-Systeme GAP (Groups-Algorithms-Programming) und Magma implementiert.

Definitionen und Terminologie Wir definieren eine Baumstruktur und starten mit einer endlichen -Gruppe .

Vorgänger und Nachfolger Vorgänger Es gibt mehrere unterschiedliche Definitionen des (unmittelbaren) Vorgängers einer endlichen -Gruppe . Das gemeinsame Prinzip ist die Bildung des Quotienten von nach einem geeigneten Normalteiler , für den es die folgenden Möglichkeiten gibt:

V

das Zentrum von , in welchem Fall der Zentralquotient von genannt wird (V1), der letzte nicht-triviale Term der absteigenden Zentralreihe von , wobei die Nilpotenzklasse von bezeichnet (V2), der letzte nicht-triviale Term der unteren Exponent-p-Zentralreihe von , wobei die Exponent-p-Klasse von bedeutet (V3), der letzte nicht-triviale Term der abgeleiteten Reihe von , wobei die abgeleitete Länge von bezeichnet (V4).

Nachfolger In jedem dieser Fälle heißt ein unmittelbarer Nachfolger von und eine gerichtete Kante des Baums wird erklärt entweder als in Richtung der kanonischen Projektion auf den Quotienten oder als in der entgegengesetzten Richtung, die für Stammbäume geläufiger ist.

Die erstere Konvention (sogenannter In-Tree) wird verwendet von C. R. Leedham-Green und M. F. Newman, von M. du Sautoy und D. Segal, von C. R. Leedham-Green und S. McKay, sowie von B. Eick, C. R. Leedham-Green, M. F. Newman und E. A. O'Brien. Die letztere Definition (sogenannter Out-Tree) findet man bei M. F. Newman, bei M. F. Newman und E. A. O'Brien, bei M. du Sautoy, sowie bei B. Eick und C. R. Leedham-Green.

Im Folgenden wird die Richtung der kanonischen Projektionen für alle Kanten gewählt, sodass Stammbäume als gewurzelte In-Trees erscheinen. Dann ist ein Vertex , in Verallgemeinerung des unmittelbaren Nachfolgers, ein Nachfolger eines Vertex , und ist ein Vorgänger von , wenn entweder mit übereinstimmt oder wenn es einen Pfad gibt, , wobei , bestehend aus gerichteten Kanten von bis zu . Die den Pfad bildenden Vertices fallen notwendigerweise zusammen mit den iterierten Vorgängern von , mit : , wobei .

Erläuterungen Definition V2 Im einen wichtigen Spezialfall (V2) von Vorgängern, die als Quotienten nach der letzten nicht-trivialen unteren Zentrale definiert sind, können die Vertices des Pfades auch aufgefasst werden als sukzessive Quotienten der Klasse von , falls die Nilpotenzklasse von durch gegeben ist: , mit .

Definition V3 Im anderen wichtigen Spezialfall (V3) von Vorgängern, die als Quotienten nach der letzten nicht-trivialen unteren Exponent-p Zentrale definiert sind, können die Vertices des Pfades auch aufgefasst werden als sukzessive Quotienten der p-Klasse von , falls die p-Klasse von durch gegeben ist: , mit .

Stammbaum Allgemein ist der Stammbaum eines Vertex der Teilbaum aller Nachfolger von , beginnend an der Wurzel . Der maximal mögliche Stammbaum der trivialen Gruppe enthält alle endlichen -Gruppen und ist sehr exzeptionell, weil die triviale Gruppe für jede Vorgänger-Definition (V1–V4) unendlich viele abelsche -Gruppen als unmittelbare Nachfolger hat. Dabei ist aber zu beachten, dass die triviale Gruppe nur eine entartete -Gruppe für jede beliebige Primzahl ist.

Der Übergang von einem Vorgänger zu seinen Nachfolgern wird auch Propagation genannt. Äquivalente Sprechweisen dafür, dass Nachfolger von ist, sind: stammt von ab, gibt Anlass zu und propagiert zu .

Weiteres zu V1–V4 Die Vorgänger-Definitionen (V2) und (V3) haben den Vorteil, dass jede nicht-triviale endliche -Gruppe (mit durch teilbarer Ordnung) nur endlich viele unmittelbare Nachfolger besitzt. Bei Verwendung der Definition (V1) des Vorgängers als Zentralquotient kann es vorkommen, dass unendlich viele -Gruppen denselben Vorgänger haben. Für jede ungerade Primzahl besitzen beispielsweise die Gruppen aller abzählbar unendlich vielen Zweige der Isoklinieklassen und von P. Hall dieselbe Gruppe maximaler Klasse als Zentralquotienten . Auch die Definition (V4) des Vorgängers als Quotient nach der letzten nicht-trivialen abgeleiteten Untergruppe hat denselben Nachteil. Beispielsweise ist jede nicht-zyklische abelsche -Gruppe Kommutator-Quotient und somit Vorgänger von unendlich vielen metabelschen -Gruppen , die ja die abgeleitete Länge haben.

Die Definition (V2) des Vorgängers als Quotient nach der letzten nicht-trivialen unteren Zentrale hat den Vorteil, dass der Vorgänger einer nicht-abelschen -Gruppe nicht nur denselben Erzeugenden-Rang , sondern sogar denselben Kommutator-Quotienten, also dieselbe Abelisierung, besitzt wie : , weil für .

mini|alt=Propagation|Abbildung 0: Arten der Propagation.

Warnung. Im Hinblick auf den -Gruppen-Erzeugungs-Algorithmus, der die Definition (V3) des Vorgängers als Quotient nach der letzten nicht-trivialen unteren p-Zentrale verwendet, muss darauf hingewiesen werden, dass zwar nach dem Basissatz von Burnside denselben Erzeugenden-Rang besitzt wie , aufgrund der Invarianz des Frattini-Quotienten, also der Elementar-Abelisierung: , weil für , dass aber eine andere Abelisierung aufweisen kann als , wenn nicht . Man spricht dann von exogenetischer Propagation, bei Invarianz der Abelisierung hingegen von endogenetischer Propagation. Diese Arten der Propagation werden in Abbildung 0 durch Nachkommen mit drei verschiedenen Schrittweiten veranschaulicht, wobei als Wurzel die elementar-bizyklische -Gruppe mit einer beliebigen Primzahl dient.

Pro-p-Gruppen und Koklassen-Bäume Für ein solides Verständnis von Koklassen-Bäumen als spezielle und besonders bedeutende Instanz von Stammbäumen, ist es erforderlich, einige Tatsachen in Bezug auf unendliche topologische pro--Gruppen zusammenzufassen. Die Terme , mit , der unteren Zentralreihe einer pro- Gruppe sind abgeschlossene (und offene) Untergruppen mit endlichem Index. Daher sind die entsprechenden Quotienten endliche -Gruppen. Man sagt, die pro--Gruppe sei von der Koklasse , wenn der Grenzwert der Koklasse der sukzessiven Quotienten existiert und endlich ist. Eine unendliche pro--Gruppe der Koklasse ist eine -adische prä-Raumgruppe, weil sie einen Normalteiler enthält, die Translationsgruppe, der als freier Modul über dem Ring der -adischen ganzen Zahlen einen eindeutig bestimmten Rang besitzt, die Dimension, sodass der Quotient eine endliche -Gruppe ist, die Punktgruppe, welche auf uniseriell operiert. Die Dimension ist gegeben durch

, mit einer gewissen ganzen Zahl .

Ein zentrales Endlichkeits-Ergebnis für unendliche pro--Gruppen der Koklasse ist enthalten im sogenannten Theorem D, einem der fünf Koklassen-Theoreme die im Jahr 1994 unabhängig bewiesen wurden von A. Shalev und von C. R. Leedham-Green, und die bereits im Jahr 1980 von C. R. Leedham-Green und M. F. Newman vermutet worden waren. Theorem D garantiert, dass es nur endlich viele Isomorphieklassen unendlicher pro--Gruppen der Koklasse gibt, für jede feste Primzahl und jede feste nicht-negative ganze Zahl . Als Konsequenz existiert zu jeder unendlichen pro--Gruppe der Koklasse eine kleinste ganze Zahl , sodass die folgenden drei Bedingungen für jede ganze Zahl erfüllt werden.

S

die Koklasse des unteren Zentralquotienten hat den festen Wert (S1), ist nicht unterer Zentralquotient einer anderen unendlichen pro--Gruppe der Koklasse , die nicht isomorph zu ist (S2), der Faktor ist zyklisch von der Ordnung (S3).

The Stammbaum , bezüglich der Vorgänger-Definition (V2), der Wurzel mit minimalem heißt der Koklassen-Baum von und sein eindeutig bestimmter maximaler unendlicher (umgekehrt-orientierter) Pfad

wird als Hauptlinie (oder Stamm) des Baumes bezeichnet.

mini|alt=Baumdiagramm|Abbildung 1: Ein abstrakter Stammbaum.

Baum-Diagramm In Diagrammen zur Visualisierung endlicher Teile von Stammbäumen verwendet man eine Terminologie, die in Abbildung 1 mit Hilfe eines abstrakten Baums erklärt wird. Auf der linken Seite bestimmt ein Niveau das grundlegende Top-Down-Design eines Stammbaums. In konkreten Bäumen, etwa in Abbildung 3, wird das Niveau üblicherweise ersetzt durch eine Skala von Ordnungen, die von Kopf bis Fuß zunehmen. Ein Vertex ist erweiterbar, wenn er zumindest einen unmittelbaren Nachfolger besitzt, anderenfalls ist er terminal (oder ein Blatt). Vertices mit einem gemeinsamen Vorgänger heißen Geschwister.

mini|alt=Koklassenbaum|Abbildung 2: Ein gestutzter abstrakter Koklassen-Baum.

Ist der Stammbaum ein Koklassen-Baum mit fester Koklasse Wurzel und mit Hauptlinie , deren Vertices dem Niveau entsprechend etikettiert sind, dann heißt der endliche Teilbaum, der als Differenz

definiert ist, der -te Zweig des Baums (Branch) oder auch der Zweig mit Wurzel , für jedes . Die Tiefe eines Zweigs ist die maximale Länge der Pfade, die seine Vertices mit seiner Wurzel verbinden. Abbildung 2 zeigt einen abstrakten Koklassen-Baum, dessen Zweige und vorperiodische Unregelmäßigkeiten aufweisen. Alle seine Zweige haben die Tiefe . Die Zweige und sind paarweise isomorph als Graphen, weil die Periodizität (mit Länge ) beim dritten Vertex der Hauptlinie, der periodischen Wurzel , einsetzt. Das Niveau der Ordnungen wird durch Verwendung eines Exponenten variabel belassen.

Wenn alle Vertices mit einer Tiefe oberhalb einer vorgegebenen ganzen Zahl aus dem Zweig entfernt werden, dann erhält man den auf die Tiefe gestutzten Zweig .Dementsprechend besteht der auf die Tiefe gestutzte Koklassen-Baum , beziehungsweise the vollständige Koklassen-Baum , aus der unendlichen Folge seiner gestutzten Zweige , beziehungsweise (vollen) Zweige , verbunden durch die Hauptlinie, deren Vertices als unendlich erweiterbar bezeichnet werden. In der Abbildung 2 ist der auf die Tiefe gestutzte Koklassen-Baum hervorgehoben.

Virtuelle Periodizität