Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: event: Polynomial Functors @ Topos

Topic: Tarmo Uustalu: "Polynomial comonads"

Tim Hosgood (Mar 16 2021 at 18:32):

Tuesday, 20:00 UTC

Tim Hosgood (Mar 16 2021 at 18:32):

Abstract:
I will discuss the category of comonoid objects in the category of polynomials, equivalently, the category of small categories and cofunctors in the sense of Aguiar. I am interested in them as a representation for polynomial comonads and update monads. I am motivated by applications of those in programming semantics. I will discuss a number of constructions with polynomial comonads and what they amount to in terms of small categories and cofunctors.

Frederick Kintanar (Mar 16 2021 at 19:54):

In David Spivak's tutorial, he mentioned a result by Ahman and Uutsulu. Looking on the Arxiv, this may be the relevant paper, although I haven't looked at it yet:
arXiv:1604.01187 doi 10.4204/EPTCS.207.5
Directed Containers as Categories
Authors: Danel Ahman, Tarmo Uustalu

There is also an earlier paper:
arXiv:1408.5809 doi 10.2168/LMCS-10(3:14)2014
When is a container a comonad?
Authors: Danel Ahman, James Chapman, Tarmo Uustalu

anuyts (Mar 18 2021 at 17:05):

So a polynomial comonad on Set is a category.

It seems that a polynomial monad on Set is an operad, where the shapes are the operations and P(s) is the arity of s, though I'm not familiar with operads. Is this a known result? The nLab states (even defines):
A (Set-based) operad is a monoid in the monoidal category (Psh(ℙ),∘,I).
This definition is almost the desired result, but the base category ℙ is slightly different: it's the category of cardinals and bijections, basically the core of Set. Can we build a polynomial endofunctor on Set out of this? I'm not sure what to do with the symmetries.

One setting where both correspondences become very visible is that of bialgebraic semantics of programming languages: the syntax monad encodes the syntax operad (?), whereas the behaviour comonad encodes the category of states and transitions.

Joachim Kock (Mar 18 2021 at 18:56):

anuyts said:

It seems that a polynomial monad on Set is an operad, where the shapes are the operations and P(s) is the arity of s, though I'm not familiar with operads. Is this a known result? The nLab states (even defines):
A (Set-based) operad is a monoid in the monoidal category (Psh(ℙ),∘,I).
This definition is almost the desired result, but the base category ℙ is slightly different: it's the category of cardinals and bijections, basically the core of Set. Can we build a polynomial endofunctor on Set out of this? I'm not sure what to do with the symmetries.

Very good question. It is quite subtle. A finitary polynomial monad is a special case of symmetric operad called sigma-cofibrant. It means that the symmetric-group actions are free.

You are right that there is a problem with symmetries, caused by non-free group actions. For example, the terminal operad Comm (whose underlying endofunctor is the exponential $y \mapsto \sum_{n\in \mathbb{N}} y^n/ \mathfrak{S}_n$) preserves pullbacks weakly, but not strictly like an honest polynomial functor.

The good news is that the difference goes away in the $\infty$-world! Over $\infty$-groupoids (in fact already over $1$-groupoids), it is as if all group actions were free. The difference between (finitary) polynomial monads and operads is really only a deficiency of the category of sets.

Joachim Kock (Mar 18 2021 at 18:59):

There is another relationship, namely that polynomial monads cartesian over the free-monoid monad are the same thing as nonsymmetric operads, also called multicategories.

Over in another thread called Shapes and algebraic structures, I plan to talk about the symmetry issues, but I think I have to talk about
multicategories first...

Tarmo Uustalu (Mar 18 2021 at 23:56):

Hi. Yes. You get a cartesian polynomial monad from every non-symmetric operad in this way. General polynomial monads correspond to something more general non-symmetric operad like where composition can discard and duplicate inputs.

Gambino and Kock have discussed these connections in detail, see here, https://arxiv.org/abs/0906.4931, see also in other writings by Kock.