## Imprimitive permutations in primitive groups

Asymptotics of permutation counts is a subject with a long history. The result that the proportion of permutations which are derangements (that is, have no fixed points) is very close to 1/e is one of the oldest results in enumerative combinatorics. Results on inversions, descents, and similar counting problems were studied by McMahon in the early 20th century. Erdős and Turán published a sequence of papers in the mid-20th century on “statistics of permutations”, with many results about their order and so forth.

One of my very favourite results in this area is the paper of Łuczak and Pyber, according to which almost all permutations in the symmetric group Sn (a proportion tending to 1 as n→∞) have the property that they are contained in no proper transitive subgroup of Sn except possibly the alternating group An. Their estimate of the rate of convergence was some way from the truth; but, as a result of subsequent work of Diaconis, Fulman and Guralnick, and of Eberhard, Ford and Green (the last of which Ben Green talked about in Singapore in May, and I discussed here), we know much more now, indeed, everything except the constant.

I want to talk about a different aspect of a very similar problem. This is discussed in a paper by João Araújo, his son Little João (or, more properly, João Pedro), Ted Dobson, Alexander Hulpke, Pedro Lopes, and me, which has just gone on the arXiv. (How was such a team assembled? Don’t ask me; I was the next to last recruited!)

A permutation fails to have the Łuczak–Pyber property if and only if it is contained in a maximal transitive subgroup of Sn other than An or in a maximal transitive subgroup of An. Now this transitive subgroup may be primitive or imprimitive. The primitive subgroups are hardest to describe (to say anything serious about them we need the Classification of Finite Simple Groups); but, ironically, the same Classification has the consequence that there are not too many of them, they are small, so that asymptotically they “catch” rather few elements of Sn. On the other hand, the maximal imprimitive subgroups are easily described; they are just the stabilisers of uniform partitions, and are wreath products of symmetric groups whose degrees multiply to give n.

Of course, group-theoretic properties like these are invariant under conjugation, and so depend only on the cycle structure of the permutation. So in principle we can look at a partition of n and decide whether a permutation with that cycle structure is contained in a particular kind of subgroup. For example, let us say that a permutation is imprimitive if it is contained in an imprimitive subgroup of Sn (without loss, a maximal one), and primitive otherwise. Now one can write down necessary and sufficient conditions for a permutation to be imprimitive, and can give an algorithm to test a partition of n for this property. This is described in the paper.

The interesting and possibly surprising thing is that there are primitive groups which are made up of imprimitive permutations. (The reverse is impossible; if a transitive group contains a primitive permutation, then the group is primitive.) The smallest example of such a group is the permutation group A6 acting on the 15 2-element subsets of {1,…6}. Apart from the identity, its elements have cycle structures [2,2,2,2,2,2,1,1,1], [4,4,4,2,1], [3,3,3,3,3], [3,3,3,3,1,1,1] and [5,5,5]. It is an easy exercise to show that each type fixes a partition into either 3 sets of 5 or 5 sets of 3 (or both).

How can one construct lots of examples of such groups? There are a couple of strategies that work well.

• The permutation character (the function giving the number of fixed points of elements) determines the cycle structures of all the elements. So if a group has two transitive actions with the same permutation character, one primitive and one imprimitive, then the primitive action is composed of imprimitive permutations. Helmut Wielandt asked whether this is possible; examples are not easy to come by. Guralnick and Saxl found an infinite family in the exceptional groups of type E8, and Breuer found a sporadic example in the Janko group J4.
• If a primitive group is the union of imprimitive subgroups, then all its elements are imprimitive. One way to do this is using the product action of the wreath product of two groups H and K, where H is primitive but not cyclic of prime order, and K is transitive. So if K is a union of intransitive subgroups, then the wreath product will have the property we are looking for. But any non-cyclic regular group is a union of intransitive subgroups!
• There are primitive groups which have imprimitive subgroups of index 2. For such a group, at least half the elements are imprimitive, and it may not be too hard to check the rest of the elements.

There are also a number of more-or-less ad hoc constructions.

Of course there is more in the paper: take a look!