What is the standard 2-generating set of the symmetric group good for?

Question

I apologize for this question which is obviously not research-level. I've been teaching to master students the standard generating sets of the symmetric and alternating groups and I wasn't able to give a simple, convincing example where it's useful to use the two-generating set $\{(1,2),(1,2,...,n)\}$. (I always find it annoying when we teach something and we're not able to convince the students that it's useful.) I asked a couple of colleagues and no simple answer came out -- let me stress that I'd like to find something simple enough, like a remark I could do in passing or an exercise that I could leave to the reader without cheating them. Do you know such examples ?

Answer 1

Let $f\in\mathbb{Q}[x]$ be an irreducible polynomial of prime degree $p$, with exactly $2$ non-real roots.

You can view the Galois group of $f$ (i.e., the Galois group of the splitting $f$) as a subgroup of $S_p$. Complex conjugation shows that the Galois group contains a transposition. You can use Cauchy's theorem from group theory to show that the Galois group contains a $p$-cycle.

Then $f$ has Galois group $S_p$. This uses the slightly stronger fact that $S_p$ is generated by any transposition and $p$-cycle (which can be proved from the standard two-generating set).

In turn, constructing a polynomial with Galois group $S_5$ is useful for proving insolvability of the quintic.

Answer 2

It might be interesting (to some) to see that every possible shuffle of a pack of $n$ cards can be achieved by a sequence of operations in which you either swap the first two cards or move the bottom card to the top of the pack.

Answer 3

As has been more or less said in comments, I think the important and useful thing to know is that $S_n$ can be generated by two elements.

It is less important which two you choose, but $(1,2)$ and $(1,2,3,\ldots,n)$ has the advantage that it is simply stated uniformly for all $n$.

Perhaps the single most important property of a generating set $X$ of a group $G$, and which could be explained to undergraduates, is that a homomorphism $f:G \to H$ to another group is determined by the images of $f$ on $X$. (This is the same principle as the fact that linear maps are determined by their images on a basis.)

So, if $H$ is a finite group, then there are at most $|H|^{|X|}$ homomorphisms from $G$ to $H$. This is important in particular in both the complexity and practical aspects of algorithmic group theory, which is an active research area.

In fact it embarrassing to have to admit that, there is no known general algorithm for computing ${\rm Aut}(G)$ for finite groups $G$ that has better complexity than the naive method of testing all possible images of the elements in a generating set. (Of course that is not relevant to $G=S_n$, for which ${\rm Aut}(G)$ is known.)

(I should add that, to check whether a given map $X \to H$ really does extend to a homomorphism $G \to H$, you also need a set of defining relations on $X$. There are such sets known for the two "standard generators" of $S_n$ -see here for example - but they are less easily stated.)

Answer 4

It is good for understanding that a small number of generators does not mean a small group.

At your very earliest encounter with permutation groups, you might think that with two generators $\alpha$ and $\beta$, well, how much can you get? Especially if one or both of them are of small order? I mean, with $\alpha=(1,2)$ you just have $\alpha^2=\text{id}$, and $\beta=(1,2,\ldots,n)$ also gives you just $n$ different permutations $\beta^1,\ldots,\beta^n=\text{id}$ so "obviously" there cannot be much more, can there?

An obvious analogy is the dihedral group $D_n$, where from your two generators — a rotation, which gives you $n$ permutations, and a reflection that gives you two — you get $2n$ permutations. So you might expect not much more here — and you would be surprised.

(And a small afterthought, which is starting to wander off-topic: It may be instructive to note that the huge difference we see here between $D_n$ and $S_n$ does not arise from the number of generators, or from their orders, nor from commutativity vs. noncommutativity. Surely, for an abelian group one is not surprised that a small number of small-order generators gives you only a small number of group elements, because order of composing the generators does not matter. But $D_n$ and $S_n$ are both nonabelian beyond the very smallest cases, yet they behave very differently. — In fact, I'm not sure how best to characterize this difference, or whether there is a meaningful general phenomenon there, or whether it is just "that's the way these two groups are".)

Answer 5

I've had occasions where I needed to know that some structure is "closed" under $S_n$. It is very convenient to only check that it is closed under those two, specific permutations. Afterwards, I can apply any permutation I want.

A similar idea is used to show that there is a finite axiomatization of NBG set theory.

Answer 6

This is pushing the envelope in terms of "useful".

Given a finitely generated discrete group $\Gamma=\langle \gamma_1,\dots,\gamma_k\rangle$, using the "Gelfand philosophy", its group algebra $\mathbb{C}\Gamma$ is the algebra of regular functions on its dual, $\widehat{\Gamma}$, and we write e.g. $\mathcal{O}(\widehat{\Gamma}):=\mathbb{C}\Gamma$.

If $\Gamma$ is generated by elements of finite order $n_1,\dots,n_k$, then, where $n=\sum_p n_p$, we have that $\widehat{\Gamma}$ is a quantum subgroup of the quantum permutation group $S_n^+$ as defined by Wang:

$$\widehat{\Gamma}\subseteq S_n^+.$$

It is long known that for finite $\Gamma$: $$\widehat{\Gamma}\subseteq S_{|\Gamma|^2}^+,$$

and using this we can show that in fact: $$\widehat{\Gamma}\subseteq S_{|\Gamma|}^+.$$

The generators above show that we have: $$\widehat{S_n}\subseteq S_{n+2}^+,$$

but as per the comments to Jukka's answer, for $n\geq 9$ we have: $$\widehat{S_n}\subseteq S_5^+.$$