Probabilidad de que dos elegidos al azar de permutaciones generará $S_n$.

Question

Cada licenciatura aprende un hecho sobre el grupo simétrico que $(1\,2)$ $(1\,2\,\cdots\,n)$ generar $S_n$.

También, es interesante saber que para un primer $p$, 2 ciclo y cualquier $p$-ciclo genera $S_p$, pero de un arbitrario $2$-ciclo y arbirtary $n$-ciclo no puede generar $S_n$. No hay un criterio para la tarde:

Teorema: Para $1\leq i<j\leq n$, $\langle (1\,2\,\cdots\,n), (i\,j)\rangle=S_n$ si y sólo si $(n,j-i)=1$.

Con estos datos interesantes, me gustaría hacer dos preguntas:

P. 1 Si $\sigma,\tau\in S_n$ son ciclos, entonces ¿cuál es la necesaria y / o suficiente condición en $\sigma,\tau,n$, de modo que $\langle \sigma,\tau\rangle=S_n$?

P. 2 ¿Qué es la totalidad de los subconjuntos $ S\subseteq S_n$ tal que $|S|=2$$\langle S\rangle=S_n$?

(Las respuestas a las dos preguntas implicará la combinatoria, y este será un buen lugar para ver cómo la combinatoria es útil para el estudio de grupos finitos; de hecho, una parte de la respuesta también se involucran agradable combinatoria argumentos. La segunda pregunta puede ser difícil!)

Answer 1

Se puede demostrar que las probabilidades de dos permutaciones al azar generando $S_n$ o $A_n$$1 - \frac{1}{n} - O(\frac{1}{n^2})$.

• $\mathbb{P} = \frac{1}{n}$ tanto permutaciones solucionar el mismo elemento, $\langle S \rangle \subset S_{n-1}$
• $\mathbb{P} = \frac{1}{4}$ tanto permutaciones tienen la misma paridad (par o impar), $\langle S \rangle \subset A_n$

Este resultado debido a Laszlo Babai, en La Probabilidad de Generar el Grupo Simétrico.

Sin embargo, si usted no desea utilizar la clasificación de los finitos simples grupos puede mostrar esta probabilidad es $1 - \frac{2}{\log \log n}$. Esto es demostrado por Jon Dixon alrededor de 1970.

Más recientemente, el mismo autor consigue términos de las probabilidades de generar el grupo simétrico: $$1 - \frac{1}{n} - \frac{1}{n^2} - \frac{4}{n^3} - \frac{23}{n^4} - \frac{171}{n^5} - \dots $$ Usted puede contar las coincidencias con la mano. Las probabilidades de ambos elementos de la corrección o de la transposición de la misma dos elementos es de orden $\frac{1}{n^2}$, etc.