# Co-ends as a trace operation on profunctors

The n-lab site on profunctors (http://ncatlab.org/nlab/show/profunctor) describes profunctor composition as using a co-end to "trace out" the connecting variable:

$F\circ G := \int^{d\in D} F(-, d) \times G(d, -)$

Naturally, one could picture for more general profunctors, $\psi : A \times B^{op} \times C \times D \rightarrow Set$, $\phi : B \times E^{op} \rightarrow Set$ a more generalised composition as co-end'ing together an input from one with an output from the other:

$\xi := \int^{b \in B} \psi(-,b,-,-) \times \phi(b,-)$

This then looks a lot like contraction of tensors:

$\xi_{e}^{a,c,d} := \sum_{b\in B} \left( \psi_{b}^{a,c,d} \phi_{e}^{b} \right)$

Even in the use of the language "trace out" (and the fact that both operations form abstract trace operations $Tr(-)$ in their respective traced monoidal categories), this analogy seems to be implied. This also seems to be a useful way to think about profunctor composition, and it appears quite feasible that tensor contraction could be described as a co-end of suitably-enriched profunctors. However, it doesn't seem obvious how to go about unifying these two operations. So, my question is:

To what extent can the analogy between tensor contraction and profunctor composition be made precise?

-
Todd's answer is exactly right. However, if you can make precise the idea of "describing tensor contraction as a coend of suitably-enriched profunctors" then I think category theory would be greatly indebted to you. Many people have thought that there should be such a thing, but as far as I know, no one has managed to make it work. – Mike Shulman Mar 28 '11 at 21:25
Chalk one up to wishful thinking. :) There must be a deeper connection than the observation that both are compact closed. I can think of a few categories (e.g. 2-Cob, and Rel with disjoint union) with traces that don't look like sums over some kind of indexing object, so there should be something more to say here. Perhaps really understanding co-ends (and even partial traces for that matter!) can shed some light on things. – Aleks Kissinger Mar 29 '11 at 0:32

The connection can be made precise via the notion of compact closure for symmetric monoidal structures.

Recall that a symmetric monoidal category $C$ is compact closed if every object $c$ has a right adjoint $c^\ast$, meaning that there are unit and counit arrows $\eta: I \to c^\ast \otimes c$ and $\varepsilon: c \otimes c^\ast \to I$ satisfying triangular equations ($I$ is the monoidal unit; the idea is that $c^\ast \otimes -$ is right adjoint to $c \otimes -$). The classical example is of course the category of finite-dimensional vector spaces: the counit $V \otimes V^\ast \to k$ is given by evaluation, and the unit $k \to V^\ast \otimes V$ takes the unit element $1 \in k$ to $\sum_i f^i \otimes e_i$ for any chosen basis $e_i$ and dual basis $f^i$.

In such a situation, there are various equivalent ways of considering morphisms $f: b \to c$. By the adjunction, they are in natural bijection with morphisms $I \to b^\ast \otimes c$. (I'll call this the 'right' picture.) By taking advantage of the symmetry of the tensor, it's also true that one can switch things around and give an adjunction $c^\ast \dashv c$, and thus morphisms $f: b \to c$ will also be in natural bijection with morphisms $b \otimes c^\ast \to I$ (the 'left' picture). Also in this situation, one can define an abstract trace of an endomorphism $f: b \to b$ by the formula

$$Tr(f) = (I \stackrel{unit}{\to} b \otimes b^\ast \stackrel{f \otimes 1_{b^\ast}}{\to} b \otimes b^\ast \stackrel{counit}{\to} I)$$

which returns the classical trace for endomorphisms on a finite-dimensional vector space. Continuing with this, the composition of two morphisms in the right picture, say $f: I \to b^\ast \otimes c$ and $g: I \to c^\ast \otimes d$, is obtained by 'tracing out':

$$I \stackrel{f \otimes g}{\to} b^\ast \otimes c \otimes c^\ast \otimes d \stackrel{1_{b^\ast} \otimes \varepsilon \otimes 1_d}{\to} b^\ast \otimes d$$

which is to say composing with the counit in a tensor sandwich.

Now, the bicategory of small categories and profunctors is a compact closed bicategory, meaning that it is a symmetric monoidal bicategory (the tensor being given at the object level by taking cartesian products), and every object $C$ has a right biadjoint, which turns out to be $C^{op}$. If we think of a profunctor from $C$ to $D$ as essentially the same thing as a cocontinuous functor

$$Set^{C^{op}} \to Set^{D^{op}},$$

then the unit $1 \to C^{op} \otimes C$ in $Prof$ corresponds to the unique (up to iso) cocontinuous functor

$$Set \to Set^{C^{op} \times C}$$

that sends the terminal object $1$ to $\hom_C$. The counit $C \otimes C^{op} \to 1$ corresponds to a cocontinuous functor

$$Set^{C \times C^{op}} \to Set$$

which sends a functor $F: C \times C^{op} \to Set$ to the coend $\int^c F(c, c)$. Thus, composition of profunctors in the right picture will involve a tracing out by applying a coend operation to the middle two factors.

-
Ah, you beat me by a few minutes. (-: – Mike Shulman Mar 28 '11 at 21:23
This reminds me of something a colleague of mine was pondering a while back... For a category C, do you know what the set COEND^d [ hom(d,d) ] = cap o cup = tr(1_C) represents? For finite-dimensional vector spaces, this is always dimension, so this seems like it could be an important invariant of a category. – Aleks Kissinger Mar 29 '11 at 0:38
It's called the trace of a category, and as you point out it's a kind of categorified dimension. So yes, it's the set of "necklaces", i.e., the set of equivalence classes of endomorphisms $h: x \to x$ where equivalence is generated by the relation $f g \sim g f$ where $f: x \to y$ and $g: y \to x$. I don't know that I can say it in a more enlightening way than that, but one can work it out in specific cases. For example, the set of necklaces for the category of finite sets is the set of finite permutations (hint: factorize $h$ as epi $f$ followed by mono $g$, put $h_1 = f g$; iterate). – Todd Trimble Mar 29 '11 at 2:02
Sorry, I should have said that the trace of Fin is the set of finite permutations considered up to conjugation, which we can identify with the set of finite partitions. – Todd Trimble Mar 29 '11 at 14:03
Simon Willerton has a nice set of slides on the subject: simonwillerton.staff.shef.ac.uk/ftp/TwoTracesBeamerTalk.pdf – Mike Stay Jun 27 '11 at 23:32