Dixon's theorem

Statement

Let $S_{n}$ denote the symmetric group of degree $n$, and $A_{n}$ denote the subgroup that is the alternating group. Pick two elements independently of each other, both uniformly at random, from $S_{n}$. Denote by $f_{1}(n)$ the probability that they generate all of $S_{n}$, and by $f_{2}(n)$ the probability that they generate $A_{n}$.

Then:

$\lim _{n\to \infty }f_{1}(n)={\frac {3}{4}}$

and:

$\lim _{n\to \infty }f_{2}(n)={\frac {1}{4}}$

Thus:

$\lim _{n\to \infty }f_{1}(n)+f_{2}(n)=1$

Another way of putting this is as follows:

• Define by $g_{1}(n)$ the probability that two permutations generate the whole group conditional to the elements not both being even permutations. Then, clearly $f_{1}(n)=(3/4)g_{1}(n)$. The first part of Dixon's theorem states that $\lim _{n\to \infty }g_{1}(n)=1$.
• Define by $g_{2}(n)$ the probability that two permutations generate the whole group conditional to the elements both being even permutations. Then, clearly $f_{2}(n)=(1/4)g_{2}(n)$. The second part of Dixon's theorem states that $\lim _{n\to \infty }g_{2}(n)=1$.

Related facts

• Symmetric group on a finite set is 2-generated
• Alternating group on a finite set is 2-generated