The symmetric group, 5

Time to say a bit about the combinatorics of the symmetric group. Certainly not a complete survey of a vast topic, which would be quite impossible; I will touch on just a few things.

Loosely speaking, the subject divides into two parts:

• properties depending on the fact that the domain is totally ordered;
• properties independent of the ordering of the domain.

Now readers of my first posting about the symmetric group will note that we are thinking of the domain as an ordinal number in the first case, and a cardinal number in the second. According to the argument I outlined there, there should be many other theories, one corresponding to each conjugacy class of subgroups of the symmetric group. I have little idea what these theories might look like!

The first topic is classical, involving counting inversions (pairs (i,j) whose order is reversed by the permutation), descents (values of i for which π(i+1)<π(i)), etc. The big name associated with this is Major MacMahon, an associate of Hardy, Littlewood and Ramanujan, of whom Robert Kanigel said,

His expertise lay in combinatorics, a sort of glorified dice-throwing, and in it he had made contributions original enough to be named a Fellow of the Royal Society.

Glorified dice-throwing, indeed…

But I find more interest in the second type of result. For this, typical data about a permutation is its number of fixed points, or more generally the number of cycles of each possible length. This data is important in combinatorial enumeration. We can summarise the data about a permutation in a monomial, in which the exponent of the ith variable is the number of cycles of length i. Now, given any subgroup G of S_n, the cycle index polynomial of G is obtained by averaging the cycle index monomials of its elements. Many problems involving counting orbits of G acting on various things can be solved by appropriate substitutions for the variables. (This is known as Pólya theory.)

The sum of the cycle index polynomials of all finite symmetric groups turns out to be the probability generating function of independent Poisson random variables with parameters 1, 1/2, 1/3, … This means that in some sense the numbers of cycles of lengths 1, 2, 3, … in a random element of S_n for large n are close to independent Poissons; but making this precise requires careful estimates.

According to André Joyal, this summation is not a completely meaningless operation. Adding the cycle indices of the automorphism groups of the objects in a species gives the cycle index of the species. In the above case, this is the species of finite sets. There are connections with oligomorphic permutation groups too, which I will discuss another time.

I will just mention one special case, the Shift Theorem:

Let G be a finite permutation group with cycle index Z(G) in indeterminates s₁, s₂, … For each orbit O of G on the set of subsets of its domain, let H(O) be the group induced on a member of O by its setwise stabiliser in G. Then the sum of the cycle indices of all the groups H(O) is obtained from Z(G) by substituting s_i+1 for s_i for all i.

In particular, if we add up Z(S_i) for i=0,…,n, we obtain Z(S_n) with this substitution applied. For n=2, the cycle indices of the first three symmetric groups are 1, s₁, and (s₁²+s₂)/2, and the theorem says that

1+s₁+(s₁²+s₂)/2 = ((s₁+1)²+(s₂+1))/2.

The order of a permutation (the smallest power of it which is the identity) is the least common multiple of its cycle lengths) has been investigated, and results about its distribution for a random permutation are known. A sequence of papers by Erdős and Rényi develop “statistical group theory” of S_n.

As I hinted in an earlier post, there is another sort of “statistical group theory”: Dixon showed that almost all pairs of permutations generate the symmetric or alternating group, and Łuczak and Pyber showed that almost all permutations lie in no proper transitive subgroup except the symmetric or alternating group.

After cycle structure and order, the huge subject one meets is representation and character theory of the symmetric group. This theory, extremely combinatorial in nature (involving Young diagrams, tableaux, symmetric functions, etc., goes back to Frobenius and Young.

Graham Higman (my mathematical grandfather) described the character theory of the symmetric group as a subject which must be re-written for each new generation of mathematicians. This was in a paper applying the theory to varieties of groups. We will see below that recently it has been used for extremal combinatorics.

The symmetric group is indeed rich in problems of extremal combinatorics. If F is a finite field, then the vector space Fⁿ has a metric structure (Hamming distance, the number of coordinates in which two n-tuples differ), and an algebraic structure (vector addition): translations preserve distance. So extremal problems of coding theory (minimum distance, covering radius, etc.) can be asked for arbitrary subsets, and specialised to subspaces (linear codes). In the same way, the symmetric group has two structures: metric (regarding a permutation as a word of length n over the alphabet {1,…,n}), and group (with the operation of composition): again, translations preserve distance. So problems about sets of permutations can be asked in general or specialised to permutation groups (subgroups of the symmetric group).

Note that the distance between two permutations g and h is equal to n–fix(gh^-1).

An interesting piece of history surrounds the following theorem:

Let G be a subgroup of S_n, and let a₁, …, a_r be the numbers of fixed points of non-identity elements of G. Then the order of G divides (n–a₁)…(n–a_r).

The theorem was proved by Blichfeldt in 1904, using the then-new method of character theory. Blichfeldt, however, said that he was giving a new proof of a theorem proved by Maillet in 1895. In fact, Maillet proved a different theorem, since he assumed a stronger hypothesis, namely, that a₁,…,a_r are the numbers of fixed points of the non-identity subgroups of G. The theorem was rediscovered by Kiyota in 1979, by which time the world was ready for it, and a lot of research followed. Now, we know all the permutation groups attaining Maillet’s bound for r>1 (using the Classification of Finite Simple Groups), but the problem of finding all groups meeting Blichfeldt’s bound is still open.

Without the restriction to subgroups, it is clear that a set of permutations, any two agreeing in fewer than t positions, has cardinality at most n(n–1)…(n–t+1), with equality only in the case of sharply t-transitive sets of permutations. For t=1, such a set forms the rows of a Latin squares, and conversely; these exist in great profusion. For t>1, however, they are much rarer. For t=2, their existence is equivalent to that of a projective plane of order n. Such objects exist for prime-power n, and not for n congruent to 1 or 2 mod 4 but not the sum of two squares (the Bruck–Ryser theorem); this is the limit of our knowledge, apart from the isolated fact that there is no projective plane of order 10, proved by Clement Lam and co-workers, and involving one of the biggest computations ever performed.

So, with the present state of our knowledge, it might be that sharply 2-transitive sets of permutations exist only for prime power orders. We desperately need a new idea, and only a few brave souls like Navin Singhi are prepared to look for one.

What about the dual question, sets of permutations any two of which agree in at least t positions? Two observations go back to Deza and Frankl in 1977:

• The set of all permutations with prescribed values on t given points satisfies this condition, and has cardinality (n–t)!.
• Because of a simple result about cliques and cocliques in vertex-transitive graphs, if there is a sharply t-transitive set in S_n, a set agreeing in at least t places cannot have cardinality greater than (n–t)!.

So we’d like to know whether the bound holds, and whether equality is realised only by the known examples. This is the analogue for permutations of the Erdős–Ko–Rado theorem in extremal set theory.

For t=1, Deza and Frankl of course knew the bound; the case of equality had to wait 30 years, when it was settled by Ku and me, and independently by Larose and Malvenuto. For t=2, the bound follows for orders of projective planes (so maybe just for prime powers), and we have no clue about which sets meet the bound, nor whether it holds for all orders.

But, amazingly, the general result was proved by Ellis, and independently by Friedgut and Pilpel, for arbitrary t, provided that n is sufficiently large in terms of t. The proof is clearly the “right” one, using clique bounds from algebraic graph theory, which themselves depend on accurate estimates for character values of the symmetric group!

This was one of the problems I most wanted to see solved; I am delighted that it has been achieved.

The subject is not finished. The result is false if n is only a little larger than t. For example, if t=n–4, the bound is 24, whereas the identity and the transpositions form a set of size 1+n(n–1)/2 permutations with this property. Deza and Frankl gave a different bound which holds in this case. But there is a gap in which neither bound applies, and we don’t know what happens.

More generally, pick your favourite theorem in extremal set theory; there is probably an interesting analogue for permutations, and chances are its truth is an open problem.

To finish, here is a cautionary tale. Let n be even. Some “generatingfunctionology” shows that the number of permutations with all cycles of even length is equal to the number of permutations with all cycles of odd length. I once asked for a bijective proof of this. One was found by Richard Lewis and Simon Norton. It is not hard: pair up the cycles and transfer one point between paired cycles in a systematic way. But it is not a very natural bijection. (For example, it doesn’t respect the action of the symmetric group by conjugation. Indeed, no bijection can do this, since the orbit sizes are different: for n=4, there are 9 elements of each type: with even cycles, 6 single cycles and 3 double transpositions; with odd cycles, 8 elements of order 3 and the identity.)

In some sense, this situation more closely resembles the other strand of the subject, since the ordering of the domain is necessary for constructing the bijection.

Previous | Next