En teoría de grupos , el algoritmo de Todd-Coxeter , creado por JA Todd y HSM Coxeter en 1936, es un algoritmo para resolver el problema de enumeración de clases laterales . Dada una presentación de un grupo G por generadores y relaciones y un subgrupo H de G , el algoritmo enumera las clases laterales de H en G y describe la representación de permutación de G en el espacio de las clases sociales (dada por la acción de multiplicación izquierda). Si el orden de un grupo Ges relativamente pequeño y el subgrupo H es conocido por ser complicada (por ejemplo, un grupo cíclico ), entonces el algoritmo se puede llevar a cabo a mano y da una descripción razonable del grupo G . Usando su algoritmo, Coxeter y Todd demostraron que ciertos sistemas de relaciones entre generadores de grupos conocidos son completos, es decir, constituyen sistemas de relaciones definitorias.
El algoritmo de Todd-Coxeter se puede aplicar a grupos infinitos y se sabe que termina en un número finito de pasos, siempre que el índice de H en G sea finito. Por otro lado, para un par general que consta de una presentación de grupo y un subgrupo, su tiempo de ejecución no está limitado por ninguna función computable del índice del subgrupo y el tamaño de los datos de entrada.
Descripción del algoritmo
Una implementación del algoritmo procede como sigue. Suponer que, dónde es un conjunto de generadores yes un conjunto de relaciones y se denota por el conjunto de generadores y sus inversas. Dejar donde el son palabras de elementos de . Hay tres tipos de tablas que se utilizarán: una tabla lateral, una tabla de relaciones para cada relación eny una tabla de subgrupos para cada generador de . La información se agrega gradualmente a estas tablas y, una vez que se completan, se enumeran todas las clases laterales y el algoritmo termina.
La tabla de clases laterales se utiliza para almacenar las relaciones entre las clases laterales conocidas cuando se multiplica por un generador. Tiene filas que representan clases laterales de y una columna para cada elemento de . Dejardenotar la clase lateral de la i- ésima fila de la tabla de clase lateral, y seadenotar generador de la j- ésima columna. La entrada de la tabla de clases laterales en la fila i , columna j se define como (si se conoce) k , donde k es tal que.
Las tablas de relaciones se utilizan para detectar cuándo algunas de las clases laterales que hemos encontrado son realmente equivalentes. Una tabla de relaciones para cada relación enes mantenido. Dejar ser una relación en , dónde . La tabla de relaciones tiene filas que representan las clases laterales de, como en la tabla de clases laterales. Tiene t columnas, y la entrada en la i- ésima fila y la j- ésima columna se define como (si se conoce) k , donde. En particular, el'la entrada es inicialmente i , ya que.
Finalmente, las tablas de subgrupos son similares a las tablas de relaciones, excepto que hacen un seguimiento de las posibles relaciones de los generadores de . Para cada generador de , con , creamos una tabla de subgrupos. Tiene una sola fila, correspondiente a la clase lateral desí mismo. Tiene t columnas, y la entrada en la j- ésima columna se define (si se conoce) como k , donde.
Cuando se completa una fila de una tabla de relación o subgrupo, una nueva pieza de información , , es encontrado. Esto se conoce como deducción . A partir de la deducción, es posible que podamos completar entradas adicionales de las tablas de relación y subgrupo, lo que da como resultado posibles deducciones adicionales. Podemos completar las entradas de la tabla de clases laterales correspondientes a las ecuaciones y .
Sin embargo, al completar la tabla de clases laterales, es posible que ya tengamos una entrada para la ecuación, pero la entrada tenga un valor diferente. En este caso, hemos descubierto que dos de nuestras clases sociales son en realidad iguales, lo que se conoce como coincidencia . Suponer, con . Reemplazamos todas las instancias de j en las tablas con i . Luego, completamos todas las entradas posibles de las tablas, lo que posiblemente lleve a más deducciones y coincidencias.
Si hay entradas vacías en la tabla después de que se hayan resuelto todas las deducciones y coincidencias, agregue una nueva clase lateral a las tablas y repita el proceso. Nos aseguramos de que al agregar clases laterales , si Hx es una clase lateral conocida, entonces Hxg se agregará en algún momento para todos. (Esto es necesario para garantizar que el algoritmo terminará siempre que es finito.)
Cuando todas las tablas están llenas, el algoritmo termina. Entonces tenemos toda la información necesaria sobre la acción de en las clases laterales de .
Ver también
Referencias
- Todd, JA ; Coxeter, HSM (1936). "Un método práctico para enumerar clases sociales de un grupo abstracto finito" . Actas de la Sociedad Matemática de Edimburgo . Serie II. 5 : 26–34. doi : 10.1017 / S0013091500008221 . JFM 62.1094.02 . Zbl 0015.10103 .
- Coxeter, HSM ; Moser, WOJ (1980). Generadores y Relaciones para Grupos Discretos . Ergebnisse der Mathematik und ihrer Grenzgebiete . 14 (4ª ed.). Springer-Verlag 1980. ISBN 3-540-09212-9. Señor 0562913 .
- Seress, Ákos (1997). "Una introducción a la teoría de grupos computacional" (PDF) . Avisos de la Sociedad Matemática Estadounidense . 44 (6): 671–679. Señor 1452069 .