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

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!)

• For Theorem, see "Group Theory: Selected Problems- B. Sury"; I would like to see other book where this Theorem is stated. – Beginner Jul 4 '13 at 9:27
• For references, see A001691 and A071605 from OEIS. To me it seems that Q2 is hard, at least if you want exact values. I think you can figure out bounds from the many papers that study the probability of generating $S_n$ with a pair of random permutations. For a recent result in this direction and some history about the problem, the paper "A. Maroti and C. M. Tamburini, Bounds for the probability of generating the symmetric and alternating groups, Arch. Math. (Basel), 96 (2011), 115-121" looked interesting. – Mikko Korhonen Jul 4 '13 at 14:34
• – Alexander Gruber Jul 5 '13 at 4:00

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$
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.