Some counting problems related to permutation groups

Peter J. Cameron

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

Abstract

This paper discusses investigations of sequences of natural numbers which count the orbits of an infinite permutation group on n-sets or n-tuples. It surveys known results on the growth rates, cycle index techniques, and an interpretation as the Hilbert series of a graded algebra, with a possible application to the question of smoothness of growth. I suggest that these orbit-counting sequences are sufficiently special to be interesting but sufficiently common to support a general theory.

‘I count a lot of things that there’s no need to count,’ Cameron said. ‘Just because that’s the way I am. But I count all the things that need to be counted.’

Richard Brautigan, The Hawkline Monster

1 Three counting problems

This paper is a survey of the problem of counting the orbits of an infinite permutation group on n-sets or n-tuples, especially the aspects closest to algebraic combinatorics. Much of the material surveyed here can be found elsewhere, for example in [4].

We begin by discussing three counting problems in different areas of mathematics and their relations.

1.1 Enumeration of finite structures

A relational structure M consists of a set X and a family of relations on X. These relations can have arbitrary arities, and there may be a finite or infinite number of relations. Many familiar structures have only a single relation:

Preprint submitted to Elsevier Preprint 29 June 1998

graphs, directed graphs, total or partial orders, and so on. However, for a general (non-uniform) hypergraph we would need a k-ary relation for each cardinality k of hyperedges.

The age of M, written Age(M), is the class of all finite relational structures (in the same language) which are embeddable in M. (This terminology was invented by Fraïssé [7], who says that the structure M is younger than N if the age of M is contained in that of N.)

Problem. How many (a) labelled, (b) unlabelled structures in Age(M)?

As standard in combinatorial enumeration, labelled structures are based on the set {1, 2, …, n}; unlabelled structures are isomorphism types.

1.2 Counting orbits

A permutation group G on a set X is oligomorphic if G has only finitely many orbits on X^{n}, for all n: equivalently, on the set of n-subsets of X, or on the set of n-tuples of distinct elements of X. (The term ‘oligomorphic’ suggests ‘few shapes’. We will see later that orbits are often associated with ‘shapes’ of finite substructures of some structure whose automorphism group is G, and ‘few’ is interpreted as ‘only finitely many’. The word ‘oligomorphic’ is also used in computer science to describe viruses which exist in only a few distinct forms and so can be recognised.)

Problem. How many orbits on (a) n-sets, (b) n-tuples of distinct elements,

(c) all n-tuples, does a given oligomorphic group have?

1.3 Types of a first-order theory

Let T be a complete consistent theory in the first-order language L. An n-type over T is a set S of formulae in L with free variables x_{1}, …, x_{n}, maximal subject to being consistent with T. Thus a type encodes everything that can be said (in the first-order language) about n elements in some model of T.

We say that T is ℵ_{0}-categorical if it has a unique countable model (up to isomorphism). This is equivalent to there being only finitely many n-types for each n. This is part of the celebrated theorem of Engeler, Ryll-Nardzewski and Svenonius, about which we shall say more later.

Problem. How many n-types?

[figure: a_{1}; a_{2}; a_{n}; b_{1}; b_{2}; b_{n}]

Fig. 1. Order-automorphism of ℚ

1.4 An example

Let M be the totally ordered set ℚ. Recall Cantor’s Theorem, which asserts that any countable dense totally ordered set with no least or greatest element is isomorphic to ℚ. Since all these properties apart from countability are firstorder, the theory of M is ℵ_{0}-categorical.

The age of M consists of all finite ordered sets: there is one unlabelled structure, and n! labelled structures, on n elements.

Its automorphism group is transitive on n-sets for every n. This is because, given any two n-tuples of rational numbers, each in increasing order, we can find a piecewise-linear order-preserving map taking the first n-tuple to the second (see Figure 1). We also see that there are n! orbits on ordered n-tuples of distinct elements.

An n-type specifies, of each pair of variables, whether they are equal, and, if not, which is greater. So the number of n-types is equal to the number of preorders (reflexive and transitive relations P such that, for all x and y, either P (x, y) or P (y, x) holds) on the set {1, 2, …, n}. This number is

∑_{k=1}^{n} S(n, k)k!

where S(n, k)is the Stirling number of the second kind, since a preorder is specified by an equivalence relation and a total order on its equivalence classes.

1.5 Connections

As the example suggests, there are close connections between the three problems.

A structure M is homogeneous if any isomorphism between finite induced substructures of M can be extended to an automorphism of M. Thus, the

[figure: A_{1}; A_{2}; A; B_{1}; B_{1}; B_{2}; B_{2}; C]

Fig. 2. The Amalgamation Property

ordered set ℚ is homogeneous.

Theorem 1 (Fraïssé’s Theorem) A class C of finite structures is the age of a countable homogeneous structure M if and only if it is closed under isomorphism, closed under taking induced substructures, contains only countably many members up to isomorphism, and has the amalgamation property.

If these conditions hold, then M is unique up to isomorphism.

The amalgamation property asserts that, if two structures B_{1} and B_{1} in C have isomorphic substructures, then they may be embedded in a larger substructure C ∈ C so that the isomorphic substructures coincide (see Figure 2).

We call a class C which satisfies the hypotheses of this theorem a Fraïssé class, and the homogeneous structure M its Fraïssé limit.

Now if M is homogeneous, then the number of orbits of its automorphism group on n-tuples of distinct elements (resp. on n-sets) is equal to the number of labelled (resp. unlabelled) structures in its age.

There is a natural topology on the symmetric group of countable degree (pointwise convergence) with the properties that

(a) a subgroup is closed if and only if it is the automorphism group of a homogeneous relational structure;

(b) the closure of a subgroup is the largest overgroup with the same orbits on X^{n} for all n.

Hence counting labelled/unlabelled structures in a Fraïssé class is equivalent to counting orbits of a permutation group on n-sets/n-tuples of distinct elements.

We turn now to the connection with counting types.

The theorem of Engeler, Ryll-Nardzewski and Svenonius says more than we have seen so far:

(a) for a countable structure M, the theory of M is ℵ_{0}-categorical if and only if Aut(M) is oligomorphic;

(b) if these condition holds, then all n-types are realised in M, and two ntuples realise the same type if and only if they are in the same orbit of Aut(M).

Thus, if T is ℵ_{0}-categorical, counting n-types of T is equivalent to counting orbits of Aut(T) on n-tuples of elements in the unique countable model of T.

Moreover, as we have seen, for any oligomorphic group G, the closure of G is the automorphism group of a homogeneous relational structure, whose theory is ℵ_{0}-categorical.

So the enumeration problem for a Fraïssé class (for which the answer is finite for all n), the orbit-counting problem for an oligomorphic permutation group, and the type-counting problem for an ℵ_{0}-categorical theory, are all ‘equivalent’. We will focus on the orbit-counting version from now on.

2 Three counting sequences

We consider the classes of sequences which can arise in this situation.

2.1 The sequences

Let G be an oligomorphic permutation group on X. Let

• f_{n}(G) = number of G-orbits on n-subsets;

• F_{n}(G) = number of G-orbits on n-tuples of distinct elements;

• F_{n}^{∗}(G) = number of G-orbits on all n-tuples.

Then f_{n} and F_{n} count unlabelled and labelled n-element structures in a Fraïssé class, while F_{n}^{∗} counts n-types in an ℵ_{0}-categorical theory. We take as a convention that the zeroth term in each sequence is 1: there is a single empty set or tuple.

These sequences are, of course, related. We have:

Theorem 2 (a) F_{n}^{∗} = ∑_{k=1}^{n} S(n, k)F_{k}, where S(n, k) is the Stirling number of

the second kind; (b) f_{n} ≤ F_{n} ≤ n! f_{n}.

Thus F determines F^{∗} and vice versa. The series (f_{n}) is more difficult to work with than (F_{n}), but for this reason more interesting. The examples G = S (the symmetric group) and G = A (the group of order-preserving permutations of ℚ) show that equality is possible in each inequality in (b).

The fundamental problem is, Which sequences occur?

Let 𝔣 and 𝔉 be the sets of f- and F -sequences arising from oligomorphic groups. A compactness argument shows that both are closed in the space ℕ^{ℕ} of all integer sequences (in the topology of pointwise convergence). In particular, each of these sets has cardinality 2^{ℵ_{0}}, the same as the whole of ℕ^{ℕ}. So the conditions we are looking for should be local ones!

The first such result is the following.

Theorem 3 For all N ≥ 0, we have F_{n+1} ≥ F_{n} and f_{n+1} ≥ f_{n}.

The first inequality is trivial: each orbit on (n + 1)-tuples is obtained by ‘extending’ a unique orbit on n-tuples. Moreover, equality holds if and only if F_{n} = F_{n+1} = 1 (that is, G is (n + 1)-transitive. The second inequality, however, is much less trivial. Two completely different proofs are known, one using linear algebra and finite combinatorics (we will discuss this later), the other a strengthened version of Ramsey’s Theorem.

For example, if G is the group of order-preserving permutations of ℚ, then we have f_{n} = 1, F_{n} = n!, and

F_{n}^{∗} = ∑_{k=1}^{n} S(n, k)k! .

2.2 Growth rates

Apart from Theorem 3, very few local conditions are known. One of these asserts that, if f_{n} = f_{n+2}, then G has a fixed set of cardinality at most n and acts on the complement as a (n + 2)-set-transitive group (one with f_{n+2} = 1). So, if the sequence (f_{n}) is not ultimately constant, then it grows at least linearly with slope \frac{1}{2}.

We now look at some examples of possible growth rates. First, we define two group-theoretic constructions. Let G_{1} and G_{2} be permutation groups on X_{1} and X_{2}. Then the direct product G_{1} × G_{2} acts on the disjoint union X_{1} ∪ X_{2}: an ordered pair (g_{1}, g_{2}) acts on X_{1} as g_{1} and on X_{2} as g_{2}.

[figure: X_{2}; X_{1}]

Fig. 3. Wreath product

The wreath product is a little more complicated. It acts on X_{1} × X_{2}, which we regard as a covering of X_{2} with all the fibres bijective with X_{1}. The wreath product G_{1} Wr G_{2} is generated by two types of permutation:

• the base group, which fixes each fibre setwise and acts on it as an element of G_{1} (these elements chosen independently);

• the top group, which permutes the fibres as an element of G_{2} acting on X_{2}.

(See Figure 3.) We let S denote the infinite symmetric group, S_{k} the finite symmetric group of degree k, and A the group of order-automorphisms of ℚ.

The following list illustrates some known growth rates.

Polynomial growth. For example, if S^{k} is the direct product of k copies of S, then an orbit of S^{k} on n-sets is specified by giving the number x_{i} of points in the intersection of the n-set with the ith orbit, for i = 1, …, k. So f_{n}(S^{k}) is the

number of choices of k non-negative integers with sum n, which is \binom{n + k − 1}{k − 1}.

This is a polynomial of degree k − 1 in n, with leading coefficient 1/(k − 1)!.

Similarly, f_{n}(S Wr S_{k}) is the number of partitions of n with at most k parts, which is a polynomial of degree k − 1 with leading coefficient 1/(k!(k − 1)!).

Note, in particular, that f_{n}(S Wr S_{2}) = 1 + ⌊n/2⌋. This shows that the result asserting that (f_{n}) is either ultimately constant or at least linear with slope \frac{1}{2} is best possible.

Fractional exponential growth. For example, f_{n}(S Wr S) = p(n), the partition function, which is roughly exp(n^{1/2})). More generally, f_{n}(S WrS WrS_{k}) is very roughly exp(n^{(k+1)/(k+2)}.

It is worth noting that the iterated wreath product of at least three copies of S has the property that (f_{n}) grows faster than any fractional exponential but slower than straight exponential.

[figure]

Fig. 4. Boron trees

Exponential growth. Here there is a wide variety of examples, of which I note three.

• f_{n}(S_{2} Wr A) = F_{n}, the nth Fibonacci number. (This is a simple exercise.)

• Boron trees. A boron tree is a tree in which all vertices have valency 1 or 3. The leaves are hydrogen atoms, and the non-leaves boron atoms, in an imaginary version of hydrocarbon chemistry in which trivalent boron replaces tetravalent carbon. Figure 4 shows the boron trees with at most five leaves. The leaves of a boron tree carry a quaternary relation R(a, b; c, d), which holds whenever the paths ab and cd in the tree are disjoint. The class of such relational structures is a Fraïssé class. The automorphism group of its Fraïssé limit has f_{n} ∼ an^{−5/2}c^{n}, where c = 2.483 · · ·.

• This example will be important later. Let q be a positive integer. Then it is possible to partition ℚ into q pairwise disjoint dense subsets in a unique way up to order-preserving permutations. Any orbit on n-sets is parametrised by a word of length n in an alphabet A with q symbols. (Associate a symbol with each of the q sets; then the word records the sets containing the n points in order.) Thus, if G(q) denotes the group of permutations preserving the order and fixing the q sets, then f_{n}(G(q)) = q^{n}.

Factorial growth. Consider the class of finite sets carrying two independent total orders. Such a set is described by the permutation which takes the first order to the second. Since the structures form a Fraïssé class, we obtain a group with f_{n} = n! . Similarly, by taking k independent orders, we obtain f_{n} = (n!)^{k}.

Another example is the group induced by S on the set of unordered pairs from the original set. For this group, f_{n} is the number of graphs with n edges and no isolated vertices (up to isomorphism). The asymptotics of this sequence appear to be unknown.

Exponential of a polynomial. The most famous example arises as follows. The class of all finite graphs is a Fraïssé class. Its Fraïssé limit is the celebrated countable random graph R discovered by Erdős and Rényi [6]. Thus, f_{n}(Aut(R)) is the number of n-vertex graphs up to isomorphism, which is asymptotically 2^{n(n−1)/2}/n! (since almost all finite graphs have trivial automorphism group).

It is worth observing here that there is no upper bound to the growth rates which can be achieved: it is possible to construct a Fraïssé class of relational structures with any given finite number of k-ary relations for all k, and in which these relations hold only for k-tuples with all elements distinct. If there are a_{k} relations of arity k, and they are independent, then clearly f_{n} ≥ 2^{a_{n}}.

The question is much more interesting over languages with only finitely many relations. It is clear that, for a homogeneous structure over such a language, f_{n} is bounded above by the exponential of a polynomial (precisely, by

2^{n^{k_{1}}+···+n^{kr}} ,

where k_{1}, …, k_{r} are the arities of the relations. It is not clear what happens for arbitrary structures.

However, the most interesting groups and structures (those with the greatest amount of symmetry) are those with the slowest growth rates.

Some restrictions on growth rate are known:

Theorem 4 (a) For homogeneous binary relational structures, either

• c_{1}n^{d} ≤ f_{n} ≤ c_{2}n^{d} (for some d ∈ ℕ, c_{1}, c_{2} > 0), or

• f_{n} grows faster than polynomially.

(b) In the latter case, f_{n} > exp(n^{1/2−ϵ}) for n > n_{0}(ϵ).

The first part is due to Pouzet [14], the second to Macpherson [12]. A much more dramatic result was proved by Macpherson [11] in the case of primitive groups (those which preserve no non-trivial equivalence relation):

Theorem 5 If G is primitive, then either f_{n} = 1 for all n, or f_{n} > c^{n} for all sufficiently large n, where c > 1.

Macpherson’s proof gives c = ^{5} \sqrt{2} − ϵ. Of the earlier examples, only those associated with boron trees are primitive. The slowest growth known for a primitive group is roughly 2^{n−2}/n. We discuss this example later.

2.3 Smoothness

Sequences arising from groups should grow smoothly. In particular, for polynomial growth, log f_{n}/ log n should tend to a limit (and, for growth of degree d in Pouzet’s Theorem, f_{n}/n^{d} should tend to a limit); for fractional exponential growth, log log f_{n}/ log n; for exponential, log f_{n}/n; and so on. How do you state a general conjecture?

(Actually we might expect such smoothness to fail for very rapid growth. As we noted, examples can be constructed of Fraïssé classes with large numbers of k-ary relations. If these numbers grow very irregularly, then probably the numbers of orbits will do so too. We return to this below.)

Another type of question has been considered. We look at the motivation for this question later.

Define an operator S on sequences of natural numbers by the rule that Sa = b if

∑_{n=0}^{∞} b_{n}x^{n} = ∏_{k=1}^{∞}(1 − x^{k})^{−a_{k}}.

Is it true that, if f = Sa counts orbits of a group, then a_{n}/f_{n} tends to a limit (possibly 0 or 1)?

(This question has something to do with smoothness of growth, since, if Sa = b, then b_{n} = a_{n} + F (a_{1}, …, a_{n−1}) for some function F.

3 An algebra

The most immediate connection of the subject of this paper with algebraic combinatorics is that we can define a graded algebra over ℂ with the property that the degree of the nth homogeneous component is f_{n}. This algebra is the topic of the present section.

3.1 Construction

Let X be an infinite set. For any non-negative integer n, let V_{n} be the set of all functions from the set of n-subsets of X to ℂ. This is a vector space over ℂ.

Define

A = ⨁_{n≥0} V_{n},

with multiplication defined as follows: for f ∈ V_{m}, g ∈ V_{n}, let fg be the function in V_{m+n} whose value on the (m + n)-set A is given by

fg(A) = ∑_{{B⊆A \atop |B|=m}} f(B)g(A \ B).

This is the reduced incidence algebra of the poset of finite subsets of X.

If G is a permutation group on X, let A^{G} be the subalgebra of A of the form ⨁_{n≥0} V_{n}^{G}, where V_{n}^{G} is the set of functions fixed by G.

If G is oligomorphic, then dim(V_{n}^{G}) is equal to the number F_{n}(G) of orbits of G on n-sets, since a function is fixed if and only if it is constant on each orbit.

3.2 Integral domain?

The algebra A has any divisors of zero. The characteristic function f of a single n-set satisfies f^{2} = 0. If the group G has this n-set as one of its orbits, then f ∈ A^{G}.

I conjecture that if G has no finite orbits, then A^{G} is an integral domain.

This would have as a consequence a smoothness result for the sequence (f_{n}), in view of the following result:

Theorem 6 Let A = ⨁ V_{n} be a graded algebra which is an integral domain, with dim(V_{n}) = a_{n}. Then a_{m+n} ≥ a_{m} + a_{n} − 1 for all m, n.

In fact, a stronger conjecture can be made. Let e denote the constant function in V_{1} with value 1. Then e ∈ V_{1}^{G} for any permutation group G. It can be shown by finite combinatorial arguments that e is not a zero-divisor. (The inequality f_{n+1}(G) ≥ f_{n}(G) follows: for multiplication by e is a linear map from V_{n}^{G} to V_{n+1}^{G}, and the fact that e is not a zero-divisor shows that its kernel is zero.) I conjecture that if G has no finite orbits, then e is prime in A^{G} (in the sense that A^{G}/eA^{G} is an integral domain). This conjecture also has a consequence for smoothness, namely

(f_{m+n} − f_{m+n−1}) ≥ (f_{m} − f_{m−1}) + (f_{n} − f_{n−1}) − 1,

since the dimension of the nth homogeneous component of A^{G}/eA^{G} is f_{n} − f_{n−1}.

These conjectures are still open after more than twenty years. Recently [5] I proved the following. Call a permutation group G entire if A^{G} is an integral domain, and strongly entire if A^{G}/eA^{G} is an integral domain. (It is easy to see that the second condition implies the first.) We call H a transitive extension of G if H is transitive and the stabiliser of the point x, acting on the points different from x, is isomorphic to G as permutation group.

Theorem 7 Let G be (strongly) entire, and H a transitive extension of G. Then H is (strongly) entire.

3.3 Polynomial algebra?

There are a few cases in which the structure of the algebra A^{G} can be determined. For a simple example, if G = S, the symmetric group, then A^{G} is a polynomial ring in one variable (generated by e). Also, we have

A^{G_{1}×G_{2}} ≅ A^{G_{1}} ⊗_{ℂ} A^{G_{2}},

so that A^{S^{k}} is isomorphic to the polynomial ring in k variables, in agreement with our formula

f_{n}(S^{k}) = \binom{n + k − 1}{k − 1}.

Moreover, if H is a finite permutation group of degree k, then S Wr H is the extension of S^{k} by H, and we see that A^{SWrH} is the ring of invariants of H (thought of as acting as a linear group by permutation matrices). In particular, A^{SWrS_{k}} is isomorphic to the ring of symmetric polynomials in k variables.

The other cases where the structure is known are instances of a general procedure.

Let M be the Fraïssé limit of C, and G = Aut(M). Suppose that the following properties hold:

• there is a notion of disjoint union in C;

• there is a partial order of involvement on the n-element structures in C, so that if a structure is partitioned in any manner, then it involves the disjoint union of the induced substructures on its parts;

• there is a notion of connected structure in C, so that every structure is uniquely expressible as the disjoint union of connected structures.

Theorem 8 Under the above assumptions, A^{G} is a polynomial algebra generated by homogeneous elements. The generators are the characteristic functions of the isomorphism types of connected structures in C.

Now the operator S that we defined earlier on integer sequences plays two roles in this context:

• Let C be a class of structures, each of which is uniquely expressible as a disjoint union of ‘connected’ substructures. Suppose that the sequence a = (a_{n}) enumerates (unlabelled) connected structures in 3matthcalC. Then b = Sa enumerates all unlabelled structures in C.

• Let A be a graded algebra which is a polynomial algebra in homogeneous generators; let the sequence a = (a_{n}) enumerate the generators by degree. Then the sequence b = Sa is the Hilbert sequence of A.

The first fact motivates the question in the earlier section concerning whether a_{n}/f_{n} tends to a limit, where f = Sa and f_{n} = f_{n}(G) for some permutation group G. In the case where the Fraïssé class C satisfies the hypotheses of the above theorem, the question is equivalent to the following: Let p_{n} be the probability that a random n-element structure in C is connected. Does p_{n} tend to a limit as n → ∞? See [1] for more information on the probability of connectedness.

3.4 Examples

Example 9 Let C be any Fraïssé class, M its Fraïssé limit, and G = Aut M. Then, regardless of the structure of A^{G}, it is true that A^{GWrS} is a polynomial algebra, where S is the symmetric group. For an orbit of G Wr S on n-sets is described by a partition of an n-set with a structure from C on each part, and no relation between the parts; the class of such partitioned structures is the Fraïssé class corresponding to G Wr S. Now we interpret ‘connected structure’ to be one in which the partition has just one part; ‘disjoint union’ of structures to mean that points of different constituent structures lie in distinct parts; and ‘involvement’ to be inclusion of all the relations (other than the equivalence relation defining the partition). The axioms for Theorem 8 are satisfied.

The polynomial generators of A^{GWrS} correspond to the orbits of G on nsets, so are enumerated by (f_{n}(G)). We see, incidentally, that the sequence (f_{n}(G Wr S)) is obtained from the sequence (f_{n}(G)) by applying the operator S. This was the reason for the choice of name. In the next section we will generalise this sequence operator.

Example 10 We met the random graph R of Erdős and Rényi. This is the Fraïssé limit of the class of finite graphs. It is the unique countable homogeneous graph R containing all finite graphs. Let G = Aut(R).

If we take the usual graph-theoretic notions of connectedness and disjoint union, and let involvement mean ‘spanning subgraph’, then the axioms before Theorem 8 are satisfied. the algebra A^{G} is a polynomial algebra, whose generators correspond to connected graphs.

The group G has a transitive extension H, which can be described as follows. A two-graph is a collection T of 3-subsets of a set X having the property that any 4-subset of H contains an even number of members of T . The class of finite two-graphs is a Fraïssé class, and the automorphism group of its Fraïssé limit is a transitive extension of G.

This leads to a curious problem. It follows from Theorem 7 that A^{H} is an integral domain (and that e is prime in A^{H}. Is it a polynomial algebra? The best chance of proving this would be to identify a class of ‘connected’ twographs.

Now Mallows and Sloane [13] showed that two-graphs and even graphs (graphs with all valencies even) on n points are equinumerous (but there is no natural bijection). Hence, if A^{H} is a polynomial algebra, then the number of polynomial generators of degree n is equal to the number of Eulerian (connected even) graphs on n vertices.

Example 11 Recall the group G(q) preserving the order on ℚ and q dense subsets which partition ℚ. We have f_{n}(G(q)) = q^{n}, and the orbits of G(q) on n-sets are described by words in an alphabet of length q. Now the nth homogeneous component of A^{G(q)} is spanned by the words of length n. The multiplication is defined on words as follows: the product of two words is the sum (with appropriate multiplicities) of all words which can be obtained by ‘shuffling’ together the two words in all possible ways. For example,

(aab) · (ab) = abaab + 3aabab + 6aaabb.

This is the shuffle algebra, which arises in the theory of free Lie algebras (see Reutenauer [16], which is a reference for what follows).

A Lyndon word is one (like aabab) which is strictly smaller (in the lexicographic order) than any proper cyclic permutation of itself. Now, if we interpret ‘connected’ to mean ‘Lyndon word’, ‘disjoint union’ to mean ‘concatenation in decreasing lexicographic order’, and ‘involvement’ to be the reverse of lexicographic order, then the axioms are satisfied. This says, in essence, that any word can be expressed uniquely as a concatenation of Lyndon words in decreasing lexicographic order (as ab.aab in the example), and that, of all the words obtained by shuffling Lyndon words together, the greatest is the concatenation in decreasing lexicographic order. We conclude that the shuffle algebra is a polynomial algebra generated by the Lyndon words. This is a result of Radford [15].

Now we get a puzzle similar to that in the last case: it turns out that the groups G(q) have transitive extensions H(q) (so that H(q) is strongly entire, by Theorem 7), but it is unknown whether A^{(}H(q)) is a polynomial algebra. Here are some further details on the case q = 2.

The Fraïssé class corresponding to H(2) consists of what have been called local orders, locally transitive tournaments, or vortex-free tournaments by authors in very different areas: permutation groups [3], model theory [10], and computational geometry [9]. These are tournaments which contain neither a 3-cycle dominating a vertex, nor a 3-cycle dominated by a vertex, as induced sub-tournaments. The Fraïssé limit can be described as follows. Choose a countable dense set on the unit circle with the property that it contains no two antipodal points. (If we choose one of each antipodal pair of complex roots of unity at random, then with probability 1, the resulting set is dense.) Now an arc joins x to y if the angular distance from x to y (in the anticlockwise direction) is smaller than that from y to x.

The number f_{n}(H(2) of n-vertex tournaments with this property, up to isomorphism, is given by

\frac{1}{2n} ∑_{{d|n \atop d odd}} ϕ(d)2^{n/d}.

From this, by applying the inverse of the operator S, it is possible to calculate the hypothetical sequence enumerating the polynomial generators (assuming that the algebra is polynomial). The sequence, which begins 1, 0, 1, 0, 2, 1, 4, 4, 12, 15 …, appears to be unknown.

Note that f_{n}(H(2)) ∼ 2^{n−1}/n. If we use instead the group H^{∗}(2) of automorphisms and anti-automorphisms of the tournament (where an anti-auto-morphism reverses all arcs), we see that f_{n}(H^{∗}(2)) ∼ 2^{n−2}/n. This is the example, promised earlier, of a primitive group with slowest known growth rate.

4 Cycle index

The class of oligomorphic groups appears to be the largest class of infinite permutation groups to which the theory of cycle index for finite permutation groups can be naturally extended. This has been adequately discussed elsewhere, so only a sketch will be given here. The challenge is to connect this material with the algebra of the last section.

4.1 Definition and properties

We begin with a brief recall of the cycle index of a finite permutation group. Let c_{i}(g) denote the number of cycles of length i in the cycle decomposition of g, where g is a permutation of a finite set of cardinality n. Then the cycle index of g is

z(g) = s_{1}^{c_{1}(g)}s_{2}^{c_{2}(g)} ⋯ s_{n}^{c_{n}(g)},

a monomial in the indeterminates s_{1}, …, s_{n}. If G is a group of permutations of a set of n elements, its cycle index is the average cycle index of its elements:

Z(G) = \frac{1}{|G|} ∑_{g∈G} z(g).

Clearly there is no hope of extending this definition to an infinite permutation group. However, if G is oligomorphic, we can proceed as follows. Choose representatives for the orbits of G on finite sets. Let G(Δ) denote the group of permutations of Δ induced by its setwise stabiliser in G. Then we define the modified cycle index of G by

Z̃(G) = ∑ Z(G(Δ)),

where the sum is over the orbit representatives. This is well-defined: for a monomial s_{1}^{a_{1}} ⋯ s_{n}^{a_{n}} occurs only in the summands G(Δ) for which

∑ ia_{i} = |Δ|,

and there are only finitely many of these, since G is oligomorphic. The result is a formal power series in infinitely many indeterminates. (By convention, we take the cycle index of a ‘permutation group on the empty set’ to be 1.)

If it happens that G is the automorphism group of a homogeneous structure M, then Z̃(G) is the sum of the cycle indices of the automorphism groups of the unlabelled structures in the age of M. This agrees with Joyal’s definition of the cycle index of a species [8].

This definition works equally well if G is a finite group. But in this case, we get nothing new: it can be shown that

Z̃(G) = Z(G; s_{i} ← s_{i} + 1).

(We use the notation F (s_{i} ← t_{i}) for the result of substituting t_{i} for s_{i} in the polynomial or formal power series F.) In this sense, then, our modified cycle index is a genuine extension of the cycle index of a finite group.

The next three results summarise the behaviour of the modified cycle index under group-theoretic constructions, how we obtain the counting sequences (f_{n}(G)) and (F_{n}(G)) as specialisations, and the modified cycle index of some special groups. As is usual in combinatorial enumeration, we represent the sequence (f_{n}(G)) (which counts unlabelled structures) by the ordinary generating function f_{G}(x) = ∑_{n≥0} f_{n}(G)x^{n}, and the sequence (F_{n}(G)) (which counts labelled structures) by the exponential generating function F_{G}(x)) = ∑_{n≥0} F_{n}(G)x^{n}/n!. As earlier, S is the infinite symmetric group and A the group of order-preserving permutations of ℚ.

Proposition 12 (a) Z̃(G × H) = Z̃(G)Z̃(H).

(b) Z̃(G Wr H) = Z̃(H; s_{n} ← Z̃(G; s_{m} ← s_{mn}) − 1).

(c) If H is a transitive extension of G, then Z̃(G) = ∂Z̃(H)/∂s_{1}.

Proposition 13 (a) f_{G}(x) = Z̃(G;_{n} ← x^{n}).

(b) F_{G}(x) = Z̃(G; s_{1} ← x, s_{n} ← 0 for n > 0).

Proposition 14 (a) Z̃(S) = exp (∑_{n≥1} \frac{s_{n}}{n} ).

(b) Z̃(A) = 1/(1 − s_{1}).

4.2 Sequence operators

From Propositions 12 and 13, we see that (f_{n}(G Wr H)) is determined by (f_{n}(G)) and the modified cycle index of H. We can define an operator associated with any oligomorphic group H (which will also be denoted by H) formally, as follows: if a = (a_{n}), then Ha = (b_{n}), where, setting a(x) = ∑ a_{n}x^{n} and b(x) = ∑ b_{n}x^{n}, we have

b(x) = Z̃(H; s_{n} ← a(x^{n}) − 1).

Thus, S is the operator we met earlier, while we see from Proposition 14 that Aa = b means

b(x) = \frac{1}{2 − a(x)}.

Now the earlier question about the probability of connectedness can be generalised: Is it true that, for any oligomorphic group H, if Ha = b and the sequence b is realised by some oligomorphic permutation group, then a_{n}/b_{n} tends to a limit as n → ∞?

Bernstein and Sloane [2] discuss a number of operators on sequences. Among their list are S and A (which they refer to as EULER and INVERT respectively). They do not consider any other operators of the above form.

Other sequence operators could be defined from groups. Here are two examples:

• For a fixed oligomorphic group H, we could consider the operator which takes (f_{n}(G)) to (f_{n}(G × H). By Propositions 12 and 13, this is just the convolution with the sequence (f_{n}(H)). In particular, if H = S, this replaces a sequence by the sequence of its partial sums.

• We could use the sequences F_{n} instead of f_{n}. Since

F_{G×H}(x) = F_{G}(x)F_{H}(x)

and

F_{GWrH}(x) = F_{H}(F_{G}(x) − 1),

these operators will be exponential convolution (for the direct product) and substitution in the exponential generating function (for the wreath product).

References

[1] E. A. Bender, P. J. Cameron, A. M. Oddlyzko and L. B. Richmond, Connectedness, classes, and cycle index, Discrete Math., to appear.

[2] M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Algebra Appl. 228 (1995), 57–72.

[3] P. J. Cameron, Orbits of permutation groups on unordered sets, II, J. London Math. Soc. (2) 23 (1981), 249–265.

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

[5] P. J. Cameron, On an algebra related to orbit-counting, J. Group Theory 1 (1998), 173–179.

[6] P. Erdős and A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963), 295–315.

[7] R. Fraïssé, Theory of Relations, North-Holland, Amsterdam, 1986.

[8] A. Joyal, Une theorie combinatoire des séries formelles, Adv. Math. 42 (1981), 1–82.

[9] D. E. Knuth, Axioms and Hulls, Lecture Notes in Computer Science 606, Springer, Berlin, 1992.

[10] A. H. Lachlan, Countable homogeneous tournaments, Trans. Amer. Math. Soc. 284 (1984), 431–461.

[11] H. D. Macpherson, The action of an infinite permutation group on the unordered subsets of a set, Proc. London Math. Soc. (3) 46 (1983), 471–486.

[12] H. D. Macpherson, Growth rates in infinite graphs and permutation groups, Proc. London Math. Soc. (3) 51 (1985), 285–294.

[13] C. L. Mallows and N. J. A. Sloane, Two-graphs, switching classes, and Euler graphs are equal in number, SIAM J. Appl. Math. 28 (1975), 876–880.

[14] M. Pouzet, Application de la notion de relation presque-enchaînable au dénombrement des restrictions finies d’une relation, Z. Math. Logik Grundl. Math. 27 (1981), 289–332.

[15] D. E. Radford, A natural ring basis for the shuffle algebra and an application to group schemes, J. Algebra 58 (1979), 432–454.

[16] C. Reutenauer, Free Lie Algebras, London Math. Soc. Monographs (New Series) 7, Oxford University Press, Oxford, 1993.