The Hecke Bicategory

Abstract

We present an application of the program of groupoidification leading up to a sketch of a categorification of the Hecke algebroid—the category of permutation representations of a finite group. As an immediate consequence, we obtain a categorification of the Hecke algebra. We suggest an explicit connection to new higher isomorphisms arising from incidence geometries, which are solutions of the Zamolodchikov tetrahedron equation. This paper is expository in style and is meant as a companion to Higher Dimensional Algebra VII: Groupoidification and an exploration of structures arising in the work in progress, Higher Dimensional Algebra VIII: The Hecke Bicategory, which introduces the Hecke bicategory in detail.

1. Introduction

Categorification is, in part, the attempt to shed new light on familiar mathematical notions by replacing a set-theoretic interpretation with a category-theoretic analogue. Loosely speaking, categorification replaces sets, or more generally n-categories, with categories, or more generally (n + 1)-categories, and functions with functors. By replacing interesting equations by isomorphisms, or more generally equivalences, this process often brings to light a new layer of structure previously hidden from view. While categorification is not a systematic process—in other words, finding this new layer of structure may require a certain amount of creativity—the reverse process of decategorification should be a systematic way of recovering the original set-theoretic structure or concept. The key idea is that considering a process of categorification requires, as a first step, a definition of the corresponding decategorification process. We then think of categorification simply as a heuristic tool allowing us to “undo” the process of decategorification.

In Higher Dimensional Algebra VII: Groupoidification [1], Baez, Walker and the author introduced a program called groupoidification initiated by Baez, Dolan and Trimble, and aimed at categorifying various notions from linear algebra, representation theory and mathematical physics. The very simple idea was that one could replace vector spaces by groupoids, i.e., categories with only isomorphisms, and replace linear operators by spans of groupoids. In fact, what we really did was define a systematic process called degroupoidification:

$$\begin{array}{c}\mathrm{groupoids}\mapsto \mathrm{vector}\mathrm{spaces}\\ \mathrm{spans}\mathrm{of}\mathrm{groupoids}\mapsto \mathrm{matrices}\end{array}$$

Thus, groupoidification is a form of categorification. We then suggested some applications of groupoidification to Hall algebras, Hecke algebras, and Feynman diagrams, so that other researchers could begin to categorify their favorite notions from representation theory.

In this paper, we give an expository account of a theory of categorified intertwining operators or categorified Hecke operators for representations of a very basic type: the permutation representations of a finite group. Following the description of categorification above, this suggests the study of a 2-dimensional category-theoretic structure and a decategorification functor. We describe this 2-dimensional structure, which we call the Hecke bicategory, in Section 4.1. Pairing the Hecke bicategory with the degroupoidification functor we are then able to state a categorification theorem as Claim 8.

The statements of the main results are as follows. For each finite group G, there is an equivalence of categories, or more precisely algebroids, between the category of permutation representations of G—the Hecke algebroid of Hecke operators—and the degroupoidification of the Hecke bicategory of categorified Hecke operators, which has G-sets as objects and is enriched over the monoidal bicategory of spans of groupoids. In other words, the Hecke bicategory categorifies the category of permutation representations. When G is the simple Lie group over a finite field of q elements attached to a Dynkin diagram, then one can choose a Borel subgroup B, and construct the G-set X = G/B, known as the flag complex. The choice of one object X in Hecke(G) yields a groupoid Hecke(G)(X,X) and a span called composition. The groupoid Hecke(G)(X,X) and accompanying span categorify the usual Hecke algebra for the chosen Dynkin diagram and prime power q.

The term “Hecke algebra” is seen in several areas of mathematics. The Hecke algebras we consider, the Iwahori–Hecke algebras, are one-parameter deformations of the group algebras of Coxeter groups. In the theory of modular forms, or more generally, automorphic representations, Hecke algebras are commutative algebras of Hecke operators. These operators can be expressed by means of double cosets in the modular group, or more generally, with respect to certain compact subgroups. Here we use the term “Hecke operator” to highlight the relationship between the intertwining operators between permutation representations of a finite group and the Hecke operators acting on the modular group. We discuss an example of Hecke operators in terms of “flag-flag relations" in the setting of Coxeter groups in Section 6.2. To describe Hecke algebras, one may use relations between varieties of the form G/H for various subgroups H, namely the discrete subgroups, or more generally, the compact subgroups. So, we think of Hecke algebras as algebras of “Hecke operators" in a slightly generalized sense. We are changing the groups, and making them finite, so that instead of varieties G/H, we have certain finite sets G/H. Thus we think of a Hecke algebra as the algebra of intertwining operators from a permutation representation to itself. Generalizing this slightly, we think of intertwining operators between permutation representations in general as Hecke operators.

We make use of the techniques of groupoidification along with the machinery of enriched bicategories and some very basic topos theory. Thus, this paper is intended to give an introduction to some concepts which should play a significant role as the subject of categorified representation theory continues to develop. Detailed accounts of the necessary structures of higher category categories of spans are presented in papers by the author [2] and by the author in collaboration with John Baez [3]. We now proceed to give a brief overview and explanation of each section.

We hope that both representation theorists and category theorists might benefit from this exposition in their continued development of suitable higher categorical frameworks for representation theory. While significant attention is given to certain fundamental ideas about Hecke algebras, the reader not well acquainted with these structures should not be hindered greatly as our discussion stems from widely accessible ideas in incidence geometries. We have attempted to include a fair sampling of the higher category theory needed in these constructions, so that the exposition would be largely self-contained for category theorist and representation theorist alike. Of course, the researcher wishing to pursue these ideas further should consult the references within.

1.1. Matrices and Spans

In Section 2, we give a heuristic discussion of a very simple notion of categorification. In particular, we recall the basic notions of spans, also known as correspondences, and see that spans of sets categorify matrices of (extended) natural numbers $\mathbb{N}\cup \{\infty \}$. Decategorification can be defined using just set cardinality with the usual rule of transfinite arithmetic, $\infty +n=\infty$, for any $n\in \mathbb{N}$, and the free vector space construction, and this process is indeed functorial, since composition of spans by pullback corresponds to matrix multiplication.

After discussing the example of linear operators, we pass to the intertwining operators for a finite group G. Then we need to consider not only spans of sets but spans of G-sets. Since the maps in the spans are now taken to be G-equivariant, the corresponding matrices should also be G-equivariant. This prompts us to recall the relationships between G-sets and permutation representations of G. There is a faithful, essentially surjective functor from the category of G-sets to the category of permutation representations of G. However, this functor is not full. Spans in a category with pullbacks naturally form a bicategory. Since G-sets and permutation representations of G are closely related, except that there are “not enough” maps of G-sets, the bicategory of spans of G-sets is a first clue in constructing categorified permutation representations. We will return to the role of spans of G-sets in Section 2, Section 5 and Section 6.

1.2. Groupoidification and Enriched Bicategories

To understand groupoidification, we need to recall the construction and basic properties of the degroupoidification functor defined in [1]. We discuss this functor and extend it to a functor on the bicategory of spans of groupoids in Section 3.2. Our intention is to define the Hecke bicategory as an enriched structure, but the replacement of functors in the monoidal 2-category of groupoids by spans in the monoidal bicategory of spans of groupoids necessitates a generalization of enriched category theory to enriched bicategory theory. Definitions of enriched bicategories were developed independently by the author and earlier in the unpublished Ph.D. thesis of Carmody [4], which is reproduced in part by Forcey [5]. We present a partial definition explaining the basic idea in this work and will define the full structure along with a change of base theorem in future work. However, the reader well-acquainted with enriched category theory and with some patience may work out the details independently. Change of base for enriched bicategories is analogous to the theorem for enriched categories, and together with the degroupoidification functor, allows us to obtain a categorification theorem for Hecke operators.

The degroupoidification functor takes the monoidal bicategory Span(Grpd) of spans of (tame) groupoids to the monoidal category Vect. The condition that a groupoid be tame ensures that certain sums converge. This condition is defined in [1], but should not be of much concern to the reader at present. We briefly recall the degroupoidification functor here. A groupoid is sent to the free vector space on its set of isomorphism classes of objects. A span of groupoids is sent to a linear operator using the weak or pseudo pullback of groupoids and the notion of groupoid cardinality [6]. That is, we think of a span of groupoids as a categorified or groupoid-valued matrix in much the same way as we think of a span of sets as a set-valued matrix, where set cardinality is replaced by groupoid cardinality.

The notion of enriched bicategories is then used to make the description of our decategorification processes precise. Given a monoidal bicategory $\mathcal{V}$, a $\mathcal{V}$-enriched bicategory consists of a set of objects, hom-objects in $\mathcal{V}$, composition morphisms in $\mathcal{V}$, and further structure and axioms, all of which live in the monoidal bicategory $\mathcal{V}$. The only theorem about enriched bicategories that we will need is a change of base theorem. In particular, given a functor $\mathcal{F}:\mathcal{V}\to {\mathcal{V}}^{\prime }$ and a $\mathcal{V}$-enriched bicategory, then we obtain a ${\mathcal{V}}^{\prime }$-enriched bicategory with hom-objects $\mathcal{F}(\mathrm{hom}(x,y))$. If $\mathcal{V}$ is a monoidal category, then a $\mathcal{V}$-enriched bicategory is a $\mathcal{V}$-enriched category in the usual sense [7]. Enriched bicategories and change of base are discussed in more detail in Section 3.3.

1.3. The Hecke Bicategory

The Hecke bicategory Hecke(G) of a finite group G is a categorification of the permutation representations of G. This is the main construction of this paper. Section 4.1 gives the basic structure of this family of enriched bicategories. For each finite group G, Hecke(G) is an enriched bicategory over the monoidal bicategory of spans of groupoids. The structure of this monoidal bicategory is given roughly in Section 3.2. A more complete and general account of monoidal bicategories (and monoidal tricategories) of spans will be given in [2].

The Hecke bicategory is constructed to study the Hecke operators between permutation representations X and Y of a finite group G by keeping track of information about the G-orbits in X × Y as the hom-groupoid (X × Y)//G. This double-slash notation denotes the action groupoid, which we recall in Definition 3. The composition process between such groupoids is closely related to the pull-tensor-push construction familiar from geometric representation theory.

Now, applying the change of base theorem of enriched bicategories together with the degroupoidification functor, we obtain a Vect-enriched category from Hecke(G). The resulting Vect-enriched category is equivalent to the Vect-enriched category of permutation representations of G. This is our main theorem and is stated in Claim 8.

1.4. Spans of Groupoids and Cocontinuous Functors

In Section 2.3, the bicategory of spans of G-sets appears in our study of the category of permutation representations. We view spans of G-sets as categorified G-equivariant matrices, but do not specify a decategorification process in this setting, although we discuss the importance of set cardinality. This bicategory of spans Span(GSet) plays two important roles in our attempt to understand categorified representation theory, which we briefly discuss here.

In Section 6.2, we will explain the categorification of the Hecke algebra associated to the A₂ Dynkin diagram as a hom-category in Span(GSet). This makes the categorification explicit in that we see the Hecke algebra relations holding up to isomorphism with special spans of G-sets acting as categorified generators. The isomorphisms representing the relations come explicitly from incidence geometries—in this example, projective plane geometry—associated to the Dynkin diagram.

To facilitate this point of view, we describe a monoidal functor in Section 5.2 that takes a groupoid to the corresponding presheaf category and linearizes a span of groupoids to a cocontinuous functor by a pull-tensor-push process familiar from many geometric constructions in representation theory, but quite generally applicable in the theory of Grothendieck toposes. This is a functor $\mathcal{L}:\mathrm{Span}\to \mathrm{Cocont}$, where Cocont is the monoidal 2-category of presheaf categories on groupoids, cocontinuous functors, and natural isomorphisms. By change of base, we obtain a bicategory enriched over certain presheaf toposes, the objects of which are interpreted as spans of G-sets in Section 5.3.

We denote the functor taking a groupoid to its category of presheaves $\mathcal{L}$ suggesting that this might be interpreted as categorified linearization. In this interpretation one thinks of a groupoid as a categorified vector space that is equipped with a chosen basis—its set of isomorphism classes of objects or connected components. From a Grothendieck topos that is equivalent to a category of presheaves on a groupoid, we can always recover the groupoid. Where a basis can always be recovered up to isomorphism from a vector space, a groupoid can be recovered up to equivalence from such a presheaf category. Then we think of such a topos as an abstract categorified vector space.

The relationship between categorified representation theory enriched over monoidal bicategories of spans of spaces and enrichment over corresponding 2-categories of sheaves on the spaces and cocontinuous functors between these will be the focus of future work. From our point of view, these monoidal 2-categories are the basic objects of study in categorified linear algebra, and in this sense, categorified representation theory is enriched over categorified linear algebra. Part of the motivation for this line of work is to better understand and unify (co)homology theories which arise in geometric representation theory.

1.5. The Categorified Hecke Algebra and Zamolodchikov Equation

As already mentioned, Section 6 discusses the main corollary, Claim 16—a categorification of the Hecke algebra of a Coxeter group—as well as possible future directions in low-dimensional topology and higher-category theory. In Section 6.1, we recall the notion of Hecke algebras associated to Dynkin diagrams and prime powers. We describe how a categorification of the Hecke algebra naturally arises from the Hecke bicategory.

Finally, in Section 6.2, we describe a concrete example of the categorified Hecke algebra in terms of spans of G-sets. We describe solutions to the Zamolodchikov tetrahedron equation, which we hope will lead to constructions of braided monoidal 2-categories as pointed out by Kapranov and Voevodsky [8], and eventually (higher) tangle invariants [9].

Other approaches to categorified Hecke algebras and their representations have been studied by a number of authors, building on Kazhdan–Lusztig theory [10]. One key step was Soergel’s introduction of what are nowadays called Soergel bimodules [11,12]. Also important was Khovanov’s categorification of the Jones polynomial [13] and work by Bernstein, Frenkel, Khovanov and Stroppel on categorifying Temperley–Lieb algebras, which are quotients of the type A Hecke algebras [14,15]. A diagrammatic interpretation of the Soergel bimodule category was developed by Elias and Khovanov [16], and a geometric approach led Webster and Williamson [17] to deep applications in knot homology theory. This geometric interpretation can be seen as going beyond the simple form of groupoidification we consider here, and requires considering groupoids in the category of schemes.

2. Matrices, Spans and G-Sets

2.1. Spans as Matrices

The first tool of representation theory is linear algebra. Vector spaces and linear operators have nice properties, which allow representation theorists to extract a great deal of information about algebraic gadgets ranging from finite groups to Lie groups to Lie algebras and their various relatives and generalizations. We start at the beginning, considering the representation theory of finite groups. Noting the utility of linear algebra in representation theory, this paper is fundamentally based on the idea that the heavy dependence of linear algebra on fields, very often the complex numbers, may at times obscure the combinatorial skeleton of the subject. Then, we hope that by peeling back the soft tissue of the continuum, we may expose and examine the bones, revealing new truths by working directly with the underlying combinatorics. In this section, we consider the notion of spans of sets, a very simple idea, which is at the heart of categorified representation theory.

A span of sets from X to Y is a pair of functions with a common domain like so:

We will often denote a span by its apex, when no confusion is likely to arise.

A span of sets can be viewed as a matrix of sets

For each pair $(x,y)\in X\times Y$, we have a set $S_{x,y}=p^{-1}(x)\cap q^{-1}(y)$. In other words, there is a “decategorification” process from spans of sets to matrices with values in $\mathbb{N}\cup \{\infty \}$. If all the sets $S_{x,y}$ are finite, we obtain a matrix of natural numbers $|S_{x,y}|$—a very familiar object in linear algebra. In this sense, a span is a “categorification” of a matrix.

In addition to spans giving rise to matrices, composition of spans gives rise to matrix multiplication. Given a pair of composable spans

we define the composite to be the pullback of the pair of functions $p:S\to Y$ and $q:T\to Y$, which is a new span

where TS is the subset of T × S

$$\{(t,s)\subseteq T\times S\mid p(s)=q(t)\}$$

with the obvious projections to S and T. It is straightforward to check that this process agrees with matrix multiplication after decategorification.

In the above example, we turn spans of sets into matrices simply by counting the number of elements in each set $S_{x,y}$. Checking that composition of spans and matrix multiplication agree after taking the cardinality is the main step in showing that our decategorification process—from the bicategory of spans of sets to the category of linear operators—is functorial.

2.2. Permutation Representations

Again we start with a very simple idea. We want to study the actions of a finite group G on sets—G-sets. However, in this article we restrict to those G-sets with a finite number of orbits. These extend to permutation representations of G. We fix the field of complex numbers and consider only complex vector spaces throughout this paper.

Definition 1.

A permutation representation of a finite group G is a finite-dimensional representation of G together with a chosen basis such that the action of G maps basis vectors to basis vectors.

Definition 2.

An intertwining operator $f:V\to W$ between permutation representations of a finite group G is a linear operator from V to W that is G-equivariant, i.e., commutes with the actions of G.

G-sets can be linearized to obtain permutation representations of G. In fact, this describes a relationship between the objects of the category of G-sets and the objects of the category of permutation representations of G. Given a finite group G, the category of G-sets has

• G-sets (with finitely many orbits) as objects,
• G-equivariant functions as morphisms,

and the category of permutation representations PermRep(G) has

• permutation representations of G as objects,
• intertwining operators as morphisms.

One usually wants the morphisms in a category to preserve the structure on the objects. Of course, an intertwining operator does not necessarily preserve the chosen basis of a permutation representation. We can reconcile our choice of intertwining operators as morphisms, by noticing that there is a bijection between objects in PermRep(G) and the category consisting of finite-dimensional representations of G with the property that there exists a basis preserved by the action of G. Thus, we are justified in working with this definition of PermRep(G).

A primary goal of this paper is to categorify the q-deformed versions of the group algebras of Coxeter groups known as Hecke algebras. Of course, an algebra is a Vect-enriched category with exactly one object, and the Hecke algebras are isomorphic to certain one-object subcategories of the Vect-enriched category of permutation representations. Thus, we refer to the category PermRep(G) as the Hecke algebroid—a many-object generalization of the Hecke algebra. We will construct a bicategory—or more precisely, an enriched bicategory—called the Hecke bicategory that categorifies the Hecke algebroid for any finite group G.

There is a functor from G-sets to permutation representations of G. A G-set X is linearized to a permutation representation $\tilde{X}$, which is the free vector space on X. As stated above, the maps between G-sets are G-equivariant functions—that is, functions between G-sets X and Y that respect the actions of G. Such a function $f:X\to Y$ gives rise to a G-equivariant linear map (or intertwining operator) $\tilde{f}:\tilde{X}\to \tilde{Y}$. However, there are many more intertwining operators from $\tilde{X}$ to $\tilde{Y}$ than there are G-equivariant maps from X to Y. In particular, the former is a complex vector space, while the latter is often a finite set. For example, an intertwining operator $\tilde{f}:\tilde{X}\to \tilde{Y}$ may take a basis vector $x\in \tilde{X}$ to any -linear combination of basis vectors in $\tilde{Y}$, whereas a map of G-sets does not have the freedom of scaling or adding basis elements.

So, in the language of category theory the process of linearizing G-sets to obtain permutation representations is a faithful, essentially surjective functor, which is not at all full.

2.3. Spans of G-Sets

In the previous section, we discussed the relationship between G-sets and permutation representations. In Section 2.1, we saw the close relationship between spans of sets and matrices of (extended) natural numbers. There is an analogous relationship between spans of G-sets and G-equivariant matrices of (extended) natural numbers.

A span of G-sets from a G-set X to a G-set Y is a pair of maps with a common domain

where S is a G-set, and p and q are G-equivariant maps with respective codomains X and Y.

Spans of G-sets are natural structures to consider in categorified representation theory because spans of sets—and, similarly G-sets—naturally form a bicategory.

The development of bicategories by Benabou [18] is an early example of categorification. A (small) category consists of a set of objects and a set of morphisms. A bicategory is a categorification of this concept, so there is a new layer of structure [19]. In particular, a (small) bicategory $\mathcal{B}$ consists of:

• a set of objects x, y, z …,
• for each pair of objects, a set of morphisms,
• for each pair of morphisms, a set of 2-morphisms,

and given any pair of objects x, y, this data forms a hom-category hom(x, y) which has:

• 1-morphisms x → y of $\mathcal{B}$ as objects,
• 2-morphisms:

  of $\mathcal{B}$ as morphisms, and a vertical composition

  of 2-morphisms of $\mathcal{B}$.

Further, the bicategory $\mathcal{B}$ consists of:

• for each triple of objects $x,y,z$, a horizontal composition functor ${\circ }_{xyz}:\mathrm{hom}(x,y)\times \mathrm{hom}(y,z)\to \mathrm{hom}(x,z)$

  on 1-morphisms and 2-morphisms,
• for each object x, an identity-assigning functor $I_x:\mathbf{1}\to \mathrm{hom}(x,x)$,
• for objects $w,x,y,z$, an associator natural isomorphism

  $$a_{wxyz}:{\circ }_{wyz}({\circ }_{wxy}\times 1)\Rightarrow {\circ }_{wxz}(1\times {\circ }_{xyz})$$
• for pairs of objects $x,y$, left and right unitor natural isomorphisms

  $$l_{xy}:{\circ }_{xxy}(I_x\times 1)\Rightarrow 1\mathrm{and}{r}_{xy}:{\circ }_{xyy}(1\times I_y)\Rightarrow 1$$

  all of which is required to satisfy associativity and unit axioms:

  $$(1\circ a_{xyz})a_{w(xy)z}(a_{wxy}\circ 1)=a_{wx(yz)}{a}_{(wx)yz}\mathrm{and}(1\circ r_{yz})a_{xyz}=l_{xy}\circ 1$$

See Leinster’s article [19] for a concise working reference on bicategories.

Benabou’s definition followed from several important examples of bicategories, which he presented in [18], and which are very familiar in categorified and geometric representation theory. The first example is the bicategory of spans of sets, which has:

• sets as objects,
• spans of sets as morphisms,
• maps of spans of sets as 2-morphisms.

We defined spans of sets in Section 2.1. A map of spans of sets from a span S to a span $S^{\prime }$ is a function $f:S\to S^{\prime }$ such that the following diagram commutes:

For each finite group G, there is a closely related bicategory Span(GSet), which has:

• G-sets as objects,
• spans of G-sets as morphisms,
• maps of spans of G-sets as 2-morphisms.

The definitions are the same as in the bicategory of spans of sets, except for the finiteness condition on orbits and that every arrow should be G-equivariant.

While this bicategory is a good candidate for a categorification of the Hecke algebroid PermRep(G), the theory of groupoidification allows for a related, but from our point of view, heuristically nicer categorification. In what follows, we develop the necessary machinery to present this categorification, the Hecke bicategory Hecke(G), in the context of groupoidification. In Section 5 and Section 6.2, we return to Span(GSet) and in future work we will make precise the relationship between spans of G-sets and the Hecke bicategory Hecke(G).

3. Groupoidification and Enriched Bicategories

The following sections introduce the necessary machinery to present the Hecke bicategory, a categorification of the Hecke algebroid. Enriched bicategories are developed for use in Section 4 to construct the Hecke bicategory and state the main result in Theorem 8, and in Section 5 to make a connection with the bicategory Span(GSet) of Section 2.3.

3.1. Action Groupoids and Groupoid Cardinality

In this section, we draw a connection between G-sets and groupoids via the “action groupoid” construction. We then introduce groupoid cardinality, which is the first step in describing the degroupoidification functor in the next section.

For any G-set, there exists a corresponding groupoid, called the action groupoid or weak quotient:

Definition 3.

Given a group G and a G-set X, the action groupoid $X//G$ is the category which has:

• elements of X as objects,
• pairs $(g,x)\in G\times X$ as morphisms $(g,x):x\to x^{\prime }$, where $g·x=x^{\prime }$.

Composition of morphisms is defined by the product in G.

Of course, associativity follows from associativity in G and the construction defines a groupoid since any morphism $(g,x):x\to x^{\prime }$ has an inverse $(g^{-1},x^{\prime }):x^{\prime }\to x$.

So every G-set defines a groupoid, and we will see in Section 4.1 that the weak quotient of G-sets plays an important role in understanding categorified permutation representations.

Next, we recall the definition of groupoid cardinality [6]:

Definition 4.

Given a (small) groupoid $\mathcal{G}$, its groupoid cardinality is defined as:

$$|\mathcal{G}|=\sum _{\mathrm{isomorphism}\mathrm{classes}\mathrm{of}\mathrm{objects}[\mathrm{x}]}\frac{1}{|\mathrm{Aut}(x)|}$$

If this sum diverges, we say $|\mathcal{G}|=\infty$.

In our examples, in particular, the hom-groupoids of the Hecke bicategory, all groupoids will have finitely many objects and morphisms, since we consider action groupoids of finite groups acting on flag complexes in vector spaces over finite fields. In general, we allow groupoids with infinitely many isomorphism classes of objects, and the cardinality of a groupoid takes values in the non-negative real numbers in case the sum converges. Generalized cardinalities have been studied by a number of authors [20,21,22,23].

We can think of groupoid cardinality as a form of categorified division analogous to the quotient of a G-set by its action of G in the case when this action is free. See the paper of Baez and Dolan [6]. In particular, we have the following equation:

$$|X//G|=|X|/|G|$$

whenever G is a finite group acting on a finite set X.

In the next section, we define degroupoidification using the notion of groupoid cardinality.

3.2. Degroupoidification

In this section, we recall some of the main ideas of groupoidification. Of course, in practice this means we will discuss the corresponding process of decategorification—the degroupoidification functor.

To define degroupoidification in [1], a functor was constructed from the category of spans of “tame” groupoids to the category of linear operators between vector spaces. In the present setting, we will need to extend degroupoidification to a functor between bicategories.

We extend the functor to a bicategory Span(Grpd) which has:

• (tame) groupoids as objects,
• spans of groupoids as 1-morphisms,
• isomorphism classes of maps of spans of groupoids as 2-morphisms.

We will often drop the adjective tame when confusion is not likely to arise.

Given a pair of parallel spans in the 2-category Grpd of groupoids, functors, and natural isomorphisms:

a map of spans is a triple $(\alpha ,f,\beta )$, where $f:S\to S^{\prime }$ is a functor and $\alpha :p\Rightarrow p^{\prime }f$ and $\beta :q\Rightarrow q^{\prime }f$ are natural isomorphisms:

In general, spans of groupoids form a (monoidal) tricategory, which has not only maps of spans as 2-morphisms, but also maps of maps of spans as 3-morphisms.

Given a parallel pair of maps of spans $(\alpha ,f,\beta )$ and $({\alpha }^{\prime },f^{\prime },{\beta }^{\prime })$:

a map of maps of spans

$$\gamma :(\alpha ,f,\beta )\Rrightarrow ({\alpha }^{\prime },f^{\prime },{\beta }^{\prime })$$

is a natural isomorphism $\gamma :f\Rightarrow f^{\prime }$ satisfying:

$$(p^{\prime }·\gamma )\alpha ={\alpha }^{\prime }\mathrm{and}(q^{\prime }·\gamma )\beta ={\beta }^{\prime }.$$

(1)

For our purposes we restrict this structure to a bicategory. While there may be more sophisticated ways of obtaining such a bicategory, we do so by taking isomorphism classes of maps of spans as 2-morphisms [2]. A related span construction is found in [24], where the 2-category of spans corresponds roughly to the local 2-categories in our tricategory of spans.

With appropriate finiteness conditions imposed, spans of groupoids are categorified matrices of non-negative rational numbers in the same way that spans of sets are categorified matrices of natural numbers. A span of groupoids is a pair of functors with common domain, and we can picture one of these roughly as follows:

Whereas one uses set cardinality to realize spans of sets as matrices, we can use groupoid cardinality to obtain a matrix from a span of groupoids.

We have seen evidence that spans of groupoids categorify matrices, so we will want to think of a groupoid as a categorified vector space. To make these notions precise, we recall the degroupoidification functor

$$\mathcal{D}:\mathrm{Span}(\mathrm{Grpd})\to \mathrm{Vect}$$

Given a groupoid $\mathcal{G}$, we obtain a vector space $\mathcal{D}(\mathcal{G})$, called the degroupoidification of $\mathcal{G}$, by taking the free vector space on the set of isomorphism classes of objects of $\mathcal{G}$.

We say a groupoid $\mathcal{V}$ over a groupoid $\mathcal{G}$

is a groupoidified vector. In particular, from the functor p we can produce a vector in $\mathcal{D}(\mathcal{G})$ in the following way.

The full inverse image of an object x in $\mathcal{G}$ is the groupoid $p^{-1}(x)$, which has:

• objects v of $\mathcal{V}$, such that $p(v)\cong x$, as objects,
• morphisms $v\to v^{\prime }$ in $\mathcal{V}$ as morphisms.

We note that this construction depends only on the isomorphism class of x. Since the set of isomorphism classes of $\mathcal{G}$ determines a basis of the corresponding vector space, the vector determined by p can be defined as

$$\sum _{\mathrm{isomorphism}\mathrm{classes}\mathrm{of}\mathrm{objects}[\mathrm{x}]}|p^{-1}(x)|[x]$$

where $|p^{-1}(x)|$ is the groupoid cardinality of $p^{-1}(x)$. We note that a “groupoidified basis” can be obtained in this way as a set of functors from the terminal groupoid $\mathbf{1}$ to representative objects of each isomorphism class of $\mathcal{G}$. A groupoidified basis of $\mathcal{G}$ is a set of groupoids $\mathcal{V}\to \mathcal{G}$ over $\mathcal{G}$ such that the corresponding vectors give a basis of the vector space $\mathcal{D}(\mathcal{G})$.

Given a span of groupoids

we want to produce a linear map $\mathcal{D}(\mathcal{S}):\mathcal{D}(\mathcal{G})\to \mathcal{D}(\mathcal{H})$. The details are checked in [1]. Here we show only that given a basis vector of $\mathcal{D}(\mathcal{G})$ viewed as a groupoidified basis vector of $\mathcal{G}$, the span $\mathcal{S}$ determines a vector in $\mathcal{D}(\mathcal{H})$. To do this, we need the notion of the weak pullback of groupoids—a categorified version of the pullback of sets.

Given a diagram of groupoids

the weak pullback of $p:\mathcal{G}\to \mathcal{I}$ and $q:\mathcal{H}\to \mathcal{I}$ is the diagram

where $\mathcal{HG}$ is a groupoid whose objects are triples $(h,g,\alpha )$ consisting of an object $h\in \mathcal{H}$, an object $g\in \mathcal{G}$, and an isomorphism $\alpha :p(g)\to q(h)$ in $\mathcal{I}$. A morphism in $\mathcal{HG}$ from $(h,g,\alpha )$ to $(h^{\prime },g^{\prime },{\alpha }^{\prime })$ consists of a morphism $f:g\to g^{\prime }$ in $\mathcal{G}$ and a morphism $f^{\prime }:h\to h^{\prime }$ in $\mathcal{H}$ such that the following square commutes:

As in the case of the pullback of sets, the maps out of $\mathcal{HG}$ are the obvious projections. Further, this construction satisfies a certain universal property. See [25], for example.

Now, given our span and a chosen groupoidified basis vector:

we obtain a groupoid over $\mathcal{H}$ by constructing the weak pullback:

Now, $\mathcal{S}\mathbf{1}$ is a groupoid over $\mathcal{H}$, and we can compute the resulting vector. The tameness condition on groupoids guarantees that the process of passing a groupoidified vector across a span defines a linear operator [1].

One can check that the process described above defines a linear operator from a span of groupoids, and, further, that this process is functorial [1]. This is the degroupoidification functor. Since isomorphic spans are sent to the same linear operator, it is straightforward to extend this to our bicategory of spans of groupoids by adding identity 2-morphisms to the category of vector spaces and sending all 2-morphisms between spans of groupoids to the corresponding identity 2-morphism.

In the next section, we give the basics of the notion of enriched bicategories. We will see that constructing an enriched bicategory requires having a monoidal bicategory in hand. The bicategory $\mathrm{Span}(\mathrm{Grpd})$ defined above is, in fact, a monoidal bicategory—that is, $\mathrm{Span}(\mathrm{Grpd})$ has a tensor product, which is a functor

$$\otimes :\mathrm{Span}(\mathrm{Grpd})\times \mathrm{Span}(\mathrm{Grpd})\to \mathrm{Span}(\mathrm{Grpd})$$

along with further structure satisfying some coherence relations. The structure of $\mathrm{Span}(\mathrm{Grpd})$, or more generally, monoidal bicategories of spans in 2-categories, is described in detail in [2].

We describe the main components of the tensor product on $\mathrm{Span}(\mathrm{Grpd})$. Given a pair of groupoids $\mathcal{G},\mathcal{H}$, the tensor product $\mathcal{G}\times \mathcal{H}$ is the product in $\mathrm{Grpd}$. Further, for each pair of pairs of groupoids $(\mathcal{G},\mathcal{H}),(\mathcal{I},\mathcal{J})$ there is a functor:

$$\otimes :\mathrm{Span}(\mathrm{Grpd})(\mathcal{G},\mathcal{H})\times \mathrm{Span}(\mathrm{Grpd})(\mathcal{I},\mathcal{J})\to \mathrm{Span}(\mathrm{Grpd})(\mathcal{G}\times \mathcal{I},\mathcal{H}\times \mathcal{J})$$

defined roughly as follows:

In fact, this tensor product will be not just a functor, but a homomorphism of bicategories. This means that it carries some more structure and satisfies some extra axioms, but we will not give these details here. See the manuscript of Gordon, Power, and Street [26] for the definition of monoidal bicategory and homomorphism between monoidal bicategories.

3.3. Enriched Bicategories

A monoidal structure, such as the tensor product on $\mathrm{Span}(\mathrm{Grpd})$ discussed in the previous section, is the crucial ingredient for defining enriched bicategories. In particular, given a monoidal bicategory $\mathcal{V}$ with the tensor product ⊗, a $\mathcal{V}$-enriched bicategory has, for each pair of objects $x,y$, an object $\mathrm{hom}(x,y)$ of $\mathcal{V}$. Composition involves the tensor product in $\mathcal{V}$

$$\circ :\mathrm{hom}(x,y)\otimes \mathrm{hom}(y,z)\to \mathrm{hom}(x,z)$$

While writing the final draft of this article, we realized that our definition of enriched bicategory is almost identical to one previously given by Carmody [4] and recalled in part by Forcey [5].

After giving the basic structure of enriched bicategories, we state a change of base theorem, which says which sort of map $f:\mathcal{V}\to {\mathcal{V}}^{\prime }$ lets us turn a $\mathcal{V}$-enriched bicategory into a ${\mathcal{V}}^{\prime }$-enriched bicategory.

Recall that, for each finite group G, we have defined a category of permutation representations $\mathrm{PermRep}(G)$. Further, the theory of enriched bicategories allows us to define the $\mathrm{Span}(\mathrm{Grpd})$-enriched bicategory $\mathrm{Hecke}(G)$, which we call the Hecke bicategory. In an ordinary bicategory, the composition operation is given by a functor. So while composition in $\mathrm{Span}(\mathrm{Grpd})$ is defined as a functor, in the Hecke bicategory, composition is given not by a functor, but rather a general morphism in the enriching bicategory $\mathrm{Span}(\mathrm{Grpd})$. Thus, the composition operation in $\mathrm{Hecke}(G)$ is given by a span of groupoids. This more general notion of composition forces us to work in the setting of enriched bicategories. An advantage to working in the setting of enriched bicategories is the existence of a change of base theorem, which we will employ as the main tool in proving our categorification theorem via degroupoidification.

Before giving the definition of an enriched bicategory, we recall the definition of an enriched category—that is, a category enriched over a monoidal category $\mathcal{V}$ [7]. An enriched category (or $\mathcal{V}$-category) consists of:

• a set of objects $x,y,z\dots$,
• for each pair of objects $x,y$, an object $\mathrm{hom}(x,y)\in \mathcal{V}$,
• composition and identity-assigning maps that are morphisms in $\mathcal{V}$.

For example, $\mathrm{PermRep}(G)$ is a category enriched over the monoidal category of vector spaces.

We now define enriched bicategories:

Definition 5.

Let $\mathcal{V}$ be a monoidal bicategory. An enriched bicategory (or $\mathcal{V}$-bicategory) $\mathcal{B}$ consists of the following data subject to the following axioms:

• a collection of objects $x,y,z,\dots$,
• for every pair of objects $x,y$, a hom-object $\mathrm{hom}(x,y)\in \mathcal{V}$, which we will often denote $(x,y)$,
• a morphism called composition

  $$\circ :\mathrm{hom}(x,y)\otimes \mathrm{hom}(y,z)\to \mathrm{hom}(x,z)$$

  for each triple of objects $x,y,z\in \mathcal{B}$,
• an identity-assigning morphism

  $$i_x:I\to \mathrm{hom}(x,x)$$

  for each object $x\in \mathcal{B}$,
• an invertible 2-morphism called the associator

  for each quadruple of objects $w,x,y,z\in \mathcal{B}$;
• and invertible 2-morphisms called the right unitor and left unitor

  for every pair of objects $x,y\in \mathcal{B}$;
• and axioms given by closed surface diagrams, the more interesting of the two being the permutahedron [4].

Given a monoidal bicategory $\mathcal{V}$, which has only identity 2-morphisms, every $\mathcal{V}$-bicategory is a $\mathcal{V}$-category in the obvious way, and every $\mathcal{V}$-enriched category can be trivially extended to a $\mathcal{V}$-bicategory. This flexibility will allow us to think of $\mathrm{PermRep}(G)$ as either a $\mathrm{Vect}$-enriched category or as a $\mathrm{Vect}$-enriched bicategory.

Now we state a change of base construction which allows us to change a $\mathcal{V}$-enriched bicategory to a ${\mathcal{V}}^{\prime }$-enriched bicategory.

Claim 6.

Given a lax-monoidal homomorphism of monoidal bicategories $f:\mathcal{V}\to {\mathcal{V}}^{\prime }$ and a $\mathcal{V}$-bicategory ${\mathcal{B}}_{\mathcal{V}}$, then there is a ${\mathcal{V}}^{\prime }$-bicategory

$$\overline{f}({\mathcal{B}}_{\mathcal{V}})$$

A monoidal homomorphism is a map between bicategories preserving the monoidal structure up to isomorphism [26,27]. A lax-monoidal homomorphism f is a bit more general: it need not preserve the tensor product up to isomorphism. Instead, it preserves the tensor product only up to a morphism:

$$f(x){\otimes }^{\prime }f(y)\to f(x\otimes y)$$

where the symbol ${\otimes }^{\prime }$ is the monoidal product in ${\mathcal{V}}^{\prime }$.

The data of the enriched bicategory $\overline{f}({\mathcal{B}}_{\mathcal{V}})$ is straightforward to write down and the proof of the claim is an equally straightforward, yet tedious surface diagram chase. Here we just point out the most important idea. The new enriched bicategory $\overline{f}({\mathcal{B}}_{\mathcal{V}})$ has the same objects as ${\mathcal{B}}_{\mathcal{V}}$, and for each pair of objects $x,y$, the $\mathrm{hom}$-category of $\overline{f}({\mathcal{B}}_{\mathcal{V}})$ is

$${\mathrm{hom}}_{\overline{f}({\mathcal{B}}_{\mathcal{V}})}(x,y):=f({\mathrm{hom}}_{{\mathcal{B}}_{\mathcal{V}}}(x,y))$$

This theorem will allow us to compare the Hecke bicategory, which we define in the next section, to bicategory of spans of finite G-sets $\mathrm{Span}(G\mathrm{Set})$.

4. A Categorification Theorem

The following sections are devoted to categorifying the Hecke algebroid. We will show how to obtain the category of permutation representations using the process of degroupoidification.

4.1. The Hecke Bicategory

We are now in a position to present the spans of groupoids enriched bicategory $\mathrm{Hecke}(G)$—the Hecke bicategory.

Claim 7.

Given a finite group G, there is a $\mathrm{Span}(\mathrm{Grpd})$-enriched bicategory $\mathrm{Hecke}(G)$ which has:

• G-sets $X,Y,Z\dots$ as objects,
• for each pair of G-sets $X,Y$, an object of $\mathrm{Span}(\mathrm{Grpd})$, the action groupoid:

  $$\mathrm{hom}(X,Y)=(X\times Y)//G$$
• composition

  $$\circ :(X\times Y)//G\times (Y\times Z)//G\to (X\times Z)//G$$

  is the span of groupoids,
• for each G-set X, an identity assigning span from the terminal groupoid 1 to $(X\times X)//G$,
• invertible 2-morphisms in $\mathrm{Span}(\mathrm{Grpd})$ assuming the role of the associator and left and right unitors.

Given this structure one needs to check that the axioms of an enriched bicategory are satisfied; however, we will not prove this here. Combining the degroupoidification functor of Section 3.2, the change of base theorem of Section 3.3, and the enriched bicategory $\mathrm{Hecke}(G)$ described above, we can now state the main theorem. This is the content of the next section.

4.2. A Categorification of the Hecke Algebroid

In this section, we describe the relationship between the Hecke algebroid $\mathrm{PermRep}(G)$ of permutation representations of a finite group G and the Hecke bicategory $\mathrm{Hecke}(G)$. The idea is that for each finite group G, the Hecke bicategory $\mathrm{Hecke}(G)$ categorifies $\mathrm{PermRep}(G)$.

We recall the functor degroupoidification:

$$\mathcal{D}:\mathrm{Span}(\mathrm{Grpd})\to \mathrm{Vect}$$

which replaces groupoids with vector spaces and spans of groupoids with linear operators. With this functor in hand, we can apply the change of base theorem to the $\mathrm{Span}(\mathrm{Grpd})$-enriched bicategory $\mathrm{Hecke}(G)$. In other words, for each finite group G there is a $\mathrm{Vect}$-enriched bicategory:

$$\overline{\mathcal{D}}\left(\mathrm{Hecke}(G)\right)$$

which has

• permutation representations $X,Y,Z,\dots$ of G as objects,
• for each pair of permutation representations $X,Y$, the vector space

  $$\mathrm{hom}(X,Y)=\mathcal{D}\left((X\times Y)//G\right)$$

with G-orbits of $X\times Y$ as basis. Of course, a Vect-enriched bicategory is also a Vect-enriched category. The following is the statement of the main theorem, an equivalence of Vect-enriched categories.

Claim 8.

Given a finite group G,

$$\overline{\mathcal{D}}\left(\mathrm{Hecke}(G)\right)\simeq \mathrm{PermRep}(G)$$

as Vect-enriched categories.

More explicitly, this says that given two permutation representations $\tilde{X}$ and $\tilde{Y}$, the vector space of intertwining operators between them can be constructed as the degroupoidification of the groupoid $(X\times Y)//G$.

An important corollary of Claim 8 is that for certain G-sets—the flag varieties X associated to Dynkin diagrams—the hom-groupoid $\mathrm{Hecke}(G)(X,X)$ categorifies the associated Hecke algebra. We will describe these Hecke algebras in Section 6.1 and make the relationship to the Hecke bicategory and some of its applications explicit in Section 6.2.

5. Spans of Groupoids and Cocontinuous Functors

In the following sections, we sketch the beginning of the project of understanding the relationship between the Hecke bicategory and $\mathrm{Span}(G\mathrm{Set})$. For this we will need to introduce the monoidal 2-category Cocont of presheaf categories on groupoids and cocontinuous functors.

5.1. The Monoidal 2-Category Cocont

In Section 3.2, we considered groupoids as categorified vector spaces. In particular, the isomorphism classes of objects assumed the role of a basis of the corresponding free vector space. A slightly different point of view, which was discussed at length in [1], assigns to a groupoid the vector space of functions on the set of isomorphism classes of that groupoid. Thus, promoting functions to functors, we can think of a categorified vector space as the presheaf category on a groupoid. Given a groupoid $\mathcal{G}$, its category of presheaves $\widehat{\mathcal{G}}$ has:

• presheaves on $\mathcal{G}$ as objects,
• natural transformations as morphisms.

Recall that a (Set-valued) presheaf on a category $\mathcal{C}$ is a contravariant functor ${\mathcal{C}}^{\mathrm{op}}\to \mathrm{Set}$. The objects of the monoidal bicategory described in this section are categories equivalent to categories of presheaves. We now define such a category, which we call a nice topos.

Definition 9.

A nice topos is a category equivalent to the category of presheaves on a (tame) groupoid.

By the above definition, there is a nice topos $\widehat{\mathcal{G}}$ of presheaves corresponding to any groupoid $\mathcal{G}$. However, mapping groupoids to these special presheaf categories suggests that nice toposes should have an intrinsic characterization. To give such a characterization of these toposes we should look to the generalization to toposes in Grothendieck’s Galois theory of schemes. The interested reader is pointed to the survey article [28] and references therein, although the present paper may be read independently of this survey. Giving this intrinsic characterization liberates the nice topos from its dependence on a particular groupoid. In particular, this supports the point of view that nice toposes are the objects of a basis independent theory of categorified vector spaces.

Following this line of reasoning, the maps between nice toposes are thought of as categorified linear operators. Thus, they should preserve sums, or more accurately, they should preserve a categorified and generalized notion of “sums”—colimits.

Definition 10.

A functor is said to be cocontinuous if it preserves all (small) colimits.

This suggests that cocontinuous functors might play the role of categorified linear operators. Indeed, we take such an approach.

In the next section, we will see further support for the analogy: nice topos is to groupoid as abstract vector space is to vector space with chosen basis and cocontinuous functor is to span of groupoids as linear operator is to matrix.

The monoidal bicategory Cocont consists of:

• nice toposes $\mathcal{D},\mathcal{E},\mathcal{F},\dots$ as objects,
• cocontinuous functors as 1-morphisms,
• natural transformations as 2-morphisms.

Objects of Cocont are categories and the morphisms between them are functors. Thus, there is a faithful functor from Cocont to Cat. It follows from the definition that the product of tame groupoids is again tame [1]. Then the product of a pair of nice toposes is again a nice topos inducing a monoidal structure on Cocont. In particular, the tensor product of nice toposes $\mathcal{E}$ and $\mathcal{F}$ is the Cartesian product $\mathcal{E}\times \mathcal{F}$. Further, the Cartesian product is a cocontinuous functor in each variable and thus the product of cocontinuous functors is again cocontinuous.

In the next section, we will describe the relationship between spans of groupoids and cocontinuous functors between nice toposes. We use some basic notions of topos theory.

5.2. From Spans of Groupoids to Cocontinuous Functors

The change of base construction for enriched bicategories offers a new interpretation of the Hecke bicategory. We have described two closely related monoidal bicategories. The relationship between groupoids and nice toposes is made manifest as a functor between monoidal bicategories. Understanding this functor will be the focus of this section.

It is clear from the definition that we can obtain a nice topos by assigning a groupoid $\mathcal{G}$ to its corresponding presheaf category $\widehat{\mathcal{G}}$. Continuing our analogy with abstract vector spaces and vector spaces with a chosen basis, we will explain how a span of groupoids gives a cocontinuous functor between the corresponding presheaf categories. In fact, a groupoid can be recovered up to equivalence from its presheaf category, just as a basis can be recovered up to isomorphism from its vector space, but in each case the equivalence or isomorphism is non-canonical.

First, we review some basic ideas from topos theory. A topos is a category which resembles the category of sets. Categories of presheaves are examples of Grothendieck toposes. In general, a Grothendieck topos is a category of sheaves on a site. A site is just a category with a notion of a covering of objects called a Grothendieck topology [29,30]. A familiar example with a particularly simple Grothendieck topology is the category of presheaves on a topological space.

So if a topos is just a special type of category, then how does topos theory differ from category theory? One answer is that while the morphisms between categories are functors, the morphisms between toposes must satisfy extra properties. Such a morphism is called a geometric morphism [30]. We define the morphisms between nice toposes, although the definition is exactly the same in the more general setting of Grothendieck toposes.

Definition 11.

A geometric morphism $e:\mathcal{E}\to \mathcal{F}$ between nice toposes is a pair of functors $e^{*}:\mathcal{F}\to \mathcal{E}$ and $e_{*}:\mathcal{E}\to \mathcal{F}$ such that $e^{*}$ is left adjoint to $e_{*}$ and $e^{*}$ is left exact, i.e., preserves finite limits. A geometric morphism $e:\mathcal{E}\to \mathcal{F}$ is said to be essential if there exists a functor $e_{!}:\mathcal{E}\to \mathcal{F}$ which is left adjoint to $e^{*}$.

We note a relationship to functors between groupoids, which allows us to define cocontinuous functors from spans. Any functor $f:\mathcal{G}\to \mathcal{H}$ defines a geometric morphism between the corresponding presheaf categories:

$$\widehat{f}:\widehat{\mathcal{G}}\to \widehat{\mathcal{H}}$$

which consists of the functor:

$$f^{*}:\widehat{\mathcal{H}}\to \widehat{\mathcal{G}}$$

which pulls presheaves back from $\mathcal{H}$ to $\mathcal{G}$, together with the right adjoint of $f^{*}$

$$f_{*}:\widehat{\mathcal{G}}\to \widehat{\mathcal{H}}$$

which pushes presheaves forward from $\mathcal{G}$ to $\mathcal{H}$. The particularly important fact is that a geometric morphism induced by a functor between groupoids will always be essential—that is, there exists a left adjoint to $f^{*}$:

$$f_{!}:\widehat{\mathcal{G}}\to \widehat{\mathcal{H}}$$

Definition 12.

A map of geometric morphisms $\alpha :e\Rightarrow f$ is a natural transformation:

$$\alpha :e^{*}\Rightarrow f^{*}$$

Using the fact that a functor between groupoids induces an essential geometric morphism, we see that from a span of groupoids:

we can define a functor:

$$q_{!}{p}^{*}:\widehat{\mathcal{G}}\to \widehat{\mathcal{H}}$$

which is a composite of left adjoint functors, and thus, cocontinuous. Although we do not go into detail at present, using this construction on spans it is not difficult to define a natural transformation between cocontinuous functors from a map of spans. After checking details, the following claim becomes evident.

Claim 13.

There is a homomorphism of monoidal bicategories

$$\mathcal{L}:\mathrm{Span}(\mathrm{Grpd})\to \mathrm{Cocont}$$

which assigns to each groupoid $\mathcal{G}$ its category of presheaves $\widehat{\mathcal{G}}$ and to each span

the cocontinuous functor $q_{!}{p}^{*}:\widehat{G}\to \widehat{H}$.

In the setting of spans of sets, the homomorphism $\mathcal{L}$ would be analogous to the functor taking a set X to the free vector space with basis X, and a span

to a linear operator between the corresponding vector spaces.

Using the map $\mathcal{L}$, we can apply change of base to the Hecke bicategory to obtain a Cocont-enriched bicategory. We will discuss the details and benefits of this new structure in the next section.

5.3. Spans of G-Sets as Nice toposes

In this section we take a closer look at the structure of the Cocont-enriched bicategory $\overline{\mathcal{L}}(\mathrm{Hecke}(G))$. Our goal is to rephrase the construction as a cocompletion of the bicategory $\mathrm{Span}(G\mathrm{Set})$ of spans of G-sets.

Claim 14.

Given a finite group G, there is a Cocont-enriched bicategory $\overline{\mathcal{L}}(\mathrm{Hecke}(G))$ which has:

• G-sets $X,Y,Z\dots$ as objects,
• for each pair of G-sets $X,Y$, an object of Cocont:

  $$\mathrm{hom}(X,Y)=\widehat{(X\times Y)//G}$$
• composition

  $$\circ :\widehat{(X\times Y)//G}\times \widehat{(Y\times Z)//G}\to \widehat{(X\times Z)//G}$$

  is the cocontinuous functor ${({\pi }_{13})}_{!}{({\pi }_{12}\times {\pi }_{23})}^{*}$,
• for each G-set X, an identity assigning cocontinuous functor from the topos $\widehat{1}\simeq \mathrm{Set}$ to $\widehat{(X\times X)//G}$,
• invertible 2-morphisms in Cocont assuming the role of the associator and left and right unitors.

The proof of this claim is immediate from the proofs of Claim 6 and Claim 7.

It turns out that the hom-categories of the Cocont-enriched bicategory $\overline{\mathcal{L}}(\mathrm{Hecke}(G))$ have a very simple description as spans of G-sets and maps of spans. Given G-sets X and Y, the product $X\times Y$ is again a G-set in an obvious way, so we can construct the action groupoid $(X\times Y)//G$. The category of presheaves on this groupoid will be a nice topos.

Lemma 15.

Given a pair of G-sets X, Y, the category whose objects are spans of G-sets from X to Y and whose morphisms are maps of these spans of G-sets is equivalent to the nice topos $\widehat{(X\times Y)//G}$.

The construction which proves this lemma is sometimes called the Grothendieck construction. The construction says that given a pair of G-sets X and Y, presheaves on $(X\times Y)//G$ are spans from X to Y and natural transformations are maps of spans. We sketch the proof of this lemma now.

Proof. (Sketch) Given a span of G-sets:

there is a presheaf on $(X\times Y)//G$, which we can think of approximately as a categorified matrix of natural numbers, i.e., a matrix of sets. Each object $(x,y)$ determines an entry in the matrix, and the entries are the sets $S_{x,y}=p^{-1}(x)\cap q^{-1}(y)$ defined in Section 2.1. For each morphism $(g,(x,y)):(x,y)\to (x^{\prime },y^{\prime })$, we define a function from $S_{x^{\prime },y^{\prime }}$ to $S_{x,y}$ by the action of $g^{-1}$ on the G-set $S_{x^{\prime },y^{\prime }}$. Thus, we obtain a presheaf from the span S.

Now from a map of spans of G-sets:

we construct a natural transformation between the presheaves corresponding to S and $S^{\prime }$. For each object $(x,y)$ of $(X\times Y)//G$, the component of the natural transformation takes an element $s\in S_{x,y}$ to $f(s)\in S_{x,y}^{\prime }$. Since f is G-equivariant, the naturality squares commute.

It is not difficult to check that this process defines an equivalence of categories. We only need to build a functor in the other direction such that the respective composites are naturally isomorphic to the identity. We construct such a functor here.

Consider a presheaf P on the groupoid $(X\times Y)//G$. We construct a span with apex the disjoint union of the sets $P(x,y)$. Given a morphism $(g,(x,y)):(x,y)\to (g·x,g·y)\in (X\times Y)//G$, there is an induced action on the set $P(x,y)$ coming from $P(g,(x,y)):P(x,y)\to P(g·x,g·y)$. The projections onto X and Y are G-equivariant maps yielding the span

Next, consider a natural transformation from a presheaf P to a presheaf Q. We define a map between the corresponding spans denoted by their apex sets $S_P$ and $S_Q$. Each element $p\in S_P$ is assigned a pair $(x,y)$ by the projections, and to this pair, the natural transformation assigns a function $f:P(x,y)\to Q(x,y)$. Since $p\in P(x,y)\subseteq S_P$ and $f(p)\in Q(x,y)\subseteq S_Q$, we have defined a map of spans.

We have seen that the hom-categories of the Cocont-enriched bicategory $\overline{\mathcal{L}}(\mathrm{Hecke}(G))$ are actually categories whose objects are spans of G-sets and whose morphisms are maps between such spans. In particular, this bicategory is the local cocompletion of $\mathrm{Span}(G\mathrm{Set})$. In describing categorified Hecke algebras we will present a groupoid and a span of groupoids. It will be useful when we consider a specific example to consider the presheaf category in place of the groupoid and to think of each presheaf as a span of G-sets.

6. The Categorified Hecke Algebra and Zamolodchikov Equation

The main claim of this paper is the existence of a categorification of the Hecke algebroid by the Hecke bicategory $\mathrm{Hecke}(G)$. This is, in fact, a statement about categorified Hecke algebras. In attempting to make connections between the categorified Hecke algebra and knot theory, the bicategory $\mathrm{Span}(G\mathrm{Set})$ allows a hands-on approach to the categorified generators and the isomorphisms of spans arising from the defining equations of the Hecke algebra. We show that in certain cases these are Yang–Baxter operators that satisfy the Zamolodchikov tetrahedron equation. The hope is that these Yang–Baxter equations will lead to interesting braided monoidal 2-categories [8].

6.1. The Hecke Algebra

There are several well-known equivalent descriptions of the Hecke algebra $\mathcal{H}(\Gamma ,q)$ obtained from a Dynkin diagram Γ and a prime power q. One description of the Hecke algebra is as a q-deformation of the group algebra of the Coxeter group of Γ. A standard example of a Coxeter group associated to a Dynkin diagram is the symmetric group on n letters $S_n$, which is the Coxeter group of the $A_{n-1}$ Dynkin diagram. We will return to this definition in Section 6.2 and see that it lends itself to combinatorial applications of the Hecke algebra. This combinatorial aspect comes from the close link between the Coxeter group and its associated Coxeter complex, a finite simplicial complex that plays an essential role in the theory of buildings [31].

Hecke algebras have an alternative definition as algebras of intertwining operators between certain coinduced representations [32]. Given a Dynkin diagram Γ and prime power q, there is an associated simple algebraic group $G=G(\Gamma ,q)$. Choosing a Borel subgroup $B\subset G$, i.e., a maximal solvable subgroup, we can construct the corresponding flag complex $X=G/B$, a transitive G-set.

Now, for a finite group G and a representation V of a subgroup $H\subset G$, the induced representation of G from H is defined as the V-valued functions on G, which commute with the action of H:

$${\mathrm{Ind}}_H^G(V)=\{f:G\to V\mid h·f(x)=f(hx),\mathrm{for}h\in H\}$$

The action of $g\in G$ is defined on a function $f:G\to V$ as $(g·f)(x)=f(xg)$. A standard fact about finite groups says that the representation induced from the trivial representation of any subgroup is isomorphic to the permutation representation on the cosets of that subgroup. Thus, from the trivial representation of a Borel subgroup B, we obtain the permutation representation $\tilde{X}$ on the cosets of B, i.e., the flag complex X. Then the Hecke algebra is defined as the algebra of intertwining operators from $\tilde{X}$ to itself:

$$\mathcal{H}(\Gamma ,q):=\mathrm{PermRep}(G)(\tilde{X},\tilde{X})$$

where $G=G(\Gamma ,q)$.

Given this definition of the Hecke algebra, we have an immediate corollary to Claim 8:

Claim 16.

Given a Dynkin diagram Γ and prime power q, denote $G=G(\Gamma ,q)$. Then the hom-category $\mathrm{Hecke}(G)(X,X)$ of the Hecke bicategory categorifies the Hecke algebra $\mathcal{H}(\Gamma ,q)$.

6.2. Categorified Generators and the Zamolodchikov Equation

Now that we have seen a categorification of Hecke algebras abstractly as a corollary, we look at a concrete example. The categorified Hecke algebra is particularly easy to understand as living inside the bicategory $\mathrm{Span}(G\mathrm{Set})$. While we found it useful earlier to view Hecke algebras as algebras of intertwining operators, viewing the Hecke algebra by its presentation as a q-deformation of a Coxeter group [33] is helpful in examples.

Any Dynkin diagram gives rise to a simple Lie group, and the Weyl group of this simple Lie group is a Coxeter group. Let Γ be a Dynkin diagram. We write $d\in \Gamma$ to mean that d is a dot in this diagram. Associated to each unordered pair of dots $d,d^{\prime }\in \Gamma$ is a number $m_{d{d}^{\prime }}\in \{2,3,4,6\}$. In the usual Dynkin diagram conventions:

• $m_{d{d}^{\prime }}=2$ is drawn as no edge at all,
• $m_{d{d}^{\prime }}=3$ is drawn as a single edge,
• $m_{d{d}^{\prime }}=4$ is drawn as a double edge,
• $m_{d{d}^{\prime }}=6$ is drawn as a triple edge.

For any prime power q, our Dynkin diagram Γ yields a Hecke algebra. The Hecke algebra $\mathcal{H}(\Gamma ,q)$ corresponding to this data is the associative algebra with one generator ${\sigma }_d$ for each $d\in \Gamma$, and relations:

$${\sigma }_d^2=(q-1){\sigma }_d+q$$

for all $d\in \Gamma$, and

$${\sigma }_d{\sigma }_{d^{\prime }}{\sigma }_d\cdots ={\sigma }_{d^{\prime }}{\sigma }_d{\sigma }_{d^{\prime }}\cdots$$

for all $d,d^{\prime }\in \Gamma$, where each side has $m_{d{d}^{\prime }}$ factors.

When $q=1$, this Hecke algebra is simply the group algebra of the Coxeter group associated to Γ—that is, the group with one generator $s_d$ for each dot $d\in \Gamma$, and relations

$$s_d^2=1,{(s_d{s}_{d^{\prime }})}^{m_{d{d}^{\prime }}}=1$$

So, the Hecke algebra can be thought of as a q-deformation of this Coxeter group.

We recall the flag complex $X=G/B$ from Section 6.1 is a finite set equipped with a transitive action of the finite group G. Starting from just this G-set X, we can see an explicit picture of the categorified Hecke algebra of spans of G-sets from X to X.

The key is that for each dot $d\in \Gamma$ there is a special span of G-sets that corresponds to the generator ${\sigma }_d\in \mathcal{H}(\Gamma ,q)$. To illustrate these ideas, let us consider the simplest nontrivial example, the Dynkin diagram $A_2$:

The Hecke algebra associated to $A_2$ has two generators, which we call P and L, for reasons soon to be revealed:

$$P={\sigma }_1,L={\sigma }_2$$

To make the connection to the description of the Hecke algebra as an algebra of intertwining operators explicit, we can choose a basis of $\tilde{X}$ corresponding to the elements of the Coxeter group $S_3$ and write these generators as the following matrices, or intertwining operators.

$$P=\left(\begin{array}{cccccc}0& q& 0& 0& 0& 0\\ 1& q-1& 0& 0& 0& 0\\ 0& 0& 0& q& 0& 0\\ 0& 0& 1& q-1& 0& 0\\ 0& 0& 0& 0& q-1& 1\\ 0& 0& 0& 0& q& 0\end{array}\right)$$

$$L=\left(\begin{array}{cccccc}0& 0& 0& 0& 0& q\\ 0& 0& q& 0& 0& 0\\ 0& 1& q-1& 0& 0& 0\\ 0& 0& 0& q-1& 1& 0\\ 0& 0& 0& q& 0& 0\\ 1& 0& 0& 0& 0& q-1\end{array}\right)$$

The relations are

$$P^2=(q-1)P+q,L^2=(q-1)L+q,PLP=LPL$$

It follows that this Hecke algebra is a quotient of the group algebra of the 3-strand braid group, which has two generators P and L, which we can draw as braids in 3-dimensional space:

and one relation $PLP=LPL$:

called the Yang–Baxter equation or third Reidemeister move. This is why Jones could use traces on the $A_n$ Hecke algebras to construct invariants of knots [34]. In light of the success of Khovanov homology—a categorification of the Jones polynomial—this connection to knot theory makes it especially interesting to categorify Hecke algebras.

So, let us see what the categorified Hecke algebra looks like, and where the Yang–Baxter equation comes from. The algebraic group corresponding to the $A_2$ Dynkin diagram and the prime power q is $G=\mathrm{SL}(3,{\mathbb{F}}_q)$, and we can choose the Borel subgroup B to consist of upper triangular matrices in $\mathrm{SL}(3,{\mathbb{F}}_q)$. Recall that a complete flag in the vector space ${\mathbb{F}}_q^3$ is a pair of subspaces

$$0\subset V_1\subset V_2\subset {\mathbb{F}}_q^3$$

The subspace $V_1$ must have dimension one, while $V_2$ must have dimension two. Since G acts transitively on the set of complete flags and B is the subgroup stabilizing a chosen flag, the flag variety $X=G/B$ in this example is just the set of complete flags in ${\mathbb{F}}_q^3$—hence its name.

We can think of $V_1\subset {\mathbb{F}}_q^3$ as a point in the projective plane ${\mathbb{F}}_q{\mathrm{P}}^2$, and $V_2\subset {\mathbb{F}}_q^3$ as a line in this projective plane. From this viewpoint, a complete flag is a chosen point lying on a chosen line in ${\mathbb{F}}_q{\mathrm{P}}^2$. This viewpoint is natural in the theory of “buildings”, where each Dynkin diagram corresponds to a type of geometry [31]. Each dot in the Dynkin diagram then stands for a “type of geometric figure”, while each edge stands for an “incidence relation”. The $A_2$ Dynkin diagram corresponds to projective plane geometry. The dots in this diagram stand for the figures “point” and “line”:

The edge in this diagram stands for the incidence relation “the point p lies on the line ℓ”.

We can think of P and L as special elements of the $A_2$ Hecke algebra, as already described. But when we categorify the Hecke algebra, P and L correspond to irreducible spans of G-sets—that is, spans that are not coproducts of two non-trivial spans of G-sets. Let us describe these spans and explain how the Hecke algebra relations arise in this categorified setting.

The objects P and L can be defined by giving irreducible spans of G-sets:

In general, any span of G-sets

such that $q\times p:S\to X\times X$ is injective can be thought of as G-invariant binary relation between elements of X. Irreducible G-invariant spans are always injective in this sense. So, such spans can also be thought of as G-invariant relations between flags. In these terms, we define P to be the relation that says two flags have the same line, but different points:

$$P=\{((p,\ell ),(p^{\prime },\ell ))\in X\times X\mid p\ne p^{\prime }\}$$

Similarly, we think of L as a relation saying two flags have different lines, but the same point:

$$L=\{((p,\ell ),(p,{\ell }^{\prime }))\in X\times X\mid \ell \ne {\ell }^{\prime }\}$$

Given this, we will check:

$$P^2\cong (q-1)\times P+q\times 1,L^2\cong (q-1)\times L+q\times 1,PLP\cong LPL$$

Here both sides refer to spans of G-sets. Addition of spans is defined using the coproduct and 1 denotes the identity span from X to X. We use “q” to stand for a fixed q-element set, and similarly for “$q-1$”. We compose spans of G-sets using the ordinary pullback.

To check the existence of the first two isomorphisms above, we just need to count. In ${\mathbb{F}}_q{\mathrm{P}}^2$, there are $q+1$ points on any line. So, given a flag we can change the point in q different ways. To change it again, we have a choice: we can either send it back to the original point, or change it to one of the $q-1$ other points. So, $P^2\cong (q-1)\times P+q\times 1$. Since there are also $q+1$ lines through any point, similar reasoning shows that $L^2\cong (q-1)\times L+q\times 1$.

The Yang–Baxter isomorphism

$$PLP\cong LPL$$

is more interesting. We construct it as follows. First consider the left-hand side, $PLP$. Start with a complete flag $(p_1,{\ell }_1)$:

Then, change the point to obtain a flag $(p_2,{\ell }_1)$. Next, change the line to obtain a flag $(p_2,{\ell }_2)$. Finally, change the point once more, which gives us the flag $(p_3,{\ell }_2)$:

The figure on the far right is a typical element of $PLP$:

$$((p_1,{\ell }_1),(p_2,{\ell }_1),(p_2,{\ell }_2),(p_3,{\ell }_2))\mathrm{such}\mathrm{that}{p}_1\ne p_2,p_2\ne p_3,{\ell }_1\ne {\ell }_2$$

On the other hand, consider $LPL$. Start with the same flag as before, but now change the line, obtaining $(p_1,{\ell }_2^{\prime })$. Next change the point, obtaining the flag $(p_2^{\prime },{\ell }_2^{\prime })$. Finally, change the line once more, obtaining the flag $(p_2^{\prime },{\ell }_3^{\prime })$:

The figure on the far right is a typical element of $LPL$.

Now, the axioms of projective plane geometry say that any two distinct points lie on a unique line, and any two distinct lines intersect in a unique point. So, any figure of the sort shown on the left below determines a unique figure of the sort shown on the right, and vice versa:

Comparing this with the pictures above, we see this bijection induces an isomorphism of spans $PLP\cong LPL$. So, we have derived the Yang–Baxter isomorphism from the axioms of projective plane geometry!

The above discussion helps illuminate the occurrence of the Yang–Baxter equation in the generators and relations description of the Hecke algebra. We have seen that the categorified setting allows us to view these equations as isomorphisms of spans of G-sets. As such, these Yang–Baxter operators satisfy an equation of their own—the Zamolodchikov tetrahedron equation [8]. However, this equation appears in the categorified $A_n$ Hecke algebra, only for $n\ge 3$. We can assign braids on four strands to the generators of the $A_3$ Hecke algebra:

where composition of spans, or multiplication in the Hecke algebra, corresponds to stacking of braid diagrams. Then we can express the Zamolodchikov equation—as an equation in the categorified Hecke algebra—in the form of a commutative diagram of braids [35,36]:

This is just the beginning of a wonderful story involving Dynkin diagrams of more general types, incidence geometries, logic, braided monoidal 2-categories [37,38], knot invariants, topological quantum field theories, geometric representation theory, and more!