A nuclear adjunction between Poly and Dir

Abstract

There are at least two interesting kinds of maps between bundles: “forward-forward” maps and “forward-backward” maps. That is, both kinds go forward on the base, but the first kind also goes forward on the fibers, whereas the second kind goes backwards on the fibers. In a paper with David Jaz Myers, we showed (for bundles of sets) that the first category is equivalent to \mathbf{Dir}, the category of Dirichlet polynomials, which are sums \sum_{b:B}(E_b)^\mathcal{y} of representables \mathbf{Set}^\textnormal{op}\to\mathbf{Set}; the second category is equivalent to \mathbf{Poly}, the category of ordinary (Descartes) polymomials, which are sums \sum_{b:B}\mathcal{y}^{E_b} of representables \mathbf{Set}\to\mathbf{Set}.

Recently I realized that for any set X, there’s an adjunction L_X\colon\mathbf{Dir}\rightleftarrows\mathbf{Poly}\colon R_X. Moreover, when |X|\geq 2 has at least two elements, this adjunction is nuclear, i.e. it’s both monadic and comonadic. In particular, this means that you can model \mathbf{Dir} inside of \mathbf{Poly} as the coalgebras for a certain comonad on \mathbf{Poly}, and you can similarly model \mathbf{Poly} inside of \mathbf{Dir} as the algebras for a monad on \mathbf{Dir}. I’m not sure if this has any practical applications, but it’s at least theoretically interesting. And when X=0, I’ll show how the coalgebras model “sets with elements marked for deletion”.

1 Introduction

I’ve been thinking about polynomial functors for a few years now, and at the beginning of that time I was also thinking about Dirichlet polynomials. The category \mathbf{Poly} has objects as on the left, and the category \mathbf{Dir} has objects as on the right: 3\mathcal{y}^5+2\mathcal{y}^2+4:\mathop{\mathrm{Ob}}(\mathbf{Poly}) \qquad\text{and}\qquad 3\cdot 5^\mathcal{y}+2\cdot2^\mathcal{y}+4\cdot 0^\mathcal{y}:\mathop{\mathrm{Ob}}(\mathbf{Dir}) I wrote a couple of short notes with David Jaz Myers about these things, e.g. that the category of Dirichlet polynomials forms a topos. Indeed, it is equivalent to the topos of functions E\to B. That is, both \mathbf{Dir} and \mathbf{Poly} have interpretations as categories of bundles in \mathbf{Set}, but with different sorts of maps: \mathbf{Dir} maps are forwards on base and forwards on fibers, whereas \mathbf{Poly} maps are forwards on base and backwards on fibers. I’ll explain this more in the next section.

Anyway, I haven’t thought much about \mathbf{Dir} for a while, but a few days ago I found a bunch of adjunctions L_X\colon\mathbf{Dir}\rightleftarrows\mathbf{Poly}\colon R_X one for every X:\mathbf{Set}. Moreover, when X has at least two elements, this adjunction is a nuclear adjunction, i.e. it’s both monadic and comonadic. That means that \mathbf{Poly} is equivalent to the category of algebras for the induced monad on \mathbf{Dir} and that \mathbf{Dir} is equivalent to the category of coalgebras for the induced comonad on \mathbf{Poly}.

I’ll try to keep this blog post pretty short. First I’ll describe \mathbf{Dir} and \mathbf{Poly} in terms of bundles. Then I’ll give the two functors L_X and R_X and say why they’re adjoint. Then I’ll say why the adjunction is both monadic and comonadic (i.e. nuclear). Finally, I’ll show what happens when X=0, and how the coalgebras for the comonad on \mathbf{Poly} correspond to “sets with elements marked for deletion”.

2 \mathbf{Dir} and \mathbf{Poly} in terms of bundles

A bundle of sets is just a function \pi\colon E\to B; here E is called the total space and B is called the base space. For each b:B, denote the fiber by E_b\coloneqq\pi^{-1}(b)\subseteq E. So we could denote this bundle by \begin{CD} \sum_{b:B}E_b \\@VV{\pi}V \\B \end{CD} Here’s a picture of the bundle where the base B=4 has four elements and the four fibers are E_1=4, E_2=1, E_3=2, and E_4=0: ¹

Note that for any function f\colon B\to B', we can take the pullback of \pi'\colon E'\to B' and in so doing get another bundle, denoted f^*(\pi'), sitting over B: \begin{CD} \sum\limits_{b:B}E'_{f(b)} @>>> \sum\limits_{b':B'}E'_{b'} \\@V{f^*(\pi')}VV @VV{\pi'}V \\B @>>{f}> B' \end{CD}

What’s the appropriate kind of map between bundles? The most obvious choice to a category theorist would be a commutative square: \begin{CD} E @>>> E' \\@V{\pi}VV @VV{\pi'}V \\B @>>{f}> B' \end{CD} This is equivalent to a map from \pi to the pullback bundle f^*(\pi'): \begin{CD} \sum\limits_{b:B}E_b @>{f^\natural}>> \sum\limits_{b:B}E'_{f(b)} @>>> \sum\limits_{b':B'}E'_{b'} \\@V{\pi}VV @V{f^*\pi}VV @VV{\pi'}V \\B @= B @>>{f}> B' \end{CD} \tag{1} (where the right-most square is a pullback). These go forwards on the base, i.e. we have f\colon B\to B', and forwards on the fibers: for each b:B, there is an induced function f^\natural_b\colon E_b\to E'_{f(b)}. Another kind of map is forwards on the base and backwards on the fibers: \begin{CD} \sum\limits_{b:B}E_b @<{f^\sharp}<< \sum\limits_{b:B}E'_{f(b)} @>>> \sum\limits_{b':B'}E'_{b'} \\@V{\pi}VV @V{f^*\pi}VV @VV{\pi'}V \\B @= B @>>{f}> B' \end{CD} \tag{2} (where again the right-most square is a pullback). The backwards part is a map from the pullback bundle f^*(\pi') back to \pi, i.e. a function f^\sharp\colon f^*(\pi')\to\pi.

It turns out that we can represent a bundle as both a Dirichlet functor \mathbf{Set}^\textnormal{op}\to\mathbf{Set} and as a polynomial functor \mathbf{Set}\to\mathbf{Set}. Namely \pi\colon E\to B corresponds to the following objects in \mathbf{Dir} and \mathbf{Poly}: d_\pi\coloneqq\sum_{b:B}(E_b)^\mathcal{y} \qquad\text{and}\qquad p_\pi\coloneqq\sum_{b:B}\mathcal{y}^{E_b} The maps (natural transformations) d_\pi\to d_{\pi'} between Dirichlet functors can be identified with the forwards-forwards bundle maps (1), and the maps (natural transformations) p_\pi\to p_{\pi'} between polynomial functors can be identified with the forwards-backwards bundle maps (2).

3 Adjunctions between \mathbf{Dir} and \mathbf{Poly}

In this section we provide an adjunction between \mathbf{Dir} and \mathbf{Poly} for each X:\mathbf{Set}. But we begin with something more basic: an adjunction between \mathbf{Set}^\textnormal{op} and \mathbf{Set} for each X:\mathbf{Set}. Clearly, mapping into X constitutes a functor X^-\colon\mathbf{Set}^\textnormal{op}\to\mathbf{Set} given by A\mapsto\mathbf{Set}(A,X). This is part of an adjunction X^{-}\colon\mathbf{Dir}\rightleftarrows\mathbf{Poly}\colon X^{-}. For example, when X=2, each of these functors 2^- is the power-set. Anyway, the idea is that we’re going to apply this adjunction to the fibers of bundles.

So let’s describe the functor L_X\colon\mathbf{Dir}\to\mathbf{Poly}. On objects it is given by \sum_{b:B}(E_b)^\mathcal{y}\quad\mapsto\quad\sum_{b:B}\mathcal{y}^{\left(X^{E_b}\right)}. In other words, the bundle E\to B is sent to a bundle with the same base, but where the fiber E_b has been replaced with the fiber X^{E_b}. A Dirichlet (forwards-forwards) map \pi\to\pi' of bundles as in (1) includes a function f\colon B\to B' and a function E_b\to E'_{f(b)} for each b:B; the latter induces a function X^{E'_{f(b)}}\to X^{E_b}, and hence a polynomial (forwards-backwards) map L_X(\pi)\to L_X(\pi') of bundles, as in (2).

The functor R_X\colon\mathbf{Poly}\to\mathbf{Dir} is quite similar. On objects it is given by \sum_{b:B}\mathcal{y}^{E_b}\quad\mapsto\quad\sum_{b:B}\big(X^{E_b}\big)^\mathcal{y}. In other words, the bundle E\to B is again sent to a bundle with the same base, but where the fiber E_b has been replaced with the fiber X^{E_b}. A polynomial (forwards-backwards) map \pi\to\pi' of bundles as in (2) includes a function f\colon B\to B' and a function E'_{f(b)}\to E_{b} for each b:B; the latter induces a function X^{E_b}\to X^{E'_{f(b)}}, and hence a Dirichlet (forwards-forwards) map R_X(\pi)\to R_X(\pi') of bundles, as in (1).

To see that these functors are adjoint, L_X\colon\mathbf{Dir}\rightleftarrows\mathbf{Poly}\colon R_X \tag{3} consider the bundle \pi\colon E\to B as an object of \mathbf{Dir} represented by \sum_{b:B}(E_b)^\mathcal{y} and the bundle \pi'\colon E'\to B' as an object of \mathbf{Poly} represented by \sum_{b':B'}\mathcal{y}^{E'_{b'}}. We calculate: \begin{aligned} \mathbf{Dir}(\pi,R_X(\pi'))&\cong \mathbf{Dir}\left(\sum_{b:B}(E_b)^\mathcal{y},\sum_{b':B'}\big(X^{E'_{b'}}\big)^\mathcal{y}\right)\\&\cong \prod_{b:B}\sum_{b':B'}\mathbf{Set}\left(E_b,X^{E'_{b'}}\right)\\&\cong \prod_{b:B}\sum_{b':B'}\mathbf{Set}\left(E_b\times E'_{b'},X\right)\\&\cong \prod_{b:B}\sum_{b':B'}\mathbf{Set}\left(E'_{b'},X^{E_b}\right)\\&\cong \mathbf{Poly}\left(\sum_{b:B}\mathcal{y}^{\left(X^{E_b}\right)},\sum_{b':B'}\mathcal{y}^{E'_{b'}}\right)\\&\cong \mathbf{Poly}(L_X(\pi),\pi'). \end{aligned}

Just as a minor point, I want to also note that both L_X and R_X preserve coproducts; this is unsurprising for L_X, but I don’t think I’d seen a right adjoint that preserves coproducts before.

4 Why they are monadic and comonadic

Let’s again look at the adjunction X^{-}\colon\mathbf{Dir}\rightleftarrows\mathbf{Poly}\colon X^{-}. The corresponding monad A\mapsto X^{X^A} on \mathbf{Set} is called the X-continuation monad. Whenever X has at least two elements, I’ve heard—and will herein rely on the belief—that the category of algebras for the continuations monad is equivalent to \mathbf{Set}^\textnormal{op}.

That is, suppose you had a set A and a function X^{X^A}\to A that satisfies the algebra axioms. For example, if X=2 then this function lets you turn elements of the double power set of A into elements of A, and the monad algebra axioms say that you’re doing it in a reasonable way. But how in the heck could you ever get such an A and such a function? How can you get from a subset of subsets of A to an element of A? Well one source of such A’s is X^B for some B. Indeed, it’s easy to (and we are about to) find a map of the form \tag{4} X^{X^{X^B}}\to X^B. An element of the domain is a function f\colon X^{X^B}\to X. Given one of those we’re supposed to find a function B\to X, so let’s give ourselves an element b:B and try to find an element of X. This is not so bad. We just take the function \textnormal{eval}_b\colon X^B\to X given by \textnormal{eval}_b(g)\coloneqq g(b), apply f to it, and thereby find an element of X, as desired. In other words, we have a function \textnormal{eval}\colon B\to X^{X^B}, and our desired map (4) is X^{\textnormal{eval}}\colon X^{X^{X^B}}\to X^B.

Well it turns out that any such set X^B, equipped with the map we just provided, can be shown to satisfy the algebra laws. Moreover they’re the only such things! This is a Stone-type duality when X\cong 2: the category of complete atomic boolean algebras is equivalent to \mathbf{Set}^\textnormal{op}. ² And supposedly, the same thing holds for X with more than 2 elements.

Now let’s consider the monad M_X\coloneqq R_X\circ L_X on \mathbf{Dir} and the comonad C_X\coloneqq L_X\circ R_X on \mathbf{Poly} induced by the adjunction (3). They both send the bundle \pi\colon\sum_{b:B}E_b\to B to the bundle \sum_{b:B}X^{X^{E_b}}\to B.

An algebra for the monad M_X on \mathbf{Dir} consists of a bundle \pi\colon E\to B, a function B\to B, which by the unit law must be the identity, and a function X^{X^{E_b}}\to E_b for each b:B, which by the algebra laws makes each E_b into a X^{X^-}-algebra. This means that E_b is in the image of the functor X^-\colon\mathbf{Set}^\textnormal{op}\to\mathbf{Set}, for each b:B, and hence that \pi is in the image of the functor R_X\colon\mathbf{Poly}\to\mathbf{Dir}. In other words, the adjunction (3) is monadic. To see that this adjunction is comonadic is completely analogous.

So the upshot is that \mathbf{Poly} is equivalent to the category of algebras for the monad M_X on \mathbf{Dir}, and that \mathbf{Dir} is equivalent to the category of coalgebras for the comonad C_X on \mathbf{Poly}. This is what it means for L_X\colon\mathbf{Dir}\rightleftarrows\mathbf{Poly}\colon R_X to be a nuclear adjunction.

5 What happens when the base is empty

The above story is the main subject of this post. I just want to end with a little light fun. So far we’ve focused on the case where |X|\geq 2. We’ll leave the X=1 case to the reader. In this section we’ll discuss the case where X=0 is empty. We’ll see something interesting: the coalgebras for the comonad C_0\coloneqq L_0\circ R_0 on \mathbf{Poly} are intuitively “sets with elements marked for deletion". I’ll explain what that means.

First, note that when X=0 the functors X^- and X^{X^-} are given by 0^A\coloneqq \begin{cases} 1&\textnormal{ if }A=0\\ 0&\textnormal{ if }A\neq 0 \end{cases} \qquad\text{and}\qquad 0^{0^A}\coloneqq \begin{cases} 0&\textnormal{ if }A=0\\ 1&\textnormal{ if }A\neq 0 \end{cases} An algebra for the monad M_0\coloneqq R_0\circ L_0 on \mathbf{Dir} is just a bundle where every fiber has either 0 or 1 element, in other words, it can be identified with a subset A\subseteq B. A map of algebras (A\subseteq B)\to (A'\subseteq B') consists of a function f\colon B\to B' such that f(A)\subseteq A'.

It’s more interesting to look at the category of coalgebras for the corresponding comonad C_0 on \mathbf{Poly}. The objects can again be identified with subsets D\subseteq B. ³ A map of coalgebras consists of a function f\colon B\to B' such that if f(b)\in D' then b\in D.

Think of the coalgebra (subset) D\subseteq B as a set B where elements of D are “marked for deletion”. In programming, Evan Patterson has told me that when deleting elements from a set, it generally messes up all the indexing if you actually remove them, so it’s convenient to just mark these elements as deleted. What should a map between sets with deleted elements be? Well it should be a map between the sets, with the requirement that an active element (one not marked for deletion) cannot be sent to a deleted element. Or using the contrapositive, if an element is sent to a deleted element, it must itself be deleted. This is exactly the sort of map we get between affine polynomials A\mathcal{y}+D\to A'\mathcal{y}+D', i.e. of C_0-coalgebras.

There is an induced equivalence of categories between the M_0-algebras and the C_0-coalgebras. It sends a subset A\subseteq B to its complement (B\setminus A)\subseteq B. That is, a function B\to B' that sends active elements to active elements (i.e. a map of M_0-algebras) can be identified with a function B\to B' that sends deleted elements backwards to deleted elements (i.e. a map of C_0-coalgebras).

6 Conclusion

The monadic adjunction \mathbf{Dir} \underset{\xleftarrow[R_X]{}}{\overset{\xrightarrow{L_X}}{\Rightarrow}} \mathbf{Poly} strengthens the connection between polynomial functors and Dirichlet functors. It says that each can model the other, namely as the (co-)algebras for a certain (co-)monad. It seems relatively important theoretically, but I’m not really sure what else to do with it, especially applications-wise. Maybe the (co-)Kleisli category is interesting for some reason? Anyway, I’ll leave this here in the hopes that someone can help me see some use for it or some further questions to ask!

Footnotes

1. I denote by N the N-element set \{'1','2',\ldots,'N'\}, so that 0 represents the empty set, etc. But rather than write E_{'1'}, E_{'2'}, etc., I’ve written E_1, E_2, etc., for typographical reasons.

2. Thanks to Alexander Gietelink Oldenziel for reminding me that this has a name (Stone-type duality) when X\cong 2.

3. In standard polynomial form, bundles A\to B for which each fiber is either empty or singleton, i.e. subsets A\subseteq B, can be identified with affine polynomials A\mathcal{y}+D, where B\cong A+D. The same bundle could be seen as the subset A\subseteq B or D\subseteq B, since each defines the other as its complement, D=B\setminus A and A=B\setminus D.