Ein Coset-Enumerations-Algorithmus, der die Wirkung einer endlich präsentierten Gruppe auf den Nebenklassen eines gegebenen Untergruppes berechnet, indem er eine Coset-Tabelle aufbaut, Cosets mittels Relatoren identifiziert und so den Index der Untergruppe und eine Permutationsdarstellung bestimmt, falls die Enumeration endlich terminiert.

Prinzip

Systematisch eine Tabelle von Coset-Vertretern anlegen und erweitern, Erzeuger und Relatoren anwenden, um Identifikationen und Zufälle zu folgern, und die Tabelle durch Propagierung der Konsequenzen schließen, bis die Tabelle stabilisiert (endlicher Index gefunden) oder der Prozess unbeschränkt wächst (wahrscheinlich unendlicher Index oder unpraktische Komplexität).

Demonstration

Gegeben eine Gruppenpräsentation ⟨S | R⟩ und eine Untergruppe H erzeugt durch eine endliche Menge, beginnt man mit dem Coset H als Coset 1, wendet Erzeuger an, um neue Coset-Bezeichnungen zu erzeugen, und zwingt durch Relatoren Identifikationen; alles wird in der Coset-Tabelle verzeichnet. Terminiert der Prozess mit einer endlichen konsistenten Tabelle, so liefert die Anzahl der Cosets den Index [G:H] und die Wirkung der Erzeuger auf Coset-Bezeichnungen ergibt eine Permutationsdarstellung.

Fehlanwendung

Der Versuch, Todd–Coxeter naiv anzuwenden, wenn die Untergruppe unendlichen Index hat, oder das Versäumnis, Kovrenzen (coincidences) und korrekte Abschlussregeln zu verarbeiten, führt zu Nichtterminierung oder falschen Tabellen; eine partielle Tabelle als abgeschlossen zu interpretieren ohne Abschlussprüfung ist ein häufiger Fehler.

Konsequenz

Bei Erfolg liefert der Algorithmus den Untergruppenindex, eine explizite Permutationsdarstellung von G auf den Cosets und oft ein praktisches Werkzeug zur Untersuchung der Untergruppenstruktur; der Erfolg hängt jedoch von Endlichkeit und Rechenressourcen ab.

Umkehrung

Das inverse Problem — eine Präsentation aus einer gegebenen Permutationsdarstellung zurückzugewinnen — ist zwar möglich, unterscheidet sich aber methodisch (erfordert z. B. Reidemeister–Schreier oder Stabilisatorenmethoden); Todd–Coxeter enumeriert Cosets, er erzeugt nicht direkt minimale Präsentationen.

Abgrenzung

Anwendbar auf endlich präsentierte Gruppen und Untergruppen angegeben durch Erzeuger; effektiv ist das Verfahren nur, wenn die Untergruppe endlichen Index hat oder wenn Trunkierungsheuristiken akzeptierbar sind. Für Untergruppen mit unendlichem Index ist keine Terminierung garantiert, und selbst bei endlichem aber großem Index kann das Verfahren rechnerisch teuer werden.

Semantische Spannung

Steht häufig im Kontrast zu Reidemeister–Schreier (Erzeugung von Untergruppenpräsentationen) und zu Strategien zur Aufzählung von Untergruppen mit kleinem Index; die Spannung besteht in der Wahl zwischen der Coset-Enumeration zur Gewinnung von Permutationsaktionen und der Konstruktion expliziter Untergruppenpräsentationen.

Synthese

Der Todd–Coxeter-Algorithmus ist ein systematisches Verfahren zur Coset-Enumeration, das eine Coset-Tabelle mittels Erzeugern und Relatoren aufbaut und schließt, um den Untergruppenindex zu bestimmen und Permutationsdarstellungen zu erzeugen, falls die Enumeration terminiert; mächtig bei endlichen Indexproblemen, aber durch Nichtterminierung und Rechenaufwand in schwierigen Fällen begrenzt.