En matemáticas , la enumeración de clases sociales es el problema de contar las clases sociales 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, enumeración clase lateral da la orden de G también.
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 lleva a cabo por computadora . Por lo general, se considera que la enumeración de Coset es uno de los problemas fundamentales en 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 de palabras 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 tomar un tiempo arbitrariamente largo y usar una cantidad arbitraria de memoria, incluso si el grupo es trivial. Dependiendo del algoritmo utilizado, puede suceder que hacer pequeños cambios en la presentación que no cambien el grupo, sin embargo, tenga un gran impacto en la cantidad de tiempo o memoria necesarios para completar la enumeración. Estos comportamientos son consecuencia de la imposibilidad de resolver el problema verbal para los grupos .
En el texto de Rotman sobre teoría de grupos se ofrece una suave introducción a la enumeración de clases sociales. [2] Se puede encontrar información más detallada sobre corrección, eficiencia e implementación práctica en los libros de Sims [3] y Holt et al. [4]
Referencias
- ^ ACE: Advanced Coset Enumerator por George Havas y Colin Ramsay Archivado 2007-09-01 en Wayback Machine
- ^ Rotman, Joseph J. (1995). Introducción a la teoría de grupos . Saltador. ISBN 0-387-94285-8.
- ^ Sims, Charles C. (1994). Computación con grupos finamente presentados . Prensa de la Universidad de Cambridge. ISBN 0-521-43213-8.
- ^ Holt, Derek F. (2005). Un manual de teoría de grupos computacional . Prensa CRC. ISBN 1-58488-372-3.