Oligomorphic Permutation Groups

In 1988, there was an LMS Durham symposium on model theory and groups. I had been developing the theory of oligomorphic permutation groups for some time: these are the permutation groups G on Ω with the property that the number of G-orbits on Ωn is finite for all natural numbers n. I spoke about these at the meeting. Subsequently it turned out that there would be no proceedings of the meeting; so, when I wrote up the notes of my lectures, I felt free to incorporate interesting bits from other speakers’ talks into my own account. In this way it became a sort of de facto proceedings.

It was written in rather a hurry, and it shows. But when I took my copy down from the shelf last week, I found in it a few notes about possible changes that might be made in a second edition, if there were ever to be one. Needless to say, there was no second edition, and now we have reached the point where the subject has moved on in some directions (much less so in others) and rather than a second edition there would need to be a complete rewrite.

I have returned to the topic on several occasions, most recently for the proceedings of Groups St Andrews 2005. I have not, however, produced a monograph-length account, and maybe never will. In lieu of such a thing, I have decided to post my rather brief notes for the revision with the oddments on the Lecture Notes page. If you look at them, you may be disappointed (as I was) at how modest my ambitions were back then (but it was only shortly after the original was published).

In brief: an oligomorphic group should probably be regarded as a species, and the numbers of orbits on ordered n-tuples of distinct elements and on n-element subsets of the domain coincide with the sequences counting, respectively, labelled and unlabelled structures in the species. Moreover, the “modified cycle index” of an oligomorphic group is the cycle index of the species.

What distinguishes the species of oligomorphic groups from the general case? In terms of the counting sequences above, two special features of the group case are that the sequences grow rapidly and smoothly. On the first point, the best result is still Macpherson’s Theorem, according to which, if G is primitive (that is, it is transitive and preserves no non-trivial equivalence relation), then either the number of orbits on n-sets is 1 for all n (the group is highly homogeneous), or the number grows at least exponentially. What is lacking to date is a proof of the conjecture that the exponential constant cannot be smaller than 2. The best known result is by Francesca Merola, giving a lower bound of about 1.324.

On smoothness, it is known that the sequence counting orbits on n-sets is the Hilbert series of a graded algebra, and the most significant result is that of Maurice Pouzet: if the group G has no finite orbits, then the algebra has no zero-divisors. (It takes a little imagination to see this as a smoothness result for the rate of growth, but it can be done.)

So these are some of the additions which I would now put on a list, in the hope that sometime in the future I might get round to it …


About Peter Cameron

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

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