Algoritmo de Schreier-Sims

Algoritmo de Schreier-Sims
Grupo Earl Cayley $S_4$
Lleva el nombre de	Charles Sims y Otto Schreyer
Autor	Carlos Sims
objetivo	Determinar el orden de un grupo de permutaciones
Estructura de datos	permutaciones
peor momento	$O(n^{3}m+n^{6})$

El algoritmo de Schreier-Sims es un algoritmo del campo de la teoría computacional de grupos que permite, tras una única ejecución en tiempo lineal, encontrar el orden de un grupo generado por permutaciones, comprobar si un elemento pertenece a dicho grupo y enumerar sus elementos. . El algoritmo fue propuesto por Charles Sims en 1970 para encontrar grupos de permutación primitivos [1] y se basa en el lema de generación de subgrupos de Schreier [2] . La representación del grupo de permutaciones que encuentra el algoritmo es similar a la forma escalonada de la matriz para su espacio de filas [3] . Los métodos desarrollados por Sims forman la base de la mayoría de los algoritmos modernos para trabajar con grupos de permutación [4] , las modificaciones del algoritmo también se utilizan en sistemas de álgebra computacional modernos como GAP y Magma [5] . Una de las aplicaciones más obvias del algoritmo es que puede usarse para resolver el Cubo de Rubik [6] .

Historia

Uno de los principales problemas de la teoría de los grupos de permutación es la búsqueda de grupos de permutación de un grado dado (es decir, el número mínimo de elementos de un conjunto cuyo grupo de permutación contiene un grupo de permutación dado). Para 1970, para las potencias 2 a 11, se habían encontrado todos los grupos de permutación, para las potencias 12 a 15, se habían encontrado todos los grupos transitivos (es decir, subgrupos que actúan transitivamente en un grupo electrógeno ), y para las potencias 16 a 20, solo se habían encontrado grupos primitivos . Se habían encontrado grupos de permutaciones . Para buscar grupos primitivos de mayor grado, Charles Sims desarrolló un programa que encuentra orden y cierta estructura en un grupo de permutación dado por su conjunto generador [1] .

El programa original mencionado en el artículo de Sims fue escrito para IBM 7040 en la Universidad de Rutgers y apoyó a cualquier grupo cuyo grado fuera inferior a 50 [7] . Furst, Hopcroft y Lax realizaron por primera vez una estimación exacta del tiempo de ejecución de un algoritmo en 1980 [8] . El tiempo de ejecución fue mejorado por Jerrum en 1982 [9] y por Donald Knuth en 1981 [10] . En 1980, se desarrolló una versión probabilística eficiente del algoritmo [11] . Varias variaciones del algoritmo, incluidas aquellas que utilizan el vector de Schreier lugar del árbol de órbitas, fueron desmanteladas por Sheresh en 2003 [12] [13] .

En la teoría de grupos computacionales, los algoritmos sobre grupos de permutación es una de las áreas más desarrolladas, e incluso hoy en día la mayoría de estos algoritmos se basan en los métodos desarrollados por Sims [4] .

Idea principal

La eficiencia de los cálculos con un grupo de permutación depende esencialmente de cómo se especifique en el programa [2] . Una forma efectiva de hacer esto es aislar varios de sus subgrupos y seleccionar clases laterales únicas para cada subgrupo en esa serie en relación con su predecesor. El algoritmo propuesto por Charles Sims encuentra una serie de subgrupos en los que cada grupo siguiente es el estabilizador del anterior. La secuencia de puntos para los que se construyen los estabilizadores se denomina base , y el conjunto que contiene los elementos generadores de cada grupo de la serie se denomina conjunto generador fuerte [2] .

El algoritmo construye una base y un conjunto generador fuerte para el subgrupo de permutación dado por su conjunto generador , usando el lema de Schreier para encontrar los conjuntos generadores. El tamaño de los conjuntos obtenidos en los pasos intermedios crece exponencialmente, por lo que se han desarrollado variaciones del algoritmo que reducen el número de elementos generadores considerados [2] .

La representación descrita anteriormente divide un grupo en un producto de subconjuntos anidados en él, similar a cómo la representación escalonada divide un espacio vectorial en una suma directa de subespacios anidados en él [3] .

Planteamiento del problema

Un grupo simétrico es un grupo cuyos elementos son permutaciones de elementos de algún conjunto . Por lo general, se toma como tal conjunto . En tal notación, los elementos de un grupo pueden verse como aplicaciones que toman un conjunto en sí mismo, es decir, sus automorfismos . La operación de grupo en tal notación es la composición de permutaciones, para permutaciones y definida como , donde para . En consecuencia, la permutación unitaria será una permutación tal que , y la permutación inversa se puede dar como [14] . $S_{n}$ $\Omega$ $\Omega =\{1,2,\puntos,n\}$ ${\ estilo de visualización \ sigma: \ Omega \ a \ Omega}$ $\Omega$ $\sigma_1$ $\sigma_2$ ${\ estilo de visualización \ sigma = \ sigma _ {1} \ sigma _ {2}}$ ${\ estilo de visualización \ sigma (\ omega) = \ sigma _ {1} (\ sigma _ {2} (\ omega))}$ $\omega \en \Omega$ $\sigma$ ${\ estilo de visualización \ sigma (\ omega) = \ omega}$ ${\ estilo de visualización \ sigma ^ {-1} (\ sigma (\ omega)) = \ omega}$

Sea el conjunto de permutaciones de longitud . Un subgrupo generado de un conjunto es el subgrupo más pequeño por inclusión que contiene como subconjunto o, de manera equivalente, un subgrupo de todos los elementos que pueden representarse como un producto finito de elementos y sus inversos. El orden de un grupo de permutaciones es el número de elementos que lo componen , y su grado es la cardinalidad del conjunto sobre el que actúa. En tal notación, el algoritmo debería ser capaz de [7] : ${\displaystyle S=\{g_{1},\dots,g_{m}\}\subconjunto S_{n))$ $norte$ $S$ $\langle S\rangle$ $S$ $S_{n}$ $S$ $S$ ${\ estilo de visualización | S |}$ ${\ estilo de visualización | \ omega |}$

Obtenga el orden del subgrupo generado por las permutaciones dadas, ${\textstyle |\langle S\rangle |}$
Por permutación , compruebe si se encuentra en el subgrupo generado , $gramo$ $\langle S\rangle$
Enumere secuencialmente los elementos del subgrupo generado sin repetición.

Aplicaciones

Las modificaciones de algoritmos se implementan en los dos sistemas de álgebra computacional más populares especializados en la teoría de grupos computacional : GAP y Magma [5] . Las herramientas para trabajar con grupos de permutación, incluidos los algoritmos de enumeración de clases laterales y el algoritmo de Schreier-Sims, también están disponibles en los sistemas populares más generales Maple y Mathematica [15] . Inicialmente, el algoritmo se desarrolló para buscar grupos de permutación primitivos de un grado dado [1] , pero posteriormente el alcance de su aplicación ha crecido muchas veces; por ejemplo, con este algoritmo, puede encontrar soluciones para una configuración de cubo de Rubik determinada. ya que sus rotaciones forman un grupo [6] . Además, el algoritmo se mostró bien al trabajar con grupos de matrices [16] .

Algoritmo

Factorización de grupos

Sea un subgrupo de algún grupo finito , denotado por la transversal de la familia de clases laterales izquierdas . Cualquier elemento se puede representar de forma única como , where y . Aplicando sucesivamente este resultado a y sus subgrupos, se puede generalizar de la siguiente forma [3] [17] : $H$ $GRAMO$ $G/H$ ${\ estilo de visualización \ {gH: g \ en G \}}$ $g\in G$ ${\ estilo de visualización g = th}$ ${\ estilo de visualización t \ en G/H}$ $h\en H$ $H$

Sea una serie de subgrupos . Entonces cualquier elemento se puede representar de forma única como , donde . ${\displaystyle G=G^{(0)}\geq G^{(1)}\geq \dots \geq G^{(k)}=\{e\))$ $GRAMO$ $g\in G$ ${\displaystyle g=g_{1}g_{2}\puntos g_{k))$ $g_{1}\en G^{(0)}/G^{(1)},g_{2}\en G^{(1)}/G^{(2)},\puntos, g_{k}\en G^{(k-1)}/G^{(k)}$

Cálculo de orden y listado de elementos

La vista descrita anteriormente tiene las siguientes propiedades:

Por el teorema de Lagrange, el orden de un grupo se puede calcular usando la fórmula [3] , ${\textstyle |G|=|G^{(0)}/G^{(1)}|\times |G^{(1)}/G^{(2)}|\times \dots \times | G^{(k-1)}/G^{(k)}|}$
Los elementos de un grupo se pueden enumerar enumerando todas las representaciones posibles [7] . ${\displaystyle g=g_{1}g_{2}\puntos g_{k))$

Para poder comprobar también la pertenencia de elementos a un subgrupo generado, es necesario considerar series de subgrupos de una forma especial, a saber, los compuestos por estabilizadores [7] .

Órbitas y estabilizadores

Dejar actuar en el plató . Elegimos un conjunto de elementos y construimos una serie de subgrupos de modo que , donde está el estabilizador del elemento . En otras palabras, es un subgrupo de elementos que traduce cada uno de los elementos en sí mismo [7] . Con este enfoque, en cada paso siguiente, la parte del conjunto , sobre la que actúa no trivialmente el siguiente subgrupo , disminuirá en un elemento, y el orden del subgrupo con el que se está trabajando será al menos el doble. . De esto se deduce que se requerirán iteraciones del algoritmo antes de encontrar la partición deseada [18] . $GRAMO$ $\Omega$ ${\estilo de texto \omega _{1},\puntos,\omega _{k}\en \Omega}$ ${\textstyle G^{(i)}=G_{\omega _{i}}^{(i-1)))$ ${\displaystyle G_{\omega }=\{g:g\omega =\omega \))$ $\omega$ ${\ estilo de texto G^{(i)))$ $GRAMO$ ${\estilo de texto \omega _{1},\puntos,\omega _{i))$ $\Omega$ $GRAMO$ $\min(|\Omega |,\log |G|)$

Para construir clases laterales, debe utilizar el hecho de que existe una correspondencia uno a uno (biyección) entre los elementos de la órbita y las clases laterales izquierdas del estabilizador [19] . $G\omega$ ${\textstyle G/G_{\omega ))$ ${\textstyle G_{\omega ))$

Prueba

Por el teorema de órbitas y estabilizadores, el conjunto de clases laterales y la órbita son equivalentes en potencia. Asocia cada elemento con un elemento de la órbita . ${\displaystyle G/G_{\omega ))$ $G\omega$ ${\displaystyle t\in G/G_{\omega ))$ $t\omega$

Dejemos que , entonces los conjuntos y coincidan. Pero de esto se sigue que también coinciden y : $t_{1}G_{\omega }=t_{2}G_{\omega }$ $(t_{1}G_{\omega })\omega$ $(t_{2}G_{\omega })\omega$ $t_{1}\omega$ $t_{2}\omega$

t una ω = t una ( GRAMO ω ω ) = ( t una GRAMO ω ) ω = ( t 2 GRAMO ω ) ω = t 2 ( GRAMO ω ω ) = t 2 ω {\displaystyle t_{1}\omega =t_{1}(G_{\omega }\omega )=(t_{1}G_{\omega })\omega =(t_{2}G_{\omega })\ omega =t_{2}(G_{\omega }\omega )=t_{2}\omega }

t_{1}\omega =t_{1}(G_{\omega }\omega )=(t_{1}G_{\omega })\omega =(t_{2}G_{\omega })\ omega =t_{2}(G_{\omega }\omega )=t_{2}\omega

A cada clase lateral se le asignó exactamente un elemento de la órbita. Debido a que las clases laterales cubren todo el grupo , todos los elementos coincidentes son diferentes. Así que de hecho es una biyección. ■ $GRAMO$

De la prueba se sigue que, como representantes de clases laterales, se pueden tomar elementos que realizan diferentes puntos de la órbita [19] . $G\omega$

Comprobación de propiedad

Denote por tal elemento que . Dividir en una serie de estabilizadores le permitirá comprobar si el elemento pertenece al grupo [7] : $\overline u$ ${\displaystyle G/G_{\omega ))$ ${\overline {u}}\omega =u$

Si , entonces existe un elemento tal que , es decir , ${\ Displaystyle g \ en G ^ {(i-1)))$ ${\displaystyle t_{i}\en G^{(i-1)}/G^{(i)))$ ${\displaystyle g\in t_{i}G^{(i)))$ ${\displaystyle t_{i}^{-1}g\in G^{(i)))$
En virtud de la biyección entre los elementos de la clase adyacente y los puntos de la órbita, se puede determinar sin ambigüedades que . $t_{i}={\overline {g(\omega_{i})}}$

Estas propiedades le permiten hacer una transición de a , lo que eventualmente conducirá al hecho de que el elemento actual debería estar en . Si este es realmente el caso, entonces , de donde es posible expresar [7] . ${\ Displaystyle G^{(i-1)))$ $G^{(i)}$ $G^{(k)}=\{e\}$ $e=t_{k}^{-1}\puntos t_{2}^{-1}t_{1}^{-1}g$ ${\displaystyle g=t_{1}t_{2}\dots t_{k))$

Cálculo de la órbita

Deje que el grupo tenga un grupo electrógeno . La órbita de cualquier elemento bajo la acción de un grupo se puede organizar en un árbol de la siguiente forma [17] : $GRAMO$ $S$ $\alfa$ $G=\langle S\rangle$

Un elemento está escrito en la raíz del árbol , ${\ estilo de visualización \ alfa \ en \ Omega}$
En cada vértice del árbol, se escribe algún elemento de la órbita del elemento , ${\ estilo de texto \ beta \ en G (\ alfa)}$ $\alfa$
En la arista que va del vértice con el elemento al vértice con el elemento , hay un elemento tal que . $tu$ $v$ $S \ en S$ ${\ estilo de visualización s (u) = v}$

El árbol descrito se puede construir mediante un recorrido primero en profundidad , para esto es necesario clasificar el elemento en cada vértice hasta que resulte que aún no se ha asignado un vértice para [17] . Ejemplo de implementación en Python : $tu$ $S \ en S$ ${\ estilo de visualización s (u)}$

# Construye un árbol de órbita dado el elemento w y el conjunto generador S def build_schreier_tree ( w , S , orbit ): for g in S : if g [ w ] not in orbit : orbit [ g [ w ]] = apply ( g , orbit [ w ]) build_schreier_tree ( g [ w ], S , órbita )

Aquí, la función devuelve el resultado de aplicar la operación de grupo a los elementos y como primer y segundo argumento, y el elemento se almacena en . ${\mathsf {aplicar}}(a,b)$ $a$ $b$ ${\mathsf {órbita}}[\alfa]$ $\overline {\alfa}$

Lema de Schreier

Del lema de Schreier se deduce que el estabilizador es generado por el conjunto de generadores de Schreier: . Este resultado nos permite construir un grupo electrógeno para a partir del grupo electrógeno para y la órbita del elemento . Posible implementación de una función que devuelve un nuevo grupo electrógeno [20] : ${\ Displaystyle G_ {\ alfa}}$ $G_{\omega }=\langle \{({\overline {su)))^{-1}s{\overline {u}}\mid u\in G\omega ,s\in S\} \rango$ ${\ Displaystyle G^{(w-1)))$ $\omega$ ${\displaystyle G^{(\omega )))$

# Toma un grupo electrógeno para G_{w-1} y una órbita de w # Devuelve un grupo electrógeno para G_w def make_gen ( S , orbit ): n = len ( next ( iter ( S ))) newS = set () for s en S : para u en órbita : newS . agregar ( reducir ( aplicar , [ invertir ( órbita [ s [ u ]]), s , orbitar [ u ]])) volver nuevoS

El algoritmo no se agota con esto, ya que aunque el tamaño del nuevo grupo electrógeno depende polinómicamente del tamaño de la órbita y del antiguo grupo electrógeno para una llamada individual, en el agregado de todas las llamadas a esta función, el tamaño del grupo generador el conjunto crece exponencialmente [2] .

Tamizar generadores

Para evitar el crecimiento descontrolado de los grupos electrógenos, se debe aplicar un procedimiento de tamizado . Esto requeriría la siguiente declaración [3] [20] :

deja _ Entonces es posible construir un conjunto de como máximo elementos tales que . $S\subconjunto G$ $S'$ ${\ estilo de visualización \ vert \ Omega \ vert ^ {2}}$ $\langle S'\rangle =\langle S\rangle$

Prueba

Primero, demostremos el siguiente lema:

deja _ Entonces las siguientes transformaciones no cambian : $S\subconjunto G$ $\langle S\rangle$

Reemplazo para $S \ en S$ $^{{-1}}$
Reemplazando con , donde y $S \ en S$ ${\ Displaystyle st}$ ${\ estilo de visualización t \ en S}$ $t\neq s$

Prueba

Supongamos que, después de aplicar una de estas operaciones, obtenemos un conjunto . Es obvio que . Por otro lado, estas conversiones pueden ser revertidas por conversiones del mismo tipo, por lo que . Entonces _ ■ $S'$ $S'\subconjunto \langle S\rangle$ $S\subconjunto \langle S'\rangle$ $\langle S\rangle =\langle S'\rangle$

Con la ayuda de tales transformaciones, podemos reducir el conjunto a tal forma que para cualquier par en el conjunto haya como máximo un elemento tal que: $S$ $(yo, j)$ $s$

s ( ω una ) = ω una , s ( ω 2 ) = ω 2 , … , s ( ω i − una ) = ω i − una , s ( ω i ) = ω j ≠ ω i {\displaystyle s(\omega_{1})=\omega_{1},\ s(\omega_{2})=\omega_{2},\dots,\ s(\omega_{i- 1})=\omega_{i-1},\ s(\omega_{i})=\omega_{j}\neq \omega_{i}}

s(\omega_{1})=\omega_{1},\ s(\omega_{2})=\omega_{2},\dots,\ s(\omega_{i- 1})=\omega_{i-1},\ s(\omega_{i})=\omega_{j}\neq \omega_{i}

Esto se puede lograr agregando elementos al nuevo conjunto uno a la vez y procediendo de manera similar al método de Gauss :

S'

Digamos que queremos agregar un nuevo elemento , $S'$ $s$
vamos secuencialmente ${\ estilo de visualización \ omega _ {1}, \ puntos, \ omega _ {n}}$
1. Si , entonces ve a , ${\ Displaystyle s (\ omega _ {i}) = \ omega _ {i}}$ ${\ estilo de visualización \ omega _ {i + 1}}$
2. Si , compruebe si ya se ha encontrado un elemento con ese par , ${\ estilo de visualización s (\ omega _ {i}) = \ omega _ {j)}$ $t$ $(yo, j)$
  1. Si nos conocimos, reemplace con y vaya a , $s$ $s^{-1}t$ ${\ estilo de visualización \ omega _ {i + 1}}$
  2. De lo contrario, recuerda lo que corresponde al par y agrega en la forma actual a , $s$ $(yo, j)$ $s$ $S'$
Si al final del algoritmo tenemos , entonces ignoramos y no cambiamos . ${\ estilo de visualización s = e}$ $s$ $S'$

Este algoritmo utiliza únicamente las operaciones elementales indicadas anteriormente, por lo tanto . Tenga en cuenta que si , entonces , entonces la transición desde en el algoritmo es correcta, y cada par en realidad corresponde a no más de una permutación. Teniendo en cuenta que existen como máximo tales pares , obtenemos la afirmación requerida.

■

\langle S'\rangle =\langle S\rangle

{\ estilo de visualización s (\ omega _ {i}) = t (\ omega _ {i})}

{\displaystyle s^{-1}t(\omega _{i})=\omega _{i))

{\ estilo de visualización \ omega _ {i + 1}}

s^{-1}t

(yo, j)

n^{2}

El procedimiento descrito en la demostración se denomina filtro de Sims y funciona en [21] . Su implementación podría verse así: $O(|S|\cdot\Omega^{2})$

# Toma un conjunto principal S # Devuelve un conjunto principal simplificado S' def normalize ( S ): n = len ( next ( iter ( S ))) newS = set () base = [{} for i in range ( n )] para s en S : para x en rango ( 0 , n ): si s [ x ] != x : si s [ x ] en base [ x ]: s = aplicar ( inversa ( s ), base [ x ][ s [ x ]]) else : base [ x ][ s [ x ]] = s newS . añadir ( s ) romper volver noticias

Además del filtro Sims, el filtro Jerrum [22] se puede utilizar para buscar un conjunto pequeño . A diferencia del filtro Sims, que encuentra un conjunto de elementos como máximo, el filtro Jerrum encuentra un conjunto de elementos como máximo. Al mismo tiempo, el filtro Jerrum funciona para , por lo que en el caso del algoritmo de Schreier-Sims, es preferible utilizar el filtro de Sims [21] . $S'$ ${\ estilo de visualización | \ omega | ^ {2}}$ ${\ estilo de visualización | \ omega |}$ $O(|S|\cdot |\Omega |^{4})$

Algoritmo

Todo lo anterior en conjunto da un algoritmo que se puede implementar de manera sucinta de la siguiente manera [20] :

# Toma un conjunto generador S = s1, ..., sk # Devuelve las transversales coset U1, ..., Uk def schreier_sims ( S ): n = len ( next ( iter ( S ))) ans = [] w = 0 while S : órbita = {} órbita [ w ] = tupla ( rango ( n )) build_schreier_tree ( w , S , orbit ) ans += [[ orbit [ i ] for i in orbit ]] S = normalizar ( make_gen ( S , orbit )) w += 1 retorno ans

Paso a paso, sus acciones tienen el siguiente significado:

La órbita del elemento se construye mediante búsqueda en profundidad, $\ omega _ {i}$
Todos los generadores de Schreier se calculan para , ${\ Displaystyle G^{(i+1)))$
Muchos generadores son diezmados para evitar su crecimiento exponencial.

A la salida, el algoritmo devolverá una lista cuyos elementos son transversales de clases laterales . $G^{(0)}/G^{(1)},G^{(1)}/G^{(2)},\dots,G^{(k-1)}/G^ {(k)}$

Tiempo de ejecución del algoritmo

En total, el algoritmo no requiere más iteraciones. Cada iteración consta de: ${\ estilo de visualización | \ omega |}$

Construyendo un árbol de órbitas que tome operaciones elementales, $O(|S|\cdot |\Omega |)$
La construcción de generadores Schreier, que toma operaciones elementales y genera generadores, $O(|S|\cdot |\Omega |^{2})$ $|S|\cdot |\Omega |$
Normalización del conjunto generador, que toma operaciones elementales, donde se encuentra el conjunto obtenido en el paso anterior. $O(|S'|\cdot |\Omega |^{2})$ $S'$

El valor en el caso en que se da el conjunto no cambia a lo largo del algoritmo y es igual a . El tamaño del grupo electrógeno es inicialmente igual a , y en cada paso posterior no excede . Por lo tanto, el tiempo total de ejecución del algoritmo en la implementación anterior se puede estimar como [8] [12] [13] . ${\ estilo de visualización | \ omega |}$ ${\displaystyle S=\{g_{1},\dots,g_{m}\}\subconjunto S_{n))$ $norte$ $metro$ $|\Omega |^{2}=n^{2}$ $O(n^{3}m+n^{6})$

Variaciones del algoritmo

Versiones pseudo-lineales

Previamente, se mostró que el algoritmo requiere iteraciones. En el caso general, el tamaño del grupo puede ser del orden de , y en este caso, según la fórmula de Stirling , que obviamente es mayor . Pero en algunos casos, el orden del grupo es pequeño y, por lo tanto, es más rentable tener un algoritmo que dependa de y no , por ejemplo, cuando se trata de algún grupo conocido que se da como un grupo de permutación [12] . $\min(|\Omega |,\log |G|)$ $¡norte!$ ${\ estilo de visualización \ log | G | \ sim n \ log n}$ ${\ estilo de visualización | \ Omega | = n}$ ${\ estilo de visualización \ registro | G |}$ $norte$

Por el teorema de Cayley , cualquier grupo finito es isomorfo a algún grupo de permutación . El grado de tal grupo puede ser grande, pero para muchos grupos su orden es tal que . Por ejemplo, el grupo diédrico es isomorfo al grupo de permutación generado por el cambio cíclico y la reflexión . Es decir, el grado de este grupo es , y el orden es , y . Para tales grupos, se pueden considerar algoritmos con tiempo de ejecución , que se denominan pseudolineales [12] . $norte$ $|G|$ ${\ estilo de visualización \ log | G | <n}$ $D_{n}$ $r=(1~~2~~\puntos~~n)$ ${\ estilo de visualización s = (1 ~ ~ n) (2 ~ ~ n-1) (3 ~ ~ n-2) \ puntos}$ $norte$ $2n$ ${\ estilo de visualización \ log | G | \ sim \ log n}$ $O(nm\log ^{c}|G|)$

En un intento por acercar el algoritmo a uno pseudolineal y reducir el grado , incluido en su tiempo de ejecución, Sheresh llegó a versiones del algoritmo que requieren [18] : $norte$

$O(n^{2}\log ^{3}|G|+mn^{2}\log |G|)$ tiempo y memoria $O(n^{2}\log |G|+mn)$
$O(n^{3}\log ^{3}|G|+mn^{3}\log |G|)$ tiempo y memoria. $O(n\log ^{2}|G|+mn)$

Versión probabilística

La primera versión probabilística funcional del algoritmo fue desarrollada por Jeffrey Leon en 1980 [11] . Por lo general, esto es lo que quieren decir cuando hablan del método probabilístico de Schreyer-Sims. En él, al reducir los generadores de Schreier, este procedimiento finalizaba prematuramente si se factorizaban 20 generadores seguidos. Sheresh demostró que, junto con algunas optimizaciones, este procedimiento da la siguiente declaración [5] :

Para cualquier constante , existe un algoritmo de tipo Monte Carlo que, con una probabilidad de error de como máximo, construirá un conjunto generador fuerte para el grupo de permutación usando tiempo y memoria. $d$ ${\ estilo de visualización n^{-d))$ $G=\langle S\rangle$ $O(n\log n\log ^{4}|G|+mn\log |G|)$ $O(n\log |G|+mn)$

En los sistemas de álgebra computacional modernos, las modificaciones de esta versión del algoritmo con varias heurísticas se utilizan generalmente para acelerar el programa [5] .

Notas

↑ 1 2 3 Sims, 1970 , pág. 169-170.
↑ 1 2 3 4 5 Murray, 2003 , pág. 1-3.
↑ 1 2 3 4 5 Holt, Eyck, O'Brien, 2005 , pág. 87-90.
↑ 1 2 Sheresh, 2003 , pág. 1-4.
↑ 1 2 3 4 Sheresh, 2003 , pág. 62-64.
↑ 1 2 Brouwer, 2016 , pág. cuatro
↑ 1 2 3 4 5 6 7 Sims, 1970 , pág. 176-177.
↑ 1 2 Furst, Hopcroft, Lax, 1980 .
↑ Jerrum, 1986 .
↑ Knuth, 1991 .
↑ 1 2 León, 1980 .
↑ 1 2 3 4 Sheresh, 2003 , pág. 48-54.
↑ 1 2 Holt, Eyck, O'Brien, 2005 , pág. 93-94.
↑ Zhuravlev, Flerov, Vyaly, 2019 , Permutaciones, pág. 31-36.
↑ Holt, Eyck, O'Brien, 2005 , pág. 1-7.
↑ Murray, O'Brien, 1995 .
↑ 1 2 3 Murray, 2003 , pág. 9-24.
↑ 1 2 Sheresh, 2003 , pág. 59-62.
↑ 1 2 Zhuravlev, Flerov, Vyaly, 2019 , Órbitas y estabilizadores, p. 140-145.
↑ 1 2 3 Murray, 2003 , pág. 25-33.
↑ 1 2 VipulNaik. Filtro Sims (inglés) . Groupprops, Wiki de propiedades de grupo . Consultado el 23 de septiembre de 2019. Archivado desde el original el 1 de septiembre de 2019.
↑ Vipul Naik. El filtro de Jerrum . Groupprops, Wiki de propiedades de grupo . Consultado el 19 de septiembre de 2023. Archivado desde el original el 1 de septiembre de 2019.

Literatura

Yu. I. Zhuravlev , Yu. A. Flerov y M. N. Vyaly Fundamentos de Álgebra Superior y Teoría de Codificación . - FUPM MIPT, 2019. - S. 144. - 305 p.
Carlos C. Sims. Métodos computacionales en el estudio de grupos de permutaciones (inglés) // Problemas computacionales en álgebra abstracta. - Elsevier, 1970. - P. 176-177. — ISBN 9780080129754 .
Derek F. Holt, Bettina Eick, Eamonn A. O'Brien. Manual de teoría de grupos computacionales (inglés) . — Nueva York: Chapman and Hall/CRC, 2005. — 536 p. — ISBN 9780429147944 .
Merrick Furst, John Hopcroft, Eugene Luks. Algoritmos de tiempo polinomial para grupos de permutación (inglés) // 21.º Simposio anual sobre fundamentos de la informática (sfcs 1980). - IEEE, 1980. - doi : 10.1109/sfcs.1980.34 .
Scott H. Murray. Algoritmo de Schreier-Sims (inglés) // Departamento de matemáticas, Universidad Nacional de Australia. — 2003.
TC Brouwer. Resolviendo un rompecabezas de permutación arbitraria (inglés) // Mathematisch Instituut, Universiteit Leiden. — 2016.
Ákos Seress. Algoritmos de grupos de permutación (inglés) // Cambridge Core. - 2003. - ISBN 9780511546549 . -doi : 10.1017 / CBO9780511546549 .
Marcos Jerrum. Una representación compacta para grupos de permutación (inglés) // Journal of Algorithms. - 1986. - vol. 7 , edición. 1 . — págs. 60–78. — ISSN 0196-6774 . - doi : 10.1016/0196-6774(86)90038-6 .
Donald E. Knuth. Representación eficiente de grupos de permanentes (inglés) // Combinatorica. - 1991. - vol. 11 , edición. 1 . — págs. 33–43. — ISSN 1439-6912 0209-9683, 1439-6912 . -doi : 10.1007/ bf01375471 .
Jeffrey S. León Sobre un algoritmo para encontrar una base y un conjunto generador fuerte para un grupo dado por la generación de permutaciones // Matemáticas de Computación. - 1980. - vol. 35 , edición. 151 . - Pág. 941-974. — ISSN 0025-5718 . -doi : 10.1090/ s0025-5718-1980-0572868-5 .
Scott H. Murray, EA O'Brien. Selección de puntos base para el algoritmo de Schreier-Sims para grupos de matrices // Journal of Symbolic Computation. - 1995. - vol. 19 , edición. 6 _ - Pág. 577-584. — ISSN 0747-7171 . -doi : 10.1006/ jsco.1995.1033 .

teoría de grupos
Conceptos básicos	Subgrupo subgrupo normal Grupo de factores Trabajar directo semidirecto libre
Propiedades algebraicas	grupo conmutativo grupo cíclico grupo ordenado Transformar grupo Grupo solucionable Lema de Schreier teorema de lagrange teoremas de Sylow Clasificación de grupos finitos simples
grupos finitos	Grupo cíclico finito C n Grupo simétrico S n Grupo diedro D n Grupo alternado A n Grupo Cuádruple Klein grupos de Mathieu M11 _ M12 _ M22 _ M23 _ M24 _ Grupos Conway Co 1 Co2_ _ Co3 _ grupos janko J1 _ J2 _ J3 _ J4 _ Grupos de pescadores F22 _ F 23 F24 _ Monstruo (M)
Grupos topológicos	grupos de mentiras Grupo ortogonal O(n) Grupo ortogonal especial SO(n) Grupo unitario U(n) Grupo unitario especial SU(n) Grupo simpléctico Sp(n) Simple excepcional grupo lorentz grupo de poincaré
Algoritmos en grupos	Schreier - Los Sims Todd - Coxeter Transformada de Fourier