%&biglatex
%January 5, 2008
%John Baez 
%Higher-Dimensional Algebra VII: Groupoidification
%in LaTeX, using macro packages including XYpic

\documentclass{article} 

\hfuzz=6pt
\usepackage{amsmath, amsthm, amssymb} 
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{euscript}
\usepackage{latexsym}
\usepackage[all, knot]{xy}
\usepackage{amsfonts,amssymb}
\usepackage{hyperref}

\newcommand{\hepth}[1]{\href{http://arxiv.org/abs/hep-th/#1}{{\tt arXiv:hep-th/#1}}}

\newcommand{\mathph}[1]{\href{http://arxiv.org/abs/math-ph/#1}{{\tt arXiv:math-ph/#1}}}

\newcommand{\Math}[1]{\href{http://arxiv.org/abs/math/#1}{{\tt arXiv:math/#1}}}

\newcommand{\MMath}[2]{\href{http://arxiv.org/abs/math.#1/#2}{{\tt arXiv:math.#1/#2}}}

\newcommand{\tto}{\nrightarrow}
\newcommand{\To}{\Rightarrow}
\renewcommand{\To}{\Rightarrow}

\newcommand{\Over}{/\!/}
\newcommand{\et}{\hspace{-0.08in}{\bf .}\hspace{0.1in}}
\newcommand{\im}{{\rm im}}
\renewcommand{\hom}{{\rm hom}}
\newcommand{\aut}{{\rm aut}}

% categories and 2-categories
\newcommand{\Nice}{\mathrm{Nice}}
\newcommand{\Fin}{\mathrm{Fin}}
\newcommand{\Span}{\mathrm{Span}}
\newcommand{\Gpd}{\mathrm{Gpd}}
\newcommand{\Set}{\mathrm{Set}}
\newcommand{\Cat}{\mathrm{Cat}}
\newcommand{\Vect}{\mathrm{Vect}}
\newcommand{\Hecke}{\mathrm{Hecke}}
\newcommand{\Perm}{\mathrm{Perm}}

\newcommand{\tensor}{\otimes}
\newcommand{\maps}{\colon}
\newcommand{\inv}{{\rm inv}}
\newcommand{\op}{{\rm op}}
\newcommand{\hf}{\frac{1}{2}}
\newcommand{\iso}{\cong}
\newcommand{\ad}{{\rm ad}}
\newcommand{\tr}{{\rm tr}}
\renewcommand{\deg}{{\rm deg}}
\newcommand{\we}{\wedge}
\renewcommand{\c}{{\mathfrak c}}
\newcommand{\g}{{\mathfrak g}}
\newcommand{\h}{{\mathfrak h}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\scs}{\scriptstyle}

\newtheorem{theorem}{Theorem}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{remark}[theorem]{Remark}

\hfuzz=10pc

\title{Higher-Dimensional Algebra VII: Groupoidification}

\author{John C.\ Baez \\
Department of Mathematics,  University of California\\
Riverside, California 92521 \\
USA \\
email: baez@math.ucr.edu}

\date{\today}

\begin{document}
\bibliographystyle{plain}
\maketitle 

\begin{center}
\textbf{DRAFT VERSION ONLY}
\end{center}

This is a very rough draft, which only attempts to lead up to
a precise statement of
the Fundamental Theorem of Hecke Operators Theorem \ref{fundamental}.
We include neither proofs, which will eventually be provided, nor
motivation --- which will also be provided, but for now can be
found online in the reams
of material associated to the Fall 2007 seminar on Geometric 
Representation Theory \cite{Fall2007}.

\section{Degroupoidification}

The idea of groupoidification is to take interesting pieces
of linear algebra, such as the representation theory of finite
groups, and systematically replace vector spaces by groupoids
and linear operators by spans of groupoids.  Equations between
linear operators then become interesting maps between spans of
groupoids.  

So, groupoidification is a special form of categorification.
As always, the hope is that we are not just making stuff up,
but \textit{revealing} structures in mathematics that were 
\textit{already implicitly there}.   And, as always, this is
not a systematic process --- but its reverse \textit{is} a
systematic process.  We call this `degroupoidification'.

Degroupoidification is a process going from spans of 
groupoids to linear operators between vector spaces.  
To avoid issues of analysis we limit ourselves here to
spans of finite groupoids.

\begin{lemma}  There is a weak 2-category $\Fin\Span$ where:
\begin{itemize}
\item the objects are finite groupoids, 
\item a morphism $S \maps X \tto Y$ is a span of
finite groupoids
\[ 
\xymatrix{ 
& S \ar[dl] \ar[dr] & \\ X & & Y } 
\] 
\item
a 2-morphism $f\maps S \To S'$ is a diagram  
\[ 
\xymatrix{ 
S \ar[d] \ar[drr] \ar[rr] & & S' \ar[dll] \ar[d] \\ X & & Y } 
\] 
commuting up to natural isomorphism,
\item
composition of morphisms is done via weak pullback of spans,
\item 
composition of 2-morphisms is done in the obvious way,
\item
all identity morphisms and 2-morphisms, left and right 
unit laws, and associators are the obvious things.
\end{itemize}
\end{lemma}

(Note: To obtain a 
bicategory $\Fin\Span$, we must arbitrarily choose
a weak pullback for each composable pair of spans.  A more
principled --- but ultimately equivalent --- approach would avoid 
these choices and yield, for example, an opetopic bicategory. 
We prefer to use traditional bicategories 
because they are more familiar.  So, henceforth we use `weak 2-category'
as a synonym for `bicategory')

Next, we fix a field $k$ of characteristic zero.  
Let $\Fin\Vect$ be the category whose
objects are finite-dimensional vector spaces and whose morphisms
are linear operators.  We shall often think of 
this as a weak 2-category with only identity 2-morphisms.  

Our goal is now to describe a weak 2-functor
$$ D \maps \Fin\Span \to \Fin\Vect $$
called `degroupoidification'.
For this we need a bit of information about the zeroth homology 
of groupoids.  This can be seen either as a covariant functor, 
via `pushforward', or as a contravariant one, via `transfer'.
(The name `transfer' is traditional in the homology theory of
spaces; sufficiently nice maps between spaces give not only 
a pushforward in homology but also a `transfer' going back.)

Let $\Fin\Gpd$ be the weak 2-category 
of finite groupoids, functors and natural isomorphisms.
Given $X \in \Fin\Gpd$, we define its {\bf zeroth homology}
with coefficients in $k$, $H_0(X)$, to be the free vector space
on the set of isomorphism classes of objects of $X$.  Given 
a functor $f \maps X \to Y$ between finite groupoids, we define 
its {\bf pushforward}
\[
f_\ast \maps H_0(X) \to H_0(Y) 
\]
by 
\[   
 f_\ast [x] = [f(x)]  
\]
where $[x]$ is the isomorphism class of $x \in X$.  It is easy
to check that naturally isomorphic functors give the same pushforward,
and:

\begin{lemma}  There is a weak 2-functor from $\Fin\Gpd$ to 
$\Fin\Vect$ sending:
\begin{itemize}
\item
$X \in \Fin\Gpd$ to its zeroth homology $H_0(X) \in \Fin\Vect$,
\item
$f \maps X \to Y$ to its pushforward $f_\ast \maps H_0(X) \to H_0(Y)$,
\item
$\alpha \maps f \To g$ to the identity.
\end{itemize}
\end{lemma}

Given a functor $f \maps X \to Y$ between finite groupoids,
we can also define a linear operator
\[
f^! \maps H_0(Y) \to H_0(X) 
\]
called its {\bf transfer}.  This maps each isomorphism class
$[y]$ of objects in $Y$ to a cleverly weighted sum over objects
in $X$ that map to it --- or more precisely, to objects isomorphic
to it.  The `clever weighting' involves the concept
of groupoid cardinality \cite{feynman}, but we will supress
that concept here for the sake of efficiency.  We still need
a little notation:

\begin{defn} Given a category $X$, let $\underline{X}$ be
the set of isomorphism classes of objects of $X$.
\end{defn}

\begin{defn} Given a category $X$ and an object $x \in X$, let
$\aut(x)$ be the group of automorphisms of $x$.  
\end{defn}

\begin{defn} Given a functor $f \maps X \to Y$ and an object
$y \in Y$, let $f^{-1}(y)$ be the {\bf essential preimage} of
$y$, that is, the full subcategory of $X$ consisting of all
objects that $f$ maps to objects isomorphic to $y$.
\end{defn}

We define the transfer by:
\[
f^![y] = |\aut(y)|
\sum_{[x] \in \underline{f^{-1}(y)}} \frac{[x]}{|\aut(x)|}
\]
Maybe it's better to say this in words too.  To compute
$f^![y]$, we sum over objects $x \in X$ mapping to objects 
isomorphic to $y$, picking one object $x$ from each isomorphism
class.  This sum is cleverly weighted by factors involving
the size of various automorphism groups.  I hope I have these
factors right!  The first way to check it is to prove this
lemma:

\begin{lemma}  There is a contravariant weak 2-functor from 
$\Fin\Gpd$ to $\Fin\Vect$ sending:
\begin{itemize}
\item
$X \in \Fin\Gpd$ to its zeroth homology $H_0(X) \in \Fin\Vect$,
\item
$f \maps X \to Y$ to its transfer $f^! \maps H_0(Y) \to H_0(X)$,
\item
$\alpha \maps f \To g$ to the identity.
\end{itemize}
\end{lemma}

Now for the punchline:

\begin{prop}
\label{degroupoidification}
There is a weak 2-functor, {\bf degroupoidification}, 
$$ D \maps \Fin\Span \to \Fin\Vect $$
sending:
\begin{itemize}
\item
any object $X \in \Fin\Span$ to its zeroth homology 
$H_0(X) \in \Fin\Vect$,
\item
any morphism
\[ 
\xymatrix{ 
& S \ar[dl]_{p} \ar[dr]^{q} & \\ X & & Y } 
\] 
to the operator $q_* p^! \maps H_0(X) \to H_0(Y)$,
\item
any 2-morphism $\alpha \maps S \To S'$ to the identity.
\end{itemize}
\end{prop}

Note that since $\Fin\Vect$ is a weak 2-category with only
identity morphisms, this is all the information we need to
provide to describe a weak 2-functor.
The main job in proving the lemma is showing that
composite spans get sent to composite linear operators.
This is where the `clever weighting' becomes important: the
lemma works when you get this weighting right.

\section{Nice Topoi}

It is profitable to study groups, or more generally 
groupoids, by their actions on sets.   In fact, any groupoid
has a topos of actions, which serves as a kind of stand-in
for the groupoid itself.  So, the degroupoidification process
we described above can also be thought of as a process sending
such a topos to a vector space.  

As in the previous section, we will impose finiteness restrictions to 
avoid some technicalities that complicate things.   If $X$ is a finite 
groupoid, there is a category $\Set^X$ whose objects are
actions of $X$ on sets --- that is, functors
\[    
A \maps X \to \Set 
\]
This category is a topos of some very nice sort: 

\begin{defn} A category is a {\bf nice topos} 
if it is equivalent,
as a category, to $\Set^X$ for some finite groupoid
$X$.
\end{defn}
\noindent
Note: the reader does not need to know what a `topos' is to 
make sense of the above definition.
We would naturally like an intrinsic characterization of nice topoi.

A functor $f \maps X \to Y$ between finite groupoids induces
a `pullback' map
\[
f^* \maps \Set^Y \to \Set^X
\]
but this has a left adjoint
\[
f_* \maps \Set^X \to \Set^Y
\]
So, any span of finite groupoids
\[ 
\xymatrix{ 
& S \ar[dl]_{p} \ar[dr]^{q} & \\ X & & Y } 
\] 
gives rise to a functor
\[   q_* p^* \maps \Set^X \to \Set^Y
\]

\begin{defn} A functor between nice topoi is {\bf nice} 
if it is naturally isomorphic to one of the form
\[   q_* p^* \maps \Set^X \to \Set^Y 
\]
for some span of finite groupoids
\[ 
\xymatrix{ 
& S \ar[dl]_{p} \ar[dr]^{q} & \\ X & & Y } 
\] 
\end{defn}

\begin{defn} A natural isomorphism between nice
functors is {\bf nice} if it is equal to one arising
from an equivalence of spans of finite groupoids.
\end{defn}
We would also like intrinsic characterizations of nice functors
and nice natural transformations. 

There is a 2-category $\Nice$ of nice topoi, nice
functors and nice natural isomorphisms, and:
 
\begin{lemma} 
\label{equivalence}
There is an equivalence of weak 2-categories
\[         J \maps \Fin\Span \to \Nice \]
sending each finite groupoid $X$ to the nice topos $\Set^X$.
\end{lemma}

Combining this and Proposition \ref{degroupoidification}, we
get a weak 2-functor from $\Nice$ to $\Fin\Vect$.  Namely, we
choose a weak inverse to $J$, say
\[         K \maps \Nice \to \Fin\Span \]
This gives an alternative form of degroupoidification, 
\[   DK \maps \Nice \to \Fin\Vect .\]  

\section{Hecke Theory}

We now apply degroupoidification to an important example.
Suppose $G$ is a finite group.  Given $G$-sets
$A$ and $B$, there is an obvious notion of a morphism from 
$A$ to $B$, namely a $G$-invariant map $f \maps A \to B$.
However, it turns out to be much more interesting to consider
a different sort of morphism, namely a span of $G$-sets
\[ 
\xymatrix{ 
& S \ar[dl] \ar[dr] & \\ A & & B } 
\] 
where the arrows are $G$-equivariant maps.
But in fact, such spans are the objects of a nice topos!

To see this, recall the concept of `action groupoid' or
`weak quotient':

\begin{defn}
Given a set
$S$ with an action of a group $G$ on it, the {\bf weak
quotient} $S\Over G$ is the groupoid
with elements of $S$ as objects, and pairs $(g,s) \in G \times S$
as morphisms from $s$ to $gs$, where the composite of 
$(g,s) \maps s \to s'$ and $(g',s') \maps s' \to s''$ is
defined to be $(g'g, s) \maps s \to s'$.  
\end{defn}

\begin{lemma}
Given a set $S$ with an action of a group $G$ on it, the category of 
$G$-sets over $S$ is equivalent to the category $\Set^{S\Over G}$.
When $G$ and $S$ are finite, so is $S\Over G$, so 
$\Set^{S\Over G}$ is a nice topos.   
\end{lemma}

So, given finite $G$-sets
$A$ and $B$, we can think of a span of $G$-sets
\[ 
\xymatrix{ 
& S \ar[dl] \ar[dr] & \\ A & & B } 
\] 
as a $G$-set over $A \times B$.  By the above lemma, this is an object of 
the nice topos $\Set^{(A \times B)//G}$.

So, unravelling what we've done, we see:

\begin{lemma}
\label{hom-topos}
Suppose $G$ is a finite group and let $A$ and $B$ be finite $G$-sets.
Then there is a nice topos $\Set^{(A \times B)//G}$ where:
\begin{itemize}
\item
objects are spans of $G$-sets
\[ 
\xymatrix{ 
& S \ar[dl] \ar[dr] & \\ A & & B } 
\] 
\item morphisms are commuting diagrams
\[ 
\xymatrix{ 
S \ar[d] \ar[drr] \ar[rr] & & S' \ar[dll] \ar[d] \\ A & & B } 
\] 
\end{itemize}
\end{lemma}

As mentioned, we want to think of a span of $G$-sets from 
$A$ to $B$ as a kind of morphism from $A$ to $B$.  The morphisms
mentioned in the above lemma should thus be 2-morphisms between these!
We can make this more precise:

\begin{lemma} 
\label{hecke-bicategory}
For any finite group $G$ there is a weak 2-category 
enriched over $\Nice$, the {\bf Hecke bicategory} of $G$, 
denoted $\Hecke(G)$, where:
\begin{itemize}
\item 
objects are finite $G$-sets,
\item 
given finite $G$-sets $A$ and $B$, $\hom(A,B)$ is
the nice topos $((A \times B)\Over G)^\Set$.
\end{itemize}
\end{lemma}
This is not a very precise statement of the lemma, since we 
haven't said how composition and the like are supposed to work!  
We also need to say how $\Nice$ is a \textit{monoidal} bicategory,
in order to speak of bicategories enriched over it.  
But for now, let us combine Lemmas \ref{hom-topos} and 
\ref{hecke-bicategory}, just to see where we stand:

\begin{lemma} 
\label{hecke-bicategory-2}
For any finite group $G$, the weak 2-category $\Hecke(G)$ has:
\begin{itemize}
\item 
finite $G$-sets as objects
\item 
spans of $G$-sets as morphisms
\[ 
\xymatrix{ 
& S \ar[dl] \ar[dr] & \\ A & & B } 
\] 
\item commuting diagrams  
\[ 
\xymatrix{ 
S \ar[d] \ar[drr] \ar[rr] & & S' \ar[dll] \ar[d] \\ A & & B } 
\] 
as 2-morphisms.
\end{itemize}
\end{lemma}
This should make it clearer how composition works: we
use the usual composition of spans, via pullback.  
Indeed, it should be pretty obvious how $\Hecke(G)$ is a
bicategory.  So, the `tricky part' is just showing that
$\Hecke(G)$ is enriched over $\Nice$.

But now let us plunge ahead and state the Fundamental Theorem
of Hecke Algebras!  For this, we first recall that by Lemma
\ref{equivalence}, the weak 2-functor
\[         J \maps \Fin\Span \to \Nice \]
has a weak inverse 
\[         K \maps \Nice \to \Fin\Span \]
In fact $J$ is monoidal (with respect to some obvious 
monoidal structures on $\Fin\Span$ and $\Nice$), and so therefore
is $K$.  This allows us to do `base change' and convert any
bicategory $B$ enriched over $\Nice$ into a bicategory
$\overline{K}(B)$ enriched over $\Fin\Span$.  Here we
use an overline to denote base change with respect to some weak monoidal
2-functor.

Similarly, degroupoidification
\[      D \maps \Fin\Span \to \Fin\Vect \]
is monoidal.  So, we can convert any bicategory $B$ enriched over
$\Fin\Span$ into a bicategory $\overline{D}(B)$ enriched over $\Fin\Vect$.  

We can do both sorts of base change starting with the Hecke
bicategory of $G$: $\Hecke(G)$ is enriched over $\Nice$,
so $\overline{D}(\overline{K}(\Hecke(G)))$ is enriched over $\Fin\Vect$.  

The Fundamental Theorem of Hecke Operators reveals this
$\Fin\Vect$-enriched category to be something very familiar:

\begin{defn}
Let $\Perm(G)$ be the category where:
\begin{itemize}
\item Objects are 
{\bf permutation representations} of $G$: that is, representations
of $G$ arising from actions of $G$ on finite sets via the `free vector
space' functor $F \maps \Fin\Set \to \Fin\Vect$.
\item Morphisms are {\bf intertwining operators} --- that is,
$G$-equivariant linear operators.
\end{itemize}
\end{defn}

\begin{theorem} 
\label{fundamental}
For any finite group $G$,
\[  \overline{D}(\overline{K}(\Hecke(G))) \simeq \Perm(G)  \]
\end{theorem}

The point of this theorem is that the familiar category $\Perm(G)$ is 
obtained from the Hecke bicategory $\Hecke(G)$ by 
a `degroupoidification' process, namely $\overline{D}$, after
a slight change in viewpoint, namely $\overline{K}$.

\subsection*{Acknowledgements}
The material presented here was developed in close collaboration
with James Dolan and Todd Trimble.  We also thank the other members
of the Geometric Representation Theory Seminar, including 
our notetakers, Alex
Hoffnung and Apoorva Khare and our cameraman, Prasad Senesi.
We also thank Tom Leinster and Urs Schreiber
for catching some errors.

\begin{thebibliography}{20}

\bibitem{feynman}
J.\ Baez and J.\ Dolan, 
From finite sets to Feynman diagrams, in 
\textsl{Mathematics Unlimited -- 2001 and Beyond}, vol. 1, eds.\
Bj\"orn Engquist and Wilfried Schmid, Springer, Berlin, 2001, pp.\ 29-50.
Also available as \MMath{QA}{0004133}.

\bibitem{Fall2007}
J.\ Baez and J.\ Dolan, the 
\href{http://math.ucr.edu/home/baez/qg-fall2007/"}{Geometric 
Representation Theory Seminar}, Fall 2007. 

\end{thebibliography}

\end{document} 
