¿Cómo está GAP generando todos los subgrupos?

Question

GAP puede devolver todos los subgrupos de $S_4$ prácticamente al instante:

gap> AllSubgroups(SymmetricGroup(4));
[ Group(()), Group([ (1,2)(3,4) ]), Group([ (1,3)(2,4) ]), Group([ (1,4)(2,3) ]), Group([ (3,4) ]), Group([ (2,3) ]),
  Group([ (2,4) ]), Group([ (1,2) ]), Group([ (1,3) ]), Group([ (1,4) ]), Group([ (2,4,3) ]), Group([ (1,3,2) ]),
  Group([ (1,4,2) ]), Group([ (1,4,3) ]), Group([ (1,4)(2,3), (1,3)(2,4) ]), Group([ (3,4), (1,2)(3,4) ]),
  Group([ (1,4), (1,4)(2,3) ]), Group([ (2,4), (1,3)(2,4) ]), Group([ (1,3,2,4), (1,2)(3,4) ]), Group([ (1,4,3,2), (1,
   3)(2,4) ]), Group([ (1,2,4,3), (1,4)(2,3) ]), Group([ (3,4), (2,4,3) ]), Group([ (1,4), (1,4,3) ]),
  Group([ (2,3), (1,3,2) ]), Group([ (1,2), (1,4,2) ]), Group([ (1,4)(2,3), (1,3)(2,4), (3,4) ]), Group([ (1,2)
  (3,4), (1,3)(2,4), (1,4) ]), Group([ (1,2)(3,4), (1,4)(2,3), (2,4) ]), Group([ (1,4)(2,3), (1,3)(2,4), (2,4,3) ]),
  Group([ (1,4)(2,3), (1,3)(2,4), (2,4,3), (3,4) ]) ]

$S_4$ tiene 24 elementos ($4! = 24$).

Un enfoque ingenuo para generar todos los subgrupos de un grupo dado G consideraría todos los posibles subconjuntos de G (es decir, el conjunto potencia de G). En este caso, hay 16,777,216 posibles subconjuntos a considerar ($2^{24} = 16777216$).

Por supuesto, el orden de cada subgrupo debe dividir uniformemente el orden de G, por lo que podemos reducir la lista de subconjuntos a considerar usando este hecho (es decir, solo considerar subconjuntos que tengan un orden que divida uniformemente el orden de G). Para $S_4$, eso reduce la lista a 3,587,174.

¡Eso sigue siendo muchos conjuntos para considerar! Me sorprendería si GAP estuviera calculando los subgrupos sobre la marcha utilizando este enfoque ingenuo.

Entonces me pregunto cómo GAP devuelve la respuesta tan rápidamente. ¿GAP tiene precalculados los subgrupos de $S_4$ (y de otros grupos comunes)?

Answer 1

Las tiendas GAP almacenan listas precomputadas de subgrupos de (grupos de automorfismos) de varios subgrupos simples, el resto se calcula sobre la marcha. Sin embargo, utiliza mucha más teoría de grupos que solo considerar subconjuntos. (Por razones de uso de memoria, GAP calculará subgrupos solo hasta la conjugación de forma predeterminada.)

Los métodos usados siguen más o menos la siguiente estrategia:

• Si $G$ tiene un subgrupo normal abeliano elemental $N\lhd G$, cada subgrupo $U$ tiene una imagen $A=UN/N$ en $G/N$ y una intersección $B=U\cap N. Calcular de forma recursiva subgrupos de $G/N$, así como de $N$ (que es un espacio vectorial) y para cada par $(A,B)$ con $A/N\le G/N$ y $B\le N$ tal que $B\lhd A$ calcular complementos a $N/B$ en $A/B$ usando la cohomología.

• Si $G$ no tiene subgrupos normales solubles, entonces el socle $S=Soc(G)$ es un producto directo de grupos simples. Calcular subgrupos de $S$ como productos subdirectos de subgrupos de los factores simples, y luego para cada subgrupo considerar subgrupos de $N_G(S)/N$.

• Los subgrupos de los factores simples están almacenados.

Dos artículos que describen el proceso (Nota: sesgo del autor) son:

MR1806212 Cannon, John J.; Cox, Bruce C.; Holt, Derek F. Computing the subgroups of a permutation group. J. Symbolic Comput. 31 (2001), no. 1-2, 149–161.

MR3206359 Hulpke, Alexander Calculation of the subgroups of a trivial-fitting group. ISSAC 2013—Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, 205–210, ACM, Nueva York, 2013.

Answer 2

Un par de cosas:

1. Dudo mucho que precalculen S4. Tienes razón en que el enfoque ingenuo es malo, y es probable que tampoco utilicen eso. No intentaré desarrollar un algoritmo mejor aquí, pero parece que podría haber una manera un poco menos ingenua de encontrar todos los conjuntos generadores distintos a través de la programación dinámica, lo que imagino sería razonablemente eficiente en comparación.

2. GAP es software de código abierto (alojado en Github aquí), por lo que en realidad no es tan difícil investigar cómo funcionan los cálculos literales en sí mismos. El comando "AllSubgroups" está definido en este archivo. Parece depender de una manera clave del método ConjugacyClassesSubgroups de este archivo. Dicho esto, no conozco la sintaxis de GAP, por lo que alguien más tendría que analizar esos archivos particulares mejor.

3. Al mirar el código, vi una referencia a un artículo sobre mejores métodos para calcular subgrupos normales, que está aquí. Creo haber visto una referencia a ellos usando el método subyacente aquí, pero esto puede que ya no sea lo último en la tecnología. Aún así, para el lado teórico de (parte) de lo que hace GAP, esta es probablemente la mejor opción.