12160

12160 is an interesting number; but I didn’t know that until last night.

As part of the work on semigroups, we are looking at the following problem.

Given n and k, with n ≥ 2k, suppose that G is a k-homogeneous subgroup of Sn. How many orbits does G have on partitions of {1,…,n} with nk parts?

First, some information. A permutation group is k-homogeneous if it acts transitively on the set of k-element subsets of {1,…,n}. Clearly k-homogeneous is equivalent to (n−k)-homogeneous, hence the restriction n ≥ 2k is sensible.

According to well-known results in permutation group theory (depending on the Classification of Finite Simple Groups), all the k-homogeneous groups with k ≥ 2 are known. For k ≥ 6, the only such groups are the symmetric and alternating groups; and for these, the number of orbits on (nk)-partitions is p(k), the number of partitions of k, independent of n. For the shape of such a partition is obtained by taking a partition of k, extending it with zeros so that it has nk parts, and then adding 1 to each part.

For k = 5, there are only two further groups to consider, the Mathieu groups M12 and M24. Clearly these will have only a finite number of orbits, so again it is true that the number is bounded by a function of k, independent of n. Also, for n = 4, there are only finitely many further groups, though the list is a little bit longer.

For k = 3, there are two infinite families of groups, together with a finite number of further examples. For one of the families (the affine groups over the 2-element field) the number of orbits is bounded independent of the degree; but for the other, it grows as a cubic in n. For k = 2, the situation is similar but even more complicated.

So can we compute the numbers?

My first attempt was to write a little program to generate all the (nk)-partitions of {1,…,n}, and count orbits under the group action. This worked fine up to about n = 12, and in particular showed that for k = 5, the Mathieu group M12 has 30 orbits on 7-partitions. But the program ran out of memory when I tried it on the large Mathieu group.

The second approach was to note that, if a partition of {1,…,n} has nk parts, then the union of the parts of size greater than 1 has a number of points between k+1 and 2k. So I could compute orbits of the group on sets of these sizes; for each orbit, choose a representative, calculate the group induced on it by its setwise stabiliser, and count orbits of this group on appropriate partitions. This involves many orbit counts, but they are of small groups. (For example, for M24, we have groups with degrees from 6 to 10 rather than 24.) This program ran for M24, and showed that it has 77 orbits on 19-partitions.

However, it still ran out of memory for the one remaining group, PΓL(2,32), a 4-homogeneous group of degree 33. It worked fine for sets of sizes 5, 6 and 7, but ran into problems for 8-sets.

So finally I implemented the following rather baroque idea. Start with a list of all the 4-subsets of {5,…,33}. Take the first subset in the list, take its union with {1,2,3,4}, take the orbit of this set under the group, filter out the sets containing {1,2,3,4}, and remove them from the list, until the list is empty. Keep an auxiliary list of the chosen 4-sets during the process, and adjoin {1,2,3,4} to each of them. Now these are orbit representatives for the group on 8-sets, and the rest of the computation is plain sailing.

The final number of orbits turned out to be 12160. (For the other 4-homogeneous groups, they are 5 – for symmetric and alternating groups – 26, 12, 21, 13, 38, and 15.)

Of course, it would be nice to have independent confirmation of this number … I count all the things that need to be counted.
This entry was posted in doing mathematics, exposition and tagged , , . Bookmark the permalink.

3 Responses to 12160

1. Robert Bailey says:

If you find yourself in need of having to enumerate representatives of each orbit of a permutation group on k-subsets, the SetOrbit package of Pech and Reichard might be useful.

2. Robin Chapman says:

Let a finite group $G$ act on a finite set $X$.
The number of orbits of $G$ on $X$ is $\sum_H a_H/|H|$
where $H$ runs through the subgroups of $G$ and $a_H$ is the number of points in $X$ whose stabilizer is $H$.
So if we can find all $a_H$ we can compute the number of orbits.

Let $b_H$ be the number of elements of $X$
fixed by the subgroup $H$.
Then $b_H=\sum_{K\ge H}a_K$. If we can find the $b_H$ we can
compute $a_H$, and so then the number of orbits.

In general, this computation can be quite nasty. The
subgroup lattice of a group can be very complicated, even for
fairly ordinary groups. But this is very practical in the case
where $G=P\Gamma L(2,32)$ and $X$ is the set o $29$-partitions
of $P$, the projective line over $GF(32)$.

Three factors are in our favour in this example. The stabilizer
of an element of $X$ is a subgroup of $G$ with order at
most $8$.
Also for a given $m\le 8$ all subgroups of $G$ with order $m$
are conjugate in $Sym(P)$ (even if not conjugate in $G$) and so $b_H$ depends only on $|H|$. Finally, if $m$, $r\le G$
the number of subgroups $K$ of order $r$ such that $K\ge H$
for a given $H$ of order $m$ only depends on $m$ and $r$.
This is because $G$ has a very simple subgroup structure,
for instance every $2$-subgroup is contained in a unique Sylow
subgroup.

Once we have noticed this, the computation of the number of $G$-orbits on $X$ is now a “back-of-an-envelope” job.
I get $12160$ orbits, just the same as Peter!

• Peter Cameron says:

Yes, and I have to say how relieved I was when Robin came up with the same answer!

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