Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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
add comment

3 Answers

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
1  
For example (1 4) and (1 2 3 4 5 6) maybe ? –  Robin Chapman May 10 '10 at 15:21
3  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.