CORRESPONDENCE FUNCTORS AND FINITENESS CONDITIONS

SERGE BOUC AND JACQUES THÉVENAZ

Abstract. We investigate the representation theory of finite sets. The correspondence functors are the functors from the category of finite sets and correspondences to the category of k-modules, where k is a commutative ring. They have various specific properties which do not hold for other types of functors. In particular, if k is a field and if F is a correspondence functor, then F is finitely generated if and only if the dimension of F (X) grows exponentially in terms of the cardinality of the finite set X. Moreover, in such a case, F has actually finite length. Also, if k is noetherian, then any subfunctor of a finitely generated functor is finitely generated.

1. Introduction

Representations of categories have been used by many authors in different contexts. The present paper is the first in a series which develops the theory in the case of the category whose objects are all finite sets and morphisms are all correspondences between finite sets.

For representing a category of finite sets, there are several possible choices. Pirashvili [Pi] treats the case of pointed sets and maps, while Church, Ellenberg and Farb [CEF] consider the case where the morphisms are all injective maps. Putman and Sam [PS] use all k-linear splittable injections between finite-rank free k-modules (where k is a commutative ring). Here, we move away from such choices by using all correspondences as morphisms. The cited papers are concerned with applications to cohomological stability, while we develop our theory without any specific application in mind. The main motivation is provided by the fact that finite sets are basic objects in mathematics. Moreover, the theory turns out to have many quite surprising results, which justify the development presented here.

Let C be the category of finite sets and correspondences. We define a correspondence functor over a commutative ring k to be a functor from C to the category k-Mod of all k-modules. As much as possible, we develop the theory for an arbitrary commutative ring k. However, let us start with the case when k is a field. If F is a correspondence functor over a field k, we prove that F is finitely generated if and only if the dimension of F (X) grows exponentially in terms of the cardinality of the finite set X (Theorem 8.7). In such a case, we also prove the striking fact that F has finite length (Theorem 9.2). This result was obtained independently by Gitlin [Gi] (for a field k of characteristic zero, or algebraically closed), using a criterion proved by Wiltshire-Gordon [WG]. Moreover, for finitely generated correspondence functors, we show that the Krull-Remak-Schmidt theorem holds (Proposition 6.6) and that projective functors coincide with injective functors (Theorem 10.6).

Date: November 6, 2017.

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.

Suppose that k is a field. By well-known results about representations of categories, simple correspondence functors can be classified. In our case, they are parametrized by triples (E, R, V), where E is a finite set, R is a partial order relation on E, and V is a simple k Aut(E, R)-module (Theorem 4.7). This is the first indication of the importance of posets in our work. However, if S_{E,R,V} is the simple functor parametrized by (E, R, V), then it is quite hard to describe the evaluation S_{E,R,V} (X) at a finite set X. We will achieve this in a future paper [BT3] by giving a closed formula for its dimension.

A natural question when dealing with a commutative ring k is to obtain specific results when k is noetherian. We follow this track in Section 11 and show for instance that any subfunctor of a finitely generated correspondence functor is again finitely generated (Corollary 11.5). Also, we obtain stabilization results for Hom and Ext between correspondence functors evaluated at large enough finite sets (Theorem 12.3).

This article uses essentially only standard facts from algebra and representation theory, with the following exceptions. A few basic results in Section 2 have been imported from elsewhere, but the main exception is the algebra E_{E} of essential relations on a finite set E. This algebra has been analyzed in [BT1] and all its simple modules have been classified there. This uses the fundamental module P_{E}f_{R} associated to a finite poset (E, R) and there is an explicit description of the action of relations on P_{E}f_{R}. All the necessary background on this algebra E_{E} of essential relations is recalled in Section 4. It follows that our approach of the parametrization of simple functors is based on [BT1] since it uses the fundamental modules P_{E}f_{R} in an important way.

2. The representation theory of categories

Before introducing the category C of finite sets and correspondences, 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 adopt a slightly unusual notation by writing D(Y, X) for the set of all morphisms from X to Y. We reverse the order of X and Y in view of having later a left action of morphisms behaving nicely under composition.

We assume that D is small (or more generally that a skeleton of D is 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. It will sometimes be noetherian and sometimes a field, but we shall always emphasize when we make additional assumptions. 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. With our choice of notation, if β ∈ kD(Z, Y), then

(βα) · m = β · (α · m) .

The category F_{k}(kD, k-Mod) of all k-representations of D is an abelian category. We need a small skeleton of D in order to have sets of natural transformations, which are morphisms in F_{k}(kD, k-Mod), but we will avoid this technical discussion. 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 W be a kD(X, X)-module. We define

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

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 , W ↦ L_{X,W}

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 W, there is a natural isomorphism

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

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

(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 [Bo1]. Part (b) follows because this functor is left adjoint of an exact functor and satisfies the property L_{X,W} (X) ≅ W.

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

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

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

(a) J_{X,W} is the unique subfunctor of L_{X,W} which is maximal with respect to the condition that it vanishes at X.

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

Proof : The proof is sketched in Lemma 2.3 of [BST] 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 W be a kD(X, X)-module. We define

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

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

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

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

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

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

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. Since S is simple, θ must be surjective. 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)}.

It should be noted that a simple k-representation S has many possible realizations S ≅ S_{Y,W} as above, where W = 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,W}, where Y is the unique minimal object such that S(Y) ≠ 0 (see Theorem 4.2 for the case of correspondence functors).

Our next proposition is Proposition 3.5 in [BST] in the case of biset functors, but it holds more generally and we just recall the proof of [BST].

2.8. Proposition. 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}, let F_{i} be the subfunctor of F generated by W_{i}. Explicitly, for any object X of D, F_{i}(X) = kD(X, Y) · W_{i} ⊆ F (X). Then F_{i}(Y) = W_{i} 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, 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 [HY], we have an equality F′_{1} = F_{1}, because both subfunctors are generated by their commun evaluation at Y.)

3. Correspondence functors

Leaving the general case, we now prepare the ground for the category C we are going to work with.

3.1. Definition. Let X and Y be sets.

(a) A correspondence from X to Y is a subset of the cartesian product Y × X. Note that we have reversed the order of X and Y for the reasons mentioned at the beginning of Section 2.

(b) A correspondence is often called a relation but we use this terminology only when X = Y, in which case we say that a subset of X × X is a relation on X.

(c) If σ is a permutation of X, then there is a corresponding relation on X which we write

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

In particular, when σ = id, we also write

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

3.2. Definition. Let C denote the following category :

• The objects of C are the finite sets.

• For any two finite sets X and Y, the set C(Y, X) is the set of all correspondences from X to Y.

• The composition of correspondences is as follows. Given R ⊆ Z × Y and S ⊆ Y × X, then RS is defined by

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

The identity morphism id_{X} is the diagonal subset Δ_{X} ⊆ X × X (in other words the equality relation on X).

3.3. Definition. Let kC be the linearization of the category C, where k is any commutative ring (see Definition 2.1).

(a) A correspondence functor (over k) is a k-representation of the category C, that is, a k-linear functor from kC to the category k-Mod of k-modules.

(b) We let F_{k} = F_{k}(kC, k-Mod) be the category of all such correspondence functors (an abelian category).

In part (b), we need to restrict to a small skeleton of C in order to have sets of natural transformations, which are morphisms in F_{k}, but we avoid this technical discussion. It is clear that C has a small skeleton, for instance by taking the full subcategory having one object for each cardinality.

For any finite set E, we define

R_{E} := kC(E, E) ,

the k-algebra of the monoid C(E, E) of all relations on E, in other words the algebra of the semigroup of Boolean matrices of size |E|. The representable functor kC(−, E) (sometimes called Yoneda functor) is the very first example of a correspondence functor. By definition, it is actually isomorphic to the functor L_{E,R_{E}}, see Notation 2.3. If W is an R_{E}-module generated by a single element w (for instance a simple module), then the functor L_{E,W} is isomorphic to a quotient of kC(−, E) via the surjective homomorphism

kC(−, E) ⟶ L_{E,W} = kC(−, E) ⊗_{R_{E}} W , ϕ ↦ ϕ ⊗ w .

The representable functor kC(−, E) is projective (by Yoneda’s lemma). Our next result is basic, but has several important corollaries.

3.4. Lemma. Let E and F be finite sets with |E| ≤ |F |. There exist correspondences i_{∗} ∈ C(F, E) and i^{∗} ∈ C(E, F) such that i^{∗}i_{∗} = id_{E}.

Proof : Since |E| ≤ |F |, there exists an injective map i : E ↪ F. Let i_{∗} ⊆ F × E denote the correspondence

i_{∗} = {(i(e), e) | e ∈ E} ,

and i^{∗} ⊆ E × F denote the correspondence

i^{∗} = {(e, i(e)) | e ∈ E} .

As i is injective, one checks easily that i^{∗}i_{∗} = Δ_{E}, that is, i^{∗}i_{∗} = id_{E}.

In other words, this lemma says that the object E of C behaves like a direct summand of the object F whenever |E| ≤ |F |.

3.5. Corollary. Let E and F be finite sets with |E| ≤ |F |. The representable functor kC(−, E) is isomorphic to a direct summand of the representable functor kC(−, F).

Proof : Right multiplication by i^{∗} defines a homomorphism of correspondence functors

kC(−, E) ⟶ kC(−, F) ,

and right multiplication by i_{∗} defines a homomorphism of correspondence functors

kC(−, F) ⟶ kC(−, E) .

Their composite is the identity of kC(−, E), because i^{∗}i_{∗} = id_{E}.

3.6. Corollary. Let E and F be finite sets with |E| ≤ |F |. The left kC(F, F)- module kC(F, E) is projective.

Proof : By Corollary 3.5, kC(F, E) is isomorphic to a direct summand of kC(F, F), which is free.

3.7. Corollary. Let E and F be finite sets with |E| ≤ |F |. Let M be a correspondence functor. If M(F) = 0, then M(E) = 0.

Proof : For any m ∈ M(E), we have m = i^{∗}i_{∗}·m. But i_{∗}·m ∈ M(F), so i_{∗}·m = 0. Therefore m = 0.

3.8. Corollary. Let E and F be finite sets with |E| ≤ |F |. For every finite set X, composition in the category kC

μ : kC(X, F) ⊗_{R_{F}} kC(F, E) ⟶ kC(X, E)

is an isomorphism.

Proof : The inverse of μ is given by

ϕ : kC(X, E) ⟶ kC(X, F) ⊗_{R_{F}} kC(F, E) , ϕ(α) = αi^{∗} ⊗ i_{∗} .

Composing with μ, we obtain μϕ(α) = μ(αi^{∗} ⊗ i_{∗}) = αi^{∗}i_{∗} = α, so μϕ = id. On the other hand, if β ∈ kC(X, F) and γ ∈ kC(F, E), then γi^{∗} belongs to R_{F} and therefore

ϕμ(β ⊗ γ) = ϕ(βγ) = βγi^{∗} ⊗ i_{∗} = β ⊗ γi^{∗}i_{∗} = β ⊗ γ ,

showing that ϕμ = id.

Now we move to direct summands of representable functors, given by some idempotent. If R is an idempotent in R_{E}, then kC(−, E)R is a direct summand of kC(−, E), hence projective again. In particular, if R is a preorder on E, that is, a relation which is reflexive and transitive, then R is idempotent (because R ⊆ R^{2} by reflexivity and R^{2} ⊆ R by transitivity). There is an equivalence relation ∼ associated with R, defined by

x ∼ y ⟺ (x, y) ∈ R and (y, x) ∈ R .

Then R induces an order relation \overline{R} on the quotient set \overline{E} = E/ ∼ such that

(x, y) ∈ R ⟺ (\overline{x}, \overline{y}) ∈ \overline{R} ,

where \overline{x} denotes the equivalence class of x under ∼.

3.9. Lemma. Let E be a finite set and let R be a preorder on E. Let \overline{R} be the corresponding order on the quotient set \overline{E} = E/ ∼ and write e ↦ \overline{e} for the quotient map E → \overline{E}. The correspondence functors kC(−, E)R and kC(−, \overline{E})\overline{R} are isomorphic via the isomorphism

kC(−, E)R ⟶ kC(−, \overline{E})\overline{R} , S ↦ \overline{S} ,

where for any correspondence S ⊆ X × E, the correspondence \overline{S} ⊆ X × \overline{E} is defined by

(x, \overline{e}) ∈ \overline{S} ⟺ (x, e) ∈ S .

Proof : It is straightforward to check that \overline{S} is well-defined. If S ∈ C(X, E)R, then S = SR and it follows that \overline{S} = \overline{S} \overline{R}. Surjectivity is easy and injectivity follows from the definition of \overline{S}.

This shows that it is relevant to consider the functors kC(−, E)R where R is an order on E. We will see later that they play an important role in connection with simple functors.

We end this section with the definition of duality.

3.10. Proposition. Let X and Y be finite sets. If R ⊆ Y × X, let R^{op} denote the opposite correspondence, defined by

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

Then the assignment R ↦ R^{op} induces an isomorphism from C to the opposite category C^{op}, which extends to an isomorphism from kC to kC^{op}.

Proof : Let X, Y, Z be finite sets, R ⊆ Y × X and S ⊆ Z × Y. One checks easily that (SR)^{op} = R^{op}S^{op}.

We use opposite correspondences to define dual functors. The notion will be used in Section 10.

3.11. Definition. Let F be a correspondence functor over k. The dual F^{♮} of F is the correspondence functor defined on a finite set X by

F^{♮}(X) := Hom_{k} (F (X), k) .

If Y is a finite set and R ⊆ Y ×X, then the map F^{♮}(R) : F^{♮}(X) → F^{♮}(Y) is defined by

∀α ∈ F^{♮}(X), F^{♮}(R)(α) := α ∘ F (R^{op}) .

4. The parametrization of simple correspondence functors

In order to study simple modules or simple functors, it suffices to work over a field k, by standard commutative algebra. If we assume that k is a field, then the evaluation at a finite set X of a representable functor, or of a simple functor, is always a finite-dimensional k-vector space. As before, we continue to work with an arbitrary commutative base ring k and assume that it is a field when necessary.

4.1. Definition. A minimal set for a correspondence functor F is a finite set X of minimal cardinality such that F (X) ≠ 0. For a nonzero functor, such a minimal set always exists and is unique up to bijection.

Our next task is to describe the parametrization of simple correspondence functors. This uses the algebra

R_{X} := kC(X, X)

of all relations on X. This algebra was studied in [BT1] and we use this approach. A relation R on X is called essential if it does not factor through a set of cardinality strictly smaller than |X|. In other words, R has maximal Schein rank in the sense of Section 1.4 of [Ki]. The k-submodule generated by the set of inessential relations is a two-sided ideal

I_{X} := ∑_{|Y |<|X|} kC(X, Y)kC(Y, X)

and the quotient

E_{X} := kC(X, X)/I_{X}

is called the essential algebra. A large part of its structure has been elucidated in [BT1].

The following parametrization theorem is similar to Proposition 2 in [Bo1] or Theorem 4.3.10 in [Bo2]. The context here is different, but the proof is essentially the same.

4.2. Theorem. Assume that k is a field.

(a) Let S be a simple correspondence functor, let E be a minimal set for S, and let W = S(E). Then W is a simple module for the essential algebra E_{E} (with I_{E} acting by zero) and S ≅ S_{E,W}.

(b) Let E be a finite set and let W be a simple module for the essential algebra E_{E}, viewed as a module for the algebra R_{E} by making I_{E} act by zero on W. Then E is a minimal set for S_{E,W}. Moreover, S_{E,W} (E) ≅ W (as E_{E}- modules).

(c) The set of isomorphism classes of simple correspondence functors is parametrized by the set of isomorphism classes of pairs (E, W) where E is a finite set and W is a simple E_{E}-module.

Proof : (a) Since S(Y) = {0} if |Y | < |E|, we have

I_{E} · S(E) = ∑_{|Y |<|E|} kC(E, Y)kC(Y, E) · S(E) ⊆ ∑_{|Y |<|E|} kC(E, Y) · S(Y) = {0} ,

so S(E) is a module for the essential algebra E_{E}. Now the identity of S(E) corresponds by adjunction to a nonzero homomorphism L_{E,W} → S, where W = S(E) (see Lemma 2.4). This homomorphism is surjective since S is simple. But L_{E,W} has a unique simple quotient, namely S_{E,W}, hence S ≅ S_{E,W}.

(b) Suppose that S_{E,W} (Y) ≠ {0}. Then L_{E,W} (Y) ≠ J_{E,W} (Y), so there exists a correspondence ϕ ∈ C(Y, E) and v ∈ W such that ϕ ⊗ v ∈ L_{E,W} (Y) − J_{E,W} (Y). By definition of J_{E,W}, this means that there exists a correspondence ψ ∈ C(E, Y) such that ψϕ · v ≠ 0. Since W is a module for the essential algebra E_{E} = R_{E}/I_{E}, we have ψϕ ∉ I_{E}. But ψϕ factorizes through Y, so we must have |Y | ≥ |E|. Thus E is a minimal set for S_{E,W}. The isomorphism S_{E,W} (E) ≅ W is a general fact mentioned before.

(c) This follows from (a) and (b).

Theorem 4.2 reduces the classification of simple correspondence functors to the question of classifying all simple modules for the essential algebra E_{E}. Fortunately, this has been achieved in [BT1]. An alternative path would be to use the classical approach to simple R_{E}-modules via idempotents in the semigroup C(E, E) and Green’s theory of J-classes (see the textbook [CP], or the recent article [GMS] for a modern point of view). We do not follow this approach because we need later in an important way a fundamental module, defined below, which is not part of the classical approach, but is the key for the classification in [BT1].

The simple E_{E}-modules are actually modules for a quotient P_{E} = E_{E}/N where N is a nilpotent ideal defined in [BT1]. We call P_{E} the algebra of permuted orders, because it has a k-basis consisting of all relations on E of the form Δ_{σ}R, where σ runs through the symmetric group Σ_{E} of all permutations of E, and R is an order on E. By an order, we always mean a partial order relation. The product of two orders R and S in P_{E} is the transitive closure of R ∪ S if this transitive closure is an order, and zero otherwise.

We let O be the set of all orders on E and Aut(E, R) the stabilizer of the order R under the action of the symmetric group Σ_{E} by conjugation. For the description of simple E_{E}-modules, we need the following new basis of P_{E} (see Theorem 6.2 in [BT1] for details).

4.3. Lemma.

(a) There is a set {f_{R} | R ∈ O} of orthogonal idempotents of P_{E} whose sum is 1, such that P_{E} has a k-basis consisting of all elements of the form Δ_{σ}f_{R}, where σ ∈ Σ_{E} and R ∈ O.

(b) For any σ ∈ Σ_{E}, we have ^{σ}f_{R} = f_{^{σ}R}, where ^{σ}x = Δ_{σ}xΔ_{σ^{−1}} for any x ∈ P_{E}. In particular, Δ_{σ}f_{R}Δ_{σ^{−1}} = f_{R} if σ ∈ Aut(E, R).

(c) For any order Q on E, we have :

Qf_{R} ≠ 0 ⟺ Qf_{R} = f_{R} ⟺ Q ⊆ R .

For the description of simple E_{E}-modules and then simple correspondence functors, we will make use of the left E_{E}-module P_{E}f_{R}. This module is actually defined without assuming that k is a field.

4.4. Definition. Let (E, R) be a finite poset (i.e. E is a finite set and R is an order on E). We call P_{E}f_{R} the fundamental module for the algebra E_{E}, associated with the poset (E, R).

We now describe its structure.

4.5. Proposition. Let (E, R) be a finite poset

(a) The fundamental module P_{E}f_{R} is a left module for the algebra P_{E}, hence also a left module for the essential algebra E_{E} and for the algebra of relations R_{E}.

(b) P_{E}f_{R} is a free k-module with a k-basis consisting of the elements Δ_{σ}f_{R}, where σ runs through the group Σ_{E} of all permutations of E.

(c) P_{E}f_{R} is a (P_{E}, k Aut(E, R))-bimodule and the right action of k Aut(E, R) is free.

(d) The action of the algebra of relations R_{E} on the module P_{E}f_{R} is given as follows. For any relation Q ∈ C(E, E),

Q · Δ_{σ}f_{R} = \{ \begin{matrix}Δ_{τσ}f_{R} & if ∃τ ∈ Σ_{E} such that Δ_{E} ⊆ Δ_{τ^{−1}}Q ⊆ ^{σ}R, \\ 0 & otherwise , \end{matrix}

where Δ_{E} is the diagonal of E × E, and ^{σ}R = {(σ(e), σ(f)) | (e, f) ∈ R} (recall that τ is unique in the first case).

Proof : See Corollary 7.3 and Proposition 8.5 in [BT1].

The description of all simple E_{E}-modules is as follows (see Theorem 8.1 in [BT1] for details).

4.6. Theorem. Assume that k is a field and let E be a finite set.

(a) Let R be an order on E and let P_{E}f_{R} be the corresponding fundamental module. If V is a simple k Aut(E, R)-module, then

T_{R,V} := P_{E}f_{R} ⊗_{k Aut(E,R)} V

is a simple P_{E}-module (hence also a simple E_{E}-module).

(b) Every simple E_{E}-module is isomorphic to a module T_{R,V} as in (a).

(c) For any permutation σ ∈ Σ_{E}, we have T_{^{σ}R,^{σ}V} ≅ T_{R,V}, where ^{σ}R = Δ_{σ}RΔ_{σ^{−1}} is the conjugate order and ^{σ}V is the conjugate module.

(d) The set of isomorphism classes of simple E_{E}-modules is parametrized by the set of conjugacy classes of pairs (R, V) where R is an order on E and V is a simple k Aut(E, R)-module.

Putting together Theorem 4.2 and Theorem 4.6, we finally obtain the following parametrization, which is essential for our purposes.

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

Proof : By Theorem 4.2, the isomorphism classes of simple correspondence functors are parametrized by pairs (E, W), where E is a finite set and W is a simple E_{E}-module. Now by Theorem 4.7, the isomorphism classes of simple E_{E}-modules W are parametrized by pairs (R, V), where R is an order on E and V is a simple k Aut(E, R)-module. Hence the pairs (E, W) become triples (E, R, V).

4.8. Notation. Let (E, R) be a finite poset.

(a) If V is a simple k Aut(E, R)-module, we denote by S_{E,R,V} the simple correspondence functor parametrized by the triple (E, R, V). Explicitly,

S_{E,R,V} = L_{E,T_{R,V}} /J_{E,T_{R,V}} .

(b) More generally, for any commutative ring k and any k Aut(E, R)-module V, we define the P_{E}-module (hence also an R_{E}-module)

T_{R,V} := P_{E}f_{R} ⊗_{k Aut(E,R)} V

and the correspondence functor

S_{E,R,V} := L_{E,T_{R,V}} /J_{E,T_{R,V}} .

We end this section with a basic result concerning the correspondence functors S_{E,R,V}, where k is any commutative ring and V is any k Aut(E, R)-module.

4.9. Lemma. Let (E, R) be a finite poset and let V be any k Aut(E, R)-module.

(a) E is a minimal set for S_{E,R,V}.

(b) S_{E,R,V} (E) ≅ T_{R,V} as R_{E}-modules.

Proof : Both P_{E}f_{R} and T_{R,V} = P_{E}f_{R} ⊗_{k Aut(E,R)} V are left modules for the essential algebra E_{E}. Therefore, the argument given in part (b) of Theorem 4.2 shows again that E is a minimal set for S_{E,R,V}. Moreover, since J_{E,T_{R,V}} vanishes on evaluation at E, we have

S_{E,R,V} (E) ≅ L_{E,T_{R,V}} (E) = T_{R,V} = P_{E}f_{R} ⊗_{k Aut(E,R)} V ,

as required.

When k is a field and V is simple, we recover the simple module S_{E,R,V} (E) = T_{R,V} of Theorem 4.6.

5. Small examples

In this section, we describe two small examples.

5.1. Example. Let E = ∅ be the empty set and consider the representable functor kC(−, ∅). Then C(X, ∅) = {∅} is a singleton for any finite set X, so kC(X, ∅) ≅ k. Moreover, any correspondence S ∈ C(Y, X) is sent to the identity map from kC(X, ∅) ≅ k to kC(Y, ∅) ≅ k. This functor deserves to be called the constant functor. We will denote it by \underline{k}.

Assume that k is a field. The algebra kC(∅, ∅) ≅ k has a unique simple module k. It is then easy to check that L_{∅,k} = kC(−, ∅) and J_{∅,k} = {0}. Therefore

kC(−, ∅) = S_{∅,∅,k}

the simple functor indexed by (∅, ∅, k). Here the second ∅ denotes the only relation on the empty set, while k is the only simple module for the group algebra k Aut(E, R) = kΣ_{∅} ≅ k, where Σ_{∅} = {id} is the symmetric group of the empty set. Note that S_{∅,∅,k} is projective, because it is a representable functor.

5.2. Example. Let E = {1} be a set with one element and consider the representable functor C(−, {1}). Then C(X, {1}) is in bijection with the set B(X) of all subsets of X, because X × {1} ≅ X. It is easy to see that a correspondence S ∈ C(Y, X) is sent to the map

B(X) ⟶ B(Y) , A ↦ S_{A} ,

where S_{A} = {y ∈ Y | ∃ a ∈ A such that (y, a) ∈ S}. Thus kB ≅ kC(−, {1}) is a correspondence functor such that kB(X) is a free k-module with basis B(X) and rank 2^{|X|} for every finite set X.

The functor kB has a subfunctor isomorphic to the constant functor S_{∅,∅,k}, because B(X) contains the element ∅ which is mapped to ∅ by any correspondence. We claim that, if k is a field, the quotient kB/S_{∅,∅,k} is a simple functor.

Assume that k is a field. The algebra kC({1}, {1}) has dimension 2, actually isomorphic to k×k with two primitive idempotents ∅ and {(1, 1)}−∅. The essential algebra E_{{1}} is a one-dimensional quotient and its unique simple module W is onedimensional and corresponds to the pair (R, k), where R is the only order relation on {1} and k is the only simple module for the group algebra k Aut(E, R) = kΣ_{{1}} ≅ k, with Σ_{{1}} = {id} the symmetric group of {1}. Thus there is a simple functor S_{{1},W} = S_{{1},R,k}.

The kernel of the quotient map

kB ≅ kC(−, {1}) ⟶ kC(−, {1}) ⊗_{kC({1},{1})} W = L_{{1},W}

is the constant subfunctor S_{∅,∅,k} mentioned above, because ∅ ∈ C(X, {1}) can be written ∅ · ∅, with the second empty set belonging to C({1}, {1}), thus acting by zero on W. Now we know that L_{{1},W} /J_{{1},W} = S_{{1},W} and we are going to show that J_{{1},W} = {0}. It then follows that L_{{1},W} = S_{{1},W} is simple and isomorphic to kB/S_{∅,∅,k}, proving the claim above.

In order to prove that J_{{1},W} = {0}, we let u ∈ L_{{1},W} (X), which can be written

u = ∑_{A∈B(X)} λ_{A}(A × {1}) ⊗ w ,

where w is a generator of W and λ_{A} ∈ k for all A. Since the empty set acts by zero on w, the sum actually runs over nonempty subsets A ∈ B(A). Then u ∈ J_{{1},W} (X) if and only if, for all ({1} × B) ∈ C({1}, X), we have

∑_{A∈B(X)} λ_{A} ({1} × B)(A × {1}) · w = 0 .

Since ∅ acts by zero and {1} acts as the identity, we obtain

(\{1\} × B)(A × \{1\}) · w = \{ \begin{matrix}0 & if B ∩ A = ∅ , \\ w & if B ∩ A ≠ ∅ . \end{matrix}

This yields the condition

∑_{A∩B≠∅} λ_{A} = 0 , for every nonempty B ∈ B(X) .

We prove by induction that λ_{C} = 0 for every nonempty C ∈ B(X). Subtracting the condition for B = X and for B = X − C, we obtain

0 = ∑_{A≠∅} λ_{A} − ∑_{A⊈C} λ_{A} = ∑_{∅≠A⊆C} λ_{A} .

If C = {c} is a singleton, we obtain λ_{{c}} = 0 and this starts the induction. In the general case, we obtain by induction λ_{A} = 0 for ∅ ≠ A ≠ C, so we are left with λ_{C} = 0. Therefore u = 0 and so J_{{1},W} = {0}.

There is a special feature of this small example, namely that the exact sequence

0 ⟶ S_{∅,∅,k} ⟶ kB ⟶ S_{{1},R,k} ⟶ 0

splits. This is because there is a retraction kB → S_{∅,∅,k} defined by

kB(X) ⟶ k , A ↦ 1 ,

which is easily checked to be a homomorphism of functors. Since kB is projective (because it is a representable functor), its direct summand S_{{1},R,k} is projective.

5.3. Remark. In both Example 5.1 and Example 5.2, there is a unique order relation R on E, which is a total order. Actually, these examples are special cases of the general situation of a total order, which is studied in [BT2].

6. Finite generation

In this section, we analyze the property of finite generation for correspondence functors.

6.1. Definition. Let {E_{i} | i ∈ I} be a family of finite sets indexed by a set I and, for every i ∈ I, let m_{i} ∈ M(E_{i}). A correspondence functor M is said to be generated by the set {m_{i} | i ∈ I} if for every finite set X and every element m ∈ M(X), there exists a finite subset J ⊆ I such that

m = ∑_{j∈J} α_{j}m_{j} , for some α_{j} ∈ kC(X, E_{j}) (where j ∈ J) .

In the case where I is finite, M is said to be finitely generated.

We remark that, in the sum above, each α_{j} decomposes as a finite k-linear combination α_{j} = ∑_{S∈C(X,E_{j})} λ_{S} S where λ_{S} ∈ k. Therefore, every m ∈ M(X) decomposes further as a (finite) k-linear combination

m = ∑_{{j∈J \atop S∈C(X,E_{j})}} λ_{S} Sm_{j} .

6.2. Example. If E is a finite set, the representable functor kC(−, E) is finitely generated. It is actually generated by a single element, namely Δ_{E} ∈ kC(E, E).

6.3. Lemma. Let M be a finitely generated correspondence functor over k. Then, for every finite set X, the evaluation M(X) is a finitely generated k-module. In particular, if k is a field, then M(X) is finite-dimensional.

Proof : Let {m_{i} | i = 1, …, n} be a finite set of generators of M, with m_{i} ∈ M(E_{i}). Let B_{X} = {Sm_{i} | S ∈ C(X, E_{i}), i = 1, …, n}. By definition and by the remark above, every element of M(X) is a k-linear combination of elements of B_{X}. But B_{X} is a finite set, so M(X) is finitely generated. If k is a field, this means that M(X) is finite-dimensional.

It follows that, in order to understand finitely generated correspondence functors, we could assume that all their evaluations are finitely generated k-modules. But we do not need this for our next characterizations.

6.4. Proposition. Let M be a correspondence functor over k. The following conditions are equivalent :

(a) M is finitely generated.

(b) M is isomorphic to a quotient of a functor of the form ⨁_{i=1}^{n} kC(−, E_{i}) for

some finite sets E_{i} (i = 1, …, n).

(c) M is isomorphic to a quotient of a functor of the form ⨁_{i∈I} kC(−, E) for

some finite set E and some finite index set I.

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

Proof : (a) ⇒ (b). Suppose that M is generated by the set {m_{i} | i = 1, …, n}, where m_{i} ∈ M(E_{i}). It follows from Yoneda’s lemma that there is a morphism

ψ_{i} : kC(−, E_{i}) → M

mapping Δ_{E_{i}} ∈ C(E_{i}, E_{i}) to the element m_{i} ∈ M(E_{i}), hence mapping β ∈ C(X, E_{i}) to βm_{i} ∈ M(X). Their sum yields a morphism

ψ : ⨁_{i=1}^{n} kC(−, E_{i}) → M .

For any X and any m ∈ M(X), we have m = ∑_{i=1}^{n} α_{i}m_{i} for some α_{i} ∈ kC(X, E_{i}),

hence m = ψ(α_{1}, …, α_{n}), proving the surjectivity of ψ.

(b) ⇒ (c). Suppose that M is isomorphic to a quotient of a functor of the form

⨁_{i=1}^{n} kC(−, E_{i}). Let F be the largest of the sets E_{i}. By Corollary 3.5, each kC(−, E_{i})

is a direct summand of kC(−, F). Therefore, M is also isomorphic to a quotient of

the functor ⨁_{i=1}^{n} kC(−, F).

(c) ⇒ (d). By Example 6.2, kC(−, E) is generated by Δ_{E} ∈ kC(E, E). Let b_{i} ∈ ⨁_{i∈I} kC(E, E) having zero components everywhere, except the i-th equal to Δ_{E}.

Since M is a quotient of ⨁_{i∈I} kC(−, E), it is generated by the images of the ele-

ments b_{i}. This is a finite set because I is finite by assumption.

(d) ⇒ (a). Since M is generated by B, it is finitely generated.

We apply this to the functors L_{E,V} and S_{E,V} defined in Lemma 2.4 and Notation 2.6.

6.5. Corollary. Let V be a finitely generated R_{E}-module, where E is a finite set and R_{E} is the algebra of relations on E. Then L_{E,V} and S_{E,V} are finitely generated correspondence functors.

Proof : Let {v_{i} | i ∈ I} be a finite set of generators of V as an R_{E}-module. There is a morphism π_{i} : kC(−, E) → L_{E,V} mapping Δ_{E} to v_{i} ∈ L_{E,V} (E) = V. Therefore, we obtain a surjective morphism

∑_{i∈I} π_{i} : ⨁_{i∈I} kC(−, E) ⟶ L_{E,V} ,

showing that L_{E,V} is finitely generated. Now S_{E,V} is a quotient of L_{E,V}, so it is also finitely generated.

6.6. Proposition. Let k be a noetherian ring.

(a) For any 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, the kmodule Hom_{F_{k}}(M, N) is finitely generated.

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

Proof : (a) Since M is finitely generated, there exists a finite set E and a surjective morphism π : ⨁_{i∈I} kC(−, E) → M for some finite set I (Proposition 6.4).

Denote by A the subalgebra of End_{F_{k}} ( ⨁_{i∈I} kC(−, E)) consisting of endomorphisms

φ such that φ(Ker π) ⊆ Ker π. The algebra A is isomorphic to a k-submodule of End_{F_{k}} ( ⨁_{i∈I} kC(−, E)), which is isomorphic to a matrix algebra of size |I| over the

k-algebra kC(E, E) (because End_{F_{k}} (kC(−, E)) ≅ kC(E, E) by Yoneda’s lemma). This matrix algebra is free of finite rank as a k-module. As k is noetherian, it follows that A is a finitely generated k-module.

Now by definition of A, any φ ∈ A induces an endomorphism \overline{φ} of M such that \overline{φ}π = πφ. This yields an algebra homomorphism A → End_{F_{k}}(M), which is surjective, since the functor kC(−, E) is projective. It follows that End_{F_{k}}(M) is also a finitely generated k-module.

(b) The functor M ⊕ N is finitely generated, hence V = End_{F_{k}}(M ⊕ N) is a finitely generated k-module, by (a). Since Hom_{F_{k}}(M, N) embeds in V, it is also a finitely generated k-module.

(c) If moreover k is a field, then End_{F_{k}}(M) is a finite dimensional k-vector space, by (a). Finding decompositions of M as a direct sum of subfunctors amounts to splitting the identity of End_{F_{k}}(M) as a sum of orthogonal idempotents. Since End_{F_{k}}(M) is a finite dimensional algebra over the field k, the standard theorems on decomposition of the identity as a sum of primitive idempotents apply. Thus M can be split as a direct sum of indecomposable functors, and such a decomposition is unique up to isomorphism.

After the Krull-Remak-Schmidt theorem, we treat the case of projective covers. Recall (see 2.5.14 in [AF] for categories of modules) that in an abelian category A, a subobject N of an object P is called superfluous if for any subobject X of P, the equality X + N = P implies X = P. Similarly, an epimorphism f : P → M in A is called superfluous if Ker f is superfluous in P, or equivalently, if for any morphism g : L → P in A, the composition f ∘ g is an epimorphism if and only if g is an epimorphism. A projective cover of an object M of A is defined as a pair (P, p), where P is projective and p is a superfluous epimorphism from P to M.

6.7. Proposition. Let M be a finitely generated correspondence functor over a commutative ring k.

(a) Suppose that M is generated by M(E) where E is a finite. If (P, p) is a projective cover of M(E) in R_{E}-Mod, then (L_{E,P} , p̃) is a projective cover of M in F_{k}, where p̃: L_{E,P} → M is obtained from p : P → M(E) by the adjunction of Lemma 2.4.

(b) If k is a field, then M admits a projective cover.

(c) In particular, when k is a field, let E be a finite set, let R be an order relation on E, and let V be a simple k Aut(E, R)-module. Let moreover (P, p) be a projective cover of Pf_{R} ⊗_{k Aut(E,R)} V in R_{E}-Mod. Then (L_{E,P} , p̃) is a projective cover of the simple correspondence functor S_{E,R,V}.

Proof : (a) (This was already proved in Lemme 2 of [Bo1].) By Lemma 2.4, the functor Q ↦ L_{E,Q} maps projectives to projectives. So the functor L_{E,P} is projective. Since M is generated by M(E), and since the evaluation at E of the morphism p̃: L_{E,P} → M is equal to p : P → M(E), it follows that p̃ is surjective. If N is any subfunctor of L_{E,P} such that p̃(N) = M, then in particular N(E) ⊆ P and p(N(E)) = M(E). Since p is superfluous, it follows that N(E) = P, hence N = L_{E,P} since L_{E,P} is generated by its evaluation P at E.

(b) The algebra R_{E} is a finite dimensional algebra over the field k. Hence any finite dimensional R_{E}-module admits a projective cover. Therefore (b) follows from (a).

(c) The evaluation of the simple functor S_{E,R,V} at E is the simple R_{E}-module Pf_{R} ⊗_{k Aut(E,R)} V. Hence (c) follows from (a) and (b).

7. Bounded type

In this section, we analyze a notion which is more general than finite generation.

7.1. Definition. Let k be a commutative ring and let M be a correspondence functor over k.

(a) We say that M has bounded type if there exists a finite set E such that M is generated by M(E).

(b) We say that M has a bounded presentation if there are projective correspondence functors P and Q of bounded type and an exact sequence of functors

Q → P → M → 0 .

Such a sequence is called a bounded presentation of M.

Suppose that M has bounded type and let E be a finite set such that M is generated by M(E). It is elementary to see that M is finitely generated if and only if M(E) is a finitely generated R_{E}-module (using Example 6.2 and Lemma 6.3). Thus an infinite direct sum of copies of a simple functor S_{E,R,V} has bounded type (because it generated by its evaluation at E) but is not finitely generated. Also, a typical example of a correspondence functor which does not have bounded type is

a direct sum of simple functors ⨁_{n=0}^{∞} S_{E_{n},R_{n},V_{n}}, where |E_{n}| = n for each n. This is

because S_{E_{n},R_{n},V_{n}} cannot be generated by a set of cardinality < n.

7.2. Lemma. Let k be a commutative ring and let M be a correspondence functor over k. Suppose that M has bounded type and let E be a finite set such that M is generated by M(E). For any finite set F with |F | ≥ |E|, the functor M is generated by M(F).

Proof : Let i_{∗} ∈ C(F, E) and i^{∗} ∈ C(E, F) be as in Lemma 3.4, so that i^{∗}i_{∗} = id_{E}. Saying that M is generated by M(E) amounts to saying that M(X) is equal to kC(X, E)M(E), for any finite set X. It follows that

M(X) = kC(X, E)M(E)
= kC(X, E)i^{∗}i_{∗}M(E)
⊆ kC(X, F)i_{∗}M(E)
⊆ kC(X, F)M(F) ⊆ M(X) ,

hence M(X) = kC(X, F)M(F), i.e. M is generated by M(F).

We are going to prove that any correspondence functor having a bounded presentation is isomorphic to some functor L_{E,V}. We first deal with the case of projective functors.

7.3. Lemma. Suppose that a correspondence functor M has bounded type and let E be a finite set such that M is generated by M(E). If M is projective, then for any finite set F with |F | ≥ |E|, the R_{F} -module M(F) is projective, and the counit morphism L_{F,M(F)} → M is an isomorphism.

Proof : By Lemma 7.2, M is generated by M(F). Choosing a set B of generators of M(F) as an R_{F} -module (e.g. B = M(F)), we see that M is also generated by B. As in the beginning of the proof of Proposition 6.4, we can apply Yoneda’s lemma and obtain a surjective morphism ⨁_{b∈B} kC(−, F) → M. Since M is projective, this

morphism splits, and its evaluation at F also splits as a map of R_{F} -modules. Hence M(F) is isomorphic to a direct summand of a free R_{F} -module, that is, a projective R_{F} -module.

By adjunction (Lemma 2.4), there is a morphism θ : L_{F,M(F)} → M which, evaluated at F, gives the identity map of M(F). As M is generated by M(F), it follows that θ is surjective, hence split since M is projective. Let η : M → L_{F,M(F)} be a section of θ. Since, on evaluation at F, we have θ_{F} = id_{M(F)}, the equation θη = id_{M} implies that, on evaluation at F, we get η_{F} = id_{M(F)}. Therefore η_{F} θ_{F} = id_{M(F)}. Now ηθ : L_{F,M(F)} → L_{F,M(F)} corresponds by adjunction to

id_{M(F)} = η_{F} θ_{F} : M(F) ⟶ L_{F,M(F)}(F) = M(F) .

Therefore ηθ must be the identity. It follows that η and θ are mutual inverses. Thus M ≅ L_{F,M(F)}.

We now prove that any functor with a bounded presentation is an L_{E,V}, and conversely. In the case of a noetherian base ring k, this result will be improved in Section 11.

7.4. Theorem.

(a) Suppose that a correspondence functor M has a bounded presentation

Q → P → M → 0 .

Let E be a finite set such that P is generated by P (E) and Q is generated by Q(E). Then for any finite set F with |F | ≥ |E|, the counit morphism

η_{M,F} : L_{F,M(F)} → M

is an isomorphism.

(b) If E is a finite set and V is an R_{E}-module, then the functor L_{E,V} has a bounded presentation. More precisely, if

W_{1} → W_{0} → V → 0

is a projective resolution of V as an R_{E}-module, then

L_{E,W_{1}} → L_{E,W_{0}} → L_{E,V} → 0

is a bounded presentation of L_{E,V}.

Proof : (a) Consider the commutative diagram

\xymatrix{L_{F,Q(F)} \ar[d]^{η_{Q,F}} \ar[r] & L_{F,P (F)} \ar[d]^{η_{P,F}} \ar[r] & L_{F,M(F)} \ar[d]^{η_{M,F}} \ar[r] & 0 \\ Q \ar[r] & P \ar[r] & M \ar[r] & 0}

where the vertical maps are obtained by the adjunction of Lemma 2.4. This lemma also asserts that the first row is exact. By Lemma 7.3, for any finite set F with |F | ≥ |E|, the vertical morphisms η_{Q,F} and η_{P,F} are isomorphisms. Since the rows of this diagram are exact, it follows that η_{M,F} is also an isomorphism.

(b) We use the adjunction of Lemma 2.4. Applying the right exact functor U ↦ L_{E,U} to the exact sequence W_{1} → W_{0} → V → 0 gives the exact sequence

L_{E,W_{1}} → L_{E,W_{0}} → L_{E,V} → 0 .

By Lemma 2.4, L_{E,W_{1}} and L_{E,W_{0}} are projective functors, since W_{1} and W_{0} are projective R_{E}-modules. They all have bounded type since they are generated by their evaluation at E.

Given a finite set E and an R_{E}-module V, we define an induction procedure as follows. For any finite set F, we define the R_{F} -module

V ↑_{E}^{F} := kC(F, E) ⊗_{R_{E}} V .

Notice that, by the definition of L_{E,V}, we have L_{E,V} (F) = V ↑_{E}^{F}. To end this section, we mention the behavior of the functors L_{E,V} under induction.

7.5. Proposition. Let E be a finite set and V be an R_{E}-module. If F is a finite set with |F | ≥ |E|, the equality L_{E,V} (F) = V ↑_{E}^{F} induces an isomorphism of correspondence functors

L_{F,V↑_{E}^{F}} ≅ L_{E,V} .

Proof : Let M = L_{E,V}. Then by Theorem 7.4, there exists a bounded presentation

Q → P → M → 0

where Q = L_{E,W_{1}} is generated by Q(E) and P = L_{E,W_{0}} is generated by P (E). Hence by Theorem 7.4, for any finite set F with |F | ≥ |E|, the counit morphism

η_{M,F} : L_{F,M(F)} → M

is an isomorphism. In other words η_{M,F} : L_{F,V↑_{E}^{F}} → L_{E,V} is an isomorphism.

8. Exponential behavior and finite length

In this section, we give a lower bound estimate for the dimension of the evaluations of a simple functor S_{E,R,V}, which is proved to behave exponentially. We also prove that the exponential behavior is equivalent to finite generation.

We first need a well-known combinatorial lemma.

8.1. Lemma. Let E be a finite set and let G be a finite set containing E.

(a) For any finite set X, the number s(X, E) of surjective maps φ : X → E is equal to

s(X, E) = ∑_{i=0}^{|E|}(−1)^{|E|−i}\binom{|E|}{i} i^{|X|} ,

or equivalently

s(X, E) = ∑_{j=0}^{|E|}(−1)^{j}\binom{|E|}{j} (|E| − j)^{|X|} .

(b) More generally, for any finite set X, the number ss(X, E, G) of all maps φ : X → G such that E ⊆ φ(X) ⊆ G is equal to

ss(X, E, G) = ∑_{i=0}^{|E|}(−1)^{i}\binom{|E|}{i}(|G| − i)^{|X|} .

Proof : (a) Up to multiplication by |E|!, the number s(X, E) is known as a Stirling number of the second kind. Either by Formula (24a) in Section 1.4 of [St], or by a direct application of Möbius inversion (i.e. inclusion-exclusion principle in the present case), we have

s(X, E) = ∑_{B⊆E}(−1)^{|E−B|}|B|^{|X|} .

Setting |B| = i, the first formula in (a) follows.

(b) Applying (a) to each subset A such that E ⊆ A ⊆ G, we obtain

ss(X, E, G) = ∑_{E⊆A⊆G} s(X, A)
= ∑_{E⊆A⊆G} ∑_{B⊆A}(−1)^{|A−B|}|B|^{|X|}
= ∑_{B⊆G} ( ∑_{E∪B⊆A⊆G}(−1)^{|A−B|})|B|^{|X|}

But the inner sum is zero unless E ∪ B = G. Therefore

ss(X, E, G) = ∑_{{B⊆G \atop E∪B=G}}(−1)^{|G−B|}|B|^{|X|}

= ∑_{C⊆E}(−1)^{|C|}(|G − C|)^{|X|} ,

where the last equality follows by setting C = G − B. This proves part (b).

Now we prove our main lower bound estimate for the dimensions of the evaluations of a simple functor.

8.2. Theorem. Suppose that k is a field and let S_{E,R,V} be a simple correspondence functor, where E is a finite set, R is an order on E, and V 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,V} (X)) ≤ (2^{|E|})^{|X|} .

Proof : Recall that S_{E,R,V} = L_{E,T_{R,V}} /J_{E,T_{R,V}} where T_{R,V} denotes the R_{E}-module

T_{R,V} = P_{E}f_{R} ⊗_{k Aut(E,R)} V .

Since V is simple, it is generated by a single element v ∈ V − {0}. Since f_{R}α = αf_{R} for any α ∈ Aut(E, R), it follows that the R_{E}-module P_{E}f_{R} ⊗_{k Aut(E,R)} V is generated by the single element f_{R} ⊗ v. Therefore, we have a surjective morphism of correspondence functors

\begin{matrix}kC(−, E) & ⟶ & kC(−, E) ⊗_{R_{E}} P_{E}f_{R} ⊗_{k Aut(E,R)} V = L_{E,T_{R,V}} \\ U & ↦ & U ⊗ f_{R} ⊗ v . \end{matrix}

Since S_{E,R,V} is a quotient of L_{E,T_{R,V}}, we obtain a surjective morphism of correspondence functors

kC(−, E) ⟶ S_{E,R,V} , U ↦ \overline{U ⊗ f_{R} ⊗ v} ,

where, for any U ∈ C(X, E), the element \overline{U ⊗ f_{R} ⊗ v} ∈ S_{E,R,V} (X) denotes the class of U ⊗ f_{R} ⊗ v ∈ L_{E,T_{R,V}} (X).

We first prove the upper bound. This is easy and holds for every finite set X. Since S_{E,R,V} is isomorphic to a quotient of kC(−, E), we have

dim (S_{E,R,V} (X)) ≤ dim (kC(X, E)) = 2^{|X×E|} = (2^{|E|})^{|X|} .

In order to find a lower bound, for some finite set X, we introduce the set Φ of all surjective maps φ : X → E. The symmetric group Σ_{E} acts (on the left) on Φ by composition. Since Φ consists of surjections onto E, this action is free, that is, the stabilizer of each φ ∈ Φ is trivial. We consider the subgroup Aut(E, R) of Σ_{E} and we let A be a set of representatives of the set of left orbits Aut(E, R)\Φ.

For any φ ∈ Φ, we define

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

We claim that Λ_{φ}R = Λ_{φ} and RΓ_{φ} = Γ_{φ}. Since Δ_{E} ⊆ R, we always have Λ_{φ} = Λ_{φ}Δ_{E} ⊆ Λ_{φ}R. Conversely, if (x, f) ∈ Λ_{φ}R, then there exists e ∈ E such that (x, e) ∈ Λ_{φ} and (e, f) ∈ R, that is, (φ(x), e) ∈ R and (e, f) ∈ R. It follows that (φ(x), f) ∈ R by transitivity of R, that is, (x, f) ∈ Λ_{φ}. Thus Λ_{φ}R ⊆ Λ_{φ} and equality follows. The proof for Γ_{φ} is similar.

Now we consider the set

{Λ_{φ} | φ ∈ A} ⊆ C(X, E) .

We want to prove that the image of this set in S_{E,R,V} (X) is linearly independent, from which we will deduce that |A| ≤ dim (S_{E,R,V} (X)). Suppose that ∑_{φ∈A} λ_{φ}Λ_{φ} is

mapped to zero in S_{E,R,V} (X), where λ_{φ} ∈ k for every φ ∈ A. In other words,

∑_{φ∈A} λ_{φ}\overline{Λ_{φ} ⊗ f_{R} ⊗ v} = 0 ,  that is,  ∑_{φ∈A} λ_{φ}Λ_{φ} ⊗ f_{R} ⊗ v ∈ J_{E,T_{R,V}} .

The definition of J_{E,T_{R,V}} implies that, for every U ∈ C(E, X),

∑_{φ∈A} λ_{φ}UΛ_{φ} · (f_{R} ⊗ v) = 0 .

Choosing in particular U = Γ_{ψ} and ψ ∈ A, we obtain :

(8.3)  for every ψ ∈ A ,  ∑_{φ∈A} λ_{φ}Γ_{ψ}Λ_{φ} · (f_{R} ⊗ v) = 0 .

By Proposition 4.5, the action of the relation Γ_{ψ}Λ_{φ} on f_{R} ⊗ v is given by

(Γ_{ψ}Λ_{φ}) · f_{R} ⊗ v = \{ \begin{matrix}Δ_{τ} f_{R} ⊗ v & if ∃τ ∈ Σ_{E} such that Δ_{E} ⊆ Δ_{τ^{−1}}Γ_{ψ}Λ_{φ} ⊆ R , \\ 0 & otherwise . \end{matrix}

In the first case, τ is unique.

We claim that

Δ_{E} ⊆ Δ_{τ^{−1}}Γ_{ψ}Λ_{φ} ⊆ R ⟺ Γ_{ψ}Λ_{φ} = Δ_{τ} R .

If the left hand side holds, then multiply on the right by R and use the fact that Λ_{φ}R = Λ_{φ} to obtain Δ_{τ^{−1}}Γ_{ψ}Λ_{φ} = R, hence Γ_{ψ}Λ_{φ} = Δ_{τ} R. Conversely, if the right hand side holds, then Δ_{τ^{−1}}Γ_{ψ}Λ_{φ} = R, hence

RΔ_{τ^{−1}}Γ_{ψ}Λ_{φ} = R^{2} = R

by transitivity and reflexivity of R. In particular, by reflexivity again,

Δ_{E} ⊆ RΔ_{τ^{−1}}Γ_{ψ}Λ_{φ}

so that, for any (a, a) ∈ Δ_{E}, there exists b ∈ E with (a, b) ∈ R and (b, a) ∈ Δ_{τ^{−1}}Γ_{ψ}Λ_{φ} = R. By antisymmetry of R, it follows that b = a and therefore (a, a) ∈ Δ_{τ^{−1}}Γ_{ψ}Λ_{φ}, so that Δ_{E} ⊆ Δ_{τ^{−1}}Γ_{ψ}Λ_{φ}. This shows that the left hand side holds, proving the claim.

We can now rewrite (8.3) as follows :

for every ψ ∈ A ,  ∑_{\begin{matrix}φ∈A , τ∈Σ_{E} \\ Γ_{ψ}Λ_{φ}=Δ_{τ} R \end{matrix}} λ_{φ}Δ_{τ} f_{R} ⊗ v = 0 .

Write τ = σα with σ ∈ S and α ∈ Aut(E, R), where S denotes some set of representatives of cosets Σ_{E}/ Aut(E, R). Since Δ_{α}f_{R} = f_{R}Δ_{α} for every α ∈ Aut(E, R) and since the tensor product is over k Aut(E, R), we obtain

(8.4)  for every ψ ∈ A ,  ∑_{σ∈S} Δ_{σ}f_{R} ⊗ ( ∑_{\begin{matrix}φ∈A , α∈Aut(E,R) \\ Γ_{ψ}Λ_{φ}=Δ_{σα}R \end{matrix}} λ_{φ}Δ_{α}v) = 0 .

By Proposition 4.5, P_{E}f_{R} is a (P_{E}, k Aut(E, R))-bimodule with a k-basis consisting of the elements Δ_{τ} f_{R}, for τ ∈ Σ_{E}. Therefore,

P_{E}f_{R} = ⨁_{σ∈S} Δ_{σ}f_{R} · (k Aut(E, R))

and it follows that

P_{E}f_{R} ⊗_{k Aut(E,R)} V = ⨁_{σ∈S} Δ_{σ}f_{R} ⊗_{k Aut(E,R)} V .

Since the sum is direct and since f_{R} ⊗_{k Aut(E,R)} V ≅ V because the right action of Aut(E, R) on f_{R} is free, each inner sum in (8.4) is zero. In particular, taking σ = id (which we may choose in S), we get :

(8.5)  for every ψ ∈ A ,  ∑_{\begin{matrix}φ∈A , α∈Aut(E,R) \\ Γ_{ψ}Λ_{φ}=Δ_{α}R \end{matrix}} λ_{φ}Δ_{α}v = 0 .

Let us analyze the condition Γ_{ψ}Λ_{φ} = Δ_{α}R. For any given x ∈ X, we can choose e = ψ(x) and f = φ(x) and we obtain (e, x) ∈ Γ_{ψ} and (x, f) ∈ Λ_{φ}, hence (e, f) ∈ Γ_{ψ}Λ_{φ} = Δ_{α}R, that is, (α^{−1}(e), f) ∈ R. In other words, if we write simply ≤_{R} for the partial order R, we obtain α^{−1}(ψ(x)) ≤_{R} φ(x). This holds for every x ∈ X and we define

ψ ⪯ φ ⟺ ∃ α ∈ Aut(E, R) such that α^{−1}(ψ(x)) ≤_{R} φ(x) for all x ∈ X .

Therefore the condition Γ_{ψ}Λ_{φ} = Δ_{α}R implies that ψ ⪯ φ.

Now we prove that the relation ⪯ is a partial order on the set A. It is reflexive, by taking simply α = id. It is transitive because if α^{−1}(ψ(x)) ≤_{R} φ(x) and β^{−1}(φ(x)) ≤_{R} χ(x) for all x, then

(αβ)^{−1}(ψ(x)) = β^{−1}α^{−1}(ψ(x)) ≤_{R} β^{−1}(φ(x)) ≤_{R} χ(x)

using the fact that β^{−1} ∈ Aut(E, R). Finally, the relation ⪯ is antisymmetric because if α^{−1}(ψ(x)) ≤_{R} φ(x) and β^{−1}(φ(x)) ≤_{R} ψ(x), then

(αβ)^{−1}(ψ(x)) ≤_{R} ψ(x)

from which it follows that

ψ(x) = (αβ)^{−n}(ψ(x)) ≤_{R} (αβ)^{−1}(ψ(x)) ≤_{R} ψ(x) ,

where n is the order of αβ in the group Aut(E, R). But this implies that ψ(x) = (αβ)^{−n}(ψ(x)) = (αβ)^{−1}(ψ(x)), hence

ψ(x) = β^{−1}α^{−1}(ψ(x)) ≤_{R} β^{−1}(φ(x)) ≤_{R} ψ(x) ,

and therefore β^{−1}(φ(x)) = ψ(x). Thus φ and ψ belong to the same orbit under the action of Aut(E, R). This forces φ = ψ because φ and ψ belong to our chosen set A of representatives of the set of left orbits Aut(E, R)\Φ.

In view of proving the linear independence we are looking for, suppose that the coefficients λ_{φ} are not all zero. Choose ψ ∈ A maximal (with respect to ⪯) such that λ_{ψ} ≠ 0. In the sum (8.5), the condition Γ_{ψ}Λ_{φ} = Δ_{α}R implies, as we have seen above, that ψ ⪯ φ. Since ψ is maximal, the sum over φ ∈ A actually runs over the single element ψ and reduces to

∑_{\begin{matrix}α∈Aut(E,R) \\ Γ_{ψ}Λ_{ψ}=Δ_{α}R \end{matrix}} λ_{ψ}Δ_{α}v = 0 .

But the condition Γ_{ψ}Λ_{ψ} = Δ_{α}R implies that α = id because Δ_{E} ⊆ Γ_{ψ}Λ_{ψ}, hence Δ_{α^{−1}} ⊆ Δ_{α^{−1}}Γ_{ψ}Λ_{ψ}, that is, Δ_{α^{−1}} ⊆ R, which can only occur if α = id. It follows that there is a single term in the whole sum (8.5), namely λ_{ψ}v = 0. Since λ_{ψ} ≠ 0, we obtain v = 0, which is impossible since v was chosen nonzero in V. This contradiction shows that all coefficients λ_{φ} are zero, proving the linear independence of the image of A in S_{E,R,V} (X). Therefore |A| ≤ dim (S_{E,R,V} (X)).

Now we need to estimate |A| and, for simplicity, we write e = |E| and x = |X|. Since A is a set of representatives of orbits in Φ under the free action of Aut(E, R), we have |Φ| = | Aut(E, R)| · |A|, so we need to estimate |Φ|. By Lemma 8.1, we have

|Φ| = ∑_{i=0}^{e}(−1)^{e−i}\binom{e}{i} i^{x} = e^{x} + ∑_{i=0}^{e−1}(−1)^{e−i}\binom{e}{i} i^{x} .

Note that the second sum is negative because the number |Φ| of surjective maps X → E is smaller than the number e^{x} of all maps X → E. We can rewrite

|Φ| = e^{x}(1 + ∑_{i=0}^{e−1}(−1)^{e−i}\binom{e}{i} (\frac{i}{e})^{x}) .

Since \frac{i}{e} ≤ \frac{e−1}{e} < 1, the sum can be made as small as we want, provided x is large enough. Therefore there exists a positive integer N and a positive real number a such that a e^{x} ≤ |Φ| whenever x ≥ N. In other words, for any finite set X of cardinality at least N, we have

(8.6)  \frac{a}{| Aut(E, R)|} |E|^{|X|} ≤ \frac{|Φ|}{| Aut(E, R)|} = |A| ≤ dim (S_{E,R,V} (X)) ,

giving the required lower bound for dim (S_{E,R,V} (X)).

We can now characterize finite generation in terms of exponential behavior.

8.7. Theorem. Let M be a correspondence functor over a field k. The following are equivalent :

(a) M is finitely generated.

(b) There exists positive real numbers a, b, r such that dim(M(X)) ≤ a b^{|X|} for every finite set X with |X| ≥ r.

Proof : (a) ⇒ (b). Let M be a quotient of ⨁_{i∈I} kC(−, E) for some finite set E and

some finite index set I. For every finite set X, we have

dim(M(X)) ≤ |I| dim(kC(X, E)) = |I| 2^{|X×E|} = |I|(2^{|E|})^{|X|} .

(b) ⇒ (a). Let P and Q be subfunctors of M such that Q ⊆ P ⊆ M and P/Q simple, hence P/Q ≅ S_{E,R,V} for some triple (E, R, V). We claim that |E| is bounded above. Indeed, for |X| large enough, we have

c|E|^{|X|} ≤ dim(S_{E,R,V} (X))

for some c > 0, by Theorem 8.2, and

dim(S_{E,R,V} (X)) ≤ dim(M(X)) ≤ a b^{|X|}

by assumption. Therefore, whenever |X| ≥ N for some N, we have

c|E|^{|X|} ≤ a b^{|X|} that is, c ≤ a(\frac{b}{|E|})^{|X|} .

Since c > 0, this forces \frac{b}{|E|} ≥ 1 otherwise a(\frac{b}{|E|})^{|X|} is as small as we want. This

shows the bound |E| ≤ b, proving the claim.

For each set E with |E| ≤ b, we choose a basis {m_{i} | 1 ≤ i ≤ n_{E}} of M(E) and we use Yoneda’s lemma to construct a morphism ψ_{i}^{E} : kC(−, E) → M such that, on evaluation at E, we have ψ_{i,E}^{E}(Δ_{E}) = m_{i}. Starting from the direct sum of n_{E} copies of kC(−, E), we obtain a morphism

ψ^{E} : kC(−, E)^{n_{E}} → M ,

such that, on evaluation at E, the morphism ψ_{E}^{E} : kC(E, E)^{n_{E}} → M(E) is surjective, because the basis of M(E) is in the image. Now the sum of all such morphisms ψ^{E} yields a morphism

ψ : ⨁_{|E|≤b} kC(−, E)^{n_{E}} ⟶ M

which is surjective on evaluation at every set E with |E| ≤ b.

Let N = Im(ψ) and suppose ab absurdo that N ≠ M. Let F be a minimal set such that M(F)/N(F) ≠ {0}. Since ψ is surjective on evaluation at every set E with |E| ≤ b, we must have |F | > b. Now M(F)/N(F) is a module for the finitedimensional algebra R_{F} = kC(F, F) and, by minimality of F, inessential relations act by zero on M(F)/N(F). Let W be a simple submodule of M(F)/N(F) as a module for the essential algebra E_{F}. Associated with W, consider the simple functor S_{F,W}. (Actually, W is parametrized by a pair (R, V) and S_{F,W} = S_{F,R,V} (see Theorem 4.6), but we do not need this.) Now the module W = S_{F,W} (F) is isomorphic to a subquotient of M(F)/N(F). By Proposition 2.8, S_{F,W} is isomorphic to a subquotient of M/N. By the claim proved above, we obtain |F | ≤ b. This contradiction shows that N = M, that is, ψ is surjective. Therefore M is isomorphic, via ψ, to a quotient of ⨁_{|E|≤b} kC(−, E)^{n_{E}}. By Proposition 6.4, M is finitely

generated.

9. Finite length

Using the exponential behaviour proved in the previous section, we now show that, if our base ring k is a field, then every finitely generated correspondence functor has finite length. We first need a lemma.

9.1. Lemma. Let k be a field and let M be a finitely generated correspondence functor over k.

(a) M has a maximal subfunctor.

(b) Any subfunctor of M is finitely generated.

Proof : (a) Since M is finitely generated, M is generated by M(E) for some finite set E (Proposition 6.4). Let N be a maximal submodule of M(E) as a R_{E}- module. Note that N exists because M(E) is finite-dimensional by Lemma 6.3. Then M(E)/N is a simple R_{E}-module. By Proposition 2.8, 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.

(b) Let N be a subfunctor of M. Since M is finitely generated, there exist positive numbers a, b such that, for every large enough finite set X, we have

dim(N(X)) ≤ dim(M(X)) ≤ a b^{|X|} ,

by Theorem 8.7. The same theorem then implies that N is finitely generated.

Lemma 9.1 fails for other categories of functors. For instance, in the category of biset functors, the Burnside functor is finitely generated and has a maximal subfunctor which is not finitely generated (see [Bo1] or [Bo2]).

We now come to one of the most important properties of the category of correspondence functors, namely an artinian property. As for the previous lemma, the theorem is a specific property of the category of correspondence functors.

9.2. Theorem. Let k be a field and let M be a finitely generated correspondence functor over k. Then M has finite length (that is, M has a finite composition series).

Proof : By Lemma 9.1, M has a maximal subfunctor F_{1} and F_{1} is again finitely generated. Then F_{1} has a maximal subfunctor F_{2} and F_{2} is again finitely generated. We construct in this way a sequence of subfunctors

(9.3)  M = F_{0} ⊃ F_{1} ⊃ F_{2} ⊃ …

such that F_{i}/F_{i+1} is simple whenever F_{i} ≠ 0. We claim that the sequence is finite, that is, F_{m} = 0 for some m.

Let F_{i}/F_{i+1} be one simple subquotient, hence F_{i}/F_{i+1} ≅ S_{E,R,V} for some triple (E, R, V). By Theorem 8.7, since M is finitely generated, there exist positive numbers a, b such that, for every large enough finite set X, we have

dim(M(X)) ≤ a b^{|X|} .

Therefore dim(S_{E,R,V} (X)) ≤ a b^{|X|}. By Theorem 8.2, there exists some constant c > 0 such that c |E|^{|X|} ≤ dim(S_{E,R,V} (X)) for |X| large enough. So we obtain c |E|^{|X|} ≤ a b^{|X|} for |X| large enough, hence |E| ≤ b. This implies that the simple functor F_{i}/F_{i+1} ≅ S_{E,R,V} belongs to a finite set of isomorphism classes of simple functors, because there are finitely many sets |E| with |E| ≤ b and, for any of them, finitely many order relations R on E, and then in turn finitely many k Aut(E, R)- simple modules V (up to isomorphism).

Therefore, if the series (9.3) of subfunctors F_{i} was infinite, then some simple functor S_{E,R,V} would occur infinitely many times (up to isomorphism). But then, on evaluation at E, the simple R_{E}-module S_{E,R,V} (E) would occur infinitely many times in M(E). This is impossible because M(E) is finite-dimensional by Lemma 6.3.

Theorem 9.2 was obtained independently by Gitlin [Gi] (for a field k of characteristic zero, or algebraically closed), using a criterion for finite length proved recently by Wiltshire-Gordon [WG].

10. Projective functors and duality

This section is devoted to projective correspondence functors, mainly in the case where k is a field. An important ingredient is the use of duality.

Recall that, by Lemma 7.3, if a projective correspondence functor M is generated by M(E), then M(X) is a projective R_{X}-module, for every set X with |X| ≥ |E|. Recall also that, by Lemma 7.3 again, a projective correspondence functor M is isomorphic to L_{E,M(E)} whenever M is generated by M(E). Thus if we work with functors having bounded type, we can assume that projective functors have the form L_{E,V} for some R_{E}-module V. In such a case, we can also enlarge E because L_{E,V} ≅ L_{F,V↑_{E}^{F}} whenever |F | ≥ |E| (see Proposition 7.5).

10.1. Lemma. Let k be a commutative ring and consider the correspondence functor L_{E,V} for some finite set E and some R_{E}-module V.

(a) L_{E,V} is projective if and only if V is a projective R_{E}-module.

(b) L_{E,V} is finitely generated projective if and only if V is a finitely generated projective R_{E}-module.

(c) L_{E,V} is indecomposable projective if and only if V is an indecomposable projective R_{E}-module.

Proof : (a) If L_{E,V} is projective, then V is projective by Lemma 7.3. Conversely, if V is projective, then L_{E,V} is projective by Lemma 2.4.

(b) If V is a finitely generated R_{E}-module, then L_{E,V} is finitely generated by Corollary 6.5. If L_{E,V} is finitely generated, then its evaluation L_{E,V} (E) = V is finitely generated by Lemma 6.3.

(c) By the adjunction property of Lemma 2.4, End_{F_{k}}(L_{E,V}) ≅ End_{R_{E}}(V), so L_{E,V} is indecomposable if and only if V is indecomposable.

Our main duality result has two aspects, which we both include in the following theorem. The notion of symmetric algebra is standard over a field and can be defined over any commutative ring as in [Br].

10.2. Theorem. Let E be a finite set.

(a) The representable functor kC(−, E) is isomorphic to its dual.

(b) Let R_{E} = kC(E, E) be the k-algebra of relations on E. Then R_{E} is a symmetric algebra. More precisely, let t : R_{E} → k be the k-linear form defined, for all basis elements S ∈ C(E, E), by the formula

t(S) := \{ \begin{matrix}1 & if S ∩ Δ_{E} = ∅ , \\ 0 & otherwise . \end{matrix}

Then t is a symmetrizing form on R_{E}, in the sense that the associated bilinear form (a, b) ↦ t(ab) is symmetric and induces an isomorphism of (R_{E}, R_{E})-bimodules between R_{E} and its dual Hom_{k}(R_{E}, k).

Proof : (a) For every finite set X, consider the symmetric bilinear form

⟨−, −⟩_{X} : kC(X, E) × kC(X, E) ⟶ k

defined, for all basis elements R, S ∈ C(X, E), by the formula

⟨R, S⟩_{X} := \{ \begin{matrix}1 & if R ∩ S = ∅ , \\ 0 & otherwise. \end{matrix}

Then, whenever U ∈ C(Y, X), R ∈ C(Y, E), and S ∈ C(X, E), we have

R ∩ US = ∅ ⟺ ((y, x) ∈ U, (x, e) ∈ S ⇒ (y, e) ∉ R)
⟺ ((x, y) ∈ U^{op}, (y, e) ∈ R ⇒ (x, e) ∉ S)
⟺ U^{op}R ∩ S = ∅ .

It follows that ⟨U^{op}R, S⟩_{X} = ⟨R, US⟩_{Y}. In view of the definition of dual functors (Definition 3.11), this implies that the associated family of linear maps

α_{X} : kC(X, E) ⟶ kC(X, E)^{♮} , S ↦ (R ↦ ⟨R, S⟩_{X})

defines a morphism of correspondence functors α : kC(−, E) ⟶ kC(−, E)^{♮}.

To prove that α is an isomorphism, we fix X and we use the complement ^{c}R = (X × E) − R, for any R ∈ C(X, E). Notice that the matrix of α_{X} relative to the canonical basis C(X, E) and its dual is the product of two matrices C and A, where C_{R,S} = 1 if S = ^{c}R and 0 otherwise, while A is the adjacency matrix of the order relation ⊆. This is because R ∩ S = ∅ if and only if R ⊆ ^{c}S. Clearly C is invertible (it has order 2) and A is unitriangular, hence invertible. Therefore α_{X} is an isomorphism.

(b) Let R, S ∈ C(E, E). Then t(RS) is equal to 1 if RS ∩Δ_{E} = ∅, and t(RS) = 0 otherwise. Now

RS ∩ Δ_{E} = ∅ ⟺ ((e, f) ∈ R ⇒ (f, e) ∉ S)
⟺ R ∩ S^{op} = ∅ .

Therefore t(RS) = ⟨R, S^{op}⟩, where ⟨−, −⟩_{E} is the bilinear form on kC(E, E) defined in (a). Since this bilinear form induces an isomorphism with the dual and since the map S ↦ S^{op} is an isomorphism (it has order 2), the bilinear form associated with t induces also an isomorphism with the dual.

Since (R ∩ S^{op})^{op} = S ∩ R^{op} and ∅^{op} = ∅, we have t(RS) = t(SR) for any relations R and S on E, hence the bilinear form (a, b) ↦ t(ab) is symmetric. It is clear that the associated k-linear map R_{E} → Hom_{k}(R_{E}, k) is a morphism of (R_{E}, R_{E})-bimodules.

10.3. Corollary. If k is a field, then the correspondence functor kC(−, E) is both projective and injective.

Proof : Since passing to the dual reverses arrows and since kC(−, E) is projective, its dual is injective. But kC(−, E) is isomorphic to its dual, so it is both projective and injective.

10.4. Remark. Corollary 10.3 holds more generally when k is a self-injective ring.

10.5. Remark. If R is an order relation on E, then there is a direct sum decomposition

kC(−, E) = kC(−, E)R ⊕ kC(−, E)(1 − R) .

With respect to the bilinear forms defined in the proof of Theorem 10.2, we have

(kC(−, E)R)^{⊥} = kC(−, E)(1 − R^{op})

because

U ∈ (kC(X, E)R)^{⊥} ⟺ ⟨U, V R⟩_{X} = 0 ∀V ∈ kC(X, E)
⟺ ⟨UR^{op}, V ⟩_{X} = 0 ∀V ∈ kC(X, E)
⟺ UR^{op} = 0
⟺ U(1 − R^{op}) = U
⟺ U ∈ kC(X, E)(1 − R^{op}) .

It follows that

kC(−, E)/(kC(−, E)R)^{⊥} = kC(−, E)/kC(−, E)(1 − R^{op}) ≅ kC(−, E)R^{op}

and therefore the bilinear forms ⟨−, −⟩_{X} induce perfect pairings

kC(−, E)R × kC(−, E)R^{op} ⟶ k .

Thus (kC(−, E)R)^{♮} ≅ kC(−, E)R^{op}.

By the Krull-Remak-Schmidt theorem (which holds when k is a field by Proposition 6.6), it is no harm to assume that our functors are indecomposable.

10.6. Theorem. Let k be a field and M be a finitely generated correspondence functor over k. The following conditions are equivalent:

(a) The functor M is projective and indecomposable.

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

(c) The functor M is projective and admits a unique minimal (nonzero) subfunctor.

(d) The functor M is injective and indecomposable.

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

(f) The functor M is injective and admits a unique minimal (nonzero) subfunctor.

Proof : (a) ⇒ (b). Suppose first that M is projective and indecomposable. Then M ≅ L_{E,V} for some finite set E and some indecomposable projective R_{E}-module V (Lemma 7.3). Since R_{E} is a finite dimensional algebra over k, the module V has a unique maximal submodule W. If N is a subfunctor of M, then N(E) is a submodule of V, so there are two cases: either N(E) = V, and then N = M, because M is generated by M(E) = V, or N(E) ⊆ W, and then N(X) ⊆ J_{W} (X) for any finite set X, where

J_{W} (X) = { ∑_{i} φ_{i} ⊗ v_{i} ∈ kC(X, E) ⊗_{R_{E}} V | ∀ψ ∈ C(E, X), ∑_{i}(ψφ_{i}) · v_{i} ∈ W } .

One checks easily that the assignment X ↦ J_{W} (X) is a subfunctor of L_{E,V}, such that J_{W} (E) = W after the identification L_{E,V} (E) ≅ V. (This subfunctor is similar to the one introduced in Lemma 2.5.) In particular J_{W} is a proper subfunctor of L_{E,V}. It follows that J_{W} is the unique maximal proper subfunctor of L_{E,V}, as it contains any proper subfunctor N of L_{E,V}.

(b) ⇒ (a). Suppose that M admits a unique maximal subfunctor N. If M splits as a direct sum M_{1} ⊕ M_{2} of two nonzero subfunctors M_{1} and M_{2}, then M_{1} and M_{2} are finitely generated. Let N_{1} be a maximal subfunctor of M_{1}, and N_{2} be a maximal subfunctor of M_{2}. Such subfunctors exist by Lemma 9.1. Then M_{1} ⊕ N_{2} and N_{1} ⊕ M_{2} are distinct maximal subfunctors of M. This contradiction proves that M is indecomposable.

(a) ⇒ (d). If M is a finitely generated projective functor, then there exists a finite set E such that M is isomorphic to a quotient, hence a direct summand, of ⨁_{i∈I} kC(−, E) for some finite set I (Proposition 6.4). Since k is a field, kC(−, E)

is an injective functor (Corollary 10.3), hence so is the direct sum and its direct summand M.

(d) ⇒ (a). If M is a finitely generated injective functor, then its dual M^{♮} is projective, hence injective, and therefore 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).

Finally, we prove that the well-known property of indecomposable projective modules over a symmetric algebra also holds for correspondence functors. Recall that M/ Rad(M) is the largest semi-simple quotient of M and that Soc(M) is the largest semi-simple subfunctor of M.

10.7. Theorem. Let k be a field.

(a) Let M be a finitely generated projective correspondence functor over k. 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 : (a) By Proposition 6.6, we can assume that M is indecomposable. In this case, by Theorem 10.6, both M/ Rad(M) and Soc(M) are simple functors. By Proposition 6.4, there is a finite set E such that M is a quotient, hence a direct summand, of F = ⨁_{i∈I} kC(−, E) for some finite set I. Since kC(−, E)^{♮} ≅ kC(−, E),

the dual M^{♮} is a direct summand of F^{♮} ≅ F, and both M and M^{♮} are generated by their evaluations at E. Thus M ≅ L_{E,M(E)} and M^{♮} ≅ L_{E,M^{♮}(E)}, by Lemma 7.3. As M is a direct summand of F and M is indecomposable, M is a direct summand of kC(−, E), by the Krull-Remak-Schmidt Theorem (Proposition 6.6). So there is a primitive idempotent e of kC(E, E) ≅ End_{F_{k}}(kC(−, E)) such that M ≅ kC(−, E)e, and we can assume that M = kC(−, E)e.

If V is a finite dimensional k-vector space, and W is a subspace of V, set

W^{⊥} = {φ ∈ Hom_{k}(V, k) | φ(W) = 0} .

If N is a subfunctor of M, the assignment sending a finite set X to N(X)^{⊥} defines a subfunctor N^{⊥} of M^{♮}, and moreover N ↦ N^{⊥} is an order reversing bijection between the set of subfunctors of M and the set of subfunctors of M^{♮}. In particular Soc(M)^{⊥} = Rad(M^{♮}). Hence Soc(M)^{⊥}(E) = ( Soc(M)(E))^{⊥} = Rad(M^{♮})(E).

Now M^{♮} ≠ Rad(M^{♮}), and M^{♮} is generated by M^{♮}(E). Hence Rad(M^{♮})(E) ≠ M^{♮}(E). It follows that Soc(M)(E) ≠ 0. Then Soc(M)(E) ⊆ R_{E}e, and Soc(M)(E) is a left ideal of R_{E}. It follows that Soc(M)(E) is not contained in the kernel of the map t defined in Theorem 10.2, that is t( Soc(M)(E)) ≠ 0. Hence

0 ≠ t( Soc(M)(E)) = t( Soc(M)(E)e) = t(e Soc(M)(E)) ,

and in particular e Soc(M)(E) ≠ 0. Since

e Soc(M)(E) ≅ Hom_{F_{k}} (kC(−, E)e, Soc(M)) ,

there is a nonzero morphism from M = kC(−, E)e to Soc(M), hence a nonzero morphism from M/ Rad(M) to Soc(M). Since M/ Rad(M) and Soc(M) are simple, it is an isomorphism.

(b) First, by Proposition 6.6, both Hom_{F_{k}}(M, N) and Hom_{F_{k}}(N, M) are finite dimensional k-vectors spaces.

Now we can again assume that M is an indecomposable projective and injective functor. For a finitely generated functor N, set α(N) = dim_{k} Hom_{F_{k}}(M, N) and β(N) = dim_{k} Hom_{F_{k}}(N, M). If 0 → N_{1} → N_{2} → N_{3} → 0 is a short exact sequence of finitely generated functors, then α(N_{2}) = α(N_{1}) + α(N_{3}) because M is projective, and β(N_{2}) = β(N_{1}) + β(N_{3}) because M is injective. So, in order to prove (b), as N has finite length, it is enough to assume that N is simple. In that case α(N) = dim_{k} End_{F_{k}}(N) if M/ Rad(M) ≅ N, and α(N) = 0 otherwise. Similarly β(N) = dim_{k} End_{F_{k}}(N) if Soc(M) ≅ N, and β(N) = 0 otherwise. Hence (b) follows from (a).

11. The noetherian case

In this section, we shall assume that the ground ring k is noetherian, in which case we obtain more results about subfunctors. For instance, we shall prove that any subfunctor of a finitely generated functor is finitely generated. It would be interesting to see if the methods developed recently by Sam and Snowden [SS] for showing noetherian properties of representations of categories can be applied for proving the results of this section.

Our first results hold without any assumption on k.

11.1. Notation. Let k be a commutative ring, let E be a finite set, and let M be a correspondence functor over k. We set

\overline{M}(E) := M(E)/ ∑_{E′⊂E} kC(E, E′)M(E′) ,

where the sum runs over proper subsets E′ of E.

Note that if F is any set of cardinality smaller than |E|, then there exists a bijection σ : E′ → F, where E′ is a proper subset of E. It follows that

kC(E, F)M(F) = kC(E, F)R_{σ}M(E′) ⊆ ∑_{E′⊂E} kC(E, E′)M(E′), where R_{σ} ⊆ F × E′

is the graph of σ.

Note also that \overline{M}(E) is a left module for the essential algebra E_{E}, because the ideal I_{E} = ∑_{|Y |<|E|} kC(E, Y)kC(Y, E) of the algebra R_{E} = kC(E, E) acts by zero

on \overline{M}(E).

11.2. Lemma. Let k be a commutative ring, and let E be a finite set. Let M be a correspondence functor over k. If 𝔭 is a prime ideal of k, denote by M_{𝔭} the localization of M at 𝔭, defined by M_{𝔭}(E) = M(E)_{𝔭} for every finite set E.

(a) M_{𝔭} is a correspondence functor over the localization k_{𝔭}.

(b) If M is finitely generated over k, then M_{𝔭} is finitely generated over k_{𝔭}.

(c) For each finite set E, there is an isomorphism of k_{𝔭}C(E, E)-modules

\overline{M}(E)_{𝔭} ≅ \overline{M_{𝔭}}(E) .

Proof : (a) This is straightforward.

(b) If E is a finite set, then clearly kC(−, E)_{𝔭} ≅ k_{𝔭}C(−, E), because this the localization of a free module (on every evaluation). If M is finitely generated, then there is a finite set F such that M is a quotient of ⨁_{i∈I} kC(−, F) for some finite set I.

Then M_{𝔭} is a quotient of the functor ⨁_{i∈I} kC(−, F)_{𝔭} ≅ ⨁_{i∈I} k_{𝔭}C(−, F), hence it is a

finitely generated functor over k_{𝔭}.

(c) Since localization is an exact functor, the exact sequence of k-modules

⨁_{E′⊂E} kC(E, E′)M(E′) → M(E) → \overline{M}(E) → 0

gives the exact sequence of k_{𝔭}-modules

⨁_{E′⊂E} (kC(E, E′)M(E′))_{𝔭} → M(E)_{𝔭} → \overline{M}(E)_{𝔭} → 0 .

Now clearly (kC(E, E′)M(E′))_{𝔭} = k_{𝔭}C(E, E′)M(E′)_{𝔭} = k_{𝔭}C(E, E′)M_{𝔭}(E′) for each E′ ⊂ E. Hence we get an exact sequence

⨁_{E′⊂E} k_{𝔭}C(E, E′)M_{𝔭}(E′) → M_{𝔭}(E) → \overline{M}(E)_{𝔭} → 0 ,

and it follows that \overline{M}(E)_{𝔭} ≅ \overline{M_{𝔭}}(E).

11.3. Proposition. Let k be a commutative ring, let E be a finite set, and let M be a correspondence functor such that \overline{M}(E) ≠ 0.

(a) There exists a prime ideal 𝔭 of k such that \overline{M_{𝔭}}(E) ≠ 0.

(b) If moreover M(E) is a finitely generated k-module, then there exist subfunctors A and B of M_{𝔭} such that 𝔭M_{𝔭} ⊆ A ⊂ B, and a simple module V for the essential algebra E_{E} of E over k(𝔭) such that B/A ≅ S_{E,V}, where k(𝔭) = k_{𝔭}/𝔭k_{𝔭}.

(c) In this case, there exist positive numbers c and d such that

c |E|^{|X|} ≤ dim_{k(𝔭)}(M_{𝔭}/𝔭M_{𝔭})(X)

whenever X is a finite set such that |X| ≥ d.

Proof : (a) This follows from the well-known fact that the localization map \overline{M}(E) ⟶ ∏_{𝔭∈Spec(k)} \overline{M}(E)_{𝔭} is injective, and from the isomorphism \overline{M}(E)_{𝔭} ≅ \overline{M_{𝔭}}(E)

of Lemma 11.2.

(b) Set N = M_{𝔭}/𝔭M_{𝔭} where 𝔭 is the prime ideal obtained in (a). Then N is a correspondence functor over k(𝔭). Suppose that \overline{N}(E) = 0. Then

M_{𝔭}(E) = 𝔭M_{𝔭}(E) + ∑_{E′⊂E} k_{𝔭}C(E, E′)M_{𝔭}(E′) .

Since M(E) is a finitely generated k-module, M_{𝔭}(E) is a finitely generated k_{𝔭}- module, and Nakayama’s lemma implies that

M_{𝔭}(E) = ∑_{E′⊂E} k_{𝔭}C(E, E′)M_{𝔭}(E′) ,

that is, \overline{M_{𝔭}}(E) = 0. This contradicts (a) and shows that \overline{N}(E) ≠ 0.

Now \overline{N}(E) is a nonzero module for the essential algebra E_{E} of E over k(𝔭), and it is finite dimensional over k(𝔭) (because M_{𝔭}(E) is a finitely generated k_{𝔭}- module). Hence it admits a simple quotient V as E_{E}-module. Then V can be viewed as a simple k(𝔭)R_{E}-module by inflation, and it is also a quotient of N(E). By Proposition 2.8, there exist subfunctors A/𝔭M_{𝔭} ⊂ B/𝔭M_{𝔭} of N such that B/A is isomorphic to the simple functor S_{E,V}, proving (b).

(c) By (b) and Theorem 8.2, there exist positive numbers c and d such that

c |E|^{|X|} ≤ dim_{k(𝔭)}(B/A)(X)

whenever X is a finite set such that |X| ≥ d. Assertion (c) follows.

Now we assume that k is noetherian and we can state the critical result.

11.4. Theorem. Let k be a commutative noetherian ring. Let N be a subfunctor of a correspondence functor M over k. If E and Y are finite sets such that M is generated by M(E) and \overline{N}(Y) ≠ 0, then |Y | ≤ 2^{|E|}.

Proof : Since M is generated by M(E), choosing a set I of generators of M(E) yields a surjection Φ : P = ⨁_{i∈I} kC(−, E) → M. Let L = Φ^{−1}(N). Since Φ induces

a surjection \overline{L}(Y) → \overline{N}(Y), and since P is generated by P (E), we can replace M by P and N by L. Hence we now assume that N is a subfunctor of ⨁_{i∈I} kC(−, E).

Since \overline{N}(Y) ≠ 0, there exists

m ∈ N(Y) − ∑_{Y′⊂Y} kC(Y, Y′)N(Y′) .

Let N′ be the subfunctor of N generated by m. Then clearly \overline{N′}(Y) ≠ 0, because

m ∈ N′(Y) − ∑_{Y′⊂Y} kC(Y, Y′)N′(Y′) .

Moreover N′(Y) = kC(Y, Y)m is a finitely generated k-module, and there is a finite subset S of I such that m ∈ ⨁_{i∈S} kC(Y, E). Therefore N′ ⊆ ⨁_{i∈S} kC(−, E). Replacing

N by N′, we can assume moreover that the set I is finite. In other words, there exists an integer s ∈ ℕ such that N ⊆ kC(−, E)^{⊕s}.

Now by Proposition 11.3, there exists a prime ideal 𝔭 of k such that \overline{N_{𝔭}}(Y) ≠ 0. Moreover N(Y) is a submodule of kC(Y, E)^{⊕s}, which is a finitely generated (free) k-module. Since k is noetherian, it follows that N(Y) is a finitely generated kmodule.

By Proposition 11.3, there exist subfunctors A ⊂ B of N_{𝔭} such that B/A is isomorphic to a simple functor of the form S_{Y,V}, where V is a simple module for the essential algebra of Y over k(𝔭). In particular Y is minimal such that (B/A)(Y) ≠ 0, thus (\overline{B/A})(Y) ≅ (B/A)(Y) ≅ V.

It follows that \overline{B}(Y) ≠ 0, and B is a subfunctor of k_{𝔭}C(−, E)^{⊕s}. In other words, replacing k by k_{𝔭} and N by B, we can assume that k is a noetherian local ring, that 𝔭 is the unique maximal ideal of k, and that N has a subfunctor A such that N/A is isomorphic to S_{Y,V}, where V is a simple module for the essential algebra E_{Y} over k/𝔭.

We claim that there exists an integer n ∈ ℕ such that

N(Y) ≠ A(Y) + (𝔭^{n}C(Y, E)^{⊕s} ∩ N(Y)) .

Indeed N(Y) is a submodule of the finitely generated k-module kC(Y, E)^{⊕s}. By the Artin-Rees lemma (see Theorem 8.5 in [Ma]), there exists an integer l ∈ ℕ such that for any n ≥ l

𝔭^{n}C(Y, E)^{⊕s} ∩ N(Y) = 𝔭^{n−l}(𝔭^{l}C(Y, E)^{⊕s} ∩ N(Y)) .

Let m_{1}, …, m_{r} be generators of N(Y) as a k-module. Suppose that n > l and that N(Y) = A(Y) + (𝔭^{n}C(Y, E)^{⊕s} ∩ N(Y)). Then

N(Y) = A(Y) + 𝔭^{n−l}(𝔭^{l}C(Y, E)^{⊕s} ∩ N(Y)) .

It follows that for each i ∈ {1, …, r}, there exist a_{i} ∈ A(Y) and scalars λ_{i,j} ∈ 𝔭^{n−l}, for 1 ≤ j ≤ r, such that

m_{i} = a_{i} + ∑_{j=1}^{r} λ_{i,j}m_{j} .

In other words the sequence (a_{i})_{i=1,...,r} is the image of the sequence (m_{i})_{i=1,...,r} under the matrix J = id_{r} −Λ, where Λ is the matrix of coefficients λ_{i,j}, and id_{r} is the identity matrix of size r. Since Λ has coefficients in 𝔭^{n−l} ⊆ 𝔭, the determinant of J is congruent to 1 modulo 𝔭, hence J is invertible. It follows that the m_{i}’s are linear combinations of the a_{j}’s with coefficients in k. Hence m_{i} ∈ A(Y) for 1 ≤ i ≤ r, thus N(Y) = A(Y). This is a contradiction since (N/A)(Y) ≅ V ≠ 0. This proves our claim.

We have obtained that N ≠ A + (𝔭^{n}C(−, E)^{⊕s} ∩ N). Since N/A is simple, it follows that 𝔭^{n}C(−, E)^{⊕s} ∩ N = 𝔭^{n}C(−, E)^{⊕s} ∩ A.

Now we reduce modulo 𝔭^{n} and we let respectively Â and N̂ denote the images of A and N in the reduction (k/𝔭^{n})C(−, E)^{⊕s}. Then

N̂/Â = ((N + 𝔭^{n}C(−, E)^{⊕s})/𝔭^{n}C(−, E)^{⊕s})/((A + 𝔭^{n}C(−, E)^{⊕s})/𝔭^{n}C(−, E)^{⊕s})
≅ (N/(𝔭^{n}C(−, E)^{⊕s} ∩ N))/(A/(𝔭^{n}C(−, E)^{⊕s} ∩ A))
≅ N/A ,

and this is isomorphic to the simple functor S_{Y,V} over the field k/𝔭. Hence for any finite set X, the module N̂(X)/Â(X) is a (k/𝔭)-vector space. Moreover, by Proposition 11.3, there exist positive numbers c and d such that the dimension of this vector space is larger than c |Y |^{|X|} whenever |X| ≥ d.

Now for any finite set X, the module (k/𝔭^{n})C(X, E)^{⊕s} is filtered by the submodules Γ_{j} = (𝔭^{j}/𝔭^{n})C(X, E)^{⊕s}, for j = 1, …, n − 1, and the quotient Γ_{j}/Γ_{j+1} is a vector space over k/𝔭, of dimension sd_{j} 2^{|X||E|}, where d_{j} = dim_{k/𝔭}(𝔭^{j}/𝔭^{j+1}). It follows that, for |X| ≥ d,

c |Y |^{|X|} ≤ dim_{k/𝔭} (N̂(X)/Â(X)) ≤ s( ∑_{j=0}^{n−1} d_{j})2^{|X||E|} .

As |X| tends to infinity, this forces |Y | ≤ 2^{|E|}, completing the proof of Theorem 11.4.

11.5. Corollary. Let k be a commutative noetherian ring and let N be a subfunctor of a correspondence functor M over k.

(a) If E is a finite set such that M is generated by M(E) and if F is a finite set with |F | ≥ 2^{|E|}, then N is generated by N(F).

(b) If M has bounded type, then N has bounded type. In particular, over k, any correspondence functor of bounded type has a bounded presentation.

(c) If M is finitely generated, then N is finitely generated. In particular, over k, any finitely generated correspondence functor is finitely presented.

Proof : (a) Let E be a finite set such that M is generated by M(E). If X is a finite set such that \overline{N}(X) ≠ 0, then |X| ≤ 2^{|E|}, by Theorem 11.4. For each integer e ≤ 2^{|E|}, let [e] = {1, …, e} and choose a subset S_{e} of N([e]) which maps to a generating set of \overline{N}([e]) as a k-module. Each i ∈ S_{e} yields a morphism ψ_{e,i} : kC(−, [e]) → N. Let

Q = ⨁_{e≤2^{|E|}} ⨁_{i∈S_{e}} kC(−, [e])  and  Ψ = ∑_{{e≤2^{|E|} \atop i∈S_{e}}} ψ_{e,i} : Q → N .

Then by construction the induced map

\overline{Ψ}_{X} : \overline{Q}(X) → \overline{N}(X)

is surjective, for any finite set X, because either \overline{N}(X) = 0 or |X| = e ≤ 2^{|E|}. Suppose that Ψ : Q → N is not surjective and let A be a set of minimal cardinality such that Ψ_{A} : Q(A) → N(A) is not surjective. Let l ∈ N(A) − Im Ψ_{A}. Since the map \overline{Ψ}_{A} is surjective, there is an element q ∈ Q(A) and elements l_{e} ∈ N([e]) and R_{e} ∈ kC(A, [e]), for e < |A|, such that

l = Ψ_{A}(q) + ∑_{e<|A|} R_{e}l_{e} .

The minimality of A implies that the map Ψ_{[e]} : Q([e]) → N([e]) is surjective for each e < |A|, so there are elements q_{e} ∈ Q([e]), for e < |A|, such that Ψ_{[e]}(q_{e}) = l_{e}. It follows that l = Ψ_{A}(q + ∑_{e<|A|} R_{e}q_{e}), thus l ∈ Im Ψ_{A}. This contradiction proves

that the morphism Ψ : Q → N is surjective.

Now let F be a set with |F | ≥ 2^{|E|}. For each e ≤ 2^{|E|}, the representable functor kC(−, [e]) is generated by its evaluation at [e], hence also by its evaluation at F, because kC(−, [e]) is a direct summand of kC(−, F) by Corollary 3.5. Therefore Q is generated by Q(F). Since Ψ : Q → N is surjective, it follows that N is generated by N(F).

(b) This follows clearly from (a).

(c) If now M is finitely generated, then the same argument applies, but we can assume moreover that all the sets S_{e} appearing in the proof of (a) are finite, since for any finite set X, the module N(X) is finitely generated, being a submodule of the finitely generated module M(X). It follows that the functor Q of the proof of (a) is finitely generated and this proves (c).

It follows from (b) and Theorem 7.4 that, whenever k is noetherian, any correspondence functor of bounded type is isomorphic to L_{F,V} for some F and V. We shall return to this in Theorem 12.2 below. 11.6. Notation. We denote by F_{k}^{b} the full subcategory of F_{k} consisting of correspondence functors having bounded type and by F_{k}^{f} the full subcategory of F_{k} consisting of finitely generated functors.

11.7. Corollary. Let k be a commutative noetherian ring. Then the categories F_{k}^{b} and F_{k}^{f} are abelian full subcategories of F_{k}.

Proof : Any quotient of a functor of bounded type has bounded type and any quotient of a finitely generated functor is finitely generated. When k is noetherian, any subfunctor of a functor of bounded type has bounded type and any subfunctor of a finitely generated functor is finitely generated, by Corollary 11.5.

12. Stabilization results

Recall from Lemma 2.5 that for any finite set E and any R_{E}-module V, we have defined a subfunctor J_{E,V} of L_{E,V} by setting

J_{E,V} (X) = { ∑_{i} R_{i} ⊗_{R_{E}} v_{i} | R_{i} ∈ C(X, E), v_{i} ∈ V, ∀S ∈ C(E, X), ∑_{i}(SR_{i})v_{i} = 0} .

Moreover J_{E,V} (E) = 0 and S_{E,V} = L_{E,V} /J_{E,V}.

We have seen in Proposition 7.5 that L_{F,V↑_{E}^{F}} ≅ L_{E,V} whenever |F | ≥ |E|. The subfunctor J_{F,V↑_{E}^{F}} vanishes at F, hence also at E, so that J_{F,V↑_{E}^{F}} ⊂ J_{E,V}. When k is noetherian, we show that this decreasing sequence reaches zero.

12.1. Theorem. Let k be a commutative noetherian ring, let E be a finite set, and let V be an R_{E}-module. For any finite set F such that |F | ≥ 2^{|E|}, we have J_{F,V↑_{E}^{F}} = 0.

Proof : Let F be a finite set. By Proposition 7.5, there is an isomorphism L_{F,V↑_{E}^{F}} ≅ L_{E,V}. Thus J_{F,V↑_{E}^{F}} is isomorphic to a subfunctor of L_{E,V}. Since J_{F,V↑_{E}^{F}}(F) = 0, it follows from Corollary 3.7 that J_{F,V↑_{E}^{F}}(X) = 0 for any finite set X with |X| ≤ |F |.

We now assume that J_{F,V↑_{E}^{F}} ≠ 0 and we prove that |F | < 2^{|E|}. Let Y be a set of minimal cardinality such that J_{F,V↑_{E}^{F}}(Y) ≠ 0. Then |Y | > |F |. Moreover \overline{J_{F,V↑_{E}^{F}}}(Y) ≅ J_{F,V↑_{E}^{F}}(Y) ≠ 0, hence |Y | ≤ 2^{|E|} by Theorem 11.4, because J_{F,V↑_{E}^{F}} is (isomorphic to) a subfunctor of L_{E,V}, which is generated by L_{E,V} (E) = V. It follows that |F | < |Y | ≤ 2^{|E|}.

We now show that, over a noetherian ring, any correspondence functor of bounded type is isomorphic to L_{F,V} for some F and V, or also isomorphic to S_{G,W} for some G and W (where the symbol S_{G,W} refers to Notation 2.6).

12.2. Theorem. Let k be a commutative noetherian ring. Let M be a correspondence functor over k generated by M(E), for some finite set E.

(a) For any finite set F such that |F | ≥ 2^{|E|}, the counit morphism η_{M,F} : L_{F,M(F)} → M is an isomorphism.

(b) For any finite set G such that |G| ≥ 2^{2^{|E|}}, we have M ≅ L_{G,M(G)} and J_{G,M(G)} = 0, hence M ≅ S_{G,M(G)}.

Proof : (a) If M is generated by M(E), then there is a set I and a surjective morphism P = ⨁_{i∈I} kC(−, E) → M. If F is a finite set with |F | ≥ 2^{|E|}, then by

Corollary 11.5 the kernel K of this morphism is generated by K(F). Then K is in turn covered by a projective functor Q and we have a bounded presentation

Q → P → M → 0

with both Q and P generated by their evaluation at F. By Theorem 7.4, the counit morphism η_{M,F} : L_{F,M(F)} → M is an isomorphism.

(b) For any finite set F such that |F | ≥ 2^{|E|}, we have M ≅ L_{F,M(F)} by (a). For any finite set G such that |G| ≥ 2^{|F |}, that is, |G| ≥ 2^{2^{|E|}}, we obtain J_{G,M(F)↑_{F}^{G}} = 0 by Theorem 12.1. It follows that

M ≅ L_{F,M(F)} ≅ L_{G,M(F)↑_{F}^{G}} = S_{G,M(F)↑_{F}^{G}} .

Finally, notice that, by the definition of L_{F,M(F)}, we have M(G) ≅ L_{F,M(F)}(G) = M(F)↑_{F}^{G}, so we obtain M ≅ L_{G,M(G)} = S_{G,M(G)}.

Other kinds of stabilizations also occur, as the next theorems show.

12.3. Theorem. Let k be a commutative noetherian ring, let M and N be correspondence functors over k, and let E and F be finite sets.

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

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

is an isomorphism.

(b) If M has bounded type, then for any integer i ∈ ℕ, there exists an integer n_{i} such that the evaluation map

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

is an isomorphism whenever |F | ≥ n_{i}.

Proof : (a) By Theorem 12.2, we have an isomorphism M ≅ L_{F,M(F)} for |F | ≥ 2^{|E|}. Hence

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

where the last isomorphism comes from the adjunction of Lemma 2.4, and is given by evaluation at F.

(b) This assertion will follow from (a) by décalage and induction on i. If M is generated by M(E), then there is an exact sequence of correspondence functors

0 → L → P → M → 0

where P is projective and generated by P (E). This gives an exact sequence

0 → Hom_{F_{k}}(M, N) → Hom_{F_{k}}(P, N) → Hom_{F_{k}}(L, N) → Ext_{F_{k}}^{1}(M, N) → 0 ,

and isomorphisms Ext_{F_{k}}^{i}(M, N) ≅ Ext_{F_{k}}^{i−1}(L, N) for i ≥ 2.

Now L has bounded type by Corollary 11.5, and P (F) is a projective R_{F} -module by Lemma 7.3, whenever |F | is large enough. It follows that there is also an exact sequence

0 →Hom_{R_{F}} (M(F), N(F)) → Hom_{R_{F}} (P (F), N(F)) →
Hom_{R_{F}} (L(F), N(F)) →Ext_{R_{F}}^{1} (M(F), N(F)) →0

and isomorphisms Ext_{R_{F}}^{i} (M(F), N(F)) ≅ Ext_{R_{F}}^{i−1}(L(F), N(F)) for i ≥ 2, whenever F is large enough.

Now by (a), the exact sequences

0 → Hom_{F_{k}}(M, N) → Hom_{F_{k}}(P, N) → Hom_{F_{k}}(L, N)

and

0 → Hom_{R_{F}} (M(F), N(F)) → Hom_{R_{F}} (P (F), N(F)) → Hom_{R_{F}} (L(F), N(F))

are isomorphic for F large enough. It follows that

Ext_{F_{k}}^{1}(M, N) ≅ Ext_{R_{F}}^{1} (M(F), N(F)) .

Similarly, for each i ≥ 2, when F is large enough (depending on i), there are isomorphisms Ext_{F_{k}}^{i}(M, N) ≅ Ext_{R_{F}}^{i} (M(F), N(F)).

There is also a stabilization result involving the Tor groups.

12.4. Theorem. Let k be a commutative noetherian ring, and E be a finite set. If F is a finite set with |F | ≥ 2^{2^{|E|}}, then for any finite set X and any left R_{E}-module V, we have

Tor_{1}^{R_{F}} (kC(X, F), V ↑_{E}^{F} ) = 0 .

Proof : Let V be a left R_{E}-module and s : Q → V be a surjective morphism of R_{E}-modules, where Q is projective. Let K denote the kernel of the surjective morphism

L_{E,s} : L_{E,Q} → L_{E,V} .

Since L_{E,Q} is generated by L_{E,Q}(E) ≅ Q, it follows from Corollary 11.5 that K is generated by K(G) whenever G is a finite set with |G| ≥ 2^{|E|}. Now by Theorem 12.2, the counit L_{F,K(F)} → K is an isomorphism whenever F is a finite set with |F | ≥ 2^{|G|}. Hence if |F | ≥ 2^{2^{|E|}}, we have an exact sequence of correspondence functors

(12.5)  0 → L_{F,W_{F}} → L_{E,Q} → L_{E,V} → 0 ,

where W_{F} = K(F), and where the middle term L_{E,Q} is projective. Evaluating this sequence at F, we get the exact sequence of R_{F} -modules

0 → W_{F} → kC(F, E) ⊗_{R_{E}} Q → kC(F, E) ⊗_{R_{E}} V → 0 ,

where the middle term is projective.

Let X be a finite set. Applying the functor kC(X, F) ⊗_{R_{F}} (−) to this sequence yields the exact sequence

0 → Tor_{1}^{R_{F}} (kC(X, F), V ↑_{E}^{F} ) →

kC(X, F) ⊗_{R_{F}} W_{F} → kC(X, E) ⊗_{R_{E}} Q → kC(X, E) ⊗_{R_{E}} V → 0 ,

because kC(X, F) ⊗_{R_{F}} kC(F, E) ≅ kC(X, E) by Corollary 3.8, as |F | ≥ |E|. On the other hand, evaluating at X the exact sequence 12.5 gives the exact sequence

0 → kC(X, F) ⊗_{R_{F}} W_{F} → kC(X, E) ⊗_{R_{E}} Q → kC(X, E) ⊗_{R_{E}} V → 0 .

In both latter exact sequences, the maps are exactly the same. It follows that

Tor_{1}^{R_{F}} (kC(X, F), V ↑_{E}^{F} ) = 0 ,

as was to be shown.

As a final approach to stabilization, we introduce the following definition.

12.6. Definition. Let G_{k} denote the following category:

• The objects of G_{k} are pairs (E, U) consisting of a finite set E and a left R_{E}-module U.

• 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 of morphisms φ : (E, U) → (F, V) and ψ : (F, V) → (G, W) is the morphism obtained by composition

U →^{φ} kC(E, F) ⊗_{R_{F}} V ⟶^{id ⊗ψ} kC(E, F) ⊗_{R_{F}} kC(F, G) ⊗_{R_{G}} W ⟶^{μ⊗id} kC(E, G) ⊗_{R_{G}} W ,

where μ : kC(E, F) ⊗_{R_{F}} kC(F, G) → kC(E, G) is the composition in the category kC.

• The identity morphism of (E, U) is the canonical isomorphism

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

resulting from the definition R_{E} = kC(E, E).

One can check easily that G_{k} is a k-linear category.

12.7. Theorem. Let k be a commutative ring. Let 𝕃 : G_{k} → F_{k}^{b} be the assignment sending (E, U) to L_{E,U}, and φ : (E, U) → (F, V) to the morphism L_{E,U} → L_{F,V} associated by adjunction to φ : U → L_{F,V} (E).

(a) 𝕃 is a fully faithful k-linear functor.

(b) 𝕃 is an equivalence of categories if k is noetherian.

(c) G_{k} is an abelian category if k is noetherian.

Proof : It is straightforward to check that 𝕃 is a k-linear functor. It is moreover fully faithful, since

Hom_{F_{k}^{b}}(L_{E,U}, L_{F,V}) ≅ Hom_{R_{E}}(U, kC(E, F) ⊗_{F} V ) ≅ Hom_{G_{k}}((E, U), (F, V)) .

Finally, if k is noetherian, then any correspondence functor M of bounded type is isomorphic to a functor of the form L_{E,U}, by Theorem 12.2, for E large enough and U = M(E). Hence 𝕃 is essentially surjective, so it is an equivalence of categories. In particular, G_{k} is abelian by Corollary 11.7.

References

[AF] F. W. Anderson, K. R. Fuller. Rings and Categories of Modules, Graduate Texts in Mathematics 13, Springer Verlag, 1992.

[Bo1] S. Bouc. Foncteurs d’ensembles munis d’une double action, J. Algebra 183 (1996), 664–736.

[Bo2] S. Bouc. Biset functors for finite groups, Springer Lecture Notes in Mathematics no. 1990 (2010).

[Br] M. Broué. Higman’s criterion revisited, Michigan Math. J. 58 (2009), no. 1, 125–179.

[BST] S. Bouc, R. Stancu, J. Thévenaz. Simple biset functors and double Burnside ring, J. Pure Appl. Alg. 217 (2013), 546–566.

[BT1] S. Bouc, J. Thévenaz. The algebra of essential relations on a finite set, J. reine angew. Math. 712 (2016), 225–250.

[BT2] S. Bouc, J. Thévenaz. Correspondence functors and lattices, preprint, 2017.

[BT3] S. Bouc, J. Thévenaz. The algebra of Boolean matrices, correspondence functors, and simplicity, in preparation.

[CEF] T. Church, J. Ellenberg, B. Farb. FI-modules and stability for representations of symmetric groups, Duke Math. J. 164 (2015), no. 9, 1833–1910.

[CP] A. H. Clifford, G. B. Preston. The algebraic theory of semigroups, Vol. I, Mathematical Surveys, No. 7, American Mathematical Society, Providence,1961.

[Gi] A. Gitlin. New examples of dimension zero categories and a computer program for calculations in representation theory, Undergraduate research project, University of Michigan, 2015. Advisor: J. D. Wiltshire-Gordon.

[GMS] O. Ganyushkin, V. Mazorchuk, B. Steinberg. On the irreducible representations of a finite semigroup, Proc. Amer. Math. Soc. 137 (2009), 3585–3592.

[HY] A. Hida, N. Yagita. Representations of the double Burnside algebra and cohomology of the extraspecial p-group, J. Algebra 409 (2014), 265–319.

[Ki] K. H. Kim. Boolean matrix theory and applications, Dekker, 1982.

[Ma] H. Matsumura. Commutative ring theory, Cambridge Studies in Advanced Mathematics, Vol. 8, Cambridge, 1989.

[Pi] T. Pirashvili. Dold-Kan type theorem for Gamma-groups, Math. Ann. 318 (2000), 277–298.

[PS] A. Putman, S. V. Sam. Representation stability and finite linear groups, Duke Math. J. 166 (2017), no. 13, 2521–2598.

[SS] S. V. Sam, A. Snowden. Gröbner methods for representations of combinatorial categories, J. Amer. Math. Soc. 30 (2017), 159–203.

[St] R. P. Stanley. Enumerative Combinatorics, Vol. I, Wadsworth & Brooks/Cole, Monterey, 1986.

[WG] J. D. Wiltshire-Gordon. Categories of dimension zero, preprint, 2015, arXiv:1508.04107.

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

serge.bouc@u-picardie.fr

Jacques Thévenaz, Section de mathématiques, EPFL, Station 8, CH-1015 Lausanne, Switzerland.

Jacques.Thevenaz@epfl.ch