CORRESPONDENCE FUNCTORS AND DUALITY

SERGE BOUC AND JACQUES THÉVENAZ

Abstract. A correspondence functor is a functor from the category of finite sets and correspondences to the category of k-modules, where k is a commutative ring. By means of a suitably defined duality, new correspondence functors are constructed, having remarkable properties. In particular, their evaluation at any finite set is always a free k-module and an explicit formula is obtained for its rank. The results use some subtle new ingredients from the theory of finite lattices.

1. Introduction

Over the last few decades, the representation theory of small categories has played an increasingly important role in algebra, see for instance [Bo, FT, NSS, SS, We1, We2]. In the special case of the category with finite sets as objects and correspondences as morphisms, this theory turns out to be very rich and has been developed in [BT2, BT3, BT4, BT5, BT6]. A correspondence functor is a functor from the category of finite sets and correspondences to the category of k-modules, where k is a commutative ring. In particular, simple functors have been classified and a k-basis has been obtained for their evaluation at any finite set, with an explicit formula for the rank. The key for such results is the construction of some special functors 𝕊_{E,R}, which we called fundamental functors, depending on a finite set E and a partial order relation R on E. The purpose of the present paper is to obtain a vast generalisation of this construction.

For any finite lattice T, we studied in [BT3] a correspondence functor F_{T} whose evaluation F_{T} (X) at a finite set X is equal to the free k-module on the set T^{X} of all maps from X to T. Associated with any join-morphism α : T → T′^{op} of finite lattices, we introduce here a suitable pairing of functors F_{T} × F_{T′} → k and, by passing to the quotient by the left kernel K_{α} of this pairing, we obtain a correspondence functor 𝕊_{α} = F_{T} /K_{α} which only depends on the given morphism α. The opposite of T′ appears for reasons explained in the construction. One of our main results produces a k-basis for the evaluation 𝕊_{α}(X) at a finite set X, with an explicit formula for the rank. The fundamental functors 𝕊_{E,R} mentioned above are just a very special case.

After a preliminary section on correspondence functors, we carry out in Section 3 the construction of 𝕊_{α}. For any given join-morphism α : T → T′^{op} of finite lattices, this construction uses a certain subset Φ_{α} of the set Irr(T) of all join-irreducible elements of the lattice T.

Finite lattices played a central role throughout our work in [BT3, BT4] and this is again the case here. Actually, several new structural results on the lattice T can be brought out from the mere presence of the join-morphism α. This lattice-theoretic part is developed in Section 4 and is a cornerstone for what comes next.

Date: November 24, 2022.

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

Key words and phrases. Finite set, correspondence, functor category, simple functor, poset, lattice.

In Section 5, we produce a set of generators for 𝕊_{α}(X), where X is any finite set, and we then prove in Section 6 that this generating set is a k-basis of S_{α}(X). The key ingredient is a subset G_{α} of T containing Φ_{α}, defined using the lattice-theoretic developments of Section 4. The main result takes the following form :

1.1. Theorem. Let α : T → T′^{op} be a join-morphism of finite lattices. Then for any finite set X, the set {φ ∈ T^{X} | Φ_{α} ⊆ φ(X) ⊆ G_{α}} maps bijectively to a k-basis of 𝕊_{α}(X) = F_{T} (X)/K_{α}(X).

As mentioned above, this result generalises the theorem obtained in [BT4] for fundamental functors and the methods are inspired by those used there, but the actual proofs are new and more involved. The mere fact that the theorem proved in [BT4] is a special case is not obvious and needs to be established. We do so in Section 7.

In Section 8, we mention the more specific case when α is injective and in Section 9 we give an explicit description of the minimal nonzero evaluation 𝕊_{α}(Φ_{α}). Finally, in Sections 10 and 11, two rather intricate results are proved, which will be used in a future paper but are also of independent interest.

2. Preliminaries

Finite lattices are essential tools in [BT3, BT4, BT5, BT6] and they continue to play a crucial role in the present work. If T is a finite lattice, we write ≤ for its (partial) order relation, ∨ for its join, ∧ for its meet, ˆ0_{T}, or simply ˆ0, for its minimal element and ˆ1_{T}, or simply ˆ1, for its maximal element. For any s, t ∈ T with s ≤ t, intervals are defined by

[s, t] = {a ∈ T | s ≤ a ≤ t} , ]s, t] = {a ∈ T | s < a ≤ t} , [s, t[= {a ∈ T | s ≤ a < t} .

We occasionally write [s, t]_{T} = [s, t] when we need to emphasize that we work inside the ambient lattice T. An element of T is called irreducible (or join-irreducible) if it cannot be written as the join of some subset of strictly smaller elements of T. In particular, ˆ0 is not irreducible because it is an empty join. We write Irr(T) for the set of irreducible elements of T, viewed as a full subposet of T. The opposite lattice T^{op} of a finite lattice T is obtained by reversing the partial order, swapping ∨ and ∧ and also swapping ˆ0 and ˆ1.

We work with the category L having all finite lattices as objects and joinmorphisms as morphisms. Recall that a map α : T → T′ between two finite lattices is a join-morphism if, for any (finite) subset S of T, we have

α( ⋁_{s∈S} s) = ⋁_{s∈S} α(s)

and in particular α(ˆ0) = ˆ0 by using an empty join. Equivalently, α is a joinmorphism if and only if α(s∨t) = α(s)∨α(t) for all s, t ∈ T and α(ˆ0) = ˆ0. It would be natural to view L as the category of finite join-semilattices, but we do not do so, because a finite join-semilattice is in fact a lattice. Indeed, recall that the meet s ∧ t is uniquely determined by the (finite) join

s ∧ t = ⋁_{\begin{matrix}a∈T \\ a≤s \\ a≤t \end{matrix}} a .

We use only join-morphisms as morphisms between finite lattices. We emphasize that, in general, a join-morphism does not preserve meets. Consequently, the image Im(α) of a join-morphism α : T → T′ may not be a sublattice of T′. More precisely, Im(α) is only join-closed in T′ and the meet of Im(α) inherited by its join is in general different from the meet of T′.

Whenever k is a commutative ring, we also need the k-linearization kL of the category L. Its objects are again the finite lattices, the set of morphisms Hom_{kL}(T, T′) is the free k-module with basis Hom_{L}(T, T′), and the composition of morphisms is the k-bilinear extension of the composition in L.

If α : T → T′ is a join-morphism, then α^{op} : T′^{op} ⟶ T^{op} is the map defined by

α^{op}(t′) = ⋁_{\begin{matrix}t∈T \\ α(t)≤t′ \end{matrix}} t .

In other words, α^{op}(t′) is the greatest element of α^{−1}([ ˆ0, t′]). This definition goes back to E.H. Spanier and J.H.C. Whitehead [SW, Wh], who introduced this functorial duality in the category of join-homomorphisms of finite lattices but used it only for their main interest, namely CW-complexes and CW-lattices. It is proved in Section 4 of [SW], or in Lemma 8.1 of [BT3], that α^{op} is a join-morphism from T′^{op} to T^{op} and that (α^{op})^{op} = α.

Now we move to representation theory, as developed in [BT2, BT3, BT4]. We recall that a correspondence R from a finite set X to a finite set Y is just a subset of Y × X and that R^{op} ⊆ X × Y is defined by (x, y) ∈ R^{op} if and only if (y, x) ∈ R. Moreover, correspondences can be composed in the usual way : if S ⊆ Z × Y and R ⊆ Y × X, then

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

If k is a commutative ring, a correspondence functor (over k) is a functor from the category of finite sets and correspondences to the category of k-modules. We let F_{k} be the category of all correspondence functors over k, with natural transformations as morphisms. This is an abelian category. If F is a correspondence functor and R ⊆ Y × X is a correspondence, we use a left action of R for the k-linear map F (R) : F (X) → F (Y), namely we set, for any v ∈ F (X),

R · v = F (R)(v) ∈ F (Y) ,

and we often omit the dot and write simply Rv.

A main example is the correspondence functor F_{T} associated with a finite lattice T, introduced in [BT3]. Its evaluation at a finite set X is the free k-module with basis T^{X}, where T^{X} denotes the set of all maps X → T. For any φ ∈ T^{X}, the left action Rφ of a correspondence R ⊆ Y × X is the map Y → T defined by

(Rφ)(y) = ⋁_{\begin{matrix}x∈X \\ (y,x)∈R \end{matrix}} φ(x) .

It is very easy to check that F_{T} is a correspondence functor. Any join-morphism α : T → T′ induces a k-linear map F_{α} : F_{T} → F_{T′} defined on the k-basis by F_{α}(φ) = α ∘ φ, for any φ ∈ T^{X}. The following main result is Theorem 4.8 in [BT3].

2.1. Theorem. The assignment sending a finite lattice T to F_{T}, and a joinmorphism α : T → T′ to the k-linear map F_{α} : F_{T} → F_{T′}, yields a k-linear functor

F_{?} : kL ⟶ F_{k}

which is fully faithful.

We end this section with a discussion of duality, which is a main tool in this paper. Let F be a correspondence functor over k. The dual F^{♮} of F is the correspondence functor defined by F^{♮}(X) = Hom_{k}(F (X), k) for any finite set X and

(R · g)(v) = g(R^{op} · v)

for any R ⊆ Y × X, g ∈ F^{♮}(X) and v ∈ F (Y). Whenever F and G are correspondence functors, a functorial pairing F × G → k is a family of k-bilinear forms

(−, −)_{X} : F (X) × G(X) ⟶ k ,

where X runs through finite sets, satisfying

(Ru, v)_{Y} = (u, R^{op}v)_{X}

for all u ∈ F (X), v ∈ G(Y), and R ⊆ Y × X. It is elementary to check that a functorial pairing F × G → k induces a morphism of correspondence functors

λ : G ⟶ F^{♮}

and that conversely any such λ determines a functorial pairing F × G → k.

An important example is provided by the following construction. Whenever T is a finite lattice, consider the family of k-bilinear forms

(− | −)_{X} : F_{T} (X) × F_{T^{op}}(X) ⟶ k

defined on the k-bases elements φ ∈ T^{X} and ψ ∈ (T^{op})^{X} by

(φ | ψ)_{X} = \{ \begin{matrix}1 & if φ ≤ ψ, i.e. φ(x) ≤ ψ(x), ∀x ∈ X, \\ 0 & otherwise. \end{matrix}

This defines a functorial pairing F_{T} × F_{T^{op}} → k, by Lemma 8.6 in [BT3]. Our next result is Theorem 8.9 in [BT3].

2.2. Proposition.

(a) The basis T^{X} of F_{T} (X) has a dual basis, namely a basis {ψ^{∗} | ψ ∈ T^{X}} of F_{T^{op}} given by

ψ^{∗} = ∑_{\begin{matrix}ρ∈T^{X} \\ ρ≤ψ \end{matrix}} μ(ρ, ψ)ρ^{o} ,

where ρ^{o} is the map ρ, viewed as a map from X to T^{op}, and where μ denotes the Möbius function of the poset T^{X}.

(b) The morphism λ : F_{T^{op}} → F_{T}^{♮} induced by the functorial pairing above is an isomorphism (i.e. nondegeneracy in the strong sense).

3. The main constructions

Let T and T′ be finite lattices. The main purpose of this section is to construct, by means of a suitably defined functorial pairing F_{T} ×F_{T′} → k, a quotient functor of F_{T} obtained by passing to the quotient by the left kernel of this pairing. This provides a way of constructing many new correspondence functors, which turn out to have remarkable properties. We will see later in Section 7 that the fundamental functors introduced in [BT3] are very special cases of the present general construction.

The main context for our constructions is the following. Let α : T → T′ and β : T′ → T be maps such that

(3.1)  ∀(t, t′) ∈ T × T′, t′ ≤ α(t) ⟺ t ≤ β(t′) .

3.2. Lemma. Let T and T′ be finite lattices.

(a) If the maps α : T → T′ and β : T′ → T satisfy Condition 3.1, then α is a join-morphism from T to T′^{op} and β is a join-morphism from T′ to T^{op}. In particular, the maps α : T → T′ and β : T′ → T are order-reversing.

(b) β is equal to α^{op} : (T′^{op})^{op} = T′ → T^{op}. In particular, β is uniquely determined by α.

(c) Conversely, if α : T → T′^{op} is a join-morphism and if we set β = α^{op}, then α and β fulfill Condition 3.1.

Proof : (a) For any t_{1}, t_{2} ∈ T and for any t′ ∈ T′, we have

t′ ≤ α(t_{1} ∨ t_{2}) ⟺ t_{1} ∨ t_{2} ≤ β(t′)
⟺ t_{1} ≤ β(t′) and t_{2} ≤ β(t′)
⟺ t′ ≤ α(t_{1}) and t′ ≤ α(t_{2})
⟺ t′ ≤ α(t_{1}) ∧ α(t_{2}) .

It follows that α(t_{1} ∨ t_{2}) = α(t_{1}) ∧ α(t_{2}). Similarly β(t′_{1} ∨ t′_{2}) = β(t′_{1}) ∧ β(t′_{2}) for any t′_{1}, t′_{2} ∈ T′.

(b) It follows from Condition 3.1 that

∀t′ ∈ T′, β(t′) = ⋁_{\begin{matrix}t∈T \\ t≤β(t′) \end{matrix}} t = ⋁_{\begin{matrix}t∈T \\ t′≤α(t) \end{matrix}} t .

In other words β = α^{op}.

(c) The definition of β = α^{op} yields the above formula for β(t′). If t′ ≤ α(t), then t is one of the terms in the join and therefore t ≤ β(t′). For the reverse implication, use the fact that β^{op} = α and apply the same argument.

3.3. Convention. Lemma 3.2 shows that we only need a given join-morphism α : T → T′^{op} to obtain an associated map β satisfying Condition 3.1. For this reason, we shall always work with a fixed join-morphism α and use a notation which includes α if necessary. Moreover, for the sake of simplicity, we shall usually define β = α^{op}.

3.4. Lemma. Let T and T′ be finite lattices, let α : T → T′^{op} be a join-morphism, and let β = α^{op}.

(a) t ≤ βα(t), for any t ∈ T, and t′ ≤ αβ(t′), for any t′ ∈ T′.

(b) αβα = α and βαβ = β.

Proof : Both assertions follow from the fact that β and α are adjoint contravariant functors between T and T′, viewed as categories. In more elementary terms, for t ∈ T, Condition 3.1 applied to t′ = α(t) implies that t ≤ βα(t). Similarly t′ ≤ αβ(t′), for any t′ ∈ T′. Taking t′ = α(t) gives α(t) ≤ αβα(t). On the other hand α(t) ≥ αβα(t) because t ≤ βα(t) and α is order-reversing. Therefore αβα = α, and similarly βαβ = β.

It follows from Lemmas 3.2 and 3.4 that α and β are inverse Galois connections of posets (see Chapter 3 of [Ro] for this standard notion). We can also view α and β as adjoint contravariant functors if we consider the posets T and T′ as categories in the usual way.

We now introduce the main ingredient for our constructions.

3.5. Notation. Given a join-morphism α : T → T′^{op} and β = α^{op}, we set

Φ_{α} := {f ∈ Irr(T) | α(f) ∈ Irr(T′), βα(f) = f} ,
Φ′_{α} := {f′ ∈ Irr(T′) | β(f′) ∈ Irr(T), αβ(f′) = f′} .

We view Φ_{α} and Φ′_{α} as full subposets of T and T′, respectively. Whenever there is no possible confusion, we will also write Φ = Φ_{α} and Φ′ = Φ′_{α}. We observe that, if we switch the roles of T, T′ and α, β, we obtain Φ_{β} = Φ′_{α} and Φ′_{β} = Φ_{α}.

We emphasize that the definition of Φ′_{α} involves the irreducible elements of T′ and not those of T′^{op}, despite the fact that the target of α is T′^{op}. Our next lemma also uses implicitly this remark.

3.6. Lemma. The restriction of α to Φ_{α} is a poset isomorphism Φ_{α} → Φ′_{α}^{op}. The inverse isomorphism Φ′_{α} → Φ_{α}^{op} is the restriction of β to Φ′_{α}.

Proof : Since α and β are both order-reversing maps, it suffices to prove that the restrictions of α to Φ = Φ_{α} and the restriction of β to Φ′ = Φ′_{α} are bijections, and inverse to one another. If f ∈ Φ, then f′ = α(f) ∈ Irr(T′) by the definition of Φ, and f = β(f′). Hence β(f′) ∈ Irr(T), and αβ(f′) = αβα(f) = α(f) = f′, by Lemma 3.4. It follows that f′ ∈ Φ′, so α(Φ) ⊆ Φ′. The reverse inclusion also holds because αβ(f′) = f′ for any f′ ∈ Φ′. Therefore α(Φ) = Φ′, and similarly β(Φ′) = Φ.

Our next lemma introduces the technical conditions which will be used for the definition of the functorial pairing we are aiming for. Recall that the notation φ_{1} ≤ φ_{2} for φ_{1}, φ_{2} ∈ T^{X} means that φ_{1}(x) ≤ φ_{2}(x) for all x ∈ X.

3.7. Lemma. Let X be a finite set. For any maps φ ∈ T^{X} and ψ ∈ (T′)^{X}, the following conditions are equivalent:

(a) ψ ≤ α ∘ φ and, for any f ∈ Φ_{α}, there exists x ∈ X such that φ(x) = f and ψ(x) = α(f).

(b) φ ≤ β ∘ ψ and, for any f′ ∈ Φ′_{α}, there exists x ∈ X such that ψ(x) = f′ and φ(x) = β(f′).

(c) ψφ^{−1}(t) ⊆ [ ˆ0, α(t)] for any t ∈ T, and α(f) ∈ ψφ^{−1}(f) for any f ∈ Φ_{α}.

(d) φψ^{−1}(t′) ⊆ [ ˆ0, β(t′)] for any t′ ∈ T′, and β(f′) ∈ φψ^{−1}(f′) for any f′ ∈ Φ′_{α}.

Proof : Clearly ψ ≤ α ∘ φ if and only if φ ≤ β ∘ ψ, by Condition 3.1. Assume that for any f ∈ Φ_{α}, there exists x ∈ X are such that φ(x) = f and ψ(x) = α(f). By Lemma 3.6, for any f′ ∈ Φ′_{α}, the element f = β(f′) belongs to Φ_{α}, and f′ = α(f). Hence there exists x ∈ X such that φ(x) = f = β(f′), and ψ(x) = α(f) = f′. So (a) implies (b). Switching T, T′ and α, β, we get that (b) implies (a).

Now if (a) holds, then for t ∈ T and x ∈ φ^{−1}(t), we have ψ(x) ≤ α(t). Hence ψφ^{−1}(t) ⊆ [ ˆ0, α(t)]. Moreover, if f ∈ Φ_{α}, there exists x ∈ φ^{−1}(f) such that ψ(x) = α(f), hence α(f) ∈ ψφ^{−1}(f). So (a) implies (c).

Conversely, if (c) holds, then for any x ∈ X, setting t = φ(x), we have x ∈ φ^{−1}(t), hence ψ(x) ∈ [ ˆ0, α(t)]. Thus ψ(x) ≤ αφ(x) and so ψ ≤ α ∘ φ. Moreover, for any f ∈ Φ_{α}, we have α(f) ∈ ψφ^{−1}(f), so there exists x ∈ φ^{−1}(f) such that α(f) = ψ(x). Thus φ(x) = f and ψ(x) = α(f). Hence (c) implies (a).

Switching T, T′ and α, β, we see that (b) is equivalent to (d) and this completes the proof.

3.8. Notation. Let φ ∈ T^{X} and ψ ∈ (T′)^{X}. If the equivalent conditions of Lemma 3.7 hold, we will write φ ⊢_{α} ψ, or simply φ ⊢ ψ when there is no possible confusion.

For each finite set X, we define a k-bilinear form

⟨−, −⟩_{α,X} : F_{T} (X) × F_{T′}(X) ⟶ k

by setting, for all maps φ ∈ T^{X} and ψ ∈ (T′)^{X},

⟨φ, ψ⟩_{α,X} = \{ \begin{matrix}1 & if φ ⊢_{α} ψ , \\ 0 & otherwise. \end{matrix}

We also write ⟨−, −⟩_{X} = ⟨−, −⟩_{α,X} when there is no possible confusion. We observe that φ ⊢_{α} ψ if and only if ψ ⊢_{β} φ, by Lemma 3.7. Therefore ⟨φ, ψ⟩_{α,X} = ⟨ψ, φ⟩_{β,X}.

3.9. Proposition. Let α : T → T′^{op} be a join-morphism. The family of bilinear forms ⟨−, −⟩_{α,X} defines a functorial pairing

⟨−, −⟩_{α} : F_{T} × F_{T′} ⟶ k .

Proof : We have to prove that ⟨Sφ, ψ⟩_{α,Y} = ⟨φ, S^{op}ψ⟩_{α,X}, where X and Y are finite sets, φ ∈ T^{X}, ψ ∈ (T′)^{Y}, and S ⊆ Y × X is a correspondence. First we claim that

ψ ≤ α ∘ (Sφ) ⟺ S^{op}ψ ≤ α ∘ φ .

Recall that (Sφ)(y) = ⋁_{(y,x)∈S} φ(x) for any y ∈ Y, by the definition of Sφ. Therefore,

the condition ψ ≤ α ∘ (Sφ) is equivalent to

∀y ∈ Y, ψ(y) ≤ α( ⋁_{(y,x)∈S} φ(x)) = ⋀_{(y,x)∈S} αφ(x) ,

that is,

∀(y, x) ∈ S, ψ(y) ≤ αφ(x) .

This in turn is equivalent to the condition

⋁_{(x,y)∈S^{op}} ψ(y) ≤ αφ(x) ,

that is,

∀x ∈ X, (S^{op}ψ)(x) ≤ αφ(x) .

Thus we have obtained S^{op}ψ ≤ α ∘ φ, proving the claim.

Assume now that ⟨Sφ, ψ⟩_{α,Y} = 1, that is, Sφ ⊢_{α} ψ. In particular ψ ≤ α ∘ (Sφ), which is equivalent to S^{op}ψ ≤ α∘φ, by the claim above. Moreover, for any f ∈ Φ_{α}, there exists an element y ∈ Y such that (Sφ)(y) = f and ψ(y) = α(f). Then

f = (Sφ)(y) = ⋁_{(y,x)∈S} φ(x)

and since f is irreducible, there exists x ∈ X with (y, x) ∈ S such that f = φ(x). Therefore

α(f) = ψ(y) ≤ ⋁_{(y′,x)∈S} ψ(y′) = ⋁_{(x,y′)∈S^{op}} ψ(y′) = (S^{op}ψ)(x) ≤ (α ∘ φ)(x) = α(f) ,

and so we get an equality (S^{op}ψ)(x) = α(f). Thus for any f ∈ Φ_{α}, there exists an element x ∈ X such that φ(x) = f and (S^{op}ψ)(x) = α(f). Hence φ ⊢_{α} S^{op}ψ and ⟨φ, S^{op}ψ⟩_{α,X} = 1.

Conversely, assume that ⟨φ, S^{op}ψ⟩_{α,X} = 1, that is, φ ⊢_{α} S^{op}ψ. Then in particular S^{op}ψ ≤ α ∘ φ, which is equivalent to ψ ≤ α ∘ (Sφ) by the claim above, hence also to Sφ ≤ β ∘ ψ by Condition 3.1. Moreover, for any f ∈ Φ_{α}, there exists x ∈ X such that φ(x) = f and (S^{op}ψ)(x) = α(f). Then

α(f) = (S^{op}ψ)(x) = ⋁_{(x,y)∈S^{op}} ψ(y) = ⋁_{(y,x)∈S} ψ(y) ,

and moreover α(f) ∈ Irr(T′) by the definition of Φ_{α}. So there exists y ∈ Y such that (y, x) ∈ S and ψ(y) = α(f). Therefore

f = φ(x) ≤ ⋁_{(y,x′)∈S} φ(x′) = (Sφ)(y) ≤ (β ∘ ψ)(y) = βα(f) = f ,

where the latter equality comes from the definition of Φ_{α}. Thus we obtain an equality (Sφ)(y) = f. So for any f ∈ Φ_{α}, there exists y ∈ Y such that (Sφ)(y) = f and ψ(y) = α(f). This shows that Sφ ⊢_{α} ψ, hence ⟨Sφ, ψ⟩_{α,Y} = 1.

We have now shown that ⟨Sφ, ψ⟩_{α,Y} = ⟨φ, S^{op}ψ⟩_{α,X}, completing the proof.

3.10. Corollary. Let K_{α} the left kernel of the pairing ⟨−, −⟩_{α} : F_{T} × F_{T′} → k of Proposition 3.9, and let K′_{α} be its right kernel. In other words, for any finite set X,

K_{α}(X) = {u ∈ F_{T} (X) | ∀ψ ∈ (T′)^{X}, ⟨u, ψ⟩_{α,X} = 0} ,
K′_{α}(X) = {u′ ∈ F_{T′}(X) | ∀φ ∈ T^{X}, ⟨φ, u′⟩_{α,X} = 0} .

Then K_{α} is a subfunctor of F_{T}, and K′_{α} is a subfunctor of F_{T′}.

Proof : Let u ∈ K_{α}(X) and consider a correspondence S ⊆ Y × X. Then, for all ψ ∈ (T′)^{X}, we have

⟨Su, ψ⟩_{α,Y} = ⟨u, S^{op}ψ⟩_{α,X} = 0

and this shows that Su ∈ K_{α}(Y), as required. The proof for K′_{α} is similar.

In view of Corollary 3.10, we can now introduce the correspondence functors which are our main object of study.

3.11. Definition. For any given join-morphism α : T → T′^{op}, we define

𝕊_{α} = F_{T} /K_{α}  and  𝕊′_{α} = F_{T′}/K′_{α} .

For completeness, observe that K_{β} = K′_{α} and hence 𝕊_{β} = 𝕊′_{α}, where β = α^{op} as usual.

3.12. Remark. The pairing ⟨−, −⟩_{α} : F_{T} × F_{T′} → k induces a pairing

𝕊_{α} × 𝕊′_{α} ⟶ k

which is nondegenerate in the weak sense, that is, it induces an injective morphism of functors

i : 𝕊_{α} ⟶ (𝕊′_{α})^{♮} ,

where (𝕊′_{α})^{♮} denotes the k-dual of 𝕊′_{α}. We will prove later in Proposition 6.9 that the pairing is actually nondegenerate in the strong sense, that is, the morphism i is an isomorphism. When k is a field, an argument about dimensions shows that there is no distinction to be made about nondegeneracy, so i is obviously an isomorphism in that case.

There is another way of obtaining the correspondence functor 𝕊_{α}, by dealing in a different way with the pairing ⟨−, −⟩_{α} : F_{T} × F_{T′} → k. We know that it induces a morphism

j_{α} : F_{T} ⟶ F_{T′}^{♮} ≅ F_{T′^{op}} ,

where the latter isomorphism comes from Proposition 2.2. Clearly K_{α} is the kernel of j_{α} and so 𝕊_{α} is isomorphic to the image of the morphism j_{α}. Since the functor

F_{?} : kL ⟶ F_{k}

is fully faithful by Theorem 2.1, j_{α} must be the image of a morphism

α̂ ∈ Hom_{kL}(T, T′^{op})

in the category kL, that is, j_{α} = Fα̂ : F_{T} ⟶ F_{T′^{op}}. We are going to show that the morphism α̂ can be described explicitly.

3.13. Definition. If T is a finite lattice, we let r : T → T be the map defined by

r(t) = ⋁_{\begin{matrix}s∈T \\ s<t \end{matrix}} s .

If t ∉ Irr(T), then clearly r(t) = t, while if t ∈ Irr(T), then r(t) is the unique maximal element strictly smaller than t.

3.14. Proposition. Let α : T → T′^{op} be a join-morphism. For any subset A of Φ_{α}, define α_{A} : T → T′ by

α_{A}(t) = \{ \begin{matrix}α(t) & if t ∈ T − A \\ rα(t) & if t ∈ A , \end{matrix}

and define α_{A}^{o} to be the map α_{A}, viewed as a map from T to T′^{op}.

(a) For any subset A of Φ_{α}, the map α_{A}^{o} is a join-morphism T → T′^{op} (hence α_{A}^{o} belongs to L).

(b) The morphism α̂ ∈ Hom_{kL}(T, T′^{op}) defined above is equal to

α̂ = ∑_{A⊆Φ_{α}}(−1)^{|A|}α_{A}^{o} .

Proof : (a) follows from (b), because the expression for α̂ obtained in (b) forces the terms to be join-morphisms. Alternatively, this can also be proved directly from the definition of α_{A}^{o}.

(b) By Proposition 2.2, the basis (T′)^{X} has a dual basis {ψ^{∗} | ψ ∈ (T′)^{X}} of F_{T′^{op}} given by

ψ^{∗} = ∑_{\begin{matrix}ρ∈(T′)^{X} \\ ρ≤ψ \end{matrix}} μ(ρ, ψ)ρ^{o} ,

where ρ^{o} is the map ρ, viewed as a map from X to T′^{op}. By the definition of the morphism j_{α,X} : F_{T} (X) → F_{T′^{op}}(X), it maps φ ∈ T^{X} to the linear combination

j_{α,X}(φ) = ∑_{ψ∈(T′)^{X}}⟨φ, ψ⟩_{X} · ψ^{∗} = ∑_{\begin{matrix}ψ∈(T′)^{X} \\ φ ⊢_{α} ψ \end{matrix}} ψ^{∗} .

The way to recover the morphism α̂ ∈ Hom_{kL}(T, T′^{op}) from its fully faithful image j_{α} is provided by the proof of part (c) of Theorem 4.8 in [BT3]. It consists of choosing X = T and φ = id_{T}, and define α̂ to be the image of id_{T} under j_{α,T}. We obtain

α̂ = ∑_{\begin{matrix}ψ∈(T′)^{T} \\ id_{T} ⊢_{α} ψ \end{matrix}} ψ^{∗} = ∑_{\begin{matrix}ψ∈(T′)^{T} \\ id_{T} ⊢_{α} ψ \end{matrix}} ∑_{\begin{matrix}ρ∈(T′)^{X} \\ ρ≤ψ \end{matrix}} μ(ρ, ψ)ρ^{o} .

Now the condition id_{T} ⊢_{α} ψ tells us that ψ ≤ α ∘ id_{T}, i.e. ψ ≤ α, and moreover

(C_{ψ}) : ψ(f) = α(f), ∀f ∈ Φ_{α} .

Therefore we get

α̂ = ∑_{\begin{matrix}ψ∈(T′)^{T} \\ ψ≤α \\ (C_{ψ}) \end{matrix}} ∑_{\begin{matrix}ρ∈(T′)^{X} \\ ρ≤ψ \end{matrix}} μ(ρ, ψ)ρ^{o} = ∑_{\begin{matrix}ρ∈(T′)^{X} \\ ρ≤α \end{matrix}} ( ∑_{\begin{matrix}ψ∈(T′)^{T} \\ ρ≤ψ≤α \\ (C_{ψ}) \end{matrix}} μ(ρ, ψ))ρ^{o}

We now fix ρ and consider the coefficient of ρ^{o}. For every ψ ∈ (T′)^{T}, we define

A_{ψ} = {f ∈ Φ_{α} | ψ(f) < α(f)} = {f ∈ Φ_{α} | ψ(f) ≤ rα(f)} ,

the second equality coming from the fact that α(f) is irreducible. Note that, for any given ψ ≤ α, the requirement that A_{ψ} = ∅ corresponds exactly to the condition (C_{ψ}). Now for any subset A ⊆ Φ_{α}, we have

A ⊆ A_{ψ} ⟺ ψ ≤ α_{A} ,

where α_{A} is defined in the statement. Using the fact that ∑_{∅⊆A⊆A_{ψ}}(−1)^{|A|} = 0 except if A_{ψ} = ∅, we see that the coefficient of ρ^{o} is equal to

∑_{\begin{matrix}ψ∈(T′)^{T} \\ ρ≤ψ≤α \\ (C_{ψ}) \end{matrix}} μ(ρ, ψ) = ∑_{\begin{matrix}ψ∈(T′)^{T} \\ ρ≤ψ≤α \\ A_{ψ}=∅ \end{matrix}} μ(ρ, ψ)

= ∑_{\begin{matrix}ψ∈(T′)^{T} \\ ρ≤ψ≤α \end{matrix}} μ(ρ, ψ) ∑_{∅⊆A⊆A_{ψ}}(−1)^{|A|}

= ∑_{∅⊆A⊆A_{ψ}}(−1)^{|A|} ∑_{\begin{matrix}ψ∈(T′)^{T} \\ ρ≤ψ≤α_{A} \end{matrix}} μ(ρ, ψ)

= ∑_{∅⊆A⊆A_{ψ}}(−1)^{|A|} δ_{ρ,α_{A}}

and this gives (−1)^{|A|} if ρ = α_{A} for some A and zero if ρ ≠ α_{A} for all A. Thus the only functions ρ ≤ α which remain are the functions ρ = α_{A} for A ⊆ Φ_{α} and we obtain

α̂ = ∑_{∅⊆A⊆Φ_{α}}(−1)^{|A|} α_{A}^{o} ,

as required.

3.15. Corollary. The correspondence functor 𝕊_{α} is isomorphic to the image of the morphism

j_{α} = Fα̂ : F_{T} ⟶ F_{T′^{op}} ,

where α̂ = ∑_{∅⊆A⊆Φ_{α}}(−1)^{|A|} α_{A}^{o}.

Proof : We have already noticed that 𝕊_{α} is isomorphic to the image of the morphism j_{α} and that j_{α} = Fα̂.

3.16. Remark. For any given join-morphism α : T → T′^{op}, there is a more elementary way of defining bilinear forms without using Φ_{α} and Φ′_{α}, but it turns out that it does not yield any new result. More precisely, if the definition of φ ⊢_{α} ψ given by Lemma 3.7 is modified by requiring the single condition ψ ≤ α ∘ φ (or equivalently φ ≤ β ∘ ψ where β = α^{op}), then the associated bilinear forms ⟨−, −⟩_{X} induce again a functorial pairing

⟨−, −⟩ : F_{T} × F_{T′} ⟶ k

and one can define 𝕊̃_{α} = F_{T} /K̃_{α} and 𝕊̃′_{α} = F_{T′}/K̃′_{α}, where K̃_{α} and K̃′_{α} are the left and right kernels of the pairing. Now recall from Section 2 that there is another pairing

(− | −)_{X} : F_{T} (X) × F_{T^{op}}(X) ⟶ k

which is nondegenerate (in the strong sense, see Proposition 2.2). It follows from the definitions that the bilinear form above can be expressed in terms of the nondegenerate pairing via ⟨φ, ψ⟩_{X} = (φ | β ∘ ψ)_{X}. Therefore, for any given v ∈ F_{T′}(X), we obtain equivalences

v ∈ K̃′_{α}(X) ⟺ ⟨φ, v⟩_{X} = 0, ∀φ ∈ T^{X} ⟺ (φ | β ∘ v)_{X} = 0, ∀φ ∈ T^{X}

and this is equivalent to β ∘ v = 0 by nondegeneracy. In other words,

v ∈ Ker (F_{β,X} : F_{T′}(X) → F_{T^{op}}(X))

and this shows that K̃′_{α} = Ker(F_{β}). It follows that

𝕊̃′_{α} = F_{T′}/K̃′_{α} = F_{T′}/ Ker(F_{β}) ≅ F_{Im(β)} .

Similarly, 𝕊̃_{α} ≅ F_{Im(α)}. Therefore 𝕊̃_{α}, respectively 𝕊̃′_{α}, is simply (up to isomorphism) the correspondence functor associated with the lattice Im(α), respectively Im(β). This shows why the more elementary way of defining a bilinear form does not yield any new correspondence functor. It does not yield any new pairing either, because α and β actually induce isomorphisms between Im(β) and Im(α)^{op} and the nondegenerate pairing

F_{Im(α)}(X) × F_{Im(α)^{op}}(X) ⟶ k

induced by the given pairing ⟨−, −⟩ actually coincides with the general pairing of Proposition 2.2.

4. Lattice-theoretic constructions

For any given join-morphism α : T → T′^{op}, we introduce several lattice-theoretic constructions which will play an essential role. Using the map r : T → T defined in (3.13), we define inductively 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).

4.1. Lemma. Let T be a finite lattice, let t ∈ T, and let n ≥ 0 be the smallest integer such that r^{n}(t) = r^{∞}(t).

(a) n ≥ 0 is the smallest integer such that r^{n}(t) ∉ Irr(T).

(b) r^{∞}(t) is the unique greatest element of T −Irr(T) smaller than or equal to t.

(c) If v ∈ T is such that v ≤ t, then either v = r^{i}(t) for some 0 ≤ i ≤ n − 1 or v ≤ r^{∞}(t).

(d) [r^{∞}(t), t] is totally ordered and consists of the elements r^{i}(t), for 0 ≤ i ≤ n.

(e) All the elements of ]r^{∞}(t), t] belong to Irr(T).

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

Proof : The proof is an easy consequence of the definitions. The result is completely trivial if t ∉ Irr(T), while if t is irreducible, then r(t) is the unique maximal element of [ ˆ0, t[ and r^{i+1}(t) is the unique maximal element of [ ˆ0, r^{i}(t)[ whenever 0 ≤ i ≤ n − 1. Details can be found in Lemma 2.5 of [BT4].

Instead of Irr(T), we need to work with the subset Φ_{α} of Irr(T) defined in Notation 3.5. For simplicity, we write Φ = Φ_{α} and Φ′ = Φ′_{α} throughout this section.

4.2. Lemma. Let T be a finite lattice, let t ∈ T, let m ≥ 0 be the smallest integer such that r^{m}(t) ∉ Φ, and set ρ(t) = r^{m}(t).

(a) ρ(t) is the unique greatest element of T − Φ smaller than or equal to t. In other words, ρ(t) = ⋁_{\begin{matrix}u∈T −Φ \\ u≤t \end{matrix}} u.

(b) If v ∈ T is such that v ≤ t, then either v = r^{i}(t) for some 0 ≤ i ≤ m − 1 or v ≤ ρ(t).

(c) [ρ(t), t)] is totally ordered and consists of the elements r^{i}(t), for 0 ≤ i ≤ m.

(d) All the elements of ]ρ(t), t] belong to Φ.

(e) The map ρ : T → T is order-preserving.

Proof : We apply Lemma 4.1. Since r^{n}(t) ∉ Irr(T), we have r^{n}(t) ∉ Φ. Thus m ≤ n and r^{∞}(t) ≤ r^{m}(t) ≤ t.

Let v ∈ T − Φ with v ≤ t. Then v cannot be equal to r^{i}(t) for 0 ≤ i ≤ m − 1 by the definition of m, so v ≤ r^{m}(t) = ρ(t), by part (c) of Lemma 4.1. The results follow easily.

4.3. Notation. We define

β^{♯} = ρβ and α^{♯} = ρ′α ,

where ρ(t) = ⋁_{\begin{matrix}u∈T −Φ \\ u≤t \end{matrix}} u and ρ′(t′) = ⋁_{\begin{matrix}u′∈T′−Φ′ \\ u′≤t′ \end{matrix}} u′.

4.4. Corollary.

(a) α^{♯}(t) = r^{l}α(t), where l is the smallest non-negative integer such that r^{l}α(t) ∉ Φ′.

(b) α^{♯}(t) is the greatest element of T′ − Φ′ smaller than or equal to α(t).

(c) If t′ ∈ T′ is such that t′ ≤ α(t), then either t′ = r^{i}α(t) for some 0 ≤ i ≤ l−1 or t′ ≤ α^{♯}(t).

(d) The interval [α^{♯}(t), α(t)] is totally ordered and consists of the elements r^{i}α(t), for 0 ≤ i ≤ l.

(e) All the elements of ]α^{♯}(t), α(t)] belong to Φ′.

(f) The map α^{♯} : T → T′ is order-reversing.

Proof : Everything follows from Lemma 4.2.

4.5. Remark. We can view the situation slightly differently. Since Φ ⊆ Irr(T), the subset T − Φ is closed under join and contains ˆ0. In other words T − Φ is a lattice (its join being the join of T, but its meet being in general different from the meet of T). The inclusion i : T − Φ ↪ T is a join-morphism and its opposite i^{op} : T^{op} → (T − Φ)^{op} is defined by

i^{op}(t) = ⋁_{\begin{matrix}u∈T −Φ \\ u≤t \end{matrix}} u .

It follows that ρ is equal to i^{op} (provided we view i^{op} as a map from T to T − Φ). Consequently, β^{♯} = ρβ = i^{op}α^{op} = (αi)^{op} and similarly α^{♯} = (βi′)^{op} using the inclusion i′ : T′ − Φ′ ↪ T′. In particular, by Lemma 3.4, β^{♯}αβ^{♯} = β^{♯}(αi)β^{♯} = β^{♯} and similarly α^{♯}βα^{♯} = α^{♯}.

Applying β and β^{♯} to the totally ordered interval [α^{♯}(t), α(t)] yields canonically defined elements of T associated to t and we want to investigate some structural information about these elements. To this end we introduce some notation.

4.6. Notation. We set

ω = βα^{♯} : T → T  and  ω′ = αβ^{♯} : T′ → T′ ,
θ = β^{♯}α^{♯} : T → T  and  θ′ = α^{♯}β^{♯} : T′ → T′ .

Let us first discuss a few properties of ω.

4.7. Lemma.

(a) The map ω : T → T is order-preserving and idempotent.

(b) Let t ∈ T and let l ≥ 0 be the smallest integer such that r^{l}α(t) ∉ Φ′, so that α^{♯}(t) = r^{l}α(t) and ω(t) = βr^{l}α(t). For 0 ≤ i ≤ l − 1, write v_{i} := βr^{i}α(t). Then

t ≤ v_{0} < v_{1} < … < v_{l−1} ≤ ω(t) ,

and v_{i} ∈ Φ, for 0 ≤ i ≤ l − 1. In particular, t ≤ ω(t).

(c) [t, ω(t)]∩Φ = {v_{0}, v_{1}, …, v_{l−1}}. In particular, ω(t) ∈ Φ if and only if l ≥ 1 and v_{l−1} = ω(t).

(d) [t, ω(t)] ∩ Im(β) = {v_{0}, v_{1}, …, v_{l−1}}.

Proof : (a) Since ω = βα^{♯} is the composition of two order-reversing maps, it is an order-preserving map. Moreover, by Remark 4.5, we get ω^{2} = βα^{♯}βα^{♯} = βα^{♯} = ω.

(b) If l = 0, then α(t) ∉ Φ′, hence α(t) = α^{♯}(t) and t ≤ βα(t) = βα^{♯}(t) = ω(t). If l > 0, Corollary 4.4 implies that there is a decreasing sequence

α(t) > rα(t) > … > r^{l−1}α(t) > r^{l}α(t) = α^{♯}(t) ,

and all the elements of this sequence, except α^{♯}(t), are in Φ′. It follows from Lemma 3.6 that the sequence

βα(t) < βrα(t) < … < βr^{l−1}α(t)

is strictly increasing and consists of elements of Φ. Moreover t ≤ βα(t) = v_{0} and v_{l−1} = βr^{l−1}α(t) ≤ βr^{l}α(t) = ω(t).

(c) Let f ∈ [t, ω(t)] ∩ Φ. Then α(t) ≥ α(f) ≥ αω(t) = αβα^{♯}(t) ≥ α^{♯}(t) and therefore, by Corollary 4.4,

α(f) ∈ [α^{♯}(t), α(t)] ∩ Φ′ = {α(t), rα(t), …, r^{l−1}α(t)} .

It follows that f = βα(f) ∈ {βα(t), βrα(t), …, βr^{l−1}α(t)}. The other inclusion and the additional statement follow from (b).

(d) Let t′ ∈ T′ such that t ≤ β(t′), so that t′ ≤ α(t) by (3.1). By Corollary 4.4, either t′ ≤ α^{♯}(t), and then β(t′) ≥ βα^{♯}(t) = ω(t), or there exists an integer j with 0 ≤ j < l such that t′ = r^{j}α(t). In that case β(t′) = βr^{j}α(t) = v_{j}, as required.

We consider next some basic properties of θ.

4.8. Lemma.

(a) The map θ : T → T is order-preserving and idempotent.

(b) If t ∈ T − Φ, then t ≤ θ(t) and α^{♯}β^{♯}α^{♯}(t) = α^{♯}(t).

(c) θ(t) is the greatest element of T − Φ smaller than or equal to ω(t).

(d) ]θ(t), ω(t)] is totally ordered and consists of elements of Φ.

Proof : Since θ = β^{♯}α^{♯} is the composition of two order-reversing maps, it is an order-preserving map. By Lemma 4.7, we have t ≤ ω(t) = βα^{♯}(t), for any t ∈ T. If t ∈ T − Φ, then t ≤ β^{♯}α^{♯}(t) ≤ βα^{♯}(t) by the definition of β^{♯}, hence t ≤ θ(t). Moreover,

α(t) ≥ αβ^{♯}α^{♯}(t) ≥ αβα^{♯}(t) ≥ α^{♯}(t) .

Since α^{♯}(t) is the greatest element of T′ − Φ′ smaller than or equal to α(t), it is also the greatest element of T′ − Φ′ smaller than or equal to αβ^{♯}α^{♯}(t). Hence α^{♯}β^{♯}α^{♯}(t) = α^{♯}(t).

Swapping the roles of T and T′, the same argument applies to any t′ ∈ T′ − Φ′ and therefore β^{♯}α^{♯}β^{♯}(t′) = β^{♯}(t′). Taking in particular t′ = α^{♯}(t) for any t ∈ T, we see that θ = β^{♯}α^{♯} is idempotent.

Finally, (c) is an immediate consequence of the definition of β^{♯}, while (d) follows from Corollary 4.4 (applied to β and β^{♯} instead of α and α^{♯}).

Some examples show that both conclusions in part (b) of Lemma 4.8 may fail if t ∈ Φ (see also Proposition 4.9).

We now examine in more detail the interval [t, ω(t)] and the position of θ(t). The elements θ(t) as well as the elements of Φ belonging to the interval [t, ω(t)] play a crucial role in the description of a k-basis of 𝕊_{α}(X), which is carried out in Sections 5 and 6.

As before, we let l ≥ 0 be minimal such that r^{l}α(t) ∉ Φ′, so that α^{♯}(t) = r^{l}α(t). If l ≥ 1, we let 0 ≤ h ≤ l be minimal such that θ(t) ≤ βr^{h}α(t). Such an h exists because θ(t) ≤ ω(t) = βr^{l}α(t).

4.9. Proposition. Let t ∈ T and let l and h be as above. For l ≥ 1 and 0 ≤ i ≤ l − 1, write v_{i} := βr^{i}α(t) and recall that v_{i} ∈ Φ (by Lemma 4.7).

(a) If l = 0, then t ∉ Φ, α(t) ∉ Φ′, θ(t) = ω(t) = βα(t) ∉ Φ, and [t, ω(t)] ∩ Φ is empty. Moreover, αθ(t) = α(t).

(b) If l ≥ 1 and 1 ≤ h ≤ l − 1, then v_{h−1} < θ(t) < v_{h}. Hence

t ≤ v_{0} < … < v_{h−1} < θ(t) < v_{h} < … < v_{l−1} = ω(t) .

Moreover, αθ(t) = r^{h}α(t).

(c) If l ≥ 1 and h = l, then θ(t) = ω(t). Hence

t ≤ v_{0} < … < v_{l−1} < θ(t) = ω(t) .

Moreover, αθ(t) = r^{l}α(t).

(d) If l ≥ 1 and h = 0 and if moreover t ∉ Φ, then t ≤ θ(t) < v_{0}. Hence

t ≤ θ(t) < v_{0} < … < v_{l−1} = ω(t) .

Moreover, αθ(t) = α(t).

(e) If l ≥ 1 and h = 0 and if moreover t ∈ Φ, then θ(t) < t. Hence

θ(t) < t = v_{0} < … < v_{l−1} = ω(t) .

Moreover, αθ(t) ≥ α(t).

(f) If either h ≥ 1 or t ∉ Φ, then αθ(t) = r^{h}α(t).

Proof : (a) If l = 0, then α(t) ∉ Φ′ by the definition of l. Then necessarily t ∉ Φ by Lemma 3.6. By the definition of ω, we have ω(t) = βα(t) and this cannot be in Φ, otherwise α(t) = αβα(t) would be in Φ′. Finally θ(t) = ω(t) because ω(t) ∉ Φ and αθ(t) = αβα(t) = α(t).

(b) By Lemma 4.7, the minimality of h implies that v_{h} is the least element of [θ(t), ω(t)] belonging to Φ. Moreover, since h ≤ l − 1, and since θ(t) ∉ Φ by the definition of θ, we must have θ(t) < v_{l−1} ≤ ω(t), forcing ω(t) ∈ Φ, hence v_{l−1} = ω(t) by Lemma 4.7(c). By Lemma 4.8, the interval [θ(t), ω(t)] is totally ordered and consists of the elements r^{i}ω(t) for i ≥ 0, so we must have θ(t) = r(v_{h}). Consequently, v_{h−1} ≤ θ(t) < v_{h}. The first inequality is strict because v_{h−1} ∈ Φ while θ(t) ∉ Φ.

Applying α to the inequality v_{h−1} = βr^{h−1}α(t) < θ(t) < v_{h} = βr^{h}α(t) and using the fact that v_{h}, v_{h−1} ∈ Φ, we obtain

r^{h−1}α(t) ≥ αθ(t) ≥ r^{h}α(t) .

If the first inequality was an equality, applying β would imply βr^{h−1}α(t) = βαθ(t), contrary to the relation v_{h−1} < θ(t) ≤ βαθ(t). Therefore r^{h−1}α(t) > αθ(t) and the definition of the operator r yields αθ(t) = r^{h}α(t).

(c) If h = l, then v_{l−1} = βr^{l−1}α(t) cannot be equal to ω(t) = βr^{l}α(t) by minimality of h, so that v_{l−1} < ω(t). By Lemma 4.7(c), it follows that ω(t) ∉ Φ and so θ(t) = ω(t).

Applying α to the inequality v_{l−1} = βr^{l−1}α(t) < ω(t) = βr^{l}α(t) and using the fact that r^{l−1}α(t) ∈ Φ, we obtain

r^{l−1}α(t) ≥ αω(t) = αβr^{l}α(t) ≥ r^{l}α(t) .

If the first inequality was an equality, applying β would imply

βr^{l−1}α(t) = βαβr^{l}α(t) = βr^{l}α(t) = ω(t) ,

contrary to the relation v_{l−1} < ω(t). Therefore r^{l−1}α(t) > αω(t) ≥ r^{l}α(t) and the definition of the operator r yields αω(t) = r^{l}α(t), that is, αθ(t) = r^{l}α(t).

(d) We have t ≤ θ(t) by Lemma 4.8(b) and the assumption t ∉ Φ. Moreover, θ(t) ≤ v_{0} = βα(t) because h = 0, and the inequality is strict because v_{0} ∈ Φ while θ(t) ∉ Φ.

Now since t ≤ θ(t) < v_{0} = βα(t), we have α(t) ≥ αθ(t) ≥ αβα(t) = α(t), hence αθ(t) = α(t).

(e) Since h = 0, we have θ(t) ≤ βα(t). But βα(t) = t because t ∈ Φ, hence θ(t) ≤ t. Moreover equality does not hold since θ(t) ∉ Φ. Since α is order-reversing, we also get αθ(t) ≥ α(t).

(f) If either h ≥ 1 or t ∉ Φ, then we are in one of the cases (a)-(d) and we have found that αθ(t) = r^{h}α(t).

4.10. Remark. The property in (f) does not extend to the case (e). More precisely, in case (e), we may have an inequality αθ(t) > α(t). This occurs precisely when there is an element f ∈ Φ such that θ(t) < f < t = v_{0}, for we then have αθ(t) ≥ α(f) > α(t) because f < t are both in Φ. In other words, since ]θ(t), ω(t)] is totally ordered and consists of elements of Φ by Lemma 4.8, we see that if u ∈ ]θ(t), ω(t)] is not the minimal element of ]θ(t), ω(t)], then θ(u) = θ(t) and αθ(u) = αθ(t) > α(u).

The property θ(u) < u only occurs in case (e) of Proposition 4.9 and this case is important in the sequel. It appears in particular when u ∈]t, ω(t)] for t ∈ Im(θ) and we now analyse this situation.

4.11. Lemma. Let α : T → T′^{op} be a join-morphism and let β = α^{op}.

(a) The restriction of α^{♯} is an anti-isomorphism of posets from Im(θ) to Im(θ′), with inverse anti-isomorphism β^{♯}.

(b) If t ∈ Im(θ) and t′ = α^{♯}(t), then α restricts to an order-reversing bijection from the totally ordered interval ]t, ω(t)] to the totally ordered interval ]t′, ω′(t′)]. The inverse bijection is induced by β.

(c) Let t ∈ Im(θ) and u ∈ [t, ω(t)]. Then ρ(u) = t, ω(u) = ω(t), and θ(u) = θ(t) = t.

Proof : (a) Let t ∈ Im(θ), i.e. t = θ(t) by Lemma 4.8. Setting t′ = α^{♯}(t), we get t = θ(t) = β^{♯}α^{♯}(t) = β^{♯}(t′). Moreover, θ′(t′) = α^{♯}β^{♯}(t′) = α^{♯}β^{♯}α^{♯}(t) = α^{♯}(t) = t′, the third equality coming from Lemma 4.8 and the fact that t ∉ Φ, because t = θ(t). Therefore t′ ∈ Im(θ′). Since α^{♯} and β^{♯} are order-reversing, the result follows.

(b) We set again t′ = α^{♯}(t) and we also have t = β^{♯}(t′) as above. Moreover,

(4.12)  ω(t) = βα^{♯}(t) = β(t′)  and  ω′(t′) = αβ^{♯}(t′) = α(t) .

If ]t, ω(t)] is empty, i.e. t = ω(t), then Proposition 4.9 shows that we must have l = 0, hence α^{♯}(t) = α(t). Therefore t′ = α(t) = ω′(t′) and the interval ]t′, ω′(t′)] is also empty. Similarly, if ]t′, ω′(t′)] is empty, then so is ]t, ω(t)]. Thus we can assume that both intervals are nonempty.

By Lemma 4.8, the interval [t, ω(t)] is totally ordered and ]t, ω(t)] ⊆ Φ. In particular, ω(t) ∈ Φ, hence β(t′) ∈ Φ by (4.12). Similarly ω′(t′) = α(t) ∈ Φ′. In particular, we have βα(t) ∈ Φ, hence t < v := βα(t) because t ∉ Φ. Note that α(t) = α(v) because αβα = α. If s ∈]t, ω(t)], then s ∈ Φ, hence

t < v = βα(t) ≤ βα(s) = s ≤ ω(t) .

Therefore v is the least element of ]t, ω(t)] and ]t, ω(t)] = [v, ω(t)] = [t, ω(t)] ∩ Φ. Similarly t′ < v′ := αβ(t′) ∈ Φ′, β(t′) = β(v′) and v′ is the least element of ]t′, ω′(t′)].

Since α(v) = α(t) = ω′(t′) and β(v′) = β(t′) = ω(t) by (4.12), and since α is order-reversing, we get

α([v, ω(t)]) = [αω(t), α(v)] = [αβ(t′), α(v)] = [v′, ω′(t′)] ,

that is, α(]t, ω(t)]) = ]t′, ω′(t′)]. Similarly β(]t′, ω′(t′)]) = ]t, ω(t)]. Therefore the maps α and β restrict to anti-isomorphisms of posets between ]t, ω(t)] and ]t′, ω′(t′)].

(c) If u ∈ [t, ω(t)], then t = ρ(t) ≤ ρ(u) ≤ ρω(t) = β^{♯}α^{♯}(t) = t, so ρ(u) = t. Similarly ω(t) ≤ ω(u) ≤ ω^{2}(t) = ω(t) by Lemma 4.7, so ω(u) = ω(t). Finally, θ(u) = ρω(u) = ρω(t) = θ(t) and θ(t) = t since t ∈ Im(θ).

To end this section we show that the image of β can be described in terms of ω and θ, and similarly for α.

4.13. Proposition. Let α : T → T′^{op} be a join-morphism and let β = α^{op}.

(a) β(T′) = Φ ⊔ {t ∈ T | t = ω(t) = θ(t)}.

(b) α(T) = Φ′ ⊔ {t′ ∈ T′ | t′ = ω′(t′) = θ′(t′)}.

Proof : Since (b) is the dual statement, it suffices to prove (a). The union is disjoint because θ(t) ∉ Φ, so t = θ(t) implies that t ∉ Φ. If t ∈ Φ, then t = βα(t) ∈ β(T′), while if t satisfies t = ω(t), then also t ∈ β(T′). So we are left with the proof of the inclusion β(T′) ⊆ Φ ⊔ {t ∈ T | t = ω(t) = θ(t)}.

Let t′ ∈ T′ and set t = β(t′). If t ∈ Φ, we are done, so we assume that t ∉ Φ. Recall that t = β(t′) = βαβ(t′) = βα(t), by Lemma 3.4. Thus α(t) ∉ Φ′, otherwise t = βα(t) would be in Φ. Therefore α^{♯}(t) = α(t), hence ω(t) = βα^{♯}(t) = βα(t) = t. Now t ∉ Φ and the property t = ω(t) ∉ Φ implies that θ(t) = ρω(t) = ω(t), by the definition of θ. This shows that t = ω(t) = θ(t), as required.

5. Generating set for the evaluation

Our main goal in this section is to describe a set of generators of the evaluation 𝕊_{α}(X) at a finite set X. To this end, we need the lattice-theoretic constructions of Section 4 and in particular the following notation :

5.1. Notation. Let α : T → T′^{op} be a join-morphism of finite lattices. Using our previous Notation 3.5 and 4.6, we set

G_{α} = Φ_{α} ⊔ Im(θ)  and  G′_{α} = Φ′_{α} ⊔ Im(θ′) .

We also write G = G_{α} and G′ = G′_{α} whenever there is no possible confusion. Note that Im(θ) can also be described as the set of fixed points of θ because θ is idempotent. The union is disjoint because θ(t) ∉ Φ_{α} by definition.

5.2. Lemma. β(T′) ⊆ G_{α} and α(T) ⊆ G′_{α}.

Proof : We have β(T′) = Φ_{α} ⊔{t ∈ T | t = ω(t) = θ(t)} by Proposition 4.13, while G_{α} = Φ_{α} ⊔ {t ∈ T | t = θ(t)} by Notation 5.1. Thus the inclusion is clear.

The key for our main result is to describe sufficiently many elements of the kernel K_{α}(X) of the surjection F_{T} (X) → 𝕊_{α}(X). They will later be used to modify arbitrary chosen elements of the basis T^{X} via consecutive reductions. This motivates the following terminology :

5.3. Definition. Let α : T → T′^{op} be a join-morphism. Let a ∈ T − G_{α} and b = θ(a). Using the notation of Proposition 4.9, we let l ≥ 0 be minimal such that r^{l}α(a) ∉ Φ′_{α}, so that α^{♯}(a) = r^{l}α(a), and if l ≥ 1 we let 0 ≤ h ≤ l be minimal such that b ≤ βr^{h}α(a). By Proposition 4.9, the elements of Φ_{α} lying in the interval [a, b] form a totally ordered set

v_{0} < … < v_{h−1} ,

where v_{i} = βr^{i}α(a) for 0 ≤ i ≤ h − 1. If h = 0, then this set is empty. The totally ordered set

{a, b} ⊔ ([a, b] ∩ Φ_{α}) = {a < v_{0} < … < v_{h−1} < b}

will be called the reduction sequence associated to a.

In this sequence, it will be convenient to set also v_{−1} = a, and v_{h} = b (but note that a, b ∉ Φ_{α}). If h = 0, the reduction sequence only consists of a < b.

Now we come to our main technical lemma.

5.4. Lemma. Let a ∈ T − G_{α} and b = θ(a). Let a < v_{0} < … < v_{h−1} < b be the associated reduction sequence (with h fixed as in Definition 5.3) and set also v_{h} = b. For any 0 ≤ k ≤ h, let [a, v_{0}, …, v_{k}] : T → T be the map defined by

∀t ∈ T, [a, v_{0}, …, v_{k}](t) = \{ \begin{matrix}v_{0} & if t = a, \\ v_{i+1} & if t = v_{i} with 0 ≤ i ≤ k − 1, \\ t & otherwise. \end{matrix}

For any function φ ∈ T^{X} (where X is a finite set), we set

φ_{k} = [a, v_{0}, …, v_{k}] ∘ φ .

Then the linear combination

w = φ + ∑_{k=0}^{h}(−1)^{k+1}φ_{k}

belongs to K_{α}(X).

Proof : We have to show that ⟨w, ψ⟩_{X} = 0 for any ψ : X → T′. To see this, we must know when φ ⊢_{α} ψ and when φ_{k} ⊢_{α} ψ, for 0 ≤ k ≤ h. For simplicity, we write φ ⊢ ψ instead of φ ⊢_{α} ψ and Φ = Φ_{α}. Recall from Lemma 3.7 that

φ ⊢ ψ ⟺ ψφ^{−1}(t) ⊆ [ ˆ0, α(t)] , ∀t ∈ T , and α(f) ∈ ψφ^{−1}(f) , ∀f ∈ Φ .

We first observe the following, for any 0 ≤ k ≤ h (including k = h in which case v_{h} = b) :

φ_{k}^{−1}(t) = φ^{−1}(t) , ∀ t ≠ a, v_{0}, …, v_{h−1}
φ_{k}^{−1}(a) = ∅
φ_{k}^{−1}(v_{i}) = φ^{−1}(v_{i−1}) , ∀i with 0 ≤ i ≤ k − 1
φ_{k}^{−1}(v_{k}) = φ^{−1}(v_{k−1}) ⊔ φ^{−1}(v_{k})
φ_{k}^{−1}(v_{i}) = φ^{−1}(v_{i}) , ∀i with k + 1 ≤ i ≤ h − 1

The proof is straightforward. For the 4th equality, note that φ_{k}(x) = v_{k} if and only if φ(x) = v_{k−1} or φ(x) = v_{k}, because v_{k−1} and v_{k} are the only elements mapped to v_{k} by the map [a, v_{0}, …, v_{k}].

Now we introduce a list of conditions which we need for the description of the property φ_{k} ⊢ ψ. The first conditions treat the case k = −1, where for convenience we set φ_{−1} = φ :

(A) : \{ \begin{matrix}ψφ^{−1}(t) ⊆ [ ˆ0, α(t)] , & ∀ t ∈ T − \{v_{0}, …, v_{h−1}\} and \\ α(f) ∈ ψφ^{−1}(f) , & ∀ f ∈ Φ − \{v_{0}, …, v_{h−1}\} \end{matrix}
(D_{−1}) : α(v_{i}) ∈ ψφ^{−1}(v_{i}) ⊆ [ ˆ0, α(v_{i})] , ∀i with 0 ≤ i ≤ h − 1

Since φ_{−1} = φ, it is obvious that

φ_{−1} ⊢ ψ ⟺ (A) and (D_{−1}) hold.

Next we consider conditions for 0 ≤ k ≤ h − 1 :

(B_{k}) : α(v_{i}) ∈ ψφ^{−1}(v_{i−1}) ⊆ [ ˆ0, α(v_{i})] , ∀i with 0 ≤ i ≤ k − 1
(C_{k}) : α(v_{k}) ∈ ψ(φ^{−1}(v_{k−1}) ⊔ φ^{−1}(v_{k})) ⊆ [ ˆ0, α(v_{k})]
(D_{k}) : α(v_{i}) ∈ ψφ^{−1}(v_{i}) ⊆ [ ˆ0, α(v_{i})] , ∀i with k + 1 ≤ i ≤ h − 1

Here (B_{0}) is empty because the condition 0 ≤ i ≤ k − 1 is empty if k = 0. Similarly (D_{h−1}) is empty because the condition k + 1 ≤ i ≤ h − 1 is empty if k = h − 1. In view of the previous observations about φ_{k}^{−1}, it is clear that, for 0 ≤ k ≤ h − 1,

φ_{k} ⊢ ψ ⟺ (A), (B_{k}), (C_{k}), and (D_{k}) hold.

Finally we consider conditions in the case k = h :

(B_{h}) : α(v_{i}) ∈ ψφ^{−1}(v_{i−1}) ⊆ [ ˆ0, α(v_{i})] , ∀i with 0 ≤ i ≤ h − 1
(C_{h}^{∗}) : ψφ^{−1}(v_{h−1}) ⊆ [ ˆ0, α(b)]

The notation (C_{h}^{∗}) suggests that the condition is not exactly a special case of (C_{k}) : the requirement ψφ^{−1}(v_{h}) ⊆ [ ˆ0, α(v_{h})] is not included in (C_{h}^{∗}) because v_{h} = b and this requirement is contained in (A). Note that (D_{h}) does not appear because it would be empty. Again it is clear that

φ_{h} ⊢ ψ ⟺ (A), (B_{h}), (C_{h}^{∗}) hold.

5.5. Claim. Let −1 ≤ k, k′ ≤ h. If both φ_{k} ⊢ ψ and φ_{k′} ⊢ ψ hold, then |k′ −k| ≤ 1.

First let −1 ≤ k < k′ ≤ h such that k′ − k ≥ 3 and suppose that both φ_{k} ⊢ ψ and φ_{k′} ⊢ ψ hold. Since φ_{k} ⊢ ψ implies (D_{k}), we obtain in particular, for i = k + 1,

α(v_{k+1}) ∈ ψφ^{−1}(v_{k+1}) .

Now φ_{k′} ⊢ ψ implies (B_{k′}) and in particular, for i = k + 2 ≤ k′ − 1, we get

ψφ^{−1}(v_{k+1}) ⊆ [ ˆ0, α(v_{k+2})] .

It follows that α(v_{k+1}) ∈ [ ˆ0, α(v_{k+2})], that is, α(v_{k+1}) ≤ α(v_{k+2}). But α(v_{k+2}) < α(v_{k+1}) because v_{k+2} > v_{k+1} both belong to Φ, so their images under α remain distinct, by Lemma 3.6. This contradiction shows that φ_{k} ⊢ ψ is incompatible with φ_{k′} ⊢ ψ when k′ − k ≥ 3.

A similar argument holds if k′ − k = 2. Again φ_{k} ⊢ ψ implies that

α(v_{k+1}) ∈ ψφ^{−1}(v_{k+1}) .

Now φ_{k′} ⊢ ψ implies (C_{k′}) if k′ ≤ h − 1, respectively (C_{h}^{∗}) if k′ = h. In either case, for i = k′ − 1 = k + 1, we get in particular

ψφ^{−1}(v_{k+1}) ⊆ [ ˆ0, α(v_{k+2})] .

Therefore α(v_{k+1}) ≤ α(v_{k+2}), but again this contradicts the fact that α(v_{k+2}) < α(v_{k+1}), which follows from v_{k+2} > v_{k+1}. A special argument is needed here if k + 2 = h, because v_{h} = b is not in Φ. We have v_{h} > v_{h−1}, hence α(v_{h}) ≤ α(v_{h−1}) and we must show that the equality α(v_{h}) = α(v_{h−1}) cannot hold. If it did hold, then we would obtain

βα(v_{h}) ≥ v_{h} > v_{h−1} = βα(v_{h−1}) = βα(v_{h}) ,

but this is impossible. Thus we also have α(v_{k+2}) < α(v_{k+1}) if k′ = k + 2 = h. We have seen that this yields a contradiction, so φ_{k} ⊢ ψ is incompatible with φ_{k′} ⊢ ψ when k′ = k + 2. Putting together the cases k′ − k ≥ 3 and k′ − k = 2, we see φ_{k} ⊢ ψ is incompatible with φ_{k′} ⊢ ψ whenever |k′ −k| ≥ 2. This completes the proof of Claim 5.5.

5.6. Claim. Let 0 ≤ k ≤ h.

(a) Suppose 0 ≤ k ≤ h − 1. If both φ_{k} ⊢ ψ and α(v_{k}) ∈ ψφ^{−1}(v_{k}) hold, then φ_{k−1} ⊢ ψ holds.

(b) Suppose k = h. If φ_{h} ⊢ ψ holds, then φ_{h−1} ⊢ ψ holds.

In order to show that φ_{k−1} ⊢ ψ holds, we need to prove (B_{k−1}), (C_{k−1}) and (D_{k−1}). This is clear for (B_{k−1}) because (B_{k}) implies (B_{k−1}) (with (B_{−1}) empty if k = 0).

(a) Suppose first that 1 ≤ k ≤ h − 1. Since (B_{k}) for i = k − 1 implies that α(v_{k−1}) ∈ ψφ^{−1}(v_{k−2}) ⊆ [ ˆ0, α(v_{k−1})], while (C_{k}) implies that ψφ^{−1}(v_{k−1}) ⊆ [ ˆ0, α(v_{k})] ⊆ [ ˆ0, α(v_{k−1})], we obtain (C_{k−1}). Now (D_{k}) is the part of (D_{k−1}) corresponding to i ≥ k + 1 and moreover (C_{k}) implies that ψφ^{−1}(v_{k}) ⊆ [ ˆ0, α(v_{k})] while the extra condition α(v_{k}) ∈ ψφ^{−1}(v_{k}) holds by assumption, so we obtain (D_{k−1}) for i = k as well.

If k = 0, then (B_{−1}) and (C_{−1}) are empty and the argument that (D_{−1}) holds is obtained in the same way as above.

(b) Assume now that k = h. Since (B_{h}) implies (B_{h−1}) and since (D_{h−1}) is empty, we are left with the proof of (C_{h−1}). Condition (B_{h}) for i = h − 1 implies that α(v_{h−1}) ∈ ψφ^{−1}(v_{h−2}) ⊆ [ ˆ0, α(v_{h−1})], while (C_{h}^{∗}) asserts that ψφ^{−1}(v_{h−1}) ⊆ [ ˆ0, α(b)] ⊆ [ ˆ0, α(v_{h−1})], so we obtain (C_{h−1}).

This completes the proof of Claim 5.6.

5.7. Claim. Let −1 ≤ k ≤ h − 1.

(a) Suppose 0 ≤ k ≤ h − 1. If φ_{k} ⊢ ψ holds and if both conditions α(v_{k}) ∈ ψφ^{−1}(v_{k−1}) and ψφ^{−1}(v_{k}) ⊆ [ ˆ0, α(v_{k+1})] are satisfied, then φ_{k+1} ⊢ ψ holds.

(b) Suppose k = −1. If φ_{−1} ⊢ ψ holds, then φ_{0} ⊢ ψ holds.

We need to prove (B_{k+1}), (C_{k+1}), and (D_{k+1}). This is clear for (D_{k+1}) because (D_{k}) implies (D_{k+1}) (with (D_{h}) empty if k = h − 1).

(a) Suppose first that 0 ≤ k ≤ h − 2. Since (D_{k}) for i = k + 1 implies that α(v_{k+1}) ∈ ψφ^{−1}(v_{k+1}) ⊆ [ ˆ0, α(v_{k+1})], while ψφ^{−1}(v_{k}) ⊆ [ ˆ0, α(v_{k+1})] by one of the assumptions, we obtain (C_{k+1}). Now (B_{k}) is the part of (B_{k+1}) corresponding to i ≤ k − 1 and moreover (C_{k}) implies that ψφ^{−1}(v_{k}) ⊆ [ ˆ0, α(v_{k})] while the extra condition α(v_{k}) ∈ ψφ^{−1}(v_{k}) holds by assumption, so we obtain (B_{k+1}) for i = k as well.

If k = h − 1, then the second additional assumption yields precisely (C_{h}^{∗}). The argument that (B_{h}) holds is obtained in the same way as above.

(b) Assume now that k = −1. Since (D_{1}) implies (D_{0}) and since (B_{0}) is empty, we are left with the proof of (C_{0}). Condition (D_{−1}) for i = 0 implies that α(v_{0}) ∈ ψφ^{−1}(v_{0}) ⊆ [ ˆ0, α(v_{0})]. Moreover, the inclusion ψφ^{−1}(v_{−1}) ⊆ [ ˆ0, α(v_{0})] is no longer an extra assumption because it is is a consequence of (A). Indeed we have v_{−1} = a and α(v_{0}) = α(a), because α(v_{0}) = αβα(a) = α(a). This proves (C_{0}) and completes the proof of Claim 5.7.

Now we prove that ⟨w, ψ⟩_{X} = 0, where w = ∑_{k=−1}^{h}(−1)^{k+1}φ_{k} and φ_{−1} = φ.

Recall that

⟨φ_{k}, ψ⟩_{X} ≠ 0 ⟺ ⟨φ_{k}, ψ⟩_{X} = 1 ⟺ φ_{k} ⊢ ψ .

There is nothing to prove if φ_{k} ⊬ ψ for all −1 ≤ k ≤ h (where ⊬ denotes of course the negation of ⊢). Excluding this case, our aim is to prove that φ_{k} ⊢ ψ for exactly two consecutive values of k. So let s be minimal such that φ_{s} ⊢ ψ (where −1 ≤ s ≤ h). We cannot have s = h by minimality of s, because φ_{h} ⊢ ψ implies φ_{h−1} ⊢ ψ, by Claim 5.6(b). We want to prove that φ_{s+1} ⊢ ψ. If s = −1, then we know that φ_{0} ⊢ ψ also holds, by Claim 5.7(b). So we can assume that 0 ≤ s ≤ h−1.

By minimality of s, we have φ_{s−1} ⊬ ψ. Now φ_{s} ⊢ ψ and φ_{s−1} ⊬ ψ imply, by Claim 5.6(a), that

(5.8)  α(v_{s}) ∉ ψφ^{−1}(v_{s}) .

By (C_{s}), we have α(v_{s}) ∈ ψ(φ^{−1}(v_{s−1}) ⊔ φ^{−1}(v_{s})), hence

(5.9)  α(v_{s}) ∈ ψφ^{−1}(v_{s−1}) .

Now (C_{s}) also implies that

ψφ^{−1}(v_{s}) ⊆ [ ˆ0, α(v_{s})] = [ ˆ0, α(v_{s+1})] ⊔ {α(v_{s})} ,

the equality coming from the fact that

rα(v_{s}) = rαβr^{s}α(a) = r^{s+1}α(a) = αβr^{s+1}α(a) = α(v_{s+1}) .

Using (5.8), it follows that

(5.10)  ψφ^{−1}(v_{s}) ⊆ [ ˆ0, α(v_{s+1})] .

Conditions 5.9 and 5.10 are precisely the two additional requirements appearing in Claim 5.7. Thus, together with the assumption φ_{s} ⊢ ψ, we get φ_{s+1} ⊢ ψ by Claim 5.7, as required.

Whenever |k − s| ≥ 2, we have φ_{k} ⊬ ψ by Claim 5.5. Thus s and s + 1 are the only two integers which come into play and we obtain

⟨w, ψ⟩_{X} = ±(⟨φ_{s}, ψ⟩_{X} − ⟨φ_{s+1}, ψ⟩_{X}) = ±(1 − 1) = 0 .

We have now proved that ⟨w, ψ⟩_{X} = 0 for any ψ : X → T′. In other words, w ∈ K_{α}(X), completing the proof of Lemma 5.4.

5.11. Notation. For any finite set X, we let

B_{α,X} = {φ ∈ T^{X} | Φ_{α} ⊆ φ(X) ⊆ G_{α}} ,

a subset of the basis T^{X} of F_{T} (X). Moreover, kB_{α,X} denotes the k-linear span of B_{α,X} inside F_{T} (X).

We can finally prove the main result of this section.

5.12. Theorem. Let α : T → T′^{op} be a join-morphism of finite lattices. For any finite set X, the image of B_{α,X} in 𝕊_{α}(X) = F_{T} (X)/K_{α}(X) is a set of k-linear generators of 𝕊_{α}(X). In other words, F_{T} (X) = kB_{α,X} + K_{α}(X).

Proof : We have to show that for any map φ : X → T, there is a linear combination u of elements of B_{α,X} such that φ − u ∈ K_{α}(X). If φ is such that Φ_{α} ⊈ φ(X), then we can take u = 0 because the mere existence of a map ψ : X → T′ such that φ ⊢ ψ implies that Φ_{α} ⊆ φ(X), by the definition of the relation φ ⊢ ψ. Thus if Φ_{α} ⊈ φ(X), then φ is forced to lie in the kernel K_{α}(X).

So we now assume that φ : X → T is such that Φ_{α} ⊆ φ(X) and we proceed by induction on the cardinality n_{φ} of the difference φ(X) − G_{α}. If n_{φ} = 0, then φ(X) ⊆ G_{α}, so φ ∈ B_{α,X}, and we can take u = φ. Assuming now that n_{φ} > 0, there exists an element a ∈ φ(X) − G_{α}. We set b = θ(a), and we consider the reduction sequence

a < v_{0} < v_{1} < … < v_{h−1} < b = θ(a)

associated to a. Recall that we set v_{−1} = a and v_{h} = b. Moreover, in the case h = 0, the reduction sequence is simply a < b.

By Lemma 5.4, the element

w = φ + ∑_{k=0}^{h}(−1)^{k+1}φ_{k}

belongs to K_{α}(X). For each 0 ≤ k ≤ h, the definition of the map φ_{k} shows that a ∉ φ_{k}(X), while we had a ∈ φ(X). Moreover, when k = h, we may have added the element b to the image φ_{h}(X), but b ∈ G_{α} because b = θ(a). Thus a ∉ G_{α}, b ∈ G_{α} − Φ_{α}, and v_{0}, … v_{h−1} ∈ Φ_{α} ⊆ G_{α}, so that the cardinality n_{φ_{k}} of the difference φ_{k}(X) − G_{α} is equal to n_{φ} − 1. By induction, φ_{k} lies in the

sum kB_{α,X} + K_{α}(X) and it follows that φ = w + ∑_{k=0}^{h}(−1)^{k}φ_{k} also belongs to

kB_{α,X} + K_{α}(X). Hence F_{T} (X) = kB_{α,X} + K_{α}(X), as required.

6. Basis for the evaluation

We continue our investigation of the evaluation 𝕊_{α}(X) and show that the image of B_{α,X} is a k-basis of 𝕊_{α}(X).

6.1. Theorem. Let α : T → T′^{op} be a join-morphism of finite lattices. Then for any finite set X, the set B_{α,X} = {φ ∈ T^{X} | Φ_{α} ⊆ φ(X) ⊆ G_{α}} maps injectively to a k-basis of 𝕊_{α}(X) = F_{T} (X)/K_{α}(X). In other words, F_{T} (X) = kB_{α,X} ⊕ K_{α}(X).

As explained in Section 7, this result is a far-reaching generalization of Theorem 6.6 in [BT4], where we only consider the so-called fundamental functors. In spirit, the proof is essentially the same as the proof in [BT4], but as it has to be generalized and adapted to the new situation, we need to go through all the arguments again.

Proof : Throughout this proof, we write G = G_{α}, Φ = Φ_{α}, and B_{X} = B_{α,X}, and we use ⊢ instead of ⊢_{α}.

Since B_{X} generates 𝕊_{α}(X) by Theorem 5.12, all we have to prove is that B_{X} maps injectively in 𝕊_{α}(X) and that its image remains a linearly independent subset. To do this, for each φ ∈ B_{X}, we consider the map ζφ : X → T′, where ζ : T → T′ is defined by

∀t ∈ T, ζ(t) = \{ \begin{matrix}α(t) & if t ∈ Φ , \\ α^{♯}(t) & otherwise . \end{matrix}

Inside the matrix of the pairing ⟨−, −⟩_{X} of Proposition 3.9, we consider the square submatrix M, indexed by B_{X} × B_{X}, defined by

∀(φ, φ′) ∈ B_{X} × B_{X} , M(φ, φ′) = ⟨φ, ζφ′⟩_{X} .

If this matrix is nonsingular, then B_{X} maps injectively in F_{T} (X)/K_{α}(X) and its image is a linearly independent set. We will actually prove more :

6.2. Theorem. The matrix M is invertible (over ℤ, hence over k).

Proof : By definition, we have

∀(φ, φ′) ∈ B_{X} × B_{X} , M(φ, φ′) = \{ \begin{matrix}1 & if φ ⊢ ζφ′ , \\ 0 & otherwise . \end{matrix}

Now

φ ⊢ ζφ′ ⟺ \{ \begin{matrix}φ ≤ βζφ′ , \\ ∀f′ ∈ Φ′, ∃x ∈ X, φ(x) = β(f′) and ζφ′(x) = f′ . \end{matrix}

We observe that the equality ζφ′(x) = f′ implies that φ′(x) ∈ Φ, otherwise we would have ζφ′(x) = α^{♯}φ′(x) ∉ Φ′, hence ζφ′(x) ≠ f′. Moreover φ′(x) ∈ Φ implies that ζφ′(x) = αφ′(x). It follows that φ′(x) = βαφ′(x) = βζφ′(x) = β(f′). Therefore, by Lemma 3.6, the condition

(6.3)  ∀f′ ∈ Φ′, ∃x ∈ X, φ(x) = β(f′) and ζφ′(x) = f′

implies that

(6.4)  ∀f ∈ Φ, ∃x ∈ X, φ(x) = f = φ′(x) .

Conversely, if (6.4) holds, then for any f′ ∈ Φ′, there exists x ∈ X such that φ(x) = β(f′) and φ′(x) = β(f′). Then ζφ′(x) = αβ(f′) = f′ and so (6.3) holds. Thus (6.3) and (6.4) are equivalent and we get

φ ⊢ ζφ′ ⟺ \{ \begin{matrix}φ ≤ βζφ′ , \\ ∀f ∈ Φ, ∃x ∈ X, φ(x) = f = φ′(x) . \end{matrix}

Now for any x ∈ X, we have βζφ′(x) = βαφ′(x) = φ′(x) if φ′(x) ∈ Φ, while βζφ′(x) = βα^{♯}φ′(x) = ωφ′(x) if φ′(x) ∉ Φ. Therefore

(6.5)  φ ≤ βζφ′ ⟺ ∀x ∈ X, \{ \begin{matrix}φ(x) ≤ φ′(x) & if φ′(x) ∈ Φ , \\ φ(x) ≤ ωφ′(x) & otherwise . \end{matrix}

Finally

φ ⊢ ζφ′ ⟺ \{ \begin{matrix}∀x ∈ X, \{ \begin{matrix}φ(x) ≤ φ′(x) & if φ′(x) ∈ Φ , \\ φ(x) ≤ ωφ′(x) & otherwise . \end{matrix} \\ ∀f ∈ Φ, ∃x ∈ X, φ(x) = f = φ′(x) . \end{matrix}

Suppose that φ ⊢ ζφ′ holds. Then in particular ωφ(x) ≤ ωφ′(x) for any x ∈ X, because ω is order-preserving and idempotent, by Lemma 4.7. By Lemma 4.2, we also deduce that ρφ(x) ≤ ρφ′(x) if φ′(x) ∈ Φ. Moroever, if φ′(x) ∉ Φ, then φ′(x) ∈ G − Φ (because φ′(X) ⊆ G by the definition of B_{X}) and we get

ρφ(x) ≤ ρωφ′(x) = ρβα^{♯}φ′(x) = β^{♯}α^{♯}φ′(x) = θφ′(x) = φ′(x) = ρφ′(x) ,

using again that φ′(x) lies in G−Φ = Im(θ), hence is fixed under θ and ρ. We have now proved that

φ ⊢ ζφ′ ⟹ \{ \begin{matrix}ωφ ≤ ωφ′ and \\ ρφ ≤ ρφ′ . \end{matrix}

We denote by ⪯ the preorder on the set B_{X} defined by the right hand side, that is, for all φ, φ′ ∈ B_{X},

φ ⪯ φ′ ⟺ (ωφ ≤ ωφ′ and ρφ ≤ ρφ′) .

It follows that the matrix M is block triangular, with blocks indexed by the equivalence classes of the preorder ⪯ on B_{X}. We denote by ⪯⪰ this equivalence relation, i.e.

φ⪯⪰φ′ ⟺ (φ ⪯ φ′ and φ′ ⪯ φ) ⟺ (ωφ = ωφ′ and ρφ = ρφ′) .

Showing that M is invertible now amounts to showing that 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.

Let t ∈ G − Φ. Then t = θ(t) and, for any u ∈ [t, ω(t)], we have ρ(u) = t and ω(u) = ω(t) by Lemma 4.11. It follows in particular that t is uniquely determined by any element u ∈ [t, ω(t)], so that the sets [t, ω(t)], for t ∈ G − Φ, are disjoint. We set

G̊ = {t ∈ G − Φ | t < ω(t)} .

Remember that, by Lemma 4.8, we have

(6.6)  ∀t ∈ G − Φ, ]t, ω(t)] ⊆ Φ .

This shows that G̊ = {t ∈ G − Φ | ω(t) ∈ Φ}. Moreover, we set

∀t ∈ G̊, G_{t} = [t, ω(t)]  and  G_{∗} = G − ⨆_{t∈G̊}G_{t} ,

so that we get a partition

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

Notice that

G_{∗} − (G_{∗} ∩ Φ) = {t ∈ T | t = θ(t) = ω(t)} .

This set is actually equal to β(T′) − Φ by Proposition 4.13, but that does not play any role in the sequel.

6.7. Lemma. Let φ′, φ ∈ B_{X}. If φ′⪯⪰φ, then φ^{′−1}(G_{t}) = φ^{−1}(G_{t}) for all t ∈ {∗} ⊔ G̊.

Proof : Since φ⪯⪰φ′, we have ρφ = ρφ′ and ωφ = ωφ′, by the above discussion. Let t ∈ G̊, and let x ∈ φ^{−1}(G_{t}). Then φ(x) ∈ [t, ω(t)], so ρ(t) = t = ρ(φ(x)) = ρ(φ′(x)) ≤ φ′(x). Similarly ω(t) = ω(φ(x)) = ω(φ′(x)) ≥ φ′(x), by Lemma 4.7. It follows that t ≤ φ′(x) ≤ ω(t), so x ∈ φ′^{−1}(G_{t}). Hence φ^{−1}(G_{t}) ⊆ φ′^{−1}(G_{t}). Exchanging the roles of φ and φ′, we obtain that φ^{−1}(G_{t}) = φ′^{−1}(G_{t}). Now G_{∗} is the complement of ⨆_{t∈G̊}G_{t} in G and the functions φ′, φ have their values in G (by

the definition of B_{X}). So we must have also φ^{′−1}(G_{∗}) = φ^{−1}(G_{∗}). This completes the proof of Lemma 6.7.

We choose an arbitrary element φ_{0} of C and, for every t ∈ {∗} ⊔ G̊, we define

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

It follows from Lemma 6.7 that this definition does not depend on the choice of φ_{0}. Therefore, the equivalence class C yields a decomposition of X as a disjoint union

X = ⨆_{t∈{∗}⊔G̊}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 ∈ G̊, define

Φ_{t} = ]t, ω(t)] .

By (6.6), we have Φ_{t} = Φ ∩ G_{t}. Then we define Φ_{∗} = Φ − ⨆_{t∈G̊}Φ_{t} = Φ ∩ G_{∗}, so that

we get a partition

Φ = ⨆_{t∈{∗}⊔G̊}Φ_{t} .

For every t ∈ {∗} ⊔ G̊ and every φ ∈ C, the function φ_{t} satisfies the condition Φ_{t} ⊆ φ_{t}(X_{t}) ⊆ G_{t}, by the definition of B_{X}. Moreover, if φ′, φ ∈ C, then

M(φ, φ′) = 1 ⟺ ∀t ∈ \{∗\} ⊔ G̊ , \{ \begin{matrix}∀x ∈ X_{t} , \{ \begin{matrix}φ(x) ≤ φ′(x) & if φ′(x) ∈ Φ_{t} , \\ φ(x) ≤ ωφ′(x) & otherwise, \end{matrix} \\ ∀f ∈ Φ_{t} , ∃x ∈ X_{t} , φ(x) = f = φ′(x) . \end{matrix}

It follows that the matrix M_{C} is a tensor product of square matrices M_{C,t}, for t ∈ {∗} ⊔ G̊, where M_{C,t} is indexed by the set A_{t} of functions φ : X_{t} → G_{t} such that Φ_{t} ⊆ φ(X_{t}). Thus M_{C,t} satisfies

M_{C,t}(φ, φ′) = 1 ⟺ \{ \begin{matrix}∀x ∈ X_{t} , \{ \begin{matrix}φ(x) ≤ φ′(x) & if φ′(x) ∈ Φ_{t} , \\ φ(x) ≤ ωφ′(x) & otherwise, \end{matrix} \\ ∀f ∈ Φ_{t} , ∃x ∈ X_{t} , φ(x) = f = φ′(x) . \end{matrix}

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

If x ∈ X_{∗} and φ′ ∈ A_{∗}, then either φ′(x) = ωφ′(x) or φ′(x) ∈ Φ_{∗}, by the construction of G_{∗}. Therefore, if M_{C,∗}(φ, φ′) ≠ 0, then φ(x) ≤ φ′(x) for any x ∈ X_{∗}. It follows that the matrix M_{C,∗} is triangular. Clearly M_{C,∗}(φ, φ) = 1 for any φ ∈ A_{∗}, so M_{C,∗} is unitriangular, hence invertible, as required.

We are left with the matrices M_{C,t} for t ∈ G̊. If t ∈ G̊, then G_{t} = [t, ω(t)] is isomorphic to the totally ordered lattice \underline{n} = \{0 < 1 < … < n\} for some n ≥ 1 (note that t < ω(t)). Moreover, Φ_{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 we consider the set A_{n} of all such maps φ : X → \underline{n} satisfying the condition [n] ⊆ φ(X). The matrix M_{C,t}, which we write M for simplicity, is now indexed by A_{n} and we have

M(φ, φ′) = 1 ⟺ \{ \begin{matrix}∀x ∈ X, \{ \begin{matrix}φ(x) ≤ φ′(x) & if φ′(x) ∈ [n] , \\ φ(x) ≤ ωφ′(x) & if φ′(x) = 0 , \end{matrix} \\ ∀f ∈ [n], ∃x ∈ X, φ(x) = f = φ′(x) . \end{matrix}

We observe that the condition φ(x) ≤ ωφ′(x) if φ′(x) = 0 is always fulfilled since ω(0) = n. Hence

M(φ, φ′) = 1 ⟺ \{ \begin{matrix}∀x ∈ X, φ(x) ≤ φ′(x) if φ′(x) ∈ [n] , \\ ∀f ∈ [n], ∃x ∈ X, φ(x) = f = φ′(x) . \end{matrix}

This is exactly the matrix M\underline{n} ; φ′,φ considered at the end of the proof of Theorem 6.1 in [BT4]. In fact, it is a reduction to the case of a totally ordered lattice because this matrix corresponds to the special case T = \underline{n}. It is proved on page 246 of [BT4] that this matrix is invertible. This completes the proof of Theorem 6.2, hence of Theorem 6.1.

6.8. Corollary. Let α : T → T′^{op} be a join-morphism of finite lattices and let 𝕊_{α} be the associated correspondence functor. Then for any finite set X the k-module 𝕊_{α}(X) is free of rank

rk(𝕊_{α}(X)) = ∑_{i=0}^{|Φ_{α}|}(−1)^{i}\binom{|Φ_{α}|}{i}(|G_{α}| − i)^{|X|} .

Proof : A well-known combinatorial formula (see Lemma 8.1 in [BT2]) shows that the right hand side in the statement gives the number of maps φ : X → T satisfying the condition Φ_{α} ⊆ φ(X) ⊆ G_{α}. The result follows from Theorem 6.1.

We can now give an answer to the question left open in Remark 3.12 and prove that the pairing 𝕊_{α} × 𝕊′_{α} → k is nondegenerate in the strong sense.

6.9. Proposition. Let α : T → T′^{op} be a join-morphism of finite lattices and let ⟨−, −⟩ : F_{T} × F_{T′} → k be the associated pairing (see Proposition 3.9). Then the natural morphism

i : S_{α} = F_{T} /K_{α} ⟶ (S′_{α})^{♮} = (F_{T′}/K′_{α})^{♮}

is an isomorphism.

Proof : For the convenience of this proof, we pass to the dual and we aim to prove that the natural morphism j : 𝕊′_{α} → 𝕊_{α}^{♮} is an isomorphism. By Lemma 6.2, we know that the matrix M indexed by B_{α,X} × B_{α,X} defined by

∀(π, φ) ∈ B_{α,X} × B_{α,X} , M(π, φ) = ⟨π, ζφ⟩_{X}

is invertible. Let N = M^{−1}. Then

∀(π, π′) ∈ B_{α,X} × B_{α,X} , ∑_{φ∈B_{α,X}}⟨π, ζφ⟩_{X} N(φ, π′) = δ_{π,π′} ,

where δ_{π,π′} is the Kronecker symbol.

The natural morphism j_{X} : F_{T′}(X)/K′_{α}(X) → (F_{T} (X)/K_{α}(X))^{♮} is injective, by the definition of K′_{α}. Now (F_{T} (X)/K_{α}(X))^{♮} is isomorphic to the submodule of F_{T} (X)^{♮} consisting of linear forms F_{T} (X) → k which vanish on K_{α}(X). Let λ be such a form, and set

λ̂ = ∑_{φ,π′∈B_{α,X}} N(φ, π′)λ(π′) ζφ ∈ F_{T′}(X) .

Then for any π ∈ B_{α,X},

⟨π, λ̂⟩_{X} = ∑_{φ,π′∈B_{α,X}} N(φ, π′)λ(π′)⟨π, ζφ⟩_{X} = ∑_{π′∈B_{α,X}} δ_{π,π′}λ(π′) = λ(π) .

Moreover ⟨u, λ̂⟩_{X} = 0 for any u ∈ K_{α}(X), by the definition of K_{α}, and λ(u) = 0 also, by our assumption on λ. It follows that the linear forms λ and ⟨−, λ̂⟩_{X} coincide on kB_{α,X} + K_{α}(X), which is the whole of F_{T} (X) by Theorem 5.12. Hence λ = ⟨−, λ̂⟩_{X}, so λ lies in the image of the morphism j_{X}. It follows that j_{X} is surjective, hence it is an isomorphism.

7. The main example of fundamental functors

Let T be a finite lattice and let (E, R) be the poset of irreducible elements of T, i.e. E = Irr(T) and R is the restriction to E of the order relation of T. For clarity, we use a subscript T for the interval [s, t]_{T} in T, where s ≤ t in T. Similarly, if a ≤ b in E, then [a, b]_{E} = {e ∈ E | a ≤ e ≤ b}. Recall that an upper subset in E is a subset A of E such that, whenever a ∈ A and a ≤ b with b ∈ E, then b ∈ A. We let I^{↑}(E, R) be the set of all upper subsets in E, which is a lattice for the usual operations of union and intersection. We consider the map

α : T ⟶ I^{↑}(E, R)^{op} , t ↦ α(t) := [ t, ˆ1 ]_{T} ∩ E ,

which is easily seen to be a join-morphism, because [ s ∨ t, ˆ1 ]_{T} = [ s, ˆ1 ]_{T} ∩ [ t, ˆ1 ]_{T} and α( ˆ0 ) = [ ˆ0, ˆ1 ]_{T} ∩ E = E = ˆ1_{I^{↑}(E,R)} = ˆ0_{I^{↑}(E,R)^{op}}.

Our aim is to show that the corresponding functor 𝕊_{α} is isomorphic to the fundamental functor 𝕊_{E,R^{op}} studied in [BT3, BT4] and that our description of a k-basis of 𝕊_{α}(X) is the same as the one obtained for 𝕊_{E,R^{op}}(X) in [BT4]. In fact, our results in Sections 5 and 6 have been inspired by this very special case, already proved in [BT4].

7.1. Lemma. Let α : T → I^{↑}(E, R)^{op} be as above and let β = α^{op}.

(a) For any A ∈ I^{↑}(E, R), we have β(A) = ⋀_{a∈A} a.

(b) Φ_{α} = E and Φ′_{α} = {[e, ·[_{E}| e ∈ E}, where [e, ·[_{E}= {f ∈ E | f ≥ e}.

Proof : (a) We have

β(A) = ⋁_{\begin{matrix}t∈T \\ α(t)⊆_{op}A \end{matrix}} t = ⋁_{\begin{matrix}t∈T \\ A⊆α(t) \end{matrix}} t = ⋁_{\begin{matrix}t∈T \\ A⊆[ t,ˆ1 ]_{T} \end{matrix}} t = ⋁_{\begin{matrix}t∈T \\ t≤A \end{matrix}} t = ⋀_{a∈A} a .

(b) For any e ∈ E = Irr(T), we have α(e) = [e, ·[_{E} and this is an irreducible element of I^{↑}(E, R) (also called a principal upper subset). Moreover, by (a),

βα(e) = ⋀_{f∈[e,·]_{E}} f = ⋀_{f≥e} f = e .

The definition of Φ_{α} (see Notation 3.5) yields Φ_{α} = E. Moreover Φ′_{α} = α(Φ_{α}) = {[e, ·[_{E}| e ∈ E}.

7.2. Proposition. With the notation above, there is an isomorphism 𝕊_{α} ≅ 𝕊_{E,R^{op}}, where 𝕊_{E,R^{op}} is the fundamental functor introduced in [BT3].

Proof : We don’t go back to the definition of 𝕊_{E,R^{op}} but use instead the following description. By Theorem 6.5 in [BT3], there is a canonical surjective morphism Θ_{T} : F_{T} → 𝕊_{E,R^{op}}. Next, Theorem 7.1 in [BT3] asserts that, on evaluation at a finite set X, the kernel of the map Θ_{T,X} : F_{T} (X) → 𝕊_{E,R^{op}}(X) consists of all linear combinations ∑_{φ∈T^{X}} λ_{φ}φ satisfying a system of linear equations (E_{ψ}) indexed by all maps ψ : X → I^{↑}(E, R). More explicitly,

(E_{ψ}) :  ∑_{\begin{matrix}φ∈T^{X} \\ φ ⊢_{E,R} ψ \end{matrix}} λ_{φ} = 0 ,

where the relation ⊢_{E,R} is defined as follows (see Theorem 7.3 in [BT3] or Theo-

rem 4.13 in [BT4]) :

φ ⊢_{E,R} ψ ⟺ ∀t ∈ T, ψ(φ^{−1}(t)) ⊆ [t, ˆ1[_{T} ∩E and ∀e ∈ E, ψ(φ^{−1}(e)) = [e, ·[_{E} ,

with the abuse of notation which identifies ψ(φ^{−1}(t)) with the union of its elements in I^{↑}(E, R). The first condition can be rewritten as

∀t ∈ T, ψ(φ^{−1}(t)) ⊆ [ ˆ0, α(t) ]_{I^{↑}(E,R)}

while the second becomes

∀e ∈ E, α(e) ∈ ψ(φ^{−1}(e)) .

Thus we find that φ ⊢_{E,R} ψ is equivalent to φ ⊢ ψ (see Notation 3.8). It follows that

the equation (E_{ψ}) can be rewritten as ∑_{φ ⊢ ψ} λ_{φ} = 0. Since this must hold for every ψ, we obtain that ∑_{φ∈T^{X}} λ_{φ}φ must belong to the left kernel of the pairing defined in Notation 3.8. In other words, Ker(Θ_{T,X}) = K_{α}(X). This implies that

𝕊_{α}(X) = F_{T} (X)/K_{α}(X) = F_{T} (X)/ Ker(Θ_{T,X}) ≅ 𝕊_{E,R^{op}}(X) ,

hence 𝕊_{α} ≅ 𝕊_{E,R^{op}}, as was to be shown.

By Theorem 6.1, we know that a k-basis of 𝕊_{α}(X) is obtained by taking the image of the subset

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

where G_{α} is defined in (5.1). Similarly, by Theorem 6.6 in [BT4], we know that a k-basis of 𝕊_{E,R^{op}}(X) is obtained by taking the image of the subset

B_{X} = {φ ∈ T^{X} | E ⊆ φ(X) ⊆ G} ⊆ F_{T} (X) ,

where G is described as

(7.3)  G = E ⊔ G^{♯} ,  G^{♯} = {a ∈ T | a = r^{∞}σ^{∞}(a)} ,

as in Lemma 2.9 of [BT4]. Here r : T → T is defined by (3.13) and σ : T → T is defined by

σ(t) = ⋀_{\begin{matrix}e∈Irr(T) \\ t<e \end{matrix}} e ,

Now we can show that both approaches coincide and that the result of [BT4] is indeed a special case of Theorem 6.1.

7.4. Proposition. With the notation above, G_{α} = G, hence B_{α,X} = B_{X}.

Proof : Since Φ_{α} = E by Lemma 7.1, we get G_{α} = E ⊔ Im(θ), so we need to show that

t ∈ Im(θ) ⟺ t ∈ G^{♯} .

We can assume that t ∉ E because both subsets intersect E trivially. Now t ∈ Im(θ) if and only if

t = θ(t) = β^{♯}α^{♯}(t) = ρω(t) = r^{∞}ω(t)

because we have ρ = r^{∞} by Lemma 4.2 and the fact that Φ_{α} = E. So we are left with the proof that ω(t) = σ^{∞}(t) for any t ∈ T with t ∉ E.

Suppose first that α(t) ∉ Φ′_{α}. Then α^{♯}(t) = α(t) and Lemma 7.1 implies that

ω(t) = βα(t) = ⋀_{a∈α(t)} a = ⋀_{\begin{matrix}a∈E \\ a≥t \end{matrix}} a = ⋀_{\begin{matrix}a∈E \\ a>t \end{matrix}} a

because t ∉ E. Therefore ω(t) = σ(t). The same argument applies to ω(t) instead of t, because α(ω(t)) = αβα(t) = α(t) ∉ Φ′_{α}. Thus ω(ω(t)) = σ(ω(t)) and therefore

σ^{2}(t) = σω(t) = ω(ω(t)) = (βα)^{2}(t) = βα(t) = σ(t) .

It follows that σ^{∞}(t) = σ(t) = ω(t).

Suppose now that α(t) ∈ Φ′_{α}. Let l ≥ 1 be the smallest integer such that α^{♯}(t) = r^{l}α(t) ∉ Φ′_{α}. By Lemma 4.7, we have [t, ω(t)] ∩ E = {u_{0}, …, u_{l−1}}, where u_{i} = βr^{i}α(t) for 0 ≤ i ≤ l − 1. For any e ∈ E with e > t, we have α(e) ≤ α(t) and Corollary 4.4 implies that either α(e) = r^{i}α(t) for some 0 ≤ i ≤ l − 1 or α(e) ≤ α^{♯}(t). Applying β and using the equality e = βα(e) (because e ∈ E = Φ_{α}), we see that either e = u_{i} for some 0 ≤ i ≤ l−1 or e ≥ βα^{♯}(t) = ω(t). The definition of σ and the fact that t < u_{0} (because t ∉ E) yield

(7.5)  σ(t) = u_{0}, σ(u_{0}) = u_{1}, …, σ(u_{l−2}) = u_{l−1} .

It remains to determine σ(u_{l−1}). Note first that, for any f ∈ E, we have α(f) = [f, ˆ1 [_{T} ∩E = [f, ·[_{E} and moreover

(7.6)  σ(f) = ⋀_{\begin{matrix}e∈E \\ e>f \end{matrix}} e = ⋀_{e∈]f,·[_{E}} e = β(]f, ·[_{E}) ,

by Lemma 7.1. Therefore

r^{l−1}α(t) = αβ(r^{l−1}α(t)) = α(u_{l−1}) = [u_{l−1}, ·[_{E}

and hence

α^{♯}(t) = r^{l}α(t) = r[u_{l−1}, ·[_{E} = ]u_{l−1}, ·[_{E} ,

so that

ω(t) = βα^{♯}(t) = β(]u_{l−1}, ·[_{E}) = σ(u_{l−1}) = σ^{l+1}(t) ,

using (7.6) and (7.5).

There are now two cases. Suppose first that σ(u_{l−1}) = u_{l−1}. Then σ^{l+1}(t) = σ(u_{l−1}) = u_{l−1}, hence σ^{∞}(t) = u_{l−1} = σ(u_{l−1}) = ω(t), as was to be shown. Suppose now that σ(u_{l−1}) > u_{l−1}, that is, ω(t) > u_{l−1}. Then ω(t) ∉ E by Lemma 4.7(c). The definition of σ implies that, for any e ∈ E,

e > u_{l−1} ⟺ e ≥ σ(u_{l−1}) ⟺ e ≥ ω(t) ⟺ e > ω(t) ,

where the latter equivalence comes from the fact that ω(t) ∉ E. We deduce that σ(u_{l−1}) = σ(ω(t)), hence ω(t) = σ(ω(t)). But since σ^{l+1}(t) = σ(u_{l−1}) = ω(t), we obtain σ^{∞}(t) = ω(t).

This shows that σ^{∞}(t) = ω(t) in all cases, completing the proof that Im(θ) = G^{♯}. The equality B_{α,X} = B_{X} follows.

8. The injective case

In this section, we study the case when our given join-morphism α : T → T′^{op} is injective. We first show that this injective case could also be called the surjective case.

8.1. Lemma. Let α : T → T′^{op} be a join-morphism of finite lattices and let β = α^{op}.

(a) If α is injective, then βα = id_{T} and in particular β is surjective.

(b) If β is surjective, then βα = id_{T} and in particular α is injective.

Proof : (a) Since αβα = α by Lemma 3.4, the injectivity of α implies that βα = id_{T}.

(b) Similarly, since βαβ = β by Lemma 3.4, the surjectivity of α implies that βα = id_{T}.

Next we show that some important simplifications occur.

8.2. Lemma. Let α : T → T′^{op} be a join-morphism of finite lattices and suppose that α is injective.

(a) Φ_{α} = {f ∈ Irr(T) | α(f) ∈ Irr(T′)}.

(b) G_{α} = T.

(c) T = Φ_{α} ⊔ {t ∈ T | t = ω(t) = θ(t)}.

Proof : (a) Let β = α^{op} as usual. The definition of Φ_{α} contains the condition βα(f) = f, but this condition is automatically satisfied when α is injective, by Lemma 8.1.

(b) By Lemma 5.2, we have β(T′) ⊆ G_{α}, hence G_{α} = T by surjectivity of β.

(c) By Proposition 4.13, we have β(T′) = Φ_{α} ⊔ {t ∈ T | t = ω(t) = θ(t)}.

8.3. Remark. Let t ∈ T and let l be the smallest integer such that r^{l}α(t) ∉ Φ′_{α}, as in Section 4. Keeping the assumption that α is injective, it is easy to see that

t ∈ Φ_{α} ⟺ α(t) ∈ Φ′_{α} ⟺ l ≥ 1 .

Moreover, if t ∈ Φ_{α} and v_{i} = βr^{i}α(t), then either

θ(t) < t = v_{0} < … < v_{l−1} = ω(t) ∈ Φ_{α} ,

or

t = v_{0} < … < v_{l−1} < θ(t) = ω(t) ∉ Φ_{α} .

Both situations occur in specific examples. Note also that if t ∉ Φ_{α}, then t = ω(t) = θ(t) by Lemma 8.2, so there are no reduction sequences.

8.4. Example. Let α : T → T′^{op} be an injective join-morphism of finite lattices. Replace every e ∈ Irr(T′) by a lozenge

[figure: e; e′; e′′; e′′′]

and let \overline{T′} be the resulting lattice, in which every such e becomes reducible. Thus no irreducible element of T′ remains irreducible in \overline{T′} under the inclusion j : T′ → \overline{T′} (mapping e ∈ Irr(T′) to the top e in the corresponding lozenge) and so no irreducible element of T is mapped to an irreducible element of \overline{T′} under the composite \overline{α} = j ∘ α : T → \overline{T′} ^{op}. By Lemma 8.2 and injectivity of \overline{α}, we get Φ\overline{α} = ∅ and G\overline{α} = T. Therefore the condition Φ\overline{α} ⊆ φ(X) ⊆ G\overline{α} is satisfied by every map φ : X → T. Consequently, by using either Theorem 6.1 or Remark 3.16, we obtain

𝕊\overline{α} = F_{T} ,

so our main construction of functors also covers the functors F_{T}. In this example, T can be any finite lattice, since we can choose T′ = T^{op} and α = id.

9. The minimal nonzero evaluation

As usual, α : T → T′^{op} is a join-morphism of finite lattices, Φ_{α} is the subset of Irr(T) defined in Notation 3.5, and 𝕊_{α} = F_{T} /K_{α}. We have seen that the set Φ_{α} plays a crucial role throughout the paper and it appears again here as a minimal set such that the evaluation 𝕊_{α}(Φ_{α}) is nonzero. Our purpose is to analyse the structure of 𝕊_{α}(Φ_{α}) as a module for the algebra of the monoid of all relations on Φ_{α}. Let us start with an easy observation.

9.1. Lemma.

(a) For any finite set X, let φ ∈ T^{X} be such that Φ_{α} ⊈ φ(X). Then φ ∈ K_{α}(X).

(b) For any finite set X such that |X| < |Φ_{α}|, we have 𝕊_{α}(X) = {0}.

(c) 𝕊_{α}(Φ_{α}) ≠ {0}.

Proof : (a) This was already observed at the beginning of the proof of Theorem 5.12.

(b) If φ ∈ T^{X} satisfies Φ_{α} ⊈ φ(X), the image of φ in 𝕊_{α}(X) = F_{T} (X)/K_{α}(X) is zero by (a). If |X| < |Φ_{α}|, then |φ(X)| ≤ |X| < |Φ_{α}|, so Φ_{α} ⊈ φ(X). Since this holds for every φ, we obtain 𝕊_{α}(X) = {0}.

(c) If X = Φ_{α}, the inclusion j : Φ_{α} → T does not lie in K_{α}(Φ_{α}) because j′ = α∘j satisfies j ⊢_{α} j′, hence ⟨j, j′⟩_{α,Φ_{α}} ≠ 0. Thus the image of j in 𝕊_{α}(Φ_{α}) is nonzero.

Alternatively, the k-basis B_{α,X} of 𝕊_{α}(X) is empty if |X| < |Φ_{α}| and nonempty if X = Φ_{α}. However, this argument is much less elementary since it requires Theorem 6.1.

Given a finite set E, the set of relations on E (i.e. all subsets of E × E) forms a monoid which is a k-basis for a k-algebra A_{E}, the algebra of the monoid. For any partial order relation R on E, there is a very special A_{E}-module M_{E,R}, called the fundamental module associated to the pair (E, R) and described explicitly in the following way. First M_{E,R} is a free k-module with a basis {m_{σ} | σ ∈ Σ_{E}}, where Σ_{E} is the group of all permutations of the set E. Then the left A_{E}-module structure is described by specifying the action of every relation Q on the k-basis :

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

Here, Δ_{τ} = {(τ(e), e) | e ∈ E} ⊆ E × E and ^{σ}R = Δ_{σ}RΔ_{σ^{−1}}, while Δ = Δ_{id} is the diagonal subset of E × E.

The module M_{E,R} was introduced in Section 7 of [BT1] as a left ideal Pf_{R}, where P is some quotient algebra of A_{E} and f_{R} is a suitable idempotent in P. The action (9.2) appears in Proposition 8.5 of [BT1]. The fundamental module M_{E,R} was used in [BT3, BT4] for the definition of the fundamental functor 𝕊_{E,R}, already mentioned in Section 7 as a very special case of 𝕊_{α}. This module can also be recovered as the evaluation 𝕊_{E,R}(E) ≅ M_{E,R}.

We now show that the latter isomorphism is again a very special case of a property of 𝕊_{α}. To make our notation precise, we note that Φ_{α} is a (full) subposet of T and we let R_{α} be the partial order relation on Φ_{α} obtained by restriction from T.

9.3. Theorem. With the notation above, 𝕊_{α}(Φ_{α}) is isomorphic to M_{Φ_{α},R_{α}^{op}} as a module over the algebra A_{Φ_{α}}.

Proof : Write Φ = Φ_{α} and R = R_{α}. Let φ ∈ T^{Φ} be such that its image in 𝕊_{α}(Φ) is nonzero. By Lemma 9.1(a), we must have Φ ⊆ φ(Φ), hence Φ = φ(Φ). Therefore, there exists a permutation τ ∈ Σ_{Φ} such that φ ∘ τ = j, where j : Φ → T denotes the inclusion map. Then, by the definition of the action of correspondences, we get, for any f ∈ Φ,

(Δ_{τ} j)(f) = ⋁_{\begin{matrix}x∈Φ \\ (f,x)∈Δ_{τ} \end{matrix}} j(x) = j(τ^{−1}(f)) = φ(f) ,

hence φ = j ∘ τ^{−1} = Δ_{τ} j. Thus all functions φ ∈ T^{Φ} map to zero in 𝕊_{α}(Φ) except the functions j ∘ τ^{−1} = Δ_{τ} j.

Suppose that σ ∈ Σ_{Φ} is such that the relation Δ_{σ}j ⊢_{α} j′ holds, where j′ = α ∘ j. Then Lemma 3.7(a) implies that α ∘ j = j′ ≤ α ∘ Δ_{σ}j, hence j ≥ Δ_{σ}j because α_{|Φ} : Φ → Φ′^{op} is a poset isomorphism (Lemma 3.6). By increasing induction in the poset Φ, we deduce that j = Δ_{σ}j, hence f = σ^{−1}(f) for all f ∈ Φ, in other words σ = id. Thus if ⟨Δ_{σ}j , j′⟩_{α,Φ} ≠ 0, then σ = id.

Now we can prove that the functions {Δ_{σ}j | σ ∈ Σ_{Φ}} remain k-linearly independent in 𝕊_{α}(Φ) = 𝔽_{T} (Φ)/K_{α}(Φ). Suppose that

∑_{σ∈Σ_{Φ}} λ_{σ}Δ_{σ}j ∈ K_{α}(Φ) ,

where λ_{σ} ∈ k. Then, for all τ ∈ Σ_{Φ},

0 = ⟨ ∑_{σ∈Σ_{Φ}} λ_{σ}Δ_{σ}j , Δ_{τ} j′⟩_{α,Φ} = ∑_{σ∈Σ_{Φ}} λ_{σ}⟨Δ_{τ}^{op}Δ_{σ}j , j′⟩_{α,Φ} ,

because this is a functorial pairing by Proposition 3.9. But since we have Δ_{τ}^{op}Δ_{σ} = Δ_{τ^{−1}}Δ_{σ} = Δ_{τ^{−1}σ}, we get a nonzero term only if τ^{−1}σ = id. So we are left with 0 = λ_{σ}⟨j , j′⟩_{α,Φ} = λ_{σ}, proving the required linear independence. Moreover, the image in 𝕊_{α}(Φ) of the set {Δ_{σ}j | σ ∈ Σ_{Φ}} is a basis of 𝕊_{α}(Φ) because all the other functions φ ∈ T^{Φ} map to zero.

Now we consider the action of a relation Q ⊆ Φ × Φ and we assume first that Qj = j. Then, for all f ∈ Φ, we have

f = j(f) = (Qj)(f) = ⋁_{\begin{matrix}x∈Φ \\ (f,x)∈Q \end{matrix}} j(x) .

Since f is irreducible in T, one of the terms must be f and j(x) ≤ j(f) for all x such that (f, x) ∈ Q. In other words, (f, f) ∈ Q and moreover the property (f, x) ∈ Q implies x ≤ f inside Φ, that is, (f, x) ∈ R^{op}. Thus if Qj = j, then Δ ⊆ Q ⊆ R^{op}. Conversely, if Δ ⊆ Q ⊆ R^{op}, then

(Qj)(f) = ⋁_{\begin{matrix}x∈Φ \\ (f,x)∈Q \end{matrix}} j(x) .

Since one of the terms is j(f) (because Δ ⊆ Q) and since (f, x) ∈ Q implies j(x) ≤ j(f) (because Q ⊆ R^{op}), we are left with (Qj)(f) = j(f), hence Qj = j. We have proved that

(9.4)  Qj = j ⟺ Δ ⊆ Q ⊆ R^{op} .

Finally we can compute the action of Q on each element Δ_{σ}j (mapping to a basis element of 𝕊_{α}(Φ), as proved above). If QΔ_{σ}j is not of the form Δ_{π}j for some π ∈ Σ_{Φ}, then its image is zero in 𝕊_{α}(Φ) by the first paragraph of the proof. Otherwise, by (9.4) followed by conjugation by Δ_{σ}, we obtain

QΔ_{σ}j = Δ_{π}j ⟺ Δ_{π^{−1}}QΔ_{σ}j = j
⟺ Δ ⊆ Δ_{π^{−1}}QΔ_{σ} ⊆ R^{op}
⟺ Δ ⊆ Δ_{σ}Δ_{π^{−1}}Q ⊆ Δ_{σ}R^{op}Δ_{σ^{−1}}
⟺ Δ ⊆ Δ_{τ^{−1}}Q ⊆ ^{σ}R^{op}

where τ = πσ^{−1}. Thus we recover exactly the action of the monoid of relations on the fundamental module M_{Φ,R^{op}}, as described in (9.2). In other words, we have an isomorphism of A_{Φ_{α}}-modules 𝕊_{α}(Φ) ≅ M_{Φ,R^{op}}.

Given a finite poset (Φ, R), the fundamental functor 𝕊_{Φ,R^{op}} is a special case of a functor 𝕊_{α}, by Proposition 7.2. By Theorem 9.3 and Lemma 9.1, its evaluation at Φ is isomorphic to M_{Φ,R^{op}} and 𝕊_{Φ,R^{op}}(X) = {0} whenever |X| < |Φ|. Moreover, this property is shared by all correspondence functors 𝕊_{α} whose associated poset (Φ_{α}, R_{α}) is isomorphic to (Φ, R). We now show that the relationship between 𝕊_{α} and 𝕊_{Φ,R^{op}} can be made more explicit by establishing that the fundamental functor 𝕊_{Φ,R^{op}} is minimal among all correspondence functors 𝕊_{α} whose associated poset (Φ_{α}, R_{α}) is isomorphic to (Φ, R).

9.5. Proposition. With the notation above, the fundamental functor 𝕊_{Φ_{α},R_{α}^{op}} is isomorphic to a subquotient of 𝕊_{α}.

Proof : Write Φ = Φ_{α} and R = R_{α}. In this proof, we need to go back to the definition of 𝕊_{Φ,R^{op}} given in Section 2 of [BT3]. First recall that evaluation at Φ has a left adjoint

A_{Φ}− Mod ⟶ F_{k} , W ↦ L_{Φ,W}

defined by L_{Φ,W} = kC(−, Φ) ⊗_{A_{Φ}} W, where C(X, Φ) denotes the set of all correspondences between X and Φ and kC(X, Φ) is the free k-module with basis C(X, Φ). Moreover, L_{Φ,W} has a unique subfunctor J_{Φ,W} which is maximal with respect to the condition that it vanishes at Φ. The fundamental functor 𝕊_{Φ,R^{op}} is defined by

𝕊_{Φ,R^{op}} := L_{Φ,M}/J_{Φ,M} ,

where M := M_{Φ,R^{op}} is the fundamental A_{Φ}-module defined by (9.2). We refer to Section 2 of [BT3] for more details.

By Theorem 9.3, there is an isomorphism 𝕊_{α}(Φ) ≅ M and the adjunction property implies that there is a corresponding morphism

π : L_{Φ,M} ⟶ 𝕊_{α}

which is an isomorphism on evaluation at Φ. Therefore Ker(π) vanishes at Φ, so that Ker(π) ⊆ J_{Φ,M} by the property of J_{Φ,M}. It follows that there is a surjective morphism

Im(π) ≅ L_{Φ,M}/ Ker(π) ⟶ L_{Φ,M}/J_{Φ,M} = 𝕊_{Φ,R^{op}} .

Since Im(π) ⊆ 𝕊_{α}, we see that 𝕊_{Φ,R^{op}} is isomorphic to a subquotient of 𝕊_{α}.

In the proof above, the morphism π is not necessarily surjective, so that 𝕊_{Φ,R^{op}} may not be a quotient of 𝕊_{α}, but only a subquotient. This can be seen by taking the special case 𝕊_{α} = F_{T} and Φ = ∅, as in Example 8.4. In that case, L_{Φ,M} is the constant functor with values k and π(L_{Φ,M}) is the unique constant subfunctor of F_{T}, which is not the whole of F_{T} as soon as |T | ≥ 2. However, this example is slightly misleading, because the constant functor does appear as a quotient of F_{T}, but in a different way.

10. A comparison theorem

Every functor 𝕊_{α} is a quotient of F_{T} which is in turn of the form 𝕊\overline{α} for a suitable \overline{α}, by Example 8.4. It is a natural question to ask more generally if one can compare functors by means of a surjective morphism. We prove here that this is indeed the case under very simple assumptions. The result will be used in an essential way in a future paper, but it is also of independent interest.

10.1. Theorem. Let α_{1} : T → T′_{1}^{op} and α_{2} : T → T′_{2}^{op} be two join-morphisms of finite lattices. Suppose that Φ_{α_{1}} = Φ_{α_{2}} and G_{α_{1}} ⊆ G_{α_{2}}. Then K_{α_{2}} ⊆ K_{α_{1}}, and this induces a surjective morphism 𝕊_{α_{2}} ⟶ 𝕊_{α_{1}}.

Proof : Let X be a finite set. We set Φ = Φ_{α_{1}} = Φ_{α_{2}} and we introduce, as in Section 6,

B_{α_{1},X} = {φ ∈ T^{X} | Φ ⊆ φ(X) ⊆ G_{α_{1}}} ,
B_{α_{2},X} = {φ ∈ T^{X} | Φ ⊆ φ(X) ⊆ G_{α_{2}}} .

We will show that F_{T} (X) = kB_{α_{2},X} + (K_{α_{1}}(X) ∩ K_{α_{2}}(X)) by a method similar to the proof of Theorem 6.1. For simplicity, we write

V := kB_{α_{2},X} + (K_{α_{1}}(X) ∩ K_{α_{2}}(X))

and we aim to prove that V = F_{T} (X). We choose φ : X → T, and we will prove that φ ∈ V by induction on n_{φ} = |φ(X) − G_{α_{2}}|.

If Φ ⊈ φ(X), then φ ∈ K_{α_{1}}(X) by Lemma 9.1, and similarly φ ∈ K_{α_{2}}(X), hence φ ∈ V. So we can assume that Φ ⊆ φ(X). If n_{φ} = 0, then φ(X) ⊆ G_{α_{2}}, so φ ∈ B_{α_{2},X} and φ ∈ V. Thus we assume that n_{φ} ≥ 1.

For i = 1, 2, let θ_{i} = β_{i}^{♯}α_{i}^{♯}, as in Notation 4.6. It follows from the assumption that G_{α_{1}} − Φ ⊆ G_{α_{2}} − Φ, in other words Im(θ_{1}) ⊆ Im(θ_{2}) (see Notation 5.1). Then θ_{2}∘θ_{1} = θ_{1}, as θ_{2} acts as the identity on Im(θ_{2}). For any a ∈ T −G_{α_{2}} ⊆ T −G_{α_{1}}, we have a < θ_{1}(a) by Lemma 4.8 and the fact that Im(θ_{1}) ⊆ G_{α_{1}}. Similarly a < θ_{2}(a). Since θ_{2} is order preserving, we obtain a < θ_{2}(a) ≤ θ_{2}θ_{1}(a) = θ_{1}(a). Applying θ_{1}, it follows that θ_{1}(a) ≤ θ_{1}θ_{2}(a) ≤ θ_{1}(a), hence θ_{1}θ_{2}(a) = θ_{1}(a).

Since n_{φ} ≥ 1, we can choose an element a ∈ φ(X) − G_{α_{2}}. We set b = θ_{2}(a) and c = θ_{1}(a), so that a < b ≤ c and θ_{1}(b) = c. We consider the reduction sequence

a < u_{0} < u_{1} < … < u_{h−1} < b

associated to a for the morphism α_{2} : T → T′_{2}^{op} (see Definition 5.3). Recall that

{a < u_{0} < u_{1} < … < u_{h−1} < b} = {a, b} ⊔ ([a, b] ∩ Φ) ,

by Proposition 4.9. Similarly, we have a ∉ G_{α_{1}} and we can consider the reduction sequence

{a < v_{0} < v_{1} < … < v_{l−1} < c} = {a, c} ⊔ ([a, c] ∩ Φ)

associated to a for the morphism α_{1} : T → T′_{1}^{op}. If b = c, then both reduction sequences coincide. If b < c, then the obvious equality ([a, c]∩Φ)∩[a, b] = [a, b]∩Φ implies that the set {a < u_{0} < u_{1} < … < u_{h−1}} is equal to the intersection with [a, b] of the second reduction sequence. Thus h ≤ l, and u_{i} = v_{i} for 0 ≤ i ≤ h − 1.

Now we claim that b < v_{h} (provided h < l, hence in particular l ≥ 1). In the case h > 0, we have v_{h−1} < v_{h} and both are in Φ. Therefore

α_{2}(v_{h}) < α_{2}(v_{h−1}) = α_{2}β_{2}r^{h−1}α_{2}(a) = r^{h−1}α_{2}(a) ,

hence α_{2}(v_{h}) ≤ rr^{h−1}α_{2}(a) = r^{h}α_{2}(a). The same inequality holds if h = 0 because a < v_{0} implies α_{2}(v_{0}) ≤ α_{2}(a). For any h, recall that α_{2}(b) = r^{h}α_{2}(a) by Proposition 4.9(f). Therefore α_{2}(v_{h}) ≤ α_{2}(b), hence b ≤ β_{2}α_{2}(b) ≤ β_{2}α_{2}(v_{h}) = v_{h}. But b ≠ v_{h} because b ∉ Φ and v_{h} ∈ Φ, so we get b < v_{h}, as claimed.

We have now obtained

a < v_{0} < v_{1} < … < v_{h−1} < b < v_{h} < … < v_{l−1} < c .

Recall that we may have h = 0 (and the first part of the sequence is just a < b) and we may also have h = l (and the second part of the sequence is either b < c or b = c).

First assume that b ∈ G_{α_{1}}, or equivalently b = c (hence in particular h = l). Then both reduction sequences coincide and we write v_{h} = b. By Lemma 5.4, the element

w = φ + ∑_{k=0}^{h}(−1)^{k+1}[a, v_{0}, …, v_{k}]φ

belongs to both K_{α_{1}}(X) and K_{α_{2}}(X), hence w ∈ V. Moreover each function φ_{k} = [a, v_{0}, …, v_{k}]φ satisfies n_{φ_{k}} = n_{φ} − 1 for 0 ≤ k ≤ h, because a ∈ Im(φ) but

a ∉ Im(φ_{k}). So φ_{k} ∈ V by induction, hence φ = w + ∑_{k=0}^{h}(−1)^{k}φ_{k} also belongs to V,

as was to be shown.

From now on, we assume that b ∉ G_{α_{1}}, that is, b < c. With the notation of Lemma 5.4, we define

φ_{k} = [a, v_{0}, …, v_{k}]φ (0 ≤ k ≤ l − 1)
φ′ = [a, v_{0}, …, v_{h−1}, b]φ
φ_{l} = [a, v_{0}, …, v_{l−1}, c]φ

Using the reduction sequence a < v_{0} < … < v_{h−1} < b for the morphism α_{2}, we see that the element

(10.2)  w := φ + ∑_{k=0}^{h−1}(−1)^{k+1}φ_{k} + (−1)^{h+1}φ′

belongs to K_{α_{2}}(X), by Lemma 5.4. Our main goal is to prove that it also belongs to K_{α_{1}}(X).

Since c = θ_{1}(b), the sequence b < v_{h} < … < v_{l−1} < c is a reduction sequence for the morphism α_{1} and we set v_{l} = c for convenience. By Lemma 5.4, we see that

(10.3) for any map ψ ∈ T^{X} , ψ + ∑_{i=h}^{l}(−1)^{i−h+1}[b, v_{h}, …, v_{i}]ψ ∈ K_{α_{1}}(X) .

We first apply (10.3) to each function φ_{k} and take the alternating sum over k, for h ≤ k ≤ l. We obtain that the expression

(10.4) ∑_{k=h}^{l}(−1)^{k}φ_{k} − ∑_{k=h}^{l}(−1)^{k}[b, v_{h}]φ_{k} + ∑_{k=h}^{l} ∑_{i=h+1}^{l}(−1)^{k+i−h+1}[b, v_{h}, …, v_{i}]φ_{k}

belongs to K_{α_{1}}(X). We separate the first two sums on purpose, because we need to analyse the remaining double sum. This double sum runs over the rectangle

P = {(k, i) | h ≤ k ≤ l , h + 1 ≤ i ≤ l}

of size m × (m − 1), where m = l − h + 1. We can decompose P as the disjoint union of the two subsets

P_{+} = {(k, i) ∈ P | k < i}  and  P_{−} = {(k, i) ∈ P | k ≥ i} .

It is elementary to check that the map (k, i) ↦ (i, k + 1) is a bijection between P_{+} and P_{−} with inverse (r, s) ↦ (s − 1, r). We now show that, for any (k, i) ∈ P_{+}, the map [b, v_{h}, …, v_{i}]φ_{k}, indexed by (k, i), is equal to the map [b, v_{h}, …, v_{k+1}]φ_{i}, indexed by (i, k + 1). In view of the definition of φ_{k}, we must prove that

[b, v_{h}, …, v_{i}][a, v_{0}, …, v_{k}] = [b, v_{h}, …, v_{k+1}][a, v_{0}, …, v_{i}] .

But this is easy since both maps have the following effect (setting v_{−1} = a for convenience) :

v_{r} ↦ v_{r+1}  if − 1 ≤ r ≤ h − 2
v_{r} ↦ v_{r+2}  if h − 1 ≤ r ≤ k − 1
v_{r} ↦ v_{r+1}  if k ≤ r ≤ i − 1
v_{r} ↦ v_{r}  if i ≤ r ≤ l
b ↦ v_{h}
t ↦ t  otherwise.

In the double sum appearing in (10.4), opposite signs are assigned to the two maps, so the pair vanishes. This applies to all pairs and therefore the whole double sum is zero. It follows that (10.4) reduces to

(10.5)  ∑_{k=h}^{l}(−1)^{k}φ_{k} − ∑_{k=h}^{l}(−1)^{k}[b, v_{h}]φ_{k} ∈ K_{α_{1}}(X) .

We now apply (10.3) to the function φ′ = [a, v_{0}, …, v_{h−1}, b]φ and we get

(10.6)  φ′ + ∑_{k=h}^{l}(−1)^{k−h+1}[b, v_{h}, …, v_{k}][a, v_{0}, …, v_{h−1}, b]φ ∈ K_{α_{1}}(X) .

But it is elementary to check that

[b, v_{h}, …, v_{k}][a, v_{0}, …, v_{h−1}, b]φ = [b, v_{h}][a, v_{0}, …, v_{k}]φ = [b, v_{h}]φ_{k} .

So if we multiply (10.6) by (−1)^{h−1} and add it to (10.5), all the functions [b, v_{h}]φ_{k} cancel and we obtain

(10.7)  (−1)^{h−1}φ′ + ∑_{k=h}^{l}(−1)^{k}φ_{k} ∈ K_{α_{1}}(X) .

Next we use the long reduction sequence a < v_{0} < … < v_{h} < v_{h+1} < … < v_{l−1} < c for the morphism α_{1} and we set v_{l} = c for convenience. By Lemma 5.4, we have

φ + ∑_{k=0}^{l}(−1)^{k+1}φ_{k} ∈ K_{α_{1}}(X)

and if we add this to (10.7), all the terms with indices k ≥ h cancel and we are left with

w = φ + ∑_{k=0}^{h−1}(−1)^{k+1}φ_{k} + (−1)^{h−1}φ′ ∈ K_{α_{1}}(X) .

But this is precisely the element w defined in (10.2), which also belongs to K_{α_{2}}(X). Therefore w ∈ K_{α_{1}}(X) ∩ K_{α_{2}}(X), hence w ∈ V.

We then proceed as we did earlier in the case b = c. We have n_{φ_{k}} = n_{φ} − 1 for 0 ≤ k ≤ h − 1, and n_{φ′} = n_{φ} − 1 as well. So φ_{k}, φ′ ∈ V by induction, hence

φ = w + ∑_{k=0}^{h−1}(−1)^{k}φ_{k} + (−1)^{h}φ′ ∈ V .

This completes the proof of the equality F_{T} (X) = kB_{α_{2},X} + (K_{α_{1}}(X) ∩ K_{α_{2}}(X)). Finally, we can finish the proof of Theorem 10.1. We have

K_{α_{1}}(X) ∩ K_{α_{2}}(X) ⊆ K_{α_{2}}(X) ⊆ kB_{α_{2},X} + (K_{α_{1}}(X) ∩ K_{α_{2}}(X)) .

It follows that

K_{α_{2}}(X) = (K_{α_{1}}(X) ∩ K_{α_{2}}(X)) + (kB_{α_{2},X} ∩ K_{α_{2}}(X)) ,

hence K_{α_{2}}(X) = K_{α_{1}}(X) ∩ K_{α_{2}}(X) since kB_{α_{2},X} ∩ K_{α_{2}}(X) = {0} by Theorem 6.1. Thus K_{α_{2}}(X) ⊆ K_{α_{1}}(X) and the proof is complete.

11. The structure of the poset G_{α}

Given a join-morphism α : T → T′^{op} of finite lattices, we have defined the subset G_{α} ⊆ T, which is used in Section 6 for the description of a basis of each evaluation 𝕊_{α}(X). Dually, G′_{α} is a subset of T′, used similarly for a description of a basis of each evaluation 𝕊′_{α}(X). Note that 𝕊′_{α} is isomorphic to the dual 𝕊_{α}^{♯}, by Proposition 6.9, but this does not tell us directly how G_{α} and G′_{α} are related. The purpose of this section is to show that G_{α} and G′_{α}, viewed as full subposets of T and T′ respectively, are actually anti-isomorphic.

We know from Lemma 4.11(a) that α^{♯} restricts to an anti-isomorphism of posets from Im(θ) to Im(θ′). Since G_{α} − Φ_{α} = Im(θ), we see that we now have two poset anti-isomorphisms

α^{♯} : G_{α} − Φ_{α} ⟶ G′_{α} − Φ′_{α}  and  α : Φ_{α} ⟶ Φ′_{α} .

The disjoint union of the two maps yields a bijection G_{α} → G′_{α}, but unfortunately, this bijection is not an anti-isomorphism. Our final theorem shows that the correct anti-isomorphism is more subtle. We start with a lemma.

11.1. Lemma. Let α : T → T′^{op} be a join-morphism of finite lattices, let β = α^{op},

and let Z_{α} := {u ∈ Φ_{α} | ρ(u) ∈ G_{α} and u ≤ ωρ(u)}. Then Z_{α} = ⨆_{t∈Im(θ)}]t, ω(t)].

Proof : If u ∈ Z_{α}, then t = ρ(u) ∈ G_{α} − Φ_{α} = Im(θ), and t < u ≤ ω(t) by the definition of Z_{α}. Thus u ∈ ]t, ω(t)]. Conversely, if u ∈]t, ω(t)] for some t ∈ Im(θ), then u ∈ Φ_{α} because ]t, ω(t)] ⊆ Φ_{α} by Lemma 4.8. Moreover t = ρ(u) and ω(t) = ω(u) by Lemma 4.11. This shows that u ∈ Z_{α}. Moreover, we see that t and ω(t) are determined by u, so that the sets ]t, ω(t)] are disjoint (possibly empty) when t runs over Im(θ).

Note that ]t, ω(t)] is empty if t = ω(t), so the disjoint union actually runs over the subset G̊ = {t ∈ Im(θ) | t < ω(t)}, which already appeared in the proof of Theorem 6.1.

11.2. Theorem. Let α : T → T′^{op} be a join-morphism of finite lattices, let β = α^{op}, and let Z_{α} be as above. Let λ_{α} : G_{α} → T′ be the map defined by

λ_{α}(u) = \{ \begin{matrix}α(u) & if u ∈ G_{α} − Z_{α} , \\ rα(u) & if u ∈ Z_{α} . \end{matrix}

Then λ_{α}(G_{α}) = G′_{α} and λ_{α} : G_{α} ⟶ G′_{α} is an anti-isomorphism of posets, with inverse λ_{β} : G_{β} = G′_{α} ⟶ G′_{β} = G_{α}.

Proof : We first prove that λ_{α}(G_{α}) ⊆ G′_{α}. Let u ∈ G_{α}. If u ∉ Z_{α}, then λ_{α}(u) = α(u). But we know that α(T) ⊆ G′_{α} by Lemma 5.2, so λ_{α}(u) ∈ G′_{α} in this case. If u ∈ Z_{α}, we let t = ρ(u) ∈ G_{α} − Φ_{α}, and t′ = α^{♯}(t). In this case λ_{α}(u) = rα(u). Moreover t < u ≤ ω(t) and, by Lemma 4.11, we deduce that t′ < α(u) ≤ α(t). If rα(u) ∈ Φ′_{α}, then rα(u) ∈ G′_{α}, that is, λ_{α}(u) ∈ G′_{α} and we are done. Otherwise rα(u) ∉ Φ′_{α}, hence rα(u) = α^{♯}(u) = α^{♯}(t) = t′ by the definition of α^{♯}. Then θ′(rα(u)) = α^{♯}β^{♯}α^{♯}(t) = α^{♯}(t) by Lemma 4.8, since t ∉ Φ_{α}. Thus λ_{α}(u) = rα(u) = α^{♯}(t) ∈ Im(θ′) ⊆ G′_{α}.

We show next that λ_{α} is order-reversing. For this, we consider elements u < v in G_{α}, and we want to show that λ_{α}(u) ≥ λ_{α}(v). The first 3 cases are easy :

• If u ∉ Z_{α} and v ∉ Z_{α}, then λ_{α}(u) = α(u) ≥ α(v) = λ_{α}(v).
• If u ∉ Z_{α} and v ∈ Z_{α}, then λ_{α}(u) = α(u) ≥ α(v) > rα(v) = λ_{α}(v).
• If u ∈ Z_{α} and v ∈ Z_{α}, then λ_{α}(u) = rα(u) ≥ rα(v) = λ_{α}(v).

In the fourth case, we have u ∈ Z_{α} and v ∉ Z_{α}, hence λ_{α}(u) = rα(u) and λ_{α}(v) = α(v). We set t = ρ(u) and observe that we still have α(u) ≥ α(v). Assume that α(u) = α(v). If v ∈ Φ_{α}, then u = v by Lemma 3.6, contradicting the assumption u < v. Thus v ∈ G_{α} − Φ_{α} = Im(θ). Since u ∈ Z_{α}, Lemma 11.1 implies that u ∈ ]t, ω(t)] where t = ρ(u) ∈ Im(θ). By Lemma 4.11, α induces an anti-isomorphism between ]t, ω(t)] and ]t′, ω′(t′)], where t′ = α^{♯}(t) and ω′(t′) = α(t). We deduce that α(v) = α(u) ∈]α^{♯}(t), α(t)], hence α^{♯}(v) = α^{♯}(t) because α^{♯}(v) = ρ′α(v) = t′ by Lemma 4.11 again. Since v, t ∈ Im(θ), they are fixed under θ, by Lemma 4.8, and therefore

v = θ(v) = β^{♯}α^{♯}(v) = β^{♯}α^{♯}(t) = θ(t) = t ,

hence v = t < u, contradicting the assumption u < v. This contradiction shows that α(u) ≠ α(v), hence α(u) > α(v), and it follows that λ_{α}(u) = rα(u) ≥ α(v) = λ_{α}(v).

Our next step is to show that λ_{β}λ_{α} = id_{G_{α}}. We have

G_{α} = (G_{α} − Φ_{α}) ⊔ (Φ_{α} − Z_{α}) ⊔ Z_{α}

and we consider successively an element in each of those 3 subsets. We start with t ∈ G_{α} − Φ_{α}, that is, t = θ(t). Applying Proposition 4.9, we see that only cases (a) or (d) of that Proposition can occur, because either t < θ(t) or θ(t) < t holds in the other cases. In case (a), we have t = θ(t) = βα(t) ∉ Φ_{α} and α(t) ∉ Φ′_{α}, hence t ∉ Z_{α} and α(t) ∉ Z′_{α}, where

Z′_{α} := {u ∈ Φ′_{α} | ρ′(u) ∈ G′_{α} and u ≤ ω′ρ′(u)} .

Thus we get λ_{β}λ_{α}(t) = λ_{β} α(t) = βα(t) = t. In case (d), we have t ∉ Φ_{α} and

t = θ(t) < v_{0} < … < v_{l−1} = ω(t) , where v_{i} = βr^{i}α(t) ∈ Φ_{α} ,

and l ≥ 1. By Lemma 4.11(c), ]t, ω(t)] is anti-isomorphic to ]t′, ω′(t′)], which is contained in Z′_{α} by Lemma 11.1. In particular α(t) = ω′(t′) ∈ Z′_{α}, while t ∉ Z_{α}, so we obtain

λ_{β}λ_{α}(t) = λ_{β} α(t) = rβα(t) = r(v_{0}) = t ,

because v_{0} is the least element of the totally ordered interval ]t, ω(t)], by Lemma 4.8, and so r(v_{0}) = t.

We consider now our second subset and take t ∈ Φ_{α} − Z_{α}. We claim that α(t) ∉ Z′_{α}. If not, then, by Lemma 11.1, we would have α(t) ∈]s′, ω′(s′)], where s′ = ρ′α(t) = α^{♯}(t) and s′ ∈ Im(θ′). By Lemma 4.11, β induces an anti-isomorphism between ]s′, ω′(s′)] and ]s, ω(s)], where s = β^{♯}(s′) ∈ Im(θ). Therefore we would obtain βα(t) ∈]s, ω(s)], hence βα(t) ∈ Z_{α}. But βα(t) = t because t ∈ Φ_{α}. Since we have chosen t ∉ Z_{α}, this proves the claim. Now, the definition of λ_{β} implies that λ_{β}λ_{α}(t) = λ_{β} α(t) = βα(t) = t.

Finally, for our third subset, we take u ∈ Z_{α} and we let t = ρ(u) and t′ = α^{♯}(t), so that u ∈]t, ω(t)]. By Lemma 4.11 again, α induces an anti-isomorphism ]t, ω(t)] → ]t′, ω′(t′)]. We have λ_{α}(u) = rα(u) ∈ [t′, ω′(t′)], and there are two cases. If rα(u) = t′, then rα(u) ∉ Z′_{α} and so λ_{β}λ_{α}(u) = βrα(u) = β(t′) = ω(t). But since rα(u) = t′, the element α(u) is the smallest element of the totally ordered interval ]t′, ω′(t′)], so that u is the top element of ]t, ω(t)], that is, u = ω(t). Hence λ_{β}λ_{α}(u) = u in this case. In the other case, we have v := rα(u) > t′, hence v ∈]t′, ω′(t′)]. Then v and α(u) are adjacent in this totally ordered interval. Since the inverse anti-isomorphism ]t′, ω′(t′)] →]t, ω(t)] is induced by β, the elements u and β(v) are adjacent in the totally ordered interval ]t, ω(t)], that is, u = rβ(v). It follows that

λ_{β}λ_{α}(u) = λ_{β} rα(u) = λ_{β}(v) = rβ(v) = u .

This completes the proof that λ_{β}λ_{α} = id_{G_{α}}.

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.

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

[BT5] S. Bouc, J. Thévenaz. Tensor product of correspondence functors, J. Algebra 558 (2020), 146–175.

[BT6] S. Bouc, J. Thévenaz. Simple and projective correspondence functors, Representation Theory 25 (2021), 224–264.

[FT] Lectures on functor homology, Lectures from the conference held in Nantes, April 2012, V. Franjou, A. Touzé (eds.), Progress in Mathematics 311, Birkhäuser/Springer, Cham, 2015.

[NSS] R. Nagpal, S.V. Sam, A. Snowden. Regularity of FI-modules and local cohomology, Proc. Amer. Math. Soc. 146 (2018), 4117–4126.

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

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

[SW] E.H. Spanier, J.H.C. Whitehead. Duality in relative homotopy theory, Ann. of Math. (2) 67 (1958), 203–238.

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

[We2] P. Webb. Sets with a category action, Oberwolfach Reports 7, Issue 3, (2010), 1940–1945. DOI: 10.4171/OWR/2010/32.

[Wh] J.H.C. Whitehead. Duality between CW-lattices, 1958 Symposium Internacional de Topología Algebraica, pp. 248–258, Universidad Nacional Autónoma de México and UNESCO, Mexico City.

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