19
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ 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. $\endgroup$
    – villemoes
    May 10, 2010 at 15:00
  • $\begingroup$ 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. $\endgroup$
    – Gabe Cunningham
    May 10, 2010 at 15:20
  • $\begingroup$ I guss that by "natural" you mean "which arises in nature" as opposed to any other technical sense? $\endgroup$
    – Mariano Suárez-Álvarez
    May 10, 2010 at 17:06
  • $\begingroup$ By the way, maybe someone can tell us what a random generating subset looks like? $\endgroup$
    – Mariano Suárez-Álvarez
    May 10, 2010 at 17:38
  • 2
    $\begingroup$ This question doesn't seem to have a 'right' answer. Shouldn't it therefore be community wiki? $\endgroup$
    – HJRW
    May 10, 2010 at 19:19

8 Answers 8

Reset to default
20
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Could you select for us one or two generating sets that are "natural"? $\endgroup$
    – Wlod AA
    Oct 19, 2020 at 7:37
  • 2
    $\begingroup$ No. Decide for yourself based on what you need. Besides, your user information box says you want nothing to do with this website. $\endgroup$
    – KConrad
    Oct 19, 2020 at 14:14
  • $\begingroup$ I did in 1978, in the background document of my patent application. (I've invited a consultant who added his contribution, to be a coinventor; we got patent in less than a year, perhaps in 9 months -- I wonder if this is a record). $\endgroup$
    – Wlod AA
    Oct 19, 2020 at 16:45
10
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 ? $\endgroup$
    – GS
    May 10, 2010 at 20:29
  • $\begingroup$ 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). $\endgroup$
    – Igor Pak
    May 10, 2010 at 21:10
  • 1
    $\begingroup$ 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). $\endgroup$
    – Roland Bacher
    May 11, 2010 at 7:03
4
$\begingroup$

Another answer from a combinatorial point of view: the set of all transpositions is a generating set for $S_n$. Obviously this is a huge overkill. But a nice thing about including all transpositions is now your generating set is closed under conjugation. In fact, this generating set is used to define the so-called absolute order or reflection order (which applies more generally to any Coxeter group); the absolute order has as its Hasse diagram the Cayley graph with respect to the transpositions as generating set. Absolute order comes up for instance in Coxeter-Catalan combinatorics, a currently popular topic.

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ For example (1 4) and (1 2 3 4 5 6) maybe ? $\endgroup$
    – Robin Chapman
    May 10, 2010 at 15:21
  • 8
    $\begingroup$ 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. $\endgroup$
    – Roland Bacher
    May 10, 2010 at 15:23
  • 4
    $\begingroup$ 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. $\endgroup$
    – KConrad
    May 10, 2010 at 20:56
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steve D
    May 10, 2010 at 21:19
  • 1
    $\begingroup$ @LSpice: This article by Isaacs and Zieschang contains a proof. $\endgroup$
    – Steve D
    Aug 4, 2020 at 5:47
1
$\begingroup$

(apologies for the shameless self-promotion)

The book "Combinatorics of Genome Rearrangements" surveys a lot of these generating sets, with a focus on the symmetric and hyperoctahedral groups as far as permutations are concerned.

Those sets are "natural" in the sense that they reflect genetic mutations. They are not covered in full mathematical depth, but hopefully you can get a few interesting references out of the survey.

Improve this answer
$\endgroup$
1
$\begingroup$

Since you ask about generating by conjugacy classes, it might be worth remarking that $S_{n} = \langle C \rangle$ for any conjugacy class $C$ consisting of odd permutations. By the simplicity of $A_{n}$ for $n \geq 5$, it suffices to check $n \leq 4$, and only the case $n = 4$ and $C$ the conjugacy class of $4$-cycles requires any effort.

Improve this answer
$\endgroup$
1
$\begingroup$

You can take any tree $T$ on $[n]$ and the set of transpositions $(i,j)$ for $\{i,j\}$ an edge of $T$ will give a (minimal) generating set for $S_n$. This obviously includes the "usual" generating set of adjacent transposition, as well as the "star transpositions" mentioned by Igor Pak, but also many more examples. In general these generating sets are pretty similar to the usual adjacent transpositions, but have their own interesting combinatorics too. In particular, I believe there's a version of the Vandermonde determinant/bialternant definition of Schur functions that depends on this choice of tree $T$ (due to Alexander Postnikov), but I can't remember the exact details at the moment.

Improve this answer
$\endgroup$
1
  • $\begingroup$ If Richard Stanley sees this answer, I'm pretty sure he knows about the tree Vandermonde determinant thing I'm thinking of and could fill in the details... $\endgroup$
    – Sam Hopkins
    Oct 18, 2020 at 18:41
1
$\begingroup$

The action of the symmetric group on the $2$-sets $\{a,b\}$ with $a \ne b$ is primitive. Hence, the point stabilizer of $\{1,2\}$, i.e., the subgroup $H = \{ g \in \mathcal S_n \mid \{1,2\}^g = \{1,2\} \}$, is maximal. Observe that $H$ is generated by the full symmetric group on $\{3,\ldots, n\}$ and the single transposition that exchanges $1$ and $2$. So, taking any $g \notin H$ and a generating set for $H$ gives a set of generators for the full symmetric group on $\{1,\ldots,n\}$.

With this observation, it follows that if you take any generating set of the symmetric group on $\{3,\ldots,n\}$, $(1~2)$ and any $g \notin G$, for example $(2~3)$, will generate the symmetric group on $\{1,\ldots,n\}$. For example, the adjacent transpositions $(j~j+1)$ have this form and inductively many other generating sets could be constructed.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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