imported>Alabasterstein: /* Weblinks */

2024-05-22T13:04:31Z

Weblinks

Neue Seite

Der '''Todd-Coxeter-Algorithmus''' ist ein [[Algorithmus]] in der [[Gruppentheorie]], der nach den beiden britischen Mathematikern [[John Arthur Todd]] und [[Harold Scott MacDonald Coxeter]] benannt ist. Der Algorithmus ermöglicht es, für eine [[Untergruppe]] einer [[Endliche Gruppe|endlichen Gruppe]] die [[Gruppentheorie#Nebenklassen|Nebenklassen]] abzuzählen, wenn eine [[Präsentation einer Gruppe|Präsentation der Gruppe]] gegeben ist. Insbesondere ermöglicht der Algorithmus, die [[Ordnung einer Gruppe]] zu bestimmen.

== Algorithmus ==
Sei <math>G</math> eine endliche Gruppe und <math>H</math> eine Untergruppe von <math>G</math>. Der Todd-Coxeter-Algorithmus ist eine Methode, um die Nebenklassen von <math>H</math> in <math>G</math> abzuzählen. Zusätzlich lässt sich durch den Algorithmus auch die [[Gruppenoperation|Operation]] von <math>G</math> auf der Menge der Nebenklassen bestimmen.

Durch den Todd-Coxeter-Algorithmus gelangt man zwar mit endlich vielen Schritten ans Ziel, aber die [[Laufzeit (Informatik)|Rechenzeit]] ist nicht vorhersagbar.

Für eine Berechnung müssen eine endliche Präsentation der Gruppe <math>G</math> und ein endliches Erzeugendensystem der Untergruppe <math>H</math> explizit angegeben sein. Daher nehme man an, <math>G</math> sei durch die Erzeugenden <math>x_1,... ,x_m</math> und die Relationen <math>r_1,... , r_k</math> konkret dargestellt:

:<math> G= \left\langle x_1,... ,x_m; r_1,... , r_k \right\rangle</math>

Damit ist <math>G</math> als [[Faktorgruppe]] <math>F/N</math> realisiert, wobei <math>F</math> die [[freie Gruppe]] auf der Menge <math>\lbrace x_1, ... , x_m \rbrace</math> und <math>N</math> ein [[Normalteiler]] von <math>F</math> ist, der <math>\lbrace r_1,... , r_k \rbrace</math> enthält. Weiterhin sei vorausgesetzt, dass die Untergruppe <math>H</math> durch eine Menge von Wörtern in der freien Gruppe gegeben sei: <math>\lbrace h_1, ... , h_s \rbrace</math>, deren [[Bild (Mathematik)|Bilder]] in <math>G</math> die Untergruppe <math>H</math> erzeugen.

Beispielhaft sei die Gruppe <math>G</math> durch die drei Erzeugenden <math>x,y,z</math> und die Relationen <math>x^3,y^2,z^2,xyz</math> definiert und als Untergruppe <math>H</math> die von <math>z</math> erzeugte [[Gruppentheorie#Zyklische Gruppen|zyklische]] Untergruppe:

: <math>G= \left\langle x,y,z;x^3,y^2,z^2,xyz \right\rangle</math>, <math>H</math> erzeugt von <math> \lbrace z \rbrace</math>

Da die Operationen auf Nebenklassen bestimmt werden sollen und sich diese als Permutationsdarstellung beschreiben lassen, muss festgesetzt werden, wie diese explizit angegeben werden sollen. Es sei festgelegt, dass <math>G</math> von rechts operiert. Die Menge der ''Rechtsnebenklassen'' <math>H g</math> sei als <math> \mathcal{K}</math> bezeichnet. Um die Operation von <math>G</math> auf <math>\mathcal{K}</math> explizit anzugeben, sei die durch die erzeugenden Elemente <math>x,y,z</math> induzierte [[Permutation]] beschrieben.

Für die Operationen auf <math>\mathcal{K}</math> gelten folgende Regeln:

# Jede Erzeugende (hier: <math>x,y,z</math>) operiert als Permutation.
# Die Relation (hier: <math>x^3,y^2,z^2,xyz</math>) operiert trivial.
# Die Erzeugenden von <math>H</math> (hier:<math>z</math>) lassen die Nebenklasse <math>H 1</math> fest.
# Die Operation auf der Menge der Nebenklassen ist [[Gruppenoperation#Transitive_und_scharf_transitive_Operationen|transitiv]].

Die erste Regel ist eine allgemeine Eigenschaft von Gruppenoperationen, die aus der Invertierbarkeit von Gruppenelementen folgt. Die zweite Regel gilt, da die Relation in <math>G</math> das Element <math>1</math> repräsentiert, und eigentlich die Gruppe <math>G</math> operiert. Die Regeln 3 und 4 sind spezielle Eigenschaften der Operation auf Nebenklassen.

== Beispiel ==
[[Datei:Tetraeder animation with cube.gif|mini|Animation eines Tetraeders]]
Man betrachte die [[A4 (Gruppe)|Tetraedergruppe]] <math>T</math> der zwölf Drehsymmetrien eines regelmäßigen [[Tetraeder]]s. Die Drehungen um den Winkel <math>\tfrac{2 \pi}{3}</math> um zwei unterschiedliche Eckpunkte im bzw. gegen den Uhrzeigersinn werden mit <math>y</math> bzw. <math>x</math> bezeichnet. Daraus resultiert die Drehung um den Mittelpunkt einer Kante <math>xy=z</math> – das Produkt ist von rechts nach links zu lesen – um <math>\pi</math>. Es gelten folgende Relationen:
:<math>x^3=1, \quad y^3=1, \quad xyxy =1.</math>
Es wird zu zeigen sein, dass die genannten Relationen ''T'' definieren. Dafür betrachte man die Gruppe <math>G=\left\langle x,y;x^3,y^3,xyxy \right\rangle</math>. Da die Relationen in der Tetraedergruppe erfüllt sind, liefert die Abbildungseigenschaft von Faktorgruppen einen Homomorphismus <math> \varphi \colon G \to T</math>. Da ''x'' und ''y'' die Gruppe ''T'' erzeugen, ist der Homomorphismus [[surjektiv]]. Um nachzuweisen, dass <math>\varphi</math> [[Injektivität|injektiv]] ist, muss gezeigt werden, dass die Ordnung der Gruppe ''G'' gleich 12 ist.

Um das zu erreichen, könnte man die Nebenklassen der trivialen Untergruppe <math>H={1}</math> zählen und so die Ordnung von ''G'' ermitteln. Allerdings wäre das nicht sehr effizient. Günstiger ist es, eine nichttriviale Untergruppe ''H'' von ''G'' zu benutzen, wie beispielsweise diejenige, die von ''y'' erzeugt wird. Diese Untergruppe ''H'' hat wegen <math>y^3=1</math> höchstens die Ordnung 3. Es reicht damit zu zeigen, dass die Ordnung von ''H'' sogar gleich 3 und der Index von ''H'' in ''G'' gleich 4 ist. Das würde folgen, dass ''G'' die Ordnung 12 hat.

Laut Algorithmus wird die Permutationsdarstellung von ''G'' bestimmt, welche die Operation auf die Menge der Nebenklassen beschreibt. Als Bezeichnung für die Nebenklassen verwendet man beispielsweise Nummer 1, 2, 3, ... , wobei 1 für die Nebenklasse ''H''1 reserviert ist. Da man die Anzahl der Nebenklassen noch nicht kennt, kann man noch nicht entscheiden, wie viele Nummern benötigt werden. Im Laufe des Verfahrens werden schrittweise neue Nummern eingeführt, sobald sie gebraucht werden.

Das Verfahren liefert folgende Tabelle:

{| = class="wikitable"
| colspan=4 |<math> x\ x\ x </math> || colspan=3 | <math> y\ y\ y\ </math> || colspan=4 |<math> x\ y\ x\ y\ </math>
|-
| style="background:#efefef;"| 1 || 2 || 3 || style="background:#efefef;"|1 || 1 || 1|| style="background:#efefef;"|1 || 2 || 3 || 1 || style="background:#efefef;"|1
|-
| style="background:#efefef;"|2 || 3 || 1 || style="background:#efefef;"|2 || 3 || 4 || style="background:#efefef;"|2 || 3 || 4 || 4 || style="background:#efefef;"|2
|-
| style="background:#efefef;"|3 || 1 || 2 || style="background:#efefef;"|3 || 4 || 2 || style="background:#efefef;"|3 || 1 || 1 || 2 || style="background:#efefef;"|3
|-
| style="background:#efefef;"|4 || 4 || 4 || style="background:#efefef;"|4 || 2 || 3 || style="background:#efefef;"|4 || 4 || 2 || 3 || style="background:#efefef;"|4
|}

Aus dem Verfahren ergibt sich die zugehörige Permutationsdarstellung
:<math>x=(123), \quad y=(234).</math>

Da vier Ziffern vorkommen, ist der Index von ''H'' in ''G'' gleich 4. ''y'' hat die Ordnung 3, weil wegen der Relation <math>y^3=1</math> die Ordnung höchsten gleich 3 sein kann und sie ist mindestens gleich 3, weil die ''y'' zugeordnete Permutation die Ordnung 3 hat. Damit ist die Ordnung von ''G'' gleich 12. Die Permutationsdarstellung liefert außerdem einen [[Isomorphismus]] von ''T'' auf die von der Permutation erzeugten Gruppe. Man kann sich davon überzeugen, dass dies die alternierende Gruppe <math>A_4</math> ist. Damit ist die Tetraedergruppe ''T'' isomorph zu <math>A_4</math>.

== Literatur ==
* Todd, J. A.; Coxeter, H. S. M.: ''A practical method for enumerating cosets of a finite abstract group.'' in: ''Proceedings of the Edinburgh Mathematical Society'', Cambridge University Press 1936, Series II. 5: S. 26–34. ({{DOI|10.1017/S0013091500008221}})
* Coxeter, H. S. M., Moser, W. O. J.: ''Generators and Relations for Discrete Groups.'' Vol. 14 (4th ed.), Springer, 1980, ISBN 3-540-09212-9.
* [[Michael Artin]]: ''Algebra'', Birkhäuser Verlag, 1993, ISBN 3-7643-2927-0, S. 252–257.
* [[Ákos Seress]]: ''An introduction to computational group theory.'' Notices of the American Mathematical Society. 44 (6), S. 671–679. ([http://www.ams.org/notices/199706/seress.pdf Digitalisat])

== Siehe auch ==
* [[Coxeter-Gruppe]]

== Weblinks ==
* Kenn Brown: [https://pi.math.cornell.edu/~kbrown/7350/toddcox.pdf Aufsatz zum Todd-Coxeter-Algorithmus] (englisch)

[[Kategorie:Algebra]]
[[Kategorie:Algorithmus]]

Todd-Coxeter-Algorithmus - Versionsgeschichte

imported>Alabasterstein: /* Weblinks */