Un algorithme d'énumération de cosets qui calcule l'action d'un groupe à présentation finie sur les cosets d'un sous-groupe spécifié en construisant une table de cosets, en identifiant des cosets à l'aide des relateurs, et en déterminant ainsi l'indice du sous-groupe et une représentation par permutations lorsque l'énumération termine de façon finie.

Principe

Créer et étendre systématiquement une table de représentants de cosets, appliquer générateurs et relateurs pour déduire identifications et coïncidences, et fermer la table en propageant les conséquences jusqu'à ce que la table se stabilise (indice fini trouvé) ou que le processus croisse indéfiniment (indice probablement infini ou complexité impraticable).

Démonstration

Pour une présentation de groupe ⟨S | R⟩ et un sous-groupe H engendré par un ensemble fini, commencer avec le coset H comme coset 1, appliquer les générateurs pour produire de nouveaux noms de cosets et imposer les relateurs pour forcer des identifications ; consigner ces informations dans la table de cosets. Si le processus termine avec une table finie et cohérente, le nombre de cosets donne l'indice [G:H] et l'action des générateurs sur les noms de cosets fournit une représentation par permutations.

Mauvaise application

Tenter une énumération Todd–Coxeter naïve lorsque le sous-groupe a indice infini, ou omettre le traitement des coïncidences ou des règles de fermeture appropriées, conduit à la non-terminaison ou à des tables incorrectes ; interpréter une table partielle comme complète sans vérifier la fermeture est une erreur commune.

Conséquence

En cas de succès, l'algorithme fournit l'indice du sous-groupe, une représentation explicite par permutations de G sur les cosets, et souvent un outil pratique pour calculer la structure des sous-groupes, mais la réussite dépend de la finitude et des ressources de calcul.

Inversion

Le problème inverse — retrouver une présentation à partir d'une représentation par permutations donnée — est possible mais de nature différente (il peut nécessiter Reidemeister–Schreier ou des méthodes de stabilisateur de cosets) ; Todd–Coxeter énumère des cosets, il ne produit pas directement des présentations minimales.

Limite

S'applique à des groupes à présentation finie et à des sous-groupes donnés par leurs générateurs ; l'efficacité requiert que le sous-groupe ait un indice fini ou que des heuristiques de troncation soient acceptables. Il n'est pas garanti de terminer pour des sous-groupes d'indice infini et peut être coûteux en calcul même si l'indice est fini mais grand.

Tension sémantique

Souvent mis en contraste avec Reidemeister–Schreier (qui fournit des présentations de sous-groupes) et avec des stratégies d'énumération de sous-groupes d'indice faible ; la tension porte sur le choix entre énumérer des cosets pour obtenir des actions par permutations et construire des présentations explicites des sous-groupes.

Synthèse

L'Algorithme Todd–Coxeter est une procédure systématique d'énumération de cosets qui construit et ferme une table de cosets via générateurs et relateurs pour déterminer l'indice d'un sous-groupe et produire des représentations par permutations lorsque l'énumération termine ; il est puissant pour les problèmes d'indice fini mais limité par la non-terminaison et le coût computationnel dans les cas difficiles.