In the nLab, Day convolution is introduced as a generalisation of convolution of complex-valued functions, but I'm wondering how exactly to understand this. I can (just about) parse the definitions, but have absolutely no intuition or geometric insight at all. Here is my thinking so far (excuse all of the quotation marks) :

A way of thinking about simple examples of presheaves is to imagine an association: to each open set of a topological space associate a set of continuous functions on that open set (really we could obtain a group or ring structure on this set of functions, but let's ignore that for a moment and just look at set-valued presheaves).

Then a presheaf is a 'function' that maps an open set to a set of functions. So a convolution of presheaves is obtained by 'blurring' these 'functions' together.

But what this actually means is rather beyond me. The issue (for me) is twofold:

  1. What does Day convolution look like in this simple case where we take our starting category to be $\mathsf{Op}(T)$, which is the category of open sets and inclusion maps of some topological space $T$ (which is usually the motivating example for presheaves). In fact, can we even look at this example? As far as I can see, $\mathsf{Op}(T)$ doesn't admit a monoidal structure;
  2. What does Day convolution look like generally? Given some convolution of presheaves, are there any simple examples (if 1. doesn't work) that give a good intuition, where the Day convolution has a reasonably succinct description?

Edit:

  1. How does Day convolution fit in with 'regular' convolution. That is, can we recover the usual convolution from Day convolution?

I hope this question is rigorous enough, and if not then I'll try to edit it to be more so.

  • 3
    Actually, the category of open subsets has two obvious monoidal structures: intersection and union. Day convolution with respect to intersection gives the cartesian product. – Zhen Lin Feb 11 '16 at 17:06
  • 2
    @ZhenLin Generalizing, any time the monoidal product is a categorical product the Day convolution is just going to be the product of the functors. – Derek Elkins Feb 11 '16 at 17:30
  • Work through the special case where the monoidal category is discrete. – Qiaochu Yuan Feb 11 '16 at 18:15
  • @QiaochuYuan do you mean as in Derek's answer? – Tim Feb 11 '16 at 18:35
up vote 13 down vote accepted

Day convolution is a categorification of the monoid algebra construction. There is a formal analogy between the two, but one is not a literal generalisation of the other. So to address your question 3, we should not expect to recover the usual convolution from Day convolution.

Let's develop the following analogy:

\begin{array}{|c|c|} \hline \textbf{monoid algebra} & \textbf{Day convolution} \\ \hline \hline \text{set} & \text{category} \\ \hline \text{monoid} & \text{monoidal category} \\ \hline \text{ring } R & \text{monoidally cocomplete category } \mathcal{V} \\ \hline R\text{-module} & \text{cocomplete } \mathcal{V}\text{-category} \\ \hline R\text{-algebra} & \text{monoidally cocomplete } \mathcal{V}\text{-category} \\ \hline \text{free } R\text{-module on a set } X& \text{free cocomplete } \mathcal{V}\text{-category on a category } \mathcal{C}\\ R^{(X)}& [\mathcal{C}^\text{op},\mathcal{V}]\\ \hline \text{free } R\text{-algebra on a monoid } M & \text{free monoidally cocomplete } \mathcal{V}\text{-category}\\ & \text{on a monoidal category } \mathcal{A} \\ R^{(M)} \text{ with convolution product} & [\mathcal{A}^\text{op},\mathcal{V}] \text{ with Day convolution}\\ \hline \end{array}

Here a monoidally cocomplete category is a cocomplete monoidal category $\mathcal{V}$ such that $\otimes \colon \mathcal{V} \times \mathcal{V} \to \mathcal{V}$ is cocontinuous in each variable. This condition corresponds in our analogy to the distributivity of multiplication over addition in a ring.

Let $(e_x)_{x\in M}$ be the canonical basis for $R^{(M)}$, so that each element of $R^{(M)}$ can be written $f = \sum_{x} f(x) e_x$. The convolution product on $R^{(M)}$ is then determined by the requirement that $M \to R^{(M)}, x \mapsto e_x$ is a monoid homomorphism. For: \begin{equation} \begin{split} f \ast g & = \left(\sum_{x} f(x) e_x \right) \ast \left(\sum_{y} g(y) e_y \right) \\ & = \sum_{x,y} f(x)g(y) e_x \ast e_y \\ & = \sum_{x,y} f(x)g(y) e_{xy}. \end{split} \end{equation}

An analogous argument gives the formula for Day convolution. The representables $\mathcal{A}(-,A)$ provide a ''basis'' of $[\mathcal{A}^{op},\mathcal{V}]$: each object may be expressed as the canonical colimit $$F \cong \int^{A} FA \otimes \mathcal{A}(-,A).$$ The Day convolution is determined by the requirement that the Yoneda embedding $\mathcal{A} \to [\mathcal{A}^\text{op},\mathcal{V}]$ be strong monoidal. We have: \begin{equation} \begin{split} F \ast G & \cong \left(\int^{A} FA \otimes \mathcal{A}(-,A) \right) \ast \left(\int^{B} GB \otimes \mathcal{A}(-,B) \right) \\ & \cong \int^{A,B} F(A)\otimes G(B) \otimes \mathcal{A}(-,A) \ast \mathcal{A}(-,B) \\ & \cong \int^{A,B} F(A)\otimes G(B) \otimes \mathcal{A}(-,A\otimes B). \end{split} \end{equation} Note that we have used the requirement that the Day convolution product must preserve colimits in each variable.

Now, Day convolution can be defined for the more general case of a promonoidal category $\mathcal{A}$. Here we can continue our analogy and think of the promonoidal structure as providing the ''structure coefficients'' of the Day convolution product.

  • 3
    Damn, that's the answer I wanted to write – Fosco Loregian Feb 11 '16 at 22:16
  • rather a stupid question, but just slightly confused by the layout of the table: is $R^{(X)}$ just the notation for the free $R$-module on the set $X$? – Tim Feb 13 '16 at 15:49
  • 1
    Yes, and I intend its elements to be the functions $X \to R$ of finite support. – Alexander Campbell Feb 13 '16 at 20:02
  • 1
    Wow this is an amazing answer. I feel like I've gained enlightenment, not just about Day convolution, but also about the density formula (it's just expanding a functor in terms of a 'basis'!) and coends in general. On a semi-related note, I'm also very pleased to find out that Fosco Loregian has an updated and expanded version of his (co)ends paper: arxiv.org/abs/1501.02503 – L.Z. Wong Mar 6 '17 at 9:02

Hmm, a logical view of presheaves is as categorified predicates. If we choose the source category as discrete, then we can interpret the coend formula as a categorification of an existential quantification (if our presheaves only return {} or {$*$} then it will be exactly existential quantification.) A discrete monoidal category is a monoid. The coend formula then becomes: $$ \begin{align} P(x) &= \int^{(c,d)\in \mathcal{D}\times\mathcal{D}}F(c)\times G(d)\times\mathcal{D}(x,c\cdot d) \\ &= \sum(c,d):\mathcal{D}\times\mathcal{D}. F(c)\times G(d)\times (x = c\cdot d) \\ &= \exists (c,d) \in \mathcal{D}\times\mathcal{D}. F(c)\land G(d)\land (x = c\cdot d) \end{align}$$ Note that $\mathcal{D}(x,y)$ is empty except when $x = y$ in which case it is a singleton set containing only $id$. The second line is what the expression would look like in dependent type theory. The third line is what the expression would look like if we "enriched" in a partially ordered set. (Incidentially, the dependent type theory one actually does generalize to arbitrary $\infty$-groupoids and even arbitrary categories if we replace $=$ with a directed notion.)

This is probably not quite the answer you're looking for, but it might be a nice perspective to keep in your pocket. Connecting back to "standard" convolution, note that $$(f*g)(k) = \sum_{i+j=k}f(i)g(j)$$ can immediately be generalized to an arbitrary monoid for the $+$, an arbitrary commutative monoid for the $\Sigma$, and a completely arbitrary binary function for the multiplication. So there is a lot more generality in the normal convolution then generally appreciated. The continuous case isn't as easy to generalize, but then that's what the category theory is doing.

Actually, if we "enrich" in $\mathbb{R}^+$ then $\mathcal{D}$ becomes a metric space, $F$ and $G$ become $\mathbb{R^+}$-valued distance-decreasing functions, and the coend formula becomes: $$P(x) = \inf_{(c,d)} \{F(c)+G(d)+||x-c\cdot d||\}$$ (I'm not completely confident I didn't mess this one up, though I am confident some expression like this is right.)

Here's the example using open sets. The coend formula looks like: $$P(U) = \int^{(U_1,U_2)\in\mathcal{O}}F(U_1)\times G(U_2) \times (U \subseteq U1 \otimes U_2)$$

For concreteness let $F(U) = G(U) = X-U$ where $X$ is the complete space. Now, $$P(U) = \bigcup_{U\subseteq U_1\otimes U_2}(X-U_1)\times(X-U_2)$$ When $\otimes = \cap$ you can see directly that $P(U) = (X-U)\times(X-U)$ (consider when $X=\mathbb{R}^+$). (You can also show this through abstract nonsense which was my comment in reply to Zhen.) When $\otimes = \cup$ the notion isn't as clean. For the $\mathbb{R}^+$ example instead of getting a quarter plane with a square cut out of it, you get the quarter plane with a triangular corner cut out. $\cap$ gives you $P(z) = \{(x,y) | z \leq \min(x,y)\}$ while $\cup$ gives you $P(z) = \{(x,y) | z \leq x+y\}$.

  • This looks like a good answer, but it's in a language with which I am really not familiar (type theory, enriching, directed notions etc.) - this is no fault of yours though – Tim Feb 11 '16 at 18:38
  • 2
    Enriching just means replacing $\mathbf{Set}$ with some other category for the codomain of $Hom$. If we enrich in a Heyting algebra or in particular in $\mathbf{2}$, then everything gains a logical flavor. If we enrich in $\mathbb{R}^+$ then a category is a (generalized) metric space. Though, knowing dependent type theory is rather valuable, the interpretation I was most emphasizing was the logical one which should be easily understandable. If instead of $\mathcal{D}$ being discrete, it was a poset like the set of open sets, then just replace $x = c\cdot d$ with $x \subseteq c\cdot d$. – Derek Elkins Feb 11 '16 at 19:08
  • Your reply is pretty bad-ass! xD – Musa Al-hassy Feb 11 '16 at 19:21
  • I suspect but am unsure, that if you enrich in $\mathbb{R}$ in the right way you will get a generalized metric space, and you should be able to define a variant where composition and product are multiplication, identity is 1, an "empty hom-set" is represented by 0, and if $\mathcal{D} = \mathbb{Z}$ or $\mathbb{N}$ the coend might actually be a sum, and Day convolution might actually be exactly convolution, perhaps even for $\mathcal{D} = \mathbb{R}$ leading to the coend being an integral. Or this might not work out at all. – Derek Elkins Feb 11 '16 at 19:34
  • This is a really thorough answer with lots of examples - thanks! It'll take me a while to read through and digest though. – Tim Feb 11 '16 at 21:47

I don't know if this can be of help, but what I found really useful to gain an intuition behind Day convolution is the correspondence between convolution products and promonoidal structures; the two things can be identified, as every convolution arises from a single promonoidal structure (this dates back to the work of Day himself, and I stated the result in my "coend-cofriend" note, Prop. A.3; I think it's an easy exercise).

The idea behind promonoidal structures is pretty easy to understand: it's what you get if you take the definition of monoidal category, and you replace every occurrence of the word "functor" with "profunctor" (or "bimodule", "distributor", it depends on how you want to call them).

Bye, Fosco

  • 1
    This was actually along the lines of what I was originally going to say but forgot that promonoidal is what I wanted. Profunctors can be viewed as categorifications of relations and then the promonoidal structure provides support for $n$-ary relations and in particular forking structure. I.e. it allows the categorification of $R(a,(b,c))$. Day convolution is then just $P \circ (F\times G)$ where $F, G : \mathbf{1} \nrightarrow A$ and $P : A\times A \nrightarrow A$. Which, if we post-compose with $R$ we can think of as producing $S(a,b) = R((F(a), G(a)),b)$. – Derek Elkins Feb 11 '16 at 21:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.