Monads on monoids

This post is inspired by a couple of posts on math.stackexchange.com asking what a ‘monad on a monoid’ is.

---

In category theory there are a couple of especially simple kinds of category. For any partial order we can put a category structure on its elements by saying that there’s a unique morphism $x\to y$ if $x\leq y$ and none otherwise. And for any monoid we can construct a category with one object and with the morphisms from that object to itself being the elements the monoid.

These two examples are complementary to each other. With partial orders you can have as many objects as you want, but the morphisms have to be as simple as possible. Monoids are the opposite, you can only have one object but it can have as many morphisms as you like.

Sometime when we’re doing category theory it can help to think about these categories as a way of restricting our attention. If we have some complicated categorical construction then we can gain some intuition about it by looking at how it applies to these two simple cases. Today the ‘complicated categorical construction’ we’re interested in is monads.

Applying the concept of monads to the case of partial orders works out very nicely. The monads on a partial order correspond precisely to closure operators, which are a well known thing that had been discovered long before monads. Examples of these include topological closures, Galois closures, and linear spans.

But that’s not what we’re talking about today. I want to look at the other case: monads on monoids. Since partial orders worked out so nicely, we might hope that monads on monoids also corresponded to some preexisting notion that we’re already familiar with.

It will turn out that this hope is only partially fulfilled. There is a familiar notion that gives us a large class on monads on monoids. But not every monad on a monoid fits into this class.

Definitions

Formally we have to distinguish between the monoid $M$ and the category it corresponds to (its delooping) $\mathbf BM$. The category $\mathbf BM$ has a single object, and the morphisms from this object to itself are the elements of $M$, with the monoid multiplication as composition. A monad on $\mathbf BM$ is given by a functor $T:\mathbf BM\to\mathbf BM$ and natural transformations $\eta:\mathrm{id}_{\mathbf BM}\to T$ and $\mu:T^2\to T$ satisfying some axioms.

We can rephrase this data in terms of $M$ itself. A functor $T:\mathbf BM\to\mathbf BM$ is the same thing as a homomorphism $\theta:M\to M$. The natural transformations $\eta$ and $\mu$ are specified by their components at the single object of $\mathbf BM$, and hence correspond to elements $h$ and $m$ in $M$.

Definition 1

A monad on a monoid $M$ is a homomorphism $\theta:M\to M$ and elements $h,m\in M$ such that

\begin{align} &&m\theta(h)&=1_M,\tag{1}\\ &&mh&=1_M,\tag{2}\\ &&m\theta(m)&=m^2,\tag{3}\\ &\forall x\in M:&\theta(x)h &= hx,\tag{4}\\ &\forall x\in M:&\theta(x)m &= m\theta(\theta(x)).\tag{5} \end{align}

Axioms (1) to (3) correspond the usual axioms for monads. Axioms (4) and (5) come from the naturality conditions for $\eta$ and $\mu$.

Every monad has a category of modules (a.k.a. a Eilenberg-Moore category). We can also define this category in terms of $M$.

Definition 2

For a monad on a monoid $(M,\theta,h,m)$ the modules of the monad are the $k\in M$ with $kh=1_M$ and $k\theta(k)=km$. An module morphism $k\to l$ is a $p\in M$ with $l\theta(p)=pk$.

Looking at these definitions I don’t notice a resemblance to any familiar notion. But as I said in the introduction, it turns out that there is a preexisting notion that gives us some examples of monads on monoids, namely conjugations.

Example 3

Suppose $a,a^{-1}\in M$ with $aa^{-1}=1_M=a^{-1}a$. Then we get a monad on $M$ by letting $\theta(x)=a^{-1}xa$, $m=a$ and $h=a^{-1}$.

There’s precisely one module, namely $a$, but every $x\in m$ is a module morphism $a\to a$. So the category of modules is just $\mathbf BM$ itself.

This is a fairly boring structure. But at least it’s something we recognise!

Theorems and countexamples

It turns out that for a lot of nice monoids these are the only examples of monads.

Theorem 4

In the following cases, every monad on $M$ has the form of Example 3:

• $M$ is commutative,
• $M$ is a group,
• $M$ is finite.

(Note that in the commutative case this further implies that every monad is the identity, since $a^{-1}xa = a^{-1}ax = x$.)

Proof

Since $mh=1_M$ it suffices to show that $mh=hm$ or that $hm=1_M$. Then $h$ and $m$ are two-sided inverses as required, and (4) implies that $\theta(x) = hxm$.

When $M$ is commutative $mh=hm$ is immediate. When $M$ is a group it follows from the fact that one-sided inverses in a group are always two-sided.

When $M$ is finite consider the action $\rho$ of $M$ on itself by left multiplication. Then $mh=1_M$ implies $\rho(m)\rho(h)=\mathrm{id}_M$ and so $\rho(m)$ is a surjection and $\rho(h)$ an injection. Since any surjection or injection from a finite set to itself is a bijection we have $\rho(h)\rho(m)=\mathrm{id}_M$ and hence $hm=1$.

So if there’s a monad on $M$ not of the ‘trivial’ form of Example 3, then $M$ has to be an infinite monoid that doesn’t commute and isn’t a group. Quite an ugly object!

The interesting thing about this theorem is that the three cases are completely independent. For any subset of the three properties in the statement of the theorem there’s a monoid with those properties but not the others. But each property implies the desired result. All roads lead to Rome.

Because of this I was hoping that we’d be able to prove that every monad on a monoid was of that form. But when I brought it up on the nForum Mike Shulman quickly fired back with a class of counterexamples:

I think it’s not too hard to come up with examples of monads on (the deloopings of) monoids that are not much simpler than monads on arbitrary categories. Suppose for instance that $\kappa$ is a cardinal number and $T$ a monad on $\mathbf{Set}$ that preserves sets of cardinality $\kappa$; then $T$ restricts to a monad on the full subcategory of sets of cardinality $\kappa$, which has only one isomorphism class and hence is equivalent to the delooping of a monoid. For instance, if $\kappa=\aleph_0$ then $T$ could be any finitary algebraic theory (groups, monoids, rings, etc.).

This sounded right to me, but I found it difficult to understand because I couldn’t think of a concrete example. Even if $\kappa$ and $T\kappa$ have the same cardinality there needn’t be a nice bijection between them which is easy to think about. For example the free group on countably many elements is itself countable. But trying to use this to write down a monad on a monoid in the form of Definition 1 is a mess, because you have to pick an ugly bijection between the naturals and the free group on the naturals.

But I did eventually find a nice example! Let $T$ be the monad on $\mathbf{Set}$ for commutative monoids. In other words, $T$ sends a set $X$ to the underlying set of the free commutative monoid on $X$. An element of the free commutative monoid on $X$ is a ‘formal product’ of some elements of $X$; a finite list of elements of $X$ where the order doesn’t matter. Another way to think about this is to say that an element of $TX$ is a function $a:T\to\mathbb N$ which is zero on all but finitely many elements of $X$. The function $a$ says how many times each element of $X$ appears in the product.

Here’s how we can use this to get a nice example of Shulman’s consturction. Let $\mathbb N_{>0}$ be the set of positive integers. Then in this case there is a nice bijection between $\mathbb N_{>0}$ and $T\mathbb N_{>0}$.

Number the primes in the usual way ($p_1 = 2$, $p_2=3$, …). The unique factorisation theorem tells us that each positive integer can be expressed in the form $\prod_{n>0} p_n^{a(n)}$ for some unique $a:\mathbb N_{>0}\to\mathbb N$ which is zero on all but finitely many elements of $\mathbb N_{>0}$. But as we said above, the set of all such $a$ is precisely $T\mathbb N_{>0}$. So we have a bijection between $\mathbb N_{>0}$ and $T\mathbb N_{>0}$. Then Shulman’s construction yields the following monad on a monoid.

Example 5

Let $M$ be the set of all functions $\mathbb N_{>0}\to\mathbb N_{>0}$. For $f\in M$ define $\theta(f)$ to be the function

$$\prod_{n\geq 1} p_n^{a(n)}\quad\mapsto\quad\prod_{n\geq 1} p_{f(n)}^{a(n)}.$$

We take $h\in M$ to be the sequence of primes, $h(n) = p_n$, and define $m\in M$ by

$$m\left(\prod_{n\geq 1} p_n^{a(n)}\right)\quad=\quad\prod_{n\geq 1} n^{a(n)}.$$

This must satisfy Definition 1 because of the way that we constructed it from a monad on $\mathbf{Set}$. But you can check the axioms $(1)$ to $(5)$ by hand if you want.

The funny thing about this monad is that despite its complexity, $h$ and $m$ are just particular integer sequences. The map $h:\mathbb N_{>0}\to\mathbb N_{>0}$ is just the sequence of primes (OEIS A000040):

$$2,3,5,7,11,13,17,19,23,29,\dots,$$

but the sequence given by $m$ is a bit less familiar (OEIS A003963):

$$1, 1, 2, 1, 3, 2, 4, 1, 4, 3,\dots.$$

I think this is quite a weird sequence to suddenly appear from what I thought were very natural definitions!

To see what the significance of $m$ is, it helps to write down what the modules of this monad are. From Definition 2 we see that they are precisely the functions $k:\mathbb N_{>0}\to\mathbb N_{>0}$ such that

$$k(p_n) = n$$

and

$$k\left(\prod_{n\geq 1}p_{f(n)}^{a(n)}\right) = k\left(\prod_{n\geq 1}n^{a(n)}\right).$$

To me these equations look far too complicated to understand. But we can decode them by remembering how we defined our monad on $M$ in the first place. We restricted the free commutative monoid monad $T$ on $\mathbf{Set}$ to just the object $\mathbb N_{>0}$. The modules of $T$ are all commutative monoids. So the modules of our monad on $M$ must be precisely the commutative monoid structures that can be defined on $\mathbb N_{>0}$. The functions $k$ are just these commutative monoid structures, encoded as an integer sequences.

How does this encoding work? Suppose $*$ is a commutative monoid structure on $\mathbb N_{>0}$. Given a finite collection of positive integers in which $n$ appears $a(n)$ times, we can combine them using $*$ to get a single integer. Then the function $k_*$ that encodes $*$ is the one that sends $\prod_{n\geq 1} p_n^{a(n)}$ to this integer. You can check that such a $k$ satisfies the axioms above.

Note that there is more than one countable commutative monoid. So we’ve found a monad on a monoid whose category of algebras does not itself have only one object! This also proves that Example 5 is definitely not a special case of Example 3.

Finally, we can say what $m$ is. It’s multiplication itself, under the above encoding.

Next time

My next post is about the related subject of Adjunctions between Monoids. We’ll see that adjunctions and monads on monoids are even more closely related than adjunctions and monads on general categories! Here are some questions you can be thinking about if you want to get a head start:

• Given an adjunction between monoids, how can it be turned into a monad?
• Given a monad on a monoid, how can it be turned into an adjunction between monoids? (Remember that the category of modules can have more than one object!)
• Are these processes inverse to each other?
  

  ---

  Addendum: This post was discussed on Reddit.