¿Cómo genera Gap los elementos en los grupos de permutación?

Question

Entiendo que los grupos de permutación en Gap se representan por generadores, lo que parece ser mucho más eficiente que los grupos representados por todos sus elementos, pero ¿cómo podría entonces por ejemplo

gap>Elements( Group( (1,2,3,4,5,6,7,8),(1,2) ) );

tan rápido lista todo $8!$ elementos de $S_8$ ? ¿Puede alguien describir el algoritmo o el método utilizado?

Answer 1

La respuesta de Alex es muy buena, pero me gustaría añadir una explicación algo simplificada del Algoritmo Schreier-Sims, ya que @Lehs lo pidió.

Quiero hacer hincapié en que éste no es el algoritmo real de Schreier-Sims, pero contiene las ideas esenciales del algoritmo de Schreier-Sims, y creo que servirá para ilustrar por qué es preferible al algoritmo exhaustivo de fuerza bruta.

Intentaré describir esto no el algoritmo de Schreier-Sims mediante un ejemplo.

Dejemos que $G$ sea el grupo generado por las permutaciones: $$a=(2\ 3),\quad b=(1\ 2\ 3)(4\ 5).$$ Utilizaremos no el Algoritmo de Schreier-Sims para encontrar el tamaño de este grupo. Esto es un poco más sencillo que encontrar los elementos reales del grupo.

Necesitamos dos conceptos:

• el órbita de un punto $\alpha$ bajo la acción de un grupo $G$ en un conjunto $\Omega$ es el conjunto $$\alpha \cdot G = \{\alpha\cdot g\in \Omega : g \in G\}.$$ En el ejemplo anterior: $1\cdot G =\{1, 2, 3\}$ .
• el estabilizador de un punto $\alpha$ bajo la acción de un grupo $G$ es el subgrupo $$G_{\alpha} = \{g\in G: \alpha \cdot g = \alpha\}.$$ En nuestro ejemplo, $G_1 = \langle (2\ 3), (4\ 5)\rangle$ .

Por el teorema del estabilizador de la órbita, $|G| = |\alpha \cdot G|\cdot |G_{\alpha}|$ es decir, el tamaño de $G$ es el tamaño de la órbita de $\alpha$ multiplicado por el tamaño del estabilizador de $\alpha$ . Esto también es importante, y lo utilizaremos más adelante.

Pero, ¿cómo calculamos el estabilizador? Una forma (¡mala!) sería enumerar todos los elementos de $G$ y comprobar qué elementos fijan $1$ . Otra forma (¡buena!) es utilizar el siguiente lema:

Lemma de Schreier. Si $G$ es generado por un conjunto $X$ y $G$ actúa sobre un conjunto $\Omega$ entonces $$G_\alpha = \langle u_ixu_j^{-1} : 1\leq i, j\leq n, x\in X, \alpha_i \cdot x = \alpha_j\rangle$$ donde $\alpha\cdot G = \{\alpha_1, \alpha_2, \ldots, \alpha_n\}$ .

En otras palabras, si se lleva la cuenta de qué asigna qué a qué al enumerar la órbita de $\alpha$ Entonces, obtendrá un grupo electrógeno para el estabilizador de forma gratuita (más o menos).

Volviendo a nuestro ejemplo $$ 1\cdot G = \{1, 2, 3\}\quad G_1 = \langle (2\ 3), (4\ 5)\rangle.$$ Tenga en cuenta que es posible encontrar los generadores para el estabilizador $G_1$ usando el Lemma de Schreier, pero esto es un poco tedioso así que no he dado ningún detalle. Repetimos este proceso en el estabilizador $G_1$ : $$ 2\cdot G_1 = \{2, 3\} \quad G_{1, 2} = \langle (4\ 5)\rangle$$ donde $G_{1,2}$ significa el estabilizador de $2$ en $G_1$ (omitiendo de nuevo los detalles). Volvemos a repetir este proceso en $G_{1,2}$ : $$4\cdot G_{1,2} = \{4, 5\} \quad G_{1, 2, 4} = \{\text{id} \}.$$ Aquí es donde termina nuestro algoritmo, por el Teorema del Estabilizador Orbital (aplicado 3 veces a $G$ entonces $G_1$ entonces $G_{1,2}$ ): $$|G| = |1\cdot G|\cdot |G_1| = |1\cdot G| \cdot |2\cdot G| \cdot |G_{1,2}| = |1\cdot G |\cdot |2\cdot G| \cdot |4\cdot G| \cdot |G_{1,2,4}| = 3\cdot 2 \cdot 2 \cdot 1 = 12.$$ El conjunto de puntos iniciales de las órbitas $\{1, 2, 5\}$ a menudo se denomina base la unión de los generadores de $G$ con los generadores de los estabilizadores $G_1$ , $G_{1,2}$ y $G_{1,2,4}$ se llama grupo electrógeno fuerte y las órbitas y estabilizadores a llamados a cadena estabilizadora . Puede utilizar una cadena estabilizadora para responder a más preguntas que la simple búsqueda de la talla, por ejemplo, puede utilizarse para comprobar la pertenencia al grupo $G$ y se puede utilizar para encontrar los elementos en $G$ .

En este ejemplo bastante simple, hacer el algoritmo exhaustivo (para encontrar el tamaño) no es mucho más difícil que el algoritmo propuesto anteriormente. Pero pensemos en el ejemplo de, por ejemplo, el grupo simétrico en 10 puntos, olvidando que ya conocemos su tamaño. Sólo hay que calcular 10 órbitas de longitud 10 a 1 (que 55 puntos en total). En el peor de los casos (que no se dará en la práctica), encontrar los generadores del estabilizador de un punto cuya órbita es de longitud $n$ implica $2n$ multiplicaciones de permutaciones que producen (de nuevo en el peor de los casos, que no se da) $n$ generadores para el estabilizador. Así que en total necesitamos 350 aplicaciones de permutaciones a puntos (para calcular las órbitas) y 110 multiplicaciones de permutaciones (para encontrar los generadores en el lema de Schreier). De esto se obtiene que el tamaño de este grupo es $10! = 3628800$ .

Compárese con el algoritmo exhaustivo en el que necesitaríamos $7257600$ productos de permutaciones en 10 puntos (no importa nada más).

Answer 2

Sólo mostraré cómo encontrar esta información en GAP, una habilidad que puede ser útil en varias situaciones.

GAP tiene es una función PageSource que puede mostrar el código fuente de una función (con comentarios, si están presentes). El argumento de PageSource debe ser un función (no una operación - ver más adelante cómo manejar ese caso). En el caso de Elements , eso sí que es una función:

gap> Elements;
function( coll ) ... end

para poder llamar a PageSource y ver la ubicación del código fuente y el propio código:

gap> PageSource(last);
Showing source in gap4r8p2/lib/list.gi (from line 3718)
#M  Elements( <coll> )
##
##  for gap3 compatibility. Because `InfoWarning' is not available
##  immediately this is not in coll.gi, but in the later read list.gi
##
InstallGlobalFunction(Elements,function(coll)
  Info(InfoPerformance,2,
    "`Elements' is an outdated synonym for `AsSSortedList'");
  Info(InfoPerformance,2,
    "If sortedness is not required, `AsList' might be much faster!");
  return AsSSortedList(coll);
end);

Además de otros detalles útiles, vemos que Elements delegados a AsSSortedList que es un atributo:

gap> AsSSortedList;
<Attribute "AsSSortedList">

El atributo es una operación, por lo que PageSource no funcionará para él de la misma manera que en el caso anterior:

gap> PageSource(AsSSortedList);
Cannot locate source of kernel function AsSSortedList.

Esto sucede porque AsSSortedList es en realidad un montón de métodos, y primero hay que encontrar el que se aplicará al grupo en cuestión a través de

gap> f:=ApplicableMethod(AsSSortedList,[Group( (1,2,3,4,5,6,7,8),(1,2) )]);
function( G ) ... end

Ahora se podría ver de la siguiente manera:

gap> PageSource(last);
Showing source in gap4r8p2/lib/grpperm.gi (from line 2031)
#############################################################################
##
#M  AsSSortedList( <G> ) elements of perm group
##
InstallMethod( AsSSortedList,"via stabchain",true, [ IsPermGroup ], 0,
function( G )
  return ElementsStabChain( StabChainMutable(G));
end );

Ambas funciones están documentadas, tipo ?ElementsStabChain y ?StabChainMutable en GAP para ver más detalles.

Tenga en cuenta que si el valor del atributo ya está almacenado en el objeto, ApplicableMethod no será útil, ya que devolverá el llamado "getter del sistema" que recupera la información almacenada:

gap> G:=Group( (1,2,3,4,5,6,7,8),(1,2) );
Group([ (1,2,3,4,5,6,7,8), (1,2) ])
gap> Size(G);
40320
gap> ApplicableMethod(Size,[G]);
function( object ) ... end
gap> PageSource(last);
Cannot locate source of kernel function GetterFunc(Size).

En este caso, para encontrar el método real que se utiliza para calcular el atributo, tendría que crear el objeto desde cero:

gap> G:=Group( (1,2,3,4,5,6,7,8),(1,2) );
Group([ (1,2,3,4,5,6,7,8), (1,2) ])
gap> ApplicableMethod(Size,[G]);
function( G ) ... end
gap> PageSource(last);
Showing source in gap4r8p2/lib/grpperm.gi (from line 482)
##
InstallMethod( Size,
    "for a permutation group",
    true,
    [ IsPermGroup ], 0,
    G -> SizeStabChain( StabChainMutable( G ) ) );

Answer 3

$8! = 40320$ es muy, muy pequeño en términos informáticos. El ordenador personal más barato de hoy en día puede hacer alrededor de $100$ millones de operaciones por segundo, por lo que cualquier algoritmo que tarde un tiempo proporcional al tamaño del grupo podrá enumerar $S_8$ en una fracción de segundo. Una búsqueda exhaustiva con memoización (como breadth-first o depth-first) sería suficiente.

James Mitchell señala que GAP no utiliza este método, por lo que ésta es sólo una posible forma que funciona para un número reducido de generadores. La ventaja de este enfoque de propósito general es simplemente que funciona para todos los demás tipos de estructuras generadas. Es asintóticamente óptimo para un número constante de generadores y cuando todos los elementos tienen una longitud de descripción constante.

Digamos que utilizamos la búsqueda en profundidad (también conocida como DFS) con memoización para generar los elementos del grupo dados sus (finitamente muchos) generadores. Usamos un procedimiento recursivo que, dado cualquier elemento del grupo como entrada, genera todos los posibles elementos del grupo que se pueden obtener de la entrada multiplicando por la derecha un generador o su inverso (multiplicar por la izquierda también estaría bien). Para cada elemento obtenido, el procedimiento se llama a sí mismo con ese elemento como entrada. Por supuesto, siempre utilizamos la memoización, lo que significa que nunca ejecutamos el procedimiento con la misma entrada dos veces. Esto se consigue fácilmente comprobando al principio del procedimiento si la entrada ha sido procesada antes, y terminando si es así. Tenga en cuenta que el procedimiento debe registrar que ha procesado la entrada antes de hacer cualquier llamada recursiva, de lo contrario entrará en un bucle infinito. Además, dado que los generadores se dan como permutaciones, sólo hay un número finito de elementos, por lo que se garantiza que el procedimiento termine. Aquí hay un pseudocódigo:

MemTable reach
Procedure group(Set<Perm> S,Perm x):
  If reach.have(x):
    Return
  reach.record(x)
  Output(x)
  For each g in S:
    group(S,x*g)
    group(S,x*inverse(g))

y para imprimir todos los elementos de un grupo generado por un conjunto S de permutaciones que uno haría:

reach.clear()
group(S,identity)