Algoritmo de Todd-Coxeter

En teoría de grupos , el algoritmo de Todd-Coxeter , creado por J. A. Todd y H. M. M. Coxeter en 1936, es un algoritmo para resolver el problema de enumeración de clases laterales . Dado un grupo G representado 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 multiplicación por la izquierda). Si el orden de un grupo G es relativamente pequeño y se sabe que el subgrupo H es sencillo (por ejemplo, un grupo cíclico ), entonces el algoritmo puede llevarse a cabo manualmente 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 puede aplicarse a grupos infinitos y se sabe que finaliza en un número finito de pasos, siempre que el índice de H en G sea finito. Por otro lado, para un par general formado por 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.

Una implementación del algoritmo procede de la siguiente manera. Supongamos que${\displaystyle G=\langle X\mid R\rangle }$, dónde${\displaystyle X}$es un conjunto de generadores y${\displaystyle R}$es un conjunto de relaciones y se denota por${\displaystyle X'}$el conjunto de generadores${\displaystyle X}$y sus inversas. Sea${\displaystyle H=\langle h_{1},h_{2},\ldots ,h_{s}\rangle }$donde el${\displaystyle h_{i}}$son palabras de elementos de${\displaystyle X'}$. Hay tres tipos de tablas que se utilizarán: una tabla de clases laterales, una tabla de relaciones para cada relación en${\displaystyle R}$y una tabla de subgrupos para cada generador${\displaystyle h_{i}}$de${\displaystyle H}$La información se va añadiendo gradualmente a estas tablas y, una vez que se han completado, se han enumerado todas las clases laterales y el algoritmo finaliza.

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${\displaystyle H}$y una columna para cada elemento de${\displaystyle X'}$. Dejar${\displaystyle C_{i}}$Denotemos la clase lateral de la i- ésima fila de la tabla de clases laterales, y sea${\displaystyle g_{j}\in X'}$denota 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 C_{k}=C_{i}g_{j}}$.

Las tablas de relación se utilizan para detectar cuándo algunos de los conjuntos laterales que hemos encontrado son realmente equivalentes. Una tabla de relación para cada relación en${\displaystyle R}$se mantiene. Deje${\displaystyle 1=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}}$ser una relación en${\displaystyle R}$, dónde${\displaystyle g_{n_{i}}\in X'}$. La tabla de relaciones tiene filas que representan las clases laterales de${\displaystyle H}$, 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${\displaystyle C_{k}=C_{i}g_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}}$. En particular, el${\displaystyle (i,t)}$La entrada 'enésima es inicialmente i , ya que${\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${\displaystyle H}$. Para cada generador${\displaystyle h_{n}=g_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}}$de${\displaystyle H}$, con${\displaystyle g_{n_{i}}\in X'}$, creamos una tabla de subgrupos. Tiene solo una fila, que corresponde al conjunto de clases laterales de${\displaystyle H}$en sí mismo. Tiene t columnas, y la entrada en la j -ésima columna se define (si se conoce) como k , donde${\displaystyle C_{k}=Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{j}}}$. En particular, la última entrada es H , ya que${\displaystyle Hg_{n_{1}}g_{n_{2}}\cdots g_{n_{t}}=Hh_{n}=H}$.

Cuando se completa una fila de una tabla de relaciones o subgrupos, se agrega una nueva pieza de información.${\displaystyle C_{i}=C_{j}g}$,${\displaystyle g\in X'}$Se encuentra. Esto se conoce como una deducción . A partir de la deducción, podemos completar entradas adicionales de las tablas de relaciones y subgrupos, lo que da lugar a posibles deducciones adicionales. Podemos completar las entradas de la tabla de clases laterales correspondientes a las ecuaciones.${\displaystyle C_{i}=C_{j}g}$y${\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 con 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${\displaystyle C_{i}=C_{j}}$, con${\displaystyle i<j}$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.

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 todas${\displaystyle g\in X'}$. (Esto es necesario para garantizar que el algoritmo termine siempre que se cumpla la condición.${\displaystyle |G:H|}$es finito.)

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

• Grupo Coxeter

• 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-9MR 0562913 .​ 
• Seress, Ákos (1997). "Una introducción a la teoría computacional de grupos" (PDF) . Notices of the American Mathematical Society . 44 (6): 671– 679. MR 1452069 .