A permutation group challenge

Long ago, in the distant past before the Classification of Finite Simple Groups, Peter Neumann, Jan Saxl and I investigated the class of permutation groups acting on sets of even cardinality n = 2k, with the following interchange property:

Any subset of the domain of size k can be interchanged with its complement by an element of the group.

I don’t remember now exactly what we found out about these groups, but I do remember the very nice argument, based on the character theory of the symmetric group (the next topic for my series, one of these days), that got us started.

So bells began to ring when João Araújo mentioned a property he had considered in connection with transformation semigroups. Again we have a permutation group G acting on 2k points.

The k-subsets of the domain fall into two orbits, so that complementary subsets lie in different orbits.

He had needed to know all the 2-homogeneous groups with this property. Such a group is necessarily primitive, and is very large (of size at least (2k choose k)/2); known order bounds for primitive groups show that only the symmetric and alternating groups and possibly some small exceptions can satisfy the condition.

So I began to wonder if there is a more structural way. Indeed, it turns out that there is.

The character-theoretic argument in this case shows that there is an even integer i < k such that the group is i-homogeneous and has two orbits on j-sets for each j with i < j ≤ k.

If the group fails to be transitive, then it is easy to see that it fixes a point and acts (k−1)-homogeneously on the remaining points. Such groups have been known since long before CFSG: von Neumann and Morgenstern, who posed the problem, attribute the solution to Chevalley, while Wielandt credits Beaumont and Peterson with it. Apart from the symmetric and alternating groups, there are only the affine group of degree 5 and order 20, the group PGL(2,5) of degree 6, and PGL(2,8) and PΓL(2,8) of degree 9. In our case, only the first, third and fourth occur since the degree must be odd.

If the group is transitive, then by the character-theoretic result, it is 2-homogeneous, and so 2-transitive (since the degree is even).

Suppose that it is not 3-homogeneous. Then it has two orbits on 3-sets, which we may distinguish by colouring them red and blue. Since there are also (at most) two orbits on 4-sets, every 4-set contains either i or j red 3-sets, for some i and j. Up to interchange of colours, we have the following possibilities:

  • (i,j) = (3,4). The blue 3-sets are the blocks of a Steiner triple system. This is impossible since such a system has an odd number of points.
  • (i,j) = (2,4). The blue 3-sets form a “regular 2-graph” containing no 4-clique, and some easy combinatorics shows that we must have the group PSL(2,5), degree 6. (The term “regular 2-graph” is used here in the sense introduced by Graham Higman, not the usage in hypergraph theory: see Don Taylor’s paper in Proceedings of the London Mathematical Society in 1977, or several surveys by Jaap Seidel.)
  • (i,j) = (1,4). A 4-set containing two red 3-sets is entirely red, so the red cliques are the lines of a Steiner system. But then a 4-set consisting of two points on each of two concurrent lines has all its 3-sets blue.
  • (i,j) = (0,4). This is impossible since there must be a red and a blue 3-set meeting in two points.
  • (i,j) = (1,3). This is excluded by a simple parity argument.

So, with the one exception PSL(2,5), the group is 3-homogeneous, hence 4-homogeneous, hence 4-transitive (by Kantor’s classification, since the exceptions have odd degree). Note that, up to this point, CFSG has not been used.

Now we can invoke CFSG to show that the only 4-transitive groups are symmetric, alternating, and Mathieu groups, all of which contain elements interchanging some k-set with its complement.

The challenge is:

Complete the analysis without using CFSG!

I feel that it is worth keeping in mind problems like this, which are to be solved without CFSG. If nothing else, the combinatorial techniques used above (especially regular 2-graphs) should not be forgotten!

About these ads

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems and tagged , , , . Bookmark the permalink.

One Response to A permutation group challenge

  1. There is a simpler way to finish the argument, if anything using CFSG can be described as “simpler”. The only 4-homogeneous groups of even degree other than symmetric and alternating groups are the Mathieu groups of degrees 12 and 24; each of them is 5-homogeneous but not 6-homogeneous. There is no need to actually find a k set interchanged with its complement by either of these groups!

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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