# Generators for $S_n$

This problem is from Dixon's book telling that; if $x$ is any nontrivial element of the symmetric group $S_n$ and $n≠4$, then there exists an element $y\in S_n$ such that $S_n=\langle x,y\rangle$. Honestly,the reference which Dixon referred to, is out of my hand. I can see this fact through $$S_3:=\{(), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) \}.$$ Please make sparks for me . Thanks.

-
"This problem." Which problem? "Dixon's book". Which book. "The reference which Dixon referred to." What reference. Or should I try searching for this particular problem in my bookshelf, when you have it right in front of you as you are posting? –  Arturo Magidin May 11 '12 at 20:24
What have you found on your own? –  Olivier Bégassat May 11 '12 at 20:39
I wonder whether there is an easy-ish way to do this, though I doubt it. Trivial observations: if you have an even permutation given, you need an odd one to generate $S_n$ rather than $A_n$; you need the permutations between them to move each of the underlying objects, otherwise you get a subgroup which stabilises a subset. The two permutations need to overlap (i.e. can't move disjoint sets of objects) else they would commute. Is it possible to choose a suitable n-cycle or (n-1)-cycle to match the permutation given? –  Mark Bennet May 11 '12 at 21:09
There are some classical sets of generators for the symmetric group. It might be handy to document these somewhere. All transpositions works. A transposition and a suitable n-cycle (which n-cycles work - I know some are easy to prove). A whole conjugacy class of odd permutations will also work (I can get any 3-cycle, by composing a suitable pair, hence $A_n$, and have an odd permutation too). –  Mark Bennet May 11 '12 at 21:47

Turns out to be problem 2.63 (which is starred, indicating its difficulty) in Problems in Group Theory by John D. Dixon, Dover Publications.

The solution provided is a simple reference. Unfortunately, the name of the author is misspelled in the reference:

Sophie Piccard, Sur les bases du groupe symétrique et du groupe alternant, Math. Ann. 116 (1939), pp. 752-767.

(The book lists the name incorrectly as "S. Picard")

The paper seems to be available through the Göttinger Digitalisierungszentrums, by going here and moving the appropriate page. I haven't had time to look through it.

-
It's Propisition I [sic] on page 753 and goes on till page 758. It seems complicated though elementary. –  lhf May 11 '12 at 21:11
A more modern reference is "Generating Symmetric Groups" by Isaacs and Zieschang, in the Monthly, v102, p734. It proceeds via Jordan's theorem on primitive permutation groups, and is very easy to follow. In fact, the article is only a few pages if you ignore the proof of Jordan's theorem given. –  user641 May 11 '12 at 21:15
@SteveD, nice! They don't mention Piccard, though. –  lhf May 11 '12 at 22:10
@Arturo: Sorry Prof. for the problem. I should not leave the problem such you pointed above. Thanks for the reference and Sorry again. –  Babak S. May 12 '12 at 5:27
@Steve: The theorem of Picard in interesting, and thanks for the modern reference. Nice reference. –  RDK May 31 '13 at 7:08