nLab
Day convolution

Idea

Just as we can convolve functions $f:M\to ℂ$ where $M$ is a group, or more generally a monoid, we can convolve functors $f:M\to \mathrm{Set}$ where $M$ is a monoidal category. So, for any monoidal category $M$, the functor category ${\mathrm{Set}}^M$ becomes a monoidal category in its own right. The tensor product in ${\mathrm{Set}}^M$ is called Day convolution, named after Brian Day.

We can generalize this idea by replacing Set with a more general cocomplete symmetric monoidal category $V$. The technical condition is that the tensor product $u\otimes v$ must preserve colimits in the separate arguments $u$ and $v$; that is, that the functors $u\otimes -$ and $-\otimes v$ must preserve colimits. This occurs when for instance $V$ is symmetric monoidal closed (so that these functors are left adjoints).

Restricted Definition

For $(C,\otimes )$ a monoidal category and $F,G:C^{\mathrm{op}}\to \mathrm{Set}$ two presheaves on $C$, their Day convolution product $F\star G$ is the presheaf given by the coend

$$F\star G:={\int }^{c,d\in C}F(c)\times G(d)\times {\mathrm{Hom}}_C(-,c\otimes d).$$F \star G := \int^{c,d \in C} F(c) \times G(d) \times Hom_C(-, c \otimes d) \,.

Properties

Let $j:C\to \mathrm{PSh}(C)$ be the Yoneda embedding.

Lemma

With $I\in C$ the tensor unit of $C$, the presheaf $j(I)$ is a unit for the Day convolution product.

Proof

Using the co-Yoneda lemma on the two coends we have

$$\begin{array}{rl}F\star j(I)& \simeq {\int }^{c,d\in C}F(c)\times {\mathrm{Hom}}_C(d,I)\times {\mathrm{Hom}}_C(-,c\otimes d)\\ & \simeq {\int }^{c\in C}F(c)\times {\mathrm{Hom}}_C(-,c\otimes I)\\ & \simeq {\int }^{c\in C}F(c)\times {\mathrm{Hom}}_C(-,c)\\ & \simeq F(-)\end{array}.$$\begin{aligned} F \star j(I) & \simeq \int^{c,d \in C} F(c) \times Hom_C(d,I) \times Hom_C(-, c\otimes d) \\ & \simeq \int^{c \in C} F(c) \times Hom_C(-, c \otimes I) \\ & \simeq \int^{c \in C} F(c) \times Hom_C(-, c) \\ & \simeq F(-) \end{aligned} \,.

Proposition

For $C$ a small monoidal category, regard the category of presheaves $(\mathrm{PSh}(C),\star ,j(I))$ as a monoidal category with tensor product the Day convolution product and unit the unit of $C$ under the Yoneda embedding $j:C\hookrightarrow \mathrm{PSh}(C)$.

Then

1. $(\mathrm{PSh}(C),\star ,j(I))$ is a closed monoidal category;

2. the Yoneda embedding constitutes a strong monoidal functor $(C,\otimes ,I)\hookrightarrow (\mathrm{PSh}(C),\star ,j(I))$.

Proof

In analogy to the cartesian closed monoidal structure on presheaves we see that if the internal hom in $\mathrm{PSh}(C)$ exists at all, (with $[F,-]$ right adjoint to $(-)\star F$) then by the Yoneda lemma it has to be given by

$$\begin{array}{rl}[F,G](c)& \simeq {\mathrm{Hom}}_C(j(c),[F,G])\\ & \simeq {\mathrm{Hom}}_C(j(c)\star F,G)\end{array}.$$\begin{aligned} [F,G](c) & \simeq Hom_C(j(c), [F,G]) \\ &\simeq Hom_C(j(c)\star F, G) \end{aligned} \,.

…

Promonoidal Day Convolution

In Day’s original paper, a stronger form of the Day convolution is discussed, in which $A$ is assumed only to be a promonoidal category.

Let $V$ be a Benabou cosmos, and $A$ a small $V$-enriched category.

Proposition

There is an equivalence of categories between the category of pro-monoidal structures on $A$ with strong pro-monoidal functors between them and the category of biclosed monoidal structures on $V^{A^{\mathrm{op}}}$ with strong monoidal functors between them.

Proof

…

Examples

• Let $C$ be a discrete category over a set, which is hence a monoid (for instance a group) with product $\cdot$.

Then the above convolution product is

$$F\star G:e\mapsto {\oplus }_{c\cdot d=e}F(c)\times G(d).$$F \star G : e \mapsto \oplus_{c \cdot d = e} F(c) \times G(d) \,.

Notice that if we regard the presheaves $F$ and $G$ here, assuming they take values in finite sets, as categorifications of $\mathbb{N}$-valued functions $\mid F\mid ,\mid G\mid :C\to \mathbb{N}$, where $\mid \cdot \mid :\mathrm{Set}\to \mathbb{N}$ is the cardinality operation on finite sets, then this reproduces precisely the ordinary convolution product of these $\mathbb{N}$-valued functions

$$\begin{array}{rlr}\mid F\star G\mid :e& \mapsto \sum _{c,d\in C}\mid F(c)\mid \times \mid G(d)\mid \times \delta (e,c\otimes d)& =\sum _{c\cdot d=e}\mid F(c)\mid \cdot \mid F(d)\mid \end{array}$$\begin{aligned} |F \star G| : e &\mapsto \sum_{c,d \in C} |F(c)| \times |G(d)| \times \delta(e, c \otimes d) & = \sum_{c \cdot d = e} |F(c)| \cdot |F(d)| \end{aligned}

This uses in particular that for every object $c\in C$ the functor

$${\mathrm{Hom}}_C(c,-)={\delta }_c$$Hom_C(c,-) = \delta_c

is in this sense the Kronecker delta-function on the set $C$ supported at $c\in C$. Precisely because by assumption $C$ has only identity morphisms.

$${\mathrm{Hom}}_C(c,d)=\{\begin{array}{cc}*& \mathrm{if}c=d\\ \varnothing & \mathrm{if}c\ne d\end{array}$$Hom_C(c,d) = \left\{ \array{ * & if c = d \\ \emptyset & if c \neq d } \right.

• There is an obvious monoidal structure on the cube category. By Day convolution this induces a monoidal structure on cubical sets. This in turn induces a monoidal structure on strict omega-categories.

• If $C$ is a large category in one universe, then its universe enlargement to a bigger universe can be given a closed monoidal structure via Day convolution.

• The semantics of linear logic obtained from Girard’s “phase spaces”, or more generally from ternary frames, is essentially Day convolution for posets.

Blog resources

• Todd Trimble on Day convolution here

Discussion

Eric says: When I see “convolution”, I think “Fourier transform”. Is Day convolution somehow related to a categorified version of Fourier transforms?

Todd says: Yes, something like that. I talk a little about this in the article on operads, in the detailed theoretical section.

The usual Fourier transform (for periodic functions) passes between Fourier coefficients $a_n$ and functions ${\sum }_n{a}_n{z}^n$ on $S^1$. One way of categorifying this is to pass from the category of functors $a:\mathbb{N}\to \mathrm{Set}$ (considered as a monoidal category with respect to Day convolution) to their so-called “analytic functors” $\hat{a}:\mathrm{Set}\to \mathrm{Set}$, mapping a set $x$ to $\hat{a}(x)={\sum }_n{a}_n\cdot x^n$. The “categorified Fourier transform” $a\mapsto \hat{a}$ takes Day convolution products to (pointwise) cartesian products.

If the “Fourier transform” is properly formulated (using enriched tensor products), then the same holds for any monoidal category in place of the discrete monoidal category $\mathbb{N}$.

AnonymousCoward says: The passage to analytic functors seems more like a z-transform or Laplace transform. In the particular case of species, it is the Laplace transform formula that applies to the analytic functor of a derivative of a species, not the Fourier transform one involving multiplication by the imaginary unit.

The use of hom above is reminiscent of the Dirac delta. Is there a connection?

John Baez says: It’s true that the passage from a sequence $a_n$ to a power series ${\sum }_n{a}_n{z}^n$ is precisely the $z$-transform. If we set $z=\exp (i\theta )$, we get the Fourier transform — but as you note this makes use of the imaginary unit $i$, which plays no evident role in Day convolution. So, the analogies Todd is discussing become most precise if we work with the $z$-transform. But the Fourier transform is closely related.

On the other hand, I’ve discovered that many ‘pure mathematicians’ don’t know about the $z$-transform — at least, not under that name. I think it’s ‘engineers’ who talk most about the $z$-transform. So, if you’re trying to explain Day convolution to pure mathematicians, it’s pedagogically best to start talking about the Fourier transform, and then later mention the $z$-transform.

In general $\mathrm{hom}$ is a categorified version of an inner product. I’m too lazy to figure out how this is related to the Dirac delta, but I would not be surprised if there were a connection.

Urs: maybe all that “anonymous coward” is looking for is this statement:

if $C$ is a discrete category (i.e. just a set regarded as a category with only identity morphisms) then a functor $Co\mathrm{Set}$ is like a $mathbZ$-valued function on the set $C$ and then for every object $c$ in $C$ the functor ${\mathrm{Hom}}_C(c,-)={\delta }_c$ is the Kronecker delta on $C$ at $c$, in that

$${\mathrm{Hom}}_C(c,d)=\{\begin{array}{cc}*& \mathrm{if}c=d\\ \varnothing & \mathrm{if}c\ne d\end{array}$$Hom_C(c,d) = \left\{ \array{ * & if c = d \\ \emptyset & if c \neq d } \right.

I have added this remark now explicitly to the entry above.