Algoritmo de Schreier–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]

(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.

Summarize Timeline Top Qs Fact Check

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]

Summarize Timeline Fact Check

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}}$.