En matemáticas , la enumeración de clases laterales es el problema de contar las clases laterales de un subgrupo H de un grupo G dado en términos de una presentación . Como subproducto, se obtiene una representación de permutación para G en las clases laterales de H. Si H tiene un orden finito conocido, la enumeración de clases laterales también da el orden de G.
Para grupos pequeños, a veces es posible realizar una enumeración de clases laterales a mano. Sin embargo, para grupos grandes requiere mucho tiempo y es propenso a errores, por lo que generalmente se realiza por computadora . La enumeración de Coset suele considerarse uno de los problemas fundamentales de la teoría computacional de grupos .
El algoritmo original para la enumeración de clases laterales fue inventado por John Arthur Todd y HSM Coxeter . Se han sugerido varias mejoras al algoritmo original de Todd-Coxeter , en particular las estrategias clásicas de V. Felsch y HLT (Haselgrove, Leech y Trotter). Una implementación práctica de estas estrategias con mejoras está disponible en el sitio web de ACE. [1] El algoritmo de Knuth-Bendix también puede realizar la enumeración de clases laterales y, a diferencia del algoritmo de Todd-Coxeter, a veces puede resolver el problema verbal para grupos infinitos.
Las principales dificultades prácticas para producir un enumerador de clases laterales son que es difícil o imposible predecir cuánta memoria o tiempo se necesitará para completar el proceso. Si un grupo es finito, entonces su enumeración de clases laterales debe terminar eventualmente, aunque puede llevar un tiempo arbitrariamente largo y utilizar una cantidad arbitraria de memoria, incluso si el grupo es trivial. Dependiendo del algoritmo utilizado, puede suceder que realizar pequeños cambios en la presentación que no cambian el grupo, sin embargo, tengan un gran impacto en la cantidad de tiempo o memoria necesaria para completar la enumeración. Estos comportamientos son consecuencia de la irresolubilidad del problema verbal para grupos .
En el texto de Rotman sobre teoría de grupos se ofrece una suave introducción a la enumeración de clases laterales. [2] Se puede encontrar información más detallada sobre la corrección, la eficiencia y la implementación práctica en los libros de Sims [3] y Holt et al. [4]