Máximo orden posible de un elemento en$S_7 \text{ and } S_{10}$

Question

Ejercicio :

Encontrar el máximo posible orden de un elemento del grupo de permutaciones $S_7$. Hacer la misma cosa para $S_{10}$.

Discusión :

Recordando que cualquier permutación se puede escribir como un producto de ciclos disjuntos :

$$c=c_1 c_2\dots c_r$$

el orden de $|σ|=\text{lcm}(|σ_1||σ_2|\dots|c_r|)$ e si $c_i$ tiene una longitud de $k_i$ será $|c_i|=k_i$.

Así que lo que tenemos que hacer es encontrar todos los posibles productos de ciclos disjuntos, que serán los siguientes :

$$(1,2) \space \text{ of order } \space 2$$ $$(1,2,3) \space \text{ of order } \space 3$$ $$(1,2,3,4) \space \text{ of order } \space 4$$ $$(1,2)(3,4) \space \text{ of order } \space 2$$ $$(1,2,3,4,5) \space \text{ of order } \space 5$$ $$(1,2,3)(4,5) \space \text{ of order } \space 6$$ $$(1,2,3,4,5,6) \space \text{ of order } \space 6$$ $$(1,2,3,4)(5,6) \space \text{ of order } \space 4$$ $$(1,2)(3,4)(5,6) \space \text{ of order } \space 2$$ $$(1,2,3)(4,5,6) \space \text{ of order } \space 3$$ $$(1,2,3)(4,5)(6,7) \space \text{ of order } \space 6$$ $$(1,2,3,4,5)(6,7) \space \text{ of order } \space 10$$ $$(1,2,3,4)(5,6,7) \space \text{ of order } \space 12$$ $$(1,2,3,4,5,6,7) \space \text{ of order } \space 7$$

Así, el máximo posible orden de un elemento en $S_7$$12$.

Pregunta :

Lo que yo quería preguntar es $(1)$ estoy en lo correcto, primero de todos?

Y $(2)$ ¿cómo se supone que voy a encontrar el máximo orden de un elemento en $S_{10}$ ? A juzgar por todos los posibles productos con ciclos de en $S_7$ va a ser una gran lista para $S_{10}$. Me estoy perdiendo un truco o algo de forma inteligente para alcanzar el resultado deseado más rápido ?

P. S. : yo sé que Landau de la función calcula exactamente que cosa, pero no hemos sido enseñados.

Answer 1

Primero de todo, sí, tu respuesta para $S_7$ es correcta. Y, de hecho, listado de todo el ciclo de tipos rápidamente se convierte en inmanejable como $n$ crece.

Es muy útil y no es difícil demostrar que el máximo es siempre asumido por una permutación que es el producto de ciclos disjuntos de potencia principal longitudes. Para el aumento de los valores de $n$ esto elimina un aumento de la proporción de permutaciones; para $n=7$ $n=10$ no elimina mucho.

También es muy útil y no es difícil demostrar que el máximo es siempre asumido por una permutación que tiene más de un punto fijo. Esto elimina una gran proporción de permutaciones para cualquier $n$.

Con estos dos hechos en mente, para $n=7$ nos quedamos con las permutaciones de ciclo de los tipos de $$(7),\ (5,2),\ (4,3),\ (4,2,1),\ (3,3,1),\ (3,2,2)\quad \text{y}\quad (2,2,2,1).$$ Para $n=10$ nos quedamos con las permutaciones de ciclo de los tipos de $$(9,1),\ (8,2),\ (7,3),\ (7,2,1),\ (5,5),\ (5,4,1),\ (5,3,2),\ (4,4,2),\ (4,3,3),\ (4,3,2,1),\ (3,3,3,1),\ (3,3,2,2),\quad\text{and}\quad (2,2,2,2,2).$$ Por supuesto, ya se puede ver algunos de recursividad en este problema, dado que la maxima para $n=3$ $n=5$ son asumidos por el ciclo de los tipos de $(3)$$(3,2)$, respectivamente, para $n=10$ podemos eliminar el ciclo de los tipos de $$(7,2,1),\ (5,5)\quad\text{and}\quad(5,4,1).$$ Hay un montón de hechos simples a tener en cuenta que cada reducir el número de ciclo de tipos a considerar un poco. Para su problema no hay que muchos, para empezar, y los hechos anteriores son suficientes para hacer que el problema sea en la mano. Pero puede ser hecho a mano por $n=100$$n=1000$, aunque esto requiere un análisis más cuidadoso del problema que no voy a entrar aquí. Los dejo con esta vaga intuición, aunque:

De forma heurística, para un gran $n$ el máximo se supone que cuando escribo $n$ como una suma de primer poderes cerca de $\sqrt{n}$, el relleno y el resto con pequeños números primos. No es fácil calcular la máxima precisión para valores grandes de a $n$, aunque asintóticamente es $\exp((1+o(1))\sqrt{n\ln{n}})$.

Answer 2

Verá que en$S_7$ la orden máxima posible está dada por$$(1,2,3,4)(5,6,7)$ $, de modo que el elemento utilizado$s_1,s_2$ es tal que$o(s_1)+o(s_2)=7$ que maximiza$l.c.m.$. Así que debe elegir un caso similar en$S_{10}$. La solución es$s_1,s_2,s_3$ tal que$o(s_1)=5,o(s_2)=3,o(s_3)=2$ así que:$$(1,2,3,4,5)(6,7,8)(9,10).$ $ No sé si es posible generalizarlo para$S_n$.