The symmetric group, 1

This is the first of a short series of posts which will try to look at the symmetric group in slightly fresh ways. It is in part a fraternal greeting to my friends on SymOmega, who named their blog after this wonderful object.

I begin with a diversion. What is a number? In particular, what is a small number like 3?

Most people distinguish two types of numbers, cardinal and ordinal. A cardinal number answers the question “how many?”, typically when the things we are counting are not being clearly distinguished; an ordinal number refers to a sequence whose elements come in order. Thus, “There are three sheep in the field” uses 3 as a cardinal number, and “Once upon a time there were three little pigs … the first pig built a house of straw … the second pig built a house of sticks … the third pig built a house of bricks …” uses 3 as an ordinal number. (There is a small problem here, which I will come to later.)

I want to extend the meaning of “ordinal number” slightly. Having the things counted come in order is really just a convenient way to distinguish them; but there may be other ways. For example, Elisabeth Kübler-Ross, the author of On Death and Dying, was one of triplets; but as her biography by Derek Gill makes very clear, the three sisters had very different personalities, and in no way resembled three sheep in a field. Moreover, their birth order seems irrelevant here. Again, to a first approximation, humanity can be divided into two genders; and, despite the story in Genesis and the title of Simone de Beauvoir’s famous book (or even the rules of chivalry), there seems no reason to say that one gender comes before the other.

(Incidentally, Kübler-Ross provides another example of things coming in threes. I was told about her by Liz Billington, then read a magazine article, then found the biography in a bookshop.)

So I will say that we use cardinal numbers to count interchangeable objects which we do not want do distinguish or treat individually; and ordinal numbers to count clearly distinguished objects.

But that is not all. Consider “paper, scissors, stone”, where the rules are:

  • scissors cut paper;
  • stone blunts scissors;
  • paper covers stone.

We are not interested in the three categories individually, but they are not interchangeable, since for example paper does not beat scissors. This cyclic structure is quite different from both the cardinal and the ordinal number 3.

There is another type as well. Examples are not so easy to find, so here is a question. In your kitchen drawer, you probably have separate compartments for knives, forks, and spoons, and they probably come in that order, but do they run left-to-right or right-to-left? (Right-to-left in my case at present, but it hasn’t always been so.) Now, when you are putting the cutlery away, you are not interested in the uses of the three types, but only getting them in the right order. We could say that there are two natural orders of the types of cutlery, one the reverse of the other. A better way, avoiding the ordering (as we did for ordinal numbers), is to say that forks come in the middle and we have no definite rule about the other two.

So this structure applies to sets of three where one is distinguished and we don’t discriminate between the other two.

Time for a digression within a digression. Jorge Luis Borges says:

The European fairy tale, and the Arab, are conventional. A ternary law rules them: there are two jealous sisters and a good younger sister, there are the king’s three sons, there are three crows, there is a riddle that is guessed by the third one who tries.

Indeed, the first two of the three little pigs are going to be eaten by the wolf in the first part of the story, so we don’t really need to distinguish them. And who can remember the difference between King Lear’s daughters Goneril and Regan?

So some of our ordinal 3s are really of this fourth, “one-distinguished”, type.

I chose to look at 3, because this phenomenon arises there for the first time. There are only two kinds of 2, cardinal and ordinal; and only one kind of 1.

But now we have to ask: Have we found all the different kinds of 3? And how many different kinds of 4, or in general, of n, are there? Here is my answer:

The number of different kinds of number n (in the sense I have described) is equal to the number of conjugacy classes of subgroups of the symmetric group Sn, or Sym({1,…,n}), the group of all permutations of {1,…,n}.

You might disagree; we can’t prove anything, since the question is too vague. But you might say, for even moderate n, there are many different structures on {1,…,n} which have only the trivial group of symmetries, for example. My contention is that, if the symmetry group of a structure is trivial, this means that all the objects 1,…,n can be distinguished from one another by the structure. For example, there are many different shapes of scalene triangles; but they all have the property that there is a vertex opposite the longest side, a vertex opposite the shortest side, and a vertex opposite the intermediate side.

The fact that we are counting conjugacy classes is less controversial, if harder to explain. Replacing a subgroup by a conjugate subgroup is exactly what happens when you re-number the elements of {1,…,n}; and the kind of number shouldn’t depend on the arbitrary enumeration we chose to set it up.

So there are four conjugacy classes of subgroups of S3, corresponding to our types of number 3 as follows:

  • The entire group (cardinal numbers).
  • The identity (ordinal numbers).
  • The cyclic group of order 3 (the “paper-scissors-stone” example).
  • The class of three cyclic groups of order 2 (the “one-distinguished” example).

So the number of “different” numbers n is the number of conjugacy classes of subgroups of Sn. Calculating this is a very difficult problem. The champion is certainly Alexander Hulpke, in work beginning in his PhD thesis, determining the numbers up to degree 11. Here is his list of values up to n=10.

1 1
2 2
3 4
4 11
5 19
6 56
7 96
8 296
9 554
10 1593

Nobody hopes to get a general formula; but what about asymptotics?

The symmetric group has an elementary subgroup of order 2n/2 generated by n/2 disjoint transpositions. (I assume that n is even; otherwise just leave one point fixed.) This group itself has about 2n2/16 subgroups. This is much greater than n!, the order of the symmetric group; so counting conjugacy classes rather than subgroups has no effect asymptotically.

In the other direction, in a remarkable piece of work, Laci Pyber showed that the number of subgroups (or conjugacy classes) in Sn is not more than cn2 for some constant c; but his constant c is a bit bigger than the sixteenth root of 2.

It is a bit unlikely that we will find uses for all this vast array of different kinds of number, however!



About Peter Cameron

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

8 Responses to The symmetric group, 1

  1. Pingback: The symmetric group, 2 « Peter Cameron's Blog

  2. Pingback: On the symmetric group « Peter Cameron's Blog

  3. Ralph Dratman says:

    “And who can remember the difference between King Lear’s daughters Goneril and Regan?”

    I am almost certain it was Regan who started plucking hairs out of Lear’s beard, for no obvious reason, when he was helpless. It is an act of savagery for which I cannot personally forgive her.

    Between Rosencrantz and Guildenstern, however, I do not think there is any real difference. Gertrude even has to say their names first in one order, then in the other, when pleading with them to probe Hamlet’s thoughts — probably because she could never remember which was which.

    • You have the advantage over me there. I know Geoffrey of Monmouth’s Lear, but never managed to get right through Shakespeare’s. (In Geoffrey the story has a happy ending.)

      I will probably get round to saying something about conjugacy sometime…

      • Ralph says:

        I found the Geoffrey of Monmouth Lear and am reading it now.

        I am extremely interested to learn more about your additional kinds of ordinal numbers. The concept gives me several ideas, particularly about rational numbers.

        Is there a web site or text to which I might refer to understand why the subgroups and their conjugacy classes are so difficult to compute? It seems that S3 is a subgroup of S4, and so forth — so I can see that the subgroups might pile up — but faster than n! itself? Seriously?

      • As I said, Alexander Hulpke has the best results about small values, and he is also extremely helpful. You might start with his stuff. I might say more about this later – but now, just back from giving the course on Laplacian eigenvalues, I am tired!

  4. Ralph Dratman says:

    I want to say I feel fortunate to know about this blog. It is like attending a tutorial class. I am slow at piecing things together in my mind, and it seems that I often see things in a peculiar way. Perhaps that is why I like your approach, which I see as naive in the best sense, uncluttered by prejudice, and open to new discussion of old topics without limitation.

    As for the conjugacy classes, I intend to keep trying to understand. I feel sure I will get it eventually.

  5. Ralph says:

    All conjugacy classes of subgroups… isn’t that the same as all integer partitions of subgroups?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s