Portal:Griechenland/Projekt

Der Todd-Coxeter-Algorithmus ist nach den zwei britischen Mathematikern John Arthur Todd und Harold Scott MacDonald Coxeter benannt. Sei $H$ eine Untergruppe von $G$ und $G$ eine endliche Gruppe. Der Todd-Coxeter-Algorithmus ist eine Methode um die Nebenklassen von $H$ in $G$ abzuzählen. Zusätzlich lässt sich durch den Algorithmus die Operation von $G$ auf die Menge der Nebenklassen bestimmen.

Durch den Todd-Coxeter-Algorithmus gelangt man in einer endlichen Zahl an Schritten ans Ziel, die Rechenzeit ist jedoch nicht vorhersagbar.

Für eine Berechnung müssen sowohl die Gruppe $G$ wie die Untergruppe $H$ explizit angegeben sein. Daher nehmen wir an, $G$ sei durch die Erzeugende $x_{1},...,x_{m}$ und die Relationen $r_{1},...,r_{k}$ konkret dargestellt:

$G=\left\langle x_{1},...,x_{m};r_{1},...,r_{k}\right\rangle$.

Damit ist $G$ als Faktorgruppe $F/N$ realisiert, wobei $F$ die freie Gruppe auf der Menge $\lbrace x_{1},...,x_{m}\rbrace$ und $N$ Normalteiler von $F$ ist, der $\lbrace r_{1},...,r_{k}\rbrace$ enthält. Weiterhin sei vorausgesetzt, dass die Untergruppe $H$ durch eine Menge von Wörtern in der freien Gruppe gegeben sei: $\lbrace h_{1},...,h_{s}\rbrace$, deren Bilder in $G$ die Untergruppe $H$ erzeugen.

Beispielhaft sei die Gruppe $G$ durch die drei Erzeugenden $x,y,z$ und den Relationen $x^{3},y^{2},z^{2},xyz$ definiert und als Untergruppe $H$ die von $z$ erzeugte zyklische Untergruppe:

$G=\left\langle x,y,z;x^{3},y^{2},xyz\right\rangle$, $H$ erzeugt von $\lbrace z\rbrace$

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 $G$ von rechts operiert. Die Menge der Rechtsnebenklassen $Hg$ sei als ${\mathcal {K}}$ bezeichnet. Um die Operation von $G$ auf ${\mathcal {K}}$ explizit anzugeben, seien die durch die erzeugende Elemente $x,y,z$ induzierte Permutation beschrieben.

Für die Operationen auf ${\mathcal {K}}$ gelten folgende Regeln:

1. Jedes Erzeugende (hier: $x,y,z$) operiert als Permutation.
2. Die Relation (hier: $x^{3},y^{2},z^{2},xyz$) operiert trivial.
3. Die Erzeugenden von $H$ (hier:$z$) lassen die Nebenklasse $H1$ fest.
4. Die Operation auf der Menge der Nebenklassen ist 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 $G$ das Element $1$ repräsentiert, und eigentlich die Gruppe $G$ operiert. Die Regeln 3 und 4 sind spezielle Eigenschaften der Operation auf Nebenklassen.

Weblinks

• Aufsatz zum Todd-Coxeter-Algorithmus (französisch)