Un algoritmo de enumeración de cosets que calcula la acción de un grupo finitamente presentado sobre los cosets de un subgrupo especificado construyendo una tabla de cosets, identificando cosets mediante reladores y determinando así el índice del subgrupo y una representación por permutaciones cuando la enumeración termina de forma finita.

Principio

Crear y extender sistemáticamente una tabla de representantes de cosets, aplicar generadores y reladores para deducir identificaciones y coincidencias, y cerrar la tabla propagando consecuencias hasta que la tabla se estabilice (se encuentra índice finito) o el proceso crezca sin control (índice probablemente infinito o complejidad impracticable).

Demostración

Dada una presentación de grupo ⟨S | R⟩ y un subgrupo H generado por un conjunto finito, comenzar con el coset H como coset 1, aplicar generadores para producir nuevos nombres de cosets e imponer reladores para forzar identificaciones; registrar esto en la tabla de cosets. Si el proceso termina con una tabla finita y consistente, el número de cosets da el índice [G:H] y la acción de los generadores sobre los nombres de coset proporciona una representación por permutaciones.

Aplicación incorrecta

Intentar una enumeración Todd–Coxeter de forma ingenua cuando el subgrupo tiene índice infinito, o no implementar el procesamiento de coincidencias o las reglas de cierre adecuadas, conduce a la no terminación o a tablas incorrectas; interpretar una tabla parcial como completa sin verificar el cierre es un error común.

Consecuencia

Cuando tiene éxito, el algoritmo proporciona el índice del subgrupo, una representación explícita por permutaciones de G sobre los cosets y a menudo una herramienta práctica para estudiar la estructura de subgrupos, pero el éxito depende de la finitud y de los recursos computacionales.

Inversión

El problema inverso — recuperar una presentación a partir de una representación por permutaciones dada — es posible pero de naturaleza distinta (puede requerir Reidemeister–Schreier o métodos de estabilizador de cosets); Todd–Coxeter enumera cosets, no produce directamente presentaciones mínimas.

Límite

Aplicable a grupos finitamente presentados y a subgrupos dados por generadores; la eficacia requiere que el subgrupo tenga índice finito o que se acepten heurísticas de truncado. No garantiza terminación para subgrupos de índice infinito y puede ser costoso computacionalmente incluso cuando el índice es finito pero grande.

Tensión semántica

A menudo se contrasta con Reidemeister–Schreier (que produce presentaciones de subgrupos) y con estrategias de enumeración de subgrupos de índice bajo; la tensión surge al elegir entre enumerar cosets para obtener acciones por permutaciones y construir presentaciones explícitas de subgrupos.

Síntesis

El Algoritmo Todd–Coxeter es un procedimiento sistemático de enumeración de cosets que construye y cierra una tabla de cosets mediante generadores y reladores para determinar el índice de un subgrupo y producir representaciones por permutaciones cuando la enumeración termina; es eficaz en problemas de índice finito pero limitado por la no terminación y el coste computacional en casos difíciles.