Regular polytopes, 3

Lunch at Strata Cafe

In the last two posts on regular polytopes, I gave away something about my method of working. Although I have known about regular polytopes for a long time, I have never attempted to do research on them before. I find the best way to start on a new project like this is to explain it to myself, and I took the opportunity of posting my explanations in case they were helpful to others.

Anyway, the attempt worked: during my time in Auckland (now, alas, over), Dimitri Leemans and I did make some progress on this. I would like to explain now what we did, in context: I will begin by describing what Dimitri and his co-authors Maria Elisa Fernandes and Mark Mixer did, and then go on to our new results and how they fit in.

By the way, the weather wasn’t always as pleasant as in the photo above!

Regular polytopes and string C-groups

To begin with a reminder: a regular polytope whose automorphism group is a group G is equivalent to an expression for G as a string C-group of rank d: this means that G is generated by d involutions (elements of order 2), say ρ0, … ρd−1 with the properties

  • (string property) if |ij| > 1, then ρi and ρj commute;
  • (intersection property) If GI denotes the subgroup generated by the involutions ρi for iI, then GIGJ = GIJ for any two sets I and J.

This can be rephrased as follows: the map IGI from subsets of {0,…d−1} which takes each subset to the subgroup generated by the corresponding involutions is an embedding of the Boolean lattice of rank d into the subgroup lattice of G, with the properties that the atoms map to subgroups of order 2 and the rank 2 elements corresponding to non-consecutive indices map to subgroups of order 4.

Note that we do not insist that adjacent involutions fail to commute. (If they do commute, then the polytope is in a certain sense “degenerate”, for example, a face might have just two vertices and two edges.)

The diagram associated with the string C-group has vertices labelled 0,…d−1, two vertices joined if the corresponding involutions do not commute. It is thus a subgraph of the “string” with consecutive pairs joined. Missing edges correspond to neighbouring involutions which commute.

An advantage is that, if the diagram is not connected, then the group is the direct product of the subgroups corresponding to the connected components; so for classification problems we can restrict to the connected case.

The main benefit of this convention is that it is ideal for induction: any subset of the generators of a string C-group themselves generate a string C-group.

The basic question we want to address is:

Problem: Given a group G, what can be said about the regular polytopes with automorphism group G, and in particular, what is the maximal rank of such a polytope, and what polytopes have rank equal to or close to this bound?

It follows from what was said earlier that, if the group G is not decomposable as a direct product, then the diagram must be connected.

Previous work of Fernandes, Leemans and Mixer

The symmetric group Sn

A very natural group to start with is the symmetric group Sn. This is the automorphism group of the regular (n−1)-simplex: the equilateral triangle for n = 3, the regular tetrahedron for n = 4, and so on. In this case, the involutions are the Coxeter generators for the symmetric group: ρi is the transposition (i+1,i+2) for i = 0,…n−2.

The generators of a string C-group form an independent set in the group: none lies in the subgroup generated by the others. As I explained, Julius Whiston showed that an independent set in Sn has cardinality at most n−1, and Philippe Cara and I showed that a string C-group is obtained only in the case when the elements are the Coxeter generators. So the regular (n−1)-simplex is the only regular polytope of rank n−1 with automorphism group Sn.

Leemans and his co-authors found a remarkable extension of this result, which is not yet published; Dimitri gave me a preprint of the paper to learn about what they had been doing at the start of my time in Auckland.

Fernandes and Leemans proved that, for n ≥ 7, there is a unique polytope of rank n−2 with automorphism group Sn. The three authors conjecture a wide generalisation of this:

Conjecture: There is a function f on the positive integers with the property that, if n ≥ 2k+3, then there exactly f(k) distinct polytopes of rank nk with automorphism group Sn.

They proved the conjecture for k = 3,4, with f(3) = 7 and f(4) = 9. Computation suggests that f(5) = 35. I am sure you find these numbers as intriguing as I do!

The alternating group An

Fernandes, Leemans and Mixer constructed regular polytopes of rank ⌊(n−1)/2⌋ with automorphism group An, and conjecture that this is best possible when n > 11. (For n = 11, there are rank 6 polytopes.)

Further progress

From the earlier comments about induction, it is clear that if we have a regular polytope whose automorphism group is Sn or An (equivalently an expression for either of these groups as a string C-group), then any subset of the generators will give a string C-group which is a subgroup of Sn.

So, to attack either of the questions above, we must look more generally at expressions for arbitrary subgroups of Sn as string C-groups.

Primitive groups not containing An

We know that primitive groups not containing the alternating group have small order. This can be proved without the Classification of Finite Simple Groups, but the strongest results are obtained using CFSG. The best result is that of Attila Maróti. Such a group satisfies one of the following:

  • G is a symmetric or alternating group Sm or Am acting on k-subsets of {1,…m} (with degree (m choose k)), or contained in the wreath product of such a group with Sl in its product action (with degree (m choose k)l).
  • G is a Mathieu group in its natural action.
  • There is an explicit upper bound for |G|, which implies in particular that |G| ≤ n1+log n (logs to base 2).

We can make strong statements in each case.

In the first case, we can replace the given action of G on n points by an action on a much smaller set (either G is Sm or Am acting on m points, or in the wreath product case we can take the imprimitive action of G on ml points). In the first case we use induction; in the second, use the analysis of imprimitive groups below to bound the rank.

The Mathieu groups are handled by direct computation. (Dimitri has a Magma program which will find all polytopes with a given, not too huge, group as automorphism group.)

In the third case, we confront the upper bound above with any one of several lower bounds:

  • By Lagrange’s Theorem, a group whose subgroup lattice embeds the Boolean lattice of rank d has order 2d. Marston Conder has shown that, if the diagram is connected, then with a few small exceptions, this can be improved to 22d−1.
  • Our group has a chain of subgroups of length at least d, so must have at least d prime divisors in its order.
  • Taking alternate vertices in the diagram, we find ⌈d/2⌉ commuting involutions; so the group must have an elementary abelian subgroup of order at least 2d/2⌉.

These arguments give bounds much smaller than n/2 for the rank, except in a few small cases.

Transitive but imprimitive groups

Here we were able to find the best possible bound.

If n is even, then the cross-polytopes (the series beginning with the square and the regular octahedron) give examples with rank n/2. I started trying to prove that this case had the largest rank; I failed because there is sometimes a polytope with rank one greater. Our final result reads as follows.

Theorem: A regular polytope whose automorphism group is a transitive but imprimitive subgroup of Sn has rank at most 1+n/2; equality is realised only if n is congruent to 2 (mod 4), in which case there is a unique polytope with this rank.

Towards the alternating conjecture

These arguments show that, in order to prove the conjectured upper bound for the rank of regular polytopes with group An, we can suppose that the “maximal parabolic” subgroups (generated by all but one of the involutions) are subgroups of Sn consisting of even permutations, so our analysis above applies. Moreover, such a subgroup, if transitive, is imprimitive (except in small cases).

We spent some time looking at the two-orbit case. Suppose the orbit lengths are n1 and n2. An ingenious argument due to Dimitri shows that, if the group on the first orbit is the symmetric group, then its rank is at most about half its degree. A similar statement holds if it is alternating (by induction), primitive (and usually we can do much better), or transitive imprimitive (by our theorem). So we are quite close to being able to prove the conjecture!

That is enough for now, I think.


About Peter Cameron

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

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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.