Polynomially bounded orbit counts

The best news I had yesterday was an email from Justine Falque with a link to a paper that she and Nicolas Thiéry have just put on the arXiv. The 12-page document is only the “short version”, and a longer paper with complete proofs will appear at some point. Nevertheless, there is enough here to persuade me that they have solved the problem (open since the 1970s) with appropriate tools, and have a very nice result.

A permutation group G, acting on the infinite set X, is said to be oligomorphic if the number of orbits of G on the set of n-element subsets of X is finite for all natural numbers n.

The first case to think about is that where the number of orbits is 1 for all n, in other words, the group is highly homogeneous (or highly set-transitive). Such groups were the subject of my first theorem about infinite permutation groups, answering a question posed by John McDermott. Either such a group preserves or reverses a linear or circular order on X, or it is transitive on ordered n-tuples for all n (that is, it is highly transitive). In fact, there is no need to worry about the complexities of uncountable sets or proper subgroups with the same degree of transitivity: the downward Löwenheim–Skolem theorem guarantees that anything that can happen happens on a countable set, and by taking the closure in the topology of pointwise convergence we need only deal with five very specific groups.

The next step might be to investigate the case where the number of orbits has polynomial growth, that is, is bounded by a polynomial in n. To simplify matters, let us assume that G acts transitively on X. At the time, I was aware that certain imprimitive groups (groups preserving partitions of X) would give examples. For example, take the group preserving all partitions of X into k infinite blocks. The orbit of an n-set is determined by the sizes of its intersections with these blocks, and so the number of orbits is the number of partitions of n into at most k parts; this grows like a polynomial of degree k−1. Also, the group preserving a partition of X into parts of size k has the number of orbits on n-sets equal to the number of partitions of n into parts of size at most k. Duality of partitions (corresponding to transposing the Ferrers diagram) shows that these numbers are equal.

The summer before Dugald Macpherson started work on his DPhil under my supervision, I suggested that he might like to consider whether there could be a primitive group with polynomial growth. This was motivated by a construction I had devised. We can describe the orbit structure on finite sets for an oligomorphic group by a graded algebra. Let Vn be the vector space of G-invariant functions from the set of n-element subsets of X to our favourite field of characteristic zero. The dimension of Vn is equal to the number of orbits on n-sets. We can make the direct sum of these spaces into a graded algebra as follows. Given f in Vn and g in Vm, define fg to be the function in Vn+m as follows: Let L be an (n+m)-set. To evaluate (fg)(L), for each n-subset K of L, we multiply f(K) by g(L\K); then sum over all choices of K. This algebra is commutative and associative, and has an identity. If it were finitely generated, then the dimensions of the homogeneous components Vn would be bounded by a polynomial in n.

By the end of the summer, Dugald had solved this problem: If G is primitive, then either it is highly homogeneous, or the orbit counts grow at least fractional-exponentially (like the unrestricted partition function). Subsequently he improved the growth rate in the second case to straight exponential.

What was left open was a precise description of the growth in the polynomially bounded case. This is what Falque and Thiéry have now produced. In a beautiful piece of work, they have shown that, if the orbit numbers are polynomially bounded, then the graded algebra constructed above is Cohen–Macaulay, a strong ring-theoretic property which implies that the Hilbert series (the generating function for the orbit numbers) has a very simple form: it is a rational function whose numerator is a polynomial with non-negative integer coefficients and whose denominator is a product of factors of the form (1−xa) for various a.

Falque and Thiéry remark that this is just a step towards a complete classification of permutation groups with polynomial growth for the orbit counts. But certainly an important step.

So the behaviour of the two examples I gave earlier, where the Hilbert series is 1/((1−x)(1−x2)…(1−xk)), is not just a special case, but is typical of the general situation.

So what next? Here are two questions which occur to me.

  1. If G is transitive and oligomorphic, then any chain of blocks of imprimitivity is finite, and in the polynomial growth case there is at most one infinite “gap” in such a chain (since, if there were two, we could encode partitions of integers). What if we allow two infinite gaps: is it possible to describe what happens? The natural restriction on growth rates would be just below exponential (the growth for the iterated wreath product of three symmetric groups is faster than any fractional exponential but below straight exponential.)
  2. A big open question which will probably require quite different techniques: what can be said about the spectrum of exponential constants for growth rates of primitive groups? The best lower bound is about 1.324 by Francesca Merola; but very little else is known!

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.

2 Responses to Polynomially bounded orbit counts

  1. Aaron Dall says:

    Very nice! One quick question: In the description of the algebra is the line “To evaluate (fg)(L), for each n-subset k of L, we multiply f(K) by g(L\K); then sum over all choices of L.” correct. It seems like it should read “To evaluate (fg)(L), for each n-subset K of L, we multiply f(K) by g(L\K); then sum over all choices of K.” Or am I missing something?

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 )

Google photo

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