Correspondence functors

Serge Bouc

Abstract: This is a report on some recent joint work with Jacques Thévenaz, which appears in [1] and [2]. It is an expanded version of a talk given at the RIMS workshop Cohomology of finite groups and related topics, February 18-20, 2015.

The first part of this joint work is presented in Thévenaz’s report, in these proceedings.

1. Introduction

1.1. This is an exposition of a joint work in progress with Jacques Thévenaz^{1}, on the representation theory of finite sets, by which we mean the following: let C denote the category in which objects are finite sets. For any two finite sets X and Y, the set of morphisms from X to Y in C is the set of all correspondences from X to Y, i.e. the set of subsets of Y × X. We denote^{2} this set by C(Y, X). A correspondence from X to itself is called a relation on X. The composition of correspondences is defined as follows: for finite sets X, Y, Z, for R ⊆ Y × X and S ⊆ Z × Y

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

The identity morphism of the finite set X is the diagonal

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

We now fix a commutative ring k (with identity element 1), and we consider functors from C to the category k-Mod of k-modules. Equivalently, we first introduce the k-linearization kC of C, i.e. the category with the same objects as C, but in which the set of morphisms from X to Y is the free k-module kC(Y, X) on the set C(Y, X), and composition is k-linearly extended from composition in C. Then we consider correspondence functors over k, i.e. k-linear functors from kC to k-Mod. These functors are the objects of a category F_{k}, in which morphisms are natural transformations of functors. The category F_{k} is an abelian k-linear category.

1cf. Jacques Thévenaz’s report in these Proceedings.

2We emphasize that our notation is opposite to the usual notation C(X, Y) of category theory.

1.2. Examples : For any finite set E, the representable functor Y_{E,k} sending a finite set X to the set Hom_{kC}(E, X) = kC(X, E) is a projective object of F_{k}, by the Yoneda Lemma. In particular:

• When E = ∅, then Y_{E,k}(X) ≅ k for any finite set X, and for any correspondence U ⊆ Y ×X from X to a finite set Y, the map Y_{E,k}(U) : Y_{E,k}(X) → Y_{E,k}(Y) is the identity map of k. In other words, the functor Y_{∅,k} is the constant functor equal to k everywhere.

• When E = • is a set of cardinality one, then for any finite set X, the module Y_{E,k}(X) is the free k-module with basis the set 2^{X} of subsets of X. Hence Y_{•,k} is the functor of subsets.

• The Yoneda Lemma implies that End_{F_{k}}(Y_{E,k}) is isomorphic to the algebra kC(E, E) of all relations on E. In particular, when R is a preorder on E, i.e. R is a reflexive and transitive relation on E, or equivalently Δ_{E} ⊆ R = R^{2}, then we get a direct summand Y_{E,k}R of Y_{E,k} defined on a finite set X by Y_{E,k}R(X) = kC(X, E)R. The functor Y_{E,k}R is a projective object of F_{k}.

2. Functors associated to lattices

2.1. The previous examples are special cases of a more general construction that we now introduce. Recall that a lattice T = (T, ∨, ∧) is a poset in which any pair {x, y} of elements has an least upper bound x ∨ y (called the join of x and y) and a greatest lower bound x ∧ y (called the meet of x and y). A finite lattice T admits a smallest element 0_{T} (the meet of all elements of T) and a largest element 1_{T} (the join of all elements of T).

2.2. Definition : Let T be a finite lattice.

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

• When U ⊆ Y × X is a correspondence from X to a finite set Y, let F_{T} (U) : F_{T} (X) → F_{T} (Y) be the k-linear map sending φ : X → T to the map F_{T} (U)(φ) : Y → T, also denoted by Uφ, defined by

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

Recall that a lattice T is called distributive if ∨ is distributive with respect to ∧ or, equivalently, if ∧ is distributive with respect to ∨.

2.3. Theorem : Let T be a finite lattice. Then F_{T} is a correspondence functor. Moreover F_{T} is projective in F_{k} if and only if T is distributive.

This result motivates the following definition:

2.4. Definition : Let kL denote the following category:

• The objects of kL are the finite lattices.

• For two finite lattices T and T′, the set of morphisms from T to T′ in kL is the free k-module with basis the set of all maps f : T → T′ which respect the join operation, i.e. such that

∀A ⊆ T, f(⋁_{t∈A} t) = ⋁_{t∈A} f(t) .

• The composition of morphisms in kL is the k-linear extension of the composition of maps.

2.5. Remark : Note that a map from a finite lattice T to a finite lattice T′ which respects the join operation need not respect the meet operation. On the other hand, it has to send the smallest element 0_{T} of T (which is equal to the join ⋁_{t∈∅} t) to the smallest element 0_{T′} of T′.

2.6. Theorem : The assignment T ↦ F_{T} is a fully faithful k-linear functor from kL to F_{k}.

2.7. We will conclude this section by introducing a canonical subfunctor H_{T} of F_{T}, for any finite lattice T, which will be fundamental in the explicit description of simple correspondence functors.

First recall that an element e of a finite lattice T is called irreducible if for any subset A of T, the equality e = ⋁_{t∈A} t implies that e ∈ A. In other

words e ≠ 0_{T}, and if e = x ∨ y for x, y ∈ T, then e = x or e = y. We denote by Irr(T) the set of irreducible elements of T, viewed as a full subposet of T.

2.8. Definition : Let T be a finite lattice. For a finite set X, let H_{T} (X) denote the k-submodule of F_{T} (X) = k(T^{X}) generated by all maps φ : X → T such that φ(X) ⊉ Irr(T).

2.9. Lemma :

1. Let Y, X be finite sets, let U ∈ C(Y, X), and let φ : X → T. Then

(Uφ)(Y) ∩ Irr(T) ⊆ φ(X) ∩ Irr(T).

2. The assignment X ↦ H_{T} (X) is a subfunctor of F_{T}.

Proof : Let U ∈ C(Y, X), let φ : X → T, let e ∈ (Uφ)(Y) ∩ Irr(T), and y ∈ Y such that e = (Uφ)(y). Then e = ⋁_{(y,x)∈U} φ(x), so there exists x such

that (y, x) ∈ U and e = φ(x). Hence e ∈ φ(X) ∩ Irr(T), proving Assertion 1. Assertion 2 follows trivially.

3. Simple functors

3.1. Let S be a simple object of F_{k}, that is, a correspondence functor admitting exactly two subfunctors. Then S is non zero, so there is a set E of minimal cardinality such that S(E) ≠ {0}. As explained in Jacques Thévenaz’s report in these proceedings, the evaluation S(E) is a simple module for the algebra E_{E} of essential relations on E, defined by

E_{E} = kC(E, E)/ ∑_{|F |<|E|} kC(E, F)C(F, E) .

It follows from [1] that the simple E_{E} modules (up to isomorphism) are parametrized by pairs (R, W) of a partial order R on E and a simple kAut(E, R)- module W (up to permutation of E), where Aut(E, R) is the automorphism group of the pair (E, R), i.e. the group of permutations of E which preserve R.

Conversely, if E is a finite set, if R is a partial order on E, and if W is a simple kAut(E, R)-module, then there is a unique simple correspondence functor S = S_{E,R,W} such that E is minimal with S(E) ≠ {0} and S(E) ≅ W as E_{E}-modules. This gives the following:

3.2. Theorem : The simple correspondence functors over k (up to isomorphism) are parametrized by triples (E, R, W) consisting of a finite set E, a partial order R on E, and a simple kAut(E, R)-module W (up to identification of triples (E, R, W) and (E′, R′, W′) for which there exists an isomorphism of posets φ : (E, R) → (E′, R′) sending W to W′).

3.3. Examples : Assume that k is a field.

• The representable functor Y_{∅,k} (see 1.2) is simple, projective, and injective in F_{k}. The corresponding triple is (∅, tot, k), where tot is the unique (order) relation on ∅, and k is the unique simple module for kAut(∅, tot) ≅ k.

• The representable functor Y_{•,k} is not simple, but one can show that it is isomorphic to the direct sum of the previous one Y_{∅,k} and the simple functor S_{•,tot,k}, where tot is the unique order relation on the set •, and k is the unique simple module for kAut(•, tot) ≅ k. This functor S_{•,tot,k} is also simple, projective ans injective in F_{k}.

3.4. The two previous examples deal with a total order on a set of cardinality 0 and 1. We now consider the general case of a total order.

For this, we chose a non negative integer n, and we denote by \underline{n} the totally ordered set \{0, 1, …, n\}. Then \underline{n} is a lattice, in which x ∨ y = Max(x, y) and x ∧ y = Min(x, y). We denote by [n] the set Irr(T). Clearly [n] = \underline{n} − \{0\} = {1, 2, …, n}.

3.5. Theorem : For n ∈ ℕ, set 𝕊_{[n]} = F\underline{n}/H\underline{n}. Then:

1. The surjection F\underline{n} → 𝕊_{[n]} splits. The functor 𝕊_{[n]} is projective.

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

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

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

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

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

3.6. In order to deal with the general case of simple functors, we need to introduce some notation. We start with a finite poset (E, R), and we first choose a finite lattice T with the following two properties:

(1) The poset Irr(T) is isomorphic to (E, R).

(2) The natural restriction map Aut(T) → Aut(E, R) is an isomorphism.

Using Condition (1), we will identify (E, R) with the subposet Irr(T) of T. In Condition (2), we denote by Aut(T) the group of automorphisms of the poset T (one can show that this is equal to the group of bijections of T which respect the join operation - see Definition 2.4). An automorphism of T clearly maps an irreducible element to an irreducible element, so we have a restriction map Aut(T) → Aut(Irr(T)). This map is injective, because any element t of T is equal to the join ⋁_{{e∈Irr(t) \atop e≤_{T} t}} e of those irreducible elements smaller that t

in T, thus any automorphism of T is determined by its restriction to Irr(T). So Condition (2) above amounts to requiring that any automorphism of the poset (E, R) can be extended to an automorphism of T.

The poset (E, R) being given, it is always possible to choose a finite lattice T with the above two properties, e.g. the lattice I_{↓}(E, R) consisting of lower ideals of (E, R) (i.e. subsets A of E such that (x, y) ∈ R and y ∈ A implies x ∈ A, for any x, y ∈ E), ordered by inclusion of subsets (the join operation on I_{↓}(E, R) is union of subsets, and the meet operation is intersection of subsets). 3.7. When T is a finite poset, and t ∈ T, we set

r(t) = ⋁_{{x∈T \atop x<_{T} t}} x .

Thus r(t) = t if t ∉ Irr(T), and if t ∈ Irr(T), then r(t) is the largest element of T strictly smaller than t.

When A ⊆ T, we denote by γ_{A} : E → T the map defined by

∀e ∈ E, γ_{A}(e) = \{ \begin{matrix}e & if e ∉ A \\ r(e) & if e ∈ A \end{matrix} .

We define moreover an element γ of k(T^{E}) by

γ = ∑_{A⊆E}(−1)^{|A|}γ_{A} ,

and we view k(T^{E}) as the evaluation at E of the functor F_{T^{op}}, where T^{op} is the opposite lattice to T (i.e. the lattice obtained by replacing the order relation on T by its opposite, or equivalently, by switching the join and meet operations of T).

Finally we denote by 𝕊_{E,R} the subfunctor of F_{T^{op}} generated by the element γ of F_{T^{op}}(E), i.e. the intersection of all subfunctors M of F_{T^{op}} such that γ ∈ M(E).

3.8. Theorem :

1. The functor 𝕊_{E,R} doesn’t depend on the choice of T, up to isomorphism.

2. There exists a positive integer f = f_{E,R} (explicitly computable) such that, for any finite set X, the k-module 𝕊_{E,R}(X) is free of rank

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

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

3. Let W be a kAut(E, R)-module. For a finite set X, define

𝕊_{E,R,W} (X) = 𝕊_{E,R}(X) ⊗_{kAut(E,R)} W .

Then the assignment X ↦ 𝕊_{E,R,W} (X) is a correspondence functor.

4. If k is a field and W is simple, then 𝕊_{E,R,W} ≅ S_{E,R,W}.

Proof : (Sketch) • First we introduce a non-degenerate functorial bilinear pairing F_{T} ×F_{T^{op}} → k, in the following way: if X is a finite set, if φ : X → T and ψ : X → T^{op}, we set

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

This pairing is functorial in the sense that for any correspondence U ⊆ Y ×X from X to a finite set Y, for any φ : X → Y and any ψ : Y → T^{op}, we have that

(Uφ, ψ)_{Y} = (φ, U^{op} ⋆ ψ)_{X} ,

where U^{op} = {(x, y) ∈ X × Y | (y, x) ∈ U} denotes the opposite correspondence, and U^{op} ⋆ ψ = F_{T^{op}}(U^{op})(ψ) ∈ F_{T^{op}}(X) is the image of ψ under U^{op}.

This pairing is non degenerate in the strong sense that it induces an isomorphism between F_{T} (X) and the k-dual of F_{T^{op}}(X), for any finite set X (so it induecs an isomorphism between F_{T^{op}} and the dual functor (F_{T})^{♮}).

• We show that there exists a surjective homomorphism of correspondence functors

Θ_{T} : F_{T} /H_{T} → 𝕊_{E,R^{op}} ,

where R^{op} is the opposite partial order to R on E.

• We define a subset G of T, containing E, and invariant under Aut(E, R), with the property that for any finite set X, the image under Θ_{T,X} ∘ π_{T,X} of the set

{φ : X → T | E ⊆ φ(X) ⊆ G}

of elements of F_{T} (X) is a k-basis of 𝕊_{E,R^{op}}(X), where π_{T} : F_{T} → F_{T} /H_{T} is the quotient morphism. Then the integer f = f_{E,R} appearing in Theorem 3.8 is equal to |G| − |E|.

3.9. Corollary : Let k be a field. Let (E, R) be a finite poset, and W be a simple kAut(E, R)-module. Then for any finite set X,

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

4. Examples

4.1. Let D denote the following lattice:

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

where the white dots are the irreducible elements. Then over a field of odd characteristic, the functor F_{D} is semisimple: its splits as

F_{D} ≅ 𝕊_{[0]} ⊕ 4𝕊_{[1]} ⊕ 4𝕊_{[2]} ⊕ 𝕊_{[3]} ⊕ 2𝕊_{_{•} _{•}} ⊕ 𝕊_{•} _{•}^{•} ,

where 𝕊_{_{•} _{•}} denotes the functor 𝕊_{E,Δ} for a set E of cardinality 2, ordered by the equality relation, and 𝕊_{•} _{•}^{•} is the functor 𝕊_{F,R} associated to a poset (F, R)

of cardinality 3 with 2 connected components.

Observe that for any i ∈ ℕ, the multiplicity of the functor 𝕊_{[i]} as a summand of F_{D} is equal to the number of increasing sequences

0_{D} = x_{0} < x_{1} < … < x_{i}

in D. This statement holds more generally for an abitrary finite lattice T. 4.2. There are 16 posets up to isomorphism on a set of cardinality 4. The following table displays the Hasse diagrams of these posets, together with the corresponding value of the integer f appearing in Theorem 3.8:

[figure: • • • •; • • • •; •; •; •; •; •; •; •; •; f = 2  f = 2  f = 2  f = 2; •; •; •; •; • • • •; •; •; •; •; •; •; •; •; f = 2  f = 2  f = 2  f = 2; •; •; •; •; •; •; •; •; • • • •; •; •; •; •; f = 3  f = 2  f = 2  f = 2; \begin{matrix}• \\ • \\ • \\ • \end{matrix}; •; •; •; •; •; •; •; •; •; •; •; •; f = 1  f = 2  f = 2  f = 2]

The only poset for which f = 1 is the total order. This is a general phenomenon: if (E, R) is a finite poset, then f_{E,R} = 1 if and only if R is a total order.

Acknowledgements: I wish to thank Professor Fumihito Oda for his invitation, and Kinki University, Osaka for support. I also thank Professor Akihiko Hida for the opportunity of giving a talk at the RIMS workshop Cohomology of finite groups and related topics, February 18-20, 2015.

References

[1] S. Bouc and J. Thévenaz. The algebra of essential relations on a finite set. to appear in J. reine angew. Math., 2013.

[2] S. Bouc and J. Thévenaz. The representation theory of finite sets and correspondences. In preparation, 2015.

Serge Bouc, CNRS-LAMFA, 33 rue St Leu, 80039 Amiens Cedex 01, France.

email:  serge.bouc@u-picardie.fr