[vstyle = Shade]

# Classification of $P$-oligomorphic groups, conjectures of Cameron and
Macpherson

Justine Falque and Nicolas M. Thiéry  Univ Paris-Sud, Laboratoire de Recherche
en Informatique, Orsay; CNRS, Orsay, F-91405, France

###### Abstract.

Let $G$ be a group of permutations of a denumerable set $E$. The profile of
$G$ is the function $\varphi_{G}$ which counts, for each $n$, the (possibly
infinite) number $\varphi_{G}(n)$ of orbits of $G$ acting on the $n$-subsets
of $E$. Counting functions arising this way, and their associated generating
series, form a rich yet apparently strongly constrained class. In particular,
Cameron conjectured in the late seventies that, whenever the profile
$\varphi_{G}(n)$ is bounded by a polynomial – we say that $G$ is
$P$-oligomorphic –, it is asymptotically equivalent to a polynomial. In 1985,
Macpherson further asked whether the orbit algebra of $G$ – a graded
commutative algebra invented by Cameron and whose Hilbert function is
$\varphi_{G}$ – is finitely generated.

In this paper we establish a classification of (closed) $P$-oligomorphic
permutation groups in terms of _finite permutation groups with decorated
blocks_.

It follows from the classification that the orbit algebra of any
$P$-oligomorphic group is isomorphic to (a straightforward quotient of) the
invariant ring of some finite permutation group. This answers positively both
Cameron’s conjecture and Macpherson’s question. The orbit algebra is in fact
Cohen-Macaulay; therefore the generating series of the profile is a rational
fraction whose numerator has positive coefficients, while the denominator
admits a combinatorial description.

In addition, the classification provides a finite data structure for encoding
closed $P$-oligomorphic groups. This paves the way for computing with them and
enumerating them as well as for proofs by structural induction. Finally, the
relative simplicity of the classification gives hopes to extend the study to,
e.g., the class of (closed) permutations groups with sub-exponential profile.

The proof exploits classical notions from group theory – notably block systems
of permutation groups and their lattice properties –, commutative algebra, and
invariant theory.

###### Key words and phrases:

Infinite permutation groups, orbit counting, profiles, generating series,
orbit algebras, invariant theory, $\aleph_{0}$-categorical complete theories,
homogeneous relational structures

##  1\. Introduction

###  1.1. A conjecture of Cameron and a question of Macpherson

Counting objects under a group action is a classical endeavor in algebraic
combinatorics. If $G$ is a permutation group acting on a finite set $E$,
Burnside’s lemma provides a formula for the number of orbits, while Pólya
theory refines this formula to compute, for example, the profile of $G$, that
is, the function which counts, for each $n\in\mathbb{N}$, the number
$\varphi_{G}(n)$ of orbits of $G$ acting on subsets of size $n$ of $E$.

In the seventies, Cameron initiated the study of the profile when $G$ is
instead a permutation group of an infinite set $E$. Of course the question
makes sense mostly if $\varphi_{G}(n)$ is finite for all $n$; in that case,
the group is called oligomorphic, and the infinite sequence
$\varphi_{G}=(\varphi_{G}(n))_{n}$ an orbital profile.

This setting includes, for example, counting integer partitions (with optional
length and height restrictions) or graphs up to an isomorphism. It also
relates naturally to logic: indeed Ryll-Nardzewski’s Theorem [RN59] implies
that orbital profiles (of oligomorphic groups) are exactly the profiles of
$\aleph_{0}$-categorical theories, that is, _complete theories admitting a
unique countable model_ (see [Cam90, Section 2.5] for further details).

The study of oligomorphic permutation groups has become a whole research
subject; see [Cam90, Cam09] for surveys. One central topic is the description
of general properties of orbital profiles. It was soon observed that the
potential growth rates exhibited jumps. For example, the profile either grows
at least as fast as the partition function, or is bounded by a polynomial
[Mac85a, Theorem 1.2]. In the latter case – we say that $G$ is
$P$-oligomorphic – it was conjectured to be asymptotically polynomial:

######  Conjecture 1.1 (Cameron [Cam90]).

Let $G$ be a $P$-oligomorphic permutation group. Then $\varphi_{G}(n)\sim
an^{k}$ for some $a>0$ and $k\in\mathbb{N}$.

As a tool in this study, Cameron introduced early on the orbit algebra
$\mathbb{Q}\mathcal{A}(G)$ of $G$, a graded connected commutative algebra
whose Hilbert function coincides with $\varphi_{G}$. As proved in [Pou08], it
is always an integral domain (assuming empty kernel), implying that the
profile is non decreasing.

Macpherson asked the following:

######  Question 1.2 (Macpherson [Mac85a] p. 286).

Let $G$ be a $P$-oligomorphic permutation group. Is $\mathbb{Q}\mathcal{A}(G)$
finitely generated?

The point is that, by standard commutative algebra, whenever
$\mathbb{Q}\mathcal{A}(G)$ is finitely generated, its Hilbert function is
asymptotically polynomial, as conjectured by Cameron. It is in fact
_eventually a quasi polynomial_ (with a constant leading coefficient).
Equivalently, the generating series of the profile
$\mathcal{H}_{G}=\sum_{n\in\mathbb{N}}\varphi_{G}(n)z^{n}$ is a rational
fraction of the form

$\mathcal{H}_{G}=\frac{P(z)}{\prod_{i\in I}(1-z^{d_{i}})}\,,$

where $P(z)$ is a polynomial in $\mathbb{Z}[z]$ and the $d_{i}$’s are the
degrees of the generators.

###  1.2. Main results

In the extended abstract [FT18], we had announced positive answers to both
Cameron’s conjecture and Macpherson’s question with sketches of proof. In this
paper we deliver a much stronger result with full proofs, namely the extension
of the classification of the five oligomorphic groups with constant profile
$1$ [Cam90] to a classification of all closed $P$-oligomorphic groups (Theorem
5.22): any such group $G$ is uniquely classified by a finite piece of data
$\Delta$, encoded as a finite permutation group endowed with a block system
whose blocks are suitably decorated. This data can be extracted from $G$ by a
detailed analysis of its lattice of _nested block systems_ (block systems of
block systems); conversely, the group can be reconstructed from the data using
wreath products of finite permutation groups with one of the five (closed)
highly homogeneous groups, direct products, and diagonal actions of finite
permutation groups.

We then derive from the classification that the orbit algebra of any
$P$-oligomorphic group $G$ (closed or not111The profile and orbit algebra of
an oligomorphic group and those of its closure coincide.) is isomorphic to (a
straightforward quotient of) the invariant ring of some finite permutation
group. By standard invariant theory, the latter is finitely generated and even
Cohen-Macaulay.

It follows that the generating series of the profile is of the form

(1) $\mathcal{H}_{G}=\frac{P(z)}{\prod_{i\in I}(1-z^{d_{i}})}\,,$

where the fraction is irreducible and $P$ is in $\mathbb{N}[z]$; therefore we
have $\varphi_{G}(n)\sim an^{|I|-1}$ for some $a>0$.

###  1.3. Connections with profiles and age algebras of relational structures

This research is part of a larger program initiated in the seventies: the
study of the _profile of relational structures_ [Fra00, Pou06] and in general
of the behavior of counting functions for hereditary classes of finite
structures, like undirected graphs, posets, tournaments, ordered graphs, or
permutations; see [Kla08, Bol98] for surveys.

In this program, _jumps_ in the set of potential growth rates of profiles are
a ubiquitous phenomenon: not all growths are encountered. For instance,
undirected graphs [BBSS09] and permutation classes [KK03] both exhibit such
jumps: the counting functions, when bounded by a polynomial, are actually
asymptotically equivalent to a polynomial. Besides, by [PT13, Theorem 1.7],
the class of relational structures with _finite monomorphic dimension_ – rough
analogues of transitive groups with a finite number of infinite blocks – also
exhibits these jumps. Thanks to our proof of Cameron’s conjecture, the same is
known to hold for homogeneous relational structures, which correspond to
oligomorphic permutation groups. This, together with evidence from many
examples, suggests that a suitable generalization of the notion of block
systems may enable to prove that large classes of relational structures
exhibit such jumps in the possible profile growths.

In [Cam97], Cameron extends the definition of orbit algebra to the general
context of relational structures. The Cohen-Macaulay property holds when the
profile is bounded (see [Pou06, Theorem 26] and [PT13, Theorem 1.5]); it can
fail as soon as the profile grows faster. Similarly, finite generation often
fails; however, when the monomorphic dimension is finite, there exists a
combinatorial characterization of when it holds [PT18].

###  1.4. Structure of the paper

This paper is structured as follows. In Section 2, we review the basic
definitions of profiles and orbit algebras, and provide classical examples and
operations. We then recall some group theory tools that we will be using a
lot, such as the central notion of block systems and the subdirect product of
groups, that will later help us handle interactions between the blocks of a
given system.

In Section 3, we see that block systems provide lower bounds on the growth of
the profile. This motivates the study of block systems and their lattice
properties, which leads to the identification of a canonical system of blocks
of blocks.

The classification of closed $P$-oligomorphic groups with a single block of
blocks is established in Section 4. It was informed by an extensive computer
exploration where $P$-oligomorphic groups were approximated by finite groups.
The proof exploits towers of groups and subdirect products to suitably control
synchronizations, and encapsulates the most technical aspects of this paper.

Section 5 builds on the previous one to extend the classification to all
$P$-oligomorphic groups, after establishing the existence of a minimal finite
index subgroup, which, together with a finite group acting diagonally,
generates $G$.

Finally, in Section 6, we deduce from the classification that the orbit
algebra is (a trivial quotient of) an invariant ring, providing positive
answers to Cameron’s conjecture and Macpherson’s question, and further
deducing that it is Cohen-Macaulay.

###  1.5. Perspectives

A notable outcome of the classification is that it provides a uniform finite
description of any $P$-oligomorphic group; otherwise said a data structure.
This prepares the ground for algorithms and computations with $P$-oligomorphic
groups: constructing $P$-oligomorphic groups from their classification,
combining them together (cartesian or wreath products), computing their
properties such as the generating series of the profile, constructing the
orbit algebras and doing arithmetic with their elements, etc. The
classification also paves the way for computations about the class of
$P$-oligomorphic groups: there are indeed countably many of them and we may
iterate through them, count them by kernel size and profile growth, etc. These
algorithms are being implemented in a library on top of SageMath [The20] and
are the topic of a follow-up publication; see the first author’s PhD
dissertation [Fal19] in the meantime.

The classification also enables proofs by structural induction: if a property
holds for the five closed permutation groups with profile $1$ and is stable
under wreath products, cartesian products and taking finite index group
extensions, then it holds for any closed $P$-oligomorphic group. It holds more
generally for any permutation group obtained by such an inductive
construction. This class of oligomorphic permutation groups would be worth
studying for its own sake. At this stage, it seems plausible that it contains
all oligomorphic permutation groups with subexponential profile growth, and
that classifying those is within reach. On the other hand there is little hope
beyond exponential growth, due to the appearance of new, more complicated
primitive groups.

###  1.6. Acknowledgments

We would like to heartily thank Maurice Pouzet for suggesting to work on this
conjecture, and Peter Cameron and Maurice Pouzet for enlightening discussions
and benevolent encouragements throughout the project.

This research was supported by extensive computer exploration, using the open
source mathematical systems GAP [GAP99] and SageMath [The20]. We are grateful
to their communities for their continuous support, notably at the occasion of
dissemination events of the OpenDreamKit Horizon 2020 European Research
Infrastructures project (#676541).

##  2\. Preliminaries

###  2.1. The age, profile and orbit algebra of a permutation group

Let $G$ be a permutation group, that is, a group of permutations of some set
$E$. Unless stated otherwise, $E$ is denumerable and $G$ is infinite. The
action of $G$ on the elements of $E$ induces an action on the set
$\mathscr{E}_{E}$ of finite subsets of $E$.

The age of $G$ is the set $\mathcal{A}(G)$ of the orbits of finite subsets in
$\mathscr{E}_{E}$ under this action. Within an orbit, all subsets share the
same cardinality, which is called the degree of the orbit. This gives a
grading of the age according to the degree of the orbits:
$\mathcal{A}(G)=\sqcup_{n\in\mathbb{N}}\mathcal{A}(G)_{n}$; we will also use
the notation
$\mathcal{A}(G)^{+}=\sqcup_{n\in\mathbb{N}\backslash\\{0\\}}\mathcal{A}(G)_{n}$.
The profile of $G$ is the function $\varphi_{G}:n\mapsto|\mathcal{A}(G)_{n}|$.
In general, the profile may take infinite values; the group is called
oligomorphic if it does not.

We call growth rate of a profile bounded by a polynomial the smallest number
$r$ satisfying $\varphi_{G}(n)=O(n^{r})$; for instance, the growth rate of
$n^{2}+n$ is $2$. By extension, the growth rate of a permutation group $G$ is
that of its profile $\varphi_{G}$.

######  Definition 2.1.

We say that a permutation group is $P$-oligomorphic if its profile is bounded
by a polynomial.

######  Examples 2.2.

Let $G$ be the infinite symmetric group $\mathfrak{S}_{\infty}$. For each $n$
there is a single orbit containing all subsets of size $n$, hence
$\varphi_{G}(n)=1$ for all $n$. We say that $G$ is _highly homogeneous_ , or,
more informally, that it _has profile $1$_.

Now take $E=E_{1}\sqcup E_{2}$, where $E_{1}$ and $E_{2}$ are two copies of
$\mathbb{N}$. Let $G$ be the group acting on $E$ by permuting the elements
independently within $E_{1}$ and $E_{2}$ and by exchanging $E_{1}$ and
$E_{2}$: $G$ is the wreath product $\mathfrak{S}_{\infty}\wr\mathfrak{S}_{2}$.
In that case, the orbits of subsets of cardinality $n$ are in bijection with
the integer partitions of $n$ with at most $2$ parts. See Figure 1 and Figure
2 for other examples of wreath products.

$\mathfrak{S}_{\infty}$ $\mathfrak{S}_{\infty}\wr\mathfrak{S}_{5}$

$\mathfrak{S}_{5}$

Figure 1. An example of a wreath product:
$\mathfrak{S}_{\infty}\wr\mathfrak{S}_{5}$; the two highlighted subsets, in
red and blue respectively, are in the same orbit.

Cameron’s orbit algebra of $G$ is the graded connected vector space
$\mathbb{Q}\mathcal{A}(G)$ of formal finite linear combinations of elements of
$\mathcal{A}(G)$; it is endowed with a commutative product as follows: let
$\mathbb{Q}\mathscr{E}_{E}$ be the _set algebra_ of $E$, namely the vector
space $\mathbb{Q}\mathscr{E}_{E}$ of (possibly infinite) formal linear
combinations of finite subsets of $E$, endowed with the _disjoint product_
that maps two finite subsets to their union if they are disjoint and to $0$
otherwise. Embed the orbit algebra $\mathbb{Q}\mathcal{A}(G)$ in the set
algebra $\mathbb{Q}\mathscr{E}_{E}$ through the linear morphism $i_{G}$ that
maps each orbit to the sum of its elements. The disjoint product stabilizes
$i_{G}(\mathbb{Q}\mathcal{A}(G))$ and can thus be retracted to
$\mathbb{Q}\mathcal{A}(G)$. Some care needs to be taken at each step to check
that everything is well defined; see [Cam90, Cam09] for details.

######  Example 2.3.

  * •

Assume, as an exception, that $G$ is a finite permutation group. Then its
orbit algebra is finitely generated (likely with redundancy) by its age, of
which all elements are nilpotent of finite order (bounded by the degree of the
finite group $G$). It is thus of Krull dimension 0.

  * •

Take $G=\mathfrak{S}_{m}$ for some $m\in\mathbb{N}$. The profile is 1 until
$n=m$ and 0 beyond, and the orbit algebra is finitely generated as a vector
space: it is isomorphic to $\mathbb{Q}[y]$, where $y$ is nilpotent of order
$m+1$. Take this to its infinite analogue, that is, $G=\mathfrak{S}_{\infty}$;
then, $\mathbb{Q}\mathcal{A}(G)$ is isomorphic to the algebra $\mathbb{Q}[x]$
of univariate polynomials. Indeed, if $e_{n}$ denotes the unique orbit of all
subsets of size $n$, then the morphism which maps $x^{n}$ onto $n!e_{n}$ is a
morphism of algebras (use that, the way the orbital product goes, we have
$e_{k}e_{\ell}={{k+\ell}\choose{k}}e_{k+\ell}$).

  * •

Take on the other end the trivial permutation group on $E$. Each orbit
consists of a single subset, and the profile counts for each $n$ the subsets
of size $n$ of $E$. When $E$ is infinite, the group is not at all
$P$-oligomorphic nor even oligomorphic; its orbit algebra is the free algebra
generated by the infinitely many singletons in $E$.

###  2.2. Basic properties and operations

We recall here a few technical basics about orbit algebras and profiles, in
particular dealing with subgroups or restrictions, that one expects indeed to
be able to manipulate in a natural way.

######  Lemma 2.4 (Relations between orbit algebras).

  1. (1)

Let $G$ be a permutation group acting on $E$, and $F$ be a stable subset of
$E$. Then, $\mathbb{Q}\mathcal{A}({G}_{|F})$ is both a subalgebra and a
quotient of $\mathbb{Q}\mathcal{A}(G)$.

  2. (2)

Let $G$ be a permutation group acting on $E$, and $H$ be a subgroup, both of
which being oligomorphic. Then, $\mathbb{Q}\mathcal{A}(G)$ is a subalgebra of
$\mathbb{Q}\mathcal{A}(H)$.

###### Proof.

We exhibit the natural morphisms for each one of these cases.

  1. (1)

We have the following commutative diagram

${\mathbb{Q}\mathscr{E}_{F}}$${\mathbb{Q}\mathscr{E}_{E}}$${\mathbb{Q}\mathcal{A}(G_{|F})}$${\mathbb{Q}\mathcal{A}(G)}$${\mathbb{Q}\mathscr{E}_{F}}$${\mathbb{Q}\mathscr{E}_{E}}$$\scriptstyle{\subseteq}$$\scriptstyle{i_{G_{|F}}}$$\scriptstyle{\phi}$$\scriptstyle{i_{G_{|F}}}$$\scriptstyle{i_{G}}$$\scriptstyle{\psi}$$\scriptstyle{i_{G}}$$\scriptstyle{\pi}$

where $\pi$ is the linear morphism mapping a subset of $E$ to itself if it is
a subset of $F$ and to 0 otherwise. The injective morphisms $i_{G}$ and
$i_{G_{|F}}$ are reversible where needed, which allows to define the
respectively injective and surjective morphisms $\phi$ and $\psi$ by
composition.

  2. (2)

In the following diagram, $i_{G}$ and $i_{H}$ are the canonical embeddings of
the orbit algebras into their set algebras.

${\mathbb{Q}\mathscr{E}_{E}}$${\mathbb{Q}\mathcal{A}(G)}$${\mathbb{Q}\mathcal{A}(H)}$$\scriptstyle{i_{G}}$$\scriptstyle{\phi}$$\scriptstyle{i_{H}}$

The orbits of $G$ are unions of orbits (of same degree) of $H$, and since the
groups are oligomorphic these unions are finite. The image of $i_{G}$ is thus
a subset of the image of $i_{H}$, and therefore the diagram is commutative.∎

######  Lemma 2.5 (Direct product).

Let $G$ and $H$ be permutation groups acting on $E$ and $F$ respectively. Take
$G\times H$ endowed with its natural action on the disjoint union $E\sqcup F$.
Then, $\mathcal{A}(G\times H)\simeq\mathcal{A}(G)\times\mathcal{A}(H)$, and
$\mathbb{Q}\mathcal{A}(G\times
H)\simeq\mathbb{Q}\mathcal{A}(G)\otimes\mathbb{Q}\mathcal{A}(H)$; it follows
that $\mathcal{H}_{G\times H}=\mathcal{H}_{G}\mathcal{H}_{H}$.

######  Lemma 2.6.

Let $G$ be a permutation group and $K$ be a normal subgroup of finite index.
Then,

$\varphi_{G}(n)\ \leq\ \varphi_{K}(n)\ \leq\ |G:K|\varphi_{G}(n)\,.$

In particular, $K$ and $G$ share the same profile growth.

###### Proof.

Let $O$ be a $G$-orbit of elements. Since $K$ is a normal subgroup, $O$ splits
into $K$-orbits on which $G$ – and actually $G/K$ – acts transitively by
permutation; there are thus finitely many such $K$-orbits, all of the same
size. In particular, infinite $G$-orbits split into infinite $K$-orbits, and
similarly for finite ones. ∎

###  2.3. Block systems and primitive groups

A key notion when studying permutation groups is that of block systems; they
are the discrete analogues of quotient modules in representation theory. A
block system is a partition of $E$ into parts, called blocks, such that each
$g\in G$ maps blocks onto blocks.

######  Example 2.7.

Following is the list of all block systems of the cyclic permutation group
$\mathcal{C}_{4}$:
$\\{\\{1,2,3,4\\}\\},~{}\\{\\{1,3\\},\\{2,4\\}\\},~{}\\{\\{1\\},\\{2\\},\\{3\\},\\{4\\}\\}$.

1234

The partitions $\\{E\\}$ and $\\{\\{e\\}\mid e\in E\\}$ are always block
systems and are therefore called the trivial block systems. A permutation
group is primitive if it admits no non trivial block system. By extension, an
orbit of elements is primitive if the restriction of the group to this orbit
is primitive, and a block may be called primitive if it cannot be refined into
smaller non trivial blocks.

The following two theorems will be central in our study.

######  Theorem 2.8 (Macpherson [Mac85b] Theorem 1.1; see also [Cam90]
(3.21)).

The profile of an oligomorphic primitive permutation group is either the
constant function $1$ or bounded below by an exponential.

In our study of Macpherson’s question, all profiles are assumed to be bounded
by a polynomial, and therefore primitive groups always have profile $1$: in
other words, they are highly homogeneous. These groups are classified (up to
_closure_ ; see below).

######  Theorem 2.9 (Cameron [Cam90] (Section 3.4)).

There are only five closed highly homogeneous groups:

  1. (1)

The automorphism group $\operatorname{Aut}(\mathbb{Q})$ of the rational chain
(order-preserving bijections on $\mathbb{Q}$);

  2. (2)

$\mathrm{Rev}(\mathbb{Q})$ (generated by $\operatorname{Aut}(\mathbb{Q})$ and
a reflection);

  3. (3)

$\operatorname{Aut}(\mathbb{Q}/\mathbb{Z})$, preserving the cyclic order (see
$\mathbb{Q}/\mathbb{Z}$ as a circle);

  4. (4)

$\mathrm{Rev}(\mathbb{Q}/\mathbb{Z})$, generated by
$\mathrm{Cyc}(\mathbb{Q}/\mathbb{Z})$ and a reflection;

  5. (5)

$\mathfrak{S}_{\infty}$.

In the vocabulary of model theory, these are the groups preserving,
respectively, the dense linear order, the betweenness order, the circular
order, the separation relation, and a pure set.

The notion of closure refers here to the topology of simple convergence,
described in Section 2.4 of [Cam90]. Thanks to the following classical lemma,
it plays only a minor role for our purposes.

######  Lemma 2.10.

A permutation group and its closure share the same profile and orbit algebra.

###### Proof.

Let $G$ be a permutation group acting on a set $E$, and take two finite
subsets $A$ and $A^{\prime}$ that are in the same orbit for its closure: there
exists a permutation $\sigma$ of the closure that maps $A$ to $A^{\prime}$. By
definition of the closure (for the simple convergence), there exists a
sequence $(\sigma_{i})_{i}$ of permutations in $G$ that coincide with $\sigma$
on more and more elements of $E$. Eventually, $\sigma_{i}$ will coincide with
$\sigma$ on $A$, and therefore $A$ and $A^{\prime}=\sigma_{i}(A)$ are in the
same $G$-orbit. The age is thus the same for $G$ and its closure, and with it
the profile and the orbit algebra. ∎

We make the following remark, that will prove crucial later on.

######  Remark 2.11.

The set of the (closed) highly homogeneous permutation groups is stable under
taking finite index normal subgroups. Among those, three out of five,
$\operatorname{Aut}(\mathbb{Q})$, $\operatorname{Aut}(\mathbb{Q}/\mathbb{Z})$
and $\mathfrak{S}_{\infty}$, have no proper finite index normal subgroup. We
will refer to them as _the three minimal highly homogeneous groups_.

######  Lemma 2.12.

Let $G$ be a (closed) $P$-oligomorphic permutation group, endowed with a block
system. If an infinite $G$-orbit of blocks is primitive and the blocks of the
orbit are not singletons, then the action on these blocks is isomorphic to
$\mathfrak{S}_{\infty}$.

###### Proof.

Using Theorem 2.9, the action on the set of blocks is given by one of the five
closed highly homogeneous groups.

Assume first that $G$ acts as $\operatorname{Aut}(\mathbb{Q})$ on the blocks.
Take $m\in\mathbb{N}$. Choose an $m$-tuple of distinct blocks and, for each
word $u=u_{1}\cdots u_{m}$ in the letters $1$ and $2$, choose a set $A_{u}$ of
size $u_{1}+\cdots+u_{m}$ by picking, for each $i$, $u_{i}$ elements from the
$i$-th block. Since $G$ preserves the blocks and cannot swap their order,
$(A_{u})_{u}$ is a collection of $2^{m}$ non isomorphic sets of size between
$m$ and $2m$. Hence $\sum_{n=m}^{2m}\varphi_{G}(n)\geq 2^{m}$. Taking $m$
large enough, we obtain a contradiction with $G$ being $P$-oligomorphic.

The argument extends straightforwardly to the three other non symmetric highly
homogeneous groups: the words $u$ just need to be considered up to a
reflection, a cyclic permutation of the letters, or both; neither changes the
exponential growth. ∎

###  2.4. Wreath products

Let $G$ and $H$ be permutation groups acting on $E$ and $F$ respectively.
Intuitively, the wreath product $G\wr H$ acts on $|F|$ copies $(E_{f})_{f\in
F}$ of $E$, by permuting elements within each copy of $E$ independently
according to $G$ and permuting the copies according to $H$. By construction,
the partition $(E_{f})_{f\in F}$ forms a block system, and $G\wr H$ is not
primitive (unless $G$ or $H$ is and $F$ or $E$, respectively, is of size 1).

######  Examples 2.13 (Algebras of wreath products).

  1. (1)

Let $G$ be the wreath product $\mathfrak{S}_{\infty}\wr\mathfrak{S}_{k}$. The
profile counts integer partitions with at most $k$ parts. The orbit algebra is
the algebra of symmetric polynomials over $k$ variables, that is, the free
commutative algebra with generators of degrees $1,\dots,k$. The generating
series of the profile is given by
$\mathcal{H}_{G}=\frac{1}{\prod_{d=1,\ldots,k}(1-z^{d})}$.

See also Figure 1, on which the red and blue subsets are in the same orbit.
The associated integer partition $(3,1)$ can be read on the blue subset.

  2. (2)

Let $G^{\prime}$ be a finite permutation group. Then, the orbit algebra of
$G=\mathfrak{S}_{\infty}\wr G^{\prime}$ is isomorphic to the invariant ring
$\mathbb{Q}[X]^{G^{\prime}}$, which consists of the polynomials in
$\mathbb{Q}[X]=\mathbb{Q}[X_{1},\ldots,X_{k}]$ that are invariant under the
action of $G^{\prime}$.

  3. (3)

Let $G^{\prime}$ be a finite permutation group. Then, the orbit algebra of
$G=G^{\prime}\wr\mathfrak{S}_{\infty}$ is the free commutative algebra
generated by the the set $\mathcal{A}(G^{\prime})^{+}$ of the
$G^{\prime}$-orbits of non trivial subsets. The generating series of the
profile is given by $\mathcal{H}_{G}=\frac{1}{\prod_{d}(1-z^{d})}$, where $d$
runs through the degrees of $\mathcal{A}(G^{\prime})^{+}$, taken with
multiplicity.

###### Sketch of proof.

The first item is a special case of the second one, that we examine now. Two
subsets having the same number of elements in each infinite block are in the
same orbit, so if one canonically embeds the orbit algebra of $G$ into the set
algebra of $E$, it is a subspace of that generated by the infinite sums

$S_{\alpha}=\sum_{\text{card}(e\cap B_{i})=\alpha_{i}}{\textit{\large
e}}~{}~{},\qquad\qquad\alpha=(\alpha_{1},\ldots,\alpha_{k})$

for each multi-index $\alpha$ of length the number of infinite blocks (that is
the degree of $G^{\prime}$), $B_{i}$ being the $i$-th block and e the subsets
of $E$. Now use the morphism $S_{\alpha}\mapsto
X^{\alpha}=\prod_{i}X_{i}^{\alpha_{i}}$ to embed $\mathbb{Q}\mathcal{A}(G)$
into the algebra of polynomials. The action of $G^{\prime}$ on the blocks acts
the variables the same way, so the image of $\mathbb{Q}\mathcal{A}(G)$ is the
algebra of invariants of $G^{\prime}$.

Set $G=G^{\prime}\wr\mathfrak{S}_{\infty}$ in order to prove the third item. A
canonical one-to-one correspondence can easily be established between
$G$-orbits and multisets of $\mathcal{A}(G^{\prime})^{+}$: a finite subset of
$E$ consists of a disjoint union of subsets that are included in the blocks,
and thus each $G$-orbit is determined by the non trivial $G^{\prime}$-orbits
of these subsets, while the order does not matter. Since, the Hilbert series
only depends on the structure of graded vector space, it is then
$\frac{1}{\prod_{d}(1-z^{d})}$, where the $d$’s are the orbital degrees of
$\mathcal{A}(G^{\prime})^{+}$, the set of generators.

Define now an alternative notion of degree $\delta$, the number of blocks
involved in (the representatives of) an orbit. In the orbit algebra
$\mathbb{Q}\mathcal{A}(G)$, the product of two orbits $O_{1}$ and $O_{2}$ has
one and only one dominant term for $\delta$, followed by lower degree terms
(we say that $\delta$ is a _filtration_ , but we will not go into the details
about this notion). It is easy to see that the dominant term is the orbit that
corresponds to the multiset $\\{O_{1},O_{2}\\}$. Therefore, every $G$-orbit
can be obtained as the dominant term of such a product of $G^{\prime}$-orbits
in $\mathbb{Q}\mathcal{A}(G)$, and since $\delta$ decreases on the other
terms, it can actually be realized as a linear combination of products of
$G^{\prime}$-orbits (this can be argued by induction on $\delta$). Hence
$\mathcal{A}(G^{\prime})^{+}$ generates all of $\mathbb{Q}\mathcal{A}(G)$.

On the other hand, and by homogeneity, the shape of the Hilbert series imply
that it is also a free family of elements: one can consider the canonical
morphism with the corresponding polynomial algebra (with indeterminates of the
degrees of $\mathcal{A}(G^{\prime})^{+}$), and deduce by dimension that it is
an isomorphism. ∎

$\mathfrak{S}_{k}$ …

$\mathfrak{S}_{\infty}$

Figure 2. Example of a wreath product:
$\mathfrak{S}_{k}\wr\mathfrak{S}_{\infty}$, with two subsets in the same orbit

We recall in the sequel some properties of wreath products that will prove
helpful later on.

######  Proposition 2.14.

Let $F_{1}$, $F_{2}$, $P_{1}$ and $P_{2}$ be permutation groups such that
$F_{1}$ (resp. $P_{1}$) is a normal subgroup of $F_{2}$ (resp. $P_{2}$). Then,
$F_{1}\wr P_{1}$ is a normal subgroup of $F_{2}\wr P_{2}$, and we have
$(F_{2}\wr P_{2})/(F_{1}\wr P_{1})\simeq(F_{2}/F_{1})\wr(P_{2}/P_{1})$.

###### Sketch of proof.

Denote each element of $(F_{2}\wr P_{2})$ as $g=((g_{i})_{i},p)$, with $i$
running through the domain of $P_{2}$, $g_{i}$ in $F_{2}$ for each $i$, and
$p$ in $P_{2}$. Then check that the following defines a natural isomorphism:

$\begin{cases}(F_{2}\wr P_{2})/(F_{1}\wr
P_{1})&\longrightarrow(F_{2}/F_{1})\wr(P_{2}/P_{1})\\\ g.(F_{1}\wr
P_{1})&\longmapsto((g_{i}.F_{1})_{i},\,p.P_{1})\end{cases}\qed$

######  Corollary 2.15.

If $P_{1}$ and $P_{2}$ have finite degree $m$, we have

$[F_{1}\wr P_{1}:F_{2}\wr P_{2}]=[F_{1}:F_{2}]^{m}[P_{1}:P_{2}]\,.$

If the degree of $P_{1}$ and $P_{2}$ is infinite, $F_{1}\wr P_{1}$ is of
infinite index in $F_{2}\wr P_{2}$ as soon as $F_{1}$ is a proper subgroup of
$F_{2}$.

###### Proof.

This is a direct consequence of Proposition 2.14 and the fact that a wreath
product $F\wr P$ is of order $|F|^{m}|P|$ where $m$ is the degree of the
permutation group $P$. ∎

###  2.5. Subdirect products

The previous two subsections dwelled on particular, well described and well
understood kinds of $P$-oligomorphic groups. In Section 3 we will see that the
support $E$ of any $P$-oligomorphic group $G$ splits up into pieces on each of
which $G$ essentially acts as one of those well understood groups. In the
later sections, we will recover the desired properties of $G$ (profile, orbit
algebra) by controlling how the different pieces interact together using the
classical notion of _subdirect product_ , which we recall here.

Let us start with the intuition. Assume that $E$ splits into $G$-stable
subsets $(E_{i})_{i}$. The actions of $G$ on each $E_{i}$ are not independent
from each other in general: there may be partial or full synchronization
between the actions, which has consequences on the profile and the orbit
algebra. For two subsets this can be formalized by describing $G$ as a
subdirect product. The general case can then be treated by induction.

######  Definition 2.16.

Let $G_{1}$ and $G_{2}$ be groups. A subdirect product of $G_{1}$ and $G_{2}$
is a subgroup of $G_{1}\times G_{2}$ which projects onto each factor under the
canonical projections.

For instance, assume $G$ is a permutation group that has two orbits of
elements $E_{1}$ and $E_{2}$. Then $G$ is a subdirect product of the groups
$G_{1}$ and $G_{2}$ induced respectively on $E_{1}$ and $E_{2}$. Denote
$N_{1}=\operatorname{Fix}_{G}(E_{2})$ and
$N_{2}=\operatorname{Fix}_{G}(E_{1})$, the pointwise stabilizers of $E_{2}$
and $E_{1}$, respectively. Then, $N_{1}$ and $N_{2}$ are normal subgroups of
$G$ and their intersection is trivial, so that we have $<N_{1},N_{2}>\simeq
N_{1}\times N_{2}$.

######  Definition 2.17.

We call synchronization between $G_{1}$ and $G_{2}$ the following isomorphic
quotients (expressed after restriction of $N_{i}$ when needed):

$\frac{G_{1}}{N_{1}}\simeq\frac{G}{N_{1}\times
N_{2}}\simeq\frac{G_{2}}{N_{2}}.$

Intuitively, these quotients describe the parts of each group that are
synchronized, whereas the $N_{i}$ are the independent parts.

######  Proposition 2.18.

Let $G$ be a subdirect product of $G_{1}$ and $G_{2}$. With the above
notations, we have

$G\simeq\\{(g_{1},g_{2})\in G_{1}\times G_{2}\mid g_{1}N_{1}=g_{2}N_{2}\\}.$

This proposition implies that a permutation group arising as a subdirect
product is uniquely characterized by the associated groups $G_{1}$, $G_{2}$,
$N_{1}$ and $N_{2}$.

In addition, the possible synchronizations between two groups are directly
linked to their normal subgroups. This observation combined with the
classification of the groups of profile 1 (see Theorem 2.9) and Remark 2.11,
lead to the following remark.

######  Remark 2.19.

Consider the action of a group $G$ on two infinite primitive orbits of points
or of finite blocks. There is either:

  1. (1)

no synchronization,

  2. (2)

total synchronization,

  3. (3)

a synchronized reflection in the cases of $\mathrm{Rev}(\mathbb{Q})$ and
$\mathrm{Rev}(\mathbb{Q}/\mathbb{Z})$ (synchronization _of order 2_).

On non trivial finite blocks, only the first two situations can occur by Lemma
2.12.

##  3\. The nested block system

Let $G$ be a $P$-oligomorphic permutation group. In this section, we go back
to the notion of block system and take a closer look at how we can exploit it
for our purposes. First, we show that each block system provides a lower bound
on the growth of the profile. Seeking to maximize this lower bound, we
establish the nature of finite lattices of the posets of block systems, and
use it to derive a construction of a special “block system” (for an extended
version of the notion) satisfying appropriate properties. The later sections
will show that this so-called nested block system minimizes synchronization
and provides a tight lower bound.

###  3.1. How block systems provide a lower bound on the profile

We first consider the case where the block system is transitive, that is, $G$
acts transitively on its blocks. In this case, all the blocks are conjugated
and thus share the same cardinality.

######  Lemma 3.1.

Let $G$ be a $P$-oligomorphic permutation group, endowed with a transitive
block system $\mathcal{B}$. Then,

  1. (1)

Case 1: $\mathcal{B}$ has finitely many infinite blocks, as in Example 2.13
(1) and (2). Then $G$ is a subgroup of
$\mathfrak{S}_{\infty}\wr\mathfrak{S}_{k}$ (where $k$ is the number of
blocks), and $\mathbb{Q}\mathcal{A}(G)$ contains $\operatorname{Sym}_{k}$
which is a free algebra with generators of degrees $(1,\dots,k)$.

  2. (2)

Case 2: $\mathcal{B}$ has infinitely many finite blocks, as in Example 2.13
(3). Then, $G$ is a subgroup of $G_{|B}\wr\mathfrak{S}_{\infty}$, and
$\mathbb{Q}\mathcal{A}(G)$ contains the free algebra with generators of
degrees given by that of the non trivial orbits of $G_{|B}$.

Note that the first case can be refined by stating that the orbit algebra
contains the algebra of invariants of the finite group $H$ acting on the
blocks (which may be smaller than the full symmetric group
$\mathfrak{S}_{k}$); this algebra is typically not free.

… …

Case 1 Case 2

Figure 3. Essential cases for a _transitive_ block system of a
$P$-oligomorphic group

###### Sketch of proof.

The blocks share the same size by transitivity, and if their size (resp.
number) is infinite, then their number (resp. size) has to be finite in order
to keep the group $P$-oligomorphic (indeed, $G$ is otherwise a subgroup of
$\mathfrak{S}_{\infty}\wr\mathfrak{S}_{\infty}$ and its profile is bounded
below by the number of integer partitions). Use Lemma 2.4 and Examples 2.13 in
each case. ∎

Assume that $G$ is endowed with a block system. Then, the proof of the above
lemma applies in the same fashion to the restrictions of $G$ to (the support
of) its orbits of blocks, leading the whole $\mathbb{Q}\mathcal{A}(G)$ (with
just one more use of Lemma 2.4) to also contain the mentioned subalgebras (in
the case with finitely many finite blocks, refer instead to the first item of
Example 2.3). Recall also that in Case 2, we have the convenient property of
Lemma 2.12.

######  Remark 3.2.

Let $G$ be an oligomorphic permutation group, and $E_{1},\ldots,E_{k}$ be a
partition of $E$ such that each $E_{i}$ is stable under $G$. In our use case,
we have a block system $\mathcal{B}$, and each $E_{i}$ is the support of one
of the orbits of blocks in $\mathcal{B}$.

Then, $G$ is a subgroup of ${G}_{|E_{1}}\times\cdots\times{G}_{|E_{k}}$
(precisely, it is a _subdirect product_ of this direct product). Therefore, by
Lemma 2.4, $\mathbb{Q}\mathcal{A}(G)$ contains
$\mathbb{Q}\mathcal{A}({G}_{|E_{1}})\otimes\cdots\otimes\mathbb{Q}\mathcal{A}({G}_{|E_{k}})$
as a subalgebra. In particular, the algebraic dimension of
$\mathbb{Q}\mathcal{A}(G)$ is bounded below by the sum of the algebraic
dimensions of the $\mathbb{Q}\mathcal{A}({G}_{|E_{i}})$.

When, in addition, the actions of $G$ on each $E_{i}$ are completely
independent, the containments above are equalities; then,
$\mathbb{Q}\mathcal{A}(G)$ is finitely generated if and only if each
$\mathbb{Q}\mathcal{A}({G}_{|E_{i}})$ is.

######  Remark 3.3.

Combining Lemma 3.1 and Remark 3.2, each block system of $G$ provides a lower
bound on the algebraic dimension of $\mathbb{Q}\mathcal{A}(G)$, and therefore
on the growth rate of the profile.

The following example illustrates that the lower bound on the profile highly
depends on the chosen block system.

######  Example 3.4.

Let $G=(\mathfrak{S}_{2}\times\mathfrak{S}_{2})\wr\mathfrak{S}_{\infty}$.
Following is the poset of all its block systems, ordered by refinement:

The picture below displays the lower bounds on the algebraic dimension that
can be deduced respectively from each of these block systems, using Lemma 3.1
and Remark 3.2:

${1}$${{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}7}}$${2}$${4}$${1}$

For instance, for the block system with two orbits of blocks of size $2$, the
lower bound on the algebraic dimension is $4=2+2$ since we have
$G_{|B}=\mathfrak{S}_{2}$ in each orbit; for the block system with finite
blocks of size $4$, the lower bound is $7$, for
$G_{|B}=\mathfrak{S}_{2}\times\mathfrak{S}_{2}$ has this many orbits of non
empty subsets. This latter lower bound is obviously tight since the inclusion
$G_{|B}\wr\mathfrak{S}_{\infty}\subset G$ is an equality: the algebraic
dimension of $\mathbb{Q}\mathcal{A}(G)$ is $7$ and the growth rate of the
profile of $G$ is $6$.

This example suggests that better lower bounds are obtained when maximizing
the size of the finite blocks (and then maximizing the number of infinite
blocks; consider also the example
$\mathfrak{S}_{\infty}\wr\operatorname{Id}_{n}$ for that).

Nevertheless, the bound provided by this heuristic alone can be improved at
rather low cost, as advertised by the following example.

######  Example 3.5 (Towards blocks of blocks).

Consider the permutation group
$G=\mathcal{C}_{4}\wr(\mathfrak{S}_{\infty}\wr\mathcal{C}_{3})$; we use here
the parentheses regardless of the associativity to emphasize the action of $G$
on its natural system of infinitely many (maximal) blocks of size $4$.

By Remark 3.3, this block system provides a lower bound of $4$ on the
algebraic dimension. As we will see, it is very crude; a lot of information
was lost when embedding the action on the blocks
$\mathfrak{S}_{\infty}\wr\mathcal{C}_{3}$ into $\mathfrak{S}_{\infty}$. This
action was not even primitive to begin with: one can form $3$ infinite blocks
(of $4$-blocks). Let us exploit that information. Consider the stabilizer $S$
of the three infinite blocks of finite blocks. This is a normal subgroup of
finite index of $G$, and therefore it has the same algebraic dimension using
Lemma 2.6. But now that these infinite blocks of blocks are stable parts of
the domain, their contributions to the algebraic dimension can be treated
separately; which hands a bound of $3*4=12$ for $S$, and thus for $G$.

Let us step toward a generalization and a formalization of the phenomenon
observed in the above example.

Let $G$ be a $P$-oligomorphic permutation group. Take a block system
$\mathcal{B}^{<\infty}$ of finite blocks only. Assume further that these
finite blocks are maximal: $G$ does not have any strictly coarser system of
finite blocks. This choice is motivated by the earlier observations (see
Example 3.4); we will see in Subsection 3.2 that $\mathcal{B}^{<\infty}$
always exists and is unique.

If $G$ has some finite orbits of elements, their union forms a stable finite
block which contains all other stable finite blocks (a stable block is a union
of orbits, that are obviously finite if the block is).

By definition of a block system, $G$ acts on the set of blocks of
$\mathcal{B}^{<\infty}$. Furthermore, this induced action does not admit any
non trivial finite block, for else the blocks of $\mathcal{B}^{<\infty}$ would
not be maximal. It has no special reason to be primitive though: its block
systems will just have infinite blocks only (plus possibly one singleton, if
$\mathcal{B}^{<\infty}$ has a stable block) – and finitely many of them, for
the same reasons as in Lemma 3.1. By choosing one such system, we end up with
two nested block systems: an inner one with finite blocks, and an outer one
with (finitely many) infinite blocks; in other words, _a finite system of
infinite blocks of finite blocks_.

######  Remark 3.6.

A lower bound can be obtained from such a double, nested block system by first
stabilizing the infinite blocks of finite blocks (which does not change the
growth of the group, as stated by Lemma 2.6), and then applying the same
method as in Remark 3.3. For the same choice of (maximal) finite blocks, the
lower bound $L$ provided by this method is better than the one deduced from
the matching simple block system _via_ Remark 3.3.

This is pretty much obvious if you consider the typical case highlighted in
Example 3.5.

As for the choice of the infinite blocks of blocks, the general intuition
remains the same as with classical, simple block systems: we feel that the
more the better, as far as the lower bound is concerned.

The next subsection formalizes these intuitions to construct a canonical block
system (in fact a system of blocks of blocks) that will hopefully maximize the
lower bound.

###  3.2. Optimizing the lower bound through lattice structures

As suggested by the previous subsection, maximizing the lower bound will
involve maximizing or minimizing block systems with certain properties. To
this end, we will exploit the lattice structure of the poset of block systems,
which we recall now.

######  Proposition 3.7.

Let $G$ be a permutation group $G$ acting on a set $E$, finite or infinite.
The poset $\mathcal{L}(G)$ of all its block systems, endowed with the
refinement order, is a sublattice of the lattice of set partitions of $E$. Its
maximum and minimum are respectively the trivial block systems $\top=\\{E\\}$
and $\bot=\\{\\{e\\}\mid e\in E\\}$.

###### Proof.

Take two block systems $\mathcal{B}$ and $\mathcal{B}^{\prime}$, and consider
their meet in the lattice of set partitions, namely the set partition:

$\mathcal{B}\wedge\mathcal{B}^{\prime}=\\{B\cap B^{\prime}\mid
B\in\mathcal{B}\text{ and }B^{\prime}\in\mathcal{B}^{\prime}\\}\,.$

It is straightforward to check that this is still a block system for the
group. Hence this is the meet of $\mathcal{B}$ and $\mathcal{B}^{\prime}$ in
$\mathcal{L}(G)$.

Similarly, consider the join $\mathcal{B}\vee\mathcal{B}^{\prime}$ in the
lattice of set partitions. It is obtained by taking the equivalence classes of
the closure of the relation “being in the same block in $\mathcal{B}$ or in
$\mathcal{B}^{\prime}$”. There remains to check that
$\mathcal{B}\vee\mathcal{B}^{\prime}$ is a block system: if $x$ and $y$ are in
the same part and $\sigma$ is an element of $G$, then $\sigma(x)$ and
$\sigma(y)$ are in the same part as well. To this end, consider a sequence
$x_{0},\ldots,x_{k}$ such that we have $x_{0}=x$, $x_{k}=y$ and any two
consecutive elements in the same block for either $\mathcal{B}$ or
$\mathcal{B}^{\prime}$; then the same holds for the sequence
$\sigma(x_{0}),\ldots,\sigma(x_{k})$.

In conclusion, $\mathcal{L}(G)$ is stable under both join and meet operations,
and therefore a sublattice of the lattice of set partitions of $E$. ∎

In the sequel, we will consider block systems with only finite blocks (resp.
only infinite blocks, up to kernel); the following propositions state that
those block systems form finite sublattices. This will provide us with a
canonical maximal (resp. minimal) block system from which we will derive
bounds.

######  Proposition 3.8.

Let $G$ be an oligomorphic permutation group, and $\mathcal{L}^{<\infty}(G)$
be the subposet of block systems consisting of finite blocks only. Then,
$\mathcal{L}^{<\infty}(G)$ is a sublattice of $\mathcal{L}(G)$, with the
trivial block system as minimum. If, in addition, $G$ is $P$-oligomorphic,
then $\mathcal{L}^{<\infty}(G)$ is finite, with a maximum
$\mathcal{B}^{<\infty}$.

######  Proposition 3.9.

Let $G$ be a $P$-oligomorphic permutation group, and $\mathcal{L}^{\infty}(G)$
be the subposet of block systems consisting of infinite blocks only; if the
kernel of $G$ is non trivial, then finite blocks contained in the kernel are
allowed as well. Then, $\mathcal{L}^{\infty}(G)$ is a finite sublattice of
$\mathcal{L}(G)$, with a minimum and the trivial block system as maximum.

Proving Propositions 3.8 and 3.9 will require a couple of lemmas.

######  Lemma 3.10.

Let $G$ be a $P$-oligomorphic group, and $L$ be the function that maps a block
system onto the associated lower bound described in the previous subsection
(Remark 3.3). Let $\mathcal{B}<\mathcal{B}^{\prime}$ be a cover (not involving
the kernel) in the lattice $\mathcal{L}^{<\infty}(G)$, then we have
$L(\mathcal{B})<L(\mathcal{B}^{\prime})$.

If instead $\mathcal{B}<\mathcal{B}^{\prime}$ is a cover (not involving the
kernel) in the lattice $\mathcal{L}^{\infty}(G)$, we have
$L(\mathcal{B})>L(\mathcal{B}^{\prime})$.

###### Proof.

Assume that $\mathcal{B}<\mathcal{B}^{\prime}$ is a cover in
$\mathcal{L}^{<\infty}(G)$. Pick one of the finite blocks $B$ in
$\mathcal{B}^{\prime}$ that splits into two new blocks $B_{1}$ and $B_{2}$ in
$\mathcal{B}$; by conjugation, the same can be said about all the other blocks
in the orbit of $B$. There are two cases: either $B_{1}$ and $B_{2}$ may swap
or they may not.

If not, then the support $O_{B}$ of the orbit of $B$ is the union of the
supports $O_{1}$ and $O_{2}$ of the orbits of $B_{1}$ and $B_{2}$ (resp.), and
the age of $G_{|O_{B}}$ contains the (disjoint) ages of the restrictions
$G_{1}$ and $G_{2}$ to $O_{1}$ and $O_{2}$ (resp.). It also contains the
additional orbits of subsets that have non empty intersections with both
$B_{1}$ and $B_{2}$, so the inclusion is strict. Using Lemma 3.1, the provided
bound on the profile is strictly better with the coarser system (since we took
a cover, the situation in $\mathcal{B}$ and $\mathcal{B}^{\prime}$ is the same
everywhere else).

If $B_{1}$ and $B_{2}$ do swap, then we get a single orbit of (small) blocks
in $\mathcal{B}$, just as in $\mathcal{B}^{\prime}$; except that if one
denotes by $H$ the restriction of $G$ to one of the small blocks in
$\mathcal{B}$, the restriction to one block of $\mathcal{B}^{\prime}$ is
$H\wr\mathfrak{S}_{2}$, which has a strictly larger age. Hence,
$\mathcal{B}^{\prime}$ provides a better bound.

As for $\mathcal{L}^{\infty}(G)$, the result is rather obvious from Lemma 3.1.
∎

######  Lemma 3.11.

Let $G$ be an oligomorphic permutation group. The poset
$\mathcal{L}^{<\infty}(G)$ is closed under taking joins (as defined in the
lattice of set partitions).

The following simple example illustrates that this statement may fail without
the oligomorphic condition.

######  Example 3.12.

Recall that the (non oligomorphic) permutation group $\text{Aut}(\mathbb{Z})$
is generated by the translation $x\mapsto x+1$, and take
$G=\text{Aut}(\mathbb{Z})\times\text{Aut}(\mathbb{Z})$, acting on two copies
of $\mathbb{Z}$: $E=\\{1,2\\}\times\mathbb{Z}$. This group admits an infinite
family of block systems $(\mathcal{B}_{j})_{j\in\mathbb{Z}}$ with non trivial
finite blocks of size $2$:

$\mathcal{B}_{j}:=\\{\\{(1,i),(2,i+j)\\}\mid i\in\mathbb{Z}\\}\,.$

The following picture illustrates the block systems $\mathcal{B}_{0}$ and
$\mathcal{B}_{1}$; their join is the trivial block system with a single
infinite block.

$\cdots$$\mathcal{B}_{0}$ and $\mathcal{B}_{1}$

In general, the join of two of block systems $\mathcal{B}_{i}$ and
$\mathcal{B}_{j}$ with $i\neq j$ is composed of infinite blocks.

###### Proof of Lemma 3.11.

Assume that the join of two systems of finite blocks $\mathcal{B}$ and
$\mathcal{B}^{\prime}$ from $\mathcal{L}^{<\infty}(G)$ contains at least one
infinite block. This block is thus a union of infinitely many blocks from both
$\mathcal{B}$ and $\mathcal{B}^{\prime}$, in which every block from one system
intersects at least one block from the other one. If all of the blocks of
$\mathcal{B}$ involved were singletons, each of them would be included in one
block from $\mathcal{B}^{\prime}$ and so the join would not have an infinite
block; hence at least one of them, call it $B_{0}$, is not.

Consider the stabilizer $S_{0}$ of this $B_{0}$ (in red in the center of
Figure 4). In this subgroup, the union of the blocks from
$\mathcal{B}^{\prime}$ having a non empty intersection with $B_{0}$ (in blue)
is also stable, so as well is their set difference with $B_{0}$. One can
iterate the argument with the union of blocks from $\mathcal{B}$ intersecting
this stable domain (the outer crown of red blocks), and so on.

Figure 4. Nested stable areas arising when stabilizing one block of
$\mathcal{B}$

This reveals an infinite sequence of finite disjoint (by taking the set
difference every time) domains that are stable under the action of $S_{0}$,
and of which the first item is $B_{0}$. Take now two distinct subsets $A_{1}$
and $A_{2}$ of $E$, each of them consisting of two elements in $B_{0}$ and
just one in any of the other $S_{0}$-stable domains. An element of $G$ mapping
$A_{1}$ to $A_{2}$, if there is any, necessarily belongs to $S_{0}$, since the
pair included in $B_{0}$ has no other choice but to be mapped onto the
corresponding pair of $A_{2}$. Therefore, changing the $S_{0}$-stable domain
in which we take the singleton for $A_{2}$ (or $A_{1}$) exhibit infinitely
many non isomorphic subsets of size $3$ for $G$, which is to say infinitely
many orbits of degree $3$, and makes $G$ a non oligomorphic group. ∎

###### Proof of Proposition 3.8.

Thanks to Lemma 3.11, we already know that $\mathcal{L}^{<\infty}(G)$ is table
under taking the join. We will successively prove that
$\mathcal{L}^{<\infty}(G)$ is stable under meets, locally finite, and that it
admits no infinitely increasing chain. We will then conclude that it is
bounded and finite.

Take two block systems $\mathcal{B}$ and $\mathcal{B}^{\prime}$ in
$\mathcal{L}^{<\infty}(G)$. Consider their meet in the lattice of block
systems:

$\mathcal{B}\wedge\mathcal{B}^{\prime}=\\{B\cap B^{\prime}\neq\varnothing\mid
B\in\mathcal{B}\text{ and }B^{\prime}\in\mathcal{B}^{\prime}\\}\,.$

By construction, it has again finite blocks, which proves that
$\mathcal{L}^{<\infty}(G)$ is stable under taking either joins or meets. In
addition to this, the trivial block system $\bot=\\{\\{e\\}\mid e\in E\\}$ is
obviously its minimal element.

Let $\mathcal{B}$ be an element of $\mathcal{L}^{<\infty}(G)$. Consider the
interval $[\bot,\mathcal{B}]$, and take a block system $\mathcal{B}^{\prime}$
in that interval. The way a block $B$ in $\mathcal{B}$ splits into blocks in
$\mathcal{B}^{\prime}$ forces the way the blocks in the same orbit split in
$\mathcal{B}^{\prime}$ themselves. Since the blocks of $B$ are finite, and and
there are finitely many orbits thereof for $G$ is oligomorphic, there are
finitely many ways of splitting them. Therefore the interval
$[\bot,\mathcal{B}]$ is finite, and the same holds for any interval:
$\mathcal{L}^{<\infty}(G)$ is locally finite.

Take a strict chain $C$ in $\mathcal{L}^{<\infty}(G)$. Using the local
finiteness, embed this chain in a strict chain $C^{\prime}$ where each step is
a cover. Thanks to Lemma 3.10, $L$ is strictly increasing along that chain.
Since $G$ is $P$-oligomorphic, $L$ is also bounded, and it follows
successively that $C^{\prime}$ and $C$ are finite.

This ensures the existence of a maximum $\mathcal{B}^{<\infty}$, for else we
could construct an infinite chain by starting with an element and then
recursively take the join with an incomparable element. We conclude by
remarking that $\mathcal{L}^{<\infty}(G)=[\bot,\mathcal{B}^{<\infty}]$ is
finite. ∎

###### Proof of Proposition 3.9.

The poset $\mathcal{L}^{\infty}(G)$ obviously has $\top=\\{E\\}$ as maximal
element, and it is stable under joins: take indeed two block systems
$\mathcal{B}$ and $\mathcal{B}^{\prime}$ in $\mathcal{L}^{<\infty}(G)$: their
blocks are infinite or included in the kernel. It is straightforward to check
that the blocks of their join satisfy the same property.

Let us prove that $\mathcal{L}^{\infty}(G)$ is stable under meet. Consider the
meet of two block systems in $\mathcal{L}^{\infty}(G)$:

$\mathcal{B}\wedge\mathcal{B}^{\prime}=\\{B\cap B^{\prime}\mid
B\in\mathcal{B}\text{ and }B^{\prime}\in\mathcal{B}^{\prime}\\}\,.$

It has finitely many blocks. The union of all the finite ones is finite and
stable under $G$; it is therefore included in the kernel of $G$. It follows
that the blocks of $\mathcal{B}\wedge\mathcal{B}^{\prime}$ are either infinite
or included in the kernel of $G$, as desired.

Consider an interval $[\mathcal{B},\top]$ in $\mathcal{L}^{\infty}(G)$. Every
block system $\mathcal{B}^{\prime}$ from the interval is obtained by merging
together some of the finitely many blocks of $\mathcal{B}$. Hence this
interval is finite, and $\mathcal{L}^{\infty}(G)$ is locally finite.

We conclude as in the proof of Proposition 3.8: there are no infinite chains
in $\mathcal{L}^{\infty}(G)$ (a bit of care needs to be taken since
$L(\mathcal{B})$ may not be strictly increasing at steps where two finite
blocks are merged; but there can be only finitely many such steps). This in
turn ensures the existence of a minimal element $\mathcal{B}^{\infty}$ and the
finiteness of $\mathcal{L}^{\infty}(G)$.

∎

###  3.3. The nested block system

We may now use the structure of finite lattice on the block systems of a
$P$-oligomorphic group to select a block system of a special kind (actually a
system of blocks of blocks), which we expect to maximize the associated lower
bound, and thus to provide a best fitted set-up for the study of the group.

######  Definition 3.13.

Let $G$ be a $P$-oligomorphic permutation group. Take:

  1. (1)

the maximal (coarsest) element $\mathcal{B}^{<\infty}$ of
$\mathcal{L}^{<\infty}(G)$

  2. (2)

the minimal (finest) element $\mathcal{B}^{\infty}$ of the lattice of block
systems for the induced action of $G$ on $\mathcal{B}^{<\infty}$.

We call the pair formed by the nested two partitions of $E$ defined this way
the nested block system $\mathcal{B}_{\mathcal{B}}(G)$ of $G$.

######  Definition 3.14.

We call an infinite primitive block of maximal finite blocks a superblock.

Note that, under the preliminary assumption of maximality, the primitivity
requirement is equivalent to asking that the infinite block be minimal, so the
above results on lattice structures imply that there is no “choice” for such
superblocks– as opposed to the many choices of blocks, for the classical
notion. From this point of view, the following (straightforward from the
construction process of the nested block system) proposition offers an
alternative definition of the superblocks, as the blocks of blocks in
$\mathcal{B}_{\mathcal{B}}(G)$.

######  Proposition 3.15 (Structure of the nested system).

The nested block system consists of finitely many superblocks, and maybe one
stable finite block.

Besides providing a competitive lower bound on the profile growth, the nested
block system can pride itself on some pleasant properties of manageability.

######  Lemma 3.16.

Take two stable superblocks; the actions induced by $G$ on their sets of
maximal finite blocks are independent (up to taking a normal subgroup of
finite index).

###### Proof.

By definition, the actions on the finite blocks of each superblock are
isomorphic to one of the five highly homogeneous groups. Recall then Remark
2.19, and if need be take the finite index subgroup in which the actions of
type $\text{Rev}(\mathbb{Q})$ and $\text{Rev}(\mathbb{Q}/\mathbb{Z})$ are
replaced by $\text{Aut}(\mathbb{Q})$ and $\text{Aut}(\mathbb{Q}/\mathbb{Z})$
to avoid synchronizations of order $2$. Now the maximality of the finite
blocks allows to eliminate the case of total synchronizations, which leaves
none possible. ∎

Put otherwise, superblocks in $\mathcal{B}_{\mathcal{B}}(G)$ are not that far
from independence, which would allow to use Remark 3.2. This paper will
eventually clarify what “not that far” actually means.

######  Lemma 3.17.

Let $G$ be a $P$-oligomorphic permutation group, and $K$ be a finite index
subgroup of $G$. Then we have
$\mathcal{B}_{\mathcal{B}}(K)=\mathcal{B}_{\mathcal{B}}(G)$.

###### Proof.

We aim to prove that $K$ has the same superblocks as $G$. Observe first that
blocks of imprimitivity of any permutation group are still blocks for any
subgroup, as a direct consequence of the definition. Let $BB$ be a superblock,
and $\mathfrak{M}$ be the action of $G$ (implicitely after stabilization and
restriction to the support of $BB$) on the set of finite blocks of $BB$. Then,
$\mathfrak{M}$ is one of the five highly homogeneous groups; as the action of
$K$ on the same set of finite blocks is necessarily a finite index subgroup of
$\mathfrak{M}$, it is highly homogeneous as well. We now just need to justify
that the maximal finite blocks of $G$ are still maximal for $K$. Assume some
of them are not, then there exists $m\geq 2$ superblocks $(BB^{(j)})_{1\leq
j\leq m}$ in $\mathcal{B}_{\mathcal{B}}(G)$ and an ordering of their
respective finite blocks $(B^{(j)}_{i})_{i}$ such that the unions
$\cup_{j}B^{(j)}_{i}$ form new blocks for $K$ (up to taking the join in
$\mathcal{L}^{<\infty}(K)$). This can only happen if some of the actions of
$K$ on distinct $(B^{(j)}_{i})_{i}$ fully synchronize for $1\leq j\leq m$.
Since they are infinite (highly homogeneous) actions, this is in contradiction
with $K$’s being of finite index. (Indeed, the action of $K$ on the blocks
would be of infinite index in that of $G$, which is not possible.) ∎

The reader has probably already wondered at this point why to stop here. We
already have blocks of blocks, why not blocks of blocks of blocks, etc.? The
blocks of blocks of the nested block system allow a good description of wreath
products of type $F_{1}\wr P\wr F_{2}$, where $F_{1}$ and $F_{2}$ are two
finite groups that may be trivial and $P$ is an infinite permutation group
(recall Example 3.5). But what if we add a layer of wreath product: $F_{1}\wr
P\wr F_{2}\wr G$ ? Well, it simply turns out that if $G$ is not finite then
the group is not $P$-oligomorphic anymore; and if it is, we are actually back
to the same configuration as earlier (by associativity). Of course, if we had
not made any hypothesis on the growth of the profile, it would be relevant to
consider any number of layers of blocks.

##  4\. Classification in the case of a single superblock

In this section, we consider the class of closed $P$-oligomorphic permutation
groups $G$ with a single superblock, of which we denote by
$B_{1},B_{2},\ldots$ the maximal finite blocks. This class includes wreath
products $G=H\wr\mathfrak{S}_{\infty}$ where $H$ is finite. In Subsection 4.1
we construct other examples by direct products; then, by combining wreath
products and direct products, we introduce a family of permutation groups that
subsumes all these examples. We show that their orbit algebras are invariant
rings of permutation groups, hence finitely generated and Cohen-Macaulay.

In Subsection 4.2 we announce a classification theorem: any instance of this
class is isomorphic to exactly one permutation group in the family. This
answers positively Macpherson’s question for this class of permutation groups.

The next subsections undertake the proof of the classification theorem:
Subsection 4.3 handles the action on the set of blocks; Subsection 4.4
introduces the tower of $G$ in order to deal with the action within the
blocks, an object that will be the key tool in the rest of the proof, and that
turns out to be classified; finally, Subsection 4.5 shows that this
classification can be lifted to the groups themselves.

###  4.1. A family of examples beyond wreath products

######  Definition 4.1.

We call direct product on blocks of two permutation groups $H$ and $S$ and
denote by $H\mathbin{\square}S$ the permutation group defined by the action of
$H\times S$ on $\text{deg}(S)$ blocks of size $\text{deg}(H)$ by

$b_{r,i}.(\tau,\sigma)=b_{\tau(r),\sigma(i)}\,,$

where $b_{1,i},\ldots b_{m,i}$ is an arbitrary ordering of the elements of
each block $B_{i}$. It is isomorphic to the natural action of $H\times S$ on
the cartesian product of the supports.

This can be pictured as $H$ and $S$ acting respectively by permutation of the
rows and of the columns of a (potentially infinite) matrix.

As opposed to the wreath product, where $H$ acts independently on each block,
here $H$ acts diagonally on all blocks at once. These two cases are in this
regard the two opposite ends of the spectrum of all possible synchronizations
between blocks.

It is then natural to think of a class of groups that would complete the
spectrum. We introduce such groups, as hybrids of wreath products and direct
products.

######  Definition 4.2.

Let $H\triangleleft H_{0}$ and $\mathfrak{M}$ be three permutation groups,
with $H$ and $H_{0}$ finite. Denote by $[H_{0},H^{\infty},\mathfrak{M}]$ the
permutation group generated by the elements of $H\wr\mathfrak{M}$ and
$H_{0}\mathbin{\square}\mathfrak{M}$. For short, denote by
$[H_{0},H^{\infty}]=[H_{0},H^{\infty},\mathfrak{S}_{\infty}]$.

######  Remark 4.3.

The group $[H_{0},H^{\infty},\mathfrak{M}]$ is $P$-oligomorphic if and only if
we have $\mathfrak{M}=\mathfrak{S}_{\infty}$ or
$H_{0}=H=\operatorname{Id}_{1}$: indeed,
$[H_{0},H^{\infty},\mathfrak{S}_{\infty}]$ contains
$H\wr\mathfrak{S}_{\infty}$ as a subgroup; it is therefore $P$-oligomorphic;
the other implications are trivial using Lemma 2.12.

######  Lemma 4.4.

The permutation group $G=[H_{0},H^{\infty},\mathfrak{M}]$ contains
$H\wr\mathfrak{M}$ as a normal subgroup of finite index $[H:H_{0}]$. In
addition, we have $G=(H\wr\mathfrak{M})H_{0}$.

###### Proof.

First note that $G$ can be defined equivalently as the group generated by
$H\wr\operatorname{Id}_{\infty}=\,<H^{\infty}$,
$\operatorname{Id}\wr\mathfrak{M}>$, and the finite group
$H_{0}\mathbin{\square}\operatorname{Id}_{\infty}$. For the sake of notations,
and when there is no ambiguity, we identify an element $h_{0}$ of $H_{0}$ with
the element $(h_{0},h_{0},\ldots)$ of
$H_{0}\mathbin{\square}\operatorname{Id}_{\infty}$, and identify $H_{0}$ with
$H_{0}\mathbin{\square}\operatorname{Id}_{\infty}$.

Note that $h_{0}$ commutes with the elements of
$\operatorname{Id}\wr\mathfrak{M}$ and, by normality of $H$ in $H_{0}$, skew-
commutes with those of $H\wr\operatorname{Id}_{\infty}$ , meaning
$H^{\infty}h_{0}=h_{0}H^{\infty}$. It follows that we have

$G=\bigcup_{h_{0}\in H_{0}}(H\wr\mathfrak{M}).h_{0}\,.$

This union becomes a decomposition into cosets if the range is restricted to
some collection of representatives of the cosets of $H$ in $H_{0}$. Therefore
$H\wr\mathfrak{M}$ is normal and of finite index $[H:H_{0}]$ in $G$, as
desired. ∎

We now describe the orbit algebra of $[H_{0},H^{\infty},\mathfrak{M}]$ as an
invariant ring of a finite permutation group. Recall that the orbit algebra
$\mathbb{Q}\mathcal{A}(H\wr\mathfrak{M})$ of $H\wr\mathfrak{M}$ is the free
commutative algebra $\mathbb{Q}[X]$, with
$X=(X_{\overline{A}})_{\overline{A}}$ where $\overline{A}$ ranges through the
non-trivial $H$-orbits, and $X_{\overline{A}}$ denotes the $H\wr\mathfrak{M}$
-orbit of $A$, seen as an element of the orbit algebra. Finally, lift the
action of $H_{0}$ on the $H$-orbits $\overline{A}$ to an action on the
variables $X_{\overline{A}}$.

######  Proposition 4.5.

With the above notations, the orbit algebra $\mathbb{Q}\mathcal{A}(G)$ of
$G=[H_{0},H^{\infty},\mathfrak{M}]$ is isomorphic to the invariant ring
$\mathbb{Q}[X]^{H_{0}}$.

###### Proof.

That an element $h_{0}\in H_{0}$ and $A$ a subset of the support of $H$. Check
that the $H\wr\mathfrak{M}$-orbit of $A$ is mapped onto another such
$H\wr\mathfrak{M}$-orbit, as prescribed by the announced action of $H_{0}$ on
the variables $X_{\overline{A}}$. ∎

######  Remark 4.6.

The variables of invariant rings are commonly taken of degree $1$; this is not
the case here: the degree of the variable $X_{\overline{A}}$ is given by
$|A|$. This must be taken into account when computing the Hilbert series using
Molien’s formula or Pólyà enumeration.

###  4.2. Classification and application to Macpherson’s conjecture

We may now state the main theorem of this section, which includes the
classification of the trivial case of highly homogeneous groups $\mathfrak{M}$
(case $H_{0}=H=\operatorname{Id}_{1}$ below); nevertheless, the core of this
section is about the case of non trivial finite blocks, in which
$\mathfrak{M}$ is necessarily $\mathfrak{S}_{\infty}$.

######  Theorem 4.7 (Classification on one superblock).

Let $G$ be a closed $P$-oligomorphic permutation group such that
$\mathcal{B}_{\mathcal{B}}(G)$ consists of a single superblock. Then $G$ is
isomorphic as a permutation group to $[H_{0},H^{\infty},\mathfrak{M}]$, where
$H\triangleleft H_{0}$ are two finite permutation groups and $\mathfrak{M}$ is
one of the five (closed) highly homogeneous groups. In addition, $H$, $H_{0}$,
and $\mathfrak{M}$ are unique, and satisfy the condition of Remark 4.3.

###### Proof.

The statement is obvious if the finite blocks are singletons. Otherwise, by
Lemma 2.12, $G$ acts on the set of finite blocks as
$\mathfrak{M}=\mathfrak{S}_{\infty}$. Use the upcoming Proposition 4.16 to
classify the action of $G$ on its blocks (the _tower of $G$_) and the upcoming
Proposition 4.19 to lift this classification to $G$ itself. ∎

A positive answer to Macpherson’s question follows immediately thanks to the
description of the orbit algebras of the groups
$[H_{0},H^{\infty},\mathfrak{M}]$ from Proposition 4.5.

######  Corollary 4.8 (Macpherson on one superblock).

Let $G$ be a closed $P$-oligomorphic permutation group such that
$\mathcal{B}_{\mathcal{B}}(G)$ consists of a single superblock. Then,
$\mathbb{Q}\mathcal{A}(G)$ is an invariant ring of permutation group, hence
finitely generated, Cohen-Macaulay, and of algebraic dimension the number of
$H$-orbits (of non trivial subsets), where $H$ is defined by the
classification.

######  Remark 4.9.

Until now, the lower bound provided by the nested block system evoked in
Remark 3.6 was calculated using Example 2.13 when it came to stable
superblocks in $\mathcal{B}_{\mathcal{B}}(G)$. With the notations of this
section, it was based on the (possibly infinite index) supergroup
$H_{0}\wr\mathfrak{M}$: namely, the provided lower bound for the algebraic
dimension was the cardinality of the age of $H_{0}$. Corollary 4.8 hands a
refinement of this bound, that is based on the subgroup $H\wr\mathfrak{M}$ and
tight on the relevant restriction of the group.

In Section 5 the strategy to tackle a group $G$ with several superblocks will
be to consider the restrictions of $G$ on each of its superblocks, and patch
together their properties. This will use the following technical corollary.

######  Corollary 4.10.

Let $G$ be a closed $P$-oligomorphic permutation group such that
$\mathcal{B}_{\mathcal{B}}(G)$ consists of a single superblock; write it as
$G=[H_{0},H^{\infty},\mathfrak{M}]$ using the classification of Theorem 4.7,
and let $M$ be the minimal finite index normal subgroup of $\mathfrak{M}$.
Then, any finite index normal subgroup $\tilde{G}$ of $G$ is of the form
$[\tilde{H_{0}},H^{\infty},\tilde{M}]$, with $H\leq\tilde{H_{0}}\leq H_{0}$
and $M\leq\tilde{M}\leq\mathfrak{M}$. In particular, $K=H\wr M$ is the minimal
finite index normal subgroup of $G$.

###### Proof.

Since $\tilde{G}$ is of finite index, its nested block system is still equal
to $\mathcal{B}_{\mathcal{B}}(G)$ by Lemma 3.17, and its action on the maximal
finite blocks is a normal subgroup of finite index of $\mathfrak{M}$. Using
the classification of Theorem 4.7, $\tilde{G}$ is of the form
$[\tilde{H_{0}},\tilde{H}^{\infty},\tilde{M}]$, with the expected group
inclusions: $\tilde{H_{0}}\triangleleft H_{0}$, $\tilde{H}\triangleleft H$,
and $\tilde{M}\triangleleft\mathfrak{M}$. Lemma 4.4 also states that it
contains $\tilde{H}\wr\tilde{M}$ as a finite index normal subgroup, while $G$
contains $H\wr\mathfrak{M}$ and thus $H\wr\tilde{M}$ as finite index normal
subgroups. Considering Lemma 2.15, we need to have $\tilde{H}=H$ for
$\tilde{G}$ to be of finite index in $G$. ∎

###  4.3. Action on the set of blocks

The sequel of Section 4 is devoted to the statement and proof of the two
propositions used in the proof of Theorem 4.7.

From now on, we assume that $G$ acts on the set of finite blocks as
$\mathfrak{M}=\mathfrak{S}_{\infty}$. The following two technical lemmas
strengthen this assumption by showing that, for an appropriate enumeration of
the elements within in each block, $G$ can permute the blocks while preserving
that enumeration.

######  Lemma 4.11.

Take any finite collection $(B_{i_{1}},\ldots,B_{i_{k}})$ of blocks; then
$\operatorname{Fix}_{G}(B_{i_{1}},\ldots,B_{i_{k}})$ acts on the remaining
blocks as $\mathfrak{S}_{\infty}$.

###### Proof.

Take $k$ in $\mathbb{N}$. As $\operatorname{Fix}_{G}(B_{1},\ldots,B_{k})$ is a
normal subgroup of finite index of
$\operatorname{Stab}_{G}(B_{1},\ldots,B_{k})$, it acts on the remaining blocks
as a subgroup of finite index of $\mathfrak{S}_{\infty}$, which may only be
$\mathfrak{S}_{\infty}$ itself. By conjugation of the blocks, the same holds
for any collection $(B_{i_{1}},\ldots,B_{i_{k}})$ of blocks. ∎

######  Lemma 4.12.

There exists an ordering $b_{1,i},\ldots b_{m,i}$ of the elements within each
block $B_{i}$ such that (the closure of) $G$ contains
$\operatorname{Id}_{m}\mathbin{\square}\mathfrak{S}_{\infty}=\operatorname{Id}_{m}\wr\mathfrak{S}_{\infty}$
as a permutation subgroup.

###### Proof.

Since $G$ acts by $\mathfrak{S}_{\infty}$ on the blocks, there exists for each
$i>1$ a permutation $\tau_{1,i}^{(0)}\in G$ that swaps $B_{1}$ and $B_{i}$ and
stabilizes all the other blocks. Take now $k\geq 0$; using Lemma 4.11 there
exists a permutation $\tau_{1,i}^{(k)}$ that not only swaps $B_{1}$ and
$B_{i}$, but also fixes all the (other) blocks in $B_{2},\ldots,B_{k}$.

Take an infinite sequence $\tau_{1,i}^{(0)},\ldots,\tau_{1,i}^{(k)},\ldots$ .
Noting that there are only finitely many possibilities for the restriction of
$\tau_{1,i}^{(k)}$ to $B_{1}\cup B_{i}$, we can extract a subsequence with
always the same restriction. Thus, using the property of closure, there exists
in $G$ a permutation $\tau_{1,i}$ which swaps $B_{1}$ and $B_{i}$ and fixes
all the other blocks. This permutation need not be of order 2 though.

Say that $\tau_{1,i}$ and $\tau_{1,j}$ are equivalent if their restrictions to
$B_{1}\cup B_{i}$ and $B_{1}\cup B_{j}$ coincide up to renaming the elements
of $B_{i}$ (or $B_{j}$).

Now consider the map $i\mapsto\tau_{1,i}$. It takes finitely many values, and
therefore there exists $i$ and $j$ such that $\tau_{1,i}$ and $\tau_{1,j}$ are
equivalent. Define
$\tau^{\prime}_{i,j}=\tau_{1,i}\tau_{1,j}^{-1}\tau_{1,i}\,$.

$B_{i}$$B_{1}$$B_{j}$$\tau_{1,i}$$\tau_{1,j}$

$\underrightarrow{~{}\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}{\tau_{1,i}}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\tau_{1,j}^{-1}}\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}{\tau_{1,i}}}$
$B_{j}$$B_{1}$$B_{i}$

Figure 5. Example: Straight swap of $B_{i}$ and $B_{j}$ (also permuting
$B_{1}$)

Now check that

  * •

$\tau^{\prime}_{i,j}$ swaps $B_{i}$ and $B_{j}$ “straightforwardly”: that is
its restriction to $B_{i}\cup B_{j}$ is of order 2 (see Figure 5);

  * •

$\tau^{\prime}_{i,j}$ stabilizes $B_{1}$;

  * •

$\tau^{\prime}_{i,j}$ fixes all the other blocks (pointwise).

We may then conjugate $\tau^{\prime}_{i,j}$ to stabilize some block $B_{k}$
instead of $B_{1}$, with $k$ as large as desired, and still swap
straightforwardly $B_{i}$ and $B_{j}$ while fixing the remaining blocks.

Therefore there exists in $G$, which we recall is assumed to be closed, a
permutation $\tau_{i,j}$ of order $2$ that swaps $B_{i}$ and $B_{j}$ and fixes
all the other blocks. By conjugation, we can find for each $n$ a similar
permutation $\tau_{n}$ swapping $B_{n}$ and $B_{n+1}$.

Choose an arbitrary ordering $b_{1,1},\ldots,b_{m,1}$ of $B_{1}$. Define the
ordering $b_{1,2},\ldots,b_{m,2}$ of $B_{2}$ so that $\tau_{1}$ is the trivial
swap, meaning that it swaps $b_{1,r}$ and $b_{2,r}$ for each $r$. Proceed
similarly to order the elements of $B_{3}$ so that $\tau_{2}$ is the trivial
swap, and so on (Figure 6 shows the stage $k-1$).

$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$B_{1}$$B_{2}$$B_{3}$$B_{k-1}$$B_{k}$$B_{k+1}$
Figure 6. Straight swaps between the first $k$ blocks

Conclusion: the $\tau_{n}$’s generate
$\operatorname{Id}_{m}\mathbin{\square}\mathfrak{S}_{\infty}$ as a permutation
subgroup of $G$, as desired. ∎

###  4.4. Towers and their classification

While the previous subsection dealt with the way the finite blocks could
permute, this subsection is going to focus on what can happen within the
blocks when they do not permute (the results obtained above state that the
actions on and within the blocks can be decorrelated anyway).

######  Definition 4.13.

Let $S_{\mathcal{B}}=S_{\mathcal{B}}^{G}=\operatorname{Stab}_{G}(\mathcal{B})$
be the kernel of the morphism that maps $G$ onto its induced action on the set
of blocks, and, for $i\geq 0$, set
$H_{i}=H_{i}^{G}=\operatorname{Fix}_{S_{\mathcal{B}}}(B_{1},\ldots,B_{i})_{|B_{i+1}}$.
We call the sequence $H_{0},H_{1},H_{2},\ldots$ the tower of $G$ with respect
to the block system $\mathcal{B}$. The groups $H_{i}$ are considered up to a
permutation group isomorphism.

######  Remark 4.14.

  * •

By conjugation, using Lemma 2.12, the tower does not depend on the ordering
$B_{1},B_{2},\dots$ of the blocks. In others words, $H_{i}$ can be obtained by
fixing (pointwise) any $i$ blocks and taking the restriction to any other
block.

  * •

Up to permutation group isomorphisms, the sequence $H_{0},H_{1},\dots$ forms a
weakly decreasing chain of subgroups of
$\operatorname{Sym}(\\{1,2,\ldots,m\\}$), where $m$ is the cardinality of the
blocks. Take indeed an arbitrary block $B^{\prime}_{0}$ and label its elements
by $\\{1,2,\ldots,m\\}$; then define each $H_{i}$ as
$\operatorname{Fix}_{S_{\mathcal{B}}}(B^{\prime}_{1},\ldots,B^{\prime}_{i})_{B^{\prime}_{0}}$
where $B^{\prime}_{1},\dots,B^{\prime}_{i}$ are $i$ arbitrary distinct blocks.
In addition, each $H_{i+1}$ is normal in $H_{i}$.

The above definition and remark also apply to a permutation group of a finite
set, as long as it acts on the (finitely many) blocks as the full symmetric
group.

######  Example 4.15 (Fundamental examples).

Let $H$ be a finite permutation group. The tower of
$H\wr\mathfrak{S}_{\infty}$ (resp. $H\mathbin{\square}\mathfrak{S}_{\infty}$)
for its natural block system is $H,H,H\cdots$ (resp.
$H,\operatorname{Id},\operatorname{Id}\cdots$). The tower of
$[H_{0},H^{\infty}]$ is $H_{0},H,H,H\cdots$ .

${H_{0}\wr\mathfrak{S}_{\infty}}$${\longleftrightarrow~{}~{}H_{0},~{}H_{0},~{}H_{0},~{}H_{0}~{}\cdots}$${\vdots}$${[H_{0},H^{\infty}]}$${\longleftrightarrow~{}~{}H_{0},~{}H_{{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}0}},~{}H_{{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}0}},~{}H_{{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}0}}~{}\cdots}$${H\wr\mathfrak{S}_{\infty}}$${\longleftrightarrow~{}~{}H_{{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}0}},~{}H_{{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}0}},~{}H_{{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}0}},~{}H_{{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}0}}~{}\cdots}$${\vdots}$${H\mathbin{\square}\mathfrak{S}_{\infty}}$${\longleftrightarrow~{}~{}H,~{}\operatorname{Id},~{}\operatorname{Id},~{}\operatorname{Id}~{}\cdots}$$\scriptstyle{<\infty}$

We aim to prove that these are the only possibilities for a tower (so there is
actually only one prototype of a tower, since the first two examples are a
specialization of the third one).

######  Proposition 4.16.

Let $G$ be a closed $P$-oligomorphic permutation group with
$\mathcal{B}_{\mathcal{B}}(G)$ consisting of a single superblock. Then, the
tower of $G$ has the form $H_{0},H,H,H\cdots$, where $H_{0}$ is a finite
permutation group and $H$ is a normal subgroup of $H_{0}$.

###### Proof.

Consider, for any $i\in\mathbb{N}$, the restriction $G_{i}$ of
$\text{Fix}_{G}(\cup_{j<i}B_{j})$ to the four next blocks. The tower of this
permutation group (for a natural extension of the notion to finite groups of
the adequate shape) is $H_{i},H_{i+1},H_{i+2},H_{i+3}$. We aim to show that
$H_{i+1}=H_{i+2}$, which will conclude the proof.

An element $s$ of the blockwise stabilizer $S_{i}$ of $G_{i}$ is determined by
its action on each block, which we write as a quadruple. Let $g$ be an element
of $H_{i+1}$. Then $S_{i}$ has an element $x$ that may be written $(1,g,h,l)$,
with $h$ and $l$ also in $H_{i+1}$. Let $\sigma$ be an element of $G_{i}$ that
permutes “straightforwardly” the first two blocks and fixes the other two
(Lemma 4.12 states that such an element actually exists). By conjugating $x$
with $\sigma$ in $G_{i}$, we get an element $y$ in $S_{i}$ that we may write
$(g,1,h,l)$, so that $x^{-1}y=(g,g^{-1},1,1)$. Hence, using Remark 4.14, $g$
is actually in $H_{i+2}$.

∎

###  4.5. Lifting of the classification from towers to groups

The two results to follow will show that $G$ is uniquely defined by its tower,
by first recovering the blockwise stabilizer of the group from the tower, and
then using the result of “straightforward” permutation we proved in Lemma
4.12.

######  Lemma 4.17.

The tower of $G$ w.r.t. $\mathcal{B}$ uniquely determines its blockwise
stabilizer $S_{\mathcal{B}}$.

###### Proof.

Let $(H_{i})_{i}$ be the tower of $G$ w.r.t. $\mathcal{B}$ and
$S_{\mathcal{B}}$ be the blockwise stabilizer of $\mathcal{B}$.

Using that $S$ is closed, it is sufficient to prove that, for any $l\geq 0$,
the restriction $S_{\ell}$ of $S$ to the first $\ell$ blocks is determined by
the tower; or equivalently to any $\ell$ blocks (recall that the order of the
blocks is irrelevant). To this end, we will show that $S_{\ell}$ admits an
expression that involves only explicit subdirect products and the $H_{i}$’s
(which will do the job thanks to Proposition 2.18).

$\cdots$$k$$\ell$$H_{k,\ell}$

In order to proceed by induction on $\ell$, we consider the larger family
$(H_{k,\ell})_{k\geq 0,\ell>0}$, where $H_{k,\ell}$ is the restriction on $l$
blocks of the fixator of $k$ other blocks in $S$. Of course,
$H_{0,\ell}=S_{\ell}$.

First, note that we have $H_{k,1}=H_{k}$ for all $k$. This gives the base case
for the induction. We now take $\ell>1$, and express $H_{k,\ell}$ as a
subdirect product involving only $H_{k^{\prime},\ell^{\prime}}$ with
$\ell^{\prime}<\ell$ (and incidentally also $k^{\prime}+\ell^{\prime}\leq
k+\ell$).

Write $l=\ell_{1}+\ell_{2}$ with $\ell_{1}>0$ and $\ell_{2}>0$, partition the
$\ell$ blocks into $\ell_{1}$ and $\ell_{2}$ blocks, and let $E_{1}$ and
$E_{2}$ be their respective union. Considering the action of $H_{k,\ell}$ on
$E_{1}$ and $E_{2}$ provides the desired expression:

$H_{k,\ell}=\operatorname{Subdirect}((G_{1},G_{2}),(N_{1},N_{2}))\,,$

where:

$\displaystyle G_{1}$ $\displaystyle={H_{k,\ell}}_{|E_{1}}$
$\displaystyle=H_{k,\ell_{1}}$ $\displaystyle G_{2}$
$\displaystyle={H_{k,\ell}}_{|E_{2}}$ $\displaystyle=H_{k,\ell_{2}}$
$\displaystyle N_{1}$
$\displaystyle=\operatorname{Fix}_{H_{k,\ell}}(E_{2})_{|E_{1}}$
$\displaystyle=H_{k+\ell_{1},\ell_{2}}$ $\displaystyle N_{2}$
$\displaystyle=\operatorname{Fix}_{H_{k,\ell}}(E_{1})_{|E_{2}}$
$\displaystyle=H_{k+\ell_{2},\ell_{1}}\qed$

######  Remark 4.18.

If desired, more explicit formulae can be obtained, by imposing the partition.
For instance, even splittings have the pleasant property that $G_{1}=G_{2}$
and $N_{1}=N_{2}$, which allows to illustrate the process by a binary tree:
following is for example a recursion tree to express $H_{0,8}$ as a subdirect
product of $H_{i}$’s, assuming that the left (resp. right) hand child of a
group is the $G_{i}$ (resp. $N_{i}$) of the subdirect product making this
group (so a group is determined by its two children). This recursion tree
generalizes immediately to any $H_{0,2^{n}}$, which is sufficient to retrieve
$S$ by closure.
$H_{0,8}$$H_{0,4}$$H_{0,2}$$H_{0,1}=H_{0}$$H_{1}$$H_{2,2}$$H_{2}$$H_{3}$$H_{4,4}$$H_{4,2}$$H_{4}$$H_{5}$$H_{6,2}$$H_{6}$$H_{7,1}=H_{7}$

######  Proposition 4.19.

The permutation group $G$ is the natural semidirect product of its blockwise
stabilizer $S_{\mathcal{B}}$ and
$L=\operatorname{Id}_{m}\mathbin{\square}\mathfrak{S}_{\infty}$. In
particular, it is uniquely defined by its tower w.r.t. $\mathcal{B}$.

###### Proof.

Use first Lemma 4.12 to state that $G$ contains
$L=\operatorname{Id}_{m}\mathbin{\square}\mathfrak{S}_{\infty}$ (for “ladder”)
as a permutation subgroup.

Take $k>0$, the stabilizer
$\operatorname{Stab}_{\tilde{G}}(B_{1},\ldots,B_{k})$ of the first $k$ blocks
is isomorphic to $\operatorname{Stab}_{G}(B_{1},\ldots,B_{k})$ by Lemma 4.17.

Now, the group generated by $L_{|B_{1}\cup\cdots\cup B_{k}}$ and
$\operatorname{Stab}_{G}(B_{1},\ldots,B_{k})_{|B_{1}\cup\cdots\cup B_{k}}$ is
a subgroup of the restriction of $G$ (actually of
$\operatorname{Stab}_{G}(B_{1}\cup\cdots\cup B_{k})$) to the same domain.
Moreover, the latter is of size
$|\mathfrak{S}_{k}|.|\operatorname{Stab}_{G}(B_{1},\ldots,B_{k})|$ (consider
the morphism that projects onto the action on the blocks); therefore the two
groups are equal.

Finally, since $G$ acts on the blocks as the symmetric group, which is the
closure of the group of all finitely supported permutations, each of its
elements is also the simple limit of a sequence of finitely supported
permutations. Since we just showed that the restrictions to any finite number
of blocks are uniquely defined by the tower, so is the whole (closed) group
$G$. ∎

This provides the final piece of the proof of the classification theorem in
the case of a single superblock, and we may now move on to the general case.

##  5\. Classification of (closed) $P$-oligomorphic groups

Let $G$ be a closed $P$-oligomorphic group. In Subsection 5.1 we exploit the
results from Subsection 3 on the blocks systems of $G$ and the classification
of closed $P$-oligomorphic groups with one single superblock of Section 4 to
give a constructive description of the minimal finite index subgroup $K$ of
$G$. This subgroup is the first piece of the classification of $G$.

In Subsection 5.2, we explicit $G$ as a semidirect product of $K$ and a finite
permutation group acting diagonally on its nested block system.

Finally, in Subsection 5.3, we classify (closed) $P$-oligomorphic groups,
using a finite data structure involving some finite group and a choice of
decorated block system for it. We first handle the case when $G$ does not act
as $\operatorname{Rev}(\mathbb{Q})$ or
$\operatorname{Rev}(\mathbb{Q}/\mathbb{Z})$ on any of its superblock, and then
show how to be inclusive.

###  5.1. The minimal finite index subgroup

……………⋮⋮

Following Definition 3.13, let $\mathcal{B}_{\mathcal{B}}(G)$ be the nested
block system of $G$; recall that it consists in a partition of the set of
maximal finite blocks (but the kernel of $G$) into finitely many superblocks
$(BB^{(j)})_{j}$. Let $\text{Stab}_{G}(\mathcal{B}_{\mathcal{B}}(G))$ be the
stabilizer of the superblocks; it is a finite index normal subgroup of $G$ and
therefore, by Lemma 3.17, has the same superblocks.

We now consider the restriction
$G^{(j)}={\text{Stab}_{G}(\mathcal{B}_{\mathcal{B}})}_{|E^{(j)}}$ of
$\text{Stab}_{G}(\mathcal{B}_{\mathcal{B}}(G))$ on the support $E^{(j)}$ of
each superblock $BB^{(j)}$. It admits a single superblock, so that we can use
the classification result of Theorem 4.7; define accordingly $H_{0}^{(j)}$,
$H^{(j)}$, and $\mathfrak{M}^{(j)}$, such that $G^{(j)}$ is isomorphic to
$[H_{0}^{(j)},{H^{(j)}}^{\infty},\mathfrak{M}^{(j)}]$. Following Corollary
4.10, let $K^{(j)}=H^{(j)}\wr M^{(j)}$ be the minimal finite index normal
subgroup of $G^{(j)}$.

Recall that, by Lemma 4.4, $K^{(j)}=H^{(j)}\wr M^{(j)}$ is the minimal finite
index normal subgroup of $G^{(j)}$, that one has $G^{(j)}=K^{(j)}H_{0}^{(j)}$
and that $H_{0}^{(j)}$ acts diagonally on $E^{(j)}$.

To be concrete, use Lemma 4.12 to choose a _coherent enumeration_ of the
elements of each block $B^{(j)}_{i}$ of $BB^{(j)}$: for each $i,i^{\prime}$
there exists $g\in G$ that maps $B^{(j)}_{i}$ to $B^{(j)}_{i^{\prime}}$ while
preserving the enumeration. From now on, we use this chosen enumeration to
implicitly identify elements of $B^{(j)}_{i}$ and of $B^{(j)}_{i^{\prime}}$
when meaningful. Recall that $M^{(j)}$ is obtained by considering the
homomorphic image $\mathfrak{M}^{(j)}$ of $G^{(j)}$ acting on the blocks in
$BB^{(j)}$ and, if needed, taking its normal subgroup of index $2$ to ensure
that it contains no proper finite index normal subgroup. $H^{(j)}$ can be
obtained by picking arbitrarily two blocks $B^{(j)}_{0}$ and $B^{(j)}_{1}$ in
$BB^{(j)}$, and taking the restriction to $B^{(j)}_{1}$ of the subgroup of $G$
that fixes $B^{(j)}_{0}$ and stabilizes $B^{(j)}_{1}$. Recall also that
$M^{(j)}$ is $\mathfrak{S}_{\infty}$ whenever the blocks are non trivial;
otherwise, $H^{(j)}$ is the trivial permutation group on one element, and
$K^{(j)}=M^{(j)}$ is one of $\mathfrak{S}_{\infty}$,
$\operatorname{Aut}(\mathbb{Q})$ or
$\operatorname{Aut}(\mathbb{Q}/\mathbb{Z})$.

In addition, set by convention $B^{(0)}_{0}=\ker{G}$, $BB^{(0)}=\\{\ker G\\}$,
and $K^{(0)}=\operatorname{Id}_{\ker{G}}$.

######  Remark 5.1.

The groups $K^{(j)}$ and $K^{(j^{\prime})}$ are conjugate whenever the
superblocks $BB^{(j)}$ and $BB^{(j^{\prime})}$ are in the same $G$-orbit.

######  Proposition 5.2.

Let $G$ be a closed $P$-oligomorphic group. Then $K=\prod_{j}K^{(j)}$ is the
minimal finite index normal subgroup of $G$.

Let us start by proving the following result.

######  Lemma 5.3.

A permutation group $K$ of the above form admits no (proper) finite index
normal subgroup.

###### Proof.

If a subgroup $\tilde{K}$ of $K$ is normal and of finite index, Lemma 3.17
states that $K$’s superblocks are still superblocks for $\tilde{K}$; and since
they are stable under $K$, they are also stable under any subgroup of $K$.
Using the classification of Corollary 4.10, the restrictions of $K$ to any
superblocks have no finite index normal subgroup, so $\tilde{K}$ has the same
restrictions and is thus a subdirect product of these. There remains to show
that there is no synchronization between these parts. Again, the $K^{(j)}$
have no finite index normal subgroups, so no finite synchronization (that
would be linked to a proper normal subgroup of finite index) is to consider;
and the case of infinite synchronizations is excluded by Lemma 3.16. ∎

###### Proof of Proposition 5.2.

We are going to reduce $G$ down to $K$ by applying two successive reductions
to a normal subgroup of finite index, which will conclude the proof using
Lemma 5.3.

Recall that the intersection of two finite index normal subgroups is again a
finite index normal subgroup. Hence the finite index normal subgroups of $G$
form a lattice. It is not guaranteed _a priori_ to have a minimal element
though.

We consider the nested block system $\mathcal{B}_{\mathcal{B}}(G)$ introduced
in Section 3. By Lemma 3.17, at each step, the nested block system of the
finite index normal subgroup will still be
$\mathcal{B}_{\mathcal{B}}=\mathcal{B}_{\mathcal{B}}(G)$. In particular, the
kernel will not grow bigger. Denote as earlier by $(BB^{(j)})_{j}$ the
superblocks of $\mathcal{B}_{\mathcal{B}}(G)$ and by $(E^{(j)})_{j}$ their
respective supports.

Let $\text{Stab}_{G}(\mathcal{B}_{\mathcal{B}})$ be the finite index normal
subgroup of $G$ that stabilizes the superblocks in
$\mathcal{B}_{\mathcal{B}}(G)$, which is the first reduction.

Assume first $j\neq 0$. We may apply the classification result of Lemma 4.4 :
${\text{Stab}_{G}(\mathcal{B}_{\mathcal{B}})}_{|E^{(j)}}$ contains as a finite
index normal subgroup some wreath product $H^{(j)}\wr M^{(j)}$, where
$M^{(j)}$ is given by the action of
$\text{Stab}_{G}(\mathcal{B}_{\mathcal{B}})$ on the set of maximal finite
blocks of $E^{(j)}$ (possibly up to taking an index 2 normal subgroup), while
$H^{(j)}$, which acts within the blocks, is given by $H$ in the tower
$H_{0},H,H,H,\ldots$ of
${\text{Stab}_{G}(\mathcal{B}_{\mathcal{B}})}_{|E^{(j)}}$. This subgroup is
isomorphic to $K^{(j)}$, which also implies that it contains no proper normal
subgroup of finite index; therefore, thanks to the aforementionned lattice
structure, it is the minimal finite index normal subgroup of
${\text{Stab}_{G}(\mathcal{B}_{\mathcal{B}})}_{|E^{(j)}}$.

The same conclusions can be reached trivially for $j=0$ (recall that $E^{(0)}$
is the kernel of $G$ and $K^{(0)}$ is the trivial group thereupon).

Now is the time for the second reduction. Consider the finitely many cosets of
$K^{(j)}$ in ${\text{Stab}_{G}(\mathcal{B}_{\mathcal{B}})}_{|E^{(j)}}$; the
latter (and therefore $\text{Stab}_{G}(\mathcal{B}_{\mathcal{B}})$) acts by
permutation on these cosets. Now denote by $\tilde{K}$ the kernel of its
simultaneous action on the whole set of cosets for all $j$. At this point, for
each given $j$, the restriction of $\tilde{K}$ to $E^{(j)}$ is a subgroup of
$K^{(j)}$; it could be a proper subgroup at first glance, due to the
constraints inherited from the action on the other sets of cosets (the cosets
from other $E^{(j)}$, for different $j$). However, thanks to the minimality of
$K^{(j)}$, we do have ${\tilde{K}}_{|E^{(j)}}=K^{(j)}$, for every $j$ :
$\tilde{K}$ is a subdirect product of the direct product $K$. Conclude the
proof by replaying that of Lemma 5.3 to show that $\tilde{K}$ is actually the
whole direct product, namely $K$ itself, and use Lemma 5.3 and the lattice
structure to state its status of minimum. ∎

######  Remark 5.4.

From Remark 3.2, $\mathbb{Q}\mathcal{A}(K)$ is a free algebra, possibly
tensored with some finite dimensional diagonal algebra, which is finitely
generated. Explicitely, we may write:

$\mathbb{Q}\mathcal{A}(K)=\bigotimes_{i}\mathbb{Q}\mathcal{A}(K_{i})\otimes\mathbb{Q}\mathcal{A}(\ker{K})=\mathcal{A}_{f}\otimes\mathbb{Q}\mathcal{A}(\ker{K})=\bigoplus_{k}e_{k}~{}\mathcal{A}_{f}$

the $e_{k}$ being the subsets of the kernel of $K$; in other words,
$\mathbb{Q}\mathcal{A}(K)$ is a Cohen-Macaulay algebra over the free
subalgebra $\mathcal{A}_{f}$.

######  Corollary 5.5.

The lower bound provided by the nested block system according to Remark 4.9 is
tight.

###### Proof.

The algebraic dimension of the algebra of $K$ is the sum of dimensions of the
$\mathcal{A}_{f}$’s, which coincide with the lower bound handed by the nested
system; and the algebraic dimension of $\mathbb{Q}\mathcal{A}(G)$ is the same
by finiteness of the index of $K$. ∎

###  5.2. Semidirect product structure and diagonal action

In this section, we generalize the notion of diagonal action of Section 4, and
prove that $G$ is a product $FK$, where $F$ is a finite permutation group
acting diagonally on $\mathcal{B}_{\mathcal{B}}(G)$, or, equivalently, that
$G$ is a semidirect product of $K$ with some natural quotient $F/K_{<\infty}$.

Informally, a permutation acts diagonally if it acts consistently within each
block of a given superblock, and possibly permutes the superblocks but not the
blocks within each superblock. Considering Figure 5.1, one may intuitively
picture it as a purely vertical action, that permutes the rows formed by the
elements of $E$ on the figure — and preserves the superblock structure of
course. There remains to define formally the vertical alignment.

An indexing of the $B^{(j)}$ within each superblock $BB^{(j)}$ is _coherent_
if, for any two superblock $BB^{(j)}$ and $BB^{(j^{\prime})}$ in the same
orbit, there exists some permutation $g_{j,j^{\prime}}$ in $G$ which maps each
block $B^{(j)}_{i}$ to $B^{(j^{\prime})}_{i}$.

######  Lemma 5.6.

A $P$-oligomorphic group always admits a coherent indexing of the blocks
within each superblock.

###### Proof.

We may, for example, proceed as follow: for each orbit of superblock, pick one
superblock $BB^{(j_{0})}$ and choose any indexing for this superblock; then,
for each superblock $BB^{(j)}$ in its orbit, pick some permutation
$g_{j_{0},j}\in G$ mapping $BB^{(j_{0})}$ to $BB^{(j)}$; use $g_{j_{0},j}\in
G$ to transport the indexing of the blocks in $BB^{(j_{0})}$ to $BB^{(j)}$;
finally, for each $BB^{(j)}$ and $BB^{(j^{\prime})}$ in the orbit of
$BB^{(j_{0})}$, define $g_{j,j^{\prime}}=g_{j_{0},j^{\prime}}g_{j_{0},j}^{-1}$
(here and elsewhere in the paper, composition is denoted from right to left).
∎

From now on, we fix a coherent indexing of the blocks within the superblock.
We further assume without loss of generality that the chosen coherent
enumeration of the elements within the blocks is preserved by the
$g_{j,j^{\prime}}$’s: the enumeration of the elements of a block $B^{(j)}_{i}$
is mapped by $g_{j,j^{\prime}}$ to the enumeration of the elements of
$B^{(j^{\prime})}_{i}$. To achieve this, we may proceed as above: choose the
coherent enumerations in the superblock $BB^{(j_{0})}$, and then use the
$g_{j_{0},j}$ to transport them to the other superblocks in the same orbit.

It will be convenient to index globally the elements of $E$. To this hand,
choose one block $U^{(j)}$ within each superblock in such a way that, whenever
$U^{(j)}$ and $U^{(j^{\prime})}$ are in the same orbit, they have the same
index in $BB^{(j)}$ and $BB^{(j^{\prime})}$ respectively. Let
$U=\sqcup_{j}U^{(j)}$. Now any element $e$ of $E$ can be uniquely described by
two coordinates: “horizontally” the index $i$ of the block $B^{(j)}$
containing it; “vertically”, the element $u\in U$ which corresponds to $e$ in
the coherent enumeration of $U^{(j)}$. For convenience, we identify $e$ with
the pair $(u,i)$.

######  Definition 5.7.

A permutation $g\in G$ _acts diagonally_ on $E$ if any pair of elements
$((u,i_{1}),\,(u,i_{2}))$ is mapped to some pair
$((u^{\prime},i_{1}),\,(u^{\prime},i_{2}))$.

Let respectively $G_{<\infty}$ (resp. $K_{<\infty}$) be the collection of the
permutations of $G$ (resp. $K$) that acts diagonally on $E$.

######  Remark 5.8.

The collections $G_{<\infty}$ and $K_{<\infty}$ are groups and can be
canonically identified with finite permutation groups of $U$. In addition,
$K_{<\infty}$ is the direct product of each $H^{(j)}$ acting on $U^{(j)}$.
Finally, $G_{<\infty}$ as a finite permutation group does not depend on the
choice of the coherent indexing of the blocks within the superblocks and, up
to isomorphism, does not depend on the choice of $U$ or of the coherent
enumeration of the elements within the blocks.

We may now state the main result of this section. Here we settle for
$\operatorname{Rev}$-free groups as this is sufficient for this paper. The
extension to the general case is straightforward at the expense of heavier
notations.

######  Proposition 5.9.

Let $G$ be a $\operatorname{Rev}$-free $P$-oligomorphic group, and $K$ and
$G_{<\infty}$ be defined as above. Then,

  1. (i)

$G=KG_{<\infty}$;

  2. (ii)

$G/K$ is isomorphic to $G_{<\infty}/K_{<\infty}$;

  3. (iii)

$G$ is a semi-direct product of $G_{<\infty}/K_{<\infty}$ and $K$.

###### Proof.

(i) We take $g\in G$ and aim to write it as a product in $KG_{<\infty}$.

Consider some superblock $BB^{(j)}$. Let $j^{\prime}$ be such that $g$ maps
$BB^{(j^{\prime})}$ to $BB^{(j)}$, and set $h=gg_{j,j^{\prime}}$; by
construction, $h$ stabilizes $BB^{(j)}$ and its restriction ${h}_{|E^{(j)}}$
is thus in $G^{(j)}$. Since $G$ is $\operatorname{Rev}$-free, we have
$M^{(j)}=\mathfrak{M}^{(j)}$, and $G^{(j)}=K^{(j)}H_{0}^{(j)}$. Pick
accordingly $k^{(j)}$ in $K^{(j)}$ such that $k^{(j)}{h}_{|E^{(j)}}$ is in
$H_{0}^{(j)}$ and thus acts diagonally on $E^{(j)}$. Then,
$k^{(j)}{g}_{|E^{(j^{\prime})}}$ maps $BB^{(j^{\prime})}$ to $BB^{(j)}$,
preserving the coherent indexing of blocks and enumeration within the blocks.

Define $k=\prod k^{(j)}\in K$ by extending each $k^{(j)}$ by the identity on
the other superblocks. Then, $kg$ acts diagonally, as desired.

(ii) Consider now the morphism $\phi:G_{<\infty}\mapsto G/K$ obtained through
the embedding of $G_{<\infty}$ in $G$ and the canonical projection of the
latter on $G/K$. Thanks to (i), $\phi$ is surjective. In addition
$\ker\phi=G_{<\infty}\cap K=K_{<\infty}$. Therefore, $\phi$ is the desired
isomorphism between $G_{<\infty}/K_{<\infty}$ and $G/K$.

(iii) is a reformulation of (ii). ∎

###  5.3. Classification of closed $P$-oligomorphic groups

We now have all the ingredients to classify (closed) $P$-oligomorphic groups.
We first use the previous sections to extract from a $P$-oligomorphic group
$G$ a finite piece of information $\operatorname{Data}(G)$. It consists of a
finite permutation group, endowed with a block system where each block is
decorated with a permutation group of its elements and one of the five highly
homogeneous permutation groups(or the trivial group). Conversely, we show
that, starting from such a permutation group with decorated blocks $\Delta$,
one can construct an oligomorphic permutation group
$\operatorname{Group}(\Delta)$.

We check that, up to a natural isomorphism, $G$ can be reconstructed from
$\operatorname{Data}(G)$ by $\operatorname{Group}$. More generally, we check
that, up to an isomorphism, $\operatorname{Data}$ and $\operatorname{Group}$
give a one-to-one correspondence between finite permutation groups with
decorated blocks and $P$-oligomorphic permutation groups. This concludes the
classification.

####  5.3.1. Classification of $\operatorname{Rev}$-free closed
$P$-oligomorphic groups

For the sake of simplicity of exposition, we first tackle the subclass of
_$\operatorname{Rev}$ -free groups_; that is groups that do not act by
$\operatorname{Rev}(\mathbb{Q})$ or
$\operatorname{Rev}(\mathbb{Q}/\mathbb{Z})$ on any of their superblocks. This
is actually sufficient to classify ages of $P$-oligomorphic groups. In the
following section, we detail how $\operatorname{Data}(G)$ can be extended to
also preserve this piece of information.

Let $G$ be a closed $P$-oligomorphic group. Take again the notations
introduced at the beginning of the previous subsection:
$\mathcal{B}_{\mathcal{B}}(G)=\\{BB^{(j)}\\}_{j}$, $K=\prod_{j}K^{(j)}$, with
$K^{(j)}=H^{(j)}\wr M^{(j)}$, and finally the finite blocks
$(B^{(j)}_{0})_{j}$ arbitrarily picked in each superblock.

Consider the group $G_{<\infty}$ together with its normal subgroup
$K_{<\infty}=\prod_{j}H^{(j)}$, as defined in Subsection 5.2, and identify
them canonically with permutation groups of the finite set
$\sqcup_{j}B^{(j)}_{0}$.

######  Definition 5.10.

Define
$\operatorname{Data}(G)=(G_{<\infty},(B^{(j)}_{0})_{j},(H^{(j)})_{j},(M^{(j)})_{j})$.

######  Definition 5.11.

A permutation group with decorated blocks $(F,B,(H^{(j)})_{j},(M^{(j)})_{j})$
consists of a finite permutation group $F$ endowed with a block system
$B=\\{B^{(j)}\\}_{j}$ together with the choice, for each block $B^{(j)}$, of

  * •

a normal subgroup $H^{(j)}$ of the restriction ${\text{Fix}_{F}(\cup_{i\neq
j}B^{(i)})}_{|B^{(j)}}$ of the pointwise stabilizer of the other blocks,

  * •

$M^{(j)}$, one of the three minimal highly homogeneous groups, or the trivial
group,

satisfying the following constraints:

  * •

the choices must be the same for $i\neq j$ whenever $B^{(i)}$ and $B^{(j)}$
are in the same $F$-orbit,

  * •

$M^{(j)}$ is $\mathfrak{S}_{\infty}$ whenever $B^{(j)}$ is not of size $1$,

  * •

at most one $M^{(j)}$ is trivial, and when it is $K^{(j)}=H^{(j)}$ is trivial
too.

######  Remark 5.12.

Let $G$ be a closed $P$-oligomorphic permutation group. Then
$\operatorname{Data}(G)$ is a permutation group with decorated blocks (recall
the construction of $K$ at the beginning of Subsection 5.1 and its normality
in $G$ stated by Proposition 5.2).

######  Definition 5.13.

Let $\Delta=(F,B,(H^{(j)})_{j},(M^{(j)})_{j})$ be a permutation group with
decorated blocks, and $E$ the disjoint union $\sqcup_{j}E^{(j)}$, where
$E^{(j)}$ is the cartesian product of $B^{(j)}$ and the domain of $M^{(j)}$.
For each $j$, take the wreath product $K^{(j)}=H^{(j)}\wr M^{(j)}$ acting
naturally on $E^{(j)}$. Finally, let $K$ be the direct product
$\prod_{j}K^{(j)}$, acting on $E$.

We define $\operatorname{Group}(\Delta)$ as the smallest permutation group on
$E$ containing both $K$ and $F$ acting diagonally on $\sqcup_{j}E^{(j)}$.
Denote additionally $H=\prod_{j}H^{(j)}=K_{<\infty}$.

######  Proposition 5.14.

Let $\Delta$ be a permutation group with decorated blocks. Define
$G=\operatorname{Group}(\Delta)$, and use the notations above. Then, $G$ is a
$P$-oligomorphic permutation group.

###### Proof.

The subgroup $K$ of $G$ is the direct product of the wreath products
$H^{(j)}\wr M^{(j)}$, and therefore $P$-oligomorphic. This implies the result
by Lemma 2.6.

∎

We proceed by defining the notion of isomorphism for groups with decorated
blocks, and checking that it matches the classical notion of isomorphism for
$P$-oligomorphic groups.

######  Definition 5.15.

Let $\Delta$ and $\Delta^{\prime}$ be two permutation groups with decorated
blocks. Then, $\Delta$ and $\Delta^{\prime}$ are isomorphic if there exists an
isomorphism between the underlying groups $F$ and $F^{\prime}$ that transports
the block system $B$ and the groups $H^{(j)}$ and $M^{(j)}$ to their
equivalents in $\Delta^{\prime}$.

######  Lemma 5.16.

Let $\Delta$ be a permutation group with decorated blocks. Then
$\operatorname{Group}(\Delta)$ is the natural semidirect product $K\rtimes
F/H$ with the notations of Definition 5.13, and
$\Delta^{\prime}=\operatorname{Data}(\operatorname{Group}(\Delta))$ is
isomorphic to $\Delta$.

###### Proof.

Denote $G=\operatorname{Group}(\Delta)$. The groups $K$, $F$ and $K_{<\infty}$
obtained in Subsection 5.2 from $G$ correspond to the groups of same name from
Definition 5.13, so the results from that subsection apply and the first part
is immediate. In particular, $K$ is a normal subgroup of $G$ of finite index,
which in addition, by Proposition 5.2, admits no finite index normal subgroup
and is therefore the unique minimal finite index normal subgroup of $G$. This
in turn implies the uniqueness of all the other pieces of
$\operatorname{Data}(G)$: the nested block system of $G$ is given by
$\mathcal{B}_{\mathcal{B}}(G)=(BB^{(j)})_{j}$, with
$BB^{(j)}=(B^{(j)}_{i})_{i}$ and, for $i$ in the support of $M^{(j)}$,
$B^{(j)}_{i}=B^{(j)}\times\\{i\\}$; the permutation subgroups $G_{<\infty}$
and $K_{<\infty}$ induced respectively by $G$ and $K$ on
$\sqcup_{j}B^{(j)}_{0}$ are respectively trivially isomorphic to $F$ and $H$.
∎

######  Lemma 5.17.

Let $G$ be a $\operatorname{Rev}$-free $P$-oligomorphic group. Then,
$G^{\prime}=\operatorname{Group}(\operatorname{Data}(G))$ is isomorphic to
$G$.

###### Proof.

We use the coherent enumeration to identify the elements of each $B^{(j)}_{i}$
with that of $B^{(j)}\times\\{i\\}$. Through this identification and by
construction, we have $K^{\prime}=K$; since the finite groups acting
diagonally are the same as well, and using Proposition 5.9, we have indeed
$G^{\prime}=G$. ∎

######  Theorem 5.18.

$\operatorname{Rev}$-free $P$-oligomorphic permutation groups are classified
by finite permutation groups with decorated blocks through the
$\operatorname{Data}$ and $\operatorname{Group}$ reciprocal correspondences.

###### Proof.

Lemma 5.16 together with Lemma 5.16 asserts that $\operatorname{Data}$ and
$\operatorname{Group}$ are reciprocal correspondences, as desired. ∎

####  5.3.2. Extending the classification to all $P$-oligomorphic groups

We start with an example illustrating that the straightforward extension of
$\operatorname{Data}$ to all $P$-oligomorphic groups does not give a proper
correspondence.

######  Example 5.19.

Consider the $P$-oligomorphic group
$G=\operatorname{Rev}{\mathbb{Q}}\times\operatorname{Rev}{\mathbb{Q}}$, and
the index $2$ subgroup generated by
$G^{\prime}=\operatorname{Aut}{\mathbb{Q}}\times\operatorname{Aut}{\mathbb{Q}}$
on the one hand and the reversal acting simultaneously on the two copies of
$\mathbb{Q}$ on the other hand.

Let us try to define $\operatorname{Data}$ on $G$ and $G^{\prime}$ as before;
in both cases, we get the same data:

$\left(\operatorname{id}(\\{1,2\\}),(\\{i\\})_{i=1,2},(\operatorname{id}(\\{i\\}))_{i=1,2},(\operatorname{Rev}(\mathbb{Q}))_{i=1,2}\right)\,.$

The information about the synchronization of the reversal on the two
superblock is lost.

We now tweak the definition of $\operatorname{Data}$ to keep track of
reversals in the finite group $G_{<\infty}$. To achieve this, each copy of
$R=\mathbb{Q}$ (or of $R=\mathbb{Q}/\mathbb{Z}$) where a reversal can occur
will be compressed into a block of two points instead of a single one.

Let $BB^{(j)}$ be a superblock; if its blocks are of size $1$ and $G$ acts on
them by $M^{(j)}=\operatorname{Rev}(R)$, then define $\overline{B}^{(j)}_{0}$
by choosing any two points of $E^{(j)}$; note that $\overline{B}^{(j)}_{0}$ is
not a block anymore, but this is fine. Otherwise, define
$\overline{B}^{(j)}_{0}$ as $B^{(j)}_{0}$.

Define $\overline{G}_{<\infty}$ as before, but using
$\sqcup_{j}\overline{B}^{(j)}_{0}$ instead of $\sqcup_{j}B^{(j)}_{0}$.

######  Example 5.20.

With $G$ and $G^{\prime}$ as in the previous example, $\overline{G}_{<\infty}$
and $\overline{G}^{\prime}_{<\infty}$ both act on $\\{1,2\\}\sqcup\\{1,2\\}$.
However $\overline{G}_{<\infty}$ is of size 4, permuting independently the two
blocks, whereas $\overline{G}^{\prime}_{<\infty}$ is of size 2, permuting
simultaneously the two blocks.

######  Definition 5.21.

Define
$\overline{\operatorname{Data}}{(G)}=(\overline{G}_{<\infty},(\overline{B}^{(j)}_{0})_{j},(H^{(j)})_{j},(M^{(j)})_{j})$.

The definition of permutation group with decorated blocks must be extended
accordingly: each $M^{(j)}$ can now be any one of the five closed highly
homogeneous groups; however $\overline{B}^{(j)}$ must be of size $2$ whenever
$M^{(j)}$ is of the form $\operatorname{Rev}(R)$ and of size $1$ whenever
$M^{(j)}$ is of the form $\operatorname{Aut}(R)$.

The definition of $\operatorname{Group}$ must be adjusted as well: if
$M^{(j)}$ is of the form $\operatorname{Rev}(R)$ and therefore $B^{(j)}$ is of
size $2$, then $E^{(j)}$ consists of a single copy of the support of
$M^{(j)}$. Furthermore, the diagonal action of an element $f$ of $F$ on $E$
must be adjusted: assumes that $M^{(j)}$ is of the form
$\operatorname{Rev}(R)$ and therefore $B^{(j)}$ is of size $2$; let
$j^{\prime}$ be such that $f$ maps $B^{(j)}$ to $B^{(j^{\prime})}$. Then, $f$
maps the elements of $E^{(j)}$ onto those of $E^{(j^{\prime})}$, with a
reversal whenever the elements of $B^{(j)}$ are swapped by $f$ in
$B^{(j^{\prime})}$.

######  Theorem 5.22.

$P$-oligomorphic permutation groups are classified by finite permutation
groups with (extended) decorated blocks through the
$\overline{\operatorname{Data}}$ and $\overline{\operatorname{Group}}$
reciprocal correspondences.

###### Proof.

Follow the steps of the proof of Theorem 5.18, mutatis-mutandis. ∎

##  6\. Resolution of the conjectures and the Cohen-Macaulay property

Here, we use the classification previously obtained to prove that the orbit
algebra of $G$ is isomorphic to (a simple quotient of) the invariant ring of a
finite permutation group $F$. We deduce that Macpherson’s conjecture holds:
$\mathbb{Q}\mathcal{A}(G)$ is finitely generated, and even Cohen-Macaulay. In
addition, the minimal finite index subgroup $K$ prescribes the algebraic
dimension of the orbit algebra of $G$ and provides a natural system of
parameters, and thus (a choice of) the degrees appearing in the denominator of
1, the Hilbert series.

Let $G$ be a (closed) $P$-oligomorphic group, $K=\prod_{j}K^{(j)}$ its minimal
subgroup of finite index, and use again the notations of the previous section.
Let $D_{G}$ be the set of degrees of the non zero degree elements of the ages
$\mathcal{A}(H^{(j)})$ of the $H^{(j)}$’s.

######  Theorem 6.1.

Let $G$ be a permutation group whose profile is bounded by a polynomial. Then,
$\mathbb{Q}\mathcal{A}(G)$ is isomorphic to the algebra of invariants of some
finite permutation group acting on variables of degrees $D_{G}$, quotiented by
the relations $x^{2}=0$ for some of the variables.

###### Proof.

For each superblock $BB^{(j)}$, let $S_{j}$ be the collection of all the non-
trivial subsets of all blocks of $BB^{(j)}$. Let $S=\sqcup_{j}S_{j}$. By the
definition of block systems, $K$ acts on each $S_{j}$ and on $S$. Denote by
$(\theta_{i,j})_{i}$ the $K$-orbits in $S_{j}$ and observe that they are in
bijection with the positive degree part $\mathcal{A}(G)^{+}(H^{(j)})$ of the
age of $H^{(j)}$.

As in Example 2.13, the orbit algebra $\mathbb{Q}\mathcal{A}(K^{(j)})$ of
$K^{(j)}$, for $j\neq 0$, is the free algebra
$\mathbb{Q}[(\theta_{i,j})_{i}]$; for $j=0$, the orbit algebra is the finite
dimensional algebra
$\mathbb{Q}[(\theta_{i,0})_{i}]/(\theta_{i,0}^{2}=0~{}\forall i)$ instead. The
orbit algebra of $K$ itself is the tensor product
$\bigotimes_{j}\mathbb{Q}\mathcal{A}(K^{(j)})$, generated by
$(\theta_{i,j})_{i,j}$.

The group $G$ itself also acts on $S$; since $K$ is normal in $G$, this lifts
to an action on the finitely many $K$-orbits $(\theta_{i,j})_{i,j}$ in $S$.
Let $G_{0}$ be the finite permutation group induced by this action, and let
$\mathbb{Q}[(\theta_{i,j})_{i,j}]^{G_{0}}$ be its invariant ring. Then,
$\mathbb{Q}\mathcal{A}(G)$ is the following quotient thereof:

$\mathbb{Q}\mathcal{A}(G)=\mathbb{Q}[(\theta_{i,j})_{i,j}]^{G_{0}}/(\theta_{i,0}^{2}=0~{}\forall
i)\,.$

∎

An immediate corollary is a positive resolution of Macpherson’s question and
therefore Cameron’s conjecture.

######  Corollary 6.2.

The orbit algebra $\mathbb{Q}\mathcal{A}(G)$ of a $P$-oligomorphic permutation
group $G$ is finitely generated.

###### Proof.

By Hilbert theorem, the invariant ring of a finite group is finitely generated
(see e.g. [Sta79, Theorem 1.2]) and $\mathbb{Q}\mathcal{A}(G)$ is a quotient
thereof. ∎

Invariant rings of permutation groups are not only finitely generated and but
also Cohen-Macaulay (see e.g. [Sta79, Theorem 3.2]). The quotient of a Cohen-
Macaulay algebra is not Cohen-Macaulay in general, but the statement and proof
of [Sta79, Theorem 3.2] can be generalized to suitable quotients of invariant
rings to deduce that orbit algebras are Cohen-Macaulay.

Let us first recall the following classical fact about graded commutative
algebras.

######  Fact 6.3.

Let $R=\bigoplus_{d\in\mathbb{N}}R_{d}$ be a graded connected commutative
algebra (over a field $\mathbb{K}$) and take a free graded $R$-module $A$.
Then, from any homogeneous $\mathbb{K}$-basis of $A$, we may extract a
subfamily which is an $R$-basis of $A$.

###### Proof.

Write $R^{+}=\bigoplus_{d>0}R_{d}$, and consider a family $(\nu_{k})_{k\in K}$
of secondary invariants for $A$: $A=\bigoplus_{k\in K}\nu_{k}R$ ; let then
$(\beta_{j})_{j}$ be a vector basis of $A$, each $\beta_{j}$ being chosen
homogeneous. Proceed by degree $d$: note that the elements $\nu_{k}$ of degree
$d$ form a vector basis of a supplementary in $A_{d}$ of the homogeneous
component $(R^{+}A)_{d}$ of the ideal $R^{+}A$; extract from $(\beta_{j})_{j}$
a basis of some other supplementary. We obtain a subfamily $(\mu_{k})_{k\in
K}$ which spans $M$ as an $R$-module and is equinumerous in each degree with
the family $(\nu_{k})_{k}$. By dimension count, it is an $R$-basis of $M$. ∎

######  Lemma 6.4.

Let $F$ be a finite permutation group of a set $X\sqcup Y$ of variables.
Assume that $F$ stabilizes $X$ and $Y$. Then, $\mathbb{Q}[X\sqcup
Y]^{F}/(y^{2},\ y\in Y)$ is Cohen-Macaulay.

###### Proof.

Since $F$ stabilizes $X$ and $Y$, we may take
$\operatorname{Sym}(X)\operatorname{Sym}(Y)$ as ring of primary invariants,
over which $A=\mathbb{Q}[X\sqcup Y]^{F}$ is a finite dimensional free module;
in other words, there exists a finite collection of homogeneous invariants
$\nu_{k}$ such that we have:

$A=\bigoplus_{k\in K}\nu_{k}\operatorname{Sym}(X)\operatorname{Sym}(Y)\,.$

It follows that $A$ is an (infinite dimensional) $\operatorname{Sym}(X)$-free
module. For instance, we have:

$A=\bigoplus_{k,\lambda}\nu_{k}p_{\lambda}(Y)\operatorname{Sym}(X)\,,$

where $(p_{\lambda}(Y))_{\lambda}$ is the _power sum multiplicative basis_ of
$\operatorname{Sym}(Y)$: for $\lambda$ an integer partition,
$p_{\lambda}(Y)=\prod_{d\in\lambda}p_{d}(Y)$, where $p_{d}(Y):=\sum_{y\in
Y}y^{d}$ is the $d$-th _symmetric power sum_. A first consequence is that the
quotient $A/(y^{2},\ y\in Y)$ is a finitely generated
$\operatorname{Sym}(X)$-module:

$A/(y^{2},\ y\in Y)=\sum_{k\in K,\
i=1,\dots,|Y|}\nu_{k}p_{1}^{i}(Y)\operatorname{Sym}(X)\,.$

There remains to show that it is a free module. To this end, let us come back
to $A$ and consider its monomial basis, that is, the collection of all
$F$-orbit sums of monomials in $\mathbb{Q}[X\sqcup Y]$. By Fact 6.3, we may
extract from the monomial basis a family $(\mu_{\ell})_{\ell\in L}$ which
forms a $\operatorname{Sym}(X)$-basis of $A$:

$A=\bigoplus_{\ell\in L}\mu_{\ell}\operatorname{Sym}(X)\,.$

Remark that, if a monomial is divisible by $y^{2}$ for some $y\in Y$, then the
same holds for any other monomial in its orbit sum. Therefore, in the
quotient, each monomial $\mu_{\ell}$ either vanishes completely or is left
unaffected, and the same holds accordingly for the principal ideal
$\mu_{\ell}\operatorname{Sym}(X)$. Therefore, we have indeed:

$A/(y^{2},\ y\in Y)=\bigoplus_{\ell\in
L^{\prime}}\mu_{\ell}\operatorname{Sym}(X)\,,$

for some subset $L^{\prime}$ of $L$, so that $A/(y^{2})$ is a finite
dimensional free $\operatorname{Sym}(X)$-module, as desired. ∎

######  Corollary 6.5.

The orbit algebra $\mathbb{Q}\mathcal{A}(G)$ of a $P$-oligomorphic permutation
group $G$ is Cohen-Macaulay.

## References

  * [BBSS09] J. Balogh, B. Bollobás, M. Saks, and V. T. Sós.  The unlabelled speed of a hereditary graph property.  J. Combin. Theory Ser. B, 99(1):9–19, 2009.
  * [Bol98] B. Bollobás.  Hereditary properties of graphs: asymptotic enumeration, global structure, and colouring.  In Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998), number Extra Vol. III, pages 333–342 (electronic), 1998.
  * [Cam90] P. J. Cameron.  Oligomorphic permutation groups, volume 152 of London Mathematical Society Lecture Note Series.  Cambridge University Press, Cambridge, 1990.
  * [Cam97] P. J. Cameron.  The algebra of an age.  In Model theory of groups and automorphism groups (Blaubeuren, 1995), volume 244 of London Math. Soc. Lecture Note Ser., pages 126–133. Cambridge Univ. Press, Cambridge, 1997.
  * [Cam09] P. J. Cameron.  Oligomorphic permutation groups.  In Mohan Delampady N. S. Narasimha Sastry, T. S. S. R. K. Rao and B. Rajeev, editors, Perspectives in Mathematical Sciences II: Pure Mathematics, pages 37–61. World Scientific, Singapore, 2009.
  * [Fal19] Justine Falque.  Classification of P-oligomorphic groups; Conjectures of Cameron and Macpherson.  PhD thesis, Université Paris-Sud, November 2019.  136 pages.
  * [Fra00] R. Fraïssé.  Theory of relations, volume 145 of Studies in Logic and the Foundations of Mathematics.  North-Holland Publishing Co., Amsterdam, revised edition, 2000.  With an appendix by Norbert Sauer.
  * [FT18] Justine Falque and Nicolas M. Thiéry.  Macpherson’s conjecture holds: The orbit algebra of a permutation group with polynomial profile is finitely generated.  In 30th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2018, Hanover), February 2018\.
  * [GAP99] The GAP Group, Aachen, St Andrews.  GAP – Groups, Algorithms, and Programming, Version 4.10, 1999\.
  * [KK03] T. Kaiser and M. Klazar.  On growth rates of closed permutation classes.  Electron. J. Combin., 9(2):Research paper 10, 20 pp. (electronic), 2002/03.  Permutation patterns (Otago, 2003).
  * [Kla08] M. Klazar.  Overview of some general results in combinatorial enumeration.  Arxiv preprint arXiv:0803.4292, 2008.
  * [Mac85a] H. D. Macpherson.  Growth rates in infinite graphs and permutation groups.  Proceedings of the London Mathematical Society, 3(2):285–294, 1985\.
  * [Mac85b] H. D. Macpherson.  Orbits of infinite permutation groups.  Proc. London Math. Soc. (3), 51(2):246–284, 1985.
  * [Pou06] M. Pouzet.  The profile of relations.  Glob. J. Pure Appl. Math., 2(3):237–272, 2006.
  * [Pou08] M. Pouzet.  When is the orbit algebra of a group an integral domain? Proof of a conjecture of P. J. Cameron.  Theor. Inform. Appl., 42(1):83–103, 2008.
  * [PT13] M. Pouzet and N. M. Thiéry.  Some relational structures with polynomial growth and their associated algebras I: Quasi-polynomiality of the profile.  Electron. J. Combin., 20(2):Paper 1, 35, 2013.
  * [PT18] M. Pouzet and N. M. Thiéry.  Some relational structures with polynomial growth and their associated algebras II: Finite generation, 2018.  In preparation, 26 pages.
  * [RN59] C. Ryll-Nardzewski.  On the categoricity in power $\leq\aleph_{0}$.  Bull. Acad. Polon. Sci. Sér. Sci. Math. Astr. Phys., 7:545–548. (unbound insert), 1959.
  * [Sta79] R. P. Stanley.  Invariants of finite groups and their applications to combinatorics.  Bull. Amer. Math. Soc. (N.S.), 1(3):475–511, 1979.
  * [The20] The Sage Developers.  SageMath, the Sage Mathematics Software System (Version 9.0), 2020.  https://www.sagemath.org.