### Iterating the Free Monoid Construction

#### Posted by John Baez

The free monoid on a set $X$ is

$F X = 1 + X + X^2 + X^3 + \cdots$

and the same formula works in many other categories. I guess it works in any monoidal category with coproducts, where the tensor product distributes over coproducts.

Sometimes it’s nice to study this free monoid construction using geometric series, by pretending that

$F X = \frac{1}{1 - X}$

It doesn’t exactly make sense, at least not to me, since I can’t think of any categories where I know both what “$1 - X$” means for an object $X$, and what the “reciprocal” of an object means. But we can still sometimes squeeze some useful insights out of this idea.

But Mike Stay asks, what about $F F F X$?

If we say

$F X = \frac{1}{1 - X}$

then

$F F X = \frac{1}{1 - \frac{1}{1-X}} = \frac{X-1}{X}$

and

$F F F X = \frac{1}{1 - \frac{X-1}{X}} = X$

We’re back where we started from! This is familiar in the theory of $SL(2,\mathbb{Z})$, where the matrix

$\left( \begin{array}{cc} A & B \\ C & D \end{array} \right)$

acts as a fractional linear transformation

$X \mapsto \frac{A X + B}{C X + D}$

But this matrix and its negative give the same fractional linear transformation. So, it’s really the quotient $SL(2,\mathbb{Z})/\pm I = PSL(2,\mathbb{Z})$ that matters here. The transformation $F$ corresponds to a famous element of order 6 in $SL(2,\mathbb{Z})$, namely

$\left( \begin{array}{cc} 0 & 1 \\ -1 & 1 \end{array} \right)$

But when you cube this element, you get

$\left( \begin{array}{cc} 0 & 1 \\ -1 & 1 \end{array} \right)^3 = - \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right)$ so the corresponding element in $PSL(2,\mathbb{Z})$ has order 3.

Anyway, Mike’s puzzle is this:

**Puzzle.** Is there some context in which the cube of the free monoid construction is ‘the same’ as doing nothing at all… perhaps in some weak sense of ‘the same’?

When I say ‘weak sense’ you should be thinking things like ‘$F^3 X$ has some of the same invariants as $X$’, or maybe ‘$F^4 X$ has some of the same invariants as $F X$’. And you should be reminded of Andreas Blass’ paper Seven trees in one, which uses similar shenanigans to motivate, and then find, a nice bijection between $T^7$ and $T$, where $T$ is the set of finite binary trees.

Of course, because $F$ is a monad, we have morphisms $F F X \to F X$ and $X \to F X$. But I don’t see how these help with Mike’s puzzle.

## Re: Iterating the Free Monoid Construction

The set of binary strings $B$ is defined by

so it has cardinality -1. If we define

then

Now, $B+1$ is like zero in the sense that

It’s the additive identity for the infinite objects.

The infinite zero shows up in both slots only after the third iteration of $ST$. Also, there’s this “negation” of both numerator and denominator that you mentioned, so unless we mod out our data types by common multiples, ST has period 6. We finally get an isomorphism between $(ST)^3$ and $(ST)^9$.

None of this bears directly on my question about $F,$ though.