Welcome to MathOverflow

Question

6

1

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?

edited May 10 2010 at 16:34

Gabe Cunningham
1,051●1●12●24

asked May 10 2010 at 13:52

Roland Bacher
6,916●10●37

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 2010 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 2010 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 2010 at 17:06

By the way, maybe someone can tell us what a random generating subset looks like? – Mariano Suárez-Alvarez May 10 2010 at 17:38

This question doesn't seem to have a 'right' answer. Shouldn't it therefore be community wiki? – HW May 10 2010 at 19:19

Igor Pak · Answer 1 · 2010-05-10 18:28:45Z UTC

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.

André Henriques · Answer 2 · 2010-05-10 15:07:46Z UTC

1

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

answered May 10 2010 at 15:07

André Henriques
14.9k●2●30●83

1

For example (1 4) and (1 2 3 4 5 6) maybe ? – Robin Chapman May 10 2010 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 2010 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 2010 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 2010 at 21:19

KConrad · Answer 3 · 2010-05-10 20:59:45Z UTC

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

“Natural” generating sets for symmetric groups.

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.