22
$\begingroup$

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 him/her. Do you know such examples ?

$\endgroup$
14
  • 5
    $\begingroup$ I never heard or thought of this as "the" standard generating subset, it's one among many. It's maybe just the simplest one on 2 generators we can describe in mathematical terms. (By the way it also works in the symmetric group over $\mathbf{Z}$, using the shift $+1$ as infinite cycle, generating the whole finite support symmetric group.) A little farther from teaching level: It's also known to be highly inefficient compared to "generic pairs", if one wants to get the size of the Cayley graph as small as possible, or if one wants to generate random elements by multiplying random generators. $\endgroup$
    – YCor
    Oct 1, 2021 at 15:25
  • 2
    $\begingroup$ It's a little unclear from the question whether you're most interested in the fact that these particular two elements generate $S_n$, or whether you care more about the observation that $S_n$ is $2$-generated in general. $\endgroup$ Oct 1, 2021 at 15:31
  • 3
    $\begingroup$ @Sam Hopkins you're right. In fact I am not particularly interested in this 2-set, and I'd be pleased to bo told concrete applications of having a pair of generating elements in $S_n$. $\endgroup$ Oct 1, 2021 at 17:00
  • 2
    $\begingroup$ @LSpice All finite simple groups are $2$-generated. In fact the probability of any two randomly chosen elements generating a nonabelian simple group $G$ tends to $1$ as $|G| \to \infty$. $\endgroup$
    – Derek Holt
    Oct 1, 2021 at 22:01
  • 1
    $\begingroup$ This might be a good question for Mathematics Educators. $\endgroup$ Oct 2, 2021 at 12:34

6 Answers 6

37
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ But why is the order of the Galois group divisible by $p$? $\endgroup$ Oct 1, 2021 at 15:13
  • 2
    $\begingroup$ Let $\alpha$ be a root of $f$. Then the splitting field of $f$ contains $\mathbb{Q}(\alpha)$. Since $f$ is irreducible, we have $[\mathbb{Q}(\alpha):\mathbb{Q}]=p$. Then the degree of the splitting field is divisible by $p$, so the order of the Galois group is divisible by $p$. $\endgroup$ Oct 1, 2021 at 15:15
  • 1
    $\begingroup$ Ah right, I was blind. This is nice indeed! $\endgroup$ Oct 1, 2021 at 15:16
  • 2
    $\begingroup$ Marginally different presentation of the reasoning: the Galois group acts transitively on the $p$ roots since the polynomial is irreducible. So there’s an orbit of size $p$, the stabilizers have index $p$, Lagrange. $\endgroup$ Oct 2, 2021 at 0:52
  • 1
    $\begingroup$ I believe that this result is usually credited to Richard Brauer. $\endgroup$ Oct 2, 2021 at 13:21
22
$\begingroup$

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.

$\endgroup$
3
15
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ The term "standard generators" is a term that appears in the computational group theory literature. It seems (as far as I can tell) this means generators that have nice properties and are used in implementations in GAP/Magma, e.g. for recognition algorithms for the group. Are $(1,2)$ and $(1,2,3,\ldots,n)$ "standard generators" in this sense? $\endgroup$
    – spin
    Oct 2, 2021 at 10:24
  • 2
    $\begingroup$ @spin No, the "standard generators" in that sense are chosen individually for each group. The idea is that given a group $H$ that is either known or suspected to be isomorphic to the group $G$ in question, you can find the standard generators in $H$ as fast as possible by choosing random element of $H$. The standard generators of $S_n$ in that sense for $n \le 23$ can be found here. After finding the standard generators, you can set up the isomorphism between $H$ and $G$ such that images and inverse images can be computed quickly. $\endgroup$
    – Derek Holt
    Oct 2, 2021 at 10:47
  • $\begingroup$ Unfortunately the bound $|H|^{|X|}$ for $\text{Hom}(G,H)$ is quite crude so it is not clear to what extent the smallness of $X$ is a measure of the smallness of $G$. For example, let $G=S_n$ and $G'=(\mathbb{Z}/p\mathbb{Z})^r$. Choose $p>n$ prime and $r$ so that $p^r$ is comparable to (or even bigger than) $n!$, so $G$ and $G'$ have comparable sizes. (An example is when $p:=n+1$ is prime, then choose $r=n$.) In this case $\text{Hom}(G,S_n)$ will have size around $n!$ whereas $\text{Hom}(G',S_n)$ will be trivial. $\endgroup$ Oct 2, 2021 at 12:46
  • $\begingroup$ Yes I agree. The bound is useful for groups in general, but for symmetric groups it is usually too crude to be useful. $\endgroup$
    – Derek Holt
    Oct 2, 2021 at 14:01
  • $\begingroup$ FWIW, (thinking of any "standard" generators in a computational context), in SageMath you can ask for the generators of a group in three ways: gens() gives the ones that were used in creating the group, gens_small() returns a set with "few" elements, and minimal_generating_set() really gives a minimal set. For SymmetricGroup(n), on my machine at least, all three agree on $(1,2),(1,2,\ldots,n)$ except for $n=3$, where the last function returns $(2,3),(1,2,3)$! $\endgroup$ Oct 4, 2021 at 13:50
13
$\begingroup$

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".)

$\endgroup$
6
  • 2
    $\begingroup$ In fact $S_n$ can be generated by an element of order $2$ and an element of order $3$ for all $n>2$, but that's not obvious. $\endgroup$
    – Derek Holt
    Oct 1, 2021 at 20:22
  • 2
    $\begingroup$ @Derek Holt - there are exceptions... $n=5,6,8$ Miller, G.A., On the groups generated by 2 operators, Bull. Amer. Math. Soc. 7, 14–32, 1901. $\endgroup$ Oct 1, 2021 at 20:37
  • $\begingroup$ @JPMcCarthy Yes of course - I should have remembered that! $\endgroup$
    – Derek Holt
    Oct 1, 2021 at 22:00
  • $\begingroup$ @JPMcCarthy what happens for those $n$? $\endgroup$
    – David Roberts
    Oct 4, 2021 at 13:39
  • 1
    $\begingroup$ @JPMcCarthy I have asked a question on this: mathoverflow.net/questions/405477/… $\endgroup$
    – David Roberts
    Oct 5, 2021 at 6:03
11
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Can you mention an example where it is easier to show closure under two permutations of different cycle types, rather than under several different permutations of the same cycle type? In most situations that occur to me, if I can prove that a structure is preserved by $(1\ 2)$, then the same argument should prove that it's preserved by $(i\ i + 1)$ for all $i$, and hence by $\operatorname S_n$. $\endgroup$
    – LSpice
    Oct 1, 2021 at 21:21
  • 1
    $\begingroup$ there are computational advantages of few generator - e.g. if you need to check that a large structure, e.g. a graph, is invariant under (often, induced) action of the group. $\endgroup$ Oct 1, 2021 at 23:48
  • 1
    $\begingroup$ @LSpice Such situations occur quite often when you want some sort of closure under $S_n$, for all $n$ simultaneously, and at the same time you also want to express the situation finitely. For instance, consider the following condition defined on unital rings: (#) "For any $n\in N$ and any $\sigma\in S_n$, if $x_1 x_2 \cdots x_n=0$, then $x_{\sigma(1)} x_{\sigma(2)}\cdots x_{\sigma(n)}=0$." This can be checked much more simply via the condition (##) "If $x_1 x_2 x_3=0$, then $x_2 x_1 x_3=0$." It looks like we are only forcing closure under $(1\ 2)\in S_3$, but in unital rings (#)<=>(##). $\endgroup$ Oct 2, 2021 at 5:19
  • 2
    $\begingroup$ Clearly (#)=>(##), so let's show the converse. If $x_1 x_2 (x_3 \cdots x_n)=0$, then (##) implies $x_2 x_1 (x_3\cdots x_n)=0$. So we have closure under $(1\ 2)\in S_n$. Also, applying (##) to the product $x_1 (x_2\cdots x_n) 1=0$, we get $(x_2\cdots x_n)x_1 1=0$. [This works even when $n=2$.] So we get closure under the standard $n$-cycle. If you see an easier way to make this argument work using $(i\ i+1)$, I'd be interested. $\endgroup$ Oct 2, 2021 at 5:26
  • 2
    $\begingroup$ I should say that what motivates my question in the very first place is exactly the remark of LSpice. In most situations I encounter, after I've checked some property for $(1,2)$ then I notice that it works just the same for any transposition $(i,j)$ and hence for all permutations in $S_n$. $\endgroup$ Oct 2, 2021 at 9:29
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ This answer could equally apply to any generating pair including an element of order 2, right? $\endgroup$
    – YCor
    Oct 4, 2021 at 11:16
  • $\begingroup$ @YCor absolutely. Pushing the envelope in terms of useful but also pushing the envelope in terms of relevance. $\endgroup$ Oct 4, 2021 at 11:38

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.