THE ALGEBRA OF BOOLEAN MATRICES, CORRESPONDENCE FUNCTORS, AND SIMPLICITY

SERGE BOUC AND JACQUES THÉVENAZ

Abstract. We determine the dimension of every simple module for the algebra of the monoid of all relations on a finite set (i.e. Boolean matrices). This is in fact the same question as the determination of the dimension of every evaluation of a simple correspondence functor. The method uses the theory of such functors developed in [BT2, BT3], as well as some new ingredients in the theory of finite lattices.

1. Introduction

Let k be a field, let R_{X} be the monoid of all relations on a finite set X (also known as Boolean matrices), and let kR_{X} be the k-algebra of the monoid. This is an algebra of dimension 2^{n^{2}}, where n = |X|, hence growing very fast in terms of n. It was considered many years ago in [CP, Ki, KR, PW, Sc1, Sc2] and more recently in [BE, Br, Di], but the dimensions of the irreducible representations of kR_{X} remained unknown in general.

We solve here the open problem of describing all simple kR_{X}-modules and finding their dimension. This requires to embed the category of kR_{X}-modules into the larger category of correspondence functors, namely functors from the category of finite sets and correspondences to the category k-Mod. We use methods of the representation theory of categories, as well as some new ingredients in the theory of finite lattices. The proof is based on very delicate arguments about a system of linear equations which was introduced in [BT3]. We also deduce a formula for the dimension of the Jacobson radical of kR_{X} (in characteristic zero). The formulas behave exponentially with respect to n.

It is not too hard to show (and known to specialists) that the simple modules for kR_{X} are classified by isomorphism classes of triples (E, R, V), where E is finite set with |E| ≤ |X|, R is a partial order relation on E, and V is a simple module for the group algebra k Aut(E, R). When E = X, we get precisely the simple modules for an algebra kP_{X} which is a quotient of kR_{X} and which we call the algebra of permuted orders on X, because it has a k-basis P_{X} consisting of all RΔ_{σ} where R is a partial order on X and Δ_{σ} is the graph of a permutation σ of X. The simple kP_{X}-modules and their dimension are known and can be described explicitly. The more difficult cases occur when |E| < |X|. All cases are uniformly treated in the present paper.

The largest part of our work is concerned with correspondence functors. It is only in Section 8 that we actually deal with the simple modules for the algebra kR_{X} and prove the main results mentioned above, which follow easily from the previous sections of a functorial nature. The connection between functors and simple kR_{X}-modules is provided by the known fact that the evaluation of a simple correspondence functor at a finite set X is either zero or a simple module for the algebra kR_{X}. Conversely every simple kR_{X}-module occurs as the evaluation at X of a simple functor. This provides a way to handle simple modules for the algebra kR_{X} by studying simple correspondence functors. It is this embedding in the larger category of correspondence functors which allows us to prove our results. A first step, which is not very hard and explained in [BT2], is the description of the parametrization of simple correspondence functors S_{E,R,V} by isomorphism classes of triples (E, R, V), where (E, R) is a finite poset (i.e. R is a partial order relation on a finite set E) and V is a simple module for the group algebra k Aut(E, R).

Date: October 17, 2020.

1991 Mathematics Subject Classification. AMS Subject Classification : 06B05, 06B15, 06E05, 16B50, 16D90, 16G30, 18A25, 18B05, 18B10.

Key words and phrases. Keywords : finite set, correspondence, relation, Boolean matrix, functor category, simple functor, simple module, poset, lattice.

The main ingredients for this work are our papers [BT2, BT3] about correspondence functors. Some fundamental modules and functors play a crucial role in our approach. Here k is allowed to be an arbitrary commutative ring. For any finite poset (E, R), we described in [BT1] a fundamental module M_{E,R} := kP_{E}f_{R} for kP_{E}, where kP_{E} is the algebra of permuted orders mentioned above and f_{R} is a suitable idempotent of kP_{E} depending on the order relation R (see Section 3). From this, we constructed and studied in [BT2, BT3] a fundamental functor 𝕊_{E,R}, which is the key for understanding simple correspondence functors because the simple functor S_{E,R,V} appears as a suitable quotient of the fundamental functor 𝕊_{E,R} (see Section 4).

Another main ingredient is the link between correspondence functors and the theory of finite lattices, see [BT3]. Associated to any finite lattice T, there is a correspondence functor F_{T} and a surjective morphism

Θ : F_{T} ⟶ 𝕊_{E,R^{op}}

where (E, R) denotes the full subposet of join-irreducible elements of T and R^{op} denotes the opposite relation. The main problem is to describe the kernel of Θ and this gives rise to a complicated system of linear equations which was introduced in [BT3]. One of the main contributions of the present paper is to solve this system. From this solution, a k-basis can be found for each evaluation 𝕊_{E,R^{op}}(X) of a fundamental functor. Generators are found in Section 5 and they are proved to be k-linearly independent in Section 6. The cardinality of this basis is given by a well-known combinatorial formula, behaving exponentially as a function of X.

Turning to simple functors (assuming again that k is a field), we need to pass to a quotient of 𝕊_{E,R} in order to obtain the simple functor S_{E,R,V}. This requires to show that each evaluation 𝕊_{E,R}(X) has a free right k Aut(E, R)-module structure and that the simple functor S_{E,R,V} is isomorphic to a tensor product 𝕊_{E,R}⊗_{k Aut(E,R)}V. This nontrivial part of the argument requires the whole of Section 7 and culminates with an explicit formula for the dimension of each evaluation S_{E,R,V} (X) of a simple correspondence functor. The last step is to go back to the algebra kR_{X} and deduce the dimension of every simple kR_{X}-module as well as a description of the action of relations on it. As mentioned above, this last step is explained in Section 8. Finally, a few examples are described in Section 9.

There is a classical approach to the classification of simple modules for the algebra of a finite semigroup, going back to the work of Munn and Ponizovsky, using Green’s theory of J -classes (see the textbook [CP], the more recent article [GMS] for a modern point of view, or the textbook [St2] for a very recent account). For the algebra kR_{X} we are interested in, we do not use this point of view for several reasons. First, our approach to the parametrization of simple modules for kR_{X} is not classical and does not use at all J -classes in the monoid R_{X}. It is based instead on the classification of simple correspondence functors, which in turn depends only, for each E, on the quotient algebra kP_{E} and its simple modules. These are easy to describe explicitly and depend in an important way on the fundamental module M_{E,R} associated to a poset (E, R). Secondly, taking advantage of the link with the theory of correspondence functors and using the functor F_{T} associated to a finite lattice T, our main task is the study of the above morphism Θ (which is itself also based on the fundamental module M_{E,R}). Finally, we do not only consider relations, namely subsets of X × X, but also correspondences, namely subsets of Y × X, for Y ≠ X, to the extent that some of them play a crucial role in the large system of linear equations which is finally solved.

Although we do not use the classical way of handling simple modules for the algebra of a finite monoid, it is not surprising that our functorial approach has connections with the classical one. Whenever such connections can be made clear, we mention them, in a series of remarks. This will help the interested reader to establish the link between some of the functorial concepts we are using and the monoid-theoretic classical approach. However, we emphasize that the question of translating all the functorial proofs of our results in monoid-theoretic terms remains wide open. If such a translation is possible, it will probably require much more work.

Acknowledgements. We are grateful to the referee for pointing out many connections between our development and the classical approach to simple modules for the algebra kR_{X}.

2. Preliminaries on lattices

In this section, we define, in any finite lattice, two operations r^{∞} and σ^{∞}, as well as a subset Ĝ of special elements, each lying at the bottom of a totally ordered subset with strong properties. We then prove some results which will play a crucial role in the description of the evaluation of fundamental functors and simple functors.

Let us first fix some notation. By an order R on a finite set E, we mean a partial order relation on E. In other words, (E, R) is a finite poset. We write ≤_{R} for the order relation, so that (a, b) ∈ R if and only if a ≤_{R} b. Moreover a <_{R} b means that a ≤_{R} b and a ≠ b. The opposite relation R^{op} of R is defined by the property that (a, b) ∈ R^{op} if and only if (b, a) ∈ R.

If T is a finite lattice, we write ≤_{T}, or sometimes simply ≤, for the order relation, ∨ for the join (least upper bound), ∧ for the meet (greatest lower bound), ˆ0 for the least element and ˆ1 for the greatest element.

2.1. Notation and definitions.

(a) If (E, R) is a finite poset and a, b ∈ E with a ≤_{R} b, we define intervals

\begin{matrix}[a, b]_{E} := \{x ∈ E | a ≤_{R} x ≤_{R} b\} , & ]a, b[_{E} := \{x ∈ E | a <_{R} x <_{R} b\} , \\ [a, b[_{E} := \{x ∈ E | a ≤_{R} x <_{R} b\} , & ]a, b]_{E} := \{x ∈ E | a <_{R} x ≤_{R} b\} , \\ [a, ·[_{E} := \{x ∈ E | a ≤_{R} x\} , & ]·, b]_{E} := \{x ∈ E | x ≤_{R} b\} . \end{matrix}

When the context is clear, we write [a, b] instead of [a, b]_{E}.

(b) If T is a finite lattice, an element e ∈ T is called join-irreducible, or simply irreducible, if, whenever e = ⋁_{a∈A} a for some subset A of T, then e ∈ A. In

case A = ∅, the join is ˆ0 and it follows that ˆ0 is not irreducible. If e ≠ ˆ0 is irreducible and e = s ∨ t with s, t ∈ T, then either e = s or e = t. In other words, if e ≠ ˆ0, then e is irreducible if and only if [ˆ0, e[ has a unique maximal element.

(c) If (E, R) is a subposet of a finite lattice T, we say that (E, R) is a full subposet of T if for all e, f ∈ E we have :

e ≤_{R} f ⟺ e ≤_{T} f .

In particular Irr(T) denotes the full subposet of irreducible elements of T.

(d) If (E, R) is a finite poset, I_{↓}(E, R) denotes the set of lower R-ideals of E, that is, the subsets A of E such that, whenever a ∈ A and x ≤ a, then x ∈ A. Clearly I_{↓}(E, R), ordered by inclusion of subsets, is a lattice, the join operation being union of subsets, and the meet operation being intersection. Similarly, I^{↑}(E, R) denotes the set of upper R-ideals of E, which is also a lattice. Obviously I^{↑}(E, R) = I_{↓}(E, R^{op}).

Note that if (E, R) is the poset of irreducible elements in a finite lattice T, then T is generated by E in the sense that any element x ∈ T is a join of elements of E. To see this, define the height of t ∈ T to be the maximal length of a chain in [ˆ0, t]_{T}. If x is not irreducible and x ≠ ˆ0, then x = t_{1} ∨ t_{2} with t_{1} and t_{2} of smaller height than x. By induction on the height, both t_{1} and t_{2} are joins of elements of E. Therefore x = t_{1} ∨ t_{2} is also a join of elements of E.

Recall that a lattice T is distributive if a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) for all a, b, c ∈ T (or equivalently a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) for all a, b, c ∈ T).

2.2. Lemma. Let (E, R) be a finite poset.

(a) The irreducible elements in the lattice I_{↓}(E, R) are the lower ideals ]·, e]_{E}, where e ∈ E. Thus the poset (E, R) is isomorphic to the poset of all irreducible elements in I_{↓}(E, R) by mapping e ∈ E to the ideal ]·, e]_{E}.

(b) I_{↓}(E, R) is a distributive lattice.

(c) For any finite lattice T with Irr(T) = (E, R), there is a join-preserving surjective map f : I_{↓}(E, R) ⟶ T which sends any lower ideal A ∈ I_{↓}(E, R) to the join ⋁_{e∈A} e in T.

(d) The map f : I_{↓}(E, R) ⟶ T above is bijective if and only if T is a distributive lattice. In that case, f is an isomorphism of lattices.

Proof : This is not difficult and well-known. For details, see Theorem 3.4.1 and Proposition 3.4.2 in [Sta], and also Theorem 6.2 in [Ro].

Whenever we use the lattice I_{↓}(E, R), we shall (abusively) identify E with its image via the map

E ⟶ I_{↓}(E, R) , e ↦ ]·, e]_{E} .

Thus we view (E, R) as a full subposet of I_{↓}(E, R).

2.3. Notation. Let T be a finite lattice and (E, R) = Irr(T). If t ∈ T, then r(t) denotes the join of all elements strictly smaller than t :

r(t) = ⋁_{a∈[ˆ0,t[} a .

It follows that r(t) = t if and only if t ∉ E. More precisely, if t ∉ E and t ≠ ˆ0, then t can be written as the join of two smaller elements, so r(t) = t, while if e ∈ E, then r(e) is the unique maximal element of [ˆ0, e[. We put r^{k}(t) = r(r^{k−1}(t)) and r^{∞}(t) = r^{n}(t) if n is such that r^{n}(t) = r^{n+1}(t).

2.4. Lemma. Let T be a finite lattice, let (E, R) = Irr(T), and let t ∈ T.

(a) The map r : T → T is order-preserving.

(b) r^{∞}(t) ∉ E.

(c) r^{∞}(t) = t if and only if t ∈ T − E.

(d) If e ∈ E, r^{∞}(e) is the unique greatest element of T − E smaller than e.

Proof : The proof is a straightforward consequence of the definitions.

2.5. Lemma. Let T be a finite lattice, let (E, R) = Irr(T), and let e ∈ E. Let n be the smallest integer such that r^{n}(e) = r^{∞}(e).

(a) [r^{∞}(e), e] is totally ordered and [r^{∞}(e), e] = {r^{n}(e), …, r^{1}(e), e}.

(b) ]r^{∞}(e), e] is contained in E.

(c) r^{∞}(r^{i}(e)) = r^{∞}(e) for all 0 ≤ i ≤ n − 1.

(d) [ˆ0, e] = [ˆ0, r^{∞}(e)] ⊔ ]r^{∞}(e), e].

Proof : Since e ∈ E, r(e) is the unique maximal element of [ˆ0, e[. Inductively, r^{i}(e) ∈ E for each 0 ≤ i ≤ n − 1 and r^{i+1}(e) is the unique maximal element of [ˆ0, r^{i}(e)[. It follows that [r^{∞}(e), e] is totally ordered and consists of the elements r^{n}(e), …, r^{1}(e), e. This proves (a), (b) and (c).

Now let f ∈ [ˆ0, e]. Then f ∨ r^{∞}(e) ∈ [r^{∞}(e), e]. If f ∨ r^{∞}(e) = r^{∞}(e), then f ∈ [ˆ0, r^{∞}(e)]. Otherwise, f ∨ r^{∞}(e) ∈ ]r^{∞}(e), e], hence f ∨ r^{∞}(e) ∈ E by (b), that is, f ∨r^{∞}(e) is irreducible. It follows that f ∨r^{∞}(e) = f or f ∨r^{∞}(e) = r^{∞}(e). But the second case is impossible because f ∨ r^{∞}(e) > r^{∞}(e). Therefore f ∨ r^{∞}(e) = f, that is, f ∈ ]r^{∞}(e), e].

2.6. Notation and definitions. Let T be a finite lattice and (E, R) = Irr(T).

(a) Define ΛE to be the subset of T consisting of all meets of elements of E, that is, elements of the form ⋀_{i∈I} e_{i} where I is a finite set of indices and

e_{i} ∈ E for every i ∈ I. Note that we include the possibility that I be the empty set, in which case one gets the unique greatest element ˆ1.

(b) If t ∈ T, define σ(t) to be the meet of all the irreducible elements of T which are strictly larger than t. Inductively, σ^{k}(t) = σ(σ^{k−1}(t)) and σ^{∞}(t) = σ^{n}(t) where n is such that σ^{n}(t) = σ^{n+1}(t).

Notice that the definition of σ is in some sense ‘dual’ to the definition of r, because r(t) is the join of all the irreducible elements which are strictly smaller than t. (However, the ‘true’ dual of r is different : it is the operation r in the opposite lattice T^{op}, thus involving meet-irreducible elements.) It is clear that the map σ : T → T is order-preserving.

2.7. Lemma. Let (E, R) = Irr(T) and let t ∈ T.

(a) If t ∈ ΛE − E, then σ(t) = t.

(b) If t ∉ ΛE, then σ(t) > t.

Proof : This follows immediately from the definitions.

2.8. Remark. For completeness, we can also describe the effect of σ on en element e ∈ E, with 3 cases :

(1) If ]e, ˆ1] ∩ E has at least two minimal elements, then either σ(e) = e or σ(e) > e but σ(e) is not irreducible.

(2) If ]e, ˆ1] ∩ E has a unique minimal element e^{+}, then σ(e) = e^{+}.

(3) If ]e, ˆ1] ∩ E is empty (that is, e is maximal in E), then σ(e) = ˆ1.

Note that the equality σ(e) = e also occurs in the third case for e = ˆ1, provided ˆ1 is irreducible.

2.9. Lemma. Let t ∈ T such that r^{∞}σ^{∞}(t) = t. Then :

(a) t ∉ E.

(b) If t ∈ ΛE, then t ∈ ΛE − E and t = σ(t) = r(t).

(c) If t ∉ ΛE and e = σ^{∞}(t), then e ∈ E, the interval [t, e] is totally ordered, and

[t, e] = {r^{n}(e), r^{n−1}(e), …, r^{1}(e), e} = {t, σ^{1}(t), …, σ^{n}(t)} ,

where n ≥ 1 is the smallest integer such that σ^{n}(t) = σ^{∞}(t).

Proof : (a) We have t = r(t) because t is in the image of r^{∞}.

(b) Since t ∈ ΛE − E, the equality t = σ(t) follows from Lemma 2.7.

(c) We have e ≥ σ(t) > t by Lemma 2.7 because t ∉ ΛE. Since t = r^{∞}(e) < e, we obtain r(e) < e, hence e ∈ E. By Lemma 2.5, [t, e] is totally ordered, and

[t, e] = {r^{n}(e), r^{n−1}(e), …, r^{1}(e), e} .

Since σ^{∞}(t) = e, we must have σ(t) > t and also σ(r^{i}(e)) > r^{i}(e) for 1 ≤ i ≤ n because t ≤ r^{i}(e) < e and σ is order-preserving. But ]t, e] ⊆ E by Lemma 2.5 again, so the definition of σ implies that σ(r^{i}(e)) = r^{i−1}(e). It follows that σ^{i}(t) = r^{n−i}(e) and therefore

[t, e] = {t, σ^{1}(t), …, σ^{n}(t)} ,

completing the proof.

Lemma 2.9 is of great significance in this paper and justifies to introduce an important notation.

2.10. Notation. Define

G^{♯} = {t ∈ T | r^{∞}σ^{∞}(t) = t} ,
Ĝ = {t ∈ G^{♯} | t ∉ ΛE} ,
G = E ⊔ G^{♯} = E ⊔ (ΛE−E) ⊔ Ĝ .

It is not hard to show that Ĝ can be characterized by the properties that t ∉ ΛE and there exists e ∈ E with t = r^{∞}(e) and σ(e) = e. If e is chosen minimal with these properties, then we recover the element e of Lemma 2.9. We note that Ĝ (corresponding to case (c) in Lemma 2.9) is usually a rather small subset of T, often even empty (as for instance in Example 9.8).

2.11. Example. If T = {0, 1, …, m} is totally ordered, E = Irr(T) = {1, …, m}. Then G^{♯} = Ĝ = {0} and G = T.

The following two propositions will be crucial for our results on evaluations of fundamental functors in Sections 5 and 6. We continue with the assumption that T is a finite lattice and (E, R) = Irr(T).

2.12. Proposition. Let a ∈ T with a ∉ G, and let b = r^{∞}σ^{∞}(a). There exists an integer r ≥ 0 such that

a < σ(a) < … < σ^{r}(a) < b ≤ σ^{r+1}(a) ,

and σ^{j}(a) ∈ E for j ∈ {1, …, r}. Moreover b ∈ G^{♯}.

Proof : We know that a = σ^{0}(a) ∉ E because a ∉ G, hence a = r(a). Also a ≤ b because a = r^{∞}(a) ≤ r^{∞}σ^{∞}(a) = b. Therefore a < b because otherwise a = b would be in G^{♯}. There are two cases (which will correspond to b satisfying case (b) or (c) of Lemma 2.9).

Suppose first that there exists an integer r ≥ 0 such that c = σ^{r+1}(a) ∉ E. In this case, we choose r minimal with this property, so that σ^{j}(a) ∈ E for 1 ≤ j ≤ r. We have c = σ(σ^{r}(a)) ∈ ΛE − E, hence c = σ(c) = σ^{∞}(c) = σ^{∞}(a). Moreover b = r^{∞}(c) = c, because c ∉ E. Therefore

a < σ(a) < … < σ^{r}(a) < b = σ^{r+1}(a)

and in fact b ∈ ΛE − E because b = c.

In the second case, we suppose that σ^{r}(a) ∈ E for all r ∈ ℤ_{>0}. Let m be the smallest positive integer such that σ^{∞}(a) = σ^{m}(a). Define e_{i} = σ^{i}(a) for all 0 ≤ i ≤ m. Note that e_{1}, …, e_{m−1} all belong to E because they belong to ΛE (since they are in the image of the operator σ) and moreover σ(e_{i}) > e_{i} (excluding the possibility e_{i} ∈ ΛE − E). Also e_{m} = σ^{∞}(a) ∈ E by assumption.

We have a = r^{∞}(a) ≤ r^{∞}(σ^{∞}(a)) < σ^{∞}(a), because σ^{∞}(a) ∈ E. Therefore, there is an integer r ≤ m−1 such that b ≤ e_{r+1} but b ≰ e_{r}. Note that b ∉ E because its definition implies that b = r(b). The inequality b < e_{r+1} is strict because b ∉ E while e_{r+1} ∈ E. (The case r = 0 occurs when a ≤ b < e_{1}.)

In particular b ≤ r^{∞}(e_{r+1}) ≤ r^{∞}(σ^{∞}(a)) = b, hence b = r^{∞}(e_{r+1}). Suppose that the element e_{r} ∨ b is irreducible. Then either e_{r} ∨ b = b or e_{r} ∨ b = e_{r}. The first case is impossible because b is not irreducible. The second case is impossible because it would imply b ≤ e_{r}, contrary to the definition of r. Therefore e_{r} ∨b ∉ E. Since e_{r} ∨ b ≤ e_{r+1}, we obtain e_{r} ∨ b ≤ r^{∞}(e_{r+1}) = b by definition of r^{∞}(e_{r+1}). It follows that e_{r} < b < e_{r+1}, as required.

The relations σ^{r}(a) < b < σ^{r+1}(a) imply that σ^{∞}(b) = σ^{∞}(a). Therefore we get r^{∞}σ^{∞}(b) = b, proving that b ∈ G^{♯}. In fact b ∈ Ĝ, otherwise b ∈ ΛE − E, hence σ(b) = b. But this is impossible because σ^{r}(a) < b implies b < σ^{r+1}(a) ≤ σ(b).

2.13. Notation. Let ζ : G ⟶ I^{↑}(E, R) be the map defined by

ζ(t) = \{ \begin{matrix}[t, ˆ1] ∩ E & if t ∈ E , \\ ]σ^{∞}(t), ˆ1] ∩ E & if t ∉ E . \end{matrix}

For any B ∈ I^{↑}(E, R), define ∧B = ∧_{e∈B} e. By definition of σ^{∞}(t), we obtain

∧ζ(t) = \{ \begin{matrix}t & if t ∈ E , \\ σ^{∞}(t) & if t ∉ E . \end{matrix}

2.14. Proposition. Let t ∈ G and t′ ∈ T such that t′ ≤ ∧ζ(t).

(a) σ^{∞}(t′) ≤ σ^{∞}(t) and r^{∞}(t′) ≤ r^{∞}(t).

(b) t′ ≤ t, except possibly if t ∈ Ĝ.

Proof : We have G = (ΛE − E) ⊔ E ⊔ Ĝ and we consider the three cases successively.

If t ∈ ΛE − E, then ∧ζ(t) = σ^{∞}(t) = t, hence t′ ≤ t and consequently σ^{∞}(t′) ≤ σ^{∞}(t) and r^{∞}(t′) ≤ r^{∞}(t).

If t ∈ E, then ∧ζ(t) = t, hence t′ ≤ t and consequently σ^{∞}(t′) ≤ σ^{∞}(t) and r^{∞}(t′) ≤ r^{∞}(t).

Finally, if t ∈ Ĝ, then ∧ζ(t) = σ^{∞}(t), thus σ^{∞}(t′) ≤ σ^{∞}(t). Moreover, using part (d) of Lemma 2.4 and the fact that r^{∞}(σ(t)) = t fo 1 ≤ i ≤ n (Lemma 2.9), we obtain

r^{∞}(t′) ≤ r^{∞}(∧ζ(t)) = r^{∞}(σ^{∞}(t)) = t = r^{∞}(t) .

This proves (a), and also (b) because the relation t′ ≰ t can appear only in the case t ∈ Ĝ.

3. Fundamental modules

For any finite poset (E, R), we describe in this section a specific module M_{E,R} for the algebra kR_{E} of the monoid of relations on E. We call it the fundamental module because it plays a crucial role throughout our work.

If X and Y are finite sets, a correspondence from X to Y is a subset of Y × X (using a reverse notation which will later be convenient for left actions). If S ⊆ Z×Y and R ⊆ Y × X, the composition of correspondences SR is a correspondence from X to Z defined by

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

When X = Y, a correspondence from X to X is called a (binary) relation on X, also called a Boolean matrix. We let C(Y, X) be the set of all correspondences from X to Y. In particular, whenever E is a finite set, R_{E} := C(E, E) is the monoid of all relations on E and kR_{E} is the k-algebra of this monoid, where k is a commutative base ring. If σ is permutation of the set E, we write Δ_{σ} = {(σ(x), x) | x ∈ E} and we also write Δ_{E} := Δ_{id}.

Define

P_{E} := { RΔ_{σ} | R is an order relation on E and σ is a permutation of E } ,

and let kP_{E} be its k-linear span, with k-basis P_{E}. Any two orders R and S can be multiplied according to the rule that R · S is equal to the transitive closure of R ∪ S if this closure is an order, and zero otherwise. Then any two basis elements RΔ_{σ}, SΔ_{τ} ∈ P_{E} can also be multiplied via the rule

(RΔ_{σ})(SΔ_{τ}) = (R ·^{σ}S)Δ_{στ} ,

where · denotes the product of orders defined above and where ^{σ}S = Δ_{σ}SΔ_{σ^{−1}}, that is, ^{σ}S = {(σ(e), σ(f)) | (e, f) ∈ S}. Thus kP_{E} is a k-algebra, which we called the algebra of permuted orders in [BT1]. Moreover, there is a surjective k-algebra map

π : kR_{E} ⟶ kP_{E}

defined as follows. First π(Δ_{σ}) = Δ_{σ} and if R is a reflexive relation then π(R) is the transitive closure \overline{R} if this closure is an order, and zero otherwise. Finally if a relation S does not contain a permutation (i.e. S cannot be written RΔ_{σ} with R reflexive), then π(R) = 0.

The full structure of the k-algebra kP_{E} can be described. We let Σ_{E} be the group of all permutations of E and for any order R on E we let Aut(E, R) be the automorphism group of the poset (E, R), that is, the stabilizer of R in Σ_{E}.

3.1. Theorem. The k-algebra kP_{E} is isomorphic to a direct product of matrix algebras

kP_{E} ≅ ∏_{R} M_{n_{R}}(k Aut(E, R)) ,

where the product runs over representatives R of conjugacy classes of orders on E and where n_{R} = |Σ_{E} : Aut(E, R)|.

This is Theorem 7.5 in [BT1] but it is in fact a very special case of a general result about inverse monoids (see Remark 3.4 below). In the R-th term of the product above, we let f_{R} be the matrix having a single nonzero entry 1 in the first position of the diagonal (and zeroes in all the other terms of the direct product). Then, for any coset representative σ in Σ_{E}/ Aut(E, R), the matrix Δ_{σ}f_{R}Δ_{σ}^{−1} = f_{^{σ}R} has a single nonzero entry 1 in the σ-th position of the diagonal. Note that the isomorphism of Theorem 3.1 maps R ∈ P_{E} to the sum ∑_{S∈P_{E},R⊆S} f_{S}.

Then we define

M_{E,R} := kP_{E}f_{R}

viewed as a left kP_{E}-module and we call it the fundamental module associated to the finite poset (E, R). All we need to know about M_{E,R} is its structure, described in the next result, which is Proposition 8.5 of [BT1].

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

(a) The fundamental module M_{E,R} is a left module for the algebra kP_{E}, hence also a left module for the algebra of relations kR_{E}.

(b) M_{E,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) M_{E,R} is a (kP_{E}, k Aut(E, R))-bimodule and the right action of k Aut(E, R) is free. Explicitly, the right action of τ ∈ Aut(E, R) maps the basis element Δ_{σ}f_{R} to the basis element Δ_{στ} f_{R}.

Using Theorem 3.1, one can also view M_{E,R} as the set of column vectors of size |Σ_{E} : Aut(E, R)| with entries in k Aut(E, R), with its obvious (kP_{E}, k Aut(E, R))- bimodule structure. In particular, if τ ∈ Aut(E, R), then Δ_{τ} f_{R} = f_{R}Δ_{τ} is the matrix having a single nonzero entry τ in the first position of the diagonal.

3.3. Remark. The action of the algebra of relations kR_{E} on the module M_{E,R} is given by an explicit formula. For any relation Q ∈ R_{E},

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

(Note that τ is unique in the first case.) This is proved in Proposition 8.5 of [BT1] but is not explicitly used in the present paper. It is used implicitly because the proof of Theorem 4.10 below is based on this formula (see Lemma 6.1 in [BT3]).

3.4. Remark (inverse monoids). The k-basis P_{E} is almost a monoid and Theorem 3.1 is a very special case of a general result about inverse monoids. Explicitly, let z be a zero element added to P_{E} and set P̃_{E} = P_{E} ⊔ {z}. Then P̃_{E} is a monoid (by replacing a product equal to 0 by a product equal to z). The algebra of this monoid satisfies kP̃_{E} ≅ kP_{E} × k and kP_{E} is the contracted monoid algebra of P̃_{E} (see Remark 5.3 in [St2]). Moreover P̃_{E} is an inverse monoid, the inverse of RΔ_{σ} being Δ_{σ^{−1}}R = R^{σ}Δ_{σ^{−1}}, where R^{σ} = Δ_{σ^{−1}}RΔ_{σ}.

By Theorem 4.3 in [St1] or Corollary 9.4 in [St2], the algebra of an inverse monoid is isomorphic to a product of matrix algebras over the group algebras of its maximal subgroups. Thus, if we discard the term k generated by z, we see that Theorem 3.1 is just a specific instance of this general result. In order to get this special case, one needs to notice that the idempotents of the inverse monoid P̃_{E} are, apart from z, all orders R and that the maximal subgroup of P̃_{E} at R is isomorphic to Aut(E, R). Moreover, two idempotents are in the same J -class if and only if they are conjugate under Σ_{E} and the number of idempotents in the J -class of R is the number of conjugates of R, that is, n_{R} = |Σ_{E} : Aut(E, R)|.

Finally, it should be noticed that the fundamental module M_{E,R} is isomorphic to the left Schützenberger module relative to R (see Section 5.2 in [St2]). More precisely, if L_{R} denotes the L-class of R in the monoid P̃_{E}, then right multiplication by f_{R} defines a surjective kP_{E}-linear map kP̃_{E}R → kP_{E}f_{R} (notice that Rf_{R} = f_{R}). The map has kernel k(P̃_{E}R − L_{R}) and induces an isomorphism of (kP_{E}, k Aut(E, R))-bimodules between the Schützenberger module kL_{R} and the fundamental module M_{E,R} = kP_{E}f_{R}.

3.5. Corollary. Assume that k is a field. The simple kP_{E}-modules have the form

T_{R,V} = M_{E,R} ⊗_{k Aut(E,R)} V

where R runs over a set of representatives of conjugacy classes of orders on E and V runs over a set of representatives of isomorphism classes of simple modules for the group algebra k Aut(E, R).

Proof : This follows from the Morita equivalence between k Aut(E, R) and the matrix algebra M_{n_{R}}(k Aut(E, R)), which is given by the tensor product

V ↦ M_{E,R} ⊗_{k Aut(E,R)} V ,

and then applying Theorem 3.1. This is made explicit in [BT1].

4. Correspondence functors

In this section, we recall the basic facts we need about correspondence functors. We refer to [BT2] for details. We denote by C the category of finite sets and correspondences. Its objects are the finite sets and the set C(Y, X) of morphisms from X to Y is the set of all correspondences from X to Y, namely all subsets of Y × X. The composition of correspondences is described at the beginning of Section 3.

For any commutative ring k, we let kC be the k-linearization of the category C. The objects are the same, the set of morphisms kC(Y, X) is the free k-module with basis C(Y, X), and composition is extended by k-bilinearity from composition in C. For any permutation σ of X, we write Δ_{σ} = {(σ(x), x) | x ∈ X}. In particular, Δ_{X} := Δ_{id} is the identity morphism of the object X.

A correspondence functor is a k-linear functor from kC to the category k-Mod of left k-modules, for some fixed commutative ring k. We let F_{k} be the category of all correspondence functors. As already observed in [BT2], there is a set-theoretic observation to be made. In order to have sets of natural transformations, we need to restrict to a small skeleton of C, for instance the full subcategory whose objects are the sets {1, 2, …, n} for n ≥ 0. For simplicity of the exposition, we avoid to recall this technical point, which is used throughout.

If F is a correspondence functor and ψ ∈ kC(Y, X), we view the k-module homomorphism F (ψ) : F (X) → F (Y) as a left action of ψ. More precisely, if α ∈ F (X), we define a left action ψ · α := F (ψ)(α) ∈ F (Y). In particular, the evaluation of a correspondence functor at a finite set X is a left kR_{X}-module where R_{X} = C(X, X) is the monoid of all relations on X. Our strategy will be to work with correspondence functors rather than kR_{X}-modules.

4.1. Remark (finite category). The category C has infinitely many objects. If one is interested in fixing an object X, then one can consider the full subcategory C_{≤X} whose objects are all subsets of X. This has finitely many objects and morphisms and the corresponding category algebra A (the free k-module on all morphisms in C_{≤X}, as defined for instance in [We]) is a k-algebra which is Morita equivalent to kR_{X}. This is because if e is the identity morphism of the object X, then AeA = A and eAe ≅ kR_{X} (see Theorem 4.13 in [St2] for details). Therefore, the representation theory of the category C_{≤X} is equivalent to the representation theory of the monoid R_{X}.

However, we do not see any strong reason for the restrictive choice of fixing an object, as opposed to considering all objects simultaneously. Thus we will always use correspondence functors defined on the whole of C and we often need to do so. Also, working with the whole category C allowed us in [BT2] to consider finiteness conditions as well as asymptotic behavior of correspondence functors. This is another important motivation for avoiding to fix an object and it is used again in Corollary 6.7.

4.2. Remark (bi-surjective relations). In Example 4.4 of his recent work [Ste], Stein gives another connection with correspondences, but again fixing a finite set X. He proves that the algebra kR_{X} is isomorphic to the category algebra of the category whose objects are the subsets of X and morphisms are bi-surjective correspondences (hence a subcategory of C).

We use in particular the following construction of correspondence functors. For any fixed left kR_{E}-module W, the correspondence functor L_{E,W} is defined by

L_{E,W} (X) := kC(X, E) ⊗_{kC(E,E)} W ,

with an obvious left action of correspondences in C(Y, X) by composition. Note that W ↦ L_{E,W} is left adjoint to the evaluation F ↦ F (E). There is a subfunctor J_{E,W} of L_{E,W} defined as follows (see Lemma 2.5 in [BT2]) :

J_{E,W} (X) = { ∑_{i} φ_{i} ⊗ w_{i} ∈ L_{E,W} (X) | ∀ρ ∈ kC(E, X) , ∑_{i}(ρφ_{i}) · w_{i} = 0} .

Let us mention an important functorial property of the quotient functor L_{E,W} /J_{E,W}.

4.3. Lemma. Let E be a finite set and let W be a left kR_{E}-module.

(a) J_{E,W} (E) = {0} and L_{E,W} (E)/J_{E,W} (E) ≅ L_{E,W} (E) ≅ W.

(b) Let α ∈ L_{E,W} (X)/J_{E,W} (X) where X is some finite set. Then ρ · α = 0 for every ρ ∈ kC(E, X) if and only if α = 0.

Proof : (a) It is clear that L_{E,W} (E) = kC(E, E) ⊗_{kC(E,E)} W ≅ W. Corresponding to w ∈ W, let id ⊗w ∈ L_{E,W} (E). If id ⊗w ∈ J_{E,W} (E), we choose ρ = id ∈ C(E, E) and we obtain w = (ρ ∘ id) · w = 0, by the definition of J_{E,W} (X). This shows that J_{E,W} (E) = {0}.

(b) Let ρ ∈ kC(E, X). It follows from (a) that there is a commutative diagram

\xymatrix{0 \ar[r] & J_{E,W} (X) \ar[r] \ar[d] & L_{E,W} (X) \ar[r]^{π} \ar[d]^{ρ} & L_{E,W} (X)/J_{E,W} (X) \ar[r] \ar[d]^{ρ} & 0 \\  & 0 \ar[r] & L_{E,W} (E) \ar[r]^{≅} & W \ar[r] & 0}

Let ∑_{i} φ_{i} ⊗ w_{i} ∈ L_{E,W} (X) such that π(∑_{i} φ_{i} ⊗ w_{i}) = α. From the assumption that ρ · α = 0 for every ρ ∈ kC(E, X), we obtain

0 = ρ · ( ∑_{i} φ_{i} ⊗ w_{i}) = ∑_{i} ρφ_{i} ⊗ w_{i} ∈ L_{E,W} (E) .

Viewing this in W via the isomorphism L_{E,W} (E) ≅ W, we get ∑_{i}(ρφ_{i}) · w_{i} = 0 for every ρ ∈ kC(E, X). In other words, ∑_{i} φ_{i} ⊗ w_{i} ∈ J_{E,W} (X) and it follows that α = 0.

We now recall the construction of fundamental functors and simple functors, which are special cases of the construction above (see [BT2, BT3]). Using the fundamental kR_{E}-module M_{E,R} associated with a poset (E, R), we obtain the fundamental functor

𝕊_{E,R} := L_{E,M_{E,R}}/J_{E,M_{E,R}} .

Its structure will be described in Theorem 4.12 below, which will be our main tool, but we first mention the following properties (see Proposition 2.6 in [BT3]).

4.4. Proposition. Let (E, R) be a finite poset and X a finite set.

(a) 𝕊_{E,R}(X) = {0} if |X| < |E|.

(b) 𝕊_{E,R}(E) ≅ M_{E,R}.

If now V is a left k Aut(E, R)-module, we define the kR_{E}-module

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

using the right k Aut(E, R)-module structure on M_{E,R} described in Proposition 3.2. We then obtain an associated correspondence functor

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

When k is a field and V is a simple k Aut(E, R)-module, we have seen in Corollary 3.5 that T_{R,V} is a simple kP_{E}-module, hence also a simple kR_{E}-module via the surjective homomorphism π : kR_{E} → kP_{E}. But we obtain more (see Theorem 4.7 in [BT2]).

4.5. Theorem. Assume that k is a field.

(a) If the k Aut(E, R)-module V is simple, then the functor S_{E,R,V} is simple and S_{E,R,V} (E) ≅ T_{R,V} is a simple kR_{E}-module.

(b) The map (E, R, V) ↦ S_{E,R,V} provides a parametrization of all simple correspondence functors by isomorphism classes of triples (E, R, V), where (E, R) is a finite poset and V is a simple k Aut(E, R)-module.

(c) If S is a simple correspondence functor, the triple (E.R, V) such that S ≅ S_{E,R,V} is obtained as follows. First E is a set of minimal cardinality such that S(E) ≠ {0}. Then (R, V) is the pair corresponding to the simple kP_{E}- module S(E) ≅ T_{R,V}.

4.6. Remark. In part (c), it should be noticed that the simple kR_{E}-module S(E) is actually a kP_{E}-module (with the kernel of π : kR_{E} → kP_{E} acting by zero). This follows from Theorems 4.2 and 4.7 in [BT2]. Therefore, S(E) has the form T_{R,V} for some pair (R, V), by Corollary 3.5.

4.7. Remark (apex and minimality). Theorem 4.5 is the corner stone in our approach to the classification of simple kR_{X}-modules, which will be given in Theorem 8.1. In the classical Munn–Ponizovsky theory using J -classes, an important concept is the apex of a simple kR_{X}-module M, which is the minimal regular J -class that does not annihilate M (see [GMS]). Here there is also a notion of minimality, but of a different, and very elementary, nature. Every simple kR_{X}-module will be realized as the evaluation at X of some simple correspondence functor S_{E,R,V} and E is then a minimal set on which this simple functor does not vanish (by part (c) of Theorem 4.5).

An important step in our strategy is to realize every simple correspondence functor as a quotient of a fundamental functor. More generally, the following property holds (see Lemma 2.7 in [BT3]).

4.8. Proposition. Let (E, R) be a finite poset, let V be a left k Aut(E, R)-module generated by a single element v, and let X be a finite set. There is a surjective morphism of correspondence functors

Φ : 𝕊_{E,R} ⟶ S_{E,R,V}

such that, on evaluation at the finite set E, we obtain the surjective homomorphism of kR_{E}-modules

Φ_{E} : M_{E,R} ⟶ T_{R,V} = M_{E,R} ⊗_{k Aut(E,R)} V , a ↦ a ⊗ v .

In order to obtain information about simple functors S_{E,R,V}, we shall always work first with the fundamental functor 𝕊_{E,R}, which is a precursor of S_{E,R,V} since we recover S_{E,R,V} by means of the surjective morphism Φ : 𝕊_{E,R} → S_{E,R,V}. This explains why the fundamental functors play a crucial role throughout our work. We shall see in Section 7 that there is an explicit way to recover S_{E,R,V} from 𝕊_{E,R}. It is also worth mentioning that both 𝕊_{E,R} and S_{E,R,V} are defined over an arbitrary commutative ring k.

Now we explain the connection between correspondence functors and lattices. Let T be a finite lattice. We defined in [BT3] a correspondence functor F_{T} as follows. If X is a finite set, then F_{T} (X) = kT^{X}, the free k-module with basis the set T^{X} of all functions from X to T. If R ⊆ Y × X is a correspondence and if φ ∈ T^{X}, then we associate the function R·φ = F_{T} (R)(φ) ∈ T^{Y}, also simply written Rφ, defined by

(Rφ)(y) := ⋁_{(y,x)∈R} φ(x) ,

with the usual rule that a join over the empty set is equal to ˆ0. The map

F_{T} (R) : F_{T} (X) ⟶ F_{T} (Y)

is the unique k-linear extension of this construction.

4.9. Remark (row spaces and lattices). There is a classical connection between relations and lattices (see [Ki]). Any relation S ∈ R_{X} can be viewed as a Boolean matrix and its rows generate the row space of S, which is a lattice under union (i.e. Boolean addition) and the induced meet. If T_{S} denotes the row space lattice of S and if a relation U ∈ R_{X} belongs to the left ideal R_{X}S, then the row space of U is contained in T_{S}. Therefore, for any x ∈ X, the x-th row of U can be viewed as the value at x of a function φ : X → T_{S}. It follows that R_{X}S can be identified with T_{S}^{X}, hence kR_{X}S ≅ F_{T_{S}}(X). It is easy to see that this is an isomorphism of left kR_{X}-modules, establishing a link between the principal left ideals of kR_{X} and the evaluation at X of some of the functors F_{T}.

However, we wish to emphasize that the functors F_{T} bring a change of perspective. First, instead of fixing X and varying T_{S} when S varies in R_{X}, we fix T (which does not depend anymore on any choice of S) and we allow X to vary in order to get a functor. Thus F_{T} has more structure, namely a functor structure when X varies, as opposed to principal left ideals in the fixed algebra kR_{X}. Note also that working with a fixed T is important throughout our approach, in particular in Sections 5 and 6. Secondly, the fact that T_{S} depends on S ∈ R_{X} implies in particular that T_{S} is contained in the lattice of subsets of X, so |T_{S}| is bounded by 2^{|X|}. Hence |X| must be large enough while this restriction disappears with the change of perspective. We can now consider an evaluation F_{T} (Y) for a finite set Y which can be arbitrarily small (up to the empty set). Thus we have not only more structure, but we have also extended the realm of possible evaluations.

The functors F_{T} play an important role in our approach because they are connected to fundamental functors by a morphism described in the following theorem (see Theorem 6.5 in [BT3]), which is the starting point for the proofs of our main results. If E denotes the set of irreducible elements in T, it is elementary to check that the functions φ ∈ T^{X} such that E ⊈ φ(X) generate a subfunctor H_{T} of F_{T}.

4.10. Theorem. Let T be a finite lattice, let (E, R) = Irr(T), and let ι : E → T denote the inclusion map.

(a) There exists a unique surjective morphism of correspondence functors

Θ_{T} : F_{T} ⟶ 𝕊_{E,R^{op}}

such that Θ_{T,E}(ι) = f_{R^{op}} (an element in 𝕊_{E,R^{op}}(E) = M_{E,R^{op}} = P_{E}f_{R^{op}}).

(b) The subfunctor H_{T} is contained in the subfunctor Ker(Θ_{T}). Explicitly, if X is a finite set and if f ∈ T^{X} satisfies the condition E ⊈ f(X), then Θ_{T,X}(f) = 0.

(c) The functor F_{T} is generated by ι ∈ F_{T} (E), while the functor 𝕊_{E,R^{op}} is generated by f_{R^{op}} ∈ 𝕊_{E,R^{op}}(E).

The precise definition of Θ_{T} will be recalled in Definition 7.3. In order to have control of the fundamental functor 𝕊_{E,R^{op}}, we need to understand the kernel of Θ_{T}. To this end, we need to consider some correspondences which were introduced in [BT3] and which play again an important role in the present paper.

4.11. Notation. Let T be a finite lattice and (E, R) = Irr(T). For any finite set X and any map φ : X → T, we associate the correspondence

Γ_{φ} := {(x, e) ∈ X × E | e ≤_{T} φ(x)} ⊆ X × E .

In the special case where T = I_{↓}(E, R), we obtain

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

For the description of the kernel of Θ_{T} : F_{T} → 𝕊_{E,R^{op}}, the following result was obtained as Theorem 7.1 in [BT3]. The result actually gives a first explicit description of every fundamental functor and it is one of our main tools in this paper.

4.12. Theorem. Let T be a finite lattice, let (E, R) = Irr(T), and let X be a finite set. The kernel of the map

Θ_{T,X} : F_{T} (X) ⟶ 𝕊_{E,R^{op}}(X)

is equal to the set of linear combinations ∑_{φ:X→T} λ_{φ}φ, where λ_{φ} ∈ k, such that for

any map ψ : X → I^{↑}(E, R)

∑_{{φ \atop Γ_{ψ}^{op}Γ_{φ}=R^{op}}} λ_{φ} = 0 .

Here Γ_{φ} = {(x, e) ∈ X × E | e ≤_{T} φ(x)} and Γ_{ψ}^{op} = {(e, x) ∈ E × X | e ∈ ψ(x)}, as in Notation 4.11.

In order to use the condition Γ_{ψ}^{op}Γ_{φ} = R^{op} appearing in Theorem 4.12, we shall also need equivalent formulations. We first fix notation. If ψ : X → I^{↑}(E, R) is a map, define the function ∧ψ : X → T by

∀x ∈ X, ∧ψ(x) = ⋀_{e∈ψ(x)} e ,

where ⋀ is the meet in the lattice T. If φ and φ′ are two functions X → T, we write φ ≤ φ′ if φ(x) ≤ φ′(x) for all x ∈ X. The following result is Theorem 7.3 in [BT3].

4.13. Theorem. Let T be a finite lattice, let (E, R) = Irr(T), let ι : E → T denote the inclusion map, and let X be a finite set. Let φ : X → T and ψ : X → I^{↑}(E, R) be maps with associated correspondence Γ_{φ} and Γ_{ψ}^{op}, as in Theorem 4.12 above. The following conditions are equivalent.

(a) Γ_{ψ}^{op}φ = ι.

(b) Γ_{ψ}^{op}Γ_{φ}ι = ι.

(c) Δ_{E} ⊆ Γ_{ψ}^{op}Γ_{φ} ⊆ R^{op}.

(d) Γ_{ψ}^{op}Γ_{φ} = R^{op}.

(e) φ ≤ ∧ψ and ∀e ∈ E, ∃x ∈ X such that φ(x) = e and ψ(x) = [e, ·[_{E}.

(f) ∀t ∈ T, ψ(φ^{−1}(t)) ⊆ [t, ·[_{T} ∩E and ∀e ∈ E, ψ(φ^{−1}(e)) = [e, ·[_{E}.

As noticed in the proof of this theorem in [BT3], we abuse notation in (f). For any subset Y of X, ψ(Y) is a subset of I^{↑}(E, R), hence a set of subsets of E, but we write ψ(Y) for the union of these subsets of E, that is, ψ(Y) = ⋃_{x∈Y} ψ(x).

Conditions (e) and (f) will play a crucial role in our results on fundamental functors and simple functors (Sections 5 and 6).

4.14. Remark (Schützenberger modules). There is another connection between the functorial constructions of the present section and the classical representation theory of the monoid R_{X} (see [GMS] or [St2]). Using the notation of Remark 4.9, suppose U ∈ R_{X}S but U and S are not in the same L-class of the monoid R_{X}, that is, R_{X}U ≠ R_{X}S. Then the row space T_{U} must be strictly contained in the row space T_{S} and therefore T_{U} cannot contain the set E of irreducible elements of T_{S} since the irreducible elements generate T_{S}. In other words, the function φ : X → T_{S} corresponding to U (as in Remark 4.9) satisfies E ⊈ φ(X), hence belongs to H_{T_{S}}(X), where H_{T_{S}} denotes the subfunctor of F_{T_{S}} defined before Theorem 4.10. Thus U is in the same L-class as S if and only if E ⊆ φ(X), that is, φ ∉ H_{T_{S}}(X). Using the isomorphism kR_{X}S ≅ F_{T_{S}}(X) of Remark 4.9, we deduce that the quotient of kR_{X}S giving the left Schützenberger module relative to S (see Section 5.2 in [St2]) is isomorphic to F_{T_{S}}(X)/H_{T_{S}}(X).

In a more functorial way, given a fixed lattice T, the functor F_{T} /H_{T} links together various Schützenberger modules F_{T} (X)/H_{T} (X) when X is allowed to vary (but subject to the restriction |T | ≤ 2^{|X|}, as mentioned in Remark 4.9). It should also be mentioned that the quotient F_{T} /H_{T} is only used explicitly at the end of the proof of Theorem 6.1 and only in the special case when T is a totally ordered lattice. However, it is used implicitly in Sections 5 and 6 where we are dealing with functions φ : X → T satisfying the condition E ⊆ φ(X).

4.15. Remark (construction of simple functors). In the Munn-Ponizovsky theory, the simple modules for kR_{X} are constructed in the following way (see [GMS] or [St2]). One starts with a poset (E, R) (with E ⊆ X) and the Schützenberger module kL_{R} relative to R (quotient of kR_{X}R, as in Remark 4.14). Then kL_{R} has a (kR_{X}, k Aut(E, R))-bimodule structure, noticing that the maximal subgroup of R_{X} at the idempotent R is isomorphic to Aut(E, R). Induction from left k Aut(E, R)- modules to left kR_{X}-modules is given by the exact functor kL_{R} ⊗_{k Aut(E,R)} −. For any simple k Aut(E, R)-module V, its image kL_{R} ⊗_{k Aut(E,R)} V has a unique maximal submodule and the quotient

(kL_{R} ⊗_{k Aut(E,R)} V)/ Rad(kL_{R} ⊗_{k Aut(E,R)} V)

is the required simple kR_{X}-module corresponding to (E, R, V).

In view of Remark 4.14, an analogous result for constructing simple correspondence functors should involve a functor F_{T} /H_{T}. This is indeed the case and the simple functor S_{E,R^{op},V} can be realized as the unique simple quotient of (F_{T} /H_{T}) ⊗_{k Aut(E,R)} V via a surjective morphism

π : (F_{T} /H_{T}) ⊗_{k Aut(E,R)} V ⟶ S_{E,R^{op},V}

where T is a lattice with Irr(T) = (E, R). But there is a main new aspect which is crucial for our approach. Namely, we consider the intermediate functor 𝕊_{E,R^{op}} and we factorize π as a composite

\xymatrix{(F_{T} /H_{T}) ⊗_{k Aut(E,R)} V \ar[r]^{\overline{Θ}_{T} ⊗id_{V}} & 𝕊_{E,R^{op}} ⊗_{k Aut(E,R)} V \ar[r]^{Ψ} & S_{E,R^{op},V} ,}

where \overline{Θ}_{T} : F_{T} /H_{T} → 𝕊_{E,R^{op}} is induced by the morphism Θ_{T} : F_{T} → 𝕊_{E,R^{op}} of Theorem 4.10. It is this new aspect which allows us to prove our main results. In Sections 5 and 6, we control the kernel of Θ_{T} and find the dimension of each evaluation 𝕊_{E,R^{op}}(X). Then we prove in Section 7 the nontrivial fact that Ψ is actually an isomorphism, allowing us to find the dimension of each evaluation S_{E,R^{op},V} (X).

5. Generators for the evaluations of fundamental functors

As usual, E denotes a fixed finite set and R an order relation on E. Our purpose is to prove that, for an arbitrary commutative ring k and for any finite set X, the evaluation 𝕊_{E,R}(X) of the fundamental correspondence functor 𝕊_{E,R} is a free k-module, by finding an explicit k-basis. In this section, we first deal with k-linear generators.

Let T be any lattice such that (E, R) = Irr(T). Note that I_{↓}(E, R) is the largest such lattice and that any other is a quotient of I_{↓}(E, R) (Lemma 2.2). By Theorem 4.10, the fundamental functor 𝕊_{E,R^{op}} is isomorphic to a quotient of F_{T} via a morphism

Θ_{T} : F_{T} ⟶ 𝕊_{E,R^{op}} .

For this reason, we work with 𝕊_{E,R^{op}} rather than 𝕊_{E,R}.

5.1. Notation. Let G = G(T) be the subset defined in Notation 2.10 and let X be a finite set. We define B_{X} to be the set of all maps φ : X → T such that E ⊆ φ(X) ⊆ G.

Our main purpose is to prove that the set Θ_{T,X}(B_{X}) is a k-basis of 𝕊_{E,R^{op}}(X). We first prove in this section that Θ_{T,X}(B_{X}) generates k-linearly 𝕊_{E,R^{op}}(X) and then we shall show in Section 6 that Θ_{T,X}(B_{X}) is k-linearly independent.

Recall that G = E ⊔ G^{♯} where G^{♯} = {a ∈ T | a = r^{∞}σ^{∞}(a)}, with r^{∞} defined in Notation 2.3 and σ^{∞} in Definition 2.6. We denote by G^{c} the complement of G in T, namely

G^{c} = {a ∈ T | a ∉ E, a < r^{∞}σ^{∞}(a)} .

Recall from Proposition 2.12 that if a ∈ G^{c} and b = r^{∞}σ^{∞}(a), there exists an integer r ≥ 0 such that

a < σ(a) < … < σ^{r}(a) < b ≤ σ^{r+1}(a) ,

and σ^{j}(a) ∈ E for j ∈ {1, …, r}. Moreover, b ∈ G^{♯}. This produces a way to pass from any element a outside G to a uniquely defined element b in G. This justifies the following terminology :

5.2. Definition. For a ∈ G^{c}, the sequence a < σ(a) < … < σ^{r}(a) < b defined above will be called the reduction sequence associated to a.

5.3. Notation. Let n ≥ 1 and let (a_{0}, a_{1}, …, a_{n}) be a sequence of distinct elements of T. We denote by [a_{0}, …, a_{n}] : T → T the map defined by

∀t ∈ T, [a_{0}, …, a_{n}](t) = \{ \begin{matrix}a_{j+1} & if t = a_{j}, j ∈ \{0, …, n − 1\} \\ t & otherwise. \end{matrix}

If a ∈ G^{c}, let (a_{0}, a_{1}, …, a_{r}, a_{r+1}) be the reduction sequence associated to a, with a_{0} = a and a_{r+1} = b = r^{∞}σ^{∞}(a). We then denote by u_{a} the element of k(T^{T}) = F_{T} (T) defined by

u_{a} = [a_{0}, a_{1}] − [a_{0}, a_{1}, a_{2}] + … + (−1)^{r}[a_{0}, a_{1}, …, a_{r+1}] .

We can now describe a family of useful elements in Ker Θ_{T}.

5.4. Theorem. Let T be a finite lattice, let (E, R) = Irr(T), let G^{c} = {a ∈ T | a ∉ E, a < r^{∞}σ^{∞}(a)}, and let X be a finite set. Then, for any a ∈ G^{c} and for any function φ : X → T,

φ − u_{a} ∘ φ ∈ Ker Θ_{T,X} ,

where u_{a} ∘φ is defined by bilinearity from the composition of maps T^{T} ×T^{X} → T^{X}.

Proof : The kernel of the map Θ_{T,X} : F_{T} (X) → 𝕊_{E,R^{op}}(X) was described in Theorem 4.12. Let ∑_{φ:X→T} λ_{φ}φ ∈ F_{T} (X), where λ_{φ} ∈ k. Then ∑_{φ:X→T} λ_{φ}φ belongs

to Ker Θ_{T,X} if and only if the coefficients λ_{φ} satisfy a system of linear equations indexed by maps ψ : X → I^{↑}(E, R). The equation (E_{ψ}) indexed by such a map ψ is the following :

(E_{ψ}) :  ∑_{φ ⊢_{E,R} ψ} λ_{φ} = 0 ,

where φ ⊢_{E,R} ψ means that φ : X → T and ψ : X → I^{↑}(E, R) satisfy the equivalent

conditions of Theorem 4.13. We shall use condition (f) of Theorem 4.13, namely

φ ⊢_{E,R} ψ ⟺ \{ \begin{matrix}∀t ∈ T, ψ(φ^{−1}(t)) ⊆ [t, ·[_{T} ∩E , \\ ∀e ∈ E, ψ(φ^{−1}(e)) = [e, ·[_{E} . \end{matrix}

Recall that we abuse notation here. For any subset Y of X, in particular for Y = φ^{−1}(t), we write ψ(Y) = ⋃_{x∈Y} ψ(x), a union of subsets of E instead of a set of

subsets of E. This abusive notation is convenient and is used throughout the proof.

Let a ∈ G^{c}, and let (a, e_{1}, e_{2}, …, e_{r}, b) be the associated reduction sequence. Recall that e_{1}, …, e_{r} ∈ E but b ∉ E. If r ≥ 1, note that [a, ·[_{T} ∩E = [e_{1}, ·[_{E} because a < σ(a) = e_{1} ∈ E. Define, for each i ∈ {1, …, r},

φ_{i} = [a, e_{1}, …, e_{i}] ∘ φ , and also φ_{r+1} = [a, e_{1}, …, e_{r}, b] ∘ φ .

In particular, for any i ∈ {1, …, r + 1},

if φ(x) ∈ T − {a, e_{1}, …, e_{r}} , then φ_{i}(x) = φ(x) .

The other values of the maps φ_{i} are given in the following table :

(5.5)  \begin{matrix}x ∈ & φ^{−1}(a) & φ^{−1}(e_{1}) & φ^{−1}(e_{2}) & … & φ^{−1}(e_{r−1}) & φ^{−1}(e_{r}) \\ φ(x) & a & e_{1} & e_{2} & … & e_{r−1} & e_{r} \\ φ_{1}(x) & e_{1} & e_{1} & e_{2} & … & e_{r−1} & e_{r} \\ φ_{2}(x) & e_{1} & e_{2} & e_{2} & … & e_{r−1} & e_{r} \\ φ_{3}(x) & e_{1} & e_{2} & e_{3} & … & e_{r−1} & e_{r} \\ … & … & … & … & … & … & … \\ φ_{r}(x) & e_{1} & e_{2} & e_{3} & … & e_{r} & e_{r} \\ φ_{r+1}(x) & e_{1} & e_{2} & e_{3} & … & e_{r} & b \end{matrix}

We want to prove that the element

φ − u_{a} ∘ φ = φ − φ_{1} + φ_{2} − … + (−1)^{r−1}φ_{r+1}

belongs to Ker Θ_{T,X}. We must prove that it satisfies the equation (E_{ψ}) for every ψ, so we must find which of the functions φ, φ_{1}, φ_{2}, …, φ_{r+1} are linked with ψ under the relation ⊢_{E,R}. We are going to prove that only two consecutive functions can be

linked with a given ψ, from which it follows that the corresponding equation (E_{ψ}) is satisfied because it reduces to either 1 − 1 = 0, or −1 + 1 = 0. Of course, if none of φ, φ_{1}, φ_{2}, …, φ_{r+1} is linked with ψ, then the corresponding equation (E_{ψ}) is just 0 = 0. It follows from this that φ − u_{a} ∘ φ satisfies all equations (E_{ψ}), hence belongs to Ker Θ_{T,X}, as required. We note for completeness that it may happen that some of the functions φ, φ_{1}, φ_{2}, …, φ_{r+1} are equal (this occurs if an inverse image is empty in some column of the table), but this does not play any role in the argument.

Assume first that r ≥ 1. Write U := T −{a, e_{1}, …, e_{r}} and V := E−{e_{1}, …, e_{r}}. The linking with a fixed ψ is controlled by the following conditions :

φ ⊢_{E,R} ψ ⟺ \{ \begin{matrix}∀t ∈ U, ψ(φ^{−1}(t)) ⊆ [t, ·[_{T} ∩E \\ ∀e ∈ V, ψ(φ^{−1}(e)) = [e, ·[_{E} \\ ψ(φ^{−1}(a)) ⊆ [a, ·[_{T} ∩E = [e_{1}, ·[_{E} \\ ψ(φ^{−1}(e_{i})) = [e_{i}, ·[_{E} ∀i ∈ \{1, …, r\} . \end{matrix}

The subsets φ_{j}^{−1}(e_{i}) are determined by Table 5.5 and can be written in terms of φ. In particular, φ_{1}^{−1}(e_{1}) = φ^{−1}(a) ⊔ φ^{−1}(e_{1}), so we obtain

φ_{1} ⊢_{E,R} ψ ⟺ \{ \begin{matrix}∀t ∈ U, ψ(φ^{−1}(t)) ⊆ [t, ·[_{T} ∩E \\ ∀e ∈ V, ψ(φ^{−1}(e)) = [e, ·[_{E} \\ ψ(φ^{−1}(a) ⊔ φ^{−1}(e_{1})) = [e_{1}, ·[_{E} \\ ψ(φ^{−1}(e_{i})) = [e_{i}, ·[_{E} ∀i ∈ \{2, …, r\} . \end{matrix}

Similarly, for 2 ≤ j ≤ r, we have φ_{j}^{−1}(e_{1}) = φ^{−1}(a) and φ_{j}^{−1}(e_{i+1}) = φ^{−1}(e_{i}) if 1 ≤ i ≤ j − 2, and then φ_{j}^{−1}(e_{j}) = φ^{−1}(e_{j−1}) ⊔ φ^{−1}(e_{j}). Therefore we get successively

φ_{2} ⊢_{E,R} ψ ⟺ \{ \begin{matrix}∀t ∈ U, ψ(φ^{−1}(t)) ⊆ [t, ·[_{T} ∩E \\ ∀e ∈ V, ψ(φ^{−1}(e)) = [e, ·[_{E} \\ ψ(φ^{−1}(a)) = [e_{1}, ·[_{E} \\ ψ(φ^{−1}(e_{1}) ⊔ φ^{−1}(e_{2})) = [e_{2}, ·[_{E} \\ ψ(φ^{−1}(e_{i})) = [e_{i}, ·[_{E} ∀i ∈ \{3, …, r\} . \end{matrix}

φ_{3} ⊢_{E,R} ψ ⟺ \{ \begin{matrix}∀t ∈ U, ψ(φ^{−1}(t)) ⊆ [t, ·[_{T} ∩E \\ ∀e ∈ V, ψ(φ^{−1}(e)) = [e, ·[_{E} \\ ψ(φ^{−1}(a)) = [e_{1}, ·[_{E} \\ ψ(φ^{−1}(e_{1})) = [e_{2}, ·[_{E} \\ ψ(φ^{−1}(e_{2}) ⊔ φ^{−1}(e_{3})) = [e_{3}, ·[_{E} \\ ψ(φ^{−1}(e_{i})) = [e_{i}, ·[_{E} ∀i ∈ \{4, …, r\} . \end{matrix}

…

φ_{r−1} ⊢_{E,R} ψ ⟺ \{ \begin{matrix}∀t ∈ U, ψ(φ^{−1}(t)) ⊆ [t, ·[_{T} ∩E \\ ∀e ∈ V, ψ(φ^{−1}(e)) = [e, ·[_{E} \\ ψ(φ^{−1}(a)) = [e_{1}, ·[_{E} \\ ψ(φ^{−1}(e_{i})) = [e_{i+1}, ·[_{E} ∀i ∈ \{1, …, r − 3\} \\ ψ(φ^{−1}(e_{r−2}) ⊔ φ^{−1}(e_{r−1})) = [e_{r−1}, ·[_{E} \\ ψ(φ^{−1}(e_{r})) = [e_{r}, ·[_{E} . \end{matrix}

φ_{r} ⊢_{E,R} ψ ⟺ \{ \begin{matrix}∀t ∈ U, ψ(φ^{−1}(t)) ⊆ [t, ·[_{T} ∩E \\ ∀e ∈ V, ψ(φ^{−1}(e)) = [e, ·[_{E} \\ ψ(φ^{−1}(a)) = [e_{1}, ·[_{E} \\ ψ(φ^{−1}(e_{i})) = [e_{i+1}, ·[_{E} ∀i ∈ \{1, …, r − 2\} \\ ψ(φ^{−1}(e_{r−1}) ⊔ φ^{−1}(e_{r})) = [e_{r}, ·[_{E} . \end{matrix}

φ_{r+1} ⊢_{E,R} ψ ⟺ \{ \begin{matrix}∀t ∈ U, ψ(φ^{−1}(t)) ⊆ [t, ·[_{T} ∩E \\ ∀e ∈ V, ψ(φ^{−1}(e)) = [e, ·[_{E} \\ ψ(φ^{−1}(a)) = [e_{1}, ·[_{E} \\ ψ(φ^{−1}(e_{i})) = [e_{i+1}, ·[_{E} ∀i ∈ \{1, …, r − 1\} \\ ψ(φ^{−1}(e_{r})) ⊆ [b, ·[_{T} ∩E . \end{matrix}

Suppose that φ ⊢_{E,R} ψ. This clearly implies φ_{1} ⊢_{E,R} ψ. Also φ_{i} ⊬_{E,R} ψ for i ≥ 2,

because φ ⊢_{E,R} ψ implies ψ(φ^{−1}(e_{1})) = [e_{1}, ·[_{E}, but φ_{i} ⊢_{E,R} ψ implies ψ(φ^{−1}(e_{1})) ⊆

[e_{2}, ·[_{E} when i ≥ 2. Therefore only φ and φ_{1} are involved in this case.

Suppose now that φ_{1} ⊢_{E,R} ψ but φ ⊬_{E,R} ψ. Then ψ(φ^{−1}(e_{1})) ⊆]e_{1}, ·[_{T} ∩E = [e_{2}, ·[_{E}

(because e_{2} = σ(e_{1})) and ψ(φ^{−1}(a)) = [e_{1}, ·[_{E}, hence in particular φ_{2} ⊢_{E,R} ψ, since φ_{1} ⊢_{E,R} ψ also implies ψ(φ^{−1}(e_{i})) = [e_{i}, ·[_{E} for i ∈ {2, …, n}. On the other hand,

since φ_{1} ⊢_{E,R} ψ implies ψ(φ^{−1}(e_{2})) = [e_{2}, ·[_{E}, we cannot have ψ(φ^{−1}(e_{2})) ⊆ [e_{3}, ·[_{E}

and so φ_{i} ⊬_{E,R} ψ, for i ≥ 3. Therefore only φ_{1} and φ_{2} are involved in this case.

Suppose by induction that φ_{i} ⊢_{E,R} ψ but φ_{i−1} ⊬_{E,R} ψ, for some i ∈ {1, …, r − 1}.

Then the same argument shows that φ_{i+1} ⊢_{E,R} ψ and that only φ_{i} and φ_{i+1} are

involved in this case.

Suppose now that φ_{r} ⊢_{E,R} ψ but φ_{r−1} ⊬_{E,R} ψ. Then ψ(φ^{−1}(e_{r−1}) ⊔ φ^{−1}(e_{r})) =

[e_{r}, ·[_{E} but ψ(φ^{−1}(e_{r})) ≠ [e_{r}, ·[_{E}. Hence ψ(φ^{−1}(e_{r})) ⊆]e_{r}, ·[_{E} ⊆ [b, ·[_{T} ∩E, since σ(e_{r}) ≥ b. Moreover e_{r} ∈ ψ(φ^{−1}(e_{r−1}) ⊔ φ^{−1}(e_{r})) and e_{r} ∉ ψ(φ^{−1}(e_{r})). It follows

that e_{r} ∈ ψ(φ^{−1}(e_{r−1})), hence ψ(φ^{−1}(e_{r−1})) = [e_{r}, ·[_{E}. Therefore φ_{r+1} ⊢_{E,R} ψ and

only φ_{r} and φ_{r+1} are involved in this case.

Finally, if φ_{r+1} ⊢_{E,R} ψ, then ψ(φ^{−1}(e_{r−1})) = [e_{r}, ·[_{E} and ψ(φ^{−1}(e_{r})) ⊆ [b, ·[_{T} ∩E ⊆

[e_{r}, ·[_{E}. Thus ψ(φ^{−1}(e_{r−1}) ⊔ φ^{−1}(e_{r})) = [e_{r}, ·[_{E}. Therefore φ_{r} ⊢_{E,R} ψ and we are

again in the case when only φ_{r} and φ_{r+1} are involved.

The special case r = 0 has to be treated separately. There are only 2 terms φ and φ_{1} in the alternating sum. If φ ⊢_{E,R} ψ, then ψ(φ^{−1}(a)) ⊆ [a, ·[_{T} ∩E, hence

ψ(φ^{−1}(a)) ⊆ [b, ·[_{T} ∩E because b ≤ σ(a) when r = 0. Therefore

ψ(φ_{1}^{−1}(b)) = ψ(φ^{−1}(a) ⊔ φ^{−1}(b)) ⊆ [b, ·[_{T} ∩E

and so φ_{1} ⊢_{E,R} ψ. Conversely, it is straightforward to see that φ_{1} ⊢_{E,R} ψ implies φ ⊢_{E,R} ψ.

We have proved that only two consecutive functions can be linked with a given ψ, as was to be shown.

We have now paved the way for finding generators of 𝕊_{E,R^{op}}(X).

5.6. Theorem. Let T be a finite lattice, let (E, R) = Irr(T), and let

G^{c} = {a ∈ T | a ∉ E, a < r^{∞}σ^{∞}(a)} .

For a ∈ G^{c}, let u_{a} be the element of k(T^{T}) introduced in Notation 5.3, and let u_{T} denote the composition of all the elements u_{a}, for a ∈ G^{c}, in some order (they actually commute, see Theorem 5.8 below).

(a) Let X be a finite set. Then for any φ : X → T, the element u_{T} ∘ φ is a k-linear combination of functions f : X → T such that f(X) ⊆ G.

(b) Let B_{X} be the set of all maps φ : X → T such that E ⊆ φ(X) ⊆ G. Then the set Θ_{T,X}(B_{X}) generates 𝕊_{E,R^{op}}(X) as a k-module.

Proof : (a) We see in Table 5.5 that the functions φ_{1}, φ_{2}, …, φ_{r+1} do not take the value a. It follows that for any a ∈ G^{c} and any φ : X → T, the element u_{a} ∘ φ = φ_{1} − φ_{2} + … + (−1)^{r}φ_{r+1} is a k-linear combination of functions φ_{i} such that φ_{i}(X) ∩ G^{c} ⊆ (φ(X) ∩ G^{c}) − {a}. We now remove successively all such elements a by applying successively all u_{a} for a ∈ G^{c}. It follows that u_{T} ∘ φ is a k-linear combination of functions f : X → T such that f(X) ∩ G^{c} = ∅, that is, f(X) ⊆ G.

(b) Since Θ_{T,X} : F_{T} (X) → 𝕊_{E,R^{op}}(X) is surjective, 𝕊_{E,R^{op}}(X) is generated as a k-module by the images Θ_{T,X}(φ) of all maps φ : X → T. For any a ∈ G^{c}, u_{a} ∘ φ has the same image as φ under Θ_{T,X}, by Theorem 5.4. Therefore u_{T} ∘ φ has the same image as φ under Θ_{T,X}. Moreover, u_{T} ∘ φ is a k-linear combination of functions f : X → T such that f(X) ⊆ G, by (a). Finally, if E ⊈ f(X), then f ∈ Ker Θ_{T,X} by Theorem 4.10, so we can remove any such function in the linear combination u_{T} ∘ φ without changing the image Θ_{T,X}(u_{T} ∘ φ). So we are left with linear combinations of maps f : X → T such that E ⊆ f(X) ⊆ G.

We now mention that much more can be said about the elements u_{a} appearing in Theorem 5.6.

5.7. Definition. Let T be a finite lattice. Recall that G^{c} denotes the complement of G in T. We define an oriented graph structure G(T) on T in the following way : for x, y ∈ T, there is an edge [figure: x; y] from x to y in G(T) if there exists a ∈ G^{c} such that (x, y) is a pair of consecutive elements in the reduction sequence associated to a.

5.8. Theorem. Keep the notation of Theorem 5.6 and let G(T) be the graph structure on T introduced in Definition 5.7.

(a) The graph G(T) has no (oriented or unoriented) cycles, and each vertex has at most one outgoing edge. Hence G(T) is a forest.

(b) For a ∈ G^{c}, the element u_{a} is an idempotent of k(T^{T}).

(c) u_{a} ∘ u_{b} = u_{b} ∘ u_{a} for any a, b ∈ G^{c}.

(d) The element u_{T} is an idempotent of k(T^{T}).

There is actually a closed formula for u_{T} and this is useful for the explicit description of the action of correspondences on the evaluation of simple functors (see Theorem 8.3). Otherwise, Theorem 5.8 has apparently no direct implication on the structure of correspondence functors, so we omit the proof.

6. Linear independence of the generators

In Section 5, we found a set Θ_{T,X}(B_{X}) of generators for the evaluation 𝕊_{E,R^{op}}(X) of a fundamental functor 𝕊_{E,R^{op}}. We now move to linear independence.

6.1. Theorem. Let T be a finite lattice, let (E, R) = Irr(T), let X be a finite set, and let B_{X} be the set of all maps φ : X → T such that E ⊆ φ(X) ⊆ G, where G = G(T) is the subset defined in Notation 2.10. The elements Θ_{T,X}(φ), for φ ∈ B_{X}, are k-linearly independent in 𝕊_{E,R^{op}}(X).

Proof : We consider again the kernel of the map

Θ_{T,X} : F_{T} (X) ⟶ 𝕊_{E,R^{op}}(X) ,

which was described in Theorem 4.12 by a system of linear equations. This can be reformulated by introducing the k-linear map

[figure: η_{E,R,X} : F_{T} (X); F_{I^{↑}(E,R)}(X); φ; ∑_{{ψ:X→I^{↑}(E,R) \atop φ ⊢_{E,R} ψ}} ψ]

where the notation φ ⊢_{E,R} ψ means, as before, that φ : X → T and ψ : X → I^{↑}(E, R)

satisfy the equivalent conditions of Theorem 4.13. Theorem 4.12 asserts that

Ker(Θ_{T,X}) = Ker(η_{E,R,X}) .

For handling the condition φ ⊢_{E,R} ψ, we shall use part (e) of Theorem 4.13, namely

(6.2)

φ ⊢_{E,R} ψ ⟺ \{ \begin{matrix}φ ≤ ∧ψ , \\ ∀e ∈ E, ∃x ∈ X such that φ(x) = e and ψ(x) = [e, ·[_{E} . \end{matrix}

Let N = N_{E,R,X} be the matrix of η_{E,R,X} with respect to the standard basis of F_{T} (X), consisting of maps φ : X → T, and the standard basis of F_{I^{↑}(E,R)}(X), consisting of maps ψ : X → I^{↑}(E, R). Explicitly,

(6.3)  N_{ψ,φ} = \{ \begin{matrix}1 & if φ ⊢_{E,R} ψ , \\ 0 & otherwise. \end{matrix}

Note that N is a square matrix in the special case when T = I_{↓}(E, R), because complementation yields a bijection between I_{↓}(E, R) and I^{↑}(E, R). However, if T is a proper quotient of I_{↓}(E, R), then N has less columns.

In order to prove that the elements Θ_{T,X}(φ), for φ ∈ B_{X}, are k-linearly independent, we shall prove that the elements η_{E,R,X}(φ), for φ ∈ B_{X}, are k-linearly independent. In other words, we have to show that the columns of N indexed by φ ∈ B_{X} are k-linearly independent. Now we consider only the rows indexed by elements of the form ψ = ζ ∘ φ′, where φ′ ∈ B_{X} and ζ : G → I^{↑}(E, R) is the map defined in (2.13). We then define the square matrix M, indexed by B_{X} × B_{X}, by

∀φ, φ′ ∈ B_{X}, M_{φ′,φ} = N_{ζ∘φ′,φ} .

We are going to prove that M is invertible and this will prove the required linear independence.

The invertibility of M implies in particular that the map ζ must be injective, otherwise two rows of M would be equal. Therefore M turns out to be a submatrix of N, but this cannot be seen directly from its definition (unless an independent proof of the injectivity of ζ is provided).

The characterization of the condition φ ⊢_{E,R} ψ given in (6.2) implies that

M_{φ′,φ} = \{ \begin{matrix}1 & if φ ≤ ∧ζφ′ and ∀e ∈ E, ∃x ∈ X, φ(x) = e = φ′(x) , \\ 0 & otherwise , \end{matrix}

because the equality ζφ′(x) = [e, ·[_{E} is equivalent to φ′(x) = e, by definition of ζ (see Notation 2.13).

By Proposition 2.14, if t, t′ ∈ G are such that t ≤ ∧ζ(t′), then r^{∞}(t) ≤ r^{∞}(t′) and σ^{∞}(t) ≤ σ^{∞}(t′). Let ⪯ be the preorder on G defined by these conditions, i.e. for all t, t′ ∈ G,

t ⪯ t′ ⟺ r^{∞}(t) ≤ r^{∞}(t′) and σ^{∞}(t) ≤ σ^{∞}(t′) .

We extend this preorder to B_{X} by setting, for all φ′, φ ∈ B_{X},

φ ⪯ φ′ ⟺ ∀x ∈ X, φ(x) ⪯ φ′(x) ,

which makes sense because φ(x), φ′(x) ∈ G by definition of B_{X}. We denote by ⪯⪰ the equivalence relation defined by this preorder.

Clearly the condition M_{φ′,φ} ≠ 0 implies φ ≤ ∧ζφ′, hence φ ⪯ φ′ by Proposition 2.14 quoted above. In other words the matrix M is block triangular, the blocks being indexed by the equivalence classes of the preorder ⪯ on B_{X}. Showing that M is invertible is equivalent to showing that all its diagonal blocks are invertible. In other words, we must prove that, for each equivalence class C of B_{X} for the relation ⪯⪰, the matrix M_{C} = (M_{φ′,φ})_{φ′,φ∈C} is invertible. Let C be such a fixed equivalence class.

Recall from Definition 2.10 that G = ΛE ⊔ Ĝ. If t ∈ Ĝ, then by Lemma 2.9 e := σ^{∞}(t) belongs to E and [t, e] = {r^{k}(e), r^{k−1}(e), …, r^{1}(e), e}, where t = r^{k}(e) = r^{∞}(e). By Lemma 2.5, all elements of [ t, σ^{∞}(t) ]_{T} belong to E except t itself. Moreover, if x ∈ [ t, σ^{∞}(t) ]_{T} then r^{∞}(x) = t by Lemma 2.9. It follows that the sets

G_{t} = [ t, σ^{∞}(t) ]_{T} , for t ∈ Ĝ ,

are disjoint, and contained in G. Let

G_{∗} = G − ⨆_{t∈Ĝ} G_{t} ,

so that we get a partition

G = ⨆_{t∈{∗}⊔Ĝ} G_{t} .

6.4. Lemma. Let φ′, φ ∈ B_{X}. If φ′⪯⪰φ, then for all t ∈ {∗} ⊔ Ĝ,

φ^{′−1}(G_{t}) = φ^{−1}(G_{t}) .

Proof : Let t ∈ Ĝ and x ∈ φ^{−1}(G_{t}). Then φ(x) ∈ [ t, σ^{∞}(t) ]_{T}, hence r^{∞}φ(x) = t and σ^{∞}φ(x) = σ^{∞}(t), by Lemma 2.9. But the relation φ′⪯⪰φ implies that r^{∞}φ′(x) = r^{∞}φ(x) and σ^{∞}φ′(x) = σ^{∞}φ(x). Therefore r^{∞}φ′(x) = t and σ^{∞}φ′(x) = σ^{∞}(t), from which it follows that φ′(x) ∈ [ t, σ^{∞}(t) ]_{T}, that is, x ∈ φ^{′−1}(G_{t}). This shows that φ^{−1}(G_{t}) ⊆ φ^{′−1}(G_{t}). By exchanging the roles of φ and φ′, we obtain φ^{′−1}(G_{t}) = φ^{−1}(G_{t}).

Now G_{∗} is the complement of ⨆_{t∈Ĝ} G_{t} in G and the functions φ′, φ have their

values in G (by definition of B_{X}). So we must have also φ^{′−1}(G_{∗}) = φ^{−1}(G_{∗}).

For every t ∈ {∗} ⊔ Ĝ, we define

X_{t} = φ_{0}^{−1}(G_{t})

where φ_{0} is an arbitrary element of C. It follows from Lemma 6.4 that this definition does not depend on the choice of φ_{0}. Therefore, the equivalence class C yields a partition

X = ⨆_{t∈{∗}⊔Ĝ} X_{t} ,

and every function φ ∈ C decomposes as the disjoint union of the functions φ_{t}, where φ_{t} : X_{t} → G_{t} is the restriction of φ to X_{t}.

For t ∈ Ĝ, define

E_{t} = ] t, σ^{∞}(t) ]_{T} .

By Lemma 2.5, this consists of elements of E, so E_{t} = E ∩ G_{t}. Then we define E_{∗} = E − ⨆_{t∈Ĝ} E_{t} = E ∩ G_{∗}, so that we get a partition

E = ⨆_{t∈{∗}⊔Ĝ} E_{t} .

For every t ∈ {∗} ⊔ Ĝ and for every φ ∈ C, the fact that φ belongs to B_{X} implies that φ_{t} belongs to the set B_{X,t} of all maps φ_{t} : X_{t} → G_{t} such that

E_{t} ⊆ φ_{t}(X_{t}) ⊆ G_{t} .

Moreover, if φ′, φ ∈ C, then

M_{φ′,φ} = 1 ⟺ ∀t ∈ \{∗\} ⊔ Ĝ, \{ \begin{matrix}∀x ∈ X_{t}, φ_{t}(x) ≤ ∧ζφ′_{t}(x) \\ ∀e ∈ E_{t}, ∃x ∈ X_{t}, φ′(x) = e = φ(x) . \end{matrix}

It follows that the matrix M_{C} is the tensor product of the square matrices M_{C,t} for t ∈ {∗} ⊔ Ĝ, where the matrix M_{C,t} is indexed by the functions φ_{t} : X_{t} → G_{t} in B_{X,t} and satisfies

(M_{C,t})_{φ′_{t},φ_{t}} = 1 ⟺ \{ \begin{matrix}∀x ∈ X_{t}, φ_{t}(x) ≤ ∧ζφ′_{t}(x) \\ ∀e ∈ E_{t}, ∃x ∈ X_{t}, φ′(x) = e = φ(x) . \end{matrix}

In order to show that M_{C} is invertible, we shall prove that each matrix M_{C,t} is invertible.

If φ_{∗} ∈ B_{X,∗} and x ∈ X_{∗}, then φ_{∗}(x) ∈ G_{∗}, hence φ_{∗}(x) ∉ Ĝ, because Ĝ consists of all the bottom elements of the intervals G_{t} where t ∈ Ĝ. Therefore, the condition φ_{∗}(x) ≤ ∧ζφ′_{∗}(x) implies φ_{∗}(x) ≤ φ′_{∗}(x) by Proposition 2.14, because φ′_{∗}(x) ∉ Ĝ. It follows that the matrix M_{C,∗} is unitriangular, hence invertible, as required.

Now we fix t ∈ Ĝ, we consider the matrix M_{C,t} and we discuss the special role played by the elements of the set Ĝ. The interval G_{t} = [t, σ^{∞}(t)]_{T} is isomorphic to the totally ordered lattice \underline{n} = \{0, 1, …, n\}, for some n ≥ 1, and the set of irreducible elements E_{t} =]t, σ^{∞}(t)]_{T} is isomorphic to [n] = {1, …, n}. Composing the maps φ_{t} : X_{t} → G_{t} with this isomorphism, we obtain maps X_{t} → \underline{n}.

Changing notation for simplicity, we write X for X_{t} and φ for φ_{t}, and we let B\underline{n} ; X be the set of all maps φ : X → \underline{n} corresponding to maps in B_{X,t}, i.e. satisfying the condition [n] ⊆ φ(X) ⊆ \underline{n}. We note that this condition is the same as the condition that φ belongs to B_{X} for the lattice \underline{n}, because the set G(\underline{n}) is the whole of \underline{n} by Example 2.11. The matrix M_{C,t}, which we write M\underline{n} for simplicity, is now indexed by all the maps in B\underline{n} ; X and we have

M\underline{n} ; φ′,φ = 1 ⟺ \{ \begin{matrix}∀x ∈ X, φ(x) ≤ ∧ζφ′(x) \\ ∀e ∈ [n], ∃x ∈ X, φ′(x) = e = φ(x) . \end{matrix}

Here we need to clarify the meaning of the notation ∧ζ, so we recall that for any g ∈ G, we have

∧ζ(g) = \{ \begin{matrix}g & if g ∈ E , \\ σ^{∞}(g) & if g ∉ E . \end{matrix}

If g belongs to G_{t} and is mapped to a ∈ \underline{n} via the isomorphism G_{t} ≅ \underline{n}, then σ^{∞}(g) is mapped to n and we obtain

∧ζ(a) = \{ \begin{matrix}a & if a ∈ [n], i.e. a ≠ 0 , \\ n & if a = 0 . \end{matrix}

The point here is that we obtain the same result as the one we would have obtained by working with the lattice \underline{n}, that is, by working with the corresponding map ζ : \underline{n} → I^{↑}([n], tot), which is easily seen to be a bijection, mapping 0 to ∅ and j ≥ 1 to [j, n].

Now we return to the beginning of the proof of Theorem 6.1 in the special case of the lattice \underline{n}, with Irr(\underline{n}) = ([n], tot), where tot denotes the usual total order. We have

Ker(Θ_{\underline{n},X}) = Ker(η_{[n],tot,X})

and the matrix N of η_{[n],tot,X} has entries 0 and 1, with

N_{ψ,φ} = 1 ⟺ \{ \begin{matrix}∀x ∈ X, φ(x) ≤ ∧ψ(x) \\ ∀e ∈ [n], ∃x ∈ X, φ(x) = e and ψ(x) = [e, ·[_{[n]} , \end{matrix}

where φ : X → \underline{n} and ψ : X → I^{↑}([n], tot). But since ζ : \underline{n} → I^{↑}([n], tot) is a bijection, we can write ψ = ζφ′ and index the rows by the set of all functions φ′ : X → \underline{n}. We obtain

N_{φ′,φ} = 1 ⟺ \{ \begin{matrix}∀x ∈ X, φ(x) ≤ ∧ζφ′(x) \\ ∀e ∈ [n], ∃x ∈ X, φ′(x) = e = φ(x) , \end{matrix}

If φ or φ′ is not in B\underline{n} ; X (that is, the image of either φ or φ′ does not contain [n]), then the second condition cannot hold and so N_{φ′,φ} = 0. Thus we restrict the matrix N to the rows and columns indexed by B\underline{n} ; X. This restriction is exactly the same matrix as the matrix M\underline{n} above. Therefore, in order to prove that M\underline{n} is invertible, it suffices to prove that the columns of N indexed by B\underline{n} ; X are k-linearly independent. This in turn is equivalent to the condition that the set η_{[n],tot,X}(B\underline{n} ; X) is k-linearly independent, or also that the set Θ_{\underline{n},X}(B\underline{n} ; X) is k-linearly independent in 𝕊_{[n],tot^{op}}(X), because Ker(Θ_{\underline{n},X}) = Ker(η_{[n],tot,X}). In other words, we have to prove Theorem 6.1 in the case of a total order.

By Theorem 4.10, we know that the surjective morphism

Θ\underline{n} : F\underline{n} ⟶ 𝕊_{[n],tot^{op}}

has H\underline{n} in its kernel, where H\underline{n} is the subfunctor of F\underline{n} generated by all the maps φ : X → \underline{n} such that [n] ⊈ φ(X). Therefore Θ\underline{n} induces a surjective morphism

\overline{Θ}\underline{n} : F\underline{n}/H\underline{n} ⟶ 𝕊_{[n],tot^{op}} .

But Theorem 11.8 in [BT3] asserts that F\underline{n}/H\underline{n} is isomorphic to 𝕊_{[n],tot}, hence also to 𝕊_{[n],tot^{op}} in view of the poset isomorphism ([n], tot^{op}) ≅ ([n], tot) via the map j ↦ n − j + 1. Clearly the set B\underline{n} ; X is a k-basis of F\underline{n}(X)/H\underline{n}(X), so that 𝕊_{[n],tot^{op}}(X) is also a free k-module of rank |B\underline{n} ; X|. Evaluation at X yields a surjective homomorphism

\overline{Θ}_{\underline{n},X} : F\underline{n}(X)/H\underline{n}(X) ⟶ 𝕊_{[n],tot^{op}}(X)

between two free k-modules of the same rank, hence an isomorphism (by standard algebraic K-theory, see Lemma 6.8 in [BT3]). Since the elements Θ_{\underline{n},X}(φ), for φ ∈ B\underline{n} ; X, are the images under \overline{Θ}_{\underline{n},X} of the k-basis B\underline{n} ; X of F\underline{n}(X)/H\underline{n}(X), they form a k-basis of 𝕊_{[n],tot^{op}}(X). In particular, they are k-linearly independent.

This completes the proof of Theorem 6.1.

In order to obtain formulas for the dimension of the evaluation of a fundamental functor, we need a well-known combinatorial lemma, which is Lemma 8.1 in [BT2], but actually goes back to [BBHM].

6.5. Lemma. Let E be a subset of a finite set G. For any finite set X, the number N of all maps φ : X → G such that E ⊆ φ(X) ⊆ G is equal to

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

We can now prove one of our main results about fundamental correspondence functors. This generalizes a formula obtained in [BT3] in the case of a total order.

6.6. Theorem. Let (E, R) be a finite poset and let T be any lattice such that (E, R) = Irr(T). Let X be a finite set and let B_{X} be the set of all maps φ : X → T such that E ⊆ φ(X) ⊆ G, where G = G(T) is the subset defined in Notation 2.10.

(a) The set Θ_{T,X}(B_{X}) (more precisely, the injective image of B_{X} under Θ_{T,X}) is a k-basis of 𝕊_{E,R^{op}}(X).

(b) The k-module 𝕊_{E,R^{op}}(X) is free of rank

rk_{k}(𝕊_{E,R^{op}}(X)) = |B_{X}| = ∑_{i=0}^{|E|}(−1)^{i}\binom{|E|}{i}(|G| − i)^{|X|} .

Proof : (a) follows from Theorem 5.6 and Theorem 6.1.

(b) The formula follows immediately from (a) and Lemma 6.5.

6.7. Corollary. With the notation above, |G| only depends on (E, R), and not on the choice of T.

Proof : The formula of Theorem 6.6 implies that

rk_{k}(𝕊_{E,R^{op}}(X)) ∼ |G|^{|X|} as |X| → ∞ .

Since 𝕊_{E,R^{op}} only depends on (E, R), it follows that |G| only depends on (E, R).

We shall prove in a future paper a stronger property : the full subposet G of T only depends on (E, R) up to isomorphism.

7. From fundamental functors to simple functors

In this section, we complete the description of simple functors by showing that they can be constructed directly from fundamental functors. This uses in an essential way the fact, proved in Theorem 7.5 below, that each evaluation of a fundamental functor 𝕊_{E,R} is a free k Aut(E, R)-module. The proof will depend on our main Theorem 6.6.

In order to use the action of automorphisms, we will need the following lemma.

7.1. Lemma. Let (E, R) be a finite poset.

(a) For any finite lattice T such that Irr(T) = (E, R), restriction induces an injective group homomorphism Aut(T) → Aut(E, R).

(b) There exists a finite lattice T such that Irr(T) = (E, R) and such that the restriction homomorphism Aut(T) → Aut(E, R) is an isomorphism.

Proof : (a) For any lattice T such that Irr(T) = (E, R), any lattice automorphism of T induces an automorphism of the poset (E, R). This gives a group homomorphism Aut(T) → Aut(E, R), which is injective since any element t of T is equal to the join of the irreducible elements e ≤_{T} t.

(b) Requiring that Aut(T) ≅ Aut(E, R) amounts to requiring that any automorphism of (E, R) can be extended to an automorphism of T. This is clearly possible if we choose T = I_{↓}(E, R).

Now let T be a finite lattice with Irr(T) = (E, R). Our first goal is to work with right k Aut(E, R)-module structures on F_{T} and 𝕊_{E,R}. First, note that the group Aut(T) acts on the right on F_{T} (X) as follows :

∀φ : X → T , ∀σ ∈ Aut(T) , φ · σ := σ^{−1} ∘ φ .

Next, recall that the fundamental functor associated to a finite poset (E, R) is

𝕊_{E,R} := L_{E,M_{E,R}}/J_{E,M_{E,R}}

where M_{E,R} is the fundamental kR_{E}-module. Using the right k Aut(E, R)-module structure on M_{E,R}, we can define a right k Aut(E, R)-module structure on each evaluation

L_{E,M_{E,R}}(X) = kC(X, E) ⊗_{kC(E,E)} M_{E,R}

and we now show that this right module structure can be carried to 𝕊_{E,R}(X).

7.2. Lemma.

(a) J_{E,M_{E,R}}(X) is a right k Aut(E, R)-submodule of L_{E,M_{E,R}}(X).

(b) 𝕊_{E,R}(X) has a right k Aut(E, R)-module structure.

(c) The left action of any element of kC(Y, X) is a homomorphism of right k Aut(E, R)-modules 𝕊_{E,R}(X) → 𝕊_{E,R}(Y).

Proof : (a) Since kP_{E} is a quotient algebra of kC(E, E) and the tensor product defining L_{E,M_{E,R}}(X) is over kC(E, E), any element of L_{E,M_{E,R}}(X) can be written φ ⊗ f_{R} for some φ ∈ kC(X, E). The right action of σ ∈ Aut(E, R) on M_{E,R} (see Proposition 3.2) induces the right action given by

(φ ⊗ f_{R})Δ_{σ} = φ ⊗ (Δ_{σ}f_{R}) = (φΔ_{σ}) ⊗ f_{R} .

If φ ⊗ f_{R} ∈ J_{E,M_{E,R}}(X), then (ρφ) · f_{R} = 0 for all ρ ∈ kC(E, X). Then the element (φΔ_{σ}) ⊗ f_{R} satisfies

(ρφΔ_{σ}) · f_{R} = (ρφ) · f_{R}Δ_{σ} = 0

for all ρ ∈ kC(E, X). Therefore (φΔ_{σ}) ⊗ f_{R} = (φ ⊗ f_{R})Δ_{σ} belongs to J_{E,M_{E,R}}(X), as was to be shown.

(b) This follows immediately from (a).

(c) This follows from the fact that the left and right actions commute, by associativity of the composition kC(Y, X) × kC(X, E) × kC(E, E) → kC(Y, E).

We need now to explain how the morphism Θ_{T} : F_{T} → 𝕊_{E,R^{op}} of Theorem 4.10 is defined. This appears in Theorem 6.5 of [BT3].

7.3. Definition. Let φ : X → T be a map, i.e. a generator of F_{T} (X). Then Θ_{T,X}(φ) is the class in the quotient 𝕊_{E,R^{op}}(X) of the element

Γ_{φ} ⊗ f_{R^{op}} ∈ kC(X, E) ⊗_{kC(E,E)} M_{E,R^{op}} = L_{E,M_{E,R^{op}}} (X) ,

where Γ_{φ} is the correspondence defined in Notation 4.11.

7.4. Lemma. Let (E, R) be a poset. Let T be a lattice such that Irr(T) = (E, R) and such that the restriction homomorphism Aut(T) → Aut(E, R) is an isomorphism. For every finite set X, the map

Θ_{T,X} : F_{T} (X) ⟶ 𝕊_{E,R^{op}}(X)

is a homomorphism of right k Aut(E, R)-modules.

Proof : Note that we obviously have an equality Aut(E, R) = Aut(E, R^{op}). Let us first prove that, for any φ : X → T and any σ ∈ Aut(T) ≅ Aut(E, R),

Γ_{φ}Δ_{σ} = Γ_{σ^{−1}φ} .

An element (x, e) ∈ X ×E belongs to the left hand side if and only if (x, σ(e)) ∈ Γ_{φ}, because (σ(e), e) ∈ Δ_{σ}. By the definition of Γ_{φ}, this is equivalent to the condition σ(e) ≤_{T} φ(x), which in turn is equivalent to e ≤_{T} σ^{−1}φ(x) because σ ∈ Aut(T). Thus we obtain that (x, e) satisfies the condition defining Γ_{σ^{−1}φ}, that is, (x, e) belongs to the right hand side.

Now we can compute Θ_{T,X}(φ · σ) = Θ_{T,X}(σ^{−1}φ). By Definition 7.3, this is the class in the quotient 𝕊_{E,R^{op}}(X) of the element

Γ_{σ^{−1}φ} ⊗ f_{R^{op}} = Γ_{φ}Δ_{σ} ⊗ f_{R^{op}} = Γ_{φ} ⊗ Δ_{σ}f_{R^{op}} = (Γ_{φ} ⊗ f_{R^{op}})Δ_{σ} .

The latter equality uses the definition of the right action of σ on f_{R^{op}} (Proposition 3.2). Since the class of Γ_{φ} ⊗ f_{R^{op}} is Θ_{T,X}(φ), this shows that Θ_{T,X}(φ · σ) = Θ_{T,X}(φ) · σ, as required.

Our next result is crucial for the rest of this section, hence for the computation of the dimension of the evaluations of simple functors (Theorem 7.10).

7.5. Theorem. Let (E, R) be a poset. Let T be a lattice such that Irr(T) = (E, R) and such that the restriction homomorphism Aut(T) → Aut(E, R) is an isomorphism. For every finite set X, the evaluation 𝕊_{E,R^{op}}(X) is a free right k Aut(E, R)- module.

Proof : The set of all maps φ : X → T is a k-basis of F_{T} (X) and is permuted by the right action of Aut(E, R). If G is as before (see Theorem 6.6), we claim that the subset B_{X} of all maps satisfying E ⊆ φ(X) ⊆ G is freely permuted by Aut(E, R). First note that Aut(E, R) obviously leaves E invariant. It also leaves G invariant because Aut(T) ≅ Aut(E, R) preserves the characterization of G given in Notation 2.10. Therefore Aut(E, R) acts on B_{X}.

If σ ∈ Aut(E, R) stabilizes some φ ∈ B_{X}, that is, φ·σ = φ, then σ^{−1}φ(x) = φ(x) for all x ∈ X, hence in particular σ^{−1}(e) = e for every e ∈ E because E ⊆ φ(X). It follows that σ is the identity automorphism of E. This proves the claim above.

Now B_{X} is mapped bijectively onto Θ_{T,X}(B_{X}), which is a k-basis of 𝕊_{E,R^{op}}(X), by Theorem 6.6. By Lemma 7.4, Θ_{T,X} is a homomorphism of k Aut(E, R)-modules. It follows that Θ_{T,X}(B_{X}) is freely permuted by Aut(E, R) and therefore 𝕊_{E,R^{op}}(X) is a free (right) k Aut(E, R)-module.

Now we construct a morphism Ψ : 𝕊_{E,R} ⊗_{k Aut(E,R)} V → S_{E,R,V}, which will be proved later to be an isomorphism (Theorem 7.9).

7.6. Proposition. Let (E, R) be a finite poset, let A = Aut(E, R), and let V be a left kA-module, generated by a single element v (e.g. a simple module).

(a) For any finite set X, there is a commutative diagram

\xymatrix{0 \ar[r] & J_{E,M_{E,R}}(X) \ar[r]^{j} \ar[d] & L_{E,M_{E,R}}(X) \ar[r]^{π} \ar[d] & 𝕊_{E,R}(X) \ar[r] \ar[d]^{id ⊗v} & 0 \\  & J_{E,M_{E,R}}(X) ⊗_{kA} V \ar[r]^{j⊗id_{V}} \ar[d] & L_{E,M_{E,R}}(X) ⊗_{kA} V \ar[r]^{π⊗id_{V}} \ar[d]^{id} & 𝕊_{E,R}(X) ⊗_{kA} V \ar[r] \ar[d]^{Ψ_{X}} & 0 \\ 0 \ar[r] & J_{E,M_{E,R}⊗V} (X) \ar[r]^{i} & L_{E,M_{E,R}⊗V} (X) \ar[r] & S_{E,R,V} (X) \ar[r] & 0}

(b) On the right hand side, both maps id ⊗v and Ψ_{X} are surjective.

Proof : The first row comes from the definition of 𝕊_{E,R} and j denotes the inclusion map while π is the quotient map. The second row is obtained from the first by tensoring with V (tensoring is right exact), using the right kA-module structure obtained in Lemma 7.2. The three vertical maps from the first to the second row are all given by α ↦ α ⊗ v and they are surjective because v generates V, hence V = kA · v. The third row comes from the definition of S_{E,R,V} and i denotes the inclusion map. Now we have to describe the vertical maps from the second to the third row. The middle vertical map is the identity because

L_{E,M_{E,R}}(X) ⊗_{kA} V = kC(X, E) ⊗_{kC(E,E)} M_{E,R} ⊗_{kA} V = L_{E,M_{E,R}⊗_{kA}V} (X) .

We claim that (j ⊗ id_{V})(J_{E,M_{E,R}}(X) ⊗_{kA} V ) is contained in J_{E,M_{E,R}⊗V} (X). It will then follow that j ⊗ id_{V} defines the vertical map on the left. This in turn shows that id induces the vertical map Ψ_{X} on the right and Ψ_{X} is surjective.

In order to prove the claim, let φ ⊗ f_{R} ∈ J_{E,M_{E,R}}(X) where φ ∈ kC(X, E). This means that

∀ρ ∈ kC(E, X) , (ρφ) · f_{R} = 0 .

It follows that (ρφ) · (f_{R} ⊗ v) = 0 in M_{E,R} ⊗_{kA} V because ρφ only acts on the first term of the tensor product. This means that the element

φ ⊗ (f_{R} ⊗ v) ∈ L_{E,M_{E,R}⊗V} (X)

actually belongs to J_{E,M_{E,R}⊗V} (X). But this element is equal to

(φ ⊗ f_{R}) ⊗ v = (j ⊗ id_{V})(φ ⊗ f_{R} ⊗ v) ,

proving the claim.

7.7. Notation. Consider the diagram of Proposition 7.6. When X is allowed to vary, the morphisms Ψ_{X} on the right hand side define a surjective morphism of correspondence functors

Ψ : 𝕊_{E,R} ⊗_{kA} V ⟶ S_{E,R,V} ,

providing a direct link between the fundamental functor 𝕊_{E,R} and the simple functor S_{E,R,V} when V is simple.

Similarly, the right hand side composite Ψ_{X} ∘(id ⊗v) yields a surjective morphism

Φ := Ψ ∘ (id ⊗v) : 𝕊_{E,R} ⟶ S_{E,R,V}

which is a morphism of correspondence functors because it is induced by the middle vertical morphism

L_{E,M_{E,R}} ⟶ L_{E,M_{E,R}⊗_{kA}V} ,

which is obviously a morphism of correspondence functors. This defines the morphism Φ appearing in Proposition 4.8.

Our goal is to prove that Ψ : 𝕊_{E,R} ⊗_{kA} V → S_{E,R,V} is an isomorphism. We prepare the ground with the following lemma, which is analogous to Lemma 4.3. In the proof, we need the full strength of Theorem 7.5, based in turn on Theorem 6.6. Since we consider simple modules, we assume that k is a field.

7.8. Lemma. Let k be a field, let (E, R) be a finite poset, let A = Aut(E, R), and let V be a simple kA-module. Let α ∈ 𝕊_{E,R}(X) ⊗_{kA} V where X is some finite set. Then ρ · α = 0 for every ρ ∈ kC(E, X) if and only if α = 0.

Proof : Since V is a simple kA-module and A is a finite group, we claim that there exists an injective homomorphism of kA-modules λ : V → kA. This follows from the following argument. If V^{♮} denotes the dual simple module, there exists a surjective homomorphism π : kA → V^{♮}, which we dualize to obtain an injective homomorphism π^{♮} : V → (kA)^{♮}. Now the group algebra of a finite group is a symmetric algebra, so (kA)^{♮} ≅ kA, and this defines the injective homomorphism λ : V → kA.

If M is a free right kA-module, then

id_{M} ⊗λ : M ⊗_{kA} V ⟶ M ⊗_{kA} kA

remains injective. This is clear if M is free of rank one and then it follows in general by taking direct sums. Now we compose with the isomorphism M ⊗_{kA} kA ≅ M and we take M = 𝕊_{E,R}(X), which is indeed a free right kA-module by Theorem 7.5. We obtain an injective homomorphism

λ_{X} : 𝕊_{E,R}(X) ⊗_{kA} V ⟶ 𝕊_{E,R}(X)

which is easily seen to define a morphism of correspondence functors

λ : 𝕊_{E,R} ⊗_{kA} V ⟶ 𝕊_{E,R}

because we use only the right module structure, whereas correspondences act on the left.

For every ρ ∈ kC(E, X), there is a commutative diagram

\xymatrix{𝕊_{E,R}(X) ⊗_{kA} V \ar[r]^{λ_{X}} \ar[d]^{ρ} & 𝕊_{E,R}(X) \ar[d]^{ρ} \\ 𝕊_{E,R}(E) ⊗_{kA} V \ar[r]^{λ_{E}} & 𝕊_{E,R}(E)}

Whenever our given element α ∈ 𝕊_{E,R}(X) ⊗_{kA} V satisfies ρ · α = 0 for every ρ ∈ kC(E, X), we also have ρ · λ_{X}(α) = 0 for every ρ ∈ kC(E, X). But this implies that λ_{X}(α) = 0 by Lemma 4.3. Since λ_{X} is injective, α = 0, as required.

Now we come to our main description of simple correspondence functors.

7.9. Theorem. Let k be a field, let (E, R) be a finite poset, let A = Aut(E, R), and let V be a simple kA-module. The morphism Ψ : 𝕊_{E,R} ⊗_{kA} V → S_{E,R,V} is an isomorphism.

Proof : For any finite set X and any ρ ∈ kC(E, X), there is a commutative diagram

\xymatrix{𝕊_{E,R}(X) ⊗_{kA} V \ar[r]^{Ψ_{X}} \ar[d]^{ρ} & S_{E,R,V} (X) \ar[d]^{ρ} \\ 𝕊_{E,R}(E) ⊗_{kA} V \ar[r]^{Ψ_{E}} & S_{E,R,V} (E)}

Note that Ψ_{E} is an isomorphism because

𝕊_{E,R}(E) ⊗_{kA} V = M_{E,R} ⊗_{kA} V = S_{E,R,V} (E)

and Ψ is induced by the identity morphism L_{E,M_{E,R}} ⊗_{kA} V → L_{E,M_{E,R}⊗_{kA}V}. Let α ∈ 𝕊_{E,R}(X) ⊗_{kA} V such that Ψ_{X}(α) = 0. Then

Ψ_{E}(ρ · α) = ρ · Ψ_{X}(α) = 0

for every ρ ∈ kC(E, X). Since Ψ_{E} is an isomorphism, we obtain ρ · α = 0 for every ρ ∈ kC(E, X). Therefore α = 0 by Lemma 7.8. This proves that Ψ_{X} is injective and we know that it is surjective by construction.

We can finally prove one of our main results, namely the determination of the dimension of any evaluation of a simple correspondence functor. Because of the link with lattices (via the morphism Θ_{T}), it is convenient to state the result for R^{op} rather than R. But this is actually a minor point because S_{E,R,V} is isomorphic to the dual of S_{E,R^{op},V^{♮}} where V^{♮} is the dual module, by Theorem 9.8 in [BT3].

7.10. Theorem. Let k be a field. Let (E, R) be a poset and let V be a simple left k Aut(E, R)-module. Let T be a lattice such that Irr(T) = (E, R) and such that the restriction homomorphism Aut(T) → Aut(E, R) is an isomorphism. Let G = E ⊔ {t ∈ T | t = r^{∞}σ^{∞}(t)} ⊆ T (see Definition 2.10).

For any finite set X, the dimension of S_{E,R^{op},V} (X) is given by

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

Proof : By Theorem 7.5, 𝕊_{E,R^{op}}(X) is isomorphic to the direct sum of n_{X} copies of the free right module k Aut(E, R), for some n_{X} ∈ ℕ. In particular

dim_{k} 𝕊_{E,R^{op}}(X) = n_{X} | Aut(E, R)| .

By Theorem 7.9, the simple functor S_{E,R^{op},V} is isomorphic to 𝕊_{E,R^{op}} ⊗_{k Aut(E,R)} V, using the obvious equality Aut(E, R) = Aut(E, R^{op}). Thus we obtain

S_{E,R^{op},V} (X) ≅ 𝕊_{E,R^{op}}(X)⊗_{k Aut(E,R)} V ≅ n_{X}(k Aut(E, R))⊗_{k Aut(E,R)} V ≅ n_{X}V .

Hence dim_{k} 𝕊_{E,R^{op},V} (X) = n_{X} dim_{k} V. Therefore

dim_{k} 𝕊_{E,R^{op},V} (X) = \frac{dim_{k} V}{| Aut(E, R)|} dim_{k} 𝕊_{E,R^{op}}(X) .

The result now follows from Theorem 6.6.

8. Simple modules for the algebra of relations

Let X be a fixed finite set and consider the monoid R_{X} = C(X, X) of all relations on X, also known as the monoid of all Boolean matrices of size |X|. As before, write kR_{X} for the algebra of this monoid. Throughout this section, we assume that the base ring k is a field. We give the parametrization of all simple modules for the algebra kR_{X} and then solve the open problem of giving a formula for their dimension. We also give an explicit description for the action of relations on every simple kR_{X}-module.

We mentioned in the introduction that, for the parametrization of all simple modules for the algebra kR_{X}, we do not use the Munn-Ponizovsky theory using Green’s J -classes. We use instead the parametrization of all simple correspondence functors S_{E,R,V} by isomorphism classes of triples (E, R, V) (see Theorem 4.5). The method is now very elementary since it simply uses the fact that every evaluation of a simple functor yields a simple module, or zero, and that every simple module arises in that way. This mechanism goes back to Green (6.2 in [Gr]) but we also give some more recent references. 8.1. Theorem. Let X be a finite set.

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

(b) The simple module parametrized by the triple (E, R, V) is S_{E,R,V} (X), where S_{E,R,V} is the simple correspondence functor corresponding to the triple (E, R, V).

Proof : We first recall that the evaluation S(X) of a simple correspondence functor S at a finite set X is either zero or a simple kR_{X}-module. The proof is very easy and appears in Proposition 3.2 of [We], or also in Proposition 2.7 of [BT2].

Conversely, we claim that any simple kR_{X}-module W occurs as the evaluation of some simple correspondence functor S, that is, W ≅ S(X). Explicitly, S is the functor L_{X,W} /J_{X,W} considered in Lemma 4.3. The claim is Lemma 2.5 of [BT2] which quotes the first lemma of [Bo]. It also appears in Proposition 3.2 of [We], where it is attributed to Green (6.2 in [Gr]). This requires to view kR_{X} = kC(X, X) as a category with a single object X, hence a full subcategory of kC. Proposition 3.2 of [We] or Proposition 2.7 of [BT2] also show that the simple correspondence functor S such that W ≅ S(X) is unique up to isomorphism. All these facts actually hold for the simple representations of any small category.

By Theorem 4.5, our simple correspondence functor S = S_{E,R,V} is parametrized by a triple (E, R, V), where E is a finite set, R is an order relation on E, and V is a simple k Aut(E, R)-module. Whenever W = S_{E,R,V} (X) ≠ {0}, we have |E| ≤ |X| because S_{E,R,V} vanishes on sets Y with |E| > |Y | (by Theorem 4.5). In order to obtain the parametrization of the statement, we also need to show that W = S_{E,R,V} (X) is nonzero if |E| ≤ |X|. This is clear if |E| = |X| because S_{E,R,V} (E) = T_{R,V} is nonzero (see the construction of S_{E,R,V} in Section 4). Knowing that S_{E,R,V} (E) ≠ {0}, Corollary 3.7 in [BT2] asserts precisely that S_{E,R,V} (X) ≠ {0} if |E| < |X|. This provides the required parametrization and completes the proof.

Note that we used at the end of the proof the non-vanishing of S_{E,R,V} (X) when |E| < |X|. This is a special property of correspondence functors (Corollary 3.7 in [BT2]) and it may not hold for representations of other small categories.

In view of Theorem 8.1, a formula for the dimension of any simple kR_{X}-module is now given by Theorem 7.10. More explicitly, we fix a poset (E, R) and a finite lattice T having (E, R) as the full subset of its join-irreducible elements. We can also choose T such that Aut(T) ≅ Aut(E, R) by taking for instance T = I_{↓}(E, R). We consider the simple kR_{X}-module S_{E,R^{op},V} (X), continuing to use R^{op} as in Theorem 7.10. We define the subset G of T as in Notation 2.10 and we write G = G_{E,R} to emphasize its dependence on (E, R). Its cardinality |G| only depends on (E, R), by Corollary 6.7. 8.2. Theorem. With the notation above, the dimension of a simple kR_{X}-module is given by the formula

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

Proof : This is a restatement of Theorem 7.10.

An explicit description can be given for the action of relations on the simple kR_{X}-module S_{E,R^{op},V} (X). We define a subset

B_{E,R,X} = {φ ∈ T^{X} | E ⊆ φ(X) ⊆ G_{E,R}} ⊆ T^{X} .

By Theorem 6.6, the surjective morphism Θ_{T} : F_{T} → 𝕊_{E,R^{op}} induces a k-module decomposition

F_{T} (X) = kB_{E,R,X} ⊕ Ker(Θ_{T,X}) ,

where kB_{E,R,X} is the k-subspace of F_{T} (X) with basis B_{E,R,X}. Thus we have a k-module isomorphism

𝕊_{E,R^{op}}(X) ≅ kB_{E,R,X} .

The family of subspaces kB_{E,R,X} do not form a subfunctor of F_{T}, but they can be used to describe the evaluations of the functors 𝕊_{E,R^{op}} and S_{E,R^{op},V}.

We explain a procedure for modifying an element φ ∈ T^{X} modulo Ker(Θ_{T,X}) in order to project it in kB_{E,R,X}. In Theorem 5.6, we introduced an element u_{T} ∈ k(T^{T}) which has the property that, for any φ ∈ T^{X}, the composition u_{T} ∘ φ is a k-linear combination of maps f ∈ T^{X} such that f(X) ⊆ G_{E,R}. (Actually, u_{T} is idempotent, by Theorem 5.8.) Moreover,

u_{T} ∘ φ ≡ φ (mod Ker(Θ_{T,X})) .

Let π_{T,X} be the k-linear idempotent endomorphism of k(T^{X}) defined by

∀φ ∈ T^{X}, π_{T,X}(φ) = \{ \begin{matrix}φ & if E ⊆ φ(X) , \\ 0 & otherwise . \end{matrix}

By Theorem 4.10,

π_{T,X}(φ) ≡ φ (mod Ker(Θ_{T,X})) .

Then, for any map φ ∈ T^{X}, we obtain

π_{T,X}(u_{T} ∘ φ) ∈ kB_{E,R,X} ,

that is, a k-linear combination of maps f ∈ T^{X} such that E ⊆ f(X) ⊆ G_{E,R}. Moreover,

π_{T,X}(u_{T} ∘ φ) ≡ φ (mod Ker(Θ_{T,X})) .

Thus if we lift arbitrarily a basis element of 𝕊_{E,R^{op}}(X) to φ ∈ F_{T} (X), we can modify it modulo Ker(Θ_{T,X}) to obtain an element of kB_{E,R,X}. Applying this procedure to the action of a relation U ∈ C(X, X) on an element φ ∈ kB_{E,R,X}, we obtain

Uφ ≡ π_{T,X}(u_{T} ∘ Uφ) (mod Ker(Θ_{T,X})) ,

and π_{T,X}(u_{T} ∘ Uφ) belongs to kB_{E,R,X}.

As in Section 7, we tensor on the right with the k Aut(E, R)-module V, using the right action of Aut(E, R) on B_{E,R,X} defined by φ·σ := σ^{−1}∘φ for all σ ∈ Aut(E, R). By Theorem 7.9, we have isomorphisms

S_{E,R^{op},V} (X) ≅ 𝕊_{E,R^{op}}(X) ⊗_{k Aut(E,R)} V ≅ kB_{E,R,X} ⊗_{k Aut(E,R)} V ,

the second isomorphism being only k-linear.

This analysis proves the following result, which provides a computational method for describing the action of a relation on a simple kR_{X}-module.

8.3. Theorem. Fix the notation above.

(a) S_{E,R^{op},V} (X) ≅ kB_{E,R,X} ⊗_{k Aut(E,R)} V as k-vector spaces.

(b) Transporting the action of relations via this isomorphism, the action of a relation U ∈ C(X, X) on an element

φ ⊗ v ∈ kB_{E,R,X} ⊗_{k Aut(E,R)} V , (φ ∈ B_{E,R,X}, v ∈ V)

is given by

U · (φ ⊗ v) = π_{T,X}(u_{T} ∘ Uφ) ⊗ v .

Our last result gives the dimension of the Jacobson radical J(kR_{X}) of the kalgebra kR_{X}. We assume for simplicity that the field k has characteristic zero. 8.4. Theorem. Assume that k is a field of characteristic zero. Let J(kR_{X}) be the Jacobson radical of the k-algebra kR_{X} and let n = |X|. Then

dim J(kR_{X}) = 2^{n^{2}} − ∑_{e=0}^{n} ∑_{R} \frac{1}{| Aut(E, R)|}( ∑_{i=0}^{e}(−1)^{i}\binom{e}{i}(|G_{E,R}| − i)^{n})^{2} ,

where R runs over a set of representatives of Σ_{e}-conjugacy classes of order relations on the set E = {1, …, e}. The integer |G_{E,R}| is the cardinality of the set G_{E,R} defined in Notation 2.10. Note that if e = 0, then E = ∅, R = ∅ and |G_{E,R}| = 1 (by Example 2.11).

Proof : Since k has characteristic zero, the semi-simple algebra kR_{X}/J(kR_{X}) is separable, that is, it remains semi-simple after scalar extension to an algebraic closure \overline{k} of k. In other words, dim J(kR_{X}) does not change after this scalar extension. Therefore, we can assume that k = \overline{k}.

By Theorem 8.1, every simple kR_{X}-module has the form S_{E,R,V} (X) with |E| ≤ |X|, where S_{E,R,V} is the simple correspondence functor parametrized by the triple (E, R, V). In order to have a parametrization, we take E = {1, …, e} with 0 ≤ e ≤ n, we take R in a set of representatives as in the statement, and finally we take V in a set of representatives of isomorphism classes of simple k Aut(E, R)- modules.

Since the endomorphism algebra of a simple module is isomorphic to k, by Schur’s lemma and the assumption that k is algebraically closed, the dimension of the semisimple algebra kR_{X}/J(kR_{X}) is equal to the sum of the squares of the dimensions of all simple modules, by Wedderburn’s theorem. From the formula for the dimension of simple modules, we obtain

dim (kR_{X}/J(kR_{X})) = ∑_{E,R,V} ( dim S_{E,R,V} (X))^{2} = ∑_{E,R,V} ( dim S_{E,R^{op},V} (X))^{2}

= ∑_{E,R,V} (\frac{dim V}{| Aut(E, R)|})^{2}( ∑_{i=0}^{|E|}(−1)^{i}\binom{|E|}{i}(|G_{E,R}| − i)^{|X|})^{2}

= ∑_{e=0}^{n} ∑_{R} ( ∑_{V} \frac{(dim V)^{2}}{| Aut(E, R)|^{2}} )( ∑_{i=0}^{e}(−1)^{i}\binom{e}{i}(|G_{E,R}| − i)^{n})^{2}
= ∑_{e=0}^{n} ∑_{R} \frac{1}{| Aut(E, R)|}( ∑_{i=0}^{e}(−1)^{i}\binom{e}{i}(|G_{E,R}| − i)^{n})^{2} ,

because ∑_{V}(dim V)^{2} = dim(k Aut(E, R)) = | Aut(E, R)|, by semi-simplicity of the

group algebra in characteristic zero (Maschke’s theorem). Now

dim J(kR_{X}) = dim kR_{X} − dim (kR_{X}/J(kR_{X})) = 2^{n^{2}} − dim (kR_{X}/J(kR_{X}))

and the result follows.

If k is an algebraically closed field of prime characteristic p, the formula has to be modified in a straightforward manner, in order to take into account the Jacobson radical of k Aut(E, R). Then it seems likely that the same formula holds over any field of characteristic p (that is, kR_{X}/J(kR_{X}) is likely to be a separable algebra), but we leave this question open.

9. Examples

We state here without proofs a list of examples. For simplicity, we assume that the base ring k is a field (but many results actually remain true over an arbitrary commutative ring k). We first describe a few small cases for modules over the algebra kR_{X}, using the notation of Section 8. Then we give the decomposition of the functors F_{T} associated to some particular lattices T.

9.1. Example. Let X = ∅. There is a single relation on ∅, namely ∅, and kR_{∅} ≅ k. Then S_{∅,∅,k}(∅) ≅ kB_{∅,∅,∅} ⊗_{k} k ≅ k and the unique relation ∅ acts as the identity on k.

9.2. Example. Let X = {1}. There are 2 relations on {1}, namely ∅ and Δ_{{1}}.

For E = ∅, we get S_{∅,∅,k}({1}) ≅ kB_{∅,∅,{1}} ⊗_{k} k ≅ k and both relations act as the identity on k.

For E = {1}, we obtain S_{{1},Δ_{{1}},k}({1}) ≅ kB_{{1},Δ_{{1}},{1}} ⊗_{k} k ≅ k, the relation ∅ acts by zero, while Δ_{{1}} acts as the identity.

Moroever, kR_{{1}} ≅ k × k is a semi-simple algebra.

9.3. Example. Let X = {1, 2}. There are 2^{4} = 16 relations on {1, 2}, so kR_{{1,2}} has dimension 16.

For E = ∅, we get a simple kR_{{1,2}}-module S_{∅,∅,k}({1, 2}) of dimension 1.

For E = {1}, we get a simple kR_{{1,2}}-module S_{{1},Δ_{{1}},k}({1, 2}) of dimension 3. For E = {1, 2}, there are two relations in P_{E} up to conjugacy, namely the

equality relation Δ_{{1,2}} and the usual total order tot. Moreover, Aut({1, 2}, Δ_{{1,2}}) is a group of order 2, with two simple modules k_{+} and k_{−} (assuming that the characteristic of k is not 2). Therefore, we obtain two simple kR_{{1,2}}-modules of dimension 1

\begin{aligned}S_{\{1,2\},Δ_{\{1,2\}},k_{+}}(\{1, 2\}) & ≅ & kB_{\{1,2\},Δ_{\{1,2\}},\{1,2\}} ⊗_{kC_{2}} k_{+} , \\ S_{\{1,2\},Δ_{\{1,2\}},k_{−}}(\{1, 2\}) & ≅ & kB_{\{1,2\},Δ_{\{1,2\}},\{1,2\}} ⊗_{kC_{2}} k_{−} , \end{aligned}

For the other relation tot, we obtain a simple kR_{{1,2}}-module of dimension 2

S_{{1,2},tot,k}({1, 2}) ≅ kB_{{1,2},tot,{1,2}} ⊗_{k} k ≅ kB_{{1,2},tot,{1,2}} ,

Altogether, there are 5 simple kR_{{1,2}}-modules and the Jacobson radical has dimension 0. Therefore kR_{{1,2}} is semi-simple (provided the characteristic of k is not 2).

9.4. Example. For |X| = 3, the algebra kR_{X} is not semi-simple. The dimension of the Jacobson radical of kR_{X} is equal to 42, using either the computer software [GAP4] or the computer calculations obtained in [Br]. According to Theorem 8.4, this value can be recovered directly as follows :

Size e Poset(E, R) | Aut(E, R)| |G_{E,R}| ∑_{i=0}^{e}(−1)^{i}\binom{e}{i}(|G_{E,R}| − i)^{3} total
0  ∅  1  1  1  1
1  •  1  2  7  49
2  ••  2  4  18  162
\begin{matrix}• \\ • \end{matrix}  1  3  12  144
3  • • •  6  5  6  6
\begin{matrix}• \\ • \end{matrix} •  1  5  6  36

{• • \atop \/} ; •  2  5  6  18

• ; {/\ \atop • •}  2  5  6  18

• ; \begin{matrix}• \\ • \end{matrix}  1  6  6  36

In this case, the algebra kR_{X} has dimension 2^{3^{2}} = 512. The sum of the last column of this table is equal to 470, so we recover the dimension of the radical 42 = 512 − 470.

9.5. Example. For |X| = 4, the algebra kR_{X} has dimension 2^{4^{2}} = 65,536. The direct computation of the radical of such a big algebra seems out of reach of usual computers. However, using the formula of Theorem 8.4 and the structure of the 16 posets of cardinality 4, one can show by hand that the radical of kR_{X} has dimension 32,616.

For larger values of n = |X|, a computer calculation using Theorem 8.4 yields the following values for the dimension of J(kR_{X}) :

\begin{matrix}n = 5 & n = 6 & n = 7 & n = 8 \\ 29,446,050 & 67,860,904,320 & 562,649,705,679,642 & 18,446,568,932,288,588,616 \end{matrix}

We now move to examples of fundamental functors and functors associated to lattices.

9.6. Example. There are many examples of fundamental functors 𝕊_{E,R} for which the set G is the whole of T, for instance when T = ΛE. In all such cases, we have F_{T} /H_{T} ≅ 𝕊_{E,R}. Moreover, in many such cases, Aut(E, R) is the trivial group. Take for instance (E, R) to be a disjoint union of trees with branches of different length. In any such case, F_{T} /H_{T} ≅ 𝕊_{E,R} ≅ S_{E,R,k} is simple, provided k is a field.

Our next purpose is to decompose the functor F_{T} for some small lattices T. In order to use an inductive process, we use inclusions A → T where A is a distributive sublattice. We could as well use surjective morphisms T → A, as in Section 10 of [BT3], but the following general result shows that it does not matter.

9.7. Lemma. Let T and A be finite lattices and assume that A is distributive. Let σ : A → T be an injective join-preserving map. Then there is a surjective join-preserving map π : T → A such that πσ = id_{A}.

Proof : We define π(t) = ⋀_{\begin{matrix}a∈A \\ σ(a)≥t \end{matrix}} a. Then π is order-preserving and therefore

π(t_{1}) ∨ π(t_{2}) ≤ π(t_{1} ∨ t_{2}) for any t_{1}, t_{2} ∈ T. Now we have

π(t_{1}) ∨ π(t_{2}) = ( ⋀_{\begin{matrix}a_{1}∈A \\ σ(a_{1})≥t_{1} \end{matrix}} a_{1}) ∨ ( ⋀_{\begin{matrix}a_{2}∈A \\ σ(a_{2})≥t_{2} \end{matrix}} a_{2}) = ⋀_{\begin{matrix}a_{1},a_{2}∈A \\ σ(a_{1})≥t_{1} \\ σ(a_{2})≥t_{2} \end{matrix}}(a_{1} ∨ a_{2})

by distributivity of A. For any such pair (a_{1}, a_{2}), the join a_{1} ∨ a_{2} belongs to the set {a ∈ A | σ(a) ≥ t_{1} ∨ t_{2}} and therefore

⋀_{\begin{matrix}a_{1},a_{2}∈A \\ σ(a_{1})≥t_{1} \\ σ(a_{2})≥t_{2} \end{matrix}}(a_{1} ∨ a_{2}) ≥ ⋀_{\begin{matrix}a∈A \\ σ(a)≥t_{1}∨t_{2} \end{matrix}} a = π(t_{1} ∨ t_{2}) .

The equality π(t_{1}) ∨ π(t_{2}) = π(t_{1} ∨ t_{2}) follows.

If σ(a_{1}) ≤ σ(a_{2}), then σ(a_{1}∨a_{2}) = σ(a_{1})∨σ(a_{2}) = σ(a_{2}), and therefore a_{1}∨a_{2} = a_{2} by injectivity of σ, i.e. a_{1} ≤ a_{2}. It follows from this observation that, for any b ∈ A,

πσ(b) = ⋀_{\begin{matrix}a∈A \\ σ(a)≥σ(b) \end{matrix}} a = ⋀_{\begin{matrix}a∈A \\ a≥b \end{matrix}} a = b ,

hence πσ = id_{A}.

The property of Lemma 9.7 is reflected in the fact that the morphism F_{A} → F_{T} induced by σ must split, because the functor F_{A} is projective by Theorem 4.12 in [BT3] and injective by Theorem 10.6 in [BT2].

9.8. Example. Let T = ♢ be the lozenge, in other words the lattice of subsets of a set of cardinality 2 :

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

By Theorem 11.12 in [BT3], for any finite lattice T, we can split off from F_{T} simple functors 𝕊_{n} := 𝕊_{\underline{n},tot} ≅ S_{\underline{n},tot,k} corresponding to all totally ordered sequences ˆ0 ≤ d_{0} < d_{1} < … < d_{n} = ˆ1 in T. In the case of F_{♢}, we obtain

F_{♢} ≅ 𝕊_{0} ⊕ 3𝕊_{1} ⊕ 2𝕊_{2} ⊕ L

for some subfunctor L. We know that F_{♢} maps surjectively onto the fundamental functor 𝕊_{∘∘} associated to the (opposite) poset of irreducible elements of ♢, that is, a set of cardinality 2 ordered by the equality relation. Moreover, all the factors 𝕊_{n} lie in the subfunctor H_{♢}, because no totally ordered subset contains the two irreducible elements of ♢ (figured with an empty circle in the above picture). Therefore L maps surjectively onto 𝕊_{∘∘}.

We can evaluate F_{♢} at a set X of cardinality x, and take dimensions over k. By Theorem 6.6, we obtain

4^{x} = 1^{x} + 3(2^{x} − 1^{x}) + 2(3^{x} − 2 · 2^{x} + 1^{x}) + dim_{k} L(X) .

It follows that

dim_{k} L(X) = 4^{x} − 2 · 3^{x} + 2^{x} .

Now we apply Theorem 6.6 to the fundamental functor 𝕊_{∘∘}. The set G is the whole of T in this case, so dim_{k} 𝕊_{∘∘}(X) = 4^{x} − 2 · 3^{x} + 2^{x}.

Since L maps surjectively onto 𝕊_{∘∘} and dim_{k} L(X) = dim_{k} 𝕊_{∘∘}(X) for any finite set X, this surjection is an isomorphism. Hence

F_{♢} ≅ 𝕊_{0} ⊕ 3𝕊_{1} ⊕ 2𝕊_{2} ⊕ 𝕊_{∘∘} .

Since the lattice ♢ is distributive, F_{♢} is projective by Theorem 4.12 in [BT3]. It follows that each summand is a projective object in the category F_{k} of correspondence functors.

9.9. Example. Let T be the following lattice :

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

As in the previous example, F_{T} admits a direct summand isomorphic to

𝕊_{0} ⊕ 4𝕊_{1} ⊕ 3𝕊_{2} .

Moreover, there are three obvious sublattices of T isomorphic to ♢, which provide three direct summands of F_{T} isomorphic to 𝕊_{∘∘}. Thus we have a decomposition

F_{T} ≅ 𝕊_{0} ⊕ 4𝕊_{1} ⊕ 3𝕊_{2} ⊕ 3𝕊_{∘∘} ⊕ M

for some subfunctor M of F_{T}. Using arguments similar to those of the previous example, we get

F_{T} ≅ 𝕊_{0} ⊕ 4𝕊_{1} ⊕ 3𝕊_{2} ⊕ 3𝕊_{∘∘} ⊕ 𝕊_{∘∘∘} .

All the summands in this decomposition of F_{T}, except possibly 𝕊_{∘∘∘}, are projective functors. Since the lattice T is not distributive, the functor F_{T} is not projective (Theorem 4.12 in [BT3]), thus 𝕊_{∘∘∘} is actually not projective either.

9.10. Example. Let D be the following lattice :

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

As before, we know that F_{T} admits a direct summand isomorphic to a direct sum 𝕊_{0} ⊕ 4𝕊_{1} ⊕ 4𝕊_{2} ⊕ 𝕊_{3}. Moreover, there are two inclusions

[figure: •; •; ∘; ∘; ∘; ∘; ∘; •; •; and; •; •; ∘; ∘; ∘; ∘; ∘; •; •]

of the lattice ♢ into D, which yield two direct summands of F_{D} isomorphic to 𝕊_{∘∘}. So there is a decomposition

F_{D} ≅ 𝕊_{0} ⊕ 4𝕊_{1} ⊕ 4𝕊_{2} ⊕ 𝕊_{3} ⊕ 2𝕊_{∘∘} ⊕ N

for a suitable subfunctor N of F_{D}. As in the previous examples, the subfunctor N maps surjectively onto the fundamental functor 𝕊 \begin{matrix}∘ \\ ∘ \end{matrix} _{∘} associated to the (opposite)

poset \begin{matrix}∘ \\ ∘ \end{matrix} ∘ of irreducible elements of D. Computing dimensions, we obtain N ≅ 𝕊 \begin{matrix}∘ \\ ∘ \end{matrix} _{∘},

and therefore

F_{D} ≅ 𝕊_{0} ⊕ 4𝕊_{1} ⊕ 4𝕊_{2} ⊕ 𝕊_{3} ⊕ 2𝕊_{∘∘} ⊕ 𝕊 \begin{matrix}∘ \\ ∘ \end{matrix} _{∘} .

Again D is not distributive, so that F_{D} is not projective. Thus the functor 𝕊 \begin{matrix}∘ \\ ∘ \end{matrix} _{∘} is

not projective either.

Actually, the lattice D and the lattice T of the previous example are the smallest non-distributive lattices and they are used for the well-known characterization of distributive lattices (see Theorem 4.7 in [Ro]).

9.11. Example. Let C be the following lattice :

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

Again, we know that F_{C} admits a direct summand isomorphic to a direct sum 𝕊_{0} ⊕ 4𝕊_{1} ⊕ 5𝕊_{2} ⊕ 2𝕊_{3}. Moreover, the inclusion

[figure: •; •; ∘; ∘; ∘; ∘; ∘; •; •]

of ♢ in C yields a direct summand of F_{C} isomorphic to 𝕊_{∘∘}. So there is a decomposition

F_{C} ≅ 𝕊_{0} ⊕ 4𝕊_{1} ⊕ 5𝕊_{2} ⊕ 2𝕊_{3} ⊕ 𝕊_{∘∘} ⊕ Q

for some direct summand Q of F_{C}.

Now F_{C} maps surjectively onto the fundamental functor 𝕊_{∘ ; {/\ \atop ∘ ∘}} associated to the

opposite poset of its irreducible elements, and arguments as before yield an isomorphism Q ≅ 𝕊_{∘ ; {/\ \atop ∘ ∘}}, hence a decomposition

F_{C} ≅ 𝕊_{0} ⊕ 4𝕊_{1} ⊕ 5𝕊_{2} ⊕ 2𝕊_{3} ⊕ 𝕊_{∘∘} ⊕ 𝕊_{∘ ; {/\ \atop ∘ ∘}} .

Since C is distributive, F_{C} is projective and we conclude that 𝕊_{∘ ; {/\ \atop ∘ ∘}} is projective.

Taking dual functors corresponds to taking opposite lattices (see Theorem 8.9 and Remark 9.7 in [BT3]), so we get a decomposition

F_{C^{op}} ≅ 𝕊_{0} ⊕ 4𝕊_{1} ⊕ 5𝕊_{2} ⊕ 2𝕊_{3} ⊕ 𝕊_{∘∘} ⊕ 𝕊_{{∘ ∘ \atop \/} ; ∘} .

Therefore 𝕊_{{∘ ∘ \atop \/} ; ∘} is also projective.

9.12. Example. Let P be the following lattice :

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

that is, the direct product of a totally ordered lattice of cardinality 3 and a totally ordered lattice of cardinality 2.

We know that F_{P} admits a direct summand isomorphic to 𝕊_{0} ⊕ 5𝕊_{1} ⊕ 7𝕊_{2} ⊕ 3𝕊_{3} and the inclusions

[figure: •; •; ∘; •; ∘; ∘; ∘; ∘; •; •; •; •; ∘; •; ∘; ∘; ∘; ∘; •; •; •; •; ∘; •; ∘; ∘; ∘; ∘; •; •]

of ♢ in P yield 3 direct summands of F_{P} isomorphic to 𝕊_{∘∘}. Moreover, the inclusions

[figure: •; •; ∘; ∘; ∘; •; ∘; ∘; ∘; •; •; and; ∘; •; •; ∘; •; ∘; ∘; ∘; ∘; •; •]

of C and C^{op} in P yield direct summands 𝕊_{{∘ ∘ \atop \/} ; ∘} and 𝕊_{∘ ; {/\ \atop ∘ ∘}} of F_{P}, hence there is a

direct summand U of F_{P} such that

F_{P} ≅ 𝕊_{0} ⊕ 5𝕊_{1} ⊕ 7𝕊_{2} ⊕ 3𝕊_{3} ⊕ 3𝕊_{∘∘} ⊕ 𝕊_{{∘ ∘ \atop \/} ; ∘} ⊕ 𝕊_{∘ ; {/\ \atop ∘ ∘}} ⊕ U .

Since the lattice P is distributive, the functor F_{P} is projective, hence U is projective. Now F_{P} maps surjectively onto the fundamental functor 𝕊 \begin{matrix}∘ \\ ∘ \end{matrix} _{∘}, and H_{P} is contained

in the kernel of this surjection. It follows that U maps surjectively onto 𝕊 \begin{matrix}∘ \\ ∘ \end{matrix} _{∘}, which

is a simple functor, as k is a field and the poset \begin{matrix}∘ \\ ∘ \end{matrix} ∘ has no nontrivial automorphisms.

A more involved analysis shows that U is indecomposable and is a projective cover of the simple functor 𝕊 \begin{matrix}∘ \\ ∘ \end{matrix} _{∘}. Moreover, one can show that the functor U is

uniserial, with a filtration

0  _{𝕊 _{\begin{matrix}∘ \\ ∘ \end{matrix} _{∘}}} ⊂  W  _{𝕊 ∘ ∘ ; /\/ ; ∘ ∘} ⊂  V  _{𝕊 _{\begin{matrix}∘ \\ ∘ \end{matrix} _{∘}}} ⊂  U ,

where W ≅ U/V ≅ 𝕊 \begin{matrix}∘ \\ ∘ \end{matrix} _{∘}, and V/W is isomorphic to the simple functor 𝕊_{∘ ∘ ; /\/ ; ∘ ∘}

associated to the poset [figure: ∘; ∘; ∘; ∘] of cardinality 4. An easy consequence of this is

that

Ext_{F_{k}}^{1}(𝕊 \begin{matrix}∘ \\ ∘ \end{matrix} _{∘}, 𝕊 /\/_{∘ ∘}^{∘ ∘}) ≅ Ext_{F_{k}}^{1}(𝕊 /\/_{∘ ∘}^{∘ ∘}, 𝕊 \begin{matrix}∘ \\ ∘ \end{matrix} _{∘}) ≅ k .

References

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

[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 finiteness conditions, J. Algebra 495 (2018), 150–198.

[BT3] S. Bouc, J. Thévenaz. Correspondence functors and lattices, J. Algebra 518 (2019), 453–518.

[BBHM] R.L. Brandon, K.H. Butler, D.W. Hardy, G. Markowsky. Cardinalities of D-classes in B_{n}, Semigroup Forum 4 (1972), 341–344.

[BE] M.R. Bremner, M. El Bachraoui. On the semigroup algebra of binary relations, Comm. Algebra 38 (2010), 3499–3505.

[Br] M.R. Bremner. Structure of the rational monoid algebra for Boolean matrices of order 3, Linear Alg. and its Applications 449 (2014), 381–401.

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

[Di] Y.I. Diasamidze. Complete semigroups of binary relations, J. Math. Sci. (N. Y.) 117 (2003), no. 4, 4271–4319.

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

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

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

[Gr] J.A. Green. Polynomial representations of GL_{n}, Springer Lecture Notes in Mathematics no. 830 (1980).

[Ki] K.H. Kim. Boolean Matrix Theory and Applications, Dekker, 1982.

[KR] K.H. Kim, F. Roush. Linear Representations of Semigroups of Boolean Matrices, Proc. Amer. Math. Soc. 63 (1977), 203–207.

[PW] R.J. Plemmons, M.T. West. On the semigroup of binary relations, Pacific J. Math. 35 (1970), 743–753.

[Ro] S. Roman. Lattices and ordered sets, Springer, 2008.

[Sc1] S. Schwarz. On the semigroup of binary relations on a finite set, Czechoslovak Math. J. 20(95) (1970), 632–679.

[Sc2] S. Schwarz. The semigroup of fully indecomposable relations and Hall relations, Czechoslovak Math. J. 23(98) (1973), 151–163.

[Sta] R.P. Stanley. Enumerative Combinatorics, Vol. I, Second edition, Cambridge studies in advanced mathematics 49, Cambridge University Press, 2012.

[Ste] I. Stein. Algebras of Ehresmann semigroups and categories, Semigroup Forum 95 (2017), 509–526.

[St1] B. Steinberg. Möbius functions and semigroup representation theory, J. Combin. Theory (Series A) 113 (2006), 866–881.

[St2] B. Steinberg. Representation Theory of Finite Monoids, Springer, 2016.

[We] P. Webb. An introduction to the representations and cohomology of categories, in: M. Geck, D. Testerman, J. Thévenaz (Eds.), “Group Representation Theory”, EPFL Press, Lausanne, 2007, pp. 149–173.

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, Institut de mathématiques, EPFL, Station 8, CH-1015 Lausanne, Switzerland.

jacques.thevenaz@epfl.ch