The simplest possible permutation, apart from the identity, is a transposition, which interchanges two points and leaves the others where they are. In this post, I will talk about transpositions and other short elements.
Transpositions
Every permutation of a finite set is a product of transpositions. This is clear if you think of a permutation as sorting a list of numbers into decreasing order. For a formal proof, any permutation can be written as a product of disjoint cycles; and, once we have checked that
(1,2,3,…,n)=(1,2)(1,3)…(1,n),
we see that each cycle can be written as a product of transpositions (one fewer than its length).
In fact, this shows that a permutation π of {1,2,…,n} can be written as a product of n–c(π) transpositions; this is easily seen to be the minimum possible. (Here c(π) is the number of cycles of the permutation π.)
A small digression. The same permutation can be written in many different ways as a product of transpositions, but the parity of the number of transpositions is the same for all such expressions. The simplest way to see this is to show that it is the same as the parity of n–c(π). To show this, consider the effect of postmultiplying π by the transposition (i,j). If i and j lie in different cycles of π, these cycles are stitched together by the transposition; if they are in the same cycle, it is cut in two. In either case, the number of cycles changes by 1.
We don’t need all the transpositions to generate the symmetric group. The minimum number which suffice is n–1. Moreover, regarding transpositions as edges of a graph, a set of transpositions generates S_{n} if and only of the corresponding graph is connected; so minimal generating sets correspond to trees.
This has a curious consequence. If a set of transpositions forms a tree in this sense, then the product (in any order) of the transpositions is an n-cycle. Since all n-cycles are conjugate, each can be expressed in the same number of ways as the product of n–1 transpositions. How many? By Cayley’s Theorem, there are n^{n-2} trees; the edges of each can be ordered in (n–1)! ways. Since there are (n–1)! cycles, the required number is n^{n-2}.
The last posting in this series mentioned Julius Whiston’s theorem that the maximum size of an independent set in S_{n} is n–1. Clearly, the transpositions corresponding to the edges of a tree meet this bound. Philippe Cara and I determined all independent sets meeting the bound. There are others, but all involve only “short” elements (one can have a 3-cycle or a double transposition in such a set).
Another question: for each tree, we have a generating set for S_{n}. Can we give defining relations? I don’t know a general solution to this problem, but there is one very famous case, where the tree is a path of length n–1.
Let t_{1},…,t_{n-1} be transpositions forming the edges of a tree. What relations do they satify? We can easily write some down:
- t_{i}^{2}=1 for all i;
- (t_{i}t_{j})^{m}=1, where m=3 if t_{i} and t_{j} share a point, m=2 otherwise.
It turns out that only in the case when the tree is a path do these form defining relations for the symmetric group. This is the celebrated Coxeter presentation. (If you know about such things, this is because the path is the only tree whose line graph is the Coxeter–Dynkin diagram of a finite reflection group.)
For example, consider the three transpositions (1,2), (1,3) and (1,4) in S_{4}. The corresponding tree is a star. The Coxeter relations define the group generated by the reflections in the sides of an equilateral triangle in the Euclidean plane. This group is an extension of C_{∞}×C_{∞} by S_{3}; the normal subgroup consists of translations. Since S_{4} is an extension of C_{2}×C_{2} by S_{3}, we must add the square of the translation corresponding to a side of the triangle as a new relation. Such a translation is T=t_{(1,2)}t_{(1,3)}t_{(1,2)}t_{(2,3)}; so putting T^{2}=1 gives a presentation for S_{4}.
A group given by generators and relations is fabulous if, given any k generators, the group presented by these elements with the relations involving proper subsets of them has a Free ABelian normal subgroup, and the k-variable relators lie in this subgroup. This class includes surprisingly many groups: cyclic groups; Coxeter groups; S_{4} as just discussed; and, as Conway (who defined this term) said, “The Monster is fabulous”.
Another big area of mathematics opens up if we take these relations (in the case of a path), remove those asserting that transpositions have order 2, and replace the other relations by
- t_{i}t_{j}t_{i} = t_{j}t_{i}t_{j} if t_{i} and t_{j} share a point, t_{i}t_{j} = t_{j}t_{i} otherwise.
These are the relations for the braid group on n strings, which thus has the symmetric group as a quotient.
The next question is: which subgroups of the symmetric group can be generated by transpositions? This is easy to solve. Indeed, let G be a subgroup which contains a transposition. Define a relation on {1,…,n} by the rule that i and j are related if either i=j, or the transposition (i,j) is in G. This is an equivalence relation (transitivity comes from the fact that from (i,j) and (j,k) we can generate (i,k)). The transpositions generate a normal subgroup of G which is the direct product of symmetric groups on the equivalence classes. In particular,
- if G is transitive, then the equivalence classes all have the same size;
- if G is primitive (and contains a transposition), then it is the symmetric group S_{n}.
A few years ago, Simone Severini passed on to me a question from the Seqfan discussion list, concerning counting subgroups of symmetric groups generated by short elements. There are three ways to count: the total number of subgroups; the number up to conjugacy in S_{n}; and the number up to group isomorphism. We see that groups generated by transpositions are determined by partitions; so the number of such groups is the Bell number B(n) (the number of partitions of {1,…,n}), while the numbers up to conjugacy or isomorphism are both the partition number p(n) (the number of partitions of the positive integer n).
One of the achievements of late 19C and early 20C permutation group theory was showing that a primitive group containing am element with small support must be symmetric or alternating. I will discuss two further cases below.
3-cycles
The even permutations (those which are products of an even number of transpositions) make up the alternating group A_{n}, a normal subgroup of S_{n} of index 2 (for n>1).
The alternating group is generated by all products of two transpositions; these are the 3-cycles (x,y,z) and the double transpositions (x,y)(z,w). Since a double transposition is a product of two 3-cycles, we see that the 3-cycles generate A_{n}.
There is a presentation of A_{n}, closely related to the Coxeter presentation of S_{n}. Let u_{i} be the 3-cycle (1,2,i+2). Then u_{i}^{3}=1, and (u_{i}u_{j})^{2}=1 for i≠j. This gives a presentation.
Sergei Tsaranov suggested an interesting variant of this presentation. There are two essentially different ways in which two 3-cycles u and v can generate A_{4}, distinguished by whether (uv)^{2}=1 (as above) or (uv^{-1})^{2}=1. Tsaranov suggested varying the above presentation for A_{n} by replacing some of the relations by the variant versions.
More precisely, let X be a graph on the vertex set {1,…,n–2}. Now consider the group Ts(X) generated by elements u_{i}, for i=1,…,n–-2, subject to the relations
- (u_{i})^{3}=1 for all i;
- if i and j are adjacent in X, then (u_{i}u_{j}^{-1})^{2}=1, otherwise (u_{i}u_{j})^{2}=1.
Note that replacing a generator by its inverse corresponds to interchanging adjacency and non-adjacency at the corresponding vertex of X, that is, Seidel switching of X at that vertex. Thus, a group is associated to a Seidel switching class, an equivalence class of the switching relation.
If X is the null graph (or indeed any graph equivalent to it by switching, that is, any complete bipartite graph), then the group is the alternating group A_{n}. Many other interesting groups arise in this way, and there are fascinating geometric (root lattices) and combinatorial (two-graphs) aspects, which unfortunately I can’t discuss here.
The question about subgroups of S_{n} containing 3-cycles is much simpler. If two 3-cycles overlap, it is easy to check that they generate A_{4} or A_{5}; each of these groups contains all the 3-cycles. So let G be a subgroup of the symmetric group containing a 3-cycle. Say that i and j are related if either i=j, or there is a 3-cycle (i,j,k) for some k. Then, as before, this relation is an equivalence relation; and if i and j are related and also j and k are related, then the 3-cycle (i,j,k) belongs to G. So we see that the 3-cycles in G generate a direct product of alternating groups on the equivalence classes of this equivalence relation. In particular,
- if G is transitive, then all the classes have the same size, and are blocks of imprimitivity;
- if G is primitive (and contains a 3-cycle), then G is the alternating or symmetric group.
So now we can count subgroups generated by 3-cycles. It is much as for transpositions, except that no part of the partition can have size 2. So the number of subgroups is the number of partitions of the set {1,…,n} with no part of size 2, and the numbers of conjugacy classes or of isomorphism types are the number of partitions of the integer n with no part of size 2.
Double transpositions
I started thinking about this because Jan Saxl (who is about to give an instructional course on permutation groups in Venice, which is highly recommended) asked me if I knew a simple proof that a primitive group containing a double transposition must be symmetric or alternating (most of the time).
One of the interesting things is that the statement is not true without exception. The dihedral group of degree 5 and its transitive extension PSL(2,5) of degree 6, and the group GL(3,2) of degree 7 and its transitive extension AGL(3,2) of degree 8, contain double transpositions. Any primitive group of degree 9 or greater containing a double transposition is symmetric or alternating.
Here is a very brief account of a proof. (This is nineteenth century mathematics.)
- If the supports of two permutations meet in one point, then their commutator is a 3-cycle. So we may assume this doesn’t happen in our primitive group G.
- Let F be the set of supports of double transpositions. Then two elements of F which are not disjoint must meet in two or three points.
- If there are two meeting in three points, the corresponding double transpositions generate a dihedral group. Now looking at these 5-sets, we find that any two must meet in four points; and if there are any, then any two of the resulting 6-sets meet in 6 points, so we have all the points.
- So we may assume that any two members of F meet in 0 or 2 points. Say that {i,j} is distinguished in a member F of F if (i,j) is a cycle in a double transposition supported by F. Now, if both {i,j} and {i,k} are distinguished in the same set F, then we find a set of seven points on which the double transpositions generate GL(3,2); two such 7-sets meet in 6 points, and if so the double transpositions generate AGL(3,2); and two such 8-sets meet in 8 points, so we have everything.
- Finally, if each member of F has only two distinguished 2-sets, then these 2-sets are distinguished in every member of F containing them, so are blocks of imprimitivity, contradicting the assumption that G is primitive.
The original seqfan question also asked for enumeration of subgroups of S_{n} generated by 3-cycles and double transpositions. The existence of these exceptions makes the question harder. I did not give a formula for the numbers, but did give an algorithmic way to describe them. One point to note is that the numbers up to conjugacy and up to isomorphism are no longer equal in this case; for n=6, the alternating group A_{5} (fixing a point) and the group PSL(2,5) are isomorphic but not conjugate.
Pingback: The symmetric group, 8 « Peter Cameron's Blog | Silcon Group
Pingback: The symmetric group, 7 « Peter Cameron's Blog
Pingback: generated discreteness | Peter's ruminations
Pingback: From Turing to Cameron | Peter's ruminations
Nice post. A maybe stupid question: You write that the maximum number of independent generators of Sn is n-1. Does this also mean that the minimum number of generators needed to generate all Sn is n-1?
OK, sorry, I should have thought more before asking. Obsviously not.
Indeed, two generators suffice. But one can learn a little more: according to Whiston’s theorem, an independent set of size n-1 is a generating set, so any proper subgroup of S_n has at most n-2 generators. This was improved to about n/2 by Annabelle McIver and Peter Neumann.