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 ${\displaystyle (S,\mu ^{S},\eta ^{S})}$ and ${\displaystyle (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

${\displaystyle l:TS\to ST}$

such that the diagrams

commute.

This law induces a composite monad ST with

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

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.^[1] Explicitly, consider the monads

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

${\displaystyle S(X):=X+1}$,

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

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

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

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

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

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

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

${\displaystyle l(w)=w-e,}$

where ${\displaystyle w-e}$ is the word derived from ${\displaystyle w}$ by removing all instances of ${\displaystyle e}$, unless ${\displaystyle w}$ is all ${\displaystyle e}$'s, in which case it's defined to be ${\displaystyle e\in 1}$. The idea, in short, is this: if we view words on ${\displaystyle X}$ as formal products of elements (i.e., the free semigroup operation), then ${\displaystyle l}$ encodes that the freely added element ${\displaystyle 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.

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

${\displaystyle LHS:w\mapsto (w-e')\mapsto (w-e'-e)\mapsto (w-e'-e)}$

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

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

• ${\displaystyle l_{X}\circ T(\eta _{X}^{S})=\eta _{T(X)}^{S}}$

${\displaystyle LHS:w\mapsto w\mapsto w-e}$

${\displaystyle RHS:w\mapsto w}$,

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

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

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

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

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

• ${\displaystyle l_{X}\circ \eta _{S(X)}^{T}=S(\eta _{X}^{T})}$

${\displaystyle LHS:(x\in X\ or\ e\in 1)\mapsto (x\ or\ e)\mapsto (x\ or\ e)-e}$

${\displaystyle RHS:(x\ or\ e)\mapsto (x\ or\ e)}$.

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

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

This is the original example given by Beck,^[2] and is the motivation for the term "distributive law". Consider the two monads ${\displaystyle G,M:{\mathbf {Set}}\to {\mathbf {Set}}}$ which send a set ${\displaystyle 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 ${\displaystyle GM}$ and ${\displaystyle MG}$ give the free ring functor. We can now use the fact that the free ring admits a distributive law ${\displaystyle 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 ${\displaystyle M(G(X))}$) can be identified with a sum of products (an element of ${\displaystyle G(M(X))}$). Note that we say ${\displaystyle G(X)}$, the additive group, distributes over ${\displaystyle M(X)}$, the multiplicative monoid - contrary to the usual convention; see the next section.

The original description by Beck calls ${\displaystyle l:TS\to ST}$ a distributive law of S over T.^[2] However, some authors prefer the reverse terminology, where ${\displaystyle 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 ${\displaystyle \prod \sum \to \sum \prod }$ (see Examples). Nevertheless, both terminologies are in use in different sources, and the original is what this article uses.^[3]

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

(D) ${\displaystyle K}$ is a distributive law, and

(B) it satisfies the Yang-Baxter equation:

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

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

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

(C) ${\displaystyle \mu _{X}^{T}\circ K_{X}=\mu _{X}^{T}}$

(as maps ${\displaystyle 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 ${\displaystyle T:{\mathbf {C}}\to {\mathbf {C}}}$ is viewed as a monoid in the category of endofunctors on ${\displaystyle {\mathbf {C}}}$.^[4]

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

• Distributive property

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

• Barr, Michael; Wells, Charles (1985). Toposes, Triples and Theories (PDF). Springer-Verlag. ISBN 0-387-96115-1. Archived from the original (PDF) on 2011-05-14.
• Distributive law at the nLab
• Böhm, G. (2005). "Internal bialgebroids, entwining structures and corings". Algebraic Structures and Their Representations. Contemporary Mathematics. Vol. 376. pp. 207–226. arXiv:math.QA/0311244. ISBN 9780821836309.
• Brzeziński, T.; Majid, S. (1998). "Coalgebra bundles". Comm. Math. Phys. 191 (2): 467–492. arXiv:q-alg/9602022. Bibcode:1998CMaPh.191..467B. doi:10.1007/s002200050274. S2CID 189829500.
• Brzezinski, Tomasz; Wisbauer, Robert (2003). Corings and Comodules. London Mathematical Society Lecture Note Series. Vol. 309. Cambridge University Press. ISBN 978-0-521-53931-9.
• Fox, T.F.; Markl, M. (1997). "Distributive laws, bialgebras, and cohomology". Operads: Proceedings of Renaissance Conferences. Contemporary Mathematics. Vol. 202. American Mathematical Society. pp. 167–205. ISBN 9780821805138.
• Lack, S. (2004). "Composing PROPS". Theory Appl. Categ. 13 (9): 147–163.
• 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. arXiv:hep-th/9409192. doi:10.5802/aif.1516. Zbl 0853.18005.
• 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. arXiv:0811.4770. doi:10.1515/GMJ.2009.183. S2CID 121946556.
• Wisbauer, R. (2008). "Algebras versus coalgebras". Appl. Categ. Structures. 16 (1–2): 255–295. doi:10.1007/s10485-007-9076-5. S2CID 8150337.