Algoritmo de Schreier–Sims

Algoritmo de Schreier–Sims
Tipo	Teoria de grupos computacional
Creador	Otto Schreier y Charles Sims
Fecha	1970

El algoritmo de Schreier-Sims es un algoritmo basado en los estudios del matemático Otto Schreier y desarrollado por Charles Sims alrededor de los años 1970 y 1971. Este algoritmo busca encontrar una base, definida como una secuencia de puntos estabilizados, y un conjunto generador fuerte del grupo o SGS por sus siglas en inglés (Strong Generating Set), dado un conjunto generador.

El orden de un grupo de permutación es comparable al del grupo simétrico del cual es subgrupo, es decir de orden factorial sobre ${\displaystyle n}$ (donde ${\displaystyle \{1,2,...,n\}}$ es el conjunto asociado al grupo simétrico). Debido a esto, el enfoque de fuerza bruta no es una opción a la hora de calcular el orden del grupo ${\displaystyle G}$ dado un conjunto generador de ${\displaystyle G}$, determinar si un elemento en ${\displaystyle S_{n}}$ pertenece a ${\displaystyle G}$ o algunas otras operaciones de verificación o generación de elementos en ${\displaystyle G}$.

El algoritmo se basa en la teoría de acción de grupos para calcular la base o cadena de estabilizadores del grupo ${\displaystyle G}$ para, finalmente, obtener el SGS, es decir, una representación del grupo simétrico que permite computar eficientemente sobre este.

Este problema está clasificado como un algoritmo de teoría de grupos computacional, el mismo permite computar el orden, listar elementos, generar elementos aleatorios, verificar la pertenencia de elementos e insertar elementos en el grupo eficientemente.

Autores

Charles C. Sims en Oberwolfach en el 2006

Charles Coffin Sims

(14 de abril de 1938 – 23 de octubre de 2017[1]​) fue un matemático estadounidense conocido por su trabajo en teoría de grupos.[2]​ Sims es oriundo de Elkhart, Indiana, graduado de la Universidad de Míchigan.[2]​ Hizo su postgrado en la Universidad de Harvard y recibió su Ph.D. en 1963. Sims es uno de los fundadores de la teoría de grupos computacionales. Fue miembro del Departamento de matemáticas de la Universidad de Rutgers de 1965 al 2007. Se retiró de Rutgers in 2007.[3]​ En 2012 se convirtió en miembro de la Sociedad Americana de Matemáticas.[4]​

Otto Schreier

(3 de marzo de 1901 – 2 de junio de 1929 ) fue un matemático austriaco[5]​ que hizo grandes contribuciones en teoría de grupos combinacional y en la topología de grupos de Lie. Estudió en la Universidad de Vienna y obtuvo su doctorado en 1923. Schreier se trasladó después a la Universidad de Hamburgo. En 1928 se volvió profesor en la Universidad de Rostock. Dictó cátedras en Hamburgo y Rostock al mismo tiempo, pero en diciembre de 1928 se enfermó de sepsis, de la cual moriría medio año después.

Descripción

El algoritmo de Schreier-Sims es un algoritmo resultado de la continua necesidad del guardado y representación computacional eficiente de un grupo de permutaciones. El algoritmo busca entregar conjuntos representativos de los co-sets, una base y un conjunto generador fuerte del grupo a representar, todo esto se define y explica a continuación:[6]​

Definición 1: Sea ${\displaystyle G}$ un grupo de permutación, se define su secuencia:

$${\displaystyle G=G^{(1)}\geq G^{(2)}\geq ...\geq G^{(k)}\geq G^{(k+1)}=e}$$

en la que ${\displaystyle G^{(i+1)}}$ es un subgrupo de ${\displaystyle G^{(i)}}$.

Definición 2: Sea ${\displaystyle G}$ un grupo de permutación, ${\displaystyle g\in G}$ una permutación, ${\displaystyle H\leq G}$ un subgrupo de ${\displaystyle G}$ y ${\displaystyle h\in H}$un elemento del subgrupo, se define su co-set:

$${\displaystyle H\cdot g=\{h\cdot g:h\in H\}}$$

Para la cadena de subgrupos de ${\displaystyle G}$, es posible escoger un conjunto ${\displaystyle U^{(i)}}$compuesto por los representantes de los co-sets para ${\displaystyle G^{(i+1)}}$en ${\displaystyle G^{(i)}}$. Para ${\displaystyle i=1}$, un elemento ${\displaystyle g\in G}$ está en exactamente un co-set de ${\displaystyle G^{(2)}}$ en ${\displaystyle G^{(1)}}$ . Por ende, ${\displaystyle g=h\cdot u_{1}}$, para unos únicos ${\displaystyle h\in G^{(2)}}$ y ${\displaystyle U^{(1)}}$. Es posible observar que, por inducción, para un elemento ${\displaystyle g\in G}$:[6]​

$${\displaystyle g=u_{k}\cdot u_{k}\cdot u_{k-1}\cdot ...\cdot u_{1}}$$

siendo cada ${\displaystyle u_{i}\in U^{(i)}}$únicamente determinado por ${\displaystyle g}$. Esta posibilidad de escribir los elementos de ${\displaystyle G}$ de manera única como producto permite muchas de las aplicaciones de las cadenas de subgrupos.[6]​

Ejemplo: Se muestra un pequeño ejemplo de lo anterior con el grupo de los enteros positivos con la suma módulo 8:

${\displaystyle G^{(1)}=(\{0,1,2,3,4,5,6,7,8\},\oplus _{8})}$

${\displaystyle G^{(2)}=(\{0,2,4,6,8\},\oplus _{8})}$

${\displaystyle G^{(3)}=(\{0,4\},\oplus _{8})}$

${\displaystyle G^{(4)}=(\{0\},\oplus _{8})}$

se evidencia la cadena:

${\displaystyle G=G^{(1)}\geq G^{(2)}\geq G^{(3)}\geq G^{(4)}=e}$

y los conjuntos:

${\displaystyle U^{1}=\{0,1\}}$

${\displaystyle U^{2}=\{0,2\}}$

${\displaystyle U^{3}=\{0,4\}}$

El algoritmo enfatiza en los grupos de permutación, sin embargo, el ejemplo anterior ejemplifica de forma sencilla lo que se busca.

Aplicado el concepto para grupos de permutaciones, se calculan los subgrupos a partir de los elementos estabilizadores del grupo, para cierto punto afectado por la permutación. Esto es, las permutaciones que envíen dicho punto a sí mismo, dejándolo estable. Cada vez que se baja en la cadena de subgrupos, se estabiliza un nuevo punto. Esto puede ser logrado definiendo cada subgrupo de la cadena como:

$${\displaystyle G^{(i)}=G\cap Stab_{Sym(n)}1,2,3,...,i}$$

El resultado es una cadena de subgrupos en el cual cada subgrupo es el estabilizador de un nuevo punto, en este caso en orden ${\displaystyle 1,2,3,...,k}$, con respecto al grupo de permutación simétrico. Este orden puede ser definido mediante una base ${\displaystyle B}$ dada por:

$${\displaystyle B=\{\beta _{1},\beta _{2},...,\beta _{k}\}}$$

con ${\displaystyle 1,2,3,...,k}$, tal que el estabilizador punto a punto de B es trivial (el único elemento que fija todos los ${\displaystyle \beta _{i}}$ punto a punto es la identidad de ${\displaystyle G}$).

Teniendo el generador de ${\displaystyle G^{(i)}}$y el conjunto de representantes de los co-sets, es posible utilizar el Lema de Schreier, que utiliza un generador de una estrategia constructiva para encontrar el generador del subgrupo. Para mantener pequeño el tamaño de cada generador, y por ende el tamaño del generador fuerte final, se utiliza un filtro que sea un algoritmo para encontrar conjuntos generadores pequeños, usualmente el filtro de Sims o el filtro de Jerrum.[7]​

Algoritmo

El algoritmo se aplica para cada subgrupo de la cadena, empezando en ${\displaystyle G^{(1)}=G}$, especificado mediante un conjunto generador ${\displaystyle A_{1}}$, hasta llegar a ${\displaystyle G^{(k)}=e}$. El conjunto generador fuerte del grupo de permutaciones ${\displaystyle G}$ es la unión de los generadores encontrados en cada paso, que responden a la estructura de permutación según la cadena de estabilizadores (la cadena de subgrupos).[7]​

Algoritmo Schreier-Sims Input: ${\displaystyle A_{i}}$un generador de un grupo ${\displaystyle G^{(i)}}$ Output: ${\displaystyle S}$(Strong Generating Set del grupo ${\displaystyle G}$) Buscar en anchura en el grafo de Cayley y guardar los mejores representantes de los co-sets (mínima cantidad). Calcule y guarde el índice (tamaño de ${\displaystyle U^{(i)}}$). Estos puede ser utilizados para determinar el orden de ${\displaystyle G}$. Halle el set generador de ${\displaystyle G^{(i+1)}}$, usando ${\displaystyle A_{i}}$ y el resultado del paso 1, obteniendo uno posiblemente mayor a ${\displaystyle A_{i}}$, usando el Lema de Schreier. Use un algoritmo para encontrar conjuntos generadores pequeños para reducir su tamaño y así generar ${\displaystyle A_{i+1}}$.

Complejidad

La complejidad del algoritmo, ya sea tiempo de ejecución o memoria depende de la implementación que se use.

Tiempo de ejecución para casos específicos:[8]​

• Pertenencia elemental al grupo: ${\displaystyle O((n^{4}log_{2}(n))}$
• Clausura normal elemental: ${\displaystyle O((n^{3}))}$
• Clausura normal usando prefijos al azar: ${\displaystyle O((n^{2}))}$
• Reducción del conjunto generador S a tamaño de a lo sumo n : ${\displaystyle O((|S|nlog(n)))}$

Se analizará, como ejemplo, una implementación del algoritmo, que se basa en encontrar el tamaño de un grupo de permutación basándose en un árbol de Schreier y el lema de Schreier.[9]​ Estos algoritmos calculan una base y un conjunto generador (SGS) para el grupo en cuestión.

Algoritmo:[9]​

1. Si el grupo ${\displaystyle G}$ es no trivial, escoja un punto ${\displaystyle b}$ que no haya sido elegido. (Donde ${\displaystyle b}$ es un punto estabilizador)
2. Calcule un árbol de Schreier con raíz ${\displaystyle b}$ y obtenga ${\displaystyle (|b^{G}|)}$.
3. Use el lema de Schreier para encontrar los generadores de ${\displaystyle (|G^{b}|)}$.
4. Aplique el algoritmo recursivamente para ${\displaystyle (G^{b})}$, para encontrar ${\displaystyle (|G^{b}|)}$.

Si denotamos los puntos elegidos del grupo para su análisis como ${\displaystyle b}$ = ${\displaystyle b_{1},b_{2},...,b_{n}}$, al aplicar el paso dos del algoritmo generamos un árbol de Schreier aplicando el método de Búsqueda a lo ancho (BFS). Crear este árbol tiene una complejidad de ${\displaystyle O(rn)}$, siendo ${\displaystyle r}$ el número de generadores del grupo. Al terminar la implementación el tamaño del grupo en cuestión va a estar dado por:

$${\displaystyle (|G|=|b_{0}^{G(0)}||b_{1}^{G(1)}|...|b_{m}^{G(m-1)}|)}$$

Este algoritmo parará hasta que se logre encontrar una base de G que cumple:

$${\displaystyle (G_{\beta _{1},\beta _{2},...,\beta _{k}}=1)}$$

Esto se logrará a lo sumo en ${\displaystyle n}$ pasos.

En términos de memoria se debe tomar en cuenta que cada vez que se ejecuta el algoritmo para cada punto de ${\displaystyle b}$ el número de generadores de ${\displaystyle G_{b}}$ crece a un factor de  ${\displaystyle (|b^{G}|)}$, gracias al lema de Schreier, entonces para el peor caso (donde cada órbita sea todo el conjunto asociado al grupo ${\displaystyle (\Omega )}$ y tome ${\displaystyle n}$ pasos para terminar), habría a lo sumo  ${\displaystyle rn^{n}}$generadores al terminar el algoritmo, siendo r el número de generadores del grupo.

Problemas relacionados y aplicaciones

Entre los problemas en los que se utilizó el algoritmo de Schreier-Sims y posibles aplicaciones se encuentran:

1. “CONDENSATION OF INDUCED REPRESENTATIONS AND AN APPLICATION: THE 2-MODULAR DECOMPOSITION NUMBERS OF Co2”:[10]​ En este artículo se presenta un algoritmo para condensar módulos inducidos arbitrarios para un grupo finito en un conjunto finito, para esto utiliza como base los algoritmos computacionales MeatAxe y el Schreier-Sims. Como un ejemplo de su aplicación en el trabajo se crea y analiza un módulo inducido para el grupo esporádico simple de Conway Co2.
2. “Pruning by Isomorphism in Branch-and-Cut”:[11]​ En este artículo se presenta un método de rama y corte para resolver (0,1) problemas lineales enteros a partir de un grupo simétrico largo, el grupo es utilizado para podar la generación del árbol y generar cortes, dichos cortes son no estándar, eliminando parte de las soluciones posibles y dejando las soluciones óptimas.  Este artículo realiza las acciones de poda y corte a partir de procedimientos de regresión a partir del algoritmo de Schreier-Sims.
3. “An Algorithm for Solving the Factorization Problem in Permutation Groups”:[12]​ En este artículo se desarrolla el problema de factorización en grupos de permutación, que se basa en representar un elemento (${\displaystyle g}$) de algún grupo ${\displaystyle G}$ como una palabra a partir de un grupo de generadores ${\displaystyle S}$ de ${\displaystyle G}$. Un algoritmo clásico de solución para este problema es el algoritmo de Schreier-Sims, siendo que este método es poco eficiente debido a un tiempo de crecimiento exponencial. Este artículo representa una optimización relativa al problema computando un SGS representando sus elementos con palabras relativamente pequeñas sobre los generadores.

Entre las posibles aplicaciones están:

• Computar ${\displaystyle |G|}$.
• Determinar si un ${\displaystyle g\in S(n)}$se encuentra en ${\displaystyle G}$.
• Chequear si ${\displaystyle H\leq S_{(}n)}$ es un subgrupo normal de ${\displaystyle G\leq S_{(}n)}$.

Referencias

1. «Charles Sims Biography». 
2. «Charles Sims Obituary». 
3. «Spring 2007 Newsletter». 
4. «List of Fellows of the American Mathematical Society». 
5. «Otto Schreier». 
6. Murray, Scott H. «The Schreier-Sims algorithm». Australian National University. Archivado desde el original el 10 de enero de 2020. 
7. /wiki/Schreier-Sims\_algorithm «Schreier-Sims Algorithm». 
8. G. Cooperman and L.Finkelstei (1993). Combinatorial Tools for Computational Group Theory. p. 6. 
9. Jaggi, Martin. «Implementations of 3 Types of the Schreier-Sims Algorithm». Queen Mary University of London. 
10. J. M ̈uller and J. Rosenboom (1999). “Condensation of induced Representations and an Application:the 2-Modular Decomposition Numbers of Co2 BT - Computational Methods for Represen-tations of Groups and Algebras,”. p. 309-321. 
11. F. Margot (2004). Pruning by Isomorphism in Branch-and-Cut BT - Integer Programming and Combinatorial Optimization,. p. 304-317. 
12. T. Minkwitz (1998). «An algorithm for solving the factorization problem in permutation groups». J.Symb. Comput. 

• Datos: Q7432874