WHEN THE ORBIT ALGEBRA OF GROUP IS AN INTEGRAL
DOMAIN? PROOF OF A CONJECTURE OF P.J. CAMERON
MAURICE POUZET
Abstract. P.J.Cameron introduced the orbit algebra of a permutation group and
conjectured that this algebra is an integral domain if and only if the group has no
finite orbit. We prove that this conjecture holds and in fact that the age algebra of a
relational structure R is an integral domain if and only if R is age-inexhaustible. We
deduce these results from a combinatorial lemma asserting that if a product of two
non-zero elements of a set algebra is zero then there is a finite common tranversal of
their supports. The proof is built on Ramsey theorem and the integrity of a shuffle
algebra.
Introduction
In 1981, P.J.Cameron [4] (see also [9] p.86) associated a graded algebra A[G] to a
permutation group G acting on an infinite set E. He formulated two conjectures on
the integrity of this algebra. The purpose of this paper is to present a solution to the
first of these conjectures. Consequences on the enumeration of finite substructures of
a given structure are mentionned. Some problems are stated.
0.1. The conjectures. Here is the content of these conjectures, freely adapted from
Cameron’s web page (see Problem 2 [10]). The graded algebra A[G] is the direct sum
A[G]n
where A[G]n is the set of all G-invariant functions f from the set [E]
n of n-element
subsets of E into the field C of complex numbers. Multiplication is defined by the
rule that if f ∈ A[G]m, g ∈ A[G]n and Q is an (m+ n)-element subset of E then
(1) (fg)(Q) :=
P∈[Q]m
f(P )g(Q \ P )
As shown by Cameron, the constant function e in A[G]1 (with value 1 on every one
element set) is not a zero-divisor (see Theorem 0.8 below). The group G is entire if
A[G] is an integral domain, and strongly entire if A[G]/eA[G] is an integral domain.
Date: November 6, 2018.
1991 Mathematics Subject Classification. 03 C13, 03 C52, 05 A16, 05 C30, 20 B27.
Key words and phrases. Relational structures, ages, counting functions, oligomorphic groups, age
algebra, Ramsey theorem, integral domain.
Research done under the auspices of Intas programme 03-51-4110 ”Universal algebra and lattice
theory” .
http://arxiv.org/abs/0704.1548v1
2 MAURICE POUZET
Conjectures 0.1. G is (strongly) entire if and only if it has no finite orbit on E.
The condition that G has no finite orbit on E is necessary. We prove that it suffices
for G to be entire. As it turns out, our proof extends to the algebra of an age, also
invented by Cameron [10].
0.2. The algebra of an age. A relational structure is a realization of a language
whose non-logical symbols are predicates. This is a pair R := (E, (ρi)i∈I) made of a
set E and a family of mi-ary relations ρi on E. The set E is the domain or base of
R; the family µ := (mi)i∈I is the signature of R. The substructure induced by R on
a subset A of E, simply called the restriction of R to A, is the relational structure
R↾A := (A, (A
mi ∩ ρi)i∈I). Notions of isomorphism, as well as isomorphic type, are
defined in natural way (see Subsection 1.1).
A map f : [E]m → C, where m is a non negative integer, is R-invariant if f(P ) =
f(P ′) whenever the restrictions R|P and R|P ′ are isomorphic. The R-invariant maps
can be multiplied. Indeed, it is not difficult to show that if f : [E]m → C and
g : [E]n → C are R-invariant, the product defined by Equation (1) is R-invariant.
Equipped with this multiplication, the C-vector space spanned by the R-invariant
maps becomes a graded algebra, the age algebra of R, that we denote by C.A(R).
The name, coined by Cameron, comes from the notion of age defined by Fräıssé [13].
Indeed, the age of R is the collection A(R) of substructures of R induced on the
finite subsets of R, isomorphic substructures being identified. And it can be shown
that two relational structures with the same age yields the same algebra (up to an
isomorphism of graded algebras).
The algebra associated to a group is a special case of age algebra. Indeed, to a
permutation group G acting on E we may associate a relational structure R with
base E such that the G-invariant maps coincide with the R-invariant maps.
Our criterium for the integrity of the age algebra is based on the notion of kernel:
The kernel of a relational structure R is the subset K(R) of x ∈ E such that
A(R|E\{x}) 6= A(R).
The emptyness of the kernel R is a necessary condition for the integrity of the
age algebra. Indeed, if K(R) 6= ∅, pick x ∈ K(R) and F ∈ [E]<ω such that R↾F ∈
A(R) \ A(R|E\{x}). Let P ∈ [E]
<ω. Set f(P ) := 1 if R↾P is isomorphic to R↾F ,
otherwise set f(P ) := 0. Then f 2 := ff = 0.
Theorem 0.2. Let R be a relational structure with possibly infinitely many non iso-
morphic types of n-element substructures. The age algebra C.A(R) is an integral
domain if and only if the kernel of R is empty.
The application to the conjecture of Cameron is immediate. LetG be a permutation
group acting on E and let R be a relational structure encoding G. Then, the kernel
of R is the union of the finite G-orbits of the one-element sets. Thus, if G has no
finite orbit, the kernel of R is empty. Hence from Theorem 0.2, A[G] is an integral
domain, as conjectured by Cameron.
We deduce Theorem 0.2 from a combinatorial property of a set algebra over a field
(Theorem 0.3 below). This property does not depends upon the field, provided that
its characteristic is zero. The proof we give in Section 1.1 is an extension of our
A CONJECTURE OF P.J. CAMERON 3
1970 proof that the profile of an infinite relational structure does not decrease (see
Theorem 0.5 below). The key tool we used then was Ramsey’s theorem presented in
terms of a property of almost-chainable relations. Here, these relations are replaced by
F −L-invariant relational structures, structures which appeared, under other names,
in several of our papers (see [24], [25], [27]). The final step is reminiscent of the proof
of the integrity of a shuffle algebra.
We introduced the notion of kernel in[24] and studied it in several papers [25] [26],
[27] and [29]. As it is easy to see (cf [25][29]), the kernel of a relational structure
R is empty if and only if for every finite subset F of E there is a disjoint subset F ′
such that the restrictions R|F and R|F ′ are isomorphic. Hence, relational structures
with empty kernel are those for which their age has the disjoint embedding property,
meaning that two arbitrary members of the age can be embedded into a third in
such a way that their domain are disjoint. In Fräıssé’s terminology, ages with the
disjoint embedding property are said inexhaustible and relational structures whose
age is inexhaustible are said age-inexhaustible; we say that relational structures with
finite kernel are almost age-inexhaustible. 1
0.3. A transversality property of the set algebra. Let K be a field with charac-
teristic zero. Let E be a set and let [E]<ω be the set of finite subsets of E (including
the empty set ∅). Let K[E]
be the set of maps f : [E]<ω → K. Endowed with the
usual addition and scalar multiplication of maps, this set is a vector space over K.
Let f, g ∈ K[E]
and Q ∈ [E]<ω. Set:
(2) fg(Q) =
P∈[Q]<ω
f(P )g(Q \ P )
With this operation added, the above set becomes a K-algebra. This algebra is
commutative and it has a unit, denoted by 1. This is the map taking the value 1
on the empty set and the value 0 everywhere else. The set algebra is the subalgebra
made of maps f such that f(P ) = 0 for every P ∈ [E]<ω with |P | large enough.
This algebra is graded, the homogeneous component of degree n being made of maps
which take the value 0 on every subset of size different from n (see Cameron [6]). If
f and g belong to two homogeneous components, their product is given by Equation
(1), thus an age algebra, or a group algebra, A, as previously defined, is a subalgebra
of this set algebra. The set algebra is far from to be an integral domain. But, with
the notion of degree, the integrity of A will reduce to the fact that if m and n are
two non negative integers and f : [E]m → K, f : [E]n → K are two non-zero maps
belonging to A, their product fg is non zero.
Let H be a family of subsets of E, a subset T of E is a transversal of H if F ∩T 6= ∅
for every F ∈ H; the transversality of H, denoted τ(H), is the minimum of the
cardinalities (possibly infinite) of transversals of H. We make the convention that
τ(H) = 0 if H is empty.
Let f : [E]m → K, denote supp(f) := {P ∈ [V ]m : f(P ) 6= 0}.
1In order to agree with Fräıssé’s terminology, we disagree with the terminology of our papers, in
which inexhaustibility, resp. almost inexhaustibility, is used for relational structures with empty,
resp. finite, kernel, rather than for their ages.
4 MAURICE POUZET
Here is our combinatorial result:
Theorem 0.3. Let m,n be two non negative integers. There is an integer t such that
for every set E with at least m + n elements, every field K with characteristic zero,
every pair of maps f : [E]m → K, g : [E]n → K such that fg is zero, but f and g are
not, then τ(supp(f) ∪ supp(g)) ≤ t.
With this result, the proof of Theorem 0.2 is immediate. Indeed, let R be a rela-
tional structure with empty kernel. If K.A(R), the age algebra of R over K, is not an
integral domain there are two non-zero maps f : [E]m → K, f : [E]n → K belonging
to K.A(R), whose product fg is zero. Since K is an integral domain, none of the in-
tegers m and n can be zero. Since f is R-invariant, m is positive and the kernel K(R)
of R is empty, it turns out that τ(supp(f)) is infinite. Hence τ(supp(f)∪ supp(g)) is
infinite, contradicting the conclusion of Theorem 0.3.
An other immediate consequence of Theorem 0.3 is the fact, due to Cameron, that
on an infinite set E, e is not a zero-divisor (see Theorem 0.8 below).
0.3.1. Existence and values of τ . The fact the size of a transversal can be bounded
independently of f and g, and the value of the least upper bound, seem to be of
independent interest.
So, let τ(m,n) be the least t for which the conclusion of Theorem 0.3 holds.
Trivially, we have τ(m,n) = τ(n,m). We have τ(0, n) = τ(m, 0) = 0. Indeed,
if m = 0, f is defined on the empty set only, an thus fg(Q) = f(∅)g(Q). Since
K has no non zero divisors, fg is non zero provided that f and g are non zero.
The fact that there is no pair f, g such that fg is zero, but f and g are not, yields
τ(supp(f) ∪ supp(g)) = 0.
We have τ(1, n) = 2n (Theorem 2.4). This is a non-trivial fact which essentially
amounts to a weighted version of the Gottlieb-Kantor Theorem on incidence matrices
([15], [19], see subsection 0.4 and Theorem 2.3). These are the only exact values
we know. We prove that τ(m,n) exists, by supposing that τ(m − 1, n) exists. Our
existence proof relies in an essential way on Ramsey theorem. It yields astronomical
upper bounds. For example, it yields τ(2, 2) ≤ 2(R2k(4) + 2) , where k = 5
30 and
R2k(4) is the Ramsey number equal to the least integer p such that for every colouring
of the pairs of {1, . . . , p} into k colors there are four integers whose all pairs have
the same colour. The only lower bound we have is τ(2, 2) ≥ 7 and more generally
τ(m,n) ≥ (m+ 1)(n + 1)− 2. We cannot preclude a extremely simple upper bound
for τ(m,n), eg quadratic in n+m.
0.4. Age algebra and profile of a relational structure. The group agebra was
invented by Cameron in order to study the behavior of the function θG which counts
for each integer n the number θG(n) of orbits of n-subsets of a set E on which acts a
permutation groupG, a function that we call the orbital profile ofG. Groups for which
the orbital profile takes only finite values are quite important. Called oligomorphic
groups by Cameron, they are an objet of study by itself (see Cameron’s book[5]).
We present first some properties of the profile, a counting function somewhat more
general. Next, we present the link with the age algebra, then we gives an illustration
of Theorem 0.2. We conclude with some problems.
A CONJECTURE OF P.J. CAMERON 5
0.4.1. Profile of a relational structure. The profile of a relational structure R with
base E is the function ϕR which counts for every integer n the number (possibly
infinite) ϕR(n) of substructures of R induced on the n-element subsets, isomorphic
substructures being identified. Clearly, if R encodes a permutation groups G, ϕR(n)
is the number θG(n) of orbits of n-element subsets of E.
If the signature µ is finite (in the sense that I is finite), there are only finitely
many relational structures with signature µ on an n-element domain, hence ϕR(n) is
necessarily an integer for each integer n. In order to capture examples coming from
algebra and group theory, one cannot preclude I to be infinite. But then, ϕR(n) could
be an infinite cardinal. As far as one is concerned by the behavior of ϕR, this case
can be excluded:
Fact 0.4. [28] Let n < |E|. Then
(3) ϕR(n) ≤ (n + 1)ϕR(n+ 1)
In particular:
(4) If ϕR(n) is infinite then ϕR(n + 1) is infinite too and ϕR(n) ≤ ϕR(n+ 1).
Inequality (3) can be substantially improved:
Theorem 0.5. If R is a relational structure on an infinite set then ϕR is non-
decreasing.
This result was conjectured with R.Fräıssé [14]. We proved it in 1971; the proof -
for a single relation- appeared in 1971 in R.Fräıssé’s book [12], Exercise 8 p. 113; the
general case was detailed in [26]. The proof relies on Ramsey theorem [32].
More is true:
Theorem 0.6. If R is a relational structure on a set E having at least 2n + m
elements then ϕR(n) ≤ ϕR(n+m).
Meaning that if |E| := ℓ then ϕR increases up to
; and, for n ≥ ℓ
the value in n
is at least the value of the symmetric of n w.r.t. ℓ
The result is a straightforward consequence of the following property of incidence
matrices.
Let m,n, ℓ be three non-negative integers and E be an ℓ-element set. Let Mn,n+m
be the matrix whose rows are indexed by the n-element subsets P of E and columns
by the n +m-element subsets Q of E, the coefficient aP,Q being equal to 1 if P ⊆ Q
and equal to 0 otherwise.
Theorem 0.7. If 2n+m ≤ l then Mn,n+m has full row rank (over the field of rational
numbers).
Theorem 0.7 is in W.Kantor 1972 [19], with similar results for affine and vector
subspaces of a vector space. Over the last 30 years, it as been applied and redis-
covered many times; recently, it was pointed out that it appeared in a 1966 paper
of D.H.Gottlieb [15]. Nowadays, this is one of the fundamental tools in algebraic
combinatorics. A proof, with a clever argument leading to further developments, was
given by Fräıssé in the 1986’s edition of his book, Theory of relations, see [13].
6 MAURICE POUZET
We proved Theorem 0.6 in 1976 [23]. The same conclusion was obtained first
for orbits of finite permutation groups by Livingstone and Wagner, 1965 [20], and
extended to arbitrary permutation groups by Cameron, 1976 [3]. His proof uses the
dual version of Theorem 0.7. Later on, he discovered a nice translation in terms of
his age algebra, that we present now.
For that, observe that ϕR only depends upon the age of R and, moreover, if ϕR take
only integer values, then K.A(R) identifies with the set of (finite) linear combinations
of members of A(R). In this case, as pointed out by Cameron, ϕR(n) is the dimension
of the homogeneous component of degree n of K.A(R).
Let e ∈ K[E]
be the map which is 1 on the one-element subsets of E and 0
elsewhere. Let U be the subalgebra generated by e. We can think of e as the sum of
isomorphic types of the one-element restrictions of R. Members of U are then of the
form λme
m + · · ·+ λ1e + λ01 where 1 is the isomorphic type of the empty relational
structure and λm, . . . , λ0 are in K. Hence U is graded, with Un, the homogeneous
component of degree n, equals to K.en.
Here is the Cameron’s result:
Theorem 0.8. If R is infinite then, for every u ∈ K.A(R), eu = 0 if and only if
u = 0
This innocent looking result implies that ϕR is non decreasing. Indeed, the image of
a basis of K.A(R)n by multiplication by e
m is an independent subset of K.A(R)n+m.
0.4.2. Growth rate of the profile. Infinite relational structures with a constant profile,
equal to 1, were called monomorphic and characterized by R. Fräıssé who proved that
they were chainable. Later on, those with bounded profile, called finimorphic, were
characterized as almost chainable [14]. Groups with orbital profile equal to 1 were
described by P.Cameron in 1976 [3]. From his characterization, Cameron obtained
that an orbital profile is ultimately constant, or grows as fast as a linear function with
slope 1
The age algebra can be also used to study the growth of the profile.
If A is a graded algebra, the Hilbert function hA of A is the function which associates
to each integer n the dimension of the homogeneous component of degree n. So,
provided that it takes only finite values, the profile ϕR is the Hilbert function of the
age algebra C.A(R). In [10], Cameron made the following important observation
about the behavior of the Hilbert fonction.
Theorem 0.9. Let A be a graded algebra over an algebraically closed field of charac-
teristic zero. If A is an integral domain the values of the Hilbert function hA satisfy
the inequality
(5) hA(n) + hA(m)− 1 ≤ hA(n +m)
for all non-negative integers n and m.
This result has an immediate consequence on the growth of the profile:
Theorem 0.10. [26] The growth of the profile of a relational structure with empty
kernel is at least linear provided that it is unbounded.
A CONJECTURE OF P.J. CAMERON 7
In fact, provided that the relational structures satisfy some mild conditions, the
existence of jumps in the behavior of the profile extends.
Let ϕ : N → N and ψ : N → N. Recall that ϕ = O(ψ) and ψ grows as fast as ϕ
if ϕ(n) ≤ aψ(n) for some positive real number a and n large enough. We say that
ϕ and ψ have the same growth if ϕ grows as fast as ψ and ψ grows as fast as ϕ.
The growth of ϕ is polynomial of degree k if ϕ has the same growth as n →֒ nk; in
other words there are positive real numbers a and b such that ank ≤ ϕ ≤ bnk for n
large enough. Note that the growth of ϕ is as fast as every polynomial if and only if
limn→+∞
= +∞ for every non negative integer k.
Theorem 0.11. Let R := (E, (ρi)i∈I) be a relational structure. The growth of ϕR
is either polynomial or as fast as every polynomial provided that either the signature
µ := (ni)i∈I is bounded or the kernel K(R) of R is finite.
Theorem 0.11 is in [24]. An outline of the proof is given in [28]. A part appeared in
[26], with a detailed proof showing that the growth of unbounded profiles of relational
structures with bounded signature is at least linear.
The kernel of any relational structure which encodes an oligomorphic permutation
group is finite (indeed, as already mentionned, if R encodes a permutation group G
acting on a set E then K(R) is the set union of the finite orbits of the one-element
subsets of E. Since the number of these orbits is at most θG(1), K(R) is finite if G is
oligomorphic). Hence:
Corollary 0.12. The orbital profile of an oligomorphic group is either polynomial or
faster than every polynomial.
For groups, and graphs, there is a much more precise result than Theorem 0.11. It
is due to Macpherson, 1985 [22].
Theorem 0.13. The profile of a graph or a permutation groups grows either as a
polynomial or as fast as fε, where fε(n) = e
, this for every ε > 0.
0.4.3. Growth rate and finite generation. A central question in the study of the profile,
raised first by Cameron in the case of oligomorphic groups, is this:
Problem 1. If the profile of a relational structures R with finite kernel has polynomial
growth, is ϕR(n) ≃ cn
k′ for some positive real c and some non-negative integer k′?
Let us associate to a relational structure R whose profile takes only finite values
its generating series
HϕR :=
ϕR(n)x
Problem 2. If R has a finite kernel and ϕR is bounded above by some polynomial,
is the series HϕR a rational fraction of the form
P (x)
(1− x)(1− x2) · · · (1− xk)
with P ∈ Z[x]?
8 MAURICE POUZET
Under the hypothesis above we do not know if HϕR is a rational fraction.
It is well known that if a generating function is of the form
P (x)
(1−x)(1−x2)···(1−xk)
for n large enough, an is a quasi-polynomial of degree k
′, with k′ ≤ k − 1, that is
a polynomial ak′(n)n
k′ + · · ·+ a0(n) whose coefficients ak′(n), . . . , a0(n) are periodic
functions. Hence, a subproblem is:
Problem 3. If R has a finite kernel and ϕR is bounded above by some polynomial,
is ϕR(n) a quasi-polynomial for n large enough?
Remark 0.14. Since the profile is non-decreasing, if ϕR(n) is a quasi-polynomial for
n large enough then ak′(n) is eventually constant. Hence the profile has polynomial
growth in the sense that ϕR(n) ∼ cn
k′ for some positive real c and k′ ∈ N. Thus, in
this case, Problem 1 has a positive solution.
A special case was solved positively with N.Thiéry [30].
These problems are linked with the structure of the age algebra. Indeed, if a
graded algebra A is finitely generated, then, since A is a quotient of a polynomial
ring K[x1, . . . , xd], its Hilbert function is bounded above by a polynomial. And, in
fact, as it is well known, its Hilbert series is a fraction of form
P (x)
(1−x)d
, thus of the form
given in (6). Moreover, one can choose a numerator with non-negative coefficients
whenever the algebra is Cohen-Macaulay. Due to Problem 2, one could be tempted
to conjecture that these sufficient conditions are necessary in the case of age agebras.
Indeed, from Theorem 0.8 one deduces easily:
Theorem 0.15. The profile of R is bounded if and only if K.A(R) is finitely generated
as a module over U , the graded algebra generated by e. In particular, if one of these
equivalent conditions holds, K.A(R) is finitely generated
But this case is exceptional. The conjecture can be disproved with tournaments.
Indeed, on one hand, there are tournaments whose profile has arbitrarily large poly-
nomial growth rate and, on an other hand, the age algebra of a tournament is finitely
generated if and only if the profile of the tournament is bounded (this result was
obtained with N.Thiery, a proof is presented in [28]).
0.4.4. Initial segments of an age and ideals of a ring. No concrete description of
relational structures with bounded signature, or finite kernel, which have polynomial
growth is known. In [24] (see also [28]) we proved that if a relational structure R
has this property then its age, A(R), is well-quasi-ordered under embeddability, that
is every final segment of A(R) is finitely generated, which amounts to the fact that
the collection F (A(R)) of final segments of A(R) is noetherian, w.r.t. the inclusion
order. Since the fundamental paper of Higman[17], applications of the notion of
well-quasi-ordering have proliferated (eg see the Robertson-Seymour’s theorem for an
application to graph theory [11] ). Final segments play for posets the same role than
ideals for rings. Noticing that an age algebra is finitely generated if and only if it is
noetherian, we are lead to have a closer look at the relationship between the basic
objects of the theory of relations and of ring theory, particularly ages and ideals.
We mention the following result which will be incorporated into a joint paper with
N.Thiéry.
A CONJECTURE OF P.J. CAMERON 9
Proposition 0.16. Let A be the age of a relational structure R such that the profile
of R takes only finite values and K.A be its age algebra. If A′ is an initial segment
of A then:
(i) The vector subspace J := K.(A \ A′) spanned by A \ A′ is an ideal of K.A.
Moreover, the quotient of K.A by J is a ring isomorphic to the ring K.A′.
(ii) If this ideal is irreducible then A′ is a subage of A.
(iii) This is a prime ideal if and only if A′ is an inexhaustible age.
The proof of Item (i) and Item (ii) are immediate. The proof of Item (iii) is
essentially based on Theorem 0.2.
According to Item (i), F (A) embeds into the collection of ideals of K.A). Conse-
quently:
Corollary 0.17. If an age algebra is finitely generated then the age is well-quasi-
ordered by embeddability.
Problem 4. How the finite generation of an age algebra translates in terms of em-
beddability between members of the ages?
0.4.5. Links with language theory. In the theory of languages, one of the basic results
is that the generating series of a regular language is a rational fraction (see [1]). This
result is not far away from our considerations. Indeed, if A is a finite alphabet, with
say k elements, and A∗ is the set of words over A, then each word can be viewed as a
finite chain coloured by k colors. Hence A∗ can be viewed as the age of the relational
structure R made of the chain Q of rational numbers divided into k colors in such
a way that, between two distinct rational numbers, all colors appear. Moreover, as
pointed out by Cameron [6], the age algebra Q.A(R) is isomorphic to the shuffle
algebra over A, an important object in algebraic combinatorics (see [21]).
Problem 5. Does the members of the age of a relational structure with polynomial
growth can be coded by words forming a regular language?
Problem 6. Extend the properties of regular languages to subsets of the collection
Ωµ made of isomorphic types of finite relational structures with signature µ.
1. Proof of Theorem 0.3
The proof idea of Theorem 0.3 is very simple and we give it first.
We prove the result by induction. We suppose that it holds for pairs (m − 1, n).
Now, let f : [E]m → K and g : [E]n → K such that fg is zero, but f and g are not.
As already mentionned, m and n are non zero, hence members of supp(f) ∪ supp(g)
are non empty. Let sup(f, g) := {(A,B) ∈ supp(f) × supp(g) : A ∩ B = ∅}. We
may suppose sup(f, g) 6= ∅, otherwise the conclusion of Theorem 0.3 holds with t :=
m+ n− 1. For the sake of simplicity, we suppose that K := Q. In this case, we color
elements A of [E]m into three colors :-,0, +, according to the value of f(A). We do the
same with elements B of [E]n and we color each member (A,B) of supp(f, g) with the
colors of its components. With the help of Ramsey’ theorem and a lexicographical
ordering, we prove that if the transversality is large enough there is an (m+n)-element
subset Q such that all pair (A,B) ∈ supp(f, g)(Q) := supp(f, g)∩ ([Q]m × [Q]n) have
10 MAURICE POUZET
the same color. This readily implies that fg(Q) 6= 0, a contradiction. If K 6= Q, we
may replace the three colors by five, as the following lemma indicates.
Lemma 1.1. Let K be a field with characteristic zero. There is a partition of K∗ :=
K \ {0} into at most four blocks such that for every integer k and every k-element
sequences (α1, . . . , αk) ∈ D
k , (β1, . . . , βk) ∈ D
′k, where D, D′ are two blocks of the
partition of K∗, then
i=1 αiβi ∈ K
Proof. This holds trivially if K := C. For an example, divide C∗ into the sets
Di := {z ∈ C
∗ : πi
≤ Argz <
π(i+1)
} (i < 4). If K is arbitrary, use the Com-
pactness theorem of first-order logic, under the form of the ”diagram method” of
A.Robinson [18]. Namely, to the language of fields, add names for the elements of
K, a binary predicate symbol, and axioms, this in such a way that a model, if any,
of the resulting theory T will be an extension of K with a partition satisfying the
conclusion of the lemma. According to the Compactness theorem of first-order logic,
the existence of a model of T , alias the consistency of T , reduces to the consistency of
every finite subset A of T . A finite subset A of T leads to a finitely generated subfield
of K. Such subfield is isomorphic to a subfield of C (see [18] Example 2, p.99, or [2]
Proposition 1, p. 108). This latter subfield equipped with the partition induced by
the partition existing on C∗ satisfies the conclusion of the lemma, hence is a model
of T , proving that A is consistent.
Let T∗ be the set of these four blocks, let T := T∪{0} and let χ be the map from
K onto T.
1.1. Invariant relational structures and their age algebra.
1.1.1. Isomorphism, local isomorphism. Let R := (E, (ρi)i∈I) and R
′ := (E ′, (ρ′i)i∈I)
be two relational structures having the same signature µ := (mi)i∈I . A map h : E →
E ′ is an isomorphism from R onto R′ if
(1) h is bijective,
(2) (x1, . . . , xmi) ∈ ρi if and only if (h(x1), . . . , h(xmi)) ∈ ρ
i for every (x1, . . . , xmi) ∈
Emi , i ∈ I.
A partial map of E is a map h from a subset A of E onto a subset A′ of E, these
subsets are the domain and codomain of h. A local isomorphism of R if a partial map
h which is an isomorphism from R↾A onto R↾A′ (where A and A
′ are the domain an
codomain of h).
1.1.2. Invariant relational structures. A chain is a pair L := (C,≤) where ≤ is a
linear order on C. Let L be a chain. Let V be a non-empty set, F be a set disjoint
from V ×C and let E := F ∪ (V ×C). Let R be a relational structure with base set
E. Let r be a non-negative integer, r ≤ |C|. Let X,X ′ ∈ [C]r. Let ℓ be the unique
order isomorphism from L↾X onto L↾X′ and let ℓ := 1F ∪ (1V , ℓ) be the partial map
such that ℓ(x) = x for x ∈ F and ℓ(x, y) = (x, ℓ(y)) for (x, y) ∈ V ×X .
We say that X and X ′ are equivalent if ℓ is an isomorphism of H↾F∪V×X onto
H↾F∪V×X′. This defines an equivalence relation on [C]
A CONJECTURE OF P.J. CAMERON 11
We say that R is r−F−L-invariant if two arbitrary members of [C]r are equivalent.
We say that R is F − L-invariant if it is r − F − L-invariant for every non-negative
integer r, r ≤ |C|.
It is easy to see that if the signature µ of R is bounded and r :=Max({mi : i ∈ I}),
R is F −L-invariant if and only if it is r′ − F − L-invariant for every r′ ≤ r. In fact:
Lemma 1.2. If |C| > r :=Max({mi : i ∈ I}), R is F −L-invariant if and only if it
is r − F − L-invariant.
This is an immediate consequence of the following lemma:
Lemma 1.3. If R is r−F −L-invariant and r < |C| then R is r′ −F −L-invariant
for all r′ ≤ r.
Proof. We only prove that R is (r− 1)− F − L-invariant. This suffices. Let X,X ′ ∈
[C]r−1. Since r < |C|, we may select Z ∈ [C]r such that the last element of Z (w.r.t.
the order L) is strictly below some element c ∈ C.
Claim 1.4. There are Y, Y ′ ∈ [Z]r−1 which are equivalent to X and X ′ respectively.
Proof of Claim 1.4. Extend X and X ′ to two r-element subsets X1 and X
1 of C.
Since R is r− F −L-invariant, X1 is equivalent to Z, hence the unique isomorphism
from L↾X1 onto L↾Z carries X onto an equivalent subset Y of Z. By the same token,
X ′1 is equivalent to a subset Y
′ of Z.
Claim 1.5. Y and Y ′ are equivalent.
Proof of Claim 1.5. The unique isomorphism from L↾Y ∪{c} onto L↾Y ′∪{c} carries
Y onto Y hence T and Y ′ are equivalent.
From the two claims above X and X ′ are equivalent. Hence, R is (r− 1)− F −L-
invariant.
1.1.3. Coding by words. Let A := P(V ) \ {∅}. Let A∗ :=
Ap be the set of
finite sequences of members of A. A finite sequence u being viewed as a word on the
alphabet A, we write it as a juxtaposition of letters and we denote by λ the empty
sequence; the length of u, denoted by |u| is the number of its terms. Let p be a non
negative integer. If X is a subset of p := {0, . . . , p − 1} and u a word of length p,
the restriction of u to X induces a word that we denote by t(u↾X). We suppose that
V is finite and we equip A with a linear order. We compare words with the same
length with the lexicographical order, denoted by ≤lex. We record without proof the
following result.
Lemma 1.6. Let p, q be two non negative integers and X be an p-element subset of
p + q := {0, . . . , p + q − 1}. The map from Ap × Aq into Ap+q which associates to
every pair (u, v) ∈ Ap × Aq the unique word w ∈ Ap+q such that t(w↾X) = u and
t(w↾p+q\X) = v is strictly increasing (w.r.t. the lexicographical order).
This word w is a shuffle of u and v that we denote uX v. We denote by u ̂ v the
largest word of the form uX v.
We order A∗ with the radix order defined as follows: if u and v are two distincts
words, we set u < v if and only if either |u| < |v| or |u| = |v| et u <lex v. We suppose
12 MAURICE POUZET
that F is finite and we order P(F ) in such a way that X < Y implies |X| ≥ |Y |.
Finally, we order P(F )×A∗ lexicographically.
Let L := (C,≤). Let Q be a finite subset of E := F ∪ (V × C). Let proj(Q) :=
{i ∈ C : Q ∩ V × {i} 6= ∅}. Let i0, . . . , ip−1 be an enumeration of proj(Q) in an
increasing order (w.r.t L) and let w(Q \ F ) be the word u0 . . . up−1 ∈ A
∗ such that
Q \ F = u0 ×{i0} ∪ · · · ∪ up−1 × {ip−1}. We set w(Q) := (Q∩ F,w(Q \ F )). If Q is a
subset of [E]<ω, we set w(Q) := {w(Q) : Q ∈ Q}. If f : [E]m → K, let lead(f) := −∞
if f = 0 and otherwise let lead(f) be the largest element of w(supp(f)). We show
below that this latter parameter behaves as the degree of a polynomial.
We start with an easy fact.
Lemma 1.7. Let m and n be two non negative integers, A ∈ [E\F ]m and B ∈ [E]n. If
|C| ≥ m+n there is A′ ∈ [E\F ]m such that proj(A′)∩proj(B) = ∅ and w(A′) = w(A).
Lemma 1.8. Let R be an F − L-invariant structure on E. Let m and n be two
non negative integers; let f : [E]m → K, g : [E]n → K be two non zero members
of K.A(R). Let A0 ∈ supp(f), and B0 ∈ supp(g) such that w(A0) = lead(f) and
w(B0) = lead(g). Suppose that F and V are finite, that |C| ≤ n +m and supp(f) ∩
[E \ F ]m 6= ∅. Then:
(7) supp(f, g) 6= ∅.
(8) (w(A), w(B)) = (lead(f), lead(g)).
for all (A,B) ∈ supp(f, g)(Q0), where w(Q0) = lead(f, g) and lead(f, g) is the largest
element of w({A ∪ B : (A,B) ∈ supp(f, g)}).
(9) (f(A), g(B)) = (f(A0), g(B0))
for every (A,B) ∈ supp(f, g)(Q0).
(10) fg(Q0) = |supp(f, g)(Q0)|f(A0)g(B0).
(11) lead(fg) = lead(f, g) = (Q0 ∩ F,w(A0)̂w(B0 \ F )).
Proof. (1) Proof of (7). Since supp(f) ∩ [E \ F ]m 6= ∅ and the order on P(F )
decreases with the size, A0 is disjoint from F . Let B ∈ supp(g). According to
Lemma 1.7 there is A′ such that proj(A′) ∩ proj(B) = ∅ and w(A′) = w(A0).
We have A′ ∩ B = ∅ and, since f ∈ K.A(R) and R is F − L-invariant,
f(A′) = f(A0). Thus (A
′, B) ∈ supp(f, g).
(2) Proof of (8). Let (A,B) ∈ supp(f, g)(Q0). Since A ∈ supp(f) and B ∈
supp(g), we have trivially:
(12) w(A) ≤ lead(f) and w(B) ≤ lead(g).
Claim 1.9. B ∩ F = Q0 ∩ F and A ∩ F = ∅.
A CONJECTURE OF P.J. CAMERON 13
The pair (A′, B) obtained in the proof of (7) belongs to supp(f, g). Let
Q′ := A′ ∪ B. By maximality of w(Q0), we have w(Q
′) ≤ w(Q0). If B ∩ F 6=
Q0 ∩ F , then |Q
′ ∩ F | < |Q0 ∩ F |, hence w(Q0) < w(Q
′). A contradiction.
The fact that A ∩ F = ∅ follows.
Claim 1.10. proj(A) ∩ proj(B) = ∅ and |proj(A)| = |proj(B).|
Apply Lemma 1.7. Let A′ such that proj(A′) ∩ proj(B) = ∅ and w(A′) =
w(A). Since f ∈ K.A(R) and R is F − L-invariant, f(A′) = f(A) thus
(A′, B) ∈ supp(f, g). Set Q′ := A′ ∪ B. We have w(Q′ \ F ) ≤ w(Q0 \ F )
hence |w(Q′)| ≤ |w(Q0)|. Since |w(Q
′ \ F )| = |proj(A′)| + |proj(B)| and
|w(Q0\F )| ≤ |proj(A)|+|proj(B)|, we get |w(Q0\F )| = |proj(A)|+|proj(B)|.
This proves our claim.
Let i0, . . . , ir−1 be an enumeration of proj(Q0 \ F ) in an increasing order.
Let X := {j ∈ r : ij ∈ proj(A)}. Since proj(A)∩proj(B) = ∅, we have w(Q0\
F ) = w(A)X w(B \ F ). Since w(A) ≤ w(A0) and |w(A)| = |w(A0)|, Lemma
1.6 yields w(Q0 \ F ) ≤ w(A0)X w(B). As it is easy to see, there is A
0 such
that w(A′0) = w(A0) and Q
′ := A′0 ∪ B satisfies w(Q
′ \ F ) = w(A0)X w(B).
Since (A′, B) ∈ supp(f, g), we have w(Q′) = w(Q0) by maximality of w(Q0).
With Lemma 1.6 again, this yields w(A) = w(A0). Hence w(A) = w(A0). A
similar argument yields w(B \F ) = w(B0 \F ) and also w(B \F ) = w(B0 \F ).
(3) Proof of (9). Since R is F −L-invariant, from w(A) = lead(f) := w(A0) we
get f(A) = f(A0). By the same token, we get g(B) = g(B0).
(4) Proof of (10). Since fg(Q0) =
(A,B)∈sup(f,g) f(A)g(B) the result follows
from (9).
(5) Proof of (11). From (10), fg(Q0) 6= 0, the equality lead(fg) = lead(f, g)
follows. The remaining equality follows from (8).
With this, the proof of the lemma is complete.
As far as invariant structures are concerned, we can retain this:
Corollary 1.11. Under the hypotheses of Lemma 1.12, fg 6= 0.
1.1.4. An application. Letm,n be two positive integers, E be a set and f : [E]m → K,
g : [E]n → K. Let R := (E, (ρ(i,j))(i,j)∈T∗×2)) be the relational structure made of the
four m-ary relations ρ(i,0) := {(x1, . . . , xm) : χ ◦ f({x1, . . . , xm}) = i} and the four n-
ary relations ρ(i,1) := {(x1, . . . , xn) : χ ◦ g({x1, . . . , xn}) = i}. A map h from a subset
A of E onto a subset A′ of E is a local isomorphism of R if χ ◦ f(P ) = χ ◦ f(h[P ])
and χ ◦ f(R) = χ ◦ f(h[R]) for every P ∈ [A]m, every R ∈ [A]n. This fact allows us
to consider the pair H := (E, (χ ◦ f, χ ◦ g)) as a relational structure. In the sequel we
suppose that E = F ∪ (V × C) with F and V finite; we fix a chain L := (C,≤).
Lemma 1.12. Suppose that there are P ∈ supp(f) ∩ [V × C]m and R ∈ supp(g) ∩
[E \ P ]n. If H is F − L-invariant and |C| ≥ m+ n. Then fg 6= 0.
Proof. Let lead(f, g) be the largest element of w({A ∪ B : (A,B) ∈ supp(f, g)}) and
let Q0 such that w(Q0) = lead(f, g).
14 MAURICE POUZET
Claim 1.13. (χ ◦ f(A), χ ◦ g(B)) is constant for (A,B) ∈ sup(f, g)(Q0).
Proof of Claim 1.13. Let s : T → K be a section of χ. Let f ′ := s ◦ χ ◦ f and
let g′ := s ◦ χ ◦ g. Then f ′, g′ ∈ K.A(H) and supp(f ′, g′) = supp(f, g). According to
Equation (9) of Lemma 1.8, (f ′(A), g′(B)) is constant for (A,B) ∈ supp(f ′, g′)(Q0).
The result follows.
From Lemma 1.1, fg(Q0) :=
(A,B)∈sup(f,g)(Q0)
f(A)g(B) 6= 0.
We recall the finite version of the theorem of Ramsey [32], [16].
Theorem 1.14. For every integers r, k, l there is an integer R such that for every
partition of the r-element subsets of a R-element set C into k colors there is a l-
element subset C ′ of C whose all r-element subsets have the same color.
The least integer R for which the conclusion of Theorem 1.14 holds is a Ramsey
number that we denote Rrk(l).
Let m and n be two non negative integers. Set r := Max({m,n}), s :=
, k := 5s and, for an integer l, l > r, set ν(l) := Rrk(l).
Lemma 1.15. If |F | = n, |V | = m and |C| ≥ ν(l) there is an l-element subset C ′ of
C such that H↾F∪V×C′ is F − L↾C′-invariant.
The proof is a basic application of Ramsey theorem. We give it for reader conve-
nience. See [13] 10.9.4 page 296, or [27] Lemme IV.3.1.1 for a similar result).
Proof. The number of equivalence classes on [C]r is at most k := 5s (indeed, this
number is bounded by the number of distinct pairs (χ◦f ′, χ◦g′) such that f ′ ∈ K[E
g′ ∈ K[E
′]n and |E ′| = n+mr). Thus, according to Theorem 1.14, there is a l-element
subset C ′ of C whose all r-element subsets are equivalent. This means that H↾F∪V×C′
is r − F − L↾C′ -invariant. Now, since r < l, Lemma 1.3 asserts that H↾F∪V×C′ is
r′ − F − L↾C′-invariant for all r
′ ≤ r. Since the signature of H is bounded by r,
H↾F∪V×C′ is F − L↾C′ -invariant from Lemma 1.2.
1.2. The existence of τ(m,n). Let m and n be two non negative integers. Suppose
1 ≤ m ≤ n and that τ(m− 1, n) exists. Let E be a set with at least m+ n elements
and f : [E]m → K, g : [E]n → K such that fg is zero, but f and g are not.
Lemma 1.16. Let A be a transversal for supp(f). Then there is a transversal B for
supp(g) such that:
(13) |B \ A| ≤ τ(m− 1, n)
Proof. Among the sets P ∈ supp(f) select one, say P0, such that F0 := P0 ∩ A has
minimum size, say r0.
Case 1. A∪P0 is also a transversal for supp(g). In this case, set B := A∪P0. We
have |B \ A| ≤ m− 1, hence inequality (13) follows from inequality (14) below:
(14) m− 1 ≤ τ(m− 1, n)
This inequality is trivial for m = 1. Let us prove it for m > 1 (a much better
inequality is given in Lemma 3.1). Let E ′ be an m + n − 1-element set, let f ′ :
[E ′]m−1 → K and g′ : [E ′]n → K, with f ′ non zero on a single m − 1-element set A′,
A CONJECTURE OF P.J. CAMERON 15
g′(B′) = 1 if A′ ∩ B′ 6= ∅ and g′(B′) = 0 otherwise. Since m − 1 and n are not 0, f ′
and g′ are not 0. Trivially, f ′g′ = 0 and, as it easy to check, A′ is a transversal for
supp(f ′) ∪ supp(g′) having minimum size, hence τ(supp(f ′) ∪ supp(g′)) = m− 1.
Case 2. Case 1 does not hold. In this case, pick x0 ∈ F0 and set E
′ := (E \ A) ∪
(F0 \ {x0}). Let f
′ : [E ′]m−1 → K be defined by setting f(P ′) := f(P ′ ∪ {x0}) for all
P ′ ∈ [E ′]m−1 and let g′ := g↾[E′]n .
Claim 1.17. |E ′| ≥ m+ n− 1 and f ′g′ = 0.
Proof of Claim 1.17. The inequality follows from the fact that A ∪ P0 is not a
transversal for supp(g). Now, let Q′ ∈ [E ′]m+n−1 and Q := Q′ ∪ {x0}.
(15) f ′g′(Q′) =
P ′∈[Q′]m−1
f ′(P ′)g′(Q′ \ P ′) =
x0∈P∈[Q]m
f(P )g(Q \ P )
Since fg = 0 we have:
0 = fg(Q) =
P∈[Q]m
f(P )g(Q \P ) =
x0∈P∈[Q]m
f(P )g(Q \P ) +
x0 6∈P∈[Q]m
f(P )g(Q \P )
If x0 6∈ P , |P ∩ A| < r0, hence f(P ) = 0. This implies that the second term in the
last member of (16) is zero, hence the second member of (15) is zero. This proves our
claim.
From our hypothesis A ∪ P0 is not a tranversal for g. Hence, we have
Claim 1.18. f ′ and g′ are not zero.
The existence of τ(m − 1, n) insures that there is a transversal H for supp(f ′) ∪
supp(g′) of size at most τ(m − 1, n). The set B := A ∪ H is a transversal for
supp(f) ∪ supp(g).
Lemma 1.19. Let l be a positive integer. If τ(supp(f) ∪ supp(g)) > n +m(l − 1) +
τ(m − 1, n) then for every F ∈ supp(g) there is a subset P ⊆ supp(f) ∩ [E \ F ]m
made of at least l pairwise disjoint sets.
Proof. Fix F ∈ supp(g). Let P ⊆ supp(f) ∩ [E \ F ]m be a finite subset made of
pairwise disjoint sets and let p := |P|. If the conclusion of the lemma does not hold,
we have p < l. Select then P with maximum size and set A := F ∪
P. Clearly A is
a transversal for supp(f). According to Lemma 1.16 above, τ(supp(f) ∪ supp(g)) ≤
|A|+ τ(m − 1, n) = n +mp + τ(m− 1, n). Thus, according to our hypothese, l ≤ p.
A contradiction.
Let ϕ(m,n) := n+m(ν(n +m)− 1) + τ(m− 1, n).
Lemma 1.20.
(17) τ(m,n) ≤ ϕ(m,m)
Proof. Suppose τ(supp(f) ∪ supp(g)) > ϕ(m,n). Let F ∈ supp(g). According to
Lemma 1.19 there is a subset P ⊆ supp(f) ∩ [E \ F ]m made of at least ν(n + m)
pairwise disjoint sets. With no loss of generality, we may suppose that ∪P is a set
16 MAURICE POUZET
of the form V × C where |V | = m and |C| = ν(m,n). Let ≤ be a linear order on C
and L := (C,≤). According to Lemma 1.15 there is an n +m-element subset C ′ of
C such that H↾F∪V×C′ is F − L↾C′-invariant. According to Lemma 1.12 fg 6= 0. A
contradiction.
With Lemma 1.20, the proof of Theorem 0.3 is complete.
Note that ϕ(1, 2) = 1 + R2
(3) + τ(0, n) = R2
(3), whereas τ(1, 2) = 4. Also
ϕ(2, 2) = 2R2
(4) + τ(1, 2) = 2(R2
(4) + 2).
Our original proof of Theorem 0.3 was a bit simpler. Instead of an m-element set
F and several pairwise disjoint n-element sets, we considered several pairwise n+m-
element sets. In the particular case of m = n = 2, we got τ(2, 2) ≤ 4R2
(4) + 1. In
term of concrete upper-bounds, we are not convinced that the improvement worth
the effort.
2. The Gottlieb-Kantor theorem and the case m = 1
Let E be a set. To each x ∈ E associate an indeterminate Xx. Let K[E] be the
algebra over the field K of polynomials in these indeterminates. Let f : [E]1 → K. Let
Df be the derivation on this algebra which is induced by f , that is Df(Xx) := f({x})
for every x ∈ E. Let ϕ : K[E] → K[E] be the ring homomorphism such that ϕf (1) :=
1 and ϕf(Xx) := f({x})Xx. Let e : [E]
1 → K be the constant map equal to 1 and
let De be the corresponding derivation. For example Df(XxXyXz) = f({x})XyXz +
f({y})XxXz + f({z})XxXy whereas De(XxXyXz) = XyXz + XxXz + XxXy. It is
easy to check that:
(18) De ◦ ϕf = ϕf ◦Df .
Let n be a non negative integer; let K[n][E] be the vector space generated by the
monomials made of n distinct variables. From equation (18), we deduce:
Corollary 2.1. If f does not take the value zero on [E]1, the surjectivity of the maps
from K[n+1][E] into K[n][E] induced by Df and De are equivalent.
Suppose that E is finite. In this case, the matrix of the restriction ofDe to K[n+1][E]
identifies to Mn,n+1. Thus, according to Theorem 0.7, De is surjective provided that
|E| ≥ 2n+ 1. Corollary asserts that in this case, Df is surjective too. This yields:
Lemma 2.2. If f does not take the value zero on a subset E ′ of E of size at least
2n + 1 but fg = 0 for some g : [E]n → K then g is zero on the n-element subsets of
Proof. Suppose that fg = 0. Let g : K[n][E] → K be the linear form defined by
setting g(Πx∈BXx) := g(B) for each B ∈ [E]
n. Then g ◦Df is 0 on K[n+1][E]. From
Corollary 2, the map from K[n+1][E
′] into K[n][E
′] induced by Df is surjective. Hence
g is 0 on K[n][E
′]. Thus g is zero on [E ′]n as claimed.
Going a step further, we get a weighted version of Gottlieb-Kantor theorem:
Theorem 2.3. Let f : [E]1 → K and g : [E]n → K. If f does not take the value zero
on a subset of size at least 2n+ 1 and if fg = 0 then g est identically zero on [E]n.
A CONJECTURE OF P.J. CAMERON 17
Proof. Set E ′ := supp(f). According to our hypothesis, E ′ 6= ∅. We prove the lemma
by induction on n. If n = 0, pick x ∈ E ′. We have fg({x}) = f({x})g(∅). Since
f({x}) 6= 0 and K is an integral domain, g(∅) = 0. Thus g = 0 and the conclusion of
the lemma holds for n = 0. Let n ≥ 1. Let B ∈ [E]n. We claim that g(B) = 0. Let
F := B \E ′ and r := |F |. If r = 0, that is B ⊆ E ′, we get g(B) = 0 from Lemma 2.2.
If r 6= 0, we define gr on [E
′]n−r, setting gr(B
′) := g(B′ ∪ F ) for each B′ ∈ [E ′]n−r.
Let Q′ ∈ [E ′]n−r+1 and Q := Q′ ∪ F . We have fgr(Q
x∈Q′ f({x})g(Q \ {x}) =∑
x∈Q f({x})g(Q \ {x}) −
x∈F f({x})g(Q \ {x}). From our hypothesis on g and
the fact that f({x}) = 0 for all x /∈ E ′, both terms on the right hand side of the
latter equality are 0, thus fgr(Q
′) = 0. Since |E ′| ≥ 2(n − r) + 1, induction on n
applies. Hence gr is 0 on [E
′]n−r. This yields g(B) = 0, proving our claim. Hence the
conclusion of the lemma holds for n.
Theorem 2.4. τ(1, n) = 2n
Proof. Trivially, the formula holds if n = 0. Hence, in the sequel, we suppose n ≥ 1.
Claim 2.5. τ(1, n) ≤ 2n
Proof of Claim 2.5.Let f and g be non identically zero such that fg = 0. From
Theorem 2.3, the support S of f has at most 2n elements. From Lemma 1.16
|supp(f) ∪ (supp(g)| ≤ |S|+ τ(0, n) = |S| ≤ 2n.
For the converse inequality, we prove that:
Claim 2.6. There is a 2n element set E and a map g : [E]n → K such that eg = 0
and g 6= 0.
Proof of Claim 2.6 Let E := {0, 1} × {0, . . . , n− 1}. Set Ei := {0, 1} × {i} for
i < n. Let B ∈ [E]n. Set g(B) := 0 if B is not a transversal of the Ei’s, g(B) := −1 if
B is a transversal containing an odd number of elements of the form (0, i), g(B) = 1
otherwise. Let Q ∈ [E]n+1. If Q is not a transversal of the Ei’s then g(B) = 0 for
every B ∈ [Q]n hence eg(Q) = 0. If Q is a transversal, then there is a unique index i
such that Ei ⊆ Q. In this case, the only members of [Q]
n on which g is non-zero are
Q\{(0, i)} and Q\{(1, i)}; by our choice, they have opposite signs, hence eg(Q) = 0.
Since in the example above τ(supp(e)) = 2n, we have τ(1, n) ≥ 2n. With this
inequality, the proof of Theorem 2.4 is complete.
3. A lower bound for τ(m,n)
Lemma 3.1. τ(m,n) ≥ (m+ 1)(n+ 1)− 2 for all m,n ≥ 1.
Proof. For m = 1 this inequality was obtained in Claim 2.6. For the case m > 1, we
need the following improvement of Claim 2.6.
Claim 3.2. Let n ≥ 1. There is a 2n element set E and a map g : [E]n → K such
that eg = 0 and supp(g) = [E]n.
Proof of Claim 3.2. Fix a 2n-element set E. From Claim 2.6 and the fact that the
symmetric group SE acts transitively on [E]
n, we get for each B ∈ [E]n some gB such
that egB = 0 and B ∈ supp(gB). Next, we observe that a map g : [E]
n → K satisfies
18 MAURICE POUZET
eg = 0 if and only if g belongs to the kernel of the linear map T : K[E]
→ K[E]
defined by setting T (g)(Q) :=
B∈[Q]n g(B) for all g, Q ∈ [E]
n+1. To conclude, we
apply the claim below with k :=
Claim 3.3. Let e1 := (1, 0 . . . , 0), . . . , ei := (0, . . . , 1, 0, . . . , 0), . . . , ek := (0, . . . , 1) be
the canonical basis of Kk and let H be a subspace of Kk. Then H contains a vector
with all its coordinates which are non-zero if and only if for every coordinate i it
contains some vector with this coordinate non-zero.
Proof of Claim 3.3. This assertion amounts to the fact that a vector space on
an infinite field is not the union of finitely many proper subspaces.
Let E be the disjoint union of m sets E0, . . . , Ei, . . . Em−1, each of size 2n. For
each i, let gi : [Ei]
n → K such that
B∈[Q]n gi(B) = 0 for each Q ∈ [Ei]
n+1 and
supp(gi) = [Ei]
n (according to Claim 3.2 such a gi exists). Let g : [E]
n → K be
the ”direct sum” of the gi’s: g(B) := gi(B) if B ∈ [Ei]
n, g(B) := 0 otherwise. Let
f : [E]m → K defined by setting f(A) := 1 if A ∩ Ei 6= ∅ for all i < m and 0
otherwise. Then, by a similar argument as in Claim 2.6, fg = 0. Next, a transversal
of supp(f) must contains some Ei (thus τ(supp(f)) = 2n). And, also, a transversal
of supp(g) must be a transversal of each of the supp(gi)’s. Since supp(gi) = [Ei]
τ(supp(gi)) = n + 1, hence τ(supp(g)) = (n + 1)m. We get easily that τ(supp(f) ∪
supp(g)) = 2n + (n + 1)(m − 1) = mn + m + n − 1. This completes the proof of
Lemma 3.1.
Example 3.4. The lemma above gives τ(2, 2) ≥ 7. An example illustrating this
inequality is quite simple: let E be made of two squares, let f be the map giving value
−1/2 on each side of the squares, value 1 on the diagonals; let g be giving value 1
on each pair meeting the two squares. Then for every x ∈ E, E \ {x} is a minimal
transversal of supp(f) ∪ supp(g).
References
[1] J. Berstel, C. Retenauer. Les séries rationnelles et leurs langages. Études et recherches en
Informatique. Masson, Paris, 1984,132 pp.
[2] N. Bourbaki. Éléments de mathématiques, Fasc. XI. Algèbre, Chap. V, Actualités scientifiques
et industrielles, Hermann, Paris, 1973.
[3] P. J. Cameron. Transitivity of permutation groups on unordered sets, Math. Z., 48(1976)127-
[4] P.J. Cameron. Orbits of permutation groups on unordered sets. II. J. London Math. Soc., (2)
23 (1981), no. 2, 249–264.
[5] P.J. Cameron.Oligomorphic permutation groups. Cambridge University Press, Cambridge, 1990.
[6] P.J. Cameron. The algebra of an age. In Model theory of groups and automorphism groups
(Blaubeuren, 1995), pages 126–133. Cambridge Univ. Press, Cambridge, 1997.
[7] P.J. Cameron. On an algebra related to orbit-counting. J. Group Theory 1 (1998), no. 2, 173–
[8] P.J. Cameron. Sequences realized by oligomorphic permutation groups. J. Integer Seq., 3(1):Ar-
ticle 00.1.5, 1 HTML document (electronic), 2000.
[9] P.J. Cameron. Some counting problems related to permutation groups. Discrete Math., 225(1-
3):77–92, 2000. Formal power series and algebraic combinatorics (Toronto, ON, 1998).
[10] P.J. Cameron.Problems on permutation groups, http://www.maths.qmul.ac.uk/∼pjc/pgprob.html.
http://www.maths.qmul.ac.uk/~pjc/pgprob.html
A CONJECTURE OF P.J. CAMERON 19
[11] R. Diestel. Graph Theory. Springer-Verlag, Heidelberg Graduate Texts in Mathematics, Volume
173, 2005, 431 pages.
[12] R. Fräıssé. Cours de logique mathématique. Tome 1: Relation et formule logique. Gauthier-
Villars Éditeur, Paris, 1971.
[13] R. Fräıssé. Theory of relations. North-Holland Publishing Co., Amsterdam, 2000.
[14] R. Fräıssé and Maurice Pouzet. Interprétabilité d’une relation pour une châıne. C. R. Acad.
Sci. Paris Sér. A-B, 272:A1624–A1627, 1971.
[15] D.H. Gottlieb. A class of incidence matrices, Proc. Amer. Math. Soc., 17(1966)1233-1237.
[16] R. Graham, B. Rothschild, J.H. Spencer, Ramsey Theory, John Wiley and Sons, NY (1990).
[17] G. Higman. Ordering by divisibility in abstract algebras. Proc. London Math. Soc. (3), 2:326–
336, 1952.
[18] W. Hodges, Model Theory, Cambridge University Press, Cambridge, 1993. xiv+772 pp.
[19] W.M. Kantor. On incidence matrices of finite projective and affine spaces, Math. Z.,
124(1972)315–318.
[20] D. Livingstone, A. Wagner, Transitivity of finite permutation groups on unordered sets. Math.
Z., 90(1965) 393-403.
[21] M. Lothaire. Combinatorics on words. Vol. 17 of Encyclopedia of Mathematics and its Appli-
cations. Addison-Wesley, Reading, Mass. Reprinted in the Cambridge Mathematical Library,
Cambridge University Press, U.K. 1997.
[22] H.D. Macpherson. Growth rates in infinite graphs and permutation groups. Proc. London Math.
Soc. (3), 51(2):285–294, 1985.
[23] M. Pouzet. Application d’une propriété combinatoire des parties d’un ensemble aux groupes et
aux relations. Math. Z., 150(2):117–134, 1976.
[24] M. Pouzet. Sur la théorie des relations. Thèse d’état, Université Claude-Bernard, Lyon 1, 1978.
[25] M. Pouzet. Relation minimale pour son âge. Z. Math. Logik Grundlag. Math., 25(1979) 315–344.
[26] M. Pouzet. Application de la notion de relation presque-enchâınable au dénombrement des
restrictions finies d’une relation. Z. Math. Logik Grundlag. Math., 27(4):289–332, 1981.
[27] M. Pouzet. Relation impartible. Dissertationnes, 103(1981)1–48.
[28] M. Pouzet. The profile of relations. Glob. J. Pure Appl.Math. Volume 2, Number 3 (2007), pp.
237–272 (Proceedings of the 14th Symposium of the Tunisian Mathematical Society held in
Hammamet, March 20-23, 2006). ArXiv math.CO/0703211.
[29] M. Pouzet and M. Sobrani. Sandwiches of ages. Ann. Pure Appl. Logic, 108 (3)(2001) 295–326.
[30] M. Pouzet, N. Thiéry. Some relational structures with polynomial growth and their associ-
ated algebras. May 10th, 2005, 19pages, presented at FPSAC for the 75 birthday of A.Garsia.
http://arxiv.org/math.CO/0601256.
[31] D. E. Radford, A natural ring basis for the shuffle algebra and an application to group schemes,
J. Algebra 58 (1979), 432-454.
[32] F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc., 30 (1930) 264-286.
ICJ, Mathématiques, Université Claude-Bernard Lyon1, Domaine de Gerland, Bât.
Recherche [B], 50 avenue Tony-Garnier, F69365 Lyon cedex 07, France, e-mail: pouzet@univ-
lyon1.fr
http://arxiv.org/abs/math/0703211
http://arxiv.org/math.CO/0601256
	 Introduction
	0.1. The conjectures
	0.2. The algebra of an age
	0.3. A transversality property of the set algebra
	0.4. Age algebra and profile of a relational structure
	1. Proof of Theorem ??
	1.1. Invariant relational structures and their age algebra
	1.2. The existence of (m,n)
	2. The Gottlieb-Kantor theorem and the case m=1 
	3. A lower bound for (m,n)
	References

  P.J.Cameron introduced the orbit algebra of a permutation group and
conjectured that this algebra is an integral domain if and only if the group
has no finite orbit. We prove that this conjecture holds and in fact that the
age algebra of a relational structure $R$ is an integral domain if and only if
$R$ is age-inexhaustible. We deduce these results from a combinatorial lemma
asserting that if a product of two non-zero elements of a set algebra is zero
then there is a finite common tranversal of their supports. The proof is built
on Ramsey theorem and the integrity of a shuffle algebra.

Introduction
In 1981, P.J.Cameron [4] (see also [9] p.86) associated a graded algebra A[G] to a
permutation group G acting on an infinite set E. He formulated two conjectures on
the integrity of this algebra. The purpose of this paper is to present a solution to the
first of these conjectures. Consequences on the enumeration of finite substructures of
a given structure are mentionned. Some problems are stated.
0.1. The conjectures. Here is the content of these conjectures, freely adapted from
Cameron’s web page (see Problem 2 [10]). The graded algebra A[G] is the direct sum
A[G]n
where A[G]n is the set of all G-invariant functions f from the set [E]
n of n-element
subsets of E into the field C of complex numbers. Multiplication is defined by the
rule that if f ∈ A[G]m, g ∈ A[G]n and Q is an (m+ n)-element subset of E then
(1) (fg)(Q) :=
P∈[Q]m
f(P )g(Q \ P )
As shown by Cameron, the constant function e in A[G]1 (with value 1 on every one
element set) is not a zero-divisor (see Theorem 0.8 below). The group G is entire if
A[G] is an integral domain, and strongly entire if A[G]/eA[G] is an integral domain.
Date: November 6, 2018.
1991 Mathematics Subject Classification. 03 C13, 03 C52, 05 A16, 05 C30, 20 B27.
Key words and phrases. Relational structures, ages, counting functions, oligomorphic groups, age
algebra, Ramsey theorem, integral domain.
Research done under the auspices of Intas programme 03-51-4110 ”Universal algebra and lattice
theory” .
http://arxiv.org/abs/0704.1548v1
2 MAURICE POUZET
Conjectures 0.1. G is (strongly) entire if and only if it has no finite orbit on E.
The condition that G has no finite orbit on E is necessary. We prove that it suffices
for G to be entire. As it turns out, our proof extends to the algebra of an age, also
invented by Cameron [10].
0.2. The algebra of an age. A relational structure is a realization of a language
whose non-logical symbols are predicates. This is a pair R := (E, (ρi)i∈I) made of a
set E and a family of mi-ary relations ρi on E. The set E is the domain or base of
R; the family µ := (mi)i∈I is the signature of R. The substructure induced by R on
a subset A of E, simply called the restriction of R to A, is the relational structure
R↾A := (A, (A
mi ∩ ρi)i∈I). Notions of isomorphism, as well as isomorphic type, are
defined in natural way (see Subsection 1.1).
A map f : [E]m → C, where m is a non negative integer, is R-invariant if f(P ) =
f(P ′) whenever the restrictions R|P and R|P ′ are isomorphic. The R-invariant maps
can be multiplied. Indeed, it is not difficult to show that if f : [E]m → C and
g : [E]n → C are R-invariant, the product defined by Equation (1) is R-invariant.
Equipped with this multiplication, the C-vector space spanned by the R-invariant
maps becomes a graded algebra, the age algebra of R, that we denote by C.A(R).
The name, coined by Cameron, comes from the notion of age defined by Fräıssé [13].
Indeed, the age of R is the collection A(R) of substructures of R induced on the
finite subsets of R, isomorphic substructures being identified. And it can be shown
that two relational structures with the same age yields the same algebra (up to an
isomorphism of graded algebras).
The algebra associated to a group is a special case of age algebra. Indeed, to a
permutation group G acting on E we may associate a relational structure R with
base E such that the G-invariant maps coincide with the R-invariant maps.
Our criterium for the integrity of the age algebra is based on the notion of kernel:
The kernel of a relational structure R is the subset K(R) of x ∈ E such that
A(R|E\{x}) 6= A(R).
The emptyness of the kernel R is a necessary condition for the integrity of the
age algebra. Indeed, if K(R) 6= ∅, pick x ∈ K(R) and F ∈ [E]<ω such that R↾F ∈
A(R) \ A(R|E\{x}). Let P ∈ [E]
<ω. Set f(P ) := 1 if R↾P is isomorphic to R↾F ,
otherwise set f(P ) := 0. Then f 2 := ff = 0.
Theorem 0.2. Let R be a relational structure with possibly infinitely many non iso-
morphic types of n-element substructures. The age algebra C.A(R) is an integral
domain if and only if the kernel of R is empty.
The application to the conjecture of Cameron is immediate. LetG be a permutation
group acting on E and let R be a relational structure encoding G. Then, the kernel
of R is the union of the finite G-orbits of the one-element sets. Thus, if G has no
finite orbit, the kernel of R is empty. Hence from Theorem 0.2, A[G] is an integral
domain, as conjectured by Cameron.
We deduce Theorem 0.2 from a combinatorial property of a set algebra over a field
(Theorem 0.3 below). This property does not depends upon the field, provided that
its characteristic is zero. The proof we give in Section 1.1 is an extension of our
A CONJECTURE OF P.J. CAMERON 3
1970 proof that the profile of an infinite relational structure does not decrease (see
Theorem 0.5 below). The key tool we used then was Ramsey’s theorem presented in
terms of a property of almost-chainable relations. Here, these relations are replaced by
F −L-invariant relational structures, structures which appeared, under other names,
in several of our papers (see [24], [25], [27]). The final step is reminiscent of the proof
of the integrity of a shuffle algebra.
We introduced the notion of kernel in[24] and studied it in several papers [25] [26],
[27] and [29]. As it is easy to see (cf [25][29]), the kernel of a relational structure
R is empty if and only if for every finite subset F of E there is a disjoint subset F ′
such that the restrictions R|F and R|F ′ are isomorphic. Hence, relational structures
with empty kernel are those for which their age has the disjoint embedding property,
meaning that two arbitrary members of the age can be embedded into a third in
such a way that their domain are disjoint. In Fräıssé’s terminology, ages with the
disjoint embedding property are said inexhaustible and relational structures whose
age is inexhaustible are said age-inexhaustible; we say that relational structures with
finite kernel are almost age-inexhaustible. 1
0.3. A transversality property of the set algebra. Let K be a field with charac-
teristic zero. Let E be a set and let [E]<ω be the set of finite subsets of E (including
the empty set ∅). Let K[E]
be the set of maps f : [E]<ω → K. Endowed with the
usual addition and scalar multiplication of maps, this set is a vector space over K.
Let f, g ∈ K[E]
and Q ∈ [E]<ω. Set:
(2) fg(Q) =
P∈[Q]<ω
f(P )g(Q \ P )
With this operation added, the above set becomes a K-algebra. This algebra is
commutative and it has a unit, denoted by 1. This is the map taking the value 1
on the empty set and the value 0 everywhere else. The set algebra is the subalgebra
made of maps f such that f(P ) = 0 for every P ∈ [E]<ω with |P | large enough.
This algebra is graded, the homogeneous component of degree n being made of maps
which take the value 0 on every subset of size different from n (see Cameron [6]). If
f and g belong to two homogeneous components, their product is given by Equation
(1), thus an age algebra, or a group algebra, A, as previously defined, is a subalgebra
of this set algebra. The set algebra is far from to be an integral domain. But, with
the notion of degree, the integrity of A will reduce to the fact that if m and n are
two non negative integers and f : [E]m → K, f : [E]n → K are two non-zero maps
belonging to A, their product fg is non zero.
Let H be a family of subsets of E, a subset T of E is a transversal of H if F ∩T 6= ∅
for every F ∈ H; the transversality of H, denoted τ(H), is the minimum of the
cardinalities (possibly infinite) of transversals of H. We make the convention that
τ(H) = 0 if H is empty.
Let f : [E]m → K, denote supp(f) := {P ∈ [V ]m : f(P ) 6= 0}.
1In order to agree with Fräıssé’s terminology, we disagree with the terminology of our papers, in
which inexhaustibility, resp. almost inexhaustibility, is used for relational structures with empty,
resp. finite, kernel, rather than for their ages.
4 MAURICE POUZET
Here is our combinatorial result:
Theorem 0.3. Let m,n be two non negative integers. There is an integer t such that
for every set E with at least m + n elements, every field K with characteristic zero,
every pair of maps f : [E]m → K, g : [E]n → K such that fg is zero, but f and g are
not, then τ(supp(f) ∪ supp(g)) ≤ t.
With this result, the proof of Theorem 0.2 is immediate. Indeed, let R be a rela-
tional structure with empty kernel. If K.A(R), the age algebra of R over K, is not an
integral domain there are two non-zero maps f : [E]m → K, f : [E]n → K belonging
to K.A(R), whose product fg is zero. Since K is an integral domain, none of the in-
tegers m and n can be zero. Since f is R-invariant, m is positive and the kernel K(R)
of R is empty, it turns out that τ(supp(f)) is infinite. Hence τ(supp(f)∪ supp(g)) is
infinite, contradicting the conclusion of Theorem 0.3.
An other immediate consequence of Theorem 0.3 is the fact, due to Cameron, that
on an infinite set E, e is not a zero-divisor (see Theorem 0.8 below).
0.3.1. Existence and values of τ . The fact the size of a transversal can be bounded
independently of f and g, and the value of the least upper bound, seem to be of
independent interest.
So, let τ(m,n) be the least t for which the conclusion of Theorem 0.3 holds.
Trivially, we have τ(m,n) = τ(n,m). We have τ(0, n) = τ(m, 0) = 0. Indeed,
if m = 0, f is defined on the empty set only, an thus fg(Q) = f(∅)g(Q). Since
K has no non zero divisors, fg is non zero provided that f and g are non zero.
The fact that there is no pair f, g such that fg is zero, but f and g are not, yields
τ(supp(f) ∪ supp(g)) = 0.
We have τ(1, n) = 2n (Theorem 2.4). This is a non-trivial fact which essentially
amounts to a weighted version of the Gottlieb-Kantor Theorem on incidence matrices
([15], [19], see subsection 0.4 and Theorem 2.3). These are the only exact values
we know. We prove that τ(m,n) exists, by supposing that τ(m − 1, n) exists. Our
existence proof relies in an essential way on Ramsey theorem. It yields astronomical
upper bounds. For example, it yields τ(2, 2) ≤ 2(R2k(4) + 2) , where k = 5
30 and
R2k(4) is the Ramsey number equal to the least integer p such that for every colouring
of the pairs of {1, . . . , p} into k colors there are four integers whose all pairs have
the same colour. The only lower bound we have is τ(2, 2) ≥ 7 and more generally
τ(m,n) ≥ (m+ 1)(n + 1)− 2. We cannot preclude a extremely simple upper bound
for τ(m,n), eg quadratic in n+m.
0.4. Age algebra and profile of a relational structure. The group agebra was
invented by Cameron in order to study the behavior of the function θG which counts
for each integer n the number θG(n) of orbits of n-subsets of a set E on which acts a
permutation groupG, a function that we call the orbital profile ofG. Groups for which
the orbital profile takes only finite values are quite important. Called oligomorphic
groups by Cameron, they are an objet of study by itself (see Cameron’s book[5]).
We present first some properties of the profile, a counting function somewhat more
general. Next, we present the link with the age algebra, then we gives an illustration
of Theorem 0.2. We conclude with some problems.
A CONJECTURE OF P.J. CAMERON 5
0.4.1. Profile of a relational structure. The profile of a relational structure R with
base E is the function ϕR which counts for every integer n the number (possibly
infinite) ϕR(n) of substructures of R induced on the n-element subsets, isomorphic
substructures being identified. Clearly, if R encodes a permutation groups G, ϕR(n)
is the number θG(n) of orbits of n-element subsets of E.
If the signature µ is finite (in the sense that I is finite), there are only finitely
many relational structures with signature µ on an n-element domain, hence ϕR(n) is
necessarily an integer for each integer n. In order to capture examples coming from
algebra and group theory, one cannot preclude I to be infinite. But then, ϕR(n) could
be an infinite cardinal. As far as one is concerned by the behavior of ϕR, this case
can be excluded:
Fact 0.4. [28] Let n < |E|. Then
(3) ϕR(n) ≤ (n + 1)ϕR(n+ 1)
In particular:
(4) If ϕR(n) is infinite then ϕR(n + 1) is infinite too and ϕR(n) ≤ ϕR(n+ 1).
Inequality (3) can be substantially improved:
Theorem 0.5. If R is a relational structure on an infinite set then ϕR is non-
decreasing.
This result was conjectured with R.Fräıssé [14]. We proved it in 1971; the proof -
for a single relation- appeared in 1971 in R.Fräıssé’s book [12], Exercise 8 p. 113; the
general case was detailed in [26]. The proof relies on Ramsey theorem [32].
More is true:
Theorem 0.6. If R is a relational structure on a set E having at least 2n + m
elements then ϕR(n) ≤ ϕR(n+m).
Meaning that if |E| := ℓ then ϕR increases up to
; and, for n ≥ ℓ
the value in n
is at least the value of the symmetric of n w.r.t. ℓ
The result is a straightforward consequence of the following property of incidence
matrices.
Let m,n, ℓ be three non-negative integers and E be an ℓ-element set. Let Mn,n+m
be the matrix whose rows are indexed by the n-element subsets P of E and columns
by the n +m-element subsets Q of E, the coefficient aP,Q being equal to 1 if P ⊆ Q
and equal to 0 otherwise.
Theorem 0.7. If 2n+m ≤ l then Mn,n+m has full row rank (over the field of rational
numbers).
Theorem 0.7 is in W.Kantor 1972 [19], with similar results for affine and vector
subspaces of a vector space. Over the last 30 years, it as been applied and redis-
covered many times; recently, it was pointed out that it appeared in a 1966 paper
of D.H.Gottlieb [15]. Nowadays, this is one of the fundamental tools in algebraic
combinatorics. A proof, with a clever argument leading to further developments, was
given by Fräıssé in the 1986’s edition of his book, Theory of relations, see [13].
6 MAURICE POUZET
We proved Theorem 0.6 in 1976 [23]. The same conclusion was obtained first
for orbits of finite permutation groups by Livingstone and Wagner, 1965 [20], and
extended to arbitrary permutation groups by Cameron, 1976 [3]. His proof uses the
dual version of Theorem 0.7. Later on, he discovered a nice translation in terms of
his age algebra, that we present now.
For that, observe that ϕR only depends upon the age of R and, moreover, if ϕR take
only integer values, then K.A(R) identifies with the set of (finite) linear combinations
of members of A(R). In this case, as pointed out by Cameron, ϕR(n) is the dimension
of the homogeneous component of degree n of K.A(R).
Let e ∈ K[E]
be the map which is 1 on the one-element subsets of E and 0
elsewhere. Let U be the subalgebra generated by e. We can think of e as the sum of
isomorphic types of the one-element restrictions of R. Members of U are then of the
form λme
m + · · ·+ λ1e + λ01 where 1 is the isomorphic type of the empty relational
structure and λm, . . . , λ0 are in K. Hence U is graded, with Un, the homogeneous
component of degree n, equals to K.en.
Here is the Cameron’s result:
Theorem 0.8. If R is infinite then, for every u ∈ K.A(R), eu = 0 if and only if
u = 0
This innocent looking result implies that ϕR is non decreasing. Indeed, the image of
a basis of K.A(R)n by multiplication by e
m is an independent subset of K.A(R)n+m.
0.4.2. Growth rate of the profile. Infinite relational structures with a constant profile,
equal to 1, were called monomorphic and characterized by R. Fräıssé who proved that
they were chainable. Later on, those with bounded profile, called finimorphic, were
characterized as almost chainable [14]. Groups with orbital profile equal to 1 were
described by P.Cameron in 1976 [3]. From his characterization, Cameron obtained
that an orbital profile is ultimately constant, or grows as fast as a linear function with
slope 1
The age algebra can be also used to study the growth of the profile.
If A is a graded algebra, the Hilbert function hA of A is the function which associates
to each integer n the dimension of the homogeneous component of degree n. So,
provided that it takes only finite values, the profile ϕR is the Hilbert function of the
age algebra C.A(R). In [10], Cameron made the following important observation
about the behavior of the Hilbert fonction.
Theorem 0.9. Let A be a graded algebra over an algebraically closed field of charac-
teristic zero. If A is an integral domain the values of the Hilbert function hA satisfy
the inequality
(5) hA(n) + hA(m)− 1 ≤ hA(n +m)
for all non-negative integers n and m.
This result has an immediate consequence on the growth of the profile:
Theorem 0.10. [26] The growth of the profile of a relational structure with empty
kernel is at least linear provided that it is unbounded.
A CONJECTURE OF P.J. CAMERON 7
In fact, provided that the relational structures satisfy some mild conditions, the
existence of jumps in the behavior of the profile extends.
Let ϕ : N → N and ψ : N → N. Recall that ϕ = O(ψ) and ψ grows as fast as ϕ
if ϕ(n) ≤ aψ(n) for some positive real number a and n large enough. We say that
ϕ and ψ have the same growth if ϕ grows as fast as ψ and ψ grows as fast as ϕ.
The growth of ϕ is polynomial of degree k if ϕ has the same growth as n →֒ nk; in
other words there are positive real numbers a and b such that ank ≤ ϕ ≤ bnk for n
large enough. Note that the growth of ϕ is as fast as every polynomial if and only if
limn→+∞
= +∞ for every non negative integer k.
Theorem 0.11. Let R := (E, (ρi)i∈I) be a relational structure. The growth of ϕR
is either polynomial or as fast as every polynomial provided that either the signature
µ := (ni)i∈I is bounded or the kernel K(R) of R is finite.
Theorem 0.11 is in [24]. An outline of the proof is given in [28]. A part appeared in
[26], with a detailed proof showing that the growth of unbounded profiles of relational
structures with bounded signature is at least linear.
The kernel of any relational structure which encodes an oligomorphic permutation
group is finite (indeed, as already mentionned, if R encodes a permutation group G
acting on a set E then K(R) is the set union of the finite orbits of the one-element
subsets of E. Since the number of these orbits is at most θG(1), K(R) is finite if G is
oligomorphic). Hence:
Corollary 0.12. The orbital profile of an oligomorphic group is either polynomial or
faster than every polynomial.
For groups, and graphs, there is a much more precise result than Theorem 0.11. It
is due to Macpherson, 1985 [22].
Theorem 0.13. The profile of a graph or a permutation groups grows either as a
polynomial or as fast as fε, where fε(n) = e
, this for every ε > 0.
0.4.3. Growth rate and finite generation. A central question in the study of the profile,
raised first by Cameron in the case of oligomorphic groups, is this:
Problem 1. If the profile of a relational structures R with finite kernel has polynomial
growth, is ϕR(n) ≃ cn
k′ for some positive real c and some non-negative integer k′?
Let us associate to a relational structure R whose profile takes only finite values
its generating series
HϕR :=
ϕR(n)x
Problem 2. If R has a finite kernel and ϕR is bounded above by some polynomial,
is the series HϕR a rational fraction of the form
P (x)
(1− x)(1− x2) · · · (1− xk)
with P ∈ Z[x]?
8 MAURICE POUZET
Under the hypothesis above we do not know if HϕR is a rational fraction.
It is well known that if a generating function is of the form
P (x)
(1−x)(1−x2)···(1−xk)
for n large enough, an is a quasi-polynomial of degree k
′, with k′ ≤ k − 1, that is
a polynomial ak′(n)n
k′ + · · ·+ a0(n) whose coefficients ak′(n), . . . , a0(n) are periodic
functions. Hence, a subproblem is:
Problem 3. If R has a finite kernel and ϕR is bounded above by some polynomial,
is ϕR(n) a quasi-polynomial for n large enough?
Remark 0.14. Since the profile is non-decreasing, if ϕR(n) is a quasi-polynomial for
n large enough then ak′(n) is eventually constant. Hence the profile has polynomial
growth in the sense that ϕR(n) ∼ cn
k′ for some positive real c and k′ ∈ N. Thus, in
this case, Problem 1 has a positive solution.
A special case was solved positively with N.Thiéry [30].
These problems are linked with the structure of the age algebra. Indeed, if a
graded algebra A is finitely generated, then, since A is a quotient of a polynomial
ring K[x1, . . . , xd], its Hilbert function is bounded above by a polynomial. And, in
fact, as it is well known, its Hilbert series is a fraction of form
P (x)
(1−x)d
, thus of the form
given in (6). Moreover, one can choose a numerator with non-negative coefficients
whenever the algebra is Cohen-Macaulay. Due to Problem 2, one could be tempted
to conjecture that these sufficient conditions are necessary in the case of age agebras.
Indeed, from Theorem 0.8 one deduces easily:
Theorem 0.15. The profile of R is bounded if and only if K.A(R) is finitely generated
as a module over U , the graded algebra generated by e. In particular, if one of these
equivalent conditions holds, K.A(R) is finitely generated
But this case is exceptional. The conjecture can be disproved with tournaments.
Indeed, on one hand, there are tournaments whose profile has arbitrarily large poly-
nomial growth rate and, on an other hand, the age algebra of a tournament is finitely
generated if and only if the profile of the tournament is bounded (this result was
obtained with N.Thiery, a proof is presented in [28]).
0.4.4. Initial segments of an age and ideals of a ring. No concrete description of
relational structures with bounded signature, or finite kernel, which have polynomial
growth is known. In [24] (see also [28]) we proved that if a relational structure R
has this property then its age, A(R), is well-quasi-ordered under embeddability, that
is every final segment of A(R) is finitely generated, which amounts to the fact that
the collection F (A(R)) of final segments of A(R) is noetherian, w.r.t. the inclusion
order. Since the fundamental paper of Higman[17], applications of the notion of
well-quasi-ordering have proliferated (eg see the Robertson-Seymour’s theorem for an
application to graph theory [11] ). Final segments play for posets the same role than
ideals for rings. Noticing that an age algebra is finitely generated if and only if it is
noetherian, we are lead to have a closer look at the relationship between the basic
objects of the theory of relations and of ring theory, particularly ages and ideals.
We mention the following result which will be incorporated into a joint paper with
N.Thiéry.
A CONJECTURE OF P.J. CAMERON 9
Proposition 0.16. Let A be the age of a relational structure R such that the profile
of R takes only finite values and K.A be its age algebra. If A′ is an initial segment
of A then:
(i) The vector subspace J := K.(A \ A′) spanned by A \ A′ is an ideal of K.A.
Moreover, the quotient of K.A by J is a ring isomorphic to the ring K.A′.
(ii) If this ideal is irreducible then A′ is a subage of A.
(iii) This is a prime ideal if and only if A′ is an inexhaustible age.
The proof of Item (i) and Item (ii) are immediate. The proof of Item (iii) is
essentially based on Theorem 0.2.
According to Item (i), F (A) embeds into the collection of ideals of K.A). Conse-
quently:
Corollary 0.17. If an age algebra is finitely generated then the age is well-quasi-
ordered by embeddability.
Problem 4. How the finite generation of an age algebra translates in terms of em-
beddability between members of the ages?
0.4.5. Links with language theory. In the theory of languages, one of the basic results
is that the generating series of a regular language is a rational fraction (see [1]). This
result is not far away from our considerations. Indeed, if A is a finite alphabet, with
say k elements, and A∗ is the set of words over A, then each word can be viewed as a
finite chain coloured by k colors. Hence A∗ can be viewed as the age of the relational
structure R made of the chain Q of rational numbers divided into k colors in such
a way that, between two distinct rational numbers, all colors appear. Moreover, as
pointed out by Cameron [6], the age algebra Q.A(R) is isomorphic to the shuffle
algebra over A, an important object in algebraic combinatorics (see [21]).
Problem 5. Does the members of the age of a relational structure with polynomial
growth can be coded by words forming a regular language?
Problem 6. Extend the properties of regular languages to subsets of the collection
Ωµ made of isomorphic types of finite relational structures with signature µ.
1. Proof of Theorem 0.3
The proof idea of Theorem 0.3 is very simple and we give it first.
We prove the result by induction. We suppose that it holds for pairs (m − 1, n).
Now, let f : [E]m → K and g : [E]n → K such that fg is zero, but f and g are not.
As already mentionned, m and n are non zero, hence members of supp(f) ∪ supp(g)
are non empty. Let sup(f, g) := {(A,B) ∈ supp(f) × supp(g) : A ∩ B = ∅}. We
may suppose sup(f, g) 6= ∅, otherwise the conclusion of Theorem 0.3 holds with t :=
m+ n− 1. For the sake of simplicity, we suppose that K := Q. In this case, we color
elements A of [E]m into three colors :-,0, +, according to the value of f(A). We do the
same with elements B of [E]n and we color each member (A,B) of supp(f, g) with the
colors of its components. With the help of Ramsey’ theorem and a lexicographical
ordering, we prove that if the transversality is large enough there is an (m+n)-element
subset Q such that all pair (A,B) ∈ supp(f, g)(Q) := supp(f, g)∩ ([Q]m × [Q]n) have
10 MAURICE POUZET
the same color. This readily implies that fg(Q) 6= 0, a contradiction. If K 6= Q, we
may replace the three colors by five, as the following lemma indicates.
Lemma 1.1. Let K be a field with characteristic zero. There is a partition of K∗ :=
K \ {0} into at most four blocks such that for every integer k and every k-element
sequences (α1, . . . , αk) ∈ D
k , (β1, . . . , βk) ∈ D
′k, where D, D′ are two blocks of the
partition of K∗, then
i=1 αiβi ∈ K
Proof. This holds trivially if K := C. For an example, divide C∗ into the sets
Di := {z ∈ C
∗ : πi
≤ Argz <
π(i+1)
} (i < 4). If K is arbitrary, use the Com-
pactness theorem of first-order logic, under the form of the ”diagram method” of
A.Robinson [18]. Namely, to the language of fields, add names for the elements of
K, a binary predicate symbol, and axioms, this in such a way that a model, if any,
of the resulting theory T will be an extension of K with a partition satisfying the
conclusion of the lemma. According to the Compactness theorem of first-order logic,
the existence of a model of T , alias the consistency of T , reduces to the consistency of
every finite subset A of T . A finite subset A of T leads to a finitely generated subfield
of K. Such subfield is isomorphic to a subfield of C (see [18] Example 2, p.99, or [2]
Proposition 1, p. 108). This latter subfield equipped with the partition induced by
the partition existing on C∗ satisfies the conclusion of the lemma, hence is a model
of T , proving that A is consistent.
Let T∗ be the set of these four blocks, let T := T∪{0} and let χ be the map from
K onto T.
1.1. Invariant relational structures and their age algebra.
1.1.1. Isomorphism, local isomorphism. Let R := (E, (ρi)i∈I) and R
′ := (E ′, (ρ′i)i∈I)
be two relational structures having the same signature µ := (mi)i∈I . A map h : E →
E ′ is an isomorphism from R onto R′ if
(1) h is bijective,
(2) (x1, . . . , xmi) ∈ ρi if and only if (h(x1), . . . , h(xmi)) ∈ ρ
i for every (x1, . . . , xmi) ∈
Emi , i ∈ I.
A partial map of E is a map h from a subset A of E onto a subset A′ of E, these
subsets are the domain and codomain of h. A local isomorphism of R if a partial map
h which is an isomorphism from R↾A onto R↾A′ (where A and A
′ are the domain an
codomain of h).
1.1.2. Invariant relational structures. A chain is a pair L := (C,≤) where ≤ is a
linear order on C. Let L be a chain. Let V be a non-empty set, F be a set disjoint
from V ×C and let E := F ∪ (V ×C). Let R be a relational structure with base set
E. Let r be a non-negative integer, r ≤ |C|. Let X,X ′ ∈ [C]r. Let ℓ be the unique
order isomorphism from L↾X onto L↾X′ and let ℓ := 1F ∪ (1V , ℓ) be the partial map
such that ℓ(x) = x for x ∈ F and ℓ(x, y) = (x, ℓ(y)) for (x, y) ∈ V ×X .
We say that X and X ′ are equivalent if ℓ is an isomorphism of H↾F∪V×X onto
H↾F∪V×X′. This defines an equivalence relation on [C]
A CONJECTURE OF P.J. CAMERON 11
We say that R is r−F−L-invariant if two arbitrary members of [C]r are equivalent.
We say that R is F − L-invariant if it is r − F − L-invariant for every non-negative
integer r, r ≤ |C|.
It is easy to see that if the signature µ of R is bounded and r :=Max({mi : i ∈ I}),
R is F −L-invariant if and only if it is r′ − F − L-invariant for every r′ ≤ r. In fact:
Lemma 1.2. If |C| > r :=Max({mi : i ∈ I}), R is F −L-invariant if and only if it
is r − F − L-invariant.
This is an immediate consequence of the following lemma:
Lemma 1.3. If R is r−F −L-invariant and r < |C| then R is r′ −F −L-invariant
for all r′ ≤ r.
Proof. We only prove that R is (r− 1)− F − L-invariant. This suffices. Let X,X ′ ∈
[C]r−1. Since r < |C|, we may select Z ∈ [C]r such that the last element of Z (w.r.t.
the order L) is strictly below some element c ∈ C.
Claim 1.4. There are Y, Y ′ ∈ [Z]r−1 which are equivalent to X and X ′ respectively.
Proof of Claim 1.4. Extend X and X ′ to two r-element subsets X1 and X
1 of C.
Since R is r− F −L-invariant, X1 is equivalent to Z, hence the unique isomorphism
from L↾X1 onto L↾Z carries X onto an equivalent subset Y of Z. By the same token,
X ′1 is equivalent to a subset Y
′ of Z.
Claim 1.5. Y and Y ′ are equivalent.
Proof of Claim 1.5. The unique isomorphism from L↾Y ∪{c} onto L↾Y ′∪{c} carries
Y onto Y hence T and Y ′ are equivalent.
From the two claims above X and X ′ are equivalent. Hence, R is (r− 1)− F −L-
invariant.
1.1.3. Coding by words. Let A := P(V ) \ {∅}. Let A∗ :=
Ap be the set of
finite sequences of members of A. A finite sequence u being viewed as a word on the
alphabet A, we write it as a juxtaposition of letters and we denote by λ the empty
sequence; the length of u, denoted by |u| is the number of its terms. Let p be a non
negative integer. If X is a subset of p := {0, . . . , p − 1} and u a word of length p,
the restriction of u to X induces a word that we denote by t(u↾X). We suppose that
V is finite and we equip A with a linear order. We compare words with the same
length with the lexicographical order, denoted by ≤lex. We record without proof the
following result.
Lemma 1.6. Let p, q be two non negative integers and X be an p-element subset of
p + q := {0, . . . , p + q − 1}. The map from Ap × Aq into Ap+q which associates to
every pair (u, v) ∈ Ap × Aq the unique word w ∈ Ap+q such that t(w↾X) = u and
t(w↾p+q\X) = v is strictly increasing (w.r.t. the lexicographical order).
This word w is a shuffle of u and v that we denote uX v. We denote by u ̂ v the
largest word of the form uX v.
We order A∗ with the radix order defined as follows: if u and v are two distincts
words, we set u < v if and only if either |u| < |v| or |u| = |v| et u <lex v. We suppose
12 MAURICE POUZET
that F is finite and we order P(F ) in such a way that X < Y implies |X| ≥ |Y |.
Finally, we order P(F )×A∗ lexicographically.
Let L := (C,≤). Let Q be a finite subset of E := F ∪ (V × C). Let proj(Q) :=
{i ∈ C : Q ∩ V × {i} 6= ∅}. Let i0, . . . , ip−1 be an enumeration of proj(Q) in an
increasing order (w.r.t L) and let w(Q \ F ) be the word u0 . . . up−1 ∈ A
∗ such that
Q \ F = u0 ×{i0} ∪ · · · ∪ up−1 × {ip−1}. We set w(Q) := (Q∩ F,w(Q \ F )). If Q is a
subset of [E]<ω, we set w(Q) := {w(Q) : Q ∈ Q}. If f : [E]m → K, let lead(f) := −∞
if f = 0 and otherwise let lead(f) be the largest element of w(supp(f)). We show
below that this latter parameter behaves as the degree of a polynomial.
We start with an easy fact.
Lemma 1.7. Let m and n be two non negative integers, A ∈ [E\F ]m and B ∈ [E]n. If
|C| ≥ m+n there is A′ ∈ [E\F ]m such that proj(A′)∩proj(B) = ∅ and w(A′) = w(A).
Lemma 1.8. Let R be an F − L-invariant structure on E. Let m and n be two
non negative integers; let f : [E]m → K, g : [E]n → K be two non zero members
of K.A(R). Let A0 ∈ supp(f), and B0 ∈ supp(g) such that w(A0) = lead(f) and
w(B0) = lead(g). Suppose that F and V are finite, that |C| ≤ n +m and supp(f) ∩
[E \ F ]m 6= ∅. Then:
(7) supp(f, g) 6= ∅.
(8) (w(A), w(B)) = (lead(f), lead(g)).
for all (A,B) ∈ supp(f, g)(Q0), where w(Q0) = lead(f, g) and lead(f, g) is the largest
element of w({A ∪ B : (A,B) ∈ supp(f, g)}).
(9) (f(A), g(B)) = (f(A0), g(B0))
for every (A,B) ∈ supp(f, g)(Q0).
(10) fg(Q0) = |supp(f, g)(Q0)|f(A0)g(B0).
(11) lead(fg) = lead(f, g) = (Q0 ∩ F,w(A0)̂w(B0 \ F )).
Proof. (1) Proof of (7). Since supp(f) ∩ [E \ F ]m 6= ∅ and the order on P(F )
decreases with the size, A0 is disjoint from F . Let B ∈ supp(g). According to
Lemma 1.7 there is A′ such that proj(A′) ∩ proj(B) = ∅ and w(A′) = w(A0).
We have A′ ∩ B = ∅ and, since f ∈ K.A(R) and R is F − L-invariant,
f(A′) = f(A0). Thus (A
′, B) ∈ supp(f, g).
(2) Proof of (8). Let (A,B) ∈ supp(f, g)(Q0). Since A ∈ supp(f) and B ∈
supp(g), we have trivially:
(12) w(A) ≤ lead(f) and w(B) ≤ lead(g).
Claim 1.9. B ∩ F = Q0 ∩ F and A ∩ F = ∅.
A CONJECTURE OF P.J. CAMERON 13
The pair (A′, B) obtained in the proof of (7) belongs to supp(f, g). Let
Q′ := A′ ∪ B. By maximality of w(Q0), we have w(Q
′) ≤ w(Q0). If B ∩ F 6=
Q0 ∩ F , then |Q
′ ∩ F | < |Q0 ∩ F |, hence w(Q0) < w(Q
′). A contradiction.
The fact that A ∩ F = ∅ follows.
Claim 1.10. proj(A) ∩ proj(B) = ∅ and |proj(A)| = |proj(B).|
Apply Lemma 1.7. Let A′ such that proj(A′) ∩ proj(B) = ∅ and w(A′) =
w(A). Since f ∈ K.A(R) and R is F − L-invariant, f(A′) = f(A) thus
(A′, B) ∈ supp(f, g). Set Q′ := A′ ∪ B. We have w(Q′ \ F ) ≤ w(Q0 \ F )
hence |w(Q′)| ≤ |w(Q0)|. Since |w(Q
′ \ F )| = |proj(A′)| + |proj(B)| and
|w(Q0\F )| ≤ |proj(A)|+|proj(B)|, we get |w(Q0\F )| = |proj(A)|+|proj(B)|.
This proves our claim.
Let i0, . . . , ir−1 be an enumeration of proj(Q0 \ F ) in an increasing order.
Let X := {j ∈ r : ij ∈ proj(A)}. Since proj(A)∩proj(B) = ∅, we have w(Q0\
F ) = w(A)X w(B \ F ). Since w(A) ≤ w(A0) and |w(A)| = |w(A0)|, Lemma
1.6 yields w(Q0 \ F ) ≤ w(A0)X w(B). As it is easy to see, there is A
0 such
that w(A′0) = w(A0) and Q
′ := A′0 ∪ B satisfies w(Q
′ \ F ) = w(A0)X w(B).
Since (A′, B) ∈ supp(f, g), we have w(Q′) = w(Q0) by maximality of w(Q0).
With Lemma 1.6 again, this yields w(A) = w(A0). Hence w(A) = w(A0). A
similar argument yields w(B \F ) = w(B0 \F ) and also w(B \F ) = w(B0 \F ).
(3) Proof of (9). Since R is F −L-invariant, from w(A) = lead(f) := w(A0) we
get f(A) = f(A0). By the same token, we get g(B) = g(B0).
(4) Proof of (10). Since fg(Q0) =
(A,B)∈sup(f,g) f(A)g(B) the result follows
from (9).
(5) Proof of (11). From (10), fg(Q0) 6= 0, the equality lead(fg) = lead(f, g)
follows. The remaining equality follows from (8).
With this, the proof of the lemma is complete.
As far as invariant structures are concerned, we can retain this:
Corollary 1.11. Under the hypotheses of Lemma 1.12, fg 6= 0.
1.1.4. An application. Letm,n be two positive integers, E be a set and f : [E]m → K,
g : [E]n → K. Let R := (E, (ρ(i,j))(i,j)∈T∗×2)) be the relational structure made of the
four m-ary relations ρ(i,0) := {(x1, . . . , xm) : χ ◦ f({x1, . . . , xm}) = i} and the four n-
ary relations ρ(i,1) := {(x1, . . . , xn) : χ ◦ g({x1, . . . , xn}) = i}. A map h from a subset
A of E onto a subset A′ of E is a local isomorphism of R if χ ◦ f(P ) = χ ◦ f(h[P ])
and χ ◦ f(R) = χ ◦ f(h[R]) for every P ∈ [A]m, every R ∈ [A]n. This fact allows us
to consider the pair H := (E, (χ ◦ f, χ ◦ g)) as a relational structure. In the sequel we
suppose that E = F ∪ (V × C) with F and V finite; we fix a chain L := (C,≤).
Lemma 1.12. Suppose that there are P ∈ supp(f) ∩ [V × C]m and R ∈ supp(g) ∩
[E \ P ]n. If H is F − L-invariant and |C| ≥ m+ n. Then fg 6= 0.
Proof. Let lead(f, g) be the largest element of w({A ∪ B : (A,B) ∈ supp(f, g)}) and
let Q0 such that w(Q0) = lead(f, g).
14 MAURICE POUZET
Claim 1.13. (χ ◦ f(A), χ ◦ g(B)) is constant for (A,B) ∈ sup(f, g)(Q0).
Proof of Claim 1.13. Let s : T → K be a section of χ. Let f ′ := s ◦ χ ◦ f and
let g′ := s ◦ χ ◦ g. Then f ′, g′ ∈ K.A(H) and supp(f ′, g′) = supp(f, g). According to
Equation (9) of Lemma 1.8, (f ′(A), g′(B)) is constant for (A,B) ∈ supp(f ′, g′)(Q0).
The result follows.
From Lemma 1.1, fg(Q0) :=
(A,B)∈sup(f,g)(Q0)
f(A)g(B) 6= 0.
We recall the finite version of the theorem of Ramsey [32], [16].
Theorem 1.14. For every integers r, k, l there is an integer R such that for every
partition of the r-element subsets of a R-element set C into k colors there is a l-
element subset C ′ of C whose all r-element subsets have the same color.
The least integer R for which the conclusion of Theorem 1.14 holds is a Ramsey
number that we denote Rrk(l).
Let m and n be two non negative integers. Set r := Max({m,n}), s :=
, k := 5s and, for an integer l, l > r, set ν(l) := Rrk(l).
Lemma 1.15. If |F | = n, |V | = m and |C| ≥ ν(l) there is an l-element subset C ′ of
C such that H↾F∪V×C′ is F − L↾C′-invariant.
The proof is a basic application of Ramsey theorem. We give it for reader conve-
nience. See [13] 10.9.4 page 296, or [27] Lemme IV.3.1.1 for a similar result).
Proof. The number of equivalence classes on [C]r is at most k := 5s (indeed, this
number is bounded by the number of distinct pairs (χ◦f ′, χ◦g′) such that f ′ ∈ K[E
g′ ∈ K[E
′]n and |E ′| = n+mr). Thus, according to Theorem 1.14, there is a l-element
subset C ′ of C whose all r-element subsets are equivalent. This means that H↾F∪V×C′
is r − F − L↾C′ -invariant. Now, since r < l, Lemma 1.3 asserts that H↾F∪V×C′ is
r′ − F − L↾C′-invariant for all r
′ ≤ r. Since the signature of H is bounded by r,
H↾F∪V×C′ is F − L↾C′ -invariant from Lemma 1.2.
1.2. The existence of τ(m,n). Let m and n be two non negative integers. Suppose
1 ≤ m ≤ n and that τ(m− 1, n) exists. Let E be a set with at least m+ n elements
and f : [E]m → K, g : [E]n → K such that fg is zero, but f and g are not.
Lemma 1.16. Let A be a transversal for supp(f). Then there is a transversal B for
supp(g) such that:
(13) |B \ A| ≤ τ(m− 1, n)
Proof. Among the sets P ∈ supp(f) select one, say P0, such that F0 := P0 ∩ A has
minimum size, say r0.
Case 1. A∪P0 is also a transversal for supp(g). In this case, set B := A∪P0. We
have |B \ A| ≤ m− 1, hence inequality (13) follows from inequality (14) below:
(14) m− 1 ≤ τ(m− 1, n)
This inequality is trivial for m = 1. Let us prove it for m > 1 (a much better
inequality is given in Lemma 3.1). Let E ′ be an m + n − 1-element set, let f ′ :
[E ′]m−1 → K and g′ : [E ′]n → K, with f ′ non zero on a single m − 1-element set A′,
A CONJECTURE OF P.J. CAMERON 15
g′(B′) = 1 if A′ ∩ B′ 6= ∅ and g′(B′) = 0 otherwise. Since m − 1 and n are not 0, f ′
and g′ are not 0. Trivially, f ′g′ = 0 and, as it easy to check, A′ is a transversal for
supp(f ′) ∪ supp(g′) having minimum size, hence τ(supp(f ′) ∪ supp(g′)) = m− 1.
Case 2. Case 1 does not hold. In this case, pick x0 ∈ F0 and set E
′ := (E \ A) ∪
(F0 \ {x0}). Let f
′ : [E ′]m−1 → K be defined by setting f(P ′) := f(P ′ ∪ {x0}) for all
P ′ ∈ [E ′]m−1 and let g′ := g↾[E′]n .
Claim 1.17. |E ′| ≥ m+ n− 1 and f ′g′ = 0.
Proof of Claim 1.17. The inequality follows from the fact that A ∪ P0 is not a
transversal for supp(g). Now, let Q′ ∈ [E ′]m+n−1 and Q := Q′ ∪ {x0}.
(15) f ′g′(Q′) =
P ′∈[Q′]m−1
f ′(P ′)g′(Q′ \ P ′) =
x0∈P∈[Q]m
f(P )g(Q \ P )
Since fg = 0 we have:
0 = fg(Q) =
P∈[Q]m
f(P )g(Q \P ) =
x0∈P∈[Q]m
f(P )g(Q \P ) +
x0 6∈P∈[Q]m
f(P )g(Q \P )
If x0 6∈ P , |P ∩ A| < r0, hence f(P ) = 0. This implies that the second term in the
last member of (16) is zero, hence the second member of (15) is zero. This proves our
claim.
From our hypothesis A ∪ P0 is not a tranversal for g. Hence, we have
Claim 1.18. f ′ and g′ are not zero.
The existence of τ(m − 1, n) insures that there is a transversal H for supp(f ′) ∪
supp(g′) of size at most τ(m − 1, n). The set B := A ∪ H is a transversal for
supp(f) ∪ supp(g).
Lemma 1.19. Let l be a positive integer. If τ(supp(f) ∪ supp(g)) > n +m(l − 1) +
τ(m − 1, n) then for every F ∈ supp(g) there is a subset P ⊆ supp(f) ∩ [E \ F ]m
made of at least l pairwise disjoint sets.
Proof. Fix F ∈ supp(g). Let P ⊆ supp(f) ∩ [E \ F ]m be a finite subset made of
pairwise disjoint sets and let p := |P|. If the conclusion of the lemma does not hold,
we have p < l. Select then P with maximum size and set A := F ∪
P. Clearly A is
a transversal for supp(f). According to Lemma 1.16 above, τ(supp(f) ∪ supp(g)) ≤
|A|+ τ(m − 1, n) = n +mp + τ(m− 1, n). Thus, according to our hypothese, l ≤ p.
A contradiction.
Let ϕ(m,n) := n+m(ν(n +m)− 1) + τ(m− 1, n).
Lemma 1.20.
(17) τ(m,n) ≤ ϕ(m,m)
Proof. Suppose τ(supp(f) ∪ supp(g)) > ϕ(m,n). Let F ∈ supp(g). According to
Lemma 1.19 there is a subset P ⊆ supp(f) ∩ [E \ F ]m made of at least ν(n + m)
pairwise disjoint sets. With no loss of generality, we may suppose that ∪P is a set
16 MAURICE POUZET
of the form V × C where |V | = m and |C| = ν(m,n). Let ≤ be a linear order on C
and L := (C,≤). According to Lemma 1.15 there is an n +m-element subset C ′ of
C such that H↾F∪V×C′ is F − L↾C′-invariant. According to Lemma 1.12 fg 6= 0. A
contradiction.
With Lemma 1.20, the proof of Theorem 0.3 is complete.
Note that ϕ(1, 2) = 1 + R2
(3) + τ(0, n) = R2
(3), whereas τ(1, 2) = 4. Also
ϕ(2, 2) = 2R2
(4) + τ(1, 2) = 2(R2
(4) + 2).
Our original proof of Theorem 0.3 was a bit simpler. Instead of an m-element set
F and several pairwise disjoint n-element sets, we considered several pairwise n+m-
element sets. In the particular case of m = n = 2, we got τ(2, 2) ≤ 4R2
(4) + 1. In
term of concrete upper-bounds, we are not convinced that the improvement worth
the effort.
2. The Gottlieb-Kantor theorem and the case m = 1
Let E be a set. To each x ∈ E associate an indeterminate Xx. Let K[E] be the
algebra over the field K of polynomials in these indeterminates. Let f : [E]1 → K. Let
Df be the derivation on this algebra which is induced by f , that is Df(Xx) := f({x})
for every x ∈ E. Let ϕ : K[E] → K[E] be the ring homomorphism such that ϕf (1) :=
1 and ϕf(Xx) := f({x})Xx. Let e : [E]
1 → K be the constant map equal to 1 and
let De be the corresponding derivation. For example Df(XxXyXz) = f({x})XyXz +
f({y})XxXz + f({z})XxXy whereas De(XxXyXz) = XyXz + XxXz + XxXy. It is
easy to check that:
(18) De ◦ ϕf = ϕf ◦Df .
Let n be a non negative integer; let K[n][E] be the vector space generated by the
monomials made of n distinct variables. From equation (18), we deduce:
Corollary 2.1. If f does not take the value zero on [E]1, the surjectivity of the maps
from K[n+1][E] into K[n][E] induced by Df and De are equivalent.
Suppose that E is finite. In this case, the matrix of the restriction ofDe to K[n+1][E]
identifies to Mn,n+1. Thus, according to Theorem 0.7, De is surjective provided that
|E| ≥ 2n+ 1. Corollary asserts that in this case, Df is surjective too. This yields:
Lemma 2.2. If f does not take the value zero on a subset E ′ of E of size at least
2n + 1 but fg = 0 for some g : [E]n → K then g is zero on the n-element subsets of
Proof. Suppose that fg = 0. Let g : K[n][E] → K be the linear form defined by
setting g(Πx∈BXx) := g(B) for each B ∈ [E]
n. Then g ◦Df is 0 on K[n+1][E]. From
Corollary 2, the map from K[n+1][E
′] into K[n][E
′] induced by Df is surjective. Hence
g is 0 on K[n][E
′]. Thus g is zero on [E ′]n as claimed.
Going a step further, we get a weighted version of Gottlieb-Kantor theorem:
Theorem 2.3. Let f : [E]1 → K and g : [E]n → K. If f does not take the value zero
on a subset of size at least 2n+ 1 and if fg = 0 then g est identically zero on [E]n.
A CONJECTURE OF P.J. CAMERON 17
Proof. Set E ′ := supp(f). According to our hypothesis, E ′ 6= ∅. We prove the lemma
by induction on n. If n = 0, pick x ∈ E ′. We have fg({x}) = f({x})g(∅). Since
f({x}) 6= 0 and K is an integral domain, g(∅) = 0. Thus g = 0 and the conclusion of
the lemma holds for n = 0. Let n ≥ 1. Let B ∈ [E]n. We claim that g(B) = 0. Let
F := B \E ′ and r := |F |. If r = 0, that is B ⊆ E ′, we get g(B) = 0 from Lemma 2.2.
If r 6= 0, we define gr on [E
′]n−r, setting gr(B
′) := g(B′ ∪ F ) for each B′ ∈ [E ′]n−r.
Let Q′ ∈ [E ′]n−r+1 and Q := Q′ ∪ F . We have fgr(Q
x∈Q′ f({x})g(Q \ {x}) =∑
x∈Q f({x})g(Q \ {x}) −
x∈F f({x})g(Q \ {x}). From our hypothesis on g and
the fact that f({x}) = 0 for all x /∈ E ′, both terms on the right hand side of the
latter equality are 0, thus fgr(Q
′) = 0. Since |E ′| ≥ 2(n − r) + 1, induction on n
applies. Hence gr is 0 on [E
′]n−r. This yields g(B) = 0, proving our claim. Hence the
conclusion of the lemma holds for n.
Theorem 2.4. τ(1, n) = 2n
Proof. Trivially, the formula holds if n = 0. Hence, in the sequel, we suppose n ≥ 1.
Claim 2.5. τ(1, n) ≤ 2n
Proof of Claim 2.5.Let f and g be non identically zero such that fg = 0. From
Theorem 2.3, the support S of f has at most 2n elements. From Lemma 1.16
|supp(f) ∪ (supp(g)| ≤ |S|+ τ(0, n) = |S| ≤ 2n.
For the converse inequality, we prove that:
Claim 2.6. There is a 2n element set E and a map g : [E]n → K such that eg = 0
and g 6= 0.
Proof of Claim 2.6 Let E := {0, 1} × {0, . . . , n− 1}. Set Ei := {0, 1} × {i} for
i < n. Let B ∈ [E]n. Set g(B) := 0 if B is not a transversal of the Ei’s, g(B) := −1 if
B is a transversal containing an odd number of elements of the form (0, i), g(B) = 1
otherwise. Let Q ∈ [E]n+1. If Q is not a transversal of the Ei’s then g(B) = 0 for
every B ∈ [Q]n hence eg(Q) = 0. If Q is a transversal, then there is a unique index i
such that Ei ⊆ Q. In this case, the only members of [Q]
n on which g is non-zero are
Q\{(0, i)} and Q\{(1, i)}; by our choice, they have opposite signs, hence eg(Q) = 0.
Since in the example above τ(supp(e)) = 2n, we have τ(1, n) ≥ 2n. With this
inequality, the proof of Theorem 2.4 is complete.
3. A lower bound for τ(m,n)
Lemma 3.1. τ(m,n) ≥ (m+ 1)(n+ 1)− 2 for all m,n ≥ 1.
Proof. For m = 1 this inequality was obtained in Claim 2.6. For the case m > 1, we
need the following improvement of Claim 2.6.
Claim 3.2. Let n ≥ 1. There is a 2n element set E and a map g : [E]n → K such
that eg = 0 and supp(g) = [E]n.
Proof of Claim 3.2. Fix a 2n-element set E. From Claim 2.6 and the fact that the
symmetric group SE acts transitively on [E]
n, we get for each B ∈ [E]n some gB such
that egB = 0 and B ∈ supp(gB). Next, we observe that a map g : [E]
n → K satisfies
18 MAURICE POUZET
eg = 0 if and only if g belongs to the kernel of the linear map T : K[E]
→ K[E]
defined by setting T (g)(Q) :=
B∈[Q]n g(B) for all g, Q ∈ [E]
n+1. To conclude, we
apply the claim below with k :=
Claim 3.3. Let e1 := (1, 0 . . . , 0), . . . , ei := (0, . . . , 1, 0, . . . , 0), . . . , ek := (0, . . . , 1) be
the canonical basis of Kk and let H be a subspace of Kk. Then H contains a vector
with all its coordinates which are non-zero if and only if for every coordinate i it
contains some vector with this coordinate non-zero.
Proof of Claim 3.3. This assertion amounts to the fact that a vector space on
an infinite field is not the union of finitely many proper subspaces.
Let E be the disjoint union of m sets E0, . . . , Ei, . . . Em−1, each of size 2n. For
each i, let gi : [Ei]
n → K such that
B∈[Q]n gi(B) = 0 for each Q ∈ [Ei]
n+1 and
supp(gi) = [Ei]
n (according to Claim 3.2 such a gi exists). Let g : [E]
n → K be
the ”direct sum” of the gi’s: g(B) := gi(B) if B ∈ [Ei]
n, g(B) := 0 otherwise. Let
f : [E]m → K defined by setting f(A) := 1 if A ∩ Ei 6= ∅ for all i < m and 0
otherwise. Then, by a similar argument as in Claim 2.6, fg = 0. Next, a transversal
of supp(f) must contains some Ei (thus τ(supp(f)) = 2n). And, also, a transversal
of supp(g) must be a transversal of each of the supp(gi)’s. Since supp(gi) = [Ei]
τ(supp(gi)) = n + 1, hence τ(supp(g)) = (n + 1)m. We get easily that τ(supp(f) ∪
supp(g)) = 2n + (n + 1)(m − 1) = mn + m + n − 1. This completes the proof of
Lemma 3.1.
Example 3.4. The lemma above gives τ(2, 2) ≥ 7. An example illustrating this
inequality is quite simple: let E be made of two squares, let f be the map giving value
−1/2 on each side of the squares, value 1 on the diagonals; let g be giving value 1
on each pair meeting the two squares. Then for every x ∈ E, E \ {x} is a minimal
transversal of supp(f) ∪ supp(g).
References
[1] J. Berstel, C. Retenauer. Les séries rationnelles et leurs langages. Études et recherches en
Informatique. Masson, Paris, 1984,132 pp.
[2] N. Bourbaki. Éléments de mathématiques, Fasc. XI. Algèbre, Chap. V, Actualités scientifiques
et industrielles, Hermann, Paris, 1973.
[3] P. J. Cameron. Transitivity of permutation groups on unordered sets, Math. Z., 48(1976)127-
[4] P.J. Cameron. Orbits of permutation groups on unordered sets. II. J. London Math. Soc., (2)
23 (1981), no. 2, 249–264.
[5] P.J. Cameron.Oligomorphic permutation groups. Cambridge University Press, Cambridge, 1990.
[6] P.J. Cameron. The algebra of an age. In Model theory of groups and automorphism groups
(Blaubeuren, 1995), pages 126–133. Cambridge Univ. Press, Cambridge, 1997.
[7] P.J. Cameron. On an algebra related to orbit-counting. J. Group Theory 1 (1998), no. 2, 173–
[8] P.J. Cameron. Sequences realized by oligomorphic permutation groups. J. Integer Seq., 3(1):Ar-
ticle 00.1.5, 1 HTML document (electronic), 2000.
[9] P.J. Cameron. Some counting problems related to permutation groups. Discrete Math., 225(1-
3):77–92, 2000. Formal power series and algebraic combinatorics (Toronto, ON, 1998).
[10] P.J. Cameron.Problems on permutation groups, http://www.maths.qmul.ac.uk/∼pjc/pgprob.html.
http://www.maths.qmul.ac.uk/~pjc/pgprob.html
A CONJECTURE OF P.J. CAMERON 19
[11] R. Diestel. Graph Theory. Springer-Verlag, Heidelberg Graduate Texts in Mathematics, Volume
173, 2005, 431 pages.
[12] R. Fräıssé. Cours de logique mathématique. Tome 1: Relation et formule logique. Gauthier-
Villars Éditeur, Paris, 1971.
[13] R. Fräıssé. Theory of relations. North-Holland Publishing Co., Amsterdam, 2000.
[14] R. Fräıssé and Maurice Pouzet. Interprétabilité d’une relation pour une châıne. C. R. Acad.
Sci. Paris Sér. A-B, 272:A1624–A1627, 1971.
[15] D.H. Gottlieb. A class of incidence matrices, Proc. Amer. Math. Soc., 17(1966)1233-1237.
[16] R. Graham, B. Rothschild, J.H. Spencer, Ramsey Theory, John Wiley and Sons, NY (1990).
[17] G. Higman. Ordering by divisibility in abstract algebras. Proc. London Math. Soc. (3), 2:326–
336, 1952.
[18] W. Hodges, Model Theory, Cambridge University Press, Cambridge, 1993. xiv+772 pp.
[19] W.M. Kantor. On incidence matrices of finite projective and affine spaces, Math. Z.,
124(1972)315–318.
[20] D. Livingstone, A. Wagner, Transitivity of finite permutation groups on unordered sets. Math.
Z., 90(1965) 393-403.
[21] M. Lothaire. Combinatorics on words. Vol. 17 of Encyclopedia of Mathematics and its Appli-
cations. Addison-Wesley, Reading, Mass. Reprinted in the Cambridge Mathematical Library,
Cambridge University Press, U.K. 1997.
[22] H.D. Macpherson. Growth rates in infinite graphs and permutation groups. Proc. London Math.
Soc. (3), 51(2):285–294, 1985.
[23] M. Pouzet. Application d’une propriété combinatoire des parties d’un ensemble aux groupes et
aux relations. Math. Z., 150(2):117–134, 1976.
[24] M. Pouzet. Sur la théorie des relations. Thèse d’état, Université Claude-Bernard, Lyon 1, 1978.
[25] M. Pouzet. Relation minimale pour son âge. Z. Math. Logik Grundlag. Math., 25(1979) 315–344.
[26] M. Pouzet. Application de la notion de relation presque-enchâınable au dénombrement des
restrictions finies d’une relation. Z. Math. Logik Grundlag. Math., 27(4):289–332, 1981.
[27] M. Pouzet. Relation impartible. Dissertationnes, 103(1981)1–48.
[28] M. Pouzet. The profile of relations. Glob. J. Pure Appl.Math. Volume 2, Number 3 (2007), pp.
237–272 (Proceedings of the 14th Symposium of the Tunisian Mathematical Society held in
Hammamet, March 20-23, 2006). ArXiv math.CO/0703211.
[29] M. Pouzet and M. Sobrani. Sandwiches of ages. Ann. Pure Appl. Logic, 108 (3)(2001) 295–326.
[30] M. Pouzet, N. Thiéry. Some relational structures with polynomial growth and their associ-
ated algebras. May 10th, 2005, 19pages, presented at FPSAC for the 75 birthday of A.Garsia.
http://arxiv.org/math.CO/0601256.
[31] D. E. Radford, A natural ring basis for the shuffle algebra and an application to group schemes,
J. Algebra 58 (1979), 432-454.
[32] F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc., 30 (1930) 264-286.
ICJ, Mathématiques, Université Claude-Bernard Lyon1, Domaine de Gerland, Bât.
Recherche [B], 50 avenue Tony-Garnier, F69365 Lyon cedex 07, France, e-mail: pouzet@univ-
lyon1.fr
http://arxiv.org/abs/math/0703211
http://arxiv.org/math.CO/0601256
	 Introduction
	0.1. The conjectures
	0.2. The algebra of an age
	0.3. A transversality property of the set algebra
	0.4. Age algebra and profile of a relational structure
	1. Proof of Theorem ??
	1.1. Invariant relational structures and their age algebra
	1.2. The existence of (m,n)
	2. The Gottlieb-Kantor theorem and the case m=1 
	3. A lower bound for (m,n)
	References
