Probability that two randomly chosen permutations will generate $S_n$.

Question

Every undergraduate learns a fact about the symmetric group that $(1\,2)$ and $(1\,2\,\cdots\,n)$ generate $S_n$.

Also, it is interesting to know that for a prime $p$, any 2-cycle and any $p$-cycle generates $S_p$, but an arbitrary $2$-cycle and arbirtary $n$-cycle may not generate $S_n$. There is a criteria for the later:

Theorem: For $1\leq i<j\leq n$, $\langle (1\,2\,\cdots\,n), (i\,j)\rangle=S_n$ if and only if $(n,j-i)=1$.

With these interesting facts, I would like to ask two questions:

Q.1 If $\sigma,\tau\in S_n$ are cycles then what is the necessary and / or sufficient condition on $\sigma,\tau,n$ so that $\langle \sigma,\tau\rangle=S_n$?

Q.2 What is the totality of subsets $ S\subseteq S_n$ such that $|S|=2$ and $\langle S\rangle=S_n$?

(Answers to the both questions will involve combinatorics, and this will be a good place to see how combinatorics is useful to study finite groups; in fact, a part of answer will also involve nice combinatorial arguments. The second question may be hard!)

Answer 1

It can be shown the odds of two random permutations generating $S_n$ or $A_n$ is $1 - \frac{1}{n} - O(\frac{1}{n^2})$.

• $\mathbb{P} = \frac{1}{n}$ both permutations fix the same element, so $\langle S \rangle \subset S_{n-1}$
• $\mathbb{P} = \frac{1}{4}$ both permutations have the same parity (odd or even), $\langle S \rangle \subset A_n$

This result due to László Babai, on The Probability of Generating the Symmetric Group.

However, if you don't want to use the classification of finite simple groups you can show this probability is greater than $1 - \frac{2}{\log \log n}$. This is proven by John Dixon around 1970.

More recently, the same author gets further terms for the odds of generating the symmetric group: $$1 - \frac{1}{n} - \frac{1}{n^2} - \frac{4}{n^3} - \frac{23}{n^4} - \frac{171}{n^5} - \dots $$ You can count the coincidences by hand. The odds both elements fix or transpose the same two elements is of order $\frac{1}{n^2}$, etc.