El número de subgrupos distintos del grupo simétrico en n puntos está dado por n 13 en oeis:A005432 el número de clases de conjugación de los subgrupos es oeis:A000638 para n 18, y el número de clases de isomorfismo (abstracto) entre los subgrupos es oeis:A174511 para n 10 (obtengo 894 para n=11, 2065 para n=12, 3845 para n=13 y creo que 7872 para n=14).
Para dar una idea de estas cifras, las incluyo en una tabla a continuación para n 15. También incluyo el número de subgrupos transitivos de Sn, ya que es un número muy diferente. El número de clases de conjugación también se conoce como el número de grupos de permutación (transitivos e intransitivos por igual). Por lo que sé, combinar los grupos transitivos para formar grupos intransitivos implica una enorme cantidad de contabilidad y cálculos, por lo que no se ha hecho (el número de grupos transitivos se conoce hasta la década de los 30 y quizás hasta n 63 por ahora). No incluyo la estimación ingenua de $2^{n!}$ ya que para $n=5$ se obtiene 1329227995784915872903807060280344576, que es bastante mayor que el número de subgrupos, que es 156.
$$\begin{array}{r|rrrrrrrrrr} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \#sub & 1 & 2 & 6 & 30 & 156 & 1455 & 11300 & 151221 & 1694723 & 29594446 \\ \#ccs & 1 & 2 & 4 & 11 & 19 & 56 & 96 & 296 & 554 & 1593 \\ \#iso & 1 & 2 & 4 & 9 & 16 & 29 & 55 & 137 & 241 & 453 \\ \#trn & 1 & 1 & 2 & 5 & 5 & 16 & 7 & 50 & 34 & 45 \\ \end{array}$$ $$\begin{array}{r|rrrrr} n & 11 & 12 & 13 & 14 & 15 \\ \hline \#sub & 404126228 & 10594925360 & 175238308453 & 5651774693595 & ? \\ \#ccs & 3094 & 10723 & 20832 & 75154 & 159129 \\ \#iso & 894 & 2065 & 3845 & 7872 & ? \\ \#trn & 8 & 301 & 9 & 63 & 104 \\ \end{array}$$
Ningún método conocido es especialmente "eficiente" en n De lo contrario, se habrían calculado bastante más. Para encontrar el número de subgrupos dadas las clases de conjugación de los subgrupos, se toma un representante de cada clase de conjugación de los subgrupos, y se suman los índices de los normalizadores. En particular, #sub no es mucho más difícil de calcular que #ccs, pero es mucho más grande y menos útil.
La asintótica de estos números es bastante diferente de estos primeros términos, pero se da en Pyber (1993) y Pyber-Shalev (1997):
- $2^{\left(\tfrac1{16}+o(1)\right)n^2} \leq \#\text{sub} \leq 24^{\left(\tfrac16+o(1)\right)n^2}$ con la conjetura de que el límite inferior es ajustado.
- $\log(\#\text{sub}) = \Theta(n^2)$ En otras palabras
- $\log(\#\text{ccs}) = \Theta(n^2)$ porque un subgrupo puede tener como máximo $n!$ conjugados, y $n!$ es tan pequeño
- $C^{n^2/\log(n)} \leq \#\text{iso}$ para algunos $C>1$
Los límites inferiores se obtienen en su mayoría considerando p -subgrupos que dominan una vez n es lo suficientemente grande. El límite superior requiere que el CFSG controle los subgrupos insolubles. No he visto el límite superior para #iso, pero por supuesto se puede usar #iso #ccs.
2 votos
¿Has mirado el software llamado GAP? Tiene una rutina de enumeración de este tipo y parece ser razonablemente rápido.
9 votos
Por "único", ¿quieres decir "hasta el isomorfismo"? Dado que todo grupo de orden $n$ es isomorfo a un subgrupo de $S_n$ me parece difícil, no fácil, enumerar todos los subgrupos de $S_n$ hasta el isomorfismo. Enumerando todos los subgrupos de, digamos, $S_{64}$ incluiría la enumeración de todos los grupos de orden hasta $64$ Dado que hay 294 grupos de orden 64, parece una tarea difícil.
0 votos
¡Buena respuesta Arturo! (+1) Enumerar los subgrupos de $S_n$ (hasta el isomorfismo) es lo mismo que clasificar todos los grupos de orden $n$ y menos. Enumerando todo subgrupos de $S_n$ ¡¡(ignorando los isomorfismos) es aún peor!!
12 votos
@Bill: En realidad es más que enumerar todos los grupos de orden $n$ y menos, porque también tienen subgrupos de $S_n$ de orden más que $n$ .
0 votos
¡Uy! Tienes razón.
2 votos
Se dispone de asintótica para el número de subgrupos. Creo que para n grande todos son grupos abelianos elementales de 2. Las clases de conjugación son menos conocidas, pero todavía hay muchas, posiblemente un montón de grupos de 2 de segunda clase, pero lo olvido exactamente. Los recuentos exactos (punto, hasta la conjugación, o hasta el isomorfismo) probablemente no son factibles para n por encima de 50.
3 votos
@Arturo El grupo $S_{64}$ tiene bastantes más elementos que átomos hay en el universo. El hecho de que haya 294 grupos de tamaño 64 va a ser su menor problema, y no excluye la posibilidad de algoritmos eficientes de enumeración de subgrupos (donde el tiempo de ejecución debe medirse en función de $|S_n|$ y no de $n$ ).
2 votos
Creo que las clases de conjugación serían relevantes si estuvieras interesado en subgrupos normales (que son necesariamente uniones de clases de conjugación).
2 votos
@Joel: Y por supuesto, determinar el normal subgrupos de $S_n$ es razonablemente fácil: después de todo, sólo tienes cuatro posibilidades. $\{1\}$ , $A_n$ , $S_n$ y $\{1, (12)(34), (13)(24), (14)(23)\} for $ n=4$.
1 votos
@Alex: ¡Ja, es justo! La cuestión es que clasificar todos los subgrupos de $S_n$ hasta el isomorfismo es "realmente" lo mismo que clasificar todo grupos hasta el isomorfismo, así que no veo por qué debería haber una "respuesta fácil".
3 votos
@Arturo El problema de enumerar todos los subgrupos de un determinado $S_n$ no es en absoluto lo mismo que clasificar todos los grupos, es clasificar todos los grupos de permutación transitiva sobre a lo sumo $n$ cartas. Por supuesto, hay algoritmos que enumeran subgrupos de un grupo dado, algunos son más eficientes que otros. La presente pregunta se refiere a si existen algoritmos que funcionen de forma particularmente eficiente en el caso especial de $S_n$ . La única forma sensata de dar sentido a "particularmente eficiente" es comparar su tiempo de ejecución en $S_n$ con los tiempos de ejecución de los algoritmos genéricos en grupos de tamaño comparable.
1 votos
@AlexB: He preguntado (por el comentario "Además,...") si quería enumerar subgrupos hasta el isomorfismo Si este es el caso, que yo sepa no hay algoritmos que lo hagan (para $S_n$ o para cualquier otro grupo), a no ser que se encadene un algoritmo de enumeración con un algoritmo de comprobación de isomorfismo, lo que sigue sonando demasiado cerca de "clasificar todos los grupos" (al menos, todos los grupos hasta un cierto grado de acción). Y la última parte de la pregunta sugiere una "respuesta fácil", no una "particularmente eficiente" (ni siquiera veo que se mencione 'particularmente' en el post original...)
0 votos
¿Existen límites superiores para el número de subgrupos de $S_n$ ? (preferiblemente algo más pequeño que $2^{n!}$ )
2 votos
@Esofos: He publicado los límites superiores. Es más bien $1.7^{n^2}$ por lo que sigue siendo bastante grande, pero incluso los grupos abelianos elementales de 2 dan $1.04^{n^2}$ subgrupos.
0 votos
El libro "Finite Simple Groups" de Wilson trata de los subgrupos de $S_n$ y muchas otras cosas de interés.