P-Gruppen-Erzeugungs-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der -Gruppen-Erzeugungs-Algorithmus von Michael F. Newman[1] und E. A. O’Brien[2][3] ist innerhalb der algorithmischen Gruppentheorie ein rekursiver Prozess für die Konstruktion des Stammbaums einer vorgegebenen endlichen -Gruppe, die als Wurzel des Baums dient.

Dabei sind endliche -Gruppen endliche Gruppen mit Primpotenz-Ordnung , für eine feste Primzahl und veränderliche ganzzahlige Exponenten .

Dieser Algorithmus ist im Softwarepaket ANUPQ (Australian National University P-Quotient)[4] der Computer-Algebra-Systeme GAP (Groups-Algorithms-Programming) und Magma implementiert. Er ist unentbehrlich für die vertiefte Erforschung von endlichen -Gruppen, weil die SmallGroups Datenbank von H. U. Besche, B. Eick and E. A. O’Brien[5][6] für jede Primzahl nur -Gruppen mit Ordnungen bis zu einer von abhängigen oberen Schranke enthält, beispielsweise für , für und für . Alle -Gruppen mit höherer Ordnung als müssen mit dem sehr leistungsfähigen und schnellen -Gruppen-Erzeugungs-Algorithmus konstruiert werden, wobei für kleine Primzahlen durchaus noch Ordnungen um innerhalb der experimentellen Reichweite liegen.

Untere Exponent-p-Zentralreihe

[Bearbeiten | Quelltext bearbeiten]

Für eine endliche -Gruppe ist die untere Exponent--Zentralreihe (kurz untere -Zentralreihe) von eine absteigende Reihe charakteristischer Untergruppen von und wird rekursiv erklärt durch

und , für .

Weil jede nicht-triviale endliche -Gruppe nilpotent ist, gibt es eine ganze Zahl , sodass der -Term der Reihe, , erstmals trivial wird, und diese Zahl wird als Exponent--Klasse (kurz -Klasse) von bezeichnet. Nur die triviale Gruppe hat die -Klasse . Generell kann für eine endliche -Gruppe ihre -Klasse als das Minimum definiert werden.

Die vollständige untere -Zentralreihe von ist daher gegeben durch

,

weil die Frattini Untergruppe von ist.

Zum Vergleich und vor allem, um die verschobene Nummerierung hervorzuheben, sei erwähnt, dass die (gewöhnliche) untere Zentralreihe von ebenfalls eine absteigende Reihe charakteristischer Untergruppen von ist und rekursiv definiert wird durch

und , für .

Analog wie oben existiert zu jeder nicht-trivialen endlichen -Gruppe eine ganze Zahl sodass der -Term der Reihe, , erstmals trivial wird, und diese Zahl wird die Nilpotenzklasse (kurz Klasse) von genannt, während als Index der Nilpotenz von bezeichnet wird. Die triviale Gruppe hat als einzige den Nilpotenzindex und somit die Klasse .

Die untere Zentralreihe von ist in ihrer Gesamtheit gegeben durch

,

weil die Kommutatoruntergruppe oder abgeleitete Untergruppe von ist.

Die folgenden vier Rechenregeln sind für das Arbeiten mit der Exponent- Klasse nützlich:

Es sei eine endliche -Gruppe.

R
  1. Regel: , weil die Terme rascher absteigen als die (R1).
  2. Regel: Ist , mit irgendeiner Gruppe , dann gilt , für alle (R2).
  3. Regel: Für implizieren die Bedingungen und , dass (R3).
  4. Regel: Sei . Wenn , dann ist , für alle , speziell, , für alle (R4).

Vorgänger und Stammbäume

[Bearbeiten | Quelltext bearbeiten]

Der (unmittelbare) Vorgänger einer endlichen nicht-trivialen -Gruppe mit Exponent--Klasse ist definiert als der Quotient von nach dem letzten nicht-trivialen Term der unteren Exponent--Zentralreihe von . Umgekehrt wird in diesem Fall ein unmittelbarer Nachfolger von genannt. Die -Klassen von Vorgänger und unmittelbarem Nachfolger sind verbunden durch die Beziehung .

Ein Stammbaum ist eine hierarchische Struktur zur anschaulichen Visualisierung von Vorgänger-Nachfolger Relationen zwischen Isomorphieklassen endlicher -Gruppen. Die Vertices (Knoten, Ecken) eines Stammbaums sind Isomorphieklassen von endlichen -Gruppen. In Baum-Diagrammen wird jedoch ein Vertex stets durch Auswahl eines konkreten Repräsentanten der entsprechenden Isomorphieklasse etikettiert. Wenn ein Vertex der unmittelbare Vorgänger eines anderen Vertex ist, so wird eine gerichtete Kante des Stammbaums definiert durch in Richtung der kanonischen Projektion auf den Quotienten .

In einem Stammbaum können die Begriffe unmittelbarer Vorgänger und unmittelbarer Nachfolger folgendermaßen verallgemeinert werden. Ein Vertex ist ein Nachfolger eines Vertex , und umgekehrt ist ein Vorgänger von , wenn entweder mit übereinstimmt oder wenn ein Pfad

, mit der Länge ,

von gerichteten Kanten von zu existiert. Die Vertices, welche den Pfad bilden, stimmen notwendigerweise überein mit den iterierten Vorgängern von , wobei :

, mit .

Sie können auch aufgefasst werden als die sukzessiven Quotienten der p-Klasse von , wenn die p-Klasse von gegeben ist durch :

, wobei .

Insbesondere definiert jede nicht-triviale endliche -Gruppe einen maximalen Pfad, der aus gerichteten Kanten besteht,

,

und in der trivialen Gruppe endigt. Der vorletzte Quotient des Maximalpfades von ist die elementar-abelsche -Gruppe , also der Frattini-Quotient vom Rang , wobei den Generatoren-Rang (oder Erzeugenden-Rang) von bezeichnet (Basissatz von Burnside).

Generell 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 exzeptionell, weil die triviale Gruppe die unendlich vielen elementar-abelschen -Gruppen mit variablem Generatoren-Rang als ihre unmittelbaren Nachfolger besitzt. Eine nicht-triviale endliche -Gruppe (mit durch teilbarer Ordnung) besitzt jedoch nur endlich viele unmittelbare Nachfolger.

Einhüllende p-Gruppe, p-Multiplikator und Nucleus

[Bearbeiten | Quelltext bearbeiten]

Ist eine endliche -Gruppe mit Erzeugenden, so möchte man in einem einzelnen Rekursionsschritt des -Gruppen-Erzeugungs-Algorithmus eine vollständige Liste paarweise nicht-isomorpher unmittelbarer Nachfolger von zusammenstellen. Es stellt sich heraus, dass sich alle unmittelbaren Nachfolger konstruieren lassen als Quotienten einer gewissen Erweiterung von , welche die einhüllende -Gruppe (-covering group) von genannt und in folgender Weise definiert wird.

Es existiert stets eine Präsentation von in Form einer exakten Sequenz

,

wobei die freie Gruppe mit Erzeugern und einen Epimorphism mit Kern bezeichnet. Dann ist ein Normalteiler von , der aus den definierenden Relationen für besteht. Für beliebige Elemente und , ist das konjugierte Element und daher auch der Kommutator in enthalten. Folglich ist eine charakteristische Untergruppe von , und der -Multiplikator von ist eine elementar-abelsche -Gruppe, weil

.

Nun kann die einhüllende -Gruppe von definiert werden als Quotient

,

und die exakte Sequenz

zeigt, dass eine (Gruppen-)Erweiterung von mittels des elementar-abelschen -Multiplikators ist. Man nennt

den -Multiplikator-Rang von , der mit dem Relationen-Rang von übereinstimmt.

Unter der Annahme, dass die vorgegebene endliche -Gruppe von der -Klasse ist, dann implizieren die Bedingungen und , dass ist, gemäß Regel (R3), und der Nucleus von kann definiert werden durch

als eine (ebenfalls elementar-abelsche) Untergruppe des -Multiplikators. Folglich ist der nukleare Rang

von durch den -Multiplikator-Rang nach oben beschränkt.

Erlaubte Untergruppen des p-Multiplikators

[Bearbeiten | Quelltext bearbeiten]

Auch weiterhin sei eine endliche -Gruppe mit Erzeugenden.

Vorbereitungssatz. Jede -elementare abelsche zentrale Erweiterung

von mit einer -elementaren abelschen Untergruppe sodass ist ein Quotient der einhüllenden -Gruppe von . ( bezeichnet das Zentrum von .)

Beweis. Wegen existiert ein (von induzierter) Epimorphismus , sodass , wobei die kanonische Projektion bezeichnet. Unter Verwendung aller Voraussetzungen ergibt sich

und daher . Ferner ist trivial, weil als -elementar angenommen wurde, und , weil zentral ist. Zusammengenommen folgt und somit induziert den gewünschten Epimorphismus , sodass sich als Quotient von darstellen lässt. (Ende des Beweises.)

Insbesondere ist ein unmittelbarer Nachfolger von eine -elementare abelsche zentrale Erweiterung

von , weil aus folgt, dass und , wobei .

Definition. Eine Untergruppe des -Multiplikators von wird als erlaubt bezeichnet, wenn sie als Kern eines Epimorphismus auf einen unmittelbaren Nachfolger von gegeben ist.

Eine äquivalente Charakterisierung ist, dass eine echte Untergruppe ist, welche den Nucleus ergänzt

.

Demnach ist der erste Teil des Vorhabens, eine vollständige Liste aller unmittelbaren Nachfolger von zusammenzustellen, erledigt, wenn alle erlaubten Untergruppen von konstruiert sind, welche den Nucleus ergänzen, wobei . Im Allgemeinen wird aber die Liste

,

wobei , redundant sein, infolge von gewissen Isomorphismen zwischen den unmittelbaren Nachfolgern.

Orbits unter fortgesetzten Automorphismen

[Bearbeiten | Quelltext bearbeiten]

Zwei erlaubte Untergruppen und des -Multiplikators von heißen äquivalent, wenn die Quotienten , also die entsprechenden unmittelbaren Nachfolger von , isomorph sind.

Ein solcher Isomorphismus zwischen unmittelbaren Nachfolgern von mit hat die Eigenschaft, dass . Er induziert daher einen Automorphismus von , der fortgesetzt werden kann zu einem Automorphismus der einhüllenden -Gruppe von . Die Einschränkung dieses fortgesetzten Automorphismus auf den -Multiplikator von ist durch eindeutig bestimmt.

Wegen der Beziehung induziert jeder fortgesetzte Automorphismus eine Permutation der erlaubten Untergruppen . Man definiert als die Permutationsgruppe, welche von allen durch Automorphismen von induzierten Permutationen erzeugt wird. Dann ist die Abbildung , ein Epimorphismus und die Äquivalenzklassen erlaubter Untergruppen sind genau die Orbits erlaubter Untergruppen unter der Operation der Permutationsgruppe .

Letztendlich wird das Ziel, eine vollständige und irredundante Liste aller unmittelbaren Nachfolger von zusammenzustellen, erreicht, wenn man einen Repräsentanten aus jedem der Orbits erlaubter Untergruppen des -Multiplikators unter der Operation der Permutationsgruppe auswählt. Das ist genau der Prozess, welchen der -Gruppen-Erzeugungs-Algorithmus in einem Einzelschritt der rekursiven Prozedur für die Konstruktion des Stammbaums einer vorgegebenen Wurzel durchführt.

Erweiterbare p-Gruppen und Schrittweite

[Bearbeiten | Quelltext bearbeiten]

Eine endliche -Gruppe heißt erweiterbar, wenn sie zumindest einen unmittelbaren Nachfolger besitzt. Anderenfalls wird sie als terminal (oder Blatt) bezeichnet. Der nukleare Rang von erlaubt eine Entscheidung über die Erweiterbarkeit von :

  • ist genau dann terminal, wenn .
  • ist genau dann erweiterbar, wenn .

Im Fall der Erweiterbarkeit besitzt unmittelbare Nachfolger mit verschiedenen Schrittweiten , in Abhängigkeit vom Index der entsprechenden erlaubten Untergruppen im -Multiplikator . Ist von der Ordnung , dann hat ein unmittelbarer Nachfolger der Schrittweite die Ordnung .

Für das verwandte Phänomen der Multifurkation eines Stammbaums an einem Vertex mit nuklearem Rang siehe den Artikel über Stammbäume.

Der -Gruppen-Erzeugungs-Algorithmus bietet die Flexibilität, die Konstruktion unmittelbarer Nachfolger auf jene mit einer einzelnen festen Schrittweite zu beschränken. Diese Freiheit ist sehr vorteilhaft im Fall von außergewöhnlich großen Anzahlen von Nachfolgern (siehe den nächsten Abschnitt).

Anzahl der unmittelbaren Nachfolger

[Bearbeiten | Quelltext bearbeiten]

Man bezeichnet die Anzahl aller unmittelbaren Nachfolger, beziehungsweise der unmittelbaren Nachfolger der Schrittweite , von durch , beziehungsweise . Dann gilt also die Summenbeziehung . Es ist illustrativ, einige interessante endliche metabelsche -Gruppen mit ausgedehnten Kollektionen unmittelbarer Nachfolger vorzustellen. Zur Identifikation der Gruppen verwendet man üblicherweise die SmallGroups Datenbank. Zusätzlich empfiehlt es sich, die Anzahlen der erweiterbaren unmittelbaren Nachfolger hervorzuheben, im üblichen Format , das von aktuellen Implementierungen des -Gruppen-Erzeugungs-Algorithmus in den Computer-Algebra Systemen GAP und MAGMA ausgegeben wird.

Zuerst sei .

Die einfachsten Gruppen besitzen Kommutator-Quotienten des Typs . Siehe die Figur 4 im Artikel über Stammbäume.

  • Die Gruppe mit Koklasse hat die Ränge , und Nachfolgerzahlen , .
  • Die Gruppe mit Koklasse hat die Ränge , und Nachfolgerzahlen , .
  • Einer ihrer unmittelbaren Nachfolger, die Gruppe , hat die Ränge , und Nachfolgerzahlen , .

Im Gegensatz dazu befinden sich Gruppen mit Kommutator-Quotient des Typs teilweise bereits jenseits des Bereichs der Berechenbarkeit.

  • Die Gruppe mit Koklasse hat die Ränge , und Nachfolgerzahlen , .
  • Die Gruppe mit Koklasse hat die Ränge , und Nachfolgerzahlen , unbekannt.
  • Die Gruppe mit Koklasse hat die Ränge , und Nachfolgerzahlen , unbekannt.

Nun sei .

Vergleichbare Gruppen mit Kommutator-Quotient des Typs besitzen größere Anzahlen von Nachfolgern als jene mit .

  • Die Gruppe mit Koklasse hat die Ränge , und Nachfolgerzahlen , .
  • Die Gruppe mit Koklasse hat die Ränge , und Nachfolgerzahlen , .

Schur-Multiplikator

[Bearbeiten | Quelltext bearbeiten]

Vermittelt durch den Isomorphismus , , kann die Quotientengruppe als additives Analogon zur multiplikativen Gruppe aller Einheitswurzeln angesehen werden.

Ist eine Primzahl und eine endliche -Gruppe mit Präsentation , wie in einigen obenstehenden Abschnitten, dann wird die zweite Kohomologiegruppe des -Moduls als Schur-Multiplikator von bezeichnet. Dieser kann auch als Quotientengruppe interpretiert werden.

I. R. Shafarevich[7] hat bewiesen, dass die Differenz zwischen dem Relationen-Rang von und dem Erzeugenden-Rang von durch die minimale Anzahl von Generatoren des Schur Multiplikators von gegeben ist, also .

N. Boston und H. Nover[8] haben gezeigt, dass , für alle Quotienten mit -Klasse , , einer pro--Gruppe mit endlichem Kommutator-Quotienten .

Ferner hat J. Blackhurst im Anhang On the nucleus of certain -groups der Abhandlung von N. Boston, M. R. Bush und F. Hajir[9] bewiesen, dass eine nicht-zyklische endliche -Gruppe mit trivialem Schur Multiplikator ein terminaler Vertex im Stammbaum der trivialen Gruppe ist, das heißt, .

  • Eine endliche -Gruppe hat genau dann eine ausgewogene Präsentation , wenn , also genau dann, wenn ihr Schur Multiplikator trivial ist. Eine solche Gruppe wird als Schur Gruppe (oder geschlossene Gruppe in der älteren Literatur) bezeichnet und sie muss ein Blatt im Stammbaum sein.
  • Eine endliche -Gruppe genügt genau dann der Bedingung , wenn , also genau dann, wenn sie einen nicht-trivialen zyklischen Schur-Multiplikator besitzt. Eine solche Gruppe wird Schur+1 Gruppe genannt.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Michael F. Newman: Determination of groups of prime-power order. In: Robert A. Bryce, John Cossey, Michael F. Newman (Hrsg.): Group Theory. Proceedings of a Miniconference held at the Australian National University, Canberra, November 4–6, 1975 (= Lecture Notes in Mathematics. 573). Springer, Berlin u. a. 1977, ISBN 3-540-08131-3, S. 73–84.
  2. Eamonn A. O’Brien: The -group generation algorithm. In: Journal of Symbolic Computation. Band 9, Nummer 5/6, 1990, S. 677–698, doi:10.1016/S0747-7171(08)80082-X
  3. Derek F. Holt, Bettina Eick, Eamonn A. O’Brien: Handbook of computational group theory. Chapman & Hall/CRC, Boca Raton FL u. a. 2005, ISBN 1-58488-372-3.
  4. Greg Gamble, Werner Nickel, Eamonn A. O’Brien: ANU p-Quotient –– p-Quotient and p-Group Generation Algorithms. 2006, An Accepted GAP 4 Package, Available also in MAGMA.
  5. Hans Ulrich Besche, Bettina Eick, Eamonn A. O’Brien: The SmallGroups Library – a library of groups of small order. An accepted and refereed GAP 4 Package, available also in MAGMA, 2005.
  6. Hans Ulrich Besche, Bettina Eick, Eamonn A. O’Brien: A millennium project: constructing small groups. In: International Journal of Algebra and Computation. Band 12, Nummer 5, 2002, S. 623–644, doi:10.1142/s0218196702001115.
  7. Игорь Р. Шафаревич: Расширения с Заданными Точками Вветвления. In: Institut des Hautes Ètudes. Publications mathématiques de l’IHES. Band 18, 1963, S. 71–92, (Englisch: Igor R. Šafarevič: Extensions with given points of ramification. In: American Mathematical Society. Translations. Serie 2, Band 59, 1966, S. 128–149).
  8. Nigel Boston, Harris Nover: Computing Pro- Galois Groups. In: Florian Hess, Sebastian Pauli, Michael Pohst (Hrsg.): Algorithmic Number Theory. 7th International Symposium, ANTS-VII. Berlin, Germany, July 23–28, 2006. Proceedings (= Lecture Notes in Computer Science. 4076). Springer, Berlin u. a. 2006, ISBN 3-540-36075-1, S. 1–10, doi:10.1007/11792086_1.
  9. Nigel Boston, Michael R. Bush, Farshid Hajir: Heuristics for -class towers of imaginary quadratic fields. With an Appendix by Jonathan Blackhurst. In: Mathematische Annalen. Band 368, Nummer 1/2, 2017, S. 633–669, arxiv:1111.4679.