Distributive law between monads

In category theory, an abstract branch of mathematics, distributive laws between monads are a way to express abstractly that two algebraic structures distribute one over the other.

Suppose that $(S,{\mu }^S,{\eta }^S)$ and $(T,{\mu }^T,{\eta }^T)$ are two monads on a category C. In general, there is no natural monad structure on the composite functor ST. However, there is a natural monad structure on the functor ST if there is a distributive law of the monad S over the monad T.

Formally, a distributive law of the monad S over the monad T is a natural transformation

$l:TS\to ST$

such that the diagrams

        

        

commute.

This law induces a composite monad ST with

• as multiplication: $STST\stackrel{SlT}{\to }SSTT\stackrel{{\mu }^S{\mu }^T}{\to }ST$,
• as unit: $1\stackrel{{\eta }^S{\eta }^T}{\to }ST$.

Examples

Monoids

Informally, one might say that the free monoid on a set is given by "the free semigroup, plus an identity element". We can formalise this intuition, using the fact that both the free semigroup and the "free element" functors are monads. Explicitly, consider the monads

$T(X):=\sum _{n\ge 1}{X}^n$

$S(X):=X+1$,

(here addition denotes disjoint union), with unit maps given by:

${\eta }_X^T:X\to T(X)$

${\eta }_X^T(x):=x\in X^1$

${\eta }_X^S:X\to S(X)$

${\eta }_X^S(x):=x\in X$.

The multiplication map ${\mu }_X^S:X+2\to X+1$ sends both elements of 2 to that of 1, but the multiplication on $T$ is a bit more tricky to describe. First, note that an arbitrary element of $T(X)$ is just a finite (nonempty) string of elements of $X$. The multiplication map $T^2(X)\to T(X)$ should therefore take a string of words on $X$ to one word. We choose ${\mu }_X^T(list)$ to be the concatenation of all (finitely many) words in $list$.

What does a distributive law $l:TS\to ST$ mean here? It takes a word on the set $X+1$ to either a word on $X$, or the disjoint point in $1$. We choose the map that interprets the unit element $e\in 1$ as the empty word; explicitly:

$l(w)=w-e,$

where $w-e$ is the word derived from $w$ by removing all instances of $e$, unless $w$ is all $e$'s, in which case it's defined to be $e\in 1$. The idea, in short, is this: if we view words on $X$ as formal products of elements (i.e., the free semigroup operation), then $l$ encodes that the freely added element $e$ can be incorporated into the semigroup as a unit element (thereby making the structure into a monoid). Let us check that all the diagrams in the definition commute.

• ${\mu }_{T(X)}^S\circ S(l_X)\circ l_{S(X)}=l_X\circ T({\mu }_X^S)$

$LHS:w\mapsto (w-e^{\prime })\mapsto (w-e^{\prime }-e)\mapsto (w-e^{\prime }-e)$

$RHS:w\mapsto w[e/e^{\prime }]\mapsto (w[e/e^{\prime }]-e)$,

$e,e^{\prime }$ being the elements of each copy of $1$ in $X+1+1$, and where $w[e/e^{\prime }]$ denotes the word $w$ with every instance of $e^{\prime }$ replaced by $e$.

• $l_X\circ T({\eta }_X^S)={\eta }_{T(X)}^S$

$LHS:w\mapsto w\mapsto w-e$

$RHS:w\mapsto w$,

and note that for $w\in T(X)$ we have $w-e=w$, as required.

• $S({\mu }_X^T)\circ l_{T(X)}\circ T(l_X)=l_X\circ {\mu }_{S(X)}^T$

$LHS:w\mapsto w[(v-e)/v]\mapsto w[(v-e)/v]-e\mapsto concat(w[(v-e)/v]-e)$

$RHS:w\mapsto concat(w)\mapsto concat(w)-e$,

where: $concat(w)$ is the concatenation of all words in $w$, i.e. the multiplication on $T$; and $w[(v-e)/v]$ is the result of replacing every word $v$ in $w$ with $(v-e)$.

• $l_X\circ {\eta }_{S(X)}^T=S({\eta }_X^T)$

$LHS:(x\in Xore\in 1)\mapsto (xore)\mapsto (xore)-e$

$RHS:(xore)\mapsto (xore)$.

In summary, the four commutation requirements encode the following ideas:

1. "Deleting" elements $w-e^{\prime }$ behaves like replacing them with the identity, $w[e/e^{\prime }]$.
2. Any word $w$ on $X$ doesn't contain the element $e$, so $w-e=w$. In other words, $X+1$ truly is a disjoint union.
3. In a list of words $w=(v_1,...,v_n)$, removing any instance of $e$ in $v_i$, removing any remaining "empty word" $v_i=e$, and concatenating the resulting list, yields the same result as first concatenating $v_1{v}_2...v_n$ then removing all instances of $e$.
4. $x-e=x$, as already covered in 2; and $e-e=e$, meaning we should interpret $e$ as the empty word.

Rings

This is the original example given by Beck, and is the motivation for the term "distributive law". Consider the two monads $G,M:\mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}\to \mathbf{𝐒}\mathbf{𝐞}\mathbf{𝐭}$ which send a set $X$ to (the underlying set of) the free commutative group and the free monoid on it, respectively. We shall regard the formal group operation as addition, and that of the monoid as multiplication. In this case, both composites $GM$ and $MG$ give the free ring functor. We can now use the fact that the free ring admits a distributive law $MG\to GM$ to show that it's also a monad.

The distributive law of G over M means exactly that a product of sums (i.e. an element of $M(G(X))$) can be identified with a sum of products (an element of $G(M(X))$). Note that we say $G(X)$, the additive group, distributes over $M(X)$, the multiplicative monoid - contrary to the usual convention; see the next section.

Terminology

The original description by Beck calls $l:TS\to ST$ a distributive law of S over T. However, some authors prefer the reverse terminology, where $l$ is instead said to be a distributive law of T over S; this is because, arguably, the latter convention corresponds more closely to the usual distributive law between multiplication and addition - multiplication is typically said to distribute over addition, by which one means that a product of sums can be rewritten as a sum of products $\prod \sum \to \sum \prod$ (see Examples). Nevertheless, both terminologies are in use in different sources, and the original is what this article uses.

Related notions

BD-law

In the case where $T=S$, the distributive law map reduces to $K:T^2\Rightarrow T^2$, and one may impose some additional conditions. $K$ is called a BD-law on $T$ if:

(D) $K$ is a distributive law, and

(B) it satisfies the Yang-Baxter equation:

$K_{T(X)}\circ T(K_X)\circ K_{T(X)}=T(K_X)\circ K_{T(X)}\circ T(K_X)$

(as maps $T^3(X)\to T^3(X)$).

A BD-law is a BCD-law if the multiplication on $T$ is "$K$-commutative", meaning that

(C) ${\mu }_X^T\circ K_X={\mu }_X^T$

(as maps $T^2(X)\to T(X)$).

Condition (B) is called a Yang-Baxter equation because it literally is the Yang-Baxter equation defined on monoid objects, when $T:\mathbf{𝐂}\to \mathbf{𝐂}$ is viewed as a monoid in the category of endofunctors on $\mathbf{𝐂}$.

Entwining

For $P$ an algebra and $C$ a coalgebra over a shared field $k$, an entwining between them is a linear map $\psi :C\otimes P\to P\otimes C$ satisfying analogous conditions to those that would be required, were $\psi$ a distributive law. Specifically, the commutation diagram $CCP\to PC$ that would be induced by a hypothetical multiplication $CC\to C$ is replaced with one for $C\otimes P\to P\otimes C\otimes C$ induced by the comultiplication $C\to C\otimes C$; likewise, the triangle diagram $P\to PC$ is replaced with one of type $C\otimes P\to P\otimes k$, induced by the counit.

See also

• Distributive property

References

• Beck, Jon (1969). "Distributive laws". Seminar on Triples and Categorical Homology Theory, ETH 1966/67. Lecture Notes in Mathematics. 80. pp. 119–140. doi:10.1007/BFb0083084. ISBN 978-3-540-04601-1. 

• Toposes, Triples and Theories. Springer-Verlag. 1985. ISBN 0-387-96115-1. http://www.case.edu/artsci/math/wells/pub/pdf/ttt.pdf. 
• Distributive law in nLab
• Böhm, G. (2005). "Internal bialgebroids, entwining structures and corings". Algebraic Structures and Their Representations. Contemporary Mathematics. 376. pp. 207–226. ISBN 9780821836309. 
• Brzeziński, T.; Majid, S. (1998). "Coalgebra bundles". Comm. Math. Phys. 191 (2): 467–492. doi:10.1007/s002200050274. Bibcode: 1998CMaPh.191..467B. 
• Brzezinski, Tomasz; Wisbauer, Robert (2003). Corings and Comodules. London Mathematical Society Lecture Note Series. 309. Cambridge University Press. ISBN 978-0-521-53931-9. https://books.google.com/books?id=Ea1EeaOu_HUC&pg=PP1. 
• Fox, T.F.; Markl, M. (1997). "Distributive laws, bialgebras, and cohomology". Operads: Proceedings of Renaissance Conferences. Contemporary Mathematics. 202. American Mathematical Society. pp. 167–205. ISBN 9780821805138. 
• Lack, S. (2004). "Composing PROPS". Theory Appl. Categ. 13 (9): 147–163. http://www.tac.mta.ca/tac/volumes/13/9/13-09abs.html. 
• Lack, S.; Street, R. (2002). "The formal theory of monads II". J. Pure Appl. Algebra 175 (1–3): 243–265. doi:10.1016/S0022-4049(02)00137-8. 
• Markl, M. (1996). "Distributive laws and Koszulness". Annales de l'Institut Fourier 46 (2): 307–323. doi:10.5802/aif.1516. 
• Street, R. (1972). "The formal theory of monads". J. Pure Appl. Alg. 2 (2): 149–168. doi:10.1016/0022-4049(72)90019-9. 
• Škoda, Z. (2004). "Distributive laws for monoidal categories". arXiv:math/0406310.
• — (2007). "Equivariant monads and equivariant lifts versus a 2-category of distributive laws". arXiv:0707.1609 [math.CT].
• — (2008). "Bicategory of entwinings". arXiv:0805.4611 [math.RA].
•   (2009). "Some equivariant constructions in noncommutative geometry". Georgian Math. J. 16 (1): 183–202. doi:10.1515/GMJ.2009.183. 
• Wisbauer, R. (2008). "Algebras versus coalgebras". Appl. Categ. Structures 16 (1–2): 255–295. doi:10.1007/s10485-007-9076-5.