## The symmetric group, 3

No account of the symmetric group can be complete without mentioning the remarkable fact that the symmetric group of degree n (finite or infinite) has an outer automorphism if and only if n=6.

Here are the definitions. An automorphism of a group G is a permutation p of the group which preserves products, that is, (xy)p=(xp)(yp) for all x,y (where, as a card-carrying algebraist, I write the function on the right of its argument). The automorphisms of G themselves form a group, and the inner automorphisms (the conjugation maps xg-1xg) form a normal subgroup; the factor group is the outer automorphism group of G. Abusing terminology, we say that G has outer automorphisms if the outer automorphism group is not the trivial group, that is, not all automorphisms are inner.

Now the symmetric group Sn has an outer automorphism if and only if it can act in more than one way on a set of n elements. For automorphisms simply permute all the actions on n points among themselves, and those which fix a given action are precisely the inner automorphisms. So an equivalent way of stating the remarkable fact is that only for n=6 does the symmetric group have more than one such action.

I will outline the construction for n=6, and the proof that such an action cannot exist for other n, and then say a bit about some of the remarkable consequences of the fact.

Sylvester, as well as being an accomplished mathematician, was a prolific deviser of terminology. I will use his terminology here, rather than the terminology of factors and factorisations in the previous post on the symmetric group. Let A be a fixed set of 6 elements. A duad is a 2-element subset of A; a syntheme a set of three duads forming a partition of A; and a synthematic total (or total) for short) a set of five synthemes partitioning the set of 15 duads. We are going to show that there are exactly six totals. Then any permutation of A induces a permutation of the set X of totals, and we have a second action of S6.

What does a total look like? Any two synthemes have at most one duad in common; if they lie in a common total, they must be disjoint, and together form a 6-cycle; if we colour the two synthemes red and blue, the colours alternate around the cycle. Now there are just two possibilities for a further syntheme disjoint from these two: either one long diagonal and the two short diagonals not meeting it (shown in green), or three long diagonals (shown in magenta).

Since there are three long and six short diagonals, we must use all three of the first type.

Now we can count totals. There are 15 choices of a syntheme, and 8 choices for a second syntheme disjoint from the first; these determine a unique total. But in a given total, there are 5 choices of a syntheme, and 4 of a second. So the number of totals is 15.8/5.4=6.

It is interesting to note that the relationship between points and totals is symmetric: if we start with the set X of 6 totals and perform the construction, we get back to A. This depends on the following facts, whose verification is not too hard.

• Two totals have exactly one syntheme in common; so synthemes are “duads of totals”.
• Three synthemes lying in disjoint pairs of totals must consist of the synthemes containing a fixed duad; so duads are “synthemes of totals”.
• Duads come from disjoint synthemes of totals in this way if and only if they share a point; so points are “totals of totals”.

I learned this construction from a wonderful series of lectures by Graham Higman when I was a student in Oxford. He went on to use it to produce many other objects, including the following:

• A generalised quadrangle of order 2. (Take the duads as points and the synthemes as lines, incident if the duad is contained in the syntheme.)
• A projective plane of order 4. (Take the elements of A and the synthemes as points, the duads and totals as lines, with the obvious inclusion; in particular, no element of A is incident with any total.)
• A Steiner system S(5,6,12). (The point set is AX; the blocks are constructed directly from the duads and synthemes.)
• A Moore graph of valency 7 on 50 vertices.

In each case, it is not too much further work to prove the uniqueness of the constructed object.

I wrote an account of this in chapter 6 of my book Graphs, Codes and Designs with Jack van Lint.

Here is another nice application. The stabiliser of two points is a subgroup of index 2 in a duad stabiliser; it must correspond to a subgroup of index 2 in a syntheme stabiliser. Can we decide which?

Take a cube, and write the numbers 1,…,6 on its faces. Now the pairs of numbers on opposite faces form a syntheme. (Standard dice, for example, represent the syntheme 16|25|34.) But only half of its 48 symmetries are induced by rotations of the cube, since its mirror-image represents the same syndrome. It is not too hard to show that the rotation group of the cube is the subgroup we are looking for.

This has the following consequence. There are 30 different ways to colour the faces of a cube with six different colours, one on each face, up to rotation. If you take a set of 30 cubes and paint them in all possible ways, you will find that the cubes can be arranged in the off-diagonal positions of a 6×6 square so that the following two conditions hold:

• Each row or column corresponds to a synthematic total. In other words, if you pick up the five cubes in any row or column of the square, then each pair of colours is on opposite faces of exactly one of the five cubes.
• The cube in position (j,i) is the mirror image of the cube in position (i,j).

I made myself a set of 30 coloured cubes once, but I don’t know what has happened to it.

Why does this business only work for n=6?

A transposition is a permutation interchanging two points and fixing the rest. Two transpositions commute if and only if the pairs of points they interchange are disjoint. So, if an automorphism of Sn preserves the class of transpositions, then we can recover the original n points, and conclude that the automorphism is inner.

If there is an outer automorphism, it must map the transpositions to another conjugacy class of elements of order 2, also containing n(n–1)/2 elements. A bit of work shows that this is impossible unless n=6. There are tricks to make the work easier. For example, the centraliser of a transposition is a maximal subgroup if n>4; the only other class with this property consists of involutions with no fixed points. (Otherwise the involution centraliser is properly contained in the setwise stabiliser of the fixed point set.) These elements correspond to “duads” and “synthemes”, so Sylvester’s construction arises naturally.

Here to finish is a brief historical note. The theory of equations developed by Lagrange, Abel and Galois took as its starting point the fact that the cubic equation was solved with the help of an auxilliary (or “resolvent”) quadratic, and the quartic using a resolvent cubic. The group-theoretic analogue is that the symmetric groups S3 and S4 have actions on sets of size 2 and 3 respectively. However, the smallest action of S5 different from the given one is on a set of 6 points. This action can be seen from our construction. The group S6 acts on the 6 points and on the 6 synthematic totals. The stabiliser of a total is isomorphic to S5 (since it acts on the 5 totals different from the chosen one), but also acts on the 6 original points. In fact, in this action, it is more familiarly known as PGL(2,5). It is, of course, the automorphism group of a synthematic total.

I count all the things that need to be counted.
This entry was posted in exposition, history, symmetric group. Bookmark the permalink.

### 20 Responses to The symmetric group, 3

1. Gabriel Verret says:

Shouldn’t “if they lie in a common syntheme” be “if they lie in a common total”?

2. In case you should stumble over your 30 cubes again, here is a nice brain teaser (“MacMahon’s cubes”): Pick any cube as a “model”, then select eight cubes from the remaining 29 and use them to build a 2x2x2 replica of the model. There is one extra condition, though: Any two faces meeting in the interior of the replica must have the same color.

3. roger luther says:

why, precisely, is the group of permutations called the “Symmetric” group?

• Good question.

I believe the answer comes from the origins of group theory, where a group (or permutation group) typically consisted of all permutations of the variables which leave a certain function invariant. A symmetric function is one (like xy+yz+zx) invariant under all permutations of its arguments; correspondingly, the group of all permutations is also called “symmetric”. By contrast, a function like (xy)(yz)(zx) is invariant under even permutations and changes sign under odd permutations, so the function and the corresponding group are called “alternating”.

4. dratman says:

Group theory is absolutely amazing. Who would have imagined all the richness to be discovered in such modest objects created using quite simple means? Then again, maybe I should look at the number 720 through the eyes of a child: that’s a lot of permutations!

As a newcomer, I find the proliferation of terminology quite vexing, yet it’s not hard to see that entering such an unexpected jungle of phenomena might leave explorers at a loss for — or else with a surfeit of — words.

And maybe it’s just me, but this topic still feels very young. It is as though I stumbled at random into the first opening of an ancient golden city only just (re)discovered, and was watching giddy tourists and guides alike wandering around the streets, mesmerized by the sights.

“Or like stout Cortez when with eagle eyes
He star’d at the Pacific—and all his men
Look’d at each other with a wild surmise—
Silent, upon a peak in Darien.”

I do understand that Galois was born 200 years ago! But this realm still seems like a magical secret place to me.

5. I am well aware that mathematics can seem shrouded in mystery to an outsider. Part of my aim on this blog is to explain things. But the level may be a bit variable. Lecturing to a postgraduate class on group theory is not quite the same as giving a public lecture on Sudoku. The same problem arises here.

I hope you will persevere; and don’t hesitate to ask if you need more explanation.

6. dratman says:

I’ve had undergraduate calculus, a semester of ordinary differential equations, some numerical work on PDEs and coupled systems of ODEs, and a lifelong interest in fun kinds of math via Lewis Carroll and Martin Gardner. I’ve loved permutations and combinations since high school. I know that e^i pi = -1 is useful for more than just tombstones — but I don’t think the square root of -1 should be called a “number,” any more than a matrix is a number.

I’ve known a few basic ideas about groups and fields for years, but the concepts never grabbed me all that much. Now that I’m learning a little bit more, I feel differently. I don’t mean to say that group theory is shrouded in mystery, exactly, but rather that it has been a wonderful surprise, like discovering a deep network of secret passages beneath one’s house.

Take S3, for example. What a lot there is to say about self-similar manipulations of the humble equilateral triangle! Epsilons and deltas are fine, for a purpose — namely physics — but this is what I call real math.

7. Pingback: Sitting Specially « Log24

8. Pingback: Midnight in the Garden « Log24

9. Pingback: Crosses for Sherlock « Log24

10. Gil Kalai says:

Dear Peter, can I reblog this post on my blog? best Gil

11. Gil Kalai says:

Reblogged this on Combinatorics and more and commented:
Here is with Peter’s kind permission a rebloging of Peter’s post on the automorphism group of $S_n$.

12. Dear Peter,
You have written that “For automorphisms simply permute all the actions on n points among themselves”. Could you please clarify this. How exactly is the action of Aut(G) defined on the set of all actions of G on [n]?

• Sorry, I was a bit brief there. It is slightly simpler to say “automorphisms permute all the transitive actions on n points among themselves”; this suffices for the argument, and it can be shown that we don’t lose anything by this simplification. Now in a transitive action of a group G on n points, the stabilisers of the points form a conjugacy class of subgroups of index n in G. So I am saying that any automorphism maps a conjugacy class of subgroups of index n to another such conjugacy class; this, I hope, is clear, since an automorphism maps a subgroup to a subgroup, preserves index, and preserves conjugacy.
The other thing we need is that an automorphism which fixes the conjugacy class of point stabilisers in the “standard” action must be an inner automorphism. This is because there is a natural bijection between the numbers 1,…,n and the point stabilisers, so such an automorphism φ induces a permutation of the set {1,…,n}. Let g be this permutation. Then φ followed by conjugation by g−1 fixes the points 1,…,n, and it is fairly easy to see that it must be the trivial automorphism. Thus φ is the inner automorphism induced by g.