REPRESENTATIONS OF FINITE SETS AND CORRESPONDENCES

SERGE BOUC

Abstract. This is a report on a long term joint work with Jacques Thévenaz on Correspondence functors. It is an expanded version of the mini-course I gave at the workshop of the ICRA2018 conference in Prague in August 2018.

1. Introduction

This report is an expanded version of the mini-course I gave during the workshop of the ICRA2018 conference in Prague in August 2018. It it a survey of the main results obtained so far in this long term joint work with Jacques Thévenaz on Correspondence functors, in which we develop the representation theory of finite sets and correspondences.

The representation theory of finite sets has been considered from various points of view. Pirashvili [Pir00] treats the case of pointed sets and maps, while Church, Ellenberg and Farb [CEF15] consider the case where the morphisms are all injective maps. Putman and Sam [PS17] use all k-linear splittable injections between finiterank free k-modules (where k is a commutative ring). We have chosen instead not to use any kind of maps, but rather all correspondences as morphisms, in order to get a self dual category of finite sets. At first we had no specific application in mind, our main motivation being provided by the fact that finite sets are basic objects in mathematics, and correspondences a natural generalization of maps. Still, it turns out that this functorial approach of sets and correspondences sheds a new light on the representation theory of the algebra of relations on a finite set (Theorem 11.7). The theory has many other surprising results, e.g. the fact that the finitely generated correspondence functors over a field have finite length, and that they are characterized by the exponential behaviour of the dimension of their evaluations (Theorem 7.5).

This survey is organized as follows: in Section 2, we recall some basics on representations of categories. The category of finite sets and correspondences is introduced in Section 3, as well as the algebra of essential relations on a finite set. Sections 4 and 5 describe the simple modules for this algebra, leading to a parametrization of the simple correspondence functors, introduced in Section 6. Sections 7 and 8 are concerned with finiteness properties and stability properties of correspondence functors. In Section 9, correspondence functors associated to finite lattices are introduced, and some of their properties are stated. This leads in Section 10 to the notion of fundamental functor associated to a finite poset. Finally, Section 11 gives a complete description of the simple correspondence functors.

1991 Mathematics Subject Classification. AMS Subject Classification: 06B05, 06B15, 06D05, 06D50, 16B50, 18B05, 18B10, 18B35, 18E05.

Key words and phrases. Keywords: finite set, correspondence, functor category, simple functor, finite length, poset.

2. The representation theory of categories

We first recall some standard facts from the representation theory of categories. Let D be a category and let X and Y be two objects of D. We reverse the usual notation and write D(Y, X) for the set of all morphisms from X to Y. We assume that D is skeletally small. This allows us to talk about the set of natural transformations between two functors starting from D.

Throughout this paper, k denotes a commutative ring.

2.1. Definition. The k-linearization of a category D, where k is any commutative ring, is defined as follows :

• The objects of kD are the objects of D.

• For any two objects X and Y, the set of morphisms from X to Y is the free k-module kD(Y, X) with basis D(Y, X).

• The composition of morphisms in kD is the k-bilinear extension

kD(Z, Y) × kD(Y, X) ⟶ kD(Z, X)

of the composition in D.

2.2. Definition. Let D be a category and k a commutative ring. A k-representation of the category D is a k-linear functor from kD to the category k- Mod of k-modules.

We could have defined a k-representation of D as a functor from D to k- Mod, but it is convenient to linearize first the category D (just as for group representations, where one can first introduce the group algebra).

If F : kD → k- Mod is a k-representation of D and if X is an object of D, then F (X) will be called the evaluation of F at X. Morphisms in kD act on the left on the evaluations of F by setting, for every m ∈ F (X) and for every morphism α ∈ kD(Y, X),

α · m := F (α)(m) ∈ F (Y) .

We often use a dot for this action of morphisms on evaluation of functors.

The category F_{k}(kD, k- Mod) of all k-representations of D is an abelian category. A sequence of functors

0 ⟶ F_{1} ⟶ F_{2} ⟶ F_{3} ⟶ 0

is exact if and only if, for every object X, the evaluation sequence

0 ⟶ F_{1}(X) ⟶ F_{2}(X) ⟶ F_{3}(X) ⟶ 0

is exact. Also, a k-representation of D is called simple if it is nonzero and has no proper nonzero subfunctor.

For any object X of D, consider the representable functor kD(−, X) (which is a projective functor by Yoneda’s lemma). Its evaluation at an object Y is the k-module kD(Y, X), which has a natural structure of a (kD(Y, Y), kD(X, X))- bimodule by composition.

2.3. Notation. Let X be an object of D and let V be a kD(X, X)-module. We define

L_{X,V} := kD(−, X) ⊗_{kD(X,X)} V .

This is a k-representation of D.

This satisfies the following adjunction property.

2.4. Lemma. Let F = F_{k}(kD, k- Mod) be the category of all k-representations of D and let X be an object of D.

(a) The functor

kD(X, X)- Mod ⟶ F , V ↦ L_{X,V}

is left adjoint of the evaluation functor

F ⟶ kD(X, X)- Mod , F ↦ F (X) .

In other words, for any k-representation F : kD → k- Mod and any kD(X, X)- module V, there is a natural isomorphism

Hom_{F}(L_{X,V} , F) ≅ Hom_{kD(X,X)} (V, F (X)) .

Moreover L_{X,V} (X) ≅ V as kD(X, X)-modules. In particular, there is a k-algebra isomorphism End_{F}(L_{X,V}) ≅ End_{kD(X,X)}(V).

(b) The functor kD(X, X)- Mod ⟶ F is right exact. It maps projective modules to projective functors, and indecomposable modules to indecomposable functors.

Proof. Part (a) is straightforward and is proved in Section 2 of [Bou96]. Part (b) follows because this functor is left adjoint of an exact functor and satisfies the property L_{X,V} (X) ≅ V. □

Our next result is a slight extension of the first lemma of [Bou96].

2.5. Lemma. Let X be an object of D and let V be a kD(X, X)-module. For any object Y of D, let

J_{X,V} (Y) := { ∑_{i} ϕ_{i} ⊗ w_{i} ∈ L_{X,V} (Y) | ∀ψ ∈ kD(X, Y), ∑_{i}(ψϕ_{i}) · w_{i} = 0} .

(a) J_{X,V} is the largest subfunctor of L_{X,V} which vanishes at X.

(b) If V is a simple module, then J_{X,V} is the unique maximal subfunctor of L_{X,V} and L_{X,V} /J_{X,V} is a simple functor.

Proof. The proof is sketched in Lemma 2.3 of [BST13] in the special case of biset functors for finite groups, but it extends without change to representations of an arbitrary category D. □

Lemma 2.5 is our main tool for dealing with simple functors. We first fix the notation.

2.6. Notation. Let X be an object of D and let V be a kD(X, X)-module. We define

S_{X,V} := L_{X,V} /J_{X,V} .

If V is a simple kD(X, X)-module, then S_{X,V} is a simple functor.

We emphasize that L_{X,V} and S_{X,V} are defined for any kD(X, X)-module V and any commutative ring k. Note that we always have J_{X,V} (X) = {0} because if

a = ∑_{i} ϕ_{i} ⊗ w_{i} ∈ J_{X,V} (X), then a = id_{X} ⊗(∑_{i} ϕ_{i} · w_{i}) = 0.

Therefore, we have isomorphisms of kD(X, X)-modules

L_{X,V} (X) ≅ S_{X,V} (X) ≅ V .

2.7. Proposition. Let S be a simple k-representation of D and let Y be an object of D such that S(Y) ≠ 0.

(a) S(Y) is a simple kD(Y, Y)-module.

(b) S ≅ S_{Y,S(Y)}.

(c) S is generated by S(Y), that is, S(X) = kD(X, Y)S(Y) for all objects X. More precisely, if 0 ≠ u ∈ S(Y), then S(X) = kD(X, Y) · u.

Proof. (c) Given 0 ≠ u ∈ S(Y), let S′(X) = kD(X, Y) · u for all objects X. This clearly defines a nonzero subfunctor S′ of S, so S′ = S by simplicity of S.

(a) This follows from (c).

(b) By the adjunction of Lemma 2.4, the identity id : S(Y) → S(Y) corresponds to a non-zero morphism θ : L_{Y,S(Y)} → S, which must be surjective since S is simple. But S_{Y,S(Y)} is the unique simple quotient of L_{Y,S(Y)}, by Lemma 2.5 and Notation 2.6, so S ≅ S_{Y,S(Y)}. □

2.8. It should be noted that a simple k-representation S has many possible realizations S ≅ S_{Y,V} as above, where V = S(Y) ≠ 0. However, if there is a notion of unique minimal object, then one can parametrize simple functors S by setting S ≅ S_{Y,V}, where Y is the unique minimal object such that S(Y) ≠ 0. In this case, the evaluation V = S(Y) is actually a module for the quotient algebra

kD̂(Y) = kD(Y, Y)/ ∑_{Z} kD(Y, Z)kD(Z, Y)

where Z runs through objects which are stricly smaller than Y. In the case of the category of finite sets and correspondences, this will be the motivation for considering the algebra of essential relations on a finite set (see Definition 3.3).

The following result establishes a link between the simple subquotients of a functor and the simple subquotients of its evaluations:

2.9. Proposition. [[BST13] Proposition 3.5, [BT18b] Proposition 2.8] Let S be a simple k-representation of D and let Y be an object of D such that S(Y) ≠ 0. Let F be any k-representation of D. Then the following are equivalent:

(a) S is isomorphic to a subquotient of F.

(b) The simple kD(Y, Y)-module S(Y) is isomorphic to a subquotient of the kD(Y, Y)-module F (Y).

Proof. It is clear that (a) implies (b). Suppose that (b) holds and let W_{1}, W_{2} be submodules of F (Y) such that W_{2} ⊂ W_{1} and W_{1}/W_{2} ≅ S(Y). For i ∈ {1, 2}, and for any object X of D, set F_{i}(X) = kD(X, Y) · W_{i} ⊆ F (X). Then F_{2} ⊆ F_{1} are subfunctors of F. Moreover F_{i}(Y) = W_{i} for i ∈ {1, 2}, and (F_{1}/F_{2})(Y) = W_{1}/W_{2} ≅ S(Y). The isomorphism S(Y) → (F_{1}/F_{2})(Y) induces, by the adjunction of Lemma 2.4, a nonzero morphism θ : L_{Y,S(Y)} → F_{1}/F_{2}. Since S(Y) is simple, the functor L_{Y,S(Y)} has a unique maximal subfunctor J_{Y,S(Y)}, by Lemma 2.5, and L_{Y,S(Y)}/J_{Y,S(Y)} ≅ S_{Y,S(Y)} ≅ S, by Proposition 2.7. Let F′_{1} = θ(L_{Y,S(Y)}) and F′_{2} = θ(J_{Y,S(Y)}). Since θ ≠ 0, we obtain

F′_{1}/F′_{2} ≅ L_{Y,S(Y)}/J_{Y,S(Y)} ≅ S_{Y,S(Y)} ≅ S ,

showing that S is isomorphic to a subquotient of F. □

(Actually, as observed by Hida and Yagita in Lemma 3.1 of [HY14], we have an equality F′_{1} = F_{1}, because both subfunctors are generated by their common evaluation at Y.)

3. Correspondences and relations

3.1. Let X and Y be finite sets. A correspondence from X to Y is a subset R of Y × X. In case X = Y, we say that R is a relation on X.

Correspondences can be composed as follows. If R ⊆ Y × X and S ⊆ Z × Y, then SR is the correspondence from X to Z defined by

SR = {(z, x) ∈ Z × X | ∃ y ∈ Y such that (z, y) ∈ S and (y, x) ∈ R} .

One can check easily that the composition of correspondences is associative. For a finite set X, the equality relation

Δ_{X} = {(x, x) | x ∈ X} ⊆ X × X

acts as an identity element for the composition of correspondences. In particular the set of all relations on X is a monoid.

3.2. Definition. The category C of finite sets and correspondences is defined as follows:

• The objects of C are finite sets.

• if X and Y are finite sets, the set of morphisms from X to Y in C is the set C(Y, X) of correspondences from X to Y.

• The composition of morphisms in C is the composition of correspondences.

• The identity morphism of the finite set X is Δ_{X} ∈ C(X, X).

Given a commutative ring k, we will also consider the k-linearization kC of C, introduced in Section 2, called the k-category of finite sets and correspondences.

When X is a finite set, the endomorphism algebra R_{X} = kC(X, X) of X in the category kC is called the algebra of relations on X. It is the algebra over k of the monoid of relations on X.

3.3. Definition. A relation R on a finite set X is called inessential if there exists a finite set Y with |Y | < |X| and correspondences U ∈ C(X, Y) and V ∈ C(Y, X) such that R = UV. A relation is called essential if it is not inessential.

The subset I_{X} of the algebra R_{X} consisting of k-linear combinations of inessential relations is a two sided ideal. The quotient algebra E_{X} = R_{X}/I_{X} is called the algebra of essential relations on X (or the essential algebra, for short).

In other words, an essential relation is a relation of maximal Schein rank, in the sense of Section 1.4 of [Kim82].

The algebra E_{X} has a k-basis consisting of essential relations. The product in E_{X} of two essential relations R and S on X is equal to RS if RS is essential, and to 0 otherwise.

3.4. Example.

• Let X be a finite set with |X| ≥ 2, and A, B be subsets of X. Then the relation R = A × B on X is inessential: if Y is a set of cardinality 1, then R = UV, where U = A × Y and V = Y × B.

• Let X = {1, 2}, and R = {(1, 1), (1, 2), (2, 1)} ∈ C(X, X). Then one checks easily that R is essential, but R^{2} = X × X is not.

3.5. Lemma. [[BT16] Lemma 2.1] Let X be a finite set of cardinality n, and R ∈ C(X, X). Then R is inessential if and only if there are subsets U_{i} and V_{i} of X,

for 1 ≤ i ≤ n − 1, such that R = ⋃_{i=1}^{n−1}(U_{i} × V_{i}).

3.6. Classical definitions When X and Y are finite sets and R ∈ C(Y, X), we denote by R^{op} ∈ C(X, Y) the opposite correspondence, defined by

R^{op} = {(x, y) ∈ X × Y | (y, x) ∈ R}.

With this notation, the following classical properties of a relation R on a finite set X can be translated as follows:

R is reflexive ⟺ Δ_{X} ⊆ R
R is transitive ⟺ R^{2} ⊆ R
R is a preorder ⟺ Δ_{X} ⊆ R = R^{2}
R is symmetric ⟺ R = R^{op}
R is an equivalence relation ⟺ Δ_{X} ⊆ R = R^{op} = R^{2}
R is antisymmetric ⟺ R ∩ R^{op} ⊆ Δ_{X}
R is an order ⟺ R = R^{2} and R ∩ R^{op} = Δ_{X}.

3.7. Remark.

• Note that unless otherwise specified, by order we always mean partial order.

• It follows from Lemma 3.5 that if R is a preorder on X which is not an order, then R is inessential.

• On the other hand, if R is an order on X and Δ_{X} ⊆ Q ⊆ R, then Q is essential.

3.8. Let X be a finite set. For an element σ of the group Σ_{X} of permutations of X, we set

Δ_{σ} = {(σ(x), x) | x ∈ X}.

We call Δ_{σ} the permuted diagonal associated to σ. One checks easily that the map σ ∈ Σ_{X} ↦ Δ_{σ} ∈ C(X, X) is a monoid homomorphism, and it follows in particular that Δ_{σ} is an essential relation on X, for any σ ∈ Σ_{X}.

3.9. Theorem. [[BT16] Theorem 3.2] Let X be a finite set and R be an essential relation on X. Then there exists a permutation σ of X such that Δ_{σ} ⊆ R, i.e. R = SΔ_{σ}, where S is a reflexive relation on X.

Proof. Let R be an essential relation on X. For any a ∈ A, set

R_{a} = {x ∈ X | (x, a) ∈ R} and _{a}R = {x ∈ X | (a, x) ∈ R}.

For any subset A of X, define

R_{A} = {x ∈ X | ∃ a ∈ A such that (x, a) ∈ R} = ⋃_{a∈A} R_{a}.

Then R decomposes as a union

R = ( ⋃_{y∉A}(R_{y} × {y})) ⋃ ( ⋃_{x∈R_{A}}({x} ×_{x}R)) .

Since R is essential, Card(X − A) + Card(R_{A}) cannot be strictly smaller than Card(X), by Lemma 3.5. Therefore Card(R_{A}) ≥ Card(A), for all subsets A of X, that is

Card ( ⋃_{a∈A} R_{a}) ≥ Card(A) .

This is precisely the assumption in a theorem of Philip Hall (see Theorem 5.1.1 in [Hal86], or [Hal35] for the original version which is slightly different). The conclusion is that there exist elements x_{y} ∈ R_{y}, where y runs over X, which are all distinct. In other words σ : y ↦ x_{y} is a permutation and

(σ(y), y) = (x_{y}, y) ∈ R for all y ∈ X .

This means that R contains Δ_{σ}, as required. □

4. The algebra of permuted orders

4.1. Let X be a finite set, and S be a reflexive relation on X. Then Δ_{X} ⊆ S, and for any integer m ≥ 1

Δ_{X} ⊆ S ⊆ S^{2} ⊆ … ⊆ S^{m}.

Since X is finite, there exists m such that S^{m} = S^{m+1}. Let \overline{S} = S^{m} denote this limit value. The relation \overline{S} is called the transitive closure of S. It is a preorder. There are now two cases, by Remark 3.7:

• either \overline{S} is not an order, and then \overline{S} = 0 in E_{X}.

• or \overline{S} is an order, and then S is essential, since Δ_{X} ⊆ S ⊆ \overline{S}.

4.2. Theorem. [[BT16] Theorem 5.3] Let N_{X} be the subset of E_{X} consisting of k-linear combinations of elements of the form (S − \overline{S})Δ_{σ}, where S is a reflexive relation on X, and σ ∈ Σ_{X}.

(a) N_{X} is a two sided nilpotent ideal of E_{X}.

(b) The quotient algebra P_{X} = E_{X}/N_{X} has a k-basis consisting of elements of the form SΔ_{σ}, where S is an order on X, and σ ∈ Σ_{X}.

Proof. (sketch) (a) Let S ⊇ Δ_{X}, and m ∈ ℕ − \{0\} such that S^{m} = \overline{S}.

• Let Q ⊇ Δ_{X}. Then Q(S − \overline{S}) = QS − Q\overline{S} = (QS − \overline{QS}) − (Q\overline{S} − \overline{Q\overline{S}}) since

\overline{QS} = \overline{Q\overline{S}}. Hence QN_{X} ⊆ N_{X}, and similarly N_{X}Q ⊆ N_{X}.
• Since S and \overline{S} commute, we have
(S − \overline{S})^{m} = ∑_{i=0}^{m}(−1)^{i}\binom{m}{i}S^{m−i}\overline{S}^{i}

= \overline{S} + ∑_{i=1}^{m}(−1)^{i}\binom{m}{i} \underbrace{S^{m−i}\overline{S}}_{\overline{S}}

= ( ∑_{i=0}^{m}(−1)^{i}\binom{m}{i})\overline{S} = 0.

Then N_{X} is a two sided ideal of the k-algebra E_{X}, linearly generated by a finite number of nilpotent elements, so it is a nilpotent ideal of E_{X} (see Lemma 5.1 of [BT16] for details).

(b) By Theorem 3.9, every essential relation R on X can be written R = SΔ_{σ}, where S is reflexive and σ ∈ Σ_{X}. By definition of N_{X}, we have SΔ_{σ} = \overline{S}Δ_{σ} in P_{X}, and \overline{S} = 0 in E_{X} if \overline{S} is not an order, by Remark 3.7. Hence P_{X} is linearly generated by the elements SΔ_{σ}, where S is an order on X, and one checks easily that these elements are linearly independent. □

Theorem 4.2 is particularly useful to describe the simple E_{X}-modules: as N_{X} acts by zero on every such module, the simple E_{X}-modules are actually simple P_{X}-modules.

4.3. A relation R on a finite set X which can be written R = SΔ_{σ}, where S is an order and σ ∈ Σ_{X}, is called a permuted order on X. One can show that this decomposition of R is unique (in other words, if R is a permuted order, there is a unique σ ∈ Σ_{X} such that Δ_{σ} ⊆ R).

In view of Assertion (b) of Theorem 4.2, the algebra P_{X} is called the algebra of permuted orders on X. If S and T are orders on X, and if σ, τ ∈ Σ_{X}, the product SΔ_{σ}T Δ_{τ} in P_{X} is equal to \overline{S.^{σ}T} Δ_{στ} if \overline{S.^{σ}T} is an order, and to 0 otherwise, where σT = Δ_{σ}T Δ_{σ^{−1}}.

In particular P_{X} is Σ_{X}-graded: for σ ∈ Σ_{X}, the degree σ part of P_{X} is the ksubmodule generated by elements SΔ_{σ}, where S is an order on X. The subalgebra P_{1} has a k-basis consisting of the set O_{X} of orders on X. For S, T ∈ O_{X}, the product of ST in P_{1} is equal to \overline{ST} = \overline{S ∪ T} if this is an order, and to 0 otherwise. In particular P_{1} is commutative. Moreover, the group Σ_{X} acts by conjugation on O_{X}, and the algebra P_{X} identifies with the semidirect product P_{1} ⋊ Σ_{X}.

If R ∈ O_{X}, then R^{2} = R in P_{1}. Moreover if R, S ∈ P_{1}, then either RS = 0 in P_{1}, or RS = \overline{R ∪ S} if this is an order. We observe that if we order O_{X} by inclusion of subsets, then RS is either 0 or the least upper bound of R and S in the poset O_{X}. So we have a k-basis O_{X} of idempotents of the commutative algebra P_{1}, which is ordered and contains 1 = Δ_{X}, such that the product of any two of them is either 0 or their supremum in the poset O_{X}. In such a situation, there is a standard procedure to produce a decomposition of the identity as a sum of orthogonal idempotents.

4.4. Notation. For R ∈ O_{X}, let f_{R} be the element of P_{1} defined by

f_{R} = ∑_{\begin{matrix}S∈O_{X} \\ S⊇R \end{matrix}} μ_{O_{X}} (R, S)S,

where μ_{O_{X}} is the Möbius function of the poset O_{X}.

4.5. Theorem. [[BT16] Theorem 6.2]

(a) The elements f_{R}, for R ∈ O_{X}, are orthogonal idempotents of P_{1}, and

∑_{R∈O_{X}} f_{R} = 1.

(b) Moreover P_{1}f_{R} = kf_{R}, for any R ∈ O_{X}.

(c) The algebra P_{1} is isomorphic to the product ∏_{R∈O_{X}} kf_{R} ≅ k^{|O_{X}|}.

4.6. Notation. For R ∈ O_{X}, let Σ_{X,R} denote the stabilizer of R in Σ_{X}, i.e.

Σ_{X,R} = {σ ∈ Σ_{X} | ^{σ}R = R}.

Let moreover e_{R} ∈ P_{1} be the orbit sum

e_{R} = ∑_{σ∈[Σ_{X}/Σ_{X,R}]} f_{^{σ}R}.

We note that the group Σ_{X,R} is isomorphic to the automorphism group Aut(X, R) of the poset (X, R). We will generally identify those two groups.

4.7. Theorem. [[BT16] Lemma 7.4 and Theorem 7.5]

(a) The elements e_{R}, for R in a set [Σ_{X}\O_{X}] of representatives of Σ_{X}-orbits on O_{X}, are central orthogonal idempotents of P_{X}, and ∑_{R∈[Σ_{X}\O_{X}]} e_{R} = 1.

(b) The algebra P_{X} is isomorphic to ∏_{R∈[Σ_{X}\O_{X}]} P_{X}e_{R}.

(c) For R ∈ O_{X}, the algebra P_{X}e_{R} is isomorphic to the full matrix algebra M_{|Σ_{X}:Σ_{X,R}|}(kΣ_{X,R}).

Proof. (sketch) The proof relies on the fact that the set {Δ_{σ}f_{R} | σ ∈ Σ_{X}, R ∈ O_{X}} is a k-basis of P_{X}, and that the product of two of these basis elements is either zero or another element of the basis (see [BT16] for details). □

5. The simple modules for the essential algebra

5.1. In this section we deal with the simple modules for the essential algebra E_{X} and the algebra of permuted orders P_{X} = E_{X}/N_{X} on a finite set X. Theorems 4.2 and 4.7 allow for a description of the simple modules for these algebras.

Recall that Σ_{X} is the group of permutations of X. The group Σ_{X} acts on the set O_{X} of orders on X. For R ∈ O_{X}, we denote by Σ_{X,R} the stabilizer of R in Σ_{X}, and by f_{R} the idempotent associated to R in P_{X} (see Notation 4.6).

5.2. Theorem. [[BT16] Theorem 7.5 and Theorem 8.1] Let X be a finite set.

(a) The surjection E_{X} ↠ P_{X} induces a one to one correspondence between the simple E_{X}-modules and the simple P_{X}-modules.

(b) Let R ∈ O_{X}. Then P_{X}f_{R} has a k-basis {Δ_{σ}f_{R} | σ ∈ Σ_{X}}, so P_{X}f_{R} ≅ kΣ_{X} as a k-module. It is an (R_{X}, kΣ_{X,R})-bimodule, free as a right kΣ_{X,R}- module.

(c) The simple P_{X}-modules (up to isomorphism) are the modules of the form P_{X}f_{R} ⊗_{kΣ_{X,R}} W, where W is a simple kΣ_{R,X}-module (up to isomorphism).

(d) If k is a field with char(k) = 0 or char(k) > |X|, then P_{X} is semisimple, and N_{X} is equal to the Jacobson radical of E_{X}.

Proof. (a) follows from Theorem 4.2. Now (b) and (c) follow from Theorem 4.7, and then (d) follows from the semisimplicity of all the group algebras kΣ_{X,R}, when char(k) = 0 or char(k) > |X|. □

As the essential algebra E_{X} is a quotient of the algebra R_{X} = kC(X, X), we now get a precise description of some simple R_{X}-modules.

5.3. Proposition. [[BT16] Theorem 8.1 and Proposition 8.5] Let R be an order on X. If S ∈ R_{X}, define a k-endomorphism β_{R}(S) of kΣ_{X} by

β_{R}(S) : σ ∈ Σ_{X} ↦ \{ \begin{matrix}τσ & if ∃τ ∈ Σ_{X}, Δ ⊆ Δ_{τ^{−1}}S ⊆ ^{σ}R \\ 0 & if there is no such τ. \end{matrix}

(a) The map β_{R}(S) is well defined, and β_{R}(S) ∈ End_{kΣ_{X,R}}(kΣ_{X}).

(b) The map S ↦ β_{R}(S) extends to an algebra homomorphism from R_{X} to End_{kΣ_{X,R}}(kΣ_{X}), which makes kΣ_{X} a (R_{X}, kΣ_{X,R})-bimodule, isomorphic to P_{X}f_{R}.

(c) For a kΣ_{X,R}-module W, let Λ_{R,W} denote the R_{X}-module P_{X}f_{R} ⊗_{kΣ_{X,R}} W. If W is a simple kΣ_{X,R}-module, then Λ_{R,W} is a simple R_{X}-module.

(d) If (R′, W′) is another pair consisting of an order R′ on X and a simple kΣ_{X,R′}-module W′, then the R_{X}-modules Λ_{R,W} and Λ_{R′,W′} are isomorphic if and only if the pairs (R, W) and (R′, W′) are conjugate by Σ_{X}.

Proof. (sketch) (a) and (b) follow from a precise description of the action of R_{X} on P_{X}f_{R}, using the basis {Δ_{σ}f_{R} | σ ∈ Σ_{X}} of P_{X}f_{R}. Then (c) and (d) follow from Theorem 4.7. □

5.4. Remark. If G is a finite group, a simple kG-module is actually a (k/m)Gmodule, where m is some maximal ideal of k. It follows that when dealing with simple correspondence functors over k, one could always suppose that k is a field.

5.5. Examples. Let k be a field.

• If R = Δ_{X}, then Σ_{X,R} = Σ_{X}, and R_{X} maps surjectively to kΣ_{X}, by S ↦ σ if S = Δ_{σ} for σ ∈ Σ_{X}, and S ↦ 0 is there is no such σ ∈ Σ_{X}.

• If R is a total order, then Σ_{X,R} = {1}, and P_{X}e_{R} ≅ M_{n!}(k) (where n = |X|). In this case kΣ_{X} becomes a simple R_{X}-module.

5.6. Remark. Recall that for an order R on a finite set X, the group Σ_{X,R} is isomorphic to the group Aut(X, R) of automorphisms of the poset (X, R). One may ask which finite groups can occur as automorphism group of some finite poset. The answer is quite simple: every finite group can. This was first proved by Birkhoff ([Bir46]), and later simplified by Thornton ([Tho72]) and Barmak-Minian ([BM09])

6. Correspondence functors

6.1. Definition. Let k be a commutative ring. A correspondence functor over k is a k-representation of the category kC introduced in Definition 3.2. The category of correspondence functors F_{k}(kC, k- Mod) is denoted by F_{k}.

6.2. Remarks. The category kC has the following special important properties:

• The functor sending a finite set to itself and a correspondence to its opposite (introduced in 3.6) induces a k-linear equivalence from kC to the opposite category kC^{op}.

• ([[BT18b] Lemma 3.4] Let X and Y be finite sets such that |X| ≤ |Y |. Let i : X ↪ Y be an injective map, and set

i_{∗} = {(i(x), x) | x ∈ X} ∈ C(Y, X),
i^{∗} = {(x, i(x)) | x ∈ X} ∈ C(X, Y).

Then i^{∗}i_{∗} = Δ_{X}. It follows that if F ∈ F_{k}, then F (i^{∗})F (i_{∗}) = id_{F (X)}, so F (X) is isomorphic to a direct summand of F (Y). In particular F (X) ≠ 0 implies F (Y) ≠ 0.

6.3. Examples.

• Yoneda functors Y_{E,k} : X ↦ kC(X, E), where E is a fixed finite set, e.g.

* E = ∅: then Y_{∅,k}(X) = kC(X, ∅) ≅ k, for any finite set X. The functor Y_{∅,k} is the constant functor with value k.

* E = {•}: then Y_{•,k}(X) = kC(X, •) ≅ k(2^{X}), for any finite set X.

Since Hom_{F_{k}}(Y_{E,k}, M) ≅ M(E) by the Yoneda Lemma, for any M ∈ F_{k}, the functor Y_{E,k} is a projective object of F_{k}, for any E.

• In particular End_{F_{k}}(Y_{E,k}) ≅ kC(E, E). Let R be a preorder on E, i.e. R ∈ C(E, E) such that Δ_{E} ⊆ R = R^{2}. Then Y_{E,k}R : X ↦ kC(X, E)R is a projective object of F_{k}.

6.4. Lemma. [[BT18b] Corollary 3.5 and Corollary 3.6] Let X and Y be finite sets with |X| ≤ |Y |.

(a) The representable functor kC(−, X) is isomorphic to a direct summand of the representable functor kC(−, Y).

(b) The left kC(Y, Y)-module kC(Y, X) is projective.

Proof. (a) In the category kC, the object X is a retract of Y, by Remark 6.2.

(b) In particular kC(Y, X) is isomorphic to a direct summand of the free module kC(Y, Y), so it is projective. □

6.5. Definition. For F ∈ F_{k}, the dual F^{♮} of F is defined by F^{♮}(X) = Hom_{k} (F (X), k) for a finite set X, and by F^{♮}(S) = ^{t}F (S^{op}) for a correspondence S from X to a finite set Y.

6.6. The results of Sections 2 and 5 yield a parametrization of simple correspondence functors, as well as a rough description of their evaluations, which will be enough for stating finiteness properties of correspondence functors in the next section. We will give a more complete description of simple correspondence functors in Section 11.

Let S be a simple correspondence functor (i.e. a simple object of F_{k}). If E is a set of minimal cardinality such that V = S(E) ≠ 0, then by Proposition 2.7 and the comments in 2.8, the functor S is isomorphic to S_{E,V}, and V is a simple module for the essential algebra E_{E}. So there exists a unique pair (R, W) consisting of an order R on E and a simple k Aut(E, R)-module W such that V is isomorphic to the module Λ_{R,W} = P_{E}f_{R} ⊗_{k Aut(E,R)} W of Proposition 5.3.

Conversely, if (E, R, W) is a triple consisting of a finite set E, an order R on E, and a simple k Aut(E, R)-module W, we denote by S_{E,R,W} the simple correspondence functor S_{E,Λ_{R,W}}. The assignment (E, R, W) ↦ S_{E,R,W} is a parametrization of the simple correspondence functors over k.

6.7. Theorem. [[BT18b] Theorem 4.7] Assume that k is a field. The set of isomorphism classes of simple correspondence functors over k is parametrized by the set of isomorphism classes of triples (E, R, W), where E is a finite set, R is an order on E, and W is a simple k Aut(E, R)-module.

6.8. Examples. Let k be a field.

• The constant functor Y_{∅,k} is simple, isomorphic to S_{∅,tot,k}: here tot denotes the unique (total) order on the empty set, and k is the trivial module for the trivial group Aut(∅, tot).

• The Yoneda functor Y_{•,k} is not simple, but splits as a direct sum of the previous functor S_{∅,tot,k} and the simple functor S_{•,tot,k}, where tot is the unique (total) order on a set • of cardinality 1, and k is the trivial module for the trivial group Aut(•, tot).

As the Yoneda functors are projective, the simple functors S_{∅,tot,k} and S_{•,tot,k} are also projective. These are two special cases of Theorem 11.2.

The following result is the first step in the description of simple correspondence functors. It gives lower and upper estimates on the dimension of their evaluations.

6.9. Theorem. [[BT18b] Theorem 8.2] Suppose that k is a field and let S_{E,R,W} be a simple correspondence functor, where E is a finite set, R is an order on E, and W is a simple k Aut(E, R)-module. There exists a positive integer N and a positive real number c such that, for any finite set X of cardinality at least N, we have

c|E|^{|X|} ≤ dim (S_{E,R,W} (X)) ≤ (2^{|E|})^{|X|} .

Proof. (sketch) The main tool is the fact that the simple functor S_{E,R,W} is a quotient of the representable functor kC(−, E). This readily gives the upper bound, since dim_{k} kC(X, E) = 2^{|E||X|} for any finite set X.

The proof of the lower bound is harder. Let A be a set of representatives of the action of the group Σ_{E} on the set of surjections φ : X → E. For φ ∈ A, set

Λ_{φ} = {(x, e) ∈ X × E | (φ(x), e) ∈ R} ∈ C(X, E).

Then one can show that the images under the surjection kC(X, E) → S_{E,R,W} (X) of the elements Λ_{φ}, for φ ∈ A, are linearly independent. The lower bound now follows from an estimate of the cardinality of A (see [BT18b] for details). □

7. Finiteness properties

The notion of finitely generated module over an algebra splits in two different notions in the realm of correspondence functors. Recall that k is a commutative ring, and that F_{k} denotes the category of correspondence functors over k.

7.1. Definition. Let M ∈ F_{k}.

(a) Let (E_{i})_{i∈I} be a family of finite sets, and for each i ∈ I, let m_{i} ∈ M(E_{i}). We say that M is generated by (m_{i})_{i∈I}, and write M = ⟨m_{i}⟩_{i∈I}, if for any finite set X and any m ∈ M(X), there exists a finite subfamily J ⊆ I and elements α_{j} ∈ kC(X, E_{j}), for j ∈ J, such that m = ∑_{j∈J} M(α_{j})(m_{j}).

(b) M is finitely generated if M = ⟨m_{i}⟩_{i∈I}, where I is finite.

(c) M has bounded type if there is a finite set E such that M = ⟨M(E)⟩.

7.2. Examples.

• The Yoneda functor Y_{E,k} is finitely generated (by the single element Δ_{E} of Y_{E,k}(E) = kC(E, E)), for any finite set E.

• When E is a finite set, and V a kC(E, E)-module, the functor L_{E,V} (see Notation 2.3) has bounded type, generated by L_{E,V} (E) ≅ V. It is finitely generated if and only if V is finitely generated.

7.3. Proposition. [[BT18b] Proposition 6.4] Let k be a commutative ring, and M be a correspondence functor over k. The following are equivalent:

(a) M is finitely generated.

(b) M is isomorphic to a quotient of a finite direct sum ⊕_{i=1}^{n} Y_{E_{i},k}.

(c) M is isomorphic to a quotient of a finite direct sum (Y_{E,k})^{⊕n}.

(d) There exists a finite set E and a finite subset B of M(E) such that M is generated by B. In particular M has bounded type.

Proof. (a)⇒(b). If M is generated by the set {m_{i} | i = 1, …, n}, where m_{i} ∈ M(E_{i}), then each m_{i} yields a morphism Y_{E_{i},k} → M, by Yoneda’s lemma. The direct sum of these morphisms is surjective.

(b)⇒(c). If M is a quotient of a finite direct sum ⊕_{i=1}^{n} Y_{E_{i},k}. If E is the largest of

the sets E_{i}, then each Y_{E_{i},k} is a direct summand, hence a quotient, of Y_{E,k}, so M is a quotient of (Y_{E,k})^{⊕n}.

(c)⇒(d). Let M be a quotient of (kC(−, E))^{⊕n}. Since kC(−, E) is generated by Δ_{E} ∈ kC(E, E), the functor M is generated by the images in M(E) of the elements Δ_{E} of each of the n components of the direct sum.

(d)⇒(a). This is obvious. □

7.4. Lemma. [[BT18b] Lemma 9.1] Let k be a field and let M be a finitely generated correspondence functor over k. Then M has a maximal subfunctor.

Proof. Since M is finitely generated, it is generated by M(E) for some finite set E, by Proposition 7.3. Moreover M(E) is a finitely generated R_{E}-module. Let N be a maximal submodule of M(E) as an R_{E}-module. Then M(E)/N is a simple R_{E}-module. By Proposition 2.9, there exist two subfunctors F ⊆ G ⊆ M such that G/F is simple, G(E) = M(E), and F (E) = N. Since M is generated by M(E) and G(E) = M(E), we have G = M. Therefore, F is a maximal subfunctor of M. □

The following result gives a characterization of the finitely generated correspondence functors over a field. It shows that a correspondence functor over a field is finitely generated if and only if it has finite length (i.e. it admits a finite composition series). It should be noted that this equivalence is false in general for other categories of functors (e.g. biset functors).

7.5. Theorem. [[BT18b] Theorem 8.7 and Theorem 9.2] Let k be a field, and M be a correspondence functor over k. The following conditions are equivalent:

(a) M is finitely generated.

(b) there exist positive real numbers a, b, r such that dim_{k} M(X) ≤ ab^{|X|} for any finite set X with |X| ≥ r.

(c) M has finite length.

Proof. (sketch) (a)⇒(b). If M is finitely generated, it is a quotient of a finite direct sum (kC(−, E))^{⊕n}, by Proposition 7.3. Now dim_{k} M(X) ≤ n dim_{k} kC(X, E) = n2^{|X||E|}, for any finite set X, so (b) holds.

The proof that (b) implies (a) is harder. We first use Theorem 6.9 to show that if S_{E,R,W} is a simple subquotient of M, then the cardinality of E is bounded above by the number b appearing in (b). Then one builds a morphism π from a finite direct sum L of representable functors to M, which is surjective on evaluations at any set X of cardinality at most b. If now F is a finite set of minimal cardinality such that Coker π(F) is non-zero, then |F | > b. Moreover Coker π(F) is a non-zero module for the essential algebra E_{F}, hence it admits a simple submodule V. By Proposition 2.9, it follows that Coker π, hence M, admits a simple subquotient isomorphic to S_{F,V}. But then |F | ≤ b, a contradiction proving that π is surjective, and that (b) implies (a). So (a) and (b) are equivalent, and in particular, any subfunctor of a finitely generated correspondence functor over k is finitely generated.

(c)⇒(b). This follows from Theorem 6.9.

(b)⇒(c). By Lemma 7.4, we can build a filtration M = M_{0} ⊃ M_{1} ⊃ M_{2} … in which every subquotient M_{i}/M_{i+1} is simple, isomorphic to S_{E_{i},R_{i},W_{i}} for some triple (E_{i}, R_{i}, W_{i}). Now (b) implies by Theorem 6.9 that |E_{i}| ≤ b for any i. In particular, there is only a finite number of simple quotients S_{E_{i},R_{i},W_{i}} in the filtration, up to isomorphism. But since the dimension of M(X) is finite for any finite set X, each of the simple quotients S_{E_{i},R_{i},W_{i}} can only occur a finite number of times in the filtration. This shows that the filtration is finite, so M has finite length. □

The equivalence of (a) and (c) in Theorem 7.5 has been proved independently by Gitlin [Git18] (for an infinite field k), using results of Wiltshire-Gordon on categories of dimension 0 [WG19].

The following is a consequence of the adjunction of Lemma 2.4.

7.6. Proposition. [[BT18b] Lemma 7.3] Let M be a correspondence functor over k, and E be a finite set.

(a) If M is projective in F_{k}, and M is generated by M(E), then M ≅ L_{F,M(F)} for any finite set F with |F | ≥ |E|, and M(F) is a projective R_{F} -module.

(b) The functor L_{E,V} is projective (resp. indecomposable) if and only if V is a projective (resp. indecomposable) R_{E}-module.

We introduce next the notion of residue of a correspondence functor at a finite set, which is an important tool to study finiteness conditions.

7.7. Definition. Let M be a correspondence functor over k, and E be a finite set. The residue of M at E is the k-module defined by

\overline{M}(E) = M(E)/ ∑_{|F |<|E|} kC(E, F)M(F).

7.8. Theorem. [[BT18b] Theorem 11.4 and Corollary 11.5] Let k be a commutative noetherian ring. Let M be a subfunctor of a correspondence functor L over k, and let E and F be finite sets.

(a) If L is generated by L(F) and \overline{M}(E) ≠ 0, then |E| ≤ 2^{|F |}.

(b) If L is generated by L(F) and |E| ≥ 2^{|F |}, then M is generated by M(E).

(c) If L has bounded type, then M has bounded type.

(d) If L is finitely generated, then M is finitely generated.

Proof. (sketch) (a) is proved by localization and Artin-Rees Lemma (Theorem 8.5 in [Mat89]). Then (b), (c), and (d) follow easily. □

7.9. Corollary. Functors of bounded type form an abelian subcategory F_{k}^{b} of F_{k}. Finitely generated functors form an abelian subcategory F_{k}^{f} of F_{k}^{b}.

7.10. Proposition. [[BT18b] Proposition 6.6] Let k be a noetherian ring.

(a) For any a finitely generated correspondence functor M over k, the algebra End_{F_{k}}(M) is a finitely generated k-module.

(b) For any two finitely generated correspondence functors M and N over k, the k-module Hom_{F_{k}}(M, N) is finitely generated.

(c) If k is a field, then the Krull-Remak-Schmidt theorem holds for finitely generated correspondence functors over k.

Proof. (a) M is a quotient of a projective functor ⊕_{i=1}^{n} kC(−, E), so End_{F_{k}}(M) is a

quotient of a k-submodule of the finitely generated k-module M_{n}(kC(E, E)).

(b) Hom_{F_{k}}(M, N) is a direct summand of End_{F_{k}}(M ⊕ N).

(c) Splitting M ∈ F_{k} amounts to splitting the identity as a sum of orthogonal idempotents in the finite dimensional k-algebra End_{F_{k}}(M). □

The following three results show that when k is a field, the category F_{k}^{f} shares many properties of the category of modules over a finite group algebra.

7.11. Theorem. [[BT18b] Theorem 10.2 and Corollary 10.3] Let E be a finite set.

(a) The representable functor Y_{E,k} = kC(−, E) is isomorphic to its dual.

(b) Let R_{E} = kC(E, E) be the algebra of relations on E. Then R_{E} is a symmetric k-algebra, in the sense of [Bro09]. More precisely, let t_{E} : R_{E} → k be defined by

∀R ∈ C(E, E), t_{E}(R) = \{ \begin{matrix}1 & if R ∩ Δ_{E} = ∅, \\ 0 & otherwise. \end{matrix}

Then t_{E} is a symmetrizing form for R_{E}.

(c) If k is a field (or more generally if k is self injective), any finitely generated projective correspondence functor over k is also injective. In particular F_{k}^{f} has infinite global dimension.

Proof. (b) Let R, S ∈ C(E, E). Then t_{E}(RS) = 1 ⇔ R ⊆ (E×E)−S^{op}. The matrix (t_{E}(RS))_{R,S∈C(E,E)} is the product of a permutation matrix (S ↦ (E × E) − S^{op}) with the matrix of an order (⊆), hence it is invertible (over ℤ).

(a) follows from a similar argument, and (c) is an easy consequence of (a). □

7.12. Theorem. [[BT18b] Theorem 10.6] Let k be a field, and M be a finitely generated correspondence functor over k. The following are equivalent:

(a) M is projective and indecomposable.

(b) M is projective and admits a unique maximal proper subfunctor.

(c) M is projective and admits a unique minimal non-zero subfunctor.

(d) M is injective and indecomposable.

(e) M is injective and admits a unique maximal proper subfunctor.

(f) M is injective and admits a unique minimal non-zero subfunctor.

Proof. We first note that if M is finitely generated, it has finite length by Theorem 7.5, hence (if it is non zero) it admits a maximal subfunctor and a minimal subfunctor. (a)⇒(b). If M is projective and indecomposable, and generated by its evaluation at some finite set E, we can assume M = L_{E,V}, where V is an indecomposable projective R_{E}-module, by Proposition 7.6. Since R_{E} is a finite dimensional kalgebra, the module V has a unique maximal submodule W. If N is a subfunctor of M, then N(E) is a submodule of M(E) = V. If N(E) = V, then N = M, as M is generated by M(E) = V. Hence N(E) ⊆ W if N ≠ M. So if N and N′ are distinct maximal subfunctors of M, then N + N′ = M, which implies N(E) + N′(E) = V, a contradiction since N(E) and N′(E) are both contained in W. (b)⇒(a). If M has a unique maximal subfunctor and M = M_{1} ⊕ M_{2} for non zero subfunctors M_{1} and M_{2}, then M_{1} and M_{2} are finitely generated by Theorem 7.5, so admit maximal subfunctors N_{1} and N_{2}, respectively. Then M_{1} ⊕ N_{2} and N_{1} ⊕ M_{2} are distinct maximal subfunctors of M. (a)⇒(d). If M is a finitely generated indecomposable projective functor, then M is injective (and indecomposable) by Theorem 7.11. (d)⇒(a). If M is finitely generated and injective, then M^{♮} is projective and finitely generated (as M and M^{♮} both have finite length), hence injective, so M ≅ (M^{♮})^{♮} is projective. (a)⇒(c). For a finitely generated functor M, the duality between M and M^{♮} induces an order reversing bijection between the subfunctors of M and the subfunctors of M^{♮}. If M is projective and indecomposable, then so is M^{♮}, that is, (a) holds for M^{♮}. Thus (b) holds for M^{♮} and the functor M^{♮} has a unique maximal subfunctor. Hence M has a unique minimal subfunctor. (c)⇒(a). If M is projective and admits a unique minimal subfunctor, then M is also injective, and its dual M^{♮} is projective and admits a unique maximal subfunctor. Hence M^{♮} is indecomposable, so M is indecomposable.

It is now clear that (e) and (f) are both equivalent to (a), (b), (c) and (d). □

7.13. Theorem. [[BT18b] Theorem 10.7] Let k be a field.

(a) Let M be a finitely generated projective correspondence functor. Then

M/ Rad(M) ≅ Soc(M).

(b) Let M and N be finitely generated correspondence functors over k. If M is projective, then

dim_{k} Hom_{F_{k}}(M, N) = dim_{k} Hom_{F_{k}}(N, M) < +∞.

Proof. (sketch) The proof is a generalization of the proof of the similar result for modules over a symmetric algebra ([Ben91] Theorem 1.6.3). It relies mainly on Theorem 7.11 (see [BT18b] for details). □

8. Stability

When k is noetherian, the Hom-sets and more generally the Ext-groups from correspondence functors of bounded type over k to arbitrary correspondence functors over k are detected on their evaluations at large enough finite sets. More precisely:

8.1. Theorem. [[BT18b] Theorem 12.3] Let k be a noetherian ring, let M, N ∈ F_{k}, and let E, F be finite sets.

(a) If M is generated by M(E), then for |F | ≥ 2^{|E|}, the evaluation map

Hom_{F_{k}}(M, N) → Hom_{R_{F}} (M(F), N(F))

is an isomorphism.

(b) If M has bounded type, then for any i ∈ ℕ, there exists n_{i} ∈ ℕ such that if |F | ≥ n_{i}, the map

Ext_{F_{k}}^{i}(M, N) → Ext_{R_{F}}^{i} (M(F), N(F))

is an isomorphism.

When k is noetherian, this leads to the following alternative description of F_{k}^{b}, up to equivalence of categories.

8.2. Definition. Let G_{k} be the following category:

• the objects of G_{k} are pairs (E, U), where E is a finite set, and U is an R_{E}-module.

• a morphism (E, U) → (F, V) in G_{k} is a morphism of R_{E}-modules

U → kC(E, F) ⊗_{R_{F}} V.

• the composition in G_{k} of f : (E, U) → (F, V) and g : (F, V) → (G, W) given respectively by

f : U → kC(E, F) ⊗_{R_{F}} V and g : V → kC(F, G) ⊗_{R_{G}} W

is the morphism (E, U) → (G, W) given by the composition

\xymatrix{U \ar[r]^{f} & kC(E, F) ⊗_{R_{F}} V \ar[r]^{h} & kC(E, F) ⊗_{R_{F}} kC(F, G) ⊗_{R_{G}} W \ar[r]^{l} & kC(E, G) ⊗_{R_{G}} W}

where \{ \begin{matrix}h & = & id_{kC(E,F)} ⊗_{R_{F}} g \\ l & = & μ ⊗_{R_{G}} id_{W} \end{matrix} , and μ : kC(E, F)⊗_{R_{F}} kC(F, G) → kC(E, G)

is the composition in kC.

• the identity morphism of (E, U) is U →^{≅} kC(E, E) ⊗_{R_{E}} U.

8.3. Theorem. [[BT18b] Theorem 12.7]

(a) The assignment (E, U) ↦ L_{E,U} is a fully faithful k-linear functor G_{k} → F_{k}^{b}.

(b) When k is noetherian, it is an equivalence of categories. In particular G_{k} is abelian.

9. Correspondence functors and lattices

9.1. In this section, we consider finite lattices, and build important examples of correspondence functors from them. Recall that a lattice (T, ∨, ∧) is a poset in which any pair {x, y} of elements admits a least upper bound x ∨ y, called the join of x and y, and a largest lower bound x ∧ y, called the meet of x and y.

If T is a lattice, and T^{op} is the opposite poset, then (T^{op}, ∧, ∨) is a lattice. A lattice T is called distributive if x ∧(y ∨ z) = (x ∧ y) ∨(x ∧ z) for any x, y, and z in T. One can show that T is distributive if and only if T^{op} is, that is, if x ∨(y ∧ z) = (x ∨ y) ∧(x ∨ z) for any x, y, and z in T.

A finite lattice T always admits a largest element (the join of all elements of T), denoted by 1_{T}, and a smallest element (the meet of all elements of T), denoted by 0_{T}.

9.2. Notation. Let T be a finite lattice.

• For a finite set X, we denote by F_{T} (X) = k(T^{X}) the free k-module with basis the set T^{X} of all maps from X to T.

• For a finite set Y and a correspondence S ∈ C(Y, X), we define a k-linear map F_{T} (S) : F_{T} (X) → F_{T} (Y) by sending φ : X → T to Sφ : Y → T defined by

∀y ∈ Y, (Sφ)(y) = ⋁_{(y,x)∈S} φ(x).

9.3. Theorem. [[BT19a] Proposition 4.2 and Theorem 4.12] Let k be a commutative ring, and T be finite lattice.

(a) F_{T} is a correspondence functor over k.

(b) F_{T} is projective in F_{k} if and only if T is distributive.

In order to study the functorial aspects of the construction T ↦ F_{T}, we introduce the following category L and its k-linearization (see Definition 2.1):

9.4. Definition.

• Let T and T′ be finite lattices. A map f : T → T′ is called a join morphism if f( ⋁_{t∈A} t) = ⋁_{t∈A} f(t), for any subset A of T.

• Let L denote the following category:

– the objects of L are the finite lattices.

– for finite lattices T and T′, the set Hom_{L}(T, T′) is the set of join morphisms from T to T′.

– the composition of morphisms in L is the composition of maps, and the identity morphism of a finite lattice T is the identity map of T.

• Let kL be the k-linearization of L.

Note that for finite lattices T and T′, a join morphism f : T → T′ always maps 0_{T} to 0_{T′} (this follows from the case A = ∅ in the definition). Conversely, if f is a map from T to T′ such that f(0_{T}) = 0_{T′} and f(a ∨ b) = f(a) ∨ f(b) for any a and b in T, then f is a join morphism.

For our next theorem, we need some notation. Let f : T → T′ be a morphism in the category L. For a finite set X, let F_{f,X} : F_{T} (X) → F_{T′}(X) be the k-linear map sending the function φ : X → T to the function f ∘ φ : X → T′.

9.5. Theorem. [[BT19a] Theorem 4.8]

(a) Let f : T → T′ be a morphism in the category L. Then the collection of maps F_{f,X} : F_{T} (X) → F_{T′}(X), for all finite sets X, yields a natural transformation F_{f} : F_{T} → F_{T′} of correspondence functors.

(b) The assignment sending a lattice T to F_{T}, and a morphism f : T → T′ in L to F_{f} : F_{T} → F_{T′}, yields a functor L → F_{k}. This functor extends uniquely to a k-linear functor

F_{?} : kL ⟶ F_{k} .

(c) The functor F_{?} is fully faithful.

The functor F_{?} is also well behaved with the duality F ↦ F^{♮} of functors introduced in Definition 6.5. To state this, we need the following notation:

9.6. Notation. For a morphism f : T → T′ in L, let f^{op} : T′ → T be the map defined by

∀t′ ∈ T′, f^{op}(t′) = ⋁_{\begin{matrix}x∈T \\ f(x)≤t′ \end{matrix}} x,

where the join is taken in T.

9.7. Theorem. [[BT19a] Lemma 8.1 and Theorem 8.9]

(a) Let T and T′ be finite lattices. If f : T → T′ is a morphism in L, then f^{op} : T′^{op} → T^{op} is a morphism in L.

(b) The assignment T ↦ T^{op} extends to an equivalence L → L^{op} and a k-linear equivalence kL → kL^{op}.

(c) The functors T ↦ (F_{T})^{♮} and T ↦ F_{T^{op}} from kL to F_{k}^{op} are naturally isomorphic.

10. Fundamental functors

10.1. Let (E, R) be a finite poset. In Proposition 5.3, we have introduced, for any k Aut(E, R)-module W, an R_{E}-module Λ_{R,W} = P_{E}f_{R} ⊗_{k Aut(E,R)} W. So far we have used this construction only in the case where W is simple, in order to parametrize the simple correspondence functors over k, by setting S_{E,R,W} = S_{E,Λ_{R,W}}, where S_{E,Λ_{R,W}} is the functor S_{X,V} introduced in Notation 2.6, in the case of the object X = E of the category D = C, and the kD(X, X) = R_{E}-module V = Λ_{R,W}.

We will now consider the correspondence functor S_{E,Λ_{R,W}} over k associated to the free module W = k Aut(E, R). Then Λ_{R,W} = P_{E}f_{R} ⊗_{k Aut(E,R)} k Aut(E, R) ≅ P_{E}f_{R}.

10.2. Definition. Let (E, R) be a finite poset. The fundamental correspondence functor over k associated to (E, R) is the functor

𝕊_{E,R} = S_{E,P_{E}f_{R}}.

We will see that the fundamental functors associated to finite posets allow for a precise description of all the simple correspondence functors.

Our first observation is that 𝕊_{E,R} is by definition a quotient of the functor L_{E,P_{E}f_{R}} = kC(−, E) ⊗_{R_{E}} P_{E}f_{R}, which is itself a quotient of the representable functor kC(−, E), since L_{E,P_{E}f_{R}} is generated by the element Δ_{E} ⊗_{R_{E}} f_{R} of its evaluation L_{E,P_{E}f_{R}}(E) = kC(E, E) ⊗_{R_{E}} P_{E}f_{R} ≅ P_{E}f_{R}.

Since R = ∑_{\begin{matrix}S∈O_{E} \\ S⊇R \end{matrix}} f_{S} in P_{E} by definition of the idempotents f_{S}, we have Rf_{R} = f_{R}

in P_{E}. Thus R(Δ_{E} ⊗_{R_{E}} f_{R}) = R ⊗_{R_{E}} f_{R} = Δ_{E} ⊗_{R_{E}} Rf_{R} = Δ_{E} ⊗_{R_{E}} f_{R}, and it follows that the direct summand kC(−, E)R of kC(−, E) maps surjectively onto 𝕊_{E,R}, so we get a canonical surjective morphism

π_{E,R} : kC(−, E)R ↠ 𝕊_{E,R}.

Before going further, we need to recall some classical definitions and results on finite lattices.

10.3. Definition.

• Let T be a finite lattice. An element e of T is called join-irreducible if whenever e can be written e = ⋁_{a∈A} a for some subset A of T, then e ∈ A.

We denote by Irr(T) the set of join-irreducible elements of T, viewed as a full subposet of T.

• Let (E, R) be a finite poset. For e ∈ E, set

]., e]_{E,R} = R_{e} = {x ∈ E | (x, e) ∈ R}.

A lower ideal of (E, R) is a closed downwards subset of E, i.e. a subset A such that ]., x]_{E,R} ⊆ A whenever x ∈ A. Let I_{↓}(E, R) be the set of lower ideals of (E, R), ordered by inclusion of subsets.

The poset I_{↓}(E, R) is a distributive lattice, the join operation being union of subsets, and the meet operation being intersection of subsets. It is easily seen moreover that

Irr(I_{↓}(E, R)) = {]., e]_{E,R} | e ∈ E}.

The map e ∈ E ↦]., e]_{E,R} is an isomorphism of posets from (E, R) to Irr(I_{↓}(E, R)). We will freely abuse notation and identify these two posets.

When T is a finite lattice, and (E, R) = Irr(T), the map

s_{T} : A ∈ I_{↓}(E, R) ↦ ⋁_{a∈A} a ∈ T

is a surjective join-morphism of lattices. By standard theorems (see [Sta12] Theorem 3.4.1 and Proposition 3.4.2, and also [Rom08] Theorem 6.2), it is a bijection if and only if T is distributive, and then it is an isomorphism of lattices.

10.4. Proposition. [[BT19a] Proposition 4.5 and Theorem 6.5] Let T be a finite lattice, and (E, R) = Irr(T).

(a) There is a canonical isomorphism of functors F_{I_{↓}(E,R)} ≅ kC(−, E)R^{op}.

(b) The morphism \xymatrix{F_{I_{↓}(E,R)} ≅ kC(−, E)R^{op} \ar@{->>}[r]^{π_{R,T}} & 𝕊_{E,R^{op}}} factors as

\xymatrix{F_{I_{↓}(E,R)} \ar@{->>}[r]^{F_{s_{T}}} & F_{T} \ar@{->>}[r]^{Θ_{T}} & 𝕊_{E,R^{op}}.}

10.5. Definition. Let T be a finite lattice, and (E, R) = Irr(T).

• For t ∈ T, let r(t) = ⋁_{\begin{matrix}e∈E \\ e<t \end{matrix}} e and σ(t) = ⋀_{\begin{matrix}e∈E \\ e>t \end{matrix}} e. Define inductively r^{n}(t) and

σ^{n}(t) by r^{n}(t) = r(r^{n−1}(t)) and σ^{n}(t) = σ(σ^{n−1}(t)).

Then t ≥ r(t) ≥ … ≥ r^{n}(t) = r^{n+1}(t) for some n. Set r^{∞}(t) = r^{n}(t). Similarly t ≤ σ(t) ≤ … σ^{m}(t) = σ^{m+1}(t) for some m. Set σ^{∞}(t) = σ^{m}(t).

• Let G_{T} = E ⊔ {t ∈ T | t = r^{∞}σ^{∞}(t)}, and G(E, R) = G_{I_{↓}(E,R)}.

Note that the union in the definition of G_{T} is disjoint because r(t) < t if (and only if) t ∈ E.

10.6. Theorem. [[BT18a] Theorem 5.6] Let (E, R) be a finite poset, and T be a finite lattice such that Irr(T) ≅ (E, R).

(a) Let \overline{G}(E, R) denote the image of G(E, R) by \xymatrix{s_{T} : I_{↓}(E, R) \ar@{->>}[r] & T} .

• The restriction of the map s_{T} to G(E, R) is an isomorphism of posets G(E, R) → \overline{G}(E, R). Moreover \overline{G}(E, R) = G_{T}. In particular G_{T} only depends on the poset Irr(T), up to isomorphism.

• For any finite set X, the set

\{φ : X → T | E ⊆ φ(X) ⊆ \overline{G}(E, R)\} ⊆ F_{T} (X)

is mapped by Θ_{T,X} : F_{T} (X) → 𝕊_{E,R^{op}}(X) to a k-basis of 𝕊_{E,R^{op}}(X).

(b) For any finite set X, the k-module 𝕊_{E,R}(X) is free of rank

rk_{k} 𝕊_{E,R}(X) = ∑_{i=0}^{e}(−1)^{i}\binom{e}{i}(g − i)^{|X|},

where e = |E| and g = |G(E, R)|.

10.7. Examples. (The black nodes of I_{↓}(E, R) are the join-irreducible elements)

\begin{matrix}(E, R) & I_{↓}(E, R) & G(E, R) \\ [figure: •; •; •; •] & [figure: ∘; •; ∘; ∘; •; •; •; ∘] & [figure: •; •; ·; ·; •; •; •; •] \end{matrix}

rk_{k}𝕊_{E,R}(X) = 6^{x} − 4.5^{x} + 6.4^{x} − 4.3^{x} + 2^{x}, where x = |X|.

\begin{matrix}(E, R) & I_{↓}(E, R) & G(E, R) \\ [figure: •; •; •] & [figure: •; ∘; •; •; ∘] & [figure: •; •; •; •; •] \end{matrix}

rk_{k}𝕊_{E,R}(X) = 5^{x} − 3.4^{x} + 3.3^{x} − 2^{x}, where x = |X|.

11. The simple correspondence functors

11.1. Theorem. [[BT18a] Theorem 6.6 and Theorem 6.10] Let (E, R) be a finite poset, and X be a finite set.

(a) 𝕊_{E,R}(X) is a free right k Aut(E, R)-module.

(b) Let k be a field, and W be a simple k Aut(E, R)-module. Then

S_{E,R,W} (X) ≅ 𝕊_{E,R}(X) ⊗_{k Aut(E,R)} W.

In particular

dim_{k} S_{E,R,W} (X) = \frac{dim_{k} W}{| Aut(E, R)|} ∑_{i=0}^{e}(−1)^{i}\binom{e}{i}(g − i)^{|X|},

where e = |E| and g = |G(E, R)|.

In the case of a totally ordered poset, the previous result takes the following form. Let n ∈ ℕ. Set \underline{n} = \{0 < 1 < … < n\}, and [n] = Irr(\underline{n}) = \underline{n}−\{0\}. Set 𝕊_{n} = 𝕊_{[n],tot}, where tot is the natural total order on [n]. Observe that ([n], tot) ≅ ([n], tot^{op})

11.2. Theorem. [[BT19a] Proposition 10.2, Theorem 11.1, Theorem 11.6 and Theorem 11.8]

(a) The surjection F\underline{n} → 𝕊_{n} splits. The functor 𝕊_{n} is projective.

(b) If X is a finite set, then 𝕊_{n}(X) is a free k-module of rank

∑_{i=0}^{n}(−1)^{n−i}\binom{n}{i}(i + 1)^{|X|}.

(c) F\underline{n} ≅ ⨁_{A⊆[n]} 𝕊_{|A|} ≅ ⨁_{j=0}^{n}(𝕊_{j})^{⊕\binom{n}{j}}.

(d) End_{kL}(\underline{n}) ≅ End_{F_{k}}(F\underline{n}) ≅ ∏_{j=0}^{n} M\binom{n}{j}(k).

(e) If k is a field, then 𝕊_{n} is simple (and projective, and injective), isomorphic to S_{[n],tot,k}.

The case of a total order raises the question of determining all simple projective correspondence functors. The answer is as follows.

11.3. Definition.

• If X and Y are posets, let X ∗Y denote the set X ⊔Y, ordered by the orders of X and Y, and moreover x ≤ y for x ∈ X and y ∈ Y.

• A pole poset is a poset of the form E_{1} ∗ E_{2} ∗ … E_{n}, where E_{i} is a set of cardinality 1 or 2, ordered by equality, for i = 1, …, n.

11.4. Theorem. [[BT19b] Theorem 4.5] Let k be a field, and S_{E,R,W} be a simple correspondence functor, where (E, R) is a finite poset, and W is a simple k Aut(E, R)-module. The following conditions are equivalent:

(a) S_{E,R,W} is projective.

(b) (E, R) is a pole poset, and W is a projective k Aut(E, R)-module.

(c) Either (E, R) is totally ordered or (E, R) is a pole poset and char(k) ≠ 2.

11.5. Examples. [[BT18a] Example 8.9 and Example 8.10]

• Let D be the following lattice:

D = [figure: ∘; •; •; •; ∘]

One can show that the functor F_{D} splits as

F_{D} ≅ 𝕊_{0} ⊕ 4𝕊_{1} ⊕ 4𝕊_{2} ⊕ 𝕊_{3} ⊕ 2𝕊_{••} ⊕ 𝕊_{•} {• \atop •} ,

where •• is a set of cardinality 2, ordered by equality, and • _{•}^{•} is a poset of cardinality 3 with 2 connected components.

In particular, when k is a field of characteristic different from 2, the functor F_{D} is semisimple. Since D is not distributive, the functor F_{D} is not projective, by Theorem 9.3. The only non projective direct summand in the above decomposition is 𝕊_{•} {• \atop •}.

• Let T be the following lattice :

T = [figure: •; ∘; ∘; ∘; •]

One can show that F_{T} splits as

F_{T} ≅ 𝕊_{0} ⊕ 4𝕊_{1} ⊕ 3𝕊_{2} ⊕ 3𝕊_{••} ⊕ 𝕊_{•••} ,

where ••• is a set of cardinality 3 ordered by equality. All the summands in this decomposition of F_{T}, except possibly 𝕊_{•••}, are projective functors. Since the lattice T is not distributive, the functor F_{T} is not projective, thus 𝕊_{•••} is actually not projective either.

11.6. Remark. The sequence of multiplicities of 𝕊_{n} as a direct summand of F_{D} is 1, 4, 4, 1, 0 for n = 0, 1, 2, 3, 4, and the number of chains 0_{D} = x_{0} < x_{1} < … < x_{n} in D is equal to 1, 4, 4, 1, 0 for n = 0, 1, 2, 3, 4. Similarly, the sequence of multiplicities of 𝕊_{n} as a direct summand of F_{T} is 1, 4, 3, 0 for n = 0, 1, 2, 3, and the number of chains 0_{T} = x_{0} < x_{1} < … < x_{n} in T is equal to 1, 4, 3, 0 for n = 0, 1, 2, 3. This is not a coincidence… (see [BT19a] Section 10 and Section 11 for details).

11.7. Theorem. [[BT18a] Theorem 7.1 and Theorem 7.2] Let X be a finite set, and R_{X} = kC(X, X), where k is a field.

(a) The set of isomorphism classes of simple R_{X}-modules is parametrized by the set of isomorphism classes of triples (E, R, W), where E is a finite set with |E| ≤ |X|, R is an order relation on E, and W is a simple k Aut(E, R)- module.

(b) The simple R_{X}-module parametrized by the triple (E, R, W) is S_{E,R,W} (X).

(c) In particular, the dimension of this simple module is equal to

dim_{k} S_{E,R,W} (X) = \frac{dim_{k} W}{| Aut(E, R)|} ∑_{i=0}^{|E|}(−1)^{i}\binom{|E|}{i}(|G(E, R)| − i)^{|X|}.

11.8. Corollary. [[BT18a] Theorem 7.4] Let k be a field of characteristic 0. Let X be a finite set, and J(R_{X}) denote the Jacobson radical of R_{X} = kC(X, X). Set n = |X|. Then

dim_{k} J(R_{X}) = 2^{n^{2}} − ∑_{e=0}^{n} ∑_{R} \frac{1}{| Aut(E, R)|}( ∑_{i=0}^{e}(−1)^{i}\binom{e}{i}(|G(E, R)| − i)^{n})^{2},

where R runs through a set of Σ_{E}-conjugacy classes of order relations on E = {1, …, e}, and E = ∅ if e = 0. For small values of n, the dimension of J(R_{X}) is given in the following table. For n ≤ 2, this dimension is 0, so the algebra kR_{X} is semisimple. For n = 3, the dimension of J(R_{X}) is 42, and follows from a computer calculation in [Bre14]. This value can be confirmed by hand using the above formula. This value has also been confirmed by a direct computation using the computer software GAP [GAP15]. For n ≥ 4, a direct computation using the algebra R_{X} is not possible on current computers, because the dimension 2^{n^{2}} of this algebra is too big. The table below has been completed via a computer calculation using GAP and the above formula.

\begin{matrix}n & dim_{k} J(R_{X}) \\ ≤ 2 & 0 \\ 3 & 42 \\ 4 & 32, 616 \\ 5 & 29, 446, 050 \\ 6 & 67, 860, 904, 320 \\ 7 & 562, 649, 705, 679, 642 \\ 8 & 18, 446, 568, 932, 288, 588, 616 \end{matrix}

References

[Ben91] D. J. Benson. Representations and cohomology. I, volume 30 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1991. Basic representation theory of finite groups and associative algebras.

[Bir46] Garrett Birkhoff. On groups of automorphisms. Revista Unión Mat. Argentina, 11:155– 157, 1946.

[BM09] Jonathan Ariel Barmak and Elias Gabriel Minian. Automorphism groups of finite posets. Discrete Math., 309(10):3424–3426, 2009.

[Bou96] Serge Bouc. Foncteurs d’ensembles munis d’une double action. J. Algebra, 183(3):664– 736, 1996.

[Bre14] Murray R. Bremner. Structure of the rational monoid algebra for Boolean matrices of order 3. Linear Algebra Appl., 449:381–401, 2014.

[Bro09] Michel Broué. Higman’s criterion revisited. Michigan Math. J., 58(1):125–179, 2009.

[BST13] Serge Bouc, Radu Stancu, and Jacques Thévenaz. Simple biset functors and double Burnside ring. J. Pure Appl. Algebra, 217(3):546–566, 2013.

[BT16] Serge Bouc and Jacques Thévenaz. The algebra of essential relations on a finite set. J. Reine Angew. Math., 712:225–250, 2016.

[BT18a] Serge Bouc and Jacques Thévenaz. The algebra of Boolean matrices, correspondence functors, and simplicity. J. Comb. Algebra, 4 (2020), 215–267.

[BT18b] Serge Bouc and Jacques Thévenaz. Correspondence functors and finiteness conditions. J. Algebra, 495:150–198, 2018.

[BT19a] Serge Bouc and Jacques Thévenaz. Correspondence functors and lattices. J. Algebra, 518:453–518, 2019.

[BT19b] Serge Bouc and Jacques Thévenaz. Simple and projective correspondence functors. Preprint, 2019. arXiv:1902.09816.

[CEF15] Thomas Church, Jordan S. Ellenberg, and Benson Farb. FI-modules and stability for representations of symmetric groups. Duke Math. J., 164(9):1833–1910, 2015.

[GAP15] The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.7.8, 2015.

(http://www.gap-system.org).

[Git18] Andrew Gitlin. New examples of dimension zero categories. J. Algebra, 505:271–278, 2018.

[Hal35] Philip Hall. On representatives of subsets. J. London Math. Soc., 10:26–30, 1935.

[Hal86] Marshall Hall, Jr. Combinatorial theory. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Inc., New York, second edition, 1986. A Wiley-Interscience Publication.

[HY14] Akihiko Hida and Nobuaki Yagita. Representations of the double Burnside algebra and cohomology of the extraspecial p-group. J. Algebra, 409:265–319, 2014.

[Kim82] Ki Hang Kim. Boolean matrix theory and applications, volume 70 of Monographs and Textbooks in Pure and Applied Mathematics. Marcel Dekker, Inc., New York, 1982. With a foreword by Gian-Carlo Rota.

[Mat89] Hideyuki Matsumura. Commutative ring theory, volume 8 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 1989. Translated from the Japanese by M. Reid.

[Pir00] Teimuraz Pirashvili. Dold-Kan type theorem for Γ-groups. Math. Ann., 318(2):277–298, 2000.

[PS17] Andrew Putman and Steven V. Sam. Representation stability and finite linear groups. Duke Math. J., 166(13):2521–2598, 2017.

[Rom08] Steven Roman. Lattices and ordered sets. Springer, New York, 2008.

[Sta12] Richard P. Stanley. Enumerative combinatorics. Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2012.

[Tho72] M. C. Thornton. Spaces with given homeomorphism groups. Proc. Amer. Math. Soc., 33:127–131, 1972.

[WG19] John D. Wiltshire-Gordon. Categories of dimension zero. Proc. Amer. Math. Soc., 147(1):35–50, 2019.

Serge Bouc, CNRS-LAMFA, Université de Picardie - Jules Verne, 33, rue St Leu, F-80039 Amiens Cedex 1, France.

serge.bouc@u-picardie.fr