On an algebra related to orbit-counting

Peter J. Cameron

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

Abstract

With any permutation group G on an infinite set Ω is associated a graded algebra A^{G} (the algebra of G-invariants in the reduced incidence algebra of finite subsets of Ω). The dimension of the nth homogeneous component of A^{G} is equal to the number of orbits of G on n-subsets of Ω. If it happens that G is the automorphism group of a homogeneous structure M, then this is the number of unlabelled nelement substructures of M. Many combinatorial enumeration problems fit into this framework.

I conjectured 20 years ago that, if G has no finite orbits on Ω, then A^{G} is an integral domain (and even has the stronger property that a specific quotient is an integral domain). I shall say that G is entire if A^{G} is an integral domain, and strongly entire if the stronger property holds. These properties have (rather subtle) consequences for the enumeration problems. The conjecture is still open; but in this paper I prove that, if G is transitive on Ω and the point stabiliser H is (strongly) entire, then G is (strongly) entire.

1 Introduction

A relational structure M such as a graph, digraph or poset is said to be homogeneous if any isomorphism between finite substructures of M can be extended to an automorphism of M.

Let M be homogeneous, G the automorphism group of M, and C the age of M, the class of finite structures embeddable in M. Then the number of orbits of G on n-element subsets of M is equal to the number of unlabelled n-element structures in C, and the number of orbits on n-tuples of distinct elements is equal to the number of labelled n-element structures in M. Moreover, a theorem of Fraïssé [4] characterises the ages of (countable) homogeneous structures. So orbit-counting problems for groups are equivalent to combinatorial enumeration problems in Fraïssé classes. (See [2] for discussion.)

As a tool for such enumeration problems, I introduced in [1] a commutative, associative graded algebra A^{G} associated with a permutation group G, with the property that the dimension of the nth homogeneous component of A^{G} is equal to the number of orbits of G on n-sets (if this number is finite — otherwise both quantities are infinite). I conjectured that, if G has no finite orbits, then A^{G} is an integral domain. (In fact, a stronger conjecture was given, as will be explained in the next section.) This conjecture would have implications for the rate of growth of the numbers of n-element unlabelled structures in Fraïssé classes under very mild assumptions.

Almost no progress has been made on this conjecture. The purpose of this paper is to prove a theorem which, while not getting any closer to proving it, introduces some techniques which may be useful. The theorem asserts that, if G is a transitive extension of H, and A^{H} is an integral domain, then so is A^{G} (and the same holds for the stronger condition of the conjecture).

2 The theorem

Let Ω be a set, usually assumed to be countably infinite. The reduced incidence algebra (Rota [8]) A of the poset of finite subsets of Ω is defined as follows. For n ≥ 0, let V_{n} be the vector space (over ℂ) of functions from the set \binom{Ω}{n} of n-element subsets of Ω to ℂ. (Addition and scalar multiplication of functions is defined pointwise.) We define a multiplication from V_{k} × V_{l} to V_{k+l} as follows: for f ∈ V_{k}, g ∈ V_{l}, the function fg ∈ V_{k+l} is given by

fg(M) = ∑_{K∈\binom{M}{k}} f(K)g(M \ K),

for any M ∈ \binom{Ω}{k+l}.

Let

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

and extend the multiplication linearly to A. It is easily verified that the multiplication is commutative and associative.

Now suppose that the group G acts on Ω. Let V_{n}^{G} be the space of functions in V_{n} fixed by G, and

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

a subalgebra of A, and hence a commutative and associative graded algebra. A function in V_{n} is fixed by G if and only if it is constant on the orbits of G; so dim(V_{n}^{G}) is equal to the number of orbits on n-sets, if this is finite.

The identity element of A is the function in V_{0} whose value (on the empty set) is 1. We will always use the symbol e for the constant function in V_{1} with value 1. It is known that e is not a zero-divisor. (In fact, multiplication of elements of V_{n} by e is one-to-one as long as |Ω| ≥ 2n + 1: see [2].)

We say that G is entire if A^{G} is an integral domain, and that G is strongly entire if e is prime (in the sense that, if e divides a product, then it divides one of the factors); equivalently, if A^{G}/eA^{G} is an integral domain.

Lemma 1 If G is strongly entire, then it is entire.

Proof. Suppose that e is prime in A^{G}, and that fg = 0, with f, g ≠ 0. By considering the homogeneous components of f and g of least degree, we can assume that f and g are homogeneous; we further assume that the sum of their degrees is minimal. Then e|fg, so e|f or e|g, say f = eh. Now ehg = 0, so hg = 0 (since e is not a zero-divisor), contradicting the minimality of deg(f) + deg(g).

Now the conjecture made in [1] asserts that, if G has no finite orbits on Ω, then G is strongly entire. According to Lemma 1, this would imply that it is entire under the same hypotheses.

The converse of the conjecture is true: for, if G has an orbit Δ with |Δ| = n, and f ∈ V_{n}^{G} takes the value 1 at Δ and 0 elsewhere, then f^{2} = 0. The conjecture seems to be related to the fact that, if G has no finite orbits, then any two finite sets have disjoint G-images (Lemma 2.3 of Neummann [7]).

These conditions were introduced in order to study the rate of growth of the number f_{n}(G) of orbits on n-sets of the permutation group G. Subsequently, global results on growth rate were proved, notably by Macpherson [5], using completely different techniques. However, the algebraic method offers the possibility of proving local results. Here is an example.

Proposition 1 Let G be a permutation group on Ω, and f_{n} the number of orbits of G on the set of n-subsets of Ω.

(a) If G is entire, then

f_{m+n} ≥ f_{m} + f_{n} − 1.

(b) If G is strongly entire, then

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

Proof. The dimension of the nth homogeneous component of A^{G} is f_{n}, while the dimension of the nth homogeneous component of A^{G}/eA^{G} is f_{n} − f_{n−1} (since e is not a zero-divisor). So the Proposition follows immediately from the following result:

Lemma 2 Let A = ⨁ V_{n} be a graded algebra over ℂ, with dim(V_{n}) = r_{n}. If A is an integral domain, then

r_{m+n} ≥ r_{m} + r_{n} − 1.

Proof. Multiplication is a bilinear map from V_{m} × V_{n} to V_{m+n}, and so induces a linear map μ from V_{m} ⊗ V_{n} to V_{m+n}. Let U = ker(μ). Now U contains no rank 1 tensor v ⊗ w, with v, w ≠ 0; for (v ⊗ w)μ = vw ≠ 0, since A is an integral domain.

Now a subspace of V_{m} ⊗ V_{n} containing no rank 1 tensor has dimension at most (r_{m} − 1)(r_{n} − 1). (For the rank 1 tensors, modulo scalars, form the projective Segre variety, with dimension r_{m} + r_{n} − 1, and this variety intersects any linear subspace whose codimension is smaller than this number: see Shafarevich [9], pp. 56, 71.) So we have

dim(V_{m+n}) ≥ r_{m}r_{n} − (r_{m} − 1)(r_{n} − 1) = r_{m} + r_{n} − 1,

as claimed.

The permutation group G on Ω is a transitive extension of the permutation group H on Δ if • G is transitive on Ω;

• for α ∈ Ω, the permutation groups G_{α} on Ω \ {α} and H on Δ are isomorphic, where G_{α} is the stabiliser of α.

Now we can state the main theorem of the paper. Theorem 1 Let G be a transitive extension of H. Then

(a) if H is entire, then so is G;

(b) if H is strongly entire, then so is G.

3 An easier result

We begin with a simpler result along the same lines, as an introduction to these ideas. Theorem 2 Let Ω be an infinite set, and G_{1} and G_{2} be permutation groups on Ω with G_{1} ≤ G_{2}.

(a) If G_{1} is entire, then so is G_{2}.

(b) If G_{1} is strongly entire, then so is G_{2}. Proof. (a) This is clear since A^{G_{2}} is a subalgebra of A^{G_{1}}.

(b) Assume that G_{1} is strongly entire and let a, b ∈ A^{G_{2}} with e|ab. Then e divides either a or b in A^{G_{1}}; say a = ec with c ∈ A^{G_{1}}. For any g ∈ G_{2}, we have a^{g} = e^{g}c^{g}, whence a = ec^{g}, since a, e ∈ A^{G_{2}}. So we have

e(c − c^{g}) = 0,

whence c = c^{g}, since e is not a zero-divisor. As this holds for all g ∈ G_{2}, we have c ∈ A^{G_{2}}, as required.

4 Proof of the Main Theorem

We assume the hypotheses of the Theorem: G is a transitive extension of H, where G acts on Ω and H on Δ.

We begin with the observation that, if K is a finite set containing α, then there exists g ∈ G such that Kg does not contain α. (Simply choose g so that αg^{−1} is not in K.) It follows that there is no non-zero homogeneous element in A^{G}, all of the sets in whose support contain α.

Now G_{α} ≅ H × U (with the intransitive action of the product), where U is the trivial group on {α}. Then A^{U} is 2-dimensional, generated by an element u of degree 1 satisfying u^{2} = 0. Hence A^{G_{α}} ≅ A^{H} ⊗ A^{U}, so A^{G_{α}} = {a + bu : a, b ∈ A^{H}}.

Furthermore, A^{G} is a subalgebra of A^{G_{α}}, since G_{α} is a subgroup of G. Hence we can define a map θ : A^{G} → A^{H} by (a + bu)θ = a.

Lemma 3 θ is a monomorphism.

Proof. That θ is a homomorphism follows from the equations

(a_{1} + b_{1}u) + (a_{2} + b_{2}u) = (a_{1} + a_{2}) + (b_{1} + b_{2})u,
(a_{1} + b_{1}u) · (a_{2} + b_{2}u) = (a_{1}a_{2}) + (a_{1}b_{2} + a_{2}b_{1})u.

That it is injective follows from the remark with which we began the proof: for the homogeneous components of an element bu of the kernel would be G-invariant functions, every set in whose support contains α.

Hence A^{G} is a subalgebra of A^{H}, and part (a) of the Theorem follows.

Remark. We have A^{G} = {a + d(a)u : a ∈ Im(θ)}, where d is a derivation on Im(θ): this is a function satisfying

d(a + b) = d(a) + d(b),
d(ab) = ad(b) + d(a)b.

For the proof of part (b), we need the following result.

Lemma 4 Let f be a function on the n-subsets of Ω\{α}, where Ω is infinite. Let G be a transitive permutation group on Ω. Suppose that f takes the same value on n-sets which lie in the same orbit of G. Then f has a unique extension to a G-invariant function on the n-subsets of Ω.

Proof. We must define f on n-subsets containing α. If K is such a set, there exists g ∈ G with α ∉ Kg, and we must set f(K) = f(Kg). We have to show that this is well-defined and G-invariant.

Suppose that g_{1}, g_{2} ∈ G with α ∉ Kg_{1} and α ∉ Kg_{2}. Then (Kg_{1})(g_{1}^{−1}g_{2}) = Kg_{2}. By hypothesis, f(Kg_{1}) = f(Kg_{2}). So the extension of f is well-defined.

Let K_{1} and K_{2} be n-sets containing α, and suppose that K_{1}h = K_{2} for some h ∈ G. Choose g ∈ G such that α ∉ (K_{1} ∪ K_{2})g. Then

(K_{1}g)(g^{−1}hg) = K_{1}hg = K_{2}g,

and so f(K_{1}g) = f(K_{2}g). Thus the extension of f is G-invariant.

Now we return to the proof of (b). Let e denote the element of A^{H} of this name. The corresponding element of A^{G} is e+u. (In the notation of the earlier Remark, d(e) = 1.) So we are concerned with divisibility by e + u.

We claim that

e + u divides a + d(a)u in A^{G} if and only if e divides a in A^{H}.

Proof. First observe that it suffices to prove the result for homogeneous elements.

Suppose that a has degree n, and that e divides a, say a = eb. Then b is a function on (n − 1)-subsets of Ω \ {α}. Also b takes the same value on sets in the same orbit of G. (For suppose that K_{1} and K_{2} are (n − 1)-sets in the same orbit of G. Choose (2n − 1)-sets L_{1} and L_{2}, in the same G-orbit, containing K_{1} and K_{2} respectively, but not containing α. Then the values of a on corresponding n-subsets of L_{1} and L_{2} are equal. Since multiplication by e is invertible on functions on the (n − 1)-subsets of a (2n − 1)-set, the values of b on corresponding subsets are also equal; that is, b(K_{1}) = b(K_{2}).)

By the Lemma, b extends to an element b + d(b)u of A^{G}. Then

(e + u)(b + d(b)u) = eb + (b + ed(b))u = a + d(a)u;

so a + d(a)u is divisible by e + u, as required. The converse is trivial: if a + d(a)u = (e + u)(b + d(b)u), then a = eb.

Now suppose that e is prime in A^{H}, and that e+u divides (a+d(a)u)(b+ d(b)u). Then e divides ab, so e divides a or e divides b, so e + u divides a + d(a)u or e + u divides b + d(b)u, as required.

5 Remarks

Previously, the only technique available for showing that G is (strongly) entire involved showing something much stronger, namely, that A^{G} is a polynomial algebra. See [3], where sufficient conditions (involving a notion of “connected structure”) on a Fraïssé class are given to ensure that, if G is the automorphism group of the corresponding homogeneous structure M, then A^{G} is a polynomial ring. Now a polynomial ring is certainly an integral domain; in fact, e is prime, since there is a set of polynomial generators including the element e. So, for example, in each of the following cases (discussed in [3]), A^{H} is a polynomial algebra, H is strongly entire:

(a) H is the automorphism group of the random graph;

(b) H is the group of order-preserving permutations of ℚ fixing q pairwise disjoint dense subsets whose union is ℚ.

In each of the cases (a) and (b), H has a transitive extension G. In (a), this is the automorphism group of the countable universal two-graph; in (b), the automorphism group of an appropriate “circular structure”. According to the Theorem, in each case G is strongly entire. (This resolves a question posed in [3].) It is unknown whether A^{G} is a polynomial algebra.

In this connection, case (a) is interesting. Since the numbers of twographs and even graphs on n vertices are equal [6], we see that, if A^{G} is a polynomial algebra, then the number of polynomial generators of degree n is equal to the number of connected even (that is, Eulerian) graphs on n vertices. However, I do not know how to choose the correct number of elements to be the polynomial generators.

References

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

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

[3] P. J. Cameron, The algebra of an age, pp. 126–133 in Model Theory of Groups and Automorphism Groups (ed. David M. Evans), London Mathematical Society Lecture Notes 244, Cambridge University Press, Cambridge, 1997.

[4] R. Fraïssé, Sur certains relations qui généralisent l’ordre des nombres rationnels, C. R. Acad. Sci. Paris 237 (1953), 540–542.

[5] 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.

[6] 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.

[7] P. M. Neumann, The lawlessness of finitary permutation groups, Arch. Math. 26 (1975), 561–566.

[8] G.-C. Rota, On the foundations of combinatorial theory, I: Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie 2 (1964), 340–368.

[9] I. R. Shafarevich, Basic Algebraic Geometry I: Varieties in Projective Space (2nd edition), Springer-Verlag, Berlin, 1994.