4
$\begingroup$

Let $\mathbf{Poly}$ denote the category of polynomial functors on $\mathbf{Set}$, and let $\mathfrak{m}\colon\mathbf{Poly}\to\mathbf{Poly}$ be the free monad monad, i.e. the functor that sends every polynomial $p$ to the free monad $(\mathfrak{m}_p,\eta,\mu)$, $$ \mathfrak{m}_p\colon\mathbf{Set}\to\mathbf{Set} \qquad \eta_p\colon\text{id}_\mathbf{Set}\to \mathfrak{m}_p \qquad \mu_p\colon \mathfrak{m}_p\circ \mathfrak{m}_p\to \mathfrak{m}_p $$ on $p$. One can think of the underlying functor $\mathfrak{m}_p$ as the coproduct over all $p$-syntax trees of the functor represented by the leaves.

Let $(t,\eta,\mu)$ denote an arbitrary polynomial monad on $\mathbf{Set}$. This means $t$ comes equipped with an algebra structure $\alpha\colon\mathfrak{m}_t\to t$ satisfying a unit law $\alpha\circ\eta_t=\text{id}_t$ and a similar composition law. We define a quine transformation of $t$ to be a section $$ \beta\colon t\to\mathfrak{m}_t$$ of the algebra map, i.e.\ a natural transformation with $\alpha\circ\beta=\mathrm{id}_t$. We say that the quine transformation $\beta$ is trivial if $\beta=\eta_t$, and we say it is nontrivial if $\beta\neq\eta_t$.

Note that a free monad $\mathfrak{m}_p$ always has a nontrivial quine transformation, namely $$ \mathfrak{m}_p\xrightarrow{\mathfrak{m}_{\eta_{\,p}}}\mathfrak{m}_{\mathfrak{m}_p} $$ which is indeed nontrivial because $\mathfrak{m}_{\eta_p}\neq\eta_{\mathfrak{m}_p}$.

Question: If a polynomial monad $t$ on $\mathbf{Set}$ has a non-trivial quine transformation, does that imply that $t$ is free, $t=^?\mathfrak{m}_p$ on some polynomial $p$? Or, instead, does there exist a non-free monad that has a non-trivial quine?

(Note: some people restrict polynomial monads to be the Cartesian ones, i.e. those for which $\eta_t$ and $\mu_t$ are Cartesian natural transformations; e.g. this is the case for any free monad $\mathfrak{m}_p$. For this question, however, I would be happy with either Cartesian or non-Cartesian polynomial monads, as long as they are not free and have a nontrivial quine.)

$\endgroup$
2
  • $\begingroup$ Brandon Shapiro noted [personal communication] that, though one might think the naturality of $\beta$ would be fairly constraining, it is not. Because $t$ is a coproduct of representables, you can just define $\beta$ on each one separately, with no need for coherence between them. He suggested a better question might be to ask that $\beta$ is a monad map (which $\eta_t$ isn't, but which $\mathfrak{m}_{\eta_p}$ is). $\endgroup$ Commented Feb 24, 2023 at 19:58
  • $\begingroup$ This probably isn't surprising, but just a note that to my eye you can check straightforwardly from the monad map axioms that there aren't any such quines for the free monoid monad or for the monad induced by any particular non-free monoid. $\endgroup$ Commented Feb 27, 2023 at 20:35

0

You must log in to answer this question.

Browse other questions tagged .