El más pequeño trivial clase conjugacy en $S_n$

Question

Hallar el mínimo no trivial clase conjugacy en $S_n$.

Para los pequeños $n$, la respuesta se puede encontrar por conteo de permutaciones de cada posible tipo de ciclo. El resultado es: $$\begin{array}{ccc} n & \text{más pequeño trivial clase(s)} & \text{tamaño} \\ \hline 1 & \text{none} & \\ 2 & \text{transposiciones} & 1 \\ 3 & 3\text{-ciclos} & 2 \\ 4 & \text{doble transposiciones} & 3 \\ 5 & \text{transposiciones} & 10 \\ 6 & \text{transposiciones, triple transposiciones} & 15 \end{array}$$

Para $n\geq 7$, creo que el único más pequeño trivial clase conjugacy en $S_n$ está dada por las transposiciones.

Las clases conjugacy en $S_n$ están dadas por los grupos de permutaciones del mismo tipo de ciclo. Para el tipo de ciclo $\alpha = 1^{a_1} 2^{a_2} \ldots$, el tamaño de la respectiva clase conjugacy es conocido por ser $$N_\alpha = \frac{n!}{\prod_i (i^{a_i} a_i!)}.$$ En particular, el número de transposiciones en $S_n$ es $\binom{n}{2}$.

De esta manera, queda por mostrar lo siguiente:

Vamos a $n \geq 7$ y $\alpha$ ser una partición de $n$ distinta de $1^n$ y $2^1 1^{n-2}$. Demostrar que $N_\alpha > \binom{n}{2}$.

Hasta ahora sólo se puede venir para arriba con una larga y técnica de caso-por-caso de estudio. Estoy buscando una forma más elegante de la prueba de la declaración.

Answer 1

Creo que no hay un enfoque conceptual de dar un sentido a la comparación de conjugacy el tamaño de las clases, pero creo que hay una manera de hacer que el argumento bastante corto. La primera cosa a hacer es cancelar el plazo $a_1!$ para $i=1$ (para los puntos restantes fijo) en el denominador en contra de una parte del numerador $n!$, lo que deja el numerador igual a $n(n-1)\ldots(a_1+1)$ (el número de factores es la suma de los tamaños de los ciclos de la clase conjugacy, en el grupo de teoría de sentido, donde los ciclos no tienen la longitud$~1$).

Un primer fáciles de simplificación nos libera el caso de ciclo mixto estructuras, clases con más de un ciclo diferente longitud${}\geq2$. Para el ciclo de los tipos de podemos mapa permutaciones en la clase a otro de no-trivial tipo de ciclo simplemente omitiendo el ciclo(s) de la longitud más larga$~l$ a partir de la descomposición. Este mapa conmuta con cualquier conjugación por un permutaciones (que simple reetiqueta elementos en los ciclos) y es, por tanto, surjective a una nueva clase conjugacy; por otra parte no es inyectiva, ya que siempre hay más de una manera de reconstruir la longitud$~$ l ciclo(s). Por lo tanto, estas clases son nunca el menor no trivial.

El siguiente paso es mostrar que sólo tenemos que lidiar con el caso de transposiciones, posiblemente vuelo en formación. Más precisamente (y con tres excepciones que no se producen por $n\geq7$), la clase con $m$ discontinuo $k$-ciclos con $k>2$ es mayor que el de uno con $m$ discontinuo $2$-ciclos. Tenemos $a_k=m$ y el factor de nuestra fórmula como $$ \frac{n(n-1)\ldots(n-mk+1)}{k^m}\times\frac1{m.}, $$ donde el segundo factor es idéntica a la de la $k=2$. En el primer factor de reemplazo de $k$ por $2$ significa abandonar la última de $m(k-2) dólares de los factores del numerador y dividiendo el denominador por $(k/2)^m$. El uso de un producto de $k-2$ distintos números enteros positivos sólo puede ser${}\leq k/2$ si $k\leq4$, vemos que esto disminuye el primer factor, excepto cuando $a_1=0$ y $(m,k)\en\{(1,3),(1,4),(2,3)\}$, que sucede solo para $n=3,4,6$ (explica de que $3$-ciclos son menos numerosos para $n=3$, $n=4$ hay muchos $4$-ciclos como $2$-ciclos, es decir, $6$, y que para $n=6$ hay menos ($40$) pares de $3$-ciclos, a continuación, los pares de transposiciones $(45)$).

Hemos reducido para el caso de los $m$ discontinuo transposiciones, que lo vamos a comparar con aislados transposiciones ($m=1$). Fijo $m$, un aumento de $n$ deja el denominador sin cambios y aumentos de todos los factores en el numerador por$~1$. Esto le da mayor aumento relativo de $m>1$ que $m=1$, así que si la clase con $m$ discontinuo transposiciones, es ser menos numerosos que los que con una transposición, ya debe ser el caso para el mínimo valor posible de $n$, que es de $n=2m$. La fórmula para el número de productos de $m$ discontinuo transposiciones cuando $n=2m$ es el producto de $1\times 3\times\cdots\times(2m-1)$ (lo que algunas personas, desafiando a la ambigüedad, escribir como $(2m-1)!!$) que es de${}\leq\binom{2m}2$ por solo $m=2,3$; esto explica estos casos para $n=4,6$. Para $n\geq7$ esto no suceda más.

Answer 2

Esta es sólo una parcial argumento que soluciona algunos casos. La idea es simple: en lugar de centrarse en una determinada clase conjugacy, consideramos que una adecuada alimentación, que tiene más simple de la estructura del ciclo.

De ello se desprende del hecho de que $\binom{n}{2}<\binom nl$ para todo $2<l<n-2$ que para cualquier permutación con longitud total de $l$ (es decir, tener $n l$ puntos fijos), su clase conjugacy es stricly más grande que el de las transposiciones. De hecho, por cada elección de $n l$ puntos hay varias permutaciones en que clase conjugacy teniendo estos como fijo pionts. También, para $l=n-2$ y $n\geq 5$, por cada elección de dos puntos hay varias permutaciones en que clase conjugacy tener estos puntos como puntos fijos. Así que no son sólo $2 dólares de los casos de interés: $l=n-1$ y $l=n$, es decir $\sigma$ tiene un punto fijo y ninguno respectivamente.

En cualquier caso, si hay dos distintas duraciones del ciclo $2\leq k<K$, entonces podemos considerar que la permutación $\sigma^k$ en su lugar. Esta permutación es diferente de la identidad, y tiene por lo menos $2\leq k$ puntos fijos, por lo que por el argumento anterior de su clase conjugacy contiene al menos $\binom n2$ elementos. El mapa $$\mathrm{Conj}(\sigma)\a\mathrm{Conj}(\sigma^k),~\theta\mapsto \theta^k$$ es sobre y no inyectiva cuando $k\geq 3$ o $k=2$ y hay al menos dos $2$-ciclos en $\sigma$. Además, si $\sigma$ contiene sólo uno $2$ ciclo, entonces obviamente existen más de $\binom n2$ elementos en la clase conjugacy. Así que tu afirmación es verdadera cuando $\sigma$ contiene ciclos de diferente duración.

Así que no hay restos de un caso: $\sigma$ tiene una longitud de $n$ o $n-1$, y sólo una longitud de ciclo de la $k$.

Si $\sigma$ tiene un punto fijo, entonces la elección del punto fijo cuentas por $n$ opciones ya. Sin embargo, podría ser más fácil recurrir a la fórmula que se ha mencionado al principio: tenemos $n=qk+1$ y la cardinalidad es igual a $\frac{n!}{k^q!}$.