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 llevar a cabo a mano y da 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 otra parte, para un par general que consiste en 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 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 inversos. Sea donde son palabras de elementos de . Hay tres tipos de tablas que se utilizarán: 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 que se completan, se han enumerado todas las clases laterales y el algoritmo termina. ${\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 al multiplicar por un generador. Tiene filas que representan clases laterales de y una columna para cada elemento de . Sea la clase lateral de la i -ésima fila de la tabla de clases laterales y sea 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 en . 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 la j ésima columna se define como (si se conoce) k , donde . En particular, la 'ésima entrada es inicialmente i , ya que . ${\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 mantienen un registro de las posibles relaciones de los generadores de . Para cada generador de , con , creamos una tabla de subgrupos. Tiene solo una fila, que corresponde a la clase lateral de sí misma. 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 relaciones o subgrupos, se encuentra una nueva pieza de información , , . Esto se conoce como deducción . A partir de la deducción, podemos completar entradas adicionales de las tablas de relaciones y subgrupos, lo que da como resultado 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 conduzca 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 que se hayan 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 todos los . (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}$

Véase 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.Sr. 0562913  .
• Seress, Ákos (1997). "Introducción a la teoría de grupos computacional" (PDF) . Avisos de la American Mathematical Society . 44 (6): 671–679. MR  1452069.