Linearity, Laws and Liftings

We have seen that we can extend algebraic operations to powersets, and these extensions preserve linear equations. This allowed us to lift the powerset monad to the Eilenberg-Moore category of a monad presented by linear equations. Equivalently, this gives us sufficient conditions for a monad to distribute over the powerset monad.

Now we have some general results about multilinear extensions, we are finally at the point when we can:

  1. Generalise the monad lifting and distributive law results we have seen so far beyond the powerset monad.
  2. Identify what is special about linear equations that makes these constructions work.

The payoff will be theorems yielding lifted monads and distributive laws.

Closure Properties of Multilinear Morphism

We will work in a symmetric monoidal category, which we assume to be strict to keep discussions simple.

A first unsurprising result is that multilinear maps are closed under permutations of their arguments. Formally, if

f^:𝕊(X)⊗…⊗𝕊(X)→𝕊(X)\hat{f} : \mathbb{S}(X) \otimes \ldots \otimes \mathbb{S}(X) \rightarrow \mathbb{S}(X)

is the multilinear extension of

f:X⊗…⊗X→Xf : X \otimes \ldots \otimes X \rightarrow X

and

sX:X⊗…⊗X→X⊗…⊗Xs_X : X \otimes \ldots \otimes X \rightarrow X \otimes \ldots \otimes X

is a natural transformation describing a permutation built using the symmetry natural transformation, then

f^⋅s𝕊(X):𝕊(X)⊗…⊗𝕊(X)→𝕊(X)\hat{f} \cdot s_{\mathbb{S}(X)} : \mathbb{S}(X) \otimes \ldots \otimes \mathbb{S}(X) \rightarrow \mathbb{S}(X)

is the multilinear extension of

f⋅sX:X⊗⋯⊗X→Xf \cdot s_{X} : X \otimes \dots \otimes X \rightarrow X

The proof is a completely routine.

An important, and only slightly less obvious closure property is that multilinear extensions are closed under composition. For example, if

f^,g^,h^:𝕊(X)⊗𝕊(X)→𝕊(X)\hat{f}, \hat{g}, \hat{h} : \mathbb{S}(X) \otimes \mathbb{S}(X) \rightarrow \mathbb{S}(X)

are the respective bilinear extensions of

f,g,h:X⊗X→Xf,g,h : X \otimes X \rightarrow X

then the composite

h⋅(f⊗g):𝕊(X)⊗𝕊(X)⊗𝕊(X)⊗𝕊(X)→𝕊(X)h \cdot (f \otimes g) : \mathbb{S}(X) \otimes \mathbb{S}(X) \otimes \mathbb{S}(X) \otimes \mathbb{S}(X) \rightarrow \mathbb{S}(X)

is the multilinear extension of

h⋅(f⊗g):X⊗X⊗X⊗X→Xh \cdot (f \otimes g) : X \otimes X \otimes X \otimes X \rightarrow X

The proof is another routine diagram chase.

Preservation of Linear Equations

We now return to the setting of algebraic structures on sets. Consider a structure with binary operations:

f,g,h:X×X→Xf,g,h : X \times X \rightarrow X

satisfying the linear equation:

h(f(w,x),g(y,z))=h(g(y,z),f(w,x))h(f(w,x),g(y,z)) = h(g(y,z),f(w,x))

We can rephrase this in terms of composite morphisms as:

h⋅(f×g)=h⋅(g×f)⋅sXh \cdot (f \times g) = h \cdot (g \times f) \cdot s_X

where s is the natural transformation that orders the arguments on the righthand side correctly.

Using the closure properties of multilinear extensions, the composites:

h^⋅(f^×g^)andh^⋅(g^×f^)⋅s𝕋(X)\hat{h} \cdot (\hat{f} \times \hat{g}) \quad\text{and}\quad \hat{h} \cdot (\hat{g} \times \hat{f}) \cdot s_{\mathbb{T}(X)}

are multilinear extensions of the left and right hand side of the previous equation. By the uniqueness of multilinear extensions:

h^⋅(f^×g^)=h^⋅(g^×f^)⋅s𝕋(X)\hat{h} \cdot (\hat{f} \times \hat{g}) = \hat{h} \cdot (\hat{g} \times \hat{f}) \cdot s_{\mathbb{T}(X)}

and so the equation lifts from X to multilinear extensions of the operations on \mathbb{S}(X).

Note this argument would not work for equations that are not linear. The whole argument hinges on the proof principle that multilinear extensions are unique, but we have no closure property of multilinear extensions that allows us to drop or duplicate arguments. We will return to this topic in the next post.

We can generalise the above argument to an arbitrary linear equation, and so all such equations are preserved when extending operations to their multilinear extensions on \mathbb{S}(X).

Consequences

If monad \mathbb{S} is commutative and monad \mathbb{T} has a presentation only requiring linear equations:

  1. The monad \mathbb{S} lifts to the category \mathsf{Set}^{\mathbb{T}}.
  2. There is a distributive law of type \mathbb{T} \circ \mathbb{S} \Rightarrow \mathbb{S} \circ \mathbb{T}.

Example: The multiset monad is both commutative and presented by linear equations. Therefore:

  1. For any commutative monad \mathbb{S} there is a distributive law of type \mathbb{M} \circ \mathbb{S} \Rightarrow \mathbb{S} \circ \mathbb{M}.
  2. For any monad \mathbb{T} with a presentation by linear equations, there is a distributive law of type \mathbb{T} \circ \mathbb{M} \Rightarrow \mathbb{M} \circ \mathbb{T}.

In particular, the multiset monad distributes over itself.

Summary

These results appear in Manes and Mulry “Monad Compositions I”, and many distributive laws arise in this way. These results are well-known, but the restriction linear equations is frustrating. In the next post, we will look at more recent results making a slightly different trade-off to circumvent the restriction to linear equations.

2 thoughts on “Linearity, Laws and Liftings”

  1. Pingback: Distributive Laws and General Equations – Dan Marsden
  2. Pingback: Affine and Relevant Strong Submonads – Dan Marsden

Leave a comment