Algoritmo de Todd-Coxeter

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 laterales (dada por la acción de multiplicación izquierda). Si el orden de un grupo G es relativamente pequeño y se sabe que el subgrupo H no es complicado (por ejemplo, un grupo cíclico ), entonces el algoritmo se puede realizar a mano y proporciona una descripción razonable del grupo G. Utilizando 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 grupal 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 de la siguiente manera. Supongamos que , donde es un conjunto de generadores y es un conjunto de relaciones y se denota por el conjunto de generadores y sus inversas. Deje donde están las palabras de los elementos de . Se utilizarán tres tipos de tablas: una tabla de clases laterales, una tabla de relaciones para cada relación en y una tabla de subgrupos para cada generador de . La información se agrega gradualmente a estas tablas y, una vez completadas, se enumeran todas las clases laterales y el algoritmo finaliza. ${\displaystyle G=\langle X\mid R\rangle }$ ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle X'}$ ${\displaystyle X}$ ${\displaystyle H=\langle h_{1},h_{2},\ldots ,h_{s}\rangle }$ ${\displaystyle h_{i}}$ ${\displaystyle X'}$ ${\displaystyle R}$ ${\displaystyle h_{i}}$ ${\displaystyle H}$

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 . Denotemos la clase lateral de la i- ésima fila de la tabla de clases laterales y denotemos el 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 . ${\displaystyle H}$ ${\displaystyle X'}$ ${\displaystyle C_{i}}$ ${\displaystyle g_{j}\in X'}$ ${\displaystyle C_{k}=C_{i}g_{j}}$

Las tablas de relaciones se utilizan para detectar cuándo algunas de las clases laterales que hemos encontrado son realmente equivalentes. Se mantiene una tabla de relaciones para cada relación . Sea una relación en , donde . 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 j -ésima columna se define como (si se conoce) k , donde . En particular, la entrada 'ésima es inicialmente i , desde . ${\displaystyle R}$ ${\displaystyle 1=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}}$ ${\displaystyle R}$ ${\displaystyle g_{n_{i}}\in X'}$ ${\displaystyle H}$ ${\displaystyle C_{k}=C_{i}g_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}}$ ${\displaystyle (i,t)}$ ${\displaystyle g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}=1}$

Finalmente, las tablas de subgrupos son similares a las tablas de relaciones, excepto que realizan 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 de sí mismo. Tiene t columnas y la entrada en la j- ésima columna se define (si se conoce) como k , donde . ${\displaystyle H}$ ${\displaystyle h_{n}=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}}$ ${\displaystyle H}$ ${\displaystyle g_{n_{i}}\in X'}$ ${\displaystyle H}$ ${\displaystyle C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}}$

Cuando se completa una fila de una tabla de relación o subgrupo, se encuentra una nueva información , . Esto se conoce como deducción . A partir de la deducción, es posible que podamos completar entradas adicionales de las tablas de relaciones y subgrupos, lo que resultará en posibles deducciones adicionales. Podemos completar las entradas de la tabla de clases laterales correspondientes a las ecuaciones y . ${\displaystyle C_{i}=C_{j}g}$ ${\displaystyle g\in X'}$ ${\displaystyle C_{i}=C_{j}g}$ ${\displaystyle C_{j}=C_{i}g^{-1}}$

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 laterales son en realidad iguales, lo que se conoce como coincidencia . Supongamos que 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. ${\displaystyle C_{i}=C_{j}}$ ${\displaystyle i<j}$

Si hay entradas vacías en la tabla después de haber tenido en cuenta 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 todas . (Esto es necesario para garantizar que el algoritmo terminará siempre que sea finito). ${\displaystyle g\in X'}$ ${\displaystyle |G:H|}$

Cuando todas las tablas están llenas, el algoritmo termina. Entonces tenemos toda la información necesaria sobre la acción de sobre las clases laterales de . ${\displaystyle G}$ ${\displaystyle H}$

Ver también

• grupo coxeter

Referencias

• Todd, JA ; Coxeter, HSM (1936). "Un método práctico para enumerar clases laterales 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 . vol. 14 (4ª ed.). Springer-Verlag 1980. ISBN 3-540-09212-9. SEÑOR  0562913.
• Seress, Ákos (1997). "Una introducción a la teoría computacional de grupos" (PDF) . Avisos de la Sociedad Matemática Estadounidense . 44 (6): 671–679. SEÑOR  1452069.