Aspects of cofinitary permutation groups

Peter J. Cameron

School of Mathematical Sciences Queen Mary and Westfield College Mile End Road London E1 4NS U.K.

Abstract A permutation group is cofinitary if any non-identity element fixes only finitely many points. In this article, I discuss two aspects of the theory of cofinitary permutation groups, one topological, the other combinatorial. Several open problems are included.

1 Introduction

A permutation group is cofinitary if any non-identity element fixes only finitely many points. A cofinitary permutation group is bounded if there is an integer m such that non-identity elements fix at most m points; it is unbounded otherwise. Every finite permutation group is cofinitary and bounded; for the most part, we assume that the degree is infinite.

I have written a more extensive survey of cofinitary permutation groups [6] to appear elsewhere. In this article, I concentrate attention on two aspects of their theory.

The first concerns the topology of pointwise convergence. It is known that a subgroup of the symmetric group is closed in this topology if and only if it is the automorphism group of some first-order structure (or, indeed, of some relational structure). Any bounded cofinitary group is discrete and hence closed. Not every closed cofinitary group is discrete; but, following a suggestion of David Evans, I conjecture that all such groups are locally compact. Examples are known, none more than 3-transitive.

The final section concerns bounded groups. This describes an attempt to extend an old result of Blichfeldt [2] for finite permutation groups to the infinite. It is necessary to change the hypotheses slightly; an even earlier paper of Maillet [10] provides the clue. This also ties up with the so-called ibis groups [8], a generalisation of geometric groups. Some questions about these groups remain unsolved even in the finite case.

2 Locally compact cofinitary groups

Let Ω be an infinite set. The topology of pointwise convergence on the symmetric group Sym(Ω) is specified by taking the point stabilisers of all finite tuples as a basis of neighbourhoods of the identity. This topology is totally disconnected. If Ω is countable, it arises from a metric. See [3] or [6] for further discussion.

Let G be a permutation group on Ω, a subgroup of Sym(Ω). As remarked in the introduction, G is closed in the induced topology if and only if G is the full automorphism group of a relational structure on Ω. In general, this structure will include relations of arbitrarily large arity. (The forward implication is shown by constructing the canonical relational structure for an arbitrary permutation group G, which has an n-ary relation for each orbit of G on n-tuples, for all positive integers n: the automorphism group of this structure is the closure of G.)

The group G is discrete if and only if there is some finite tuple whose pointwise stabiliser is the identity. Now it is not hard to show that, if there is an n-tuple whose stabiliser is trivial, then G is the automorphism group of a relation of arity 2n + 2; this bound can be reduced by the degree of transitivity of G (see [5]).

Now any bounded cofinitary group satisfies the above condition, and hence is discrete. However, there exist discrete cofinitary groups which are not bounded. The simplest example is a group with two orbits on each of which it acts faithfully as a cofinitary group, one bounded and the other unbounded. In [6], a construction technique is given for groups with arbitrary degrees of transitivity which are discrete and cofinitary but unbounded.

At the other extreme, in some sense, lie the compact groups. A permutation group is compact if and only if it is closed and all its orbits are finite. If a group of countable degree has these properties, then it has another action as a compact cofinitary group of countable degree. The groups which have such actions are precisely the profinite groups; and the topology induced from the topology of pointwise convergence in the symmetric group coincides with the profinite topology. (On the other hand, a cofinitary permutation group with all orbits finite cannot have uncountable degree, unless it is finite and all but finitely many of its orbits are regular.)

The natural class of topological groups including both discrete and compact groups consists of locally compact groups. A permutation group is locally compact if and only if it is closed and there is a finite tuple whose stabiliser has all orbits finite. Examples of such groups (which are neither discrete nor compact) do exist. Indeed, there are t-transitive groups with all t-point stabilisers compact for t ≤ 3. An example for t = 3 follows; for smaller values of t, take the stabiliser of one or two points in this example.

Let F be a field, and let G = PΓL(2, F) denote the group of permutations of the projective line PG(1, F) = F ∪ {∞} of the form

z ↦ \frac{az^{σ} + b}{cz^{σ} + d}

for a, b, c, d ∈ F, ad − bc ≠ 0, σ ∈ Aut(F). As is well known, this group is 3-transitive; the stabiliser of the three points ∞, 0 and 1 is Aut(F), which is closed, so that G itself is closed. If F is algebraic over its prime field, then every element of F lies in a finite orbit under Aut(F) (the set of its algebraic conjugates), and so G is locally compact. Now, if an element of G fixes ∞, 0 and 1, then its fixed point set is the projective line over a subfield of F. So, if every proper subfield of F is finite (that is, if F = ⋃_{n≥0} GF(r^{p^{n}}), where r and p are primes), then G is cofinitary.

Three open problems which arise from this discussion are:

(a) Is it true that every closed cofinitary permutation group is locally compact?

(b) Does there exist a locally compact cofinitary group which is more than 3-transitive?

(c) In particular, does there exist a cofinitary group which is t-transitive and has the property that the stabiliser of t points is compact, for t > 3?

In connection with problem (c), recall the theorem of Yoshizawa [12]:

Theorem 2.1 A t-transitive permutation group of infinite degree in which the stabiliser of t points is finite can exist only for t ≤ 3.

This implies that a group satisfying the conditions of problem (c) above must have countable degree. (As we observed earlier, a compact cofinitary group of uncountable degree is finite.)

3 Sharp groups and ibis groups

The paper [8] begins the study of a subclass of the bounded cofinitary groups, the so-called ibis groups. The name is an acronym for ‘Irredundant Bases of Invariant Size’. A base for a permutation group is a sequence of points whose pointwise stabiliser is trivial; it is irredundant if no point in the sequence is fixed by the pointwise stabiliser of its predecessors. Thus, a permutation group is discrete if and only if it has a finite base. An ibis group is one satisfying the three equivalent conditions of the following result:

Theorem 3.1 For a permutation group with a finite base, the following conditions are equivalent:

(a) all irredundant bases have the same size; (b) the irredundant bases are preserved by re-ordering;

(c) the irredundant bases are the bases of a matroid.

In order to consider these further we take a detour via two old results due to Maillet [10] and Blichfeldt [2]. Let G be a bounded cofinitary permutation group (possibly of finite degree). The type of G is the set of cardinalities of fixed point sets of non-trivial elements of G, and the Maillet type of G is the set of cardinalities of fixed point sets of non-trivial subgroups of G. Both are finite sets of non-negative integers, having the same maximum element; the Maillet type is a superset of the type. For example, the group PGL(2, F) of linear fractional transformations of the projective line over F has Maillet type {0, 1, 2}; its type is {1, 2} if F is quadratically closed, and {0, 1, 2} otherwise. Given a finite set L of non-negative integers, let f_{L}(x) = ∏_{l∈L}(x − l) be the monic polynomial whose simple roots are the elements of L. Now Blichfeldt proved a theorem equivalent to the following.

Theorem 3.2 Let G be a finite permutation group on Ω, with type L. Let n = |Ω|; let f_{L}(x) = ∑_{i=0}^{r} a_{i}x^{i}, where r = |L|; and let m_{i} be the number of orbits of G on Ω^{i}. Then

∑_{i=0}^{r} a_{i}m_{i} = \frac{f_{L}(n)}{|G|}.

In particular,

(a) |G| divides f_{L}(n);

(b) ∑_{i=0}^{r} a_{i}m_{i} > 0.

A group which attains the (equivalent) bounds |G| = f_{L}(n) and ∑_{i=0}^{r} a_{i}m_{i} = 1 is called sharp by Ito and Kiyota [9]. Sharp groups generalize sharply ttransitive groups; but be warned that the term ‘sharp’ has also been used in the literature as a synonym for ‘cofinitary’ (for example, by Adeleke [1]).

Does this result generalise to infinite (bounded cofinitary) groups? Condition (a) is obviously meaningless. Condition (b) makes sense, but unfortunately turns out to be false (see [6]).

Blichfeldt attributed his theorem to Maillet (he gave a ‘new’ proof using character theory); but in fact Maillet’s result was different, since he used Maillet type. In fact, Blichfeldt’s argument applies if L is replaced by any set of nonnegeative integers which contains the type but doesn’t contain n, in particular, the Maillet type. But the case of equality for the Maillet type has a more precise description:

Theorem 3.3 Let G be a finite permutation group on Ω, with Maillet type L. Let n = |Ω|; let f_{L}(x) = ∑_{i=0}^{r} a_{i}x^{i}, where r = |L|; and let m_{i} be the number of orbits of G on Ω^{i}. Then the following are equivalent:

(a) |G| = f_{L}(n);

(b) ∑_{i=0}^{r} a_{i}m_{i} = 1;

(c) G permutes its irredundant bases transitively.

Groups satisfying these equivalent conditions were called geometric groups by Cameron and Deza [7]; they give rise to ‘permutation geometries’ which are analogues for permutations of the ‘combinatorial geometries’ or matroids. (The original definition was a bit different.) It follows from (c) that any geometric group is an ibis group; the rank of a geometric group is the number of elements in any irredundant base. All finite geometric groups of rank greater than 1 were determined by Maund [11]. (Those of rank 1 are arbitrary finite groups acting regularly on their non-fixed points.) By contrast, finite ibis groups are determined only under strong additional hypotheses [8].

It is also true that, for finite geometric groups, the type and the Maillet type coincide; so these are precisely the sharp ibis groups.

For bounded cofinitary groups, the failure of Theorem 3.2 is repaired by using the Maillet type, as follows.

Theorem 3.4 Let G be a bounded cofinitary permutation group on the infinite set Ω, with Maillet type L. Let f_{L}(x) = ∑_{i=0}^{r} a_{i}x^{i}, where r = |L|; and let m_{i} be the number of orbits of G on Ω^{i}. Then m_{i} is infinite for i > r. If m_{r} is finite, then G is an ibis group with irredundant bases of size r, and ∑_{i=0}^{r} a_{i}m_{i} is the number of orbits of G on irredundant bases. In particular, ∑_{i=0}^{r} a_{i}m_{i} > 0; and this sum is equal to 1 if and only if G is geometric.

In this connection, we have the following result of [4]:

Theorem 3.5 There is no bounded cofinitary group of infinite degree which is geometric of rank 4 or greater.

Problems arising from this discussion include:

(a) Determine the finite ibis groups under suitable hypotheses (for example, those which are transitive and have base size at least 3).

(b) Same question for infinite ibis groups.

(c) In particular, is it true that every infinite geometric group of rank 3 is sharply 3-transitive?

(d) Do Theorems 2.1 and 3.5 have a common generalisation?

References

[1] S. A. Adeleke, Embeddings of infinite permutation groups in sharp, highly transitive, and homogeneous groups, Proc. Edinburgh Math. Soc. 31 (1988), 169–178.

[2] H. F. Blichfeldt, A theorem concerning the invariants of linear homogeneous groups, with some applications to substitution groups, Trans Amer. Math. Soc. 5 (1904), 461–466.

[3] P. J. Cameron, Oligomorphic Permutation Groups, London Math. Soc. Lecture Notes 152, Cambridge University Press, Cambridge, 1990.

[4] P. J. Cameron, Infinite geometric groups of rank 4, Europ. J. Combinatorics, 13 (1992), 87–88.

[5] P. J. Cameron, Bases in permutation groups, pp. 181–198 in Automorphisms of First-Order Structures (ed. R. Kaye and H. D. Macpherson), Oxford University Press, Oxford, 1994.

[6] P. J. Cameron, Cofinitary permutation groups, Bull. London Math. Soc., to appear.

[7] P. J. Cameron and M. Deza, On permutation geometries, J. London Math. Soc. (2) 20 (1979), 373–386.

[8] P. J. Cameron and D. G. Fon-Der-Flaass, Bases for permutation groups and matroids, Europ. J. Combinatorics, to appear.

[9] T. Ito and M. Kiyota, Sharp permutation groups, J. Math. Soc. Japan 33 (1981), 435–444.

[10] L. Maillet, Sur quelques propriétés des groupes de substitutions d’ordre donnée, Ann. Fac. Sci. Toulouse, 8 (1895), 1–22.

[11] T. Maund, D. Phil. thesis, Oxford University, 1989.

[12] M. Yoshizawa, On infinite four-transitive permutation groups, J. London Math. Soc. (2) 19 (1979), 437–438.