# “Natural” generating sets for symmetric groups.

The symmetric group on $n$ letters has many sets of generators. Some of them are more natural than others, eg the set $(i,i+1)$ of adjacent transpositions (natural with respect to the type A Weyl group), the set of all shuffles (permutations corresponding to "card-shuffles", ie $\sigma(1),\sigma(2),\dots,$ contains at most two increasing subsequences) perhaps also sets consisting of conjugacy classes (preferably of signature $-1$ in order to avoid a stupid mistake).

Which other sets of generators of symmetric groups occur in a natural way?

-
I guess you need to give a more precise definition of what you expect from a natural generating set. The transpositions (i,i+1) are only "natural" when you take into account the extra structure on your set, the linear ordering of {1,...,n}. Other structures on the underlying set might give rise to other "natural" generating sets. BTW, what is a "shuffle", if it is not just a synonym for a permutation? If it is a permutation without fixed points, then S_3 is not generated by shuffles. –  villemoes May 10 '10 at 15:00
The definition I'm familiar with is that a permutation p is a shuffle if the sequence p(1), p(2), ..., p(n) consists of two increasing subsequences that have been interleaved. Informally speaking, shuffles are exactly those permutations that are obtained by performing a single riffle shuffle on a deck of cards. –  Gabe Cunningham May 10 '10 at 15:20
I guss that by "natural" you mean "which arises in nature" as opposed to any other technical sense? –  Mariano Suárez-Alvarez May 10 '10 at 17:06
By the way, maybe someone can tell us what a random generating subset looks like? –  Mariano Suárez-Alvarez May 10 '10 at 17:38
This question doesn't seem to have a 'right' answer. Shouldn't it therefore be community wiki? –  HJRW May 10 '10 at 19:19

I wrote a handout on generating sets for symmetric and alternating groups for an algebra course. It's available at http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/genset.pdf. The table at the end of Section 1 lists several choices of generating sets for $S_n$ and $A_n$.

-

I am not exactly sure what you looking for. As you know, two random permutations generate $S_n$ or $A_n$ with probability $\to 1$ as $n\to \infty$. However, if you are looking for generating sets that came up in my work, here a a couple:

1) $a = (12)(34)\cdots$, $b= (23)(45)\cdots$, $c=(12)$. The generating set $\{a,b,c\}$ comes up in a number of problems and even has a name $(2,2\times 2)$ generating set (three involutions two of which commute). See here for many refs to $(2,2\times 2)$ generating sets.

2) $s_i = (1,i)$, $i=2\ldots n$. These are called "star transpositions" and have a number of interesting combinatorial properties. See here (pref-f. 2b) how they come up in Knuth ACP.

-
Hi Igor! Does the published version of your paper differ much from the free version, which I found at math.ucla.edu/~pak/papers/hamcayley9.pdf ? –  GS May 10 '10 at 20:29
Hi Steve! No, I think it is pretty much the same. Thank you for checking it out. The article has a survey section where I discuss many people effort to study $(2,2\times 2)$ generating sets in simple groups (this is based on classification - with few exceptions, almost all series and all sporadics have such generating triples). –  Igor Pak May 10 '10 at 21:10
Your example 1) is new two me. 2) falls into a larger class: Consider a simple connected graph with $n$ vertices labelled from $1$ to $n$. The edges of the graph, considered as transpositions of their endpoints, generate always $S_n$. The line graph yields $(i,i+1)$, the star graph your example 2). –  Roland Bacher May 11 '10 at 7:03

Here's an example: One transposition, and one cycle of length n.

-
For example (1 4) and (1 2 3 4 5 6) maybe ? –  Robin Chapman May 10 '10 at 15:21
You cannot choose the transposition completely arbitrarily. The permutation defined by adjacent elements of the cycle (in cyclic notation) always works since one gets then essentially back the set $(1,2),(2,3),\dots$. More generally, one can always choose (the transposition associated to) two elements at (cyclic) distance prime to the order since this does not change the situation in an essential way. I guess one has to be more careful for divisors, eg. the transposition $(1,3)$ and the cycle $(1,2,3,4)$ generete of course the dihedral group with 8 elements and not the symmetric group. –  Roland Bacher May 10 '10 at 15:23
We can always choose the numbering so that an n-cycle is (12...n). The 2-cycle (ab) and the n-cycle (12...n) generate S_n if and only if b-a is relatively prime to n. If you want to state this for any n-cycle, then it goes as follows. Let s be an n-cycle in S_n and t = (ab) be a transposition. There is a unique k in Z/n such that s^k(a) = b. Then s and t generate S_n if and only if k and n are relatively prime. –  KConrad May 10 '10 at 20:56
In fact, if $n\neq 4$, given any element of $S_n$, you can always choose another element which, together, generate the whole group. The same is true of $A_n$, but is much harder to prove, I think. –  Steve D May 10 '10 at 21:19