Symmetric group on a finite set is 2-generated

Statement

The Symmetric group (?) on a finite set is a 2-generated group (?): it can be generated by two elements.

Note that when the finite set has 3 or more elements (so the degree is 3 or more), the symmetric group is not cyclic, so we obtain that the Minimum size of generating set (?) is precisely 2.

Related facts

Stronger facts

• Dixon's theorem: This states that two randomly picked elements have a high chance of generating the whole symmetric group.

Also refer presentation theory of symmetric groups to learn about good choices of presentation for symmetric groups.

Facts used

1. Transpositions of adjacent elements generate the symmetric group on a finite set

Proof

A transposition and a cycle

Consider the set $\{ 1,2,3, \dots, n \}$. We show that the symmetric group on this set is generated by the permutations:

$(1,2)$ and $(1,2,3,\dots,n)$.

Proof: Observe that, for $0 \le i < n -1$:

$(1,2,3,\dots,n)^i (1,2) (1,2,3,\dots,n)^{-i} = (i+1,i+2)$

Thus, all transpositions of adjacent elements are in the subgroup generated by these two permutations. Using fact (1), we see that these two permutations generate the whole group.