¿Es la distribución de las órdenes de los grupos cíclicos generados por elementos de $S_n$ conocido?

Question

Hace una semana yo estaba jugando con una tarjeta-shuffle método correspondiente a un elemento de $S_{52}$, y el orden del grupo cíclico generado fue de 272 (es decir, 272 baraja devuelve la cubierta original de la orden).

Estaba curioso por saber si era mayor o menor de lo esperado. Un cálculo completo requeriría de computación de las órdenes de la cíclico de los grupos generados por todos los $52!$ elementos de $S_{52}$, que es computacionalmente imposible, así que en su lugar me encontré con una simulación Monte-Carlo de las órdenes de la cíclico de los grupos generados por uniformemente distribuidas aleatoriamente elementos elegidos de $S_{52}$:

dat52 = ParallelTable[
   GroupOrder[PermutationGroup[{RandomPermutation[52]}]], {10^6}];

Aquí hay un grueso de registro-$x$-eje histograma de los resultados:

Histogram[dat52, "Log"]

El pico de cerca de 40 no es un artefacto estadístico; los resultados son sólo perturbado por $1/\sqrt{N}$ ruido, que en este caso es astronómicamente pequeñas (ver el $y$-eje).

Tenía curiosidad por ver si había alguna más finos de la estructura, así que he hecho el siguiente histograma como el de la imagen (click derecho y abrir en una pestaña nueva para ver grandes 4320 x 2320 píxel de la imagen):

El $x$-eje es logarítmica como antes, y el $y$-eje sube a cerca de 24.000 cuenta (no etiquetado). Como usted puede ver, hay un montón de estructura fina en la distribución de órdenes del grupo.

Del mismo modo, aquí está el histograma perfil del grupo de órdenes de los elementos de $S_{51}$ (de tamaño completo es 4320 x 2320 píxeles):

Aquí es $S_{53}$ (de tamaño completo es 4580 x 2020 píxeles):

Y aquí es $S_{256}$ (de tamaño completo es 10020 x 4020 píxeles):

Naturalmente, tengo curiosidad por ver si hay algo que sabe acerca de estas distribuciones, ya sea estructuralmente (es decir, una fórmula explícita para la distribución de cargos de $S_n$), o asintóticamente (es decir, la atenuación del perfil tiende a fulano de distribución como $n\to\infty$). ¿Alguien sabe, o se trata más allá de las matemáticas?

A partir de los comentarios en esta pregunta, parece que este es un problema difícil, pero todavía tenía curiosidad por saber en qué medida la estructura es explicable.

Answer 1

La pregunta puede ser factorizado en dos preguntas: ¿cuál es la distribución conjunta de las duraciones del ciclo de una permutación aleatoria, y lo que es el mcm de todo el ciclo de duración? La segunda pregunta es una forma tremendamente delicado aritmética cuestión (por ejemplo, la lcm depende delicadamente sobre si un gran ciclo pasa a tener el primer largo) así que me siento tentado a ignorar a concentrarse en la primera pregunta.

Aquí es lo que sé acerca de las duraciones del ciclo de permutaciones al azar. En primer lugar, es un buen ejercicio para mostrar que el número esperado de ciclos de longitud $k \le n$ en una permutación de $n$ elementos es $\frac{1}{k}$, y por lo tanto el total de número esperado de ciclos es

$$H_n = \sum_{k=1}^n \frac{1}{k} \approx \log n.$$

Al $k \ll n$ uno puede hacer mucho más fuertes declaraciones: como $n \to \infty$, el número de ciclos de longitud $k \ll n$ es asintóticamente Poisson con parámetro de $\frac{1}{k}$. Por otra parte, por varios $k \ll n$ estas variables aleatorias de Poisson son asintóticamente conjuntamente independiente. Ver este post en el blog algunos detalles.

Por desgracia, yo no sé mucho acerca de la gran $k$.

Edit: Un límite superior para el mcm de las duraciones del ciclo es su producto, y podemos decir algo acerca de eso. El producto es $\prod k^{c_k}$ donde $c_k$ es el número de ciclos de longitud $k$, por lo que el logaritmo de un producto es

$$\sum_{k=1}^n c_k \log k.$$

Si asumimos que el$c_k$, para todos los $k$, conjuntamente Poisson con parámetro de $\frac{1}{k}$, entonces podemos calcular los momentos de este logaritmo. Por ejemplo, su valor esperado es

$$\sum_{k=1}^n \frac{\log k}{k} \approx \frac{(\log n)^2}{2}.$$

Conectar $n = 52$ da que la exponencial del valor esperado del logaritmo del producto es de alrededor de $2400$, que es, al menos, dentro de un orden de magnitud de lo que tenemos.