17
$\begingroup$

By composition of monads, I mean given two monads $S$ and $T$, making their composite $S T$ into a monad. Or more generally, given two monoid $X$ and $Y$ in a non-symetric monoidal category, making $X \otimes Y$ into a monoid.

This is fairly classical and generally done using a distributive law, that is map $ l : TS \to ST$ that satisfies four axioms that I'll call "compatibility to the unit of $S$, to the unit of $T$, to the multiplication of $S$ and to the multiplication of $T$."

One then make $S T$ into a monoids/monads by defining $Id \to ST$ to be $I = II \overset{\epsilon_S \epsilon_T}\to ST$ and

$$(ST)(ST) \overset{S l T}{\to} SSTT \overset{\mu_S \mu_T}{\to} ST$$.

Now I've recently encountered a situation where I have a monad structure on $ST$, that is also obtained out of a map $l:TS \to ST$, but this map is not a distributive law and the way it is used to get a monad structure on $ST$ is kind of different.

I'll describe the situation below, But essentially my question are: Has anyone has seen something like this somewhere else ? - has been studied or considered somewhere ? Also, there is some general theory for distributive law: A distributive law as above is the same as the data of a lift of $S$ to a monad $S^l$ on the category of $T$-algebras, and a $S^l$-algebra (sometime called a $l$-algebra) is the same as $ST$-algebra. Is there some general theory of this kind for the situation I'm about to described (For e.g. a way to see this sort of composition in terms of the category of algebras) ? I haven't found anything really convincing yet, but I'm not sure what to look for...

Ok, so in my situation, I still have a map $l:TS \to ST$, which satisifes:

  1. $l$ is actually an isomorphism.

  2. $l$ satisfies 2 of the four axioms for distributive law: compatibility to the unit of $T$ and to the multiplication of $T$. So, following the terminology of the nLab, $l$ is a distributive law of the monad $T$ on the underlying endofunctor of $S$.

  3. $l$ satisfies one additional axiom, which would be a consequence of the compatibility of the multiplication of $S$ with $l$, but is a little bit weaker, which says that the following two maps $SSTS \to ST$ are equal:

$$ SSTS \overset{\mu_S T S}{\to} STS \overset{l^{-1}S}{\to} TSS \overset{T \mu_S}{\to} TS \overset{l}{\to} ST $$

$$ SSTS \overset{S l^{-1} S}{\to} STSS \overset{ST \mu_S}{\to} STS \overset{Sl}{\to} SST \overset{\mu_S T}{\to} ST $$

And now, what I think is the most important difference with the usual notion of distributive law: the way it is used to build a monad structure on $ST$ is a little different: The unit law of $ST$ is the same, but now the multiplication is given by:

$$ (ST)(ST) \overset{l^{-1} ST}\to T S S T \overset{T \mu_S T}\to TST \overset{l^{-1} T}{\to} STT \overset{S \mu_T}\to ST $$

Note that if this $l$ is actually a distributive law and is invertible (as required by my hypothesis (1)), then this definition and the usual multiplication of $ST$ can be shown to be equal, but in the absence of the compatibility of $l$ with the multiplication of $S$ this is a different definition.

I claim that this indeed makes $ST$ into a monad (hope I haven't forgotten an axiom - it works on the example I care about anyway)

Example: I'll give one simple explicit example of this. It is a toy model of the situation I care about, but it is already quite interesting. I work in the cartesian monoidal category of Sets, so "monads" are just monoids (you can promote them to actual monads by looking at the endofunctor $X \times \_$ if you prefer).

I have $S = M$ any monoid and $T = L(M)$ is the monoid of finite lists of elements of $M$, with the multiplication being given by concatenation (so it does not involve the monoid structure of $M$).

$$l : L(M) \times M \to M \times L(M)$$

is the map that sends $(a_1,\dots,a_k),m$ to $a_1,(a_2,\dots,a_k,m)$ and $\varnothing,a$ to $a,\varnothing$. One easily check that $l$ satisfies all three conditions above, but crucially it is not a distributive law because it is not at all compatible to the multiplication of $M$ nor the unit of $M$.

The multiplication it defines on $M \times L(M)$ works as follow (the arrow represents the steps in the definition above):

$$m,(a_1,\dots,a_k), m',(a'_1,\dots,a'_{k'}) \to (m,a_1,\dots,a_{k-1}), a_k,m',(a'_1,\dots,a'_{k'}) \to $$ $$ (m,a_1,\dots,a_{k-1}), a_k m',(a'_1,\dots,a'_{k'}) \to m,(a_1,\dots,a_{k-1},a_k m'),(a'_1,\dots,a'_{k'}) \to $$ $$ m,(a_1,\dots,a_{k-1},a_k m',a'_1,\dots,a'_{k'}) $$

So the combined monad can be thought of as $L^+(M)$ the monoid of non-empty list of elements of $M$, where the multiplication is performed by concatenating the lists, but multiplying the last element of the left list with the first element of the right list. ( the unit element is the list $(1)$ for $ 1$ the unit of $M$, which in the definition above corresponds to the pair $(1,\varnothing)$).

More motivation: In case someone wants to see more examples, here is the general situation I was studying when I encountered this - but it is a lot less elementary. Fix $M=(M_0,\mu_M,\epsilon_M)$ a monad on a category $C$. I assume $C$ is locally presentable and $M$ is accessible so that all the construction below make sense.

It is a known result that the initial algebra for the endofunctor $M_0$ is isomorphic to the initial object in the category of $M$-algebras $X$ endowed with a map (not a morphism) $s:X \to X$. This only apply to the initial algebra, but there seems to be a close link between these two algebraic structures.

I'm calling $M_0^*$ the free monad on the underlying endofunctor $M_0$ of $M$, I'm calling $M^s$ the monad whose algebras are the $M$-algebras $X$ endowed with a "successor" function $s: X\to X$ as above (both exists thanks to our accessibility assumptions).

Refining the result above (I'm hiding a lot of details here), one can show that, one has isomorphisms relating the underlying endofunctors of these two monads :

$$ M_0^*(X) \simeq X \coprod M^s(X) $$ $$ M^s(X) \simeq M(M_0^*(X)) $$

(and yes, combining the two, we have $M_0^*(X) \simeq X \coprod M(M_0^*(X))$ which is a consequence from the fact that the initial algebra for an endofunctor $P$ satisfies $X \simeq P(X)$)

But it is not so clear how to relate them as monads... I computed several examples and the first line doesn't seem to work well regarding the monad structure, but in all cases (and I suspect something similar works in general though I'm not completely sure yet) the monad structure of $M^s(X)$ is obtained from the composite $M M_0^*$ by the process described above. The example detailed above corresponds to the special case where $M$ is the monad a sets $M(X) = M \times X$ after some computation.

$\endgroup$
6
  • 2
    $\begingroup$ Your monoid construction from nonempty lists (or at least a small variant of it) is used as the first step of constructing the left Karnosfky-Rhodes expansion of $M$ (with respect to the generating set $M$). Then on imposes a certain congruence. $\endgroup$ Oct 4, 2022 at 0:34
  • 1
    $\begingroup$ I'll try to look it up a good reference. One issue is there are semigroup and monoid versions and usually in a way similar to the homegeneous versus nonhomegeneous bar resolution the Karnofsky-Rhodes construction will look at the sequence of edges And vertices you get in the left Cayley graph by multiplying the susccesive guys in the list and then view m' as translating the second list and doing the same. $\endgroup$ Oct 4, 2022 at 3:09
  • 2
    $\begingroup$ Very interesting! A test case for a general construction like this would be two submonoids $M_1$, $M_2$ of a monoid $M$ such that $M_1M_2=\{m_1m_2\mid m_i\in M_i,i=1,2\}$ is a submonoid too. I believe this does not always come from (an appropriate case of) a distributive law. Does it come from your construction? $\endgroup$ Oct 4, 2022 at 4:30
  • 2
    $\begingroup$ This is very intriguing. The only immediate comment is that the multiplication on $M\times L(M)$ that you obtain is something I have already seen in a linearized context: it measures to what extent the differential of the bar complex $B(A)$ of an associative algebra $A$ is not a derivation of the concatenation product imposed on the $B(A)$ (which is naturally a coalgebra, not an algebra, hence "imposed"). It leads to a non-commutative analogue of Batalin-Vilkovisky algebras, see arxiv.org/abs/1510.03261 and references therein. $\endgroup$ Oct 4, 2022 at 7:13
  • 7
    $\begingroup$ It may be irrelevant (I haven't the time to look more carefully now), but there is a more general way of composing monads than a distributive law: namely a wreath (§3 of The formal theory of monads II). It may be worth checking whether there's any relation to your situation. $\endgroup$
    – varkor
    Oct 4, 2022 at 10:54

1 Answer 1

9
$\begingroup$

Ok, I think I've solved the mystery, and it is a little disappointing: The point is that there is actually a distributive law lurking in the background , constructed from the $l$ in the original question, that gives the same monad structure on the composite $ST$. (Many thanks to მამუკა ჯიბლაძე and Varkor - I've realized it by trying to follow their surgestions in the comment.)

Right, so the idea is that given a $l : TS \to ST$ as in the original post, I consider the following map $\alpha: TS \to ST $ defined as the composite:

$$ TS \overset{\epsilon_S TS }\to STS \overset{l^{-1}S}\to TSS \overset{T \mu_S}\to TS \overset{l}\to ST $$

Then I claim that this $\alpha$ is a distributive law and that the monad structure on $ST$ defined from $l$ in the original post can be obtained from $\alpha$ by using the classical formula. The proof is just a bunch of diagram computation that would be hard to reproduce here (and it is a little late so I hope I didn't make any mistakes in my computation)

For example, in the case of $M$ and $L(M)$ in the original question, $\alpha$ is the map $L(M) \times M \to M \times L(M)$ defined by $\alpha((m_1,\dots,m_k),m) = (1 , (m_1,\dots,m_k m))$

It should be noted that while $l$ was invertible, $\alpha$ no longer is. So there seem to be still something interesting going on here. For example, I have the impression that one can also define a distributive law $ ST \to TS$ using something similar that produce the monad structure on $TS$ coming from the isomorphism $ST \simeq TS$ given by $l$ and the monad structure on $ST$). But in any case that solve my problem: This is "just" a distributive law with some special additional property, but I was using the wrong function $TS \to ST$.

The case of monoids: Following the suggestion of მამუკა ჯიბლაძე in the comment, here is what happens with distributive law between ordinary monoids, which I think gives a good idea of what happens in general:

In the standard case, a distributivity law of $T$ on $S$ can be thought of as a monoid $M$ that contains $S$ and $T$ as submonoids and such that each element of $M$ is written uniquely as $st$. The distributive law $TS \to ST$ itself is the function that gives you the expression as $st$ of an element of the form $ts$. You then use it to describe the multiplication $(s_1 t_1)(s_2 t_2) = (s_1 s'_2) (t'_1 t_1)$

The case described in the original post corresponds to the situation where we have two inclusions of monoids $i,j: T \to M$, and $S$ is a submonoid of $M$, and every element of $M$ can be written uniquely both as $j(t) s$ and as $s' i(t')$. The function $l$ is now the bijection that sends $(t,s)$ to $(s',t')$ where $j(t) s = s' i(t')$.

One can also use it to compute the product a bit like a distributivity law, but one has to be a bit more careful on how we do it:

$$(s_1 i(t_1)) (s_2 i(t_2)) = j(t'_1) s_1 s_2 i (t_2) =s'' i(t''_1) i(t_2) = s'' i(t''_1 t_2) $$

which corresponds exactly to the formula for the product in the original question.

The fact that this $l$ isn't compatible to unit law of $S$ exactly means that $i \neq j$, indeed $i$ and $j$ are respectively obtained as $T \overset{\epsilon_s T}\to ST$ and $T \overset{T \epsilon_s }\to TS \overset{l}{\to} ST$ so the compatibility of $l$ with $\epsilon_S$ is exactly the condition that $i=j$. The compatibility of $l$ with multiplication fails for similar reason: if one try to swap $j(t)$ with $s_1 s_2$ one can do it in a single step, but doing in two steps doesn't make sense as $j(t)s_1 s_2 = s'_1 i(t') s_2$ and then we are stuck and using $l$ to replace $(t',s_2)$ by a $(s'_2,t'')$ won't give the correct result.

But nonetheless, in this situation any "wrong side" product $i(t) s$ can be rewritten in the correct order as $s'i(t')$ by computing the product $(1 i(t)) (s i(1))$ using the formula given above, and this is how one obtains the distributive law $\alpha$ mentioned above.

$\endgroup$
1
  • 2
    $\begingroup$ What might be also relevant is the "propositional" case: given two nuclei $j$ and $k$, the composite $jk$ is a nucleus iff $kj\leqslant jk$ iff $kjk=jk$ iff $j(\operatorname{Fix}(k))\subseteq\operatorname{Fix}(k)$ $\endgroup$ Oct 5, 2022 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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