## April 3, 2013

### 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.

Posted at April 3, 2013 7:42 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2608

### Re: Iterating the Free Monoid Construction

The set of binary strings $B$ is defined by

(1)$B = 2B + 1,$

so it has cardinality -1. If we define

(2)$ST[M,N] = [N, B M + N]$

then

(3)$(ST)^3[M,N] = [B M + (B+1)N, B N + B(B+1)M + (B+1)N]$

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

(4)$2(B+1) = 2B + 1 + 1 = B + 1$

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.

Posted by: Mike Stay on April 3, 2013 8:47 PM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

It’s a great question, and I hope there’s a really nice answer. I’ve heard it asked before by Joachim Kock — which is funny, because I’m building up to another post inspired by a thought of Joachim’s.

The following isn’t directly relevant to the question, but the first thought I had when I read the title “Iterating the free monoid construction” was globular pasting diagrams. Writing $F$ for the free monoid construction, an $n$-dimensional globular pasting diagram is precisely an element of $F^n 1$.

For example, an element of $F^1 1$ is a natural number $k$, which can be thought of as a chain of $k$ arrows.

An element of $F^2 1 = F \mathbb{N}$ is a finite sequence $(k_1, \ldots, k_n)$ of natural numbers. This can be thought of as the 2-dimensional globular pasting diagram consisting of (from left to right) $k_1$ 2-cells stacked up, then $k_2$ 2-cells stacked up, and so on, so that the whole thing is $n$ units wide. I’m too lazy to draw a picture.

Posted by: Tom Leinster on April 4, 2013 1:23 AM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

Here’s a first contribution. The free monoid monad $F$ satisfies $F X \cong 1 + X \times F X.$ On the one hand, this is a recursive definition (since an element of the free monoid on a set $X$ is either the empty sequence or an element of $X$ followed by an element of the free monoid on $X$). On the other hand, it’s the closest thing to $F X = \frac{1}{1 - X}$ that can be stated without subtraction or division.

Let’s see if we can take John’s calculation that doing $X \mapsto \frac{1}{1 - X}$ three times over is the identity, and redo it without mentioning subtraction or division. This is the kind of thing Marcelo Fiore and I used to do, so it’s pleasantly nostalgic for me.

I’ll switch to small letters. Formally speaking, I’m going to work in a commutative rig $R$ equipped with a map of sets $f\colon R \to R$ satisfying $f(x) = 1 + x f(x)$ for all $x \in R$. Now, for any $x$, $f^2(x) = 1 + f(x)f^2(x).$ Multiplying by $x$ then adding $f^2(x)$, $(1 + x)f^2(x) = x + (1 + x f(x))f^2(x)$ and so $(1 + x)f^2(x) = x + f(x)f^2(x).$ Next add 1 to each side: $1 + f^2(x) + x f^2(x) = x + (1 + f(x)f^2(x))$ or equivalently $1 + x f^2(x) + f^2(x) = x + f^2(x).$ If we could cancel then we’d have $1 + x f^2(x) = x$, which is a riggy version of the statement $f^2(x) = \frac{x-1}{x}$ that appeared in John’s calculation.

So that tells us about $f^2(x)$; let’s do $f^3(x)$. We have $f^3(x) = 1 + f^2(x)f^3(x).$ Multiplying each side by $x$ then adding $(1 + f^2(x))f^3(x)$, this gives $(1 + x + f^2(x))f^3(x) = x + (1 + x f^2(x) + f^2(x))f^3(x)$ which by the result of the previous paragraph gives $(1 + x + f^2(x))f^3(x) = x + (x + f^2(x))f^3(x).$ Now rearranging, $f^3(x) + [(x + f^2(x))f^3(x)] = x + [(x + f^2(x))f^3(x)].$ If we could cancel the term in square brackets, we’d be able to conclude that $f^3(x) = x$.

One notable thing about this conclusion is that only additive cancellation is needed. Before I did the calculation, I was imagining that we’d need multiplicative cancellation too.

Posted by: Tom Leinster on April 4, 2013 2:23 AM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

It’s maybe worth noting that there are no nontrivial cases in which the three-times iterated free monoid functor is literally isomorphic to the identity functor — at least, not if we’re in the easiest setting for the free monoid construction (the one in brackets above).

Proof: suppose that $F^3(X) \cong X$ for all $X$. Then, in particular, $F^3(0) \cong 0$, where $0$ is the initial object. Now $1$ is a summand of $F(Y)$ for any $Y$, so $1$ is a summand of $F^3(0)$, so $1$ is a summand of $0$. On the other hand, it’s a general fact about categories that any summand of an initial object is initial. So $1$ is initial, which gives $X \cong X \times 1 \cong X \times 0 \cong 0$ for all $X$. Hence $C$ is equivalent to the terminal category.

This backs up what John wrote at the end of his post: we have to shoot for something less ambitious than $F^3 \cong id$.

My calculations above have a corollary. To state it, we need some terminology and a lemma. In a commutative semigroup $(R, +)$, call an element $h \in R$ high if for all $s \in R$ there exists $t \in R$ such that $h = s + t$.

Lemma Let $h_1$ and $h_2$ be high elements of a commutative semigroup $(R, +)$. If $h_1 + r = h_2 + r$ for some $r \in R$ then $h_1 = h_2$.

I think this goes back to the 1950s; Marcelo Fiore and I rediscovered it and gave it as Corollary 3.4 of our paper Objects of categories as complex numbers. The key fact behind the lemma is that the set of high elements of a commutative semigroup $R$ is either empty or forms a group — with the same binary operation as $R$, but usually a different identity!

Anyway, the calculation of my previous post shows that if $F^3(X)$ and $X$ are high then $F^3(X) \cong X$. In fact, we can drop the hypothesis that $F^3(X)$ is high: for $X$ is a summand of $F(X)$, which is a summand of $F^2(X)$, which is a summand of $F^3(X)$, so if $X$ is high then $F^3(X)$ is too. Hence:

Corollary Let $C$ be a category and $F\colon C \to C$ a functor such that

$F(X) \cong 1 + X \times F(X)$

for all $X \in C$. (Fo r instance, let $C$ be a category with finite products and countable coproducts, with products distributing over coproducts, and let $F$ be free monoid.) Let $X$ be an object of $C$ such that for all $Y \in C$, there exists $Z$ in $C$ with $X \cong Y + Z$. Then $F^3(X) \cong X$.

However, I can’t think of any interesting instances of this.

Posted by: Tom Leinster on April 4, 2013 11:02 AM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

Tom, you might want to look at Schutzenberger’s theory of rational power series over semirings and formal language theory. The book of Berstel and Reutenauer is good for this. They take a similar approach to you on thinking about these things.
Posted by: Benjamin Steinberg on April 5, 2013 12:37 AM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

In the category of sets, $F(X)$ is always high, right? So we should get an isomorphism between $F(X)$ and $F^4(X).$

Posted by: Mike Stay on April 5, 2013 2:42 AM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

Well, supposing choice, $|F(X)| = | X + \omega |$; but that doesn’t say much; on the other hand, we already have $|F(F(X))| = |F(X)|$!

The thing that has been bothering me this whole time is that the analogy $F(X) \sim \frac{1}{1-X}$ can’t mean $F^2 (X) \sim \frac{X-1}{X}$, because $F$, being defined by its power series, doesn’t belong to the domain of convergence of that power series to $\frac{1}{1-X}$; for instance, in graded things, this is reflected in that even if $F(X)$ is of finite type, $F(F(X))$ is not. Incidentally, the fixed-points of $X\mapsto \frac{1}{1-X}$ are $\frac{1\pm i\sqrt{3}}{2}$, which aren’t in the domain of convergence either.

Posted by: Jesse McKeown on April 5, 2013 3:13 PM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

This is related to the fact that generally speaking, you can’t substitute one formal power series $G(x)$ into another $F(x)$ unless some conditions are satisfied, e.g., you can do it if $G(x)$ has constant term zero or if $F(x)$ is polynomial.

At the categorified level, you can substitute one functor into another with impunity, or relatedly you can always define the substitution product (= plethystic product) of two Joyal species, but if you want your coefficient objects to be finite (so as to avoid traps like Eilenberg swindles), then analogous restrictions apply.

Posted by: Todd Trimble on April 5, 2013 3:56 PM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

Jesse wrote:

Well, supposing choice, $∣F(X)∣=∣X+\omega∣$; but that doesn’t say much; on the other hand, we already have $∣F(F(X))∣=∣F(X)∣$!

To me what’s interesting in this context is not isomorphisms but natural isomorphisms. The fact that you’re resorting to the axiom of choice shows you’re missing the fun to be had here.

If $CountSet$ is the category of countably infinite sets and

$F: CountSet \to CountSet$

is the free monoid functor, is $F^3$ naturally isomorphic to the identity? That would be really interesting to me.

As for convergence of power series, I’m afraid when I’m playing this particular kind of game, I follow the brazen words of Heaviside:

The series diverges; therefore we can do something useful with it.

For example, the species of binary (finite, rooted, planar) trees comes with an isomorphism

$T(z) \cong z + T(z)^2$

This says “trees with $z$-colored leaves correspond to either $z$-colorings of the unique leaf or pairs of trees of this sort.” We can then decategorify and get an equation between generating functions

$T(z) = z + T(z)^2$

which gives

$T(z) = (1 - \sqrt{1 - 4z})/2$

and using a Taylor series

$T(z) = z + z^2 + 2z^3 + 5z^4 + 14z^5 + 42z^6 + \cdots$

The coefficients are the Catalan numbers, and this says things like: the number of binary trees with six leaves, all $z$-colored, is $42 z^6$. And that’s right.

Now we can do something crazy like evaluate this at $z = 1$, which is outside the radius of convergence. We should get the cardinality of the set of finite binary trees: the sum of all the Catalan numbers. This obviously diverges, but we can brazenly try to compute it using

$T(z) = (1 - \sqrt{1 - 4z})/2$

We get a complex number, namely a sixth root of unity… which makes no sense… but Blass showed that all this craziness actually can lead to correct mathematics if we’re clever enough.

We can even set $z = -1$, get the golden ratio, and make sense of that! See Robin Houston’s construction of a golden object.

So, the idea is to start by being very reckless, and then use a lot of category theory and intelligence to save the day. In this blog article I did the first part… then Tom started doing the second part.

Posted by: John Baez on April 6, 2013 1:54 AM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

If $CountSet$ is the category of countably infinite sets and

$F: CountSet \to CountSet$

is the free monoid functor, is $F^3$ naturally isomorphic to the identity? That would be really interesting to me.

It’s not though, because there’s not even a natural transformation from $F^3$ to the identity. Indeed, we have the obvious unit transformation $u: Id \to F$ (the inclusion of $X$ into $1 + X + X^2 + \ldots$), and so we also have transformations from $F$ to $F F F$ such as

$F \stackrel{F u}{\to} F F \stackrel{F F u}{\to} F F F;$

thus, if there were a transformation $F F F \to Id$, there would have to be one of the form $F \to Id$ as well. I will show this is not the case.

Suppose we had a transformation $\theta: F \to Id$, so for each countable set $X$ we have a component

$\theta_X: 1 + X + X^2 + \ldots \to X.$

Let $c_X$ be the value of $\theta_X$ applied to the unique element of the summand $1$. Then the commutativity of the naturality square would force the equation

$c_Y = f(c_X)$

for every function $f: X \to Y$. This is absurd.

This kind of argument shows what sorts of restricted contexts might be involved to get anything like this to work.

Posted by: Todd Trimble on April 7, 2013 2:10 AM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

Great argument, Todd! Even though the result makes me a bit sad…

Posted by: John Baez on April 7, 2013 2:56 AM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

Well, I wasn’t trying to strike a death blow to the entire enterprise; in fact I’d been thinking a little on this problem in a more optimistic spirit.

I’m afraid I don’t have any really bright ideas to share at the moment, but my own vague thoughts were pushing me more in the direction of hoping one could cook up some sort of weak equivalence between $F^3$ and the identity, as realized on some other category (like species valued in $\mathbb{Z}_2$-graded chain complexes, or something). There one can play with the idea that the degree 1 shift functor behaves something like additive inverse, and there are stack-y sorts of constructions one could try… as I say, I’m not really prepared to say a whole lot more at the moment. But there could be hope.

Posted by: Todd Trimble on April 7, 2013 3:25 AM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

Tom wrote:

$f^3(x) + [(x + f^2(x))f^3(x)] = x + [(x + f^2(x))f^3(x)].$

Bravo! I’m so glad you took a crack at this, because after those papers you wrote with Marcelo, you know more tricks than almost anyone else for dealing with this sort of problem.

The above equation, while less charismatic than $f^3(x) = x$, has the virtue of being true… and it’s a fact about free monoids that we might never have guessed had not the tempting mirage of $f^3(x) = x$ lured you through the desert of calculations.

And it seems to me your argument says a bit more. Suppose we have any symmetric rig category $\mathcal{R}$ equipped with a functor $F : \mathcal{R} \to \mathcal{R}$ equipped with a natural isomorphism

$F(X) \stackrel{\sim}{\longrightarrow} 1 \; \oplus \; X \otimes F(X)$

For example, $\mathcal{R}$ could be the category of sets, or countable sets, or vector spaces, or countable-dimensional vector spaces, or $R$-modules for any commutative ring, or countably generated ones, or topological spaces, or simplicial sets, or lots of other familiar categories. Then we get

$F^3(X) \oplus [(X \oplus F^2(X)) \otimes F^3(X)] \cong X \oplus [(X \oplus F^2(X)) \otimes F^3(X)]$

This is quite nice.

And then we can take the Grothendieck group of $\mathcal{R}$, forming an abelian group generated by isomorphism classes of objects of $\mathcal{R}$ and then imposing the relation $[X \oplus Y] = [X] + [Y]$. And in this group we can simplify the above equation to

$[F^3(X)] = [X]$

Unfortunately this Grothendieck group is trivial in the examples I’ve given. For example, the Grothendieck group of the category of finite-dimensional vector spaces is $\mathbb{Z}$, where the integer comes from the dimension of a vector space. But if we go to all vector spaces, or even countable-dimensional ones, the Grothendieck group becomes trivial, because for any vector space $V$ there’s a vector space $W$ such that $V \oplus W \cong W$, so we get $[V] = 0$.

So, the magic wand of subtraction, which could transform the ugly frog

$F^3(X) \oplus [(X \oplus F^2(X)) \otimes F^3(X)] \cong X \oplus [(X \oplus F^2(X)) \otimes F^3(X)]$

into the handsome prince

$F^3(X) \cong X$

is so powerful that it has a dangerous tendency to make the prince disappear in a puff of smoke:

$X \cong 0$

Posted by: John Baez on April 4, 2013 5:14 PM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

The free monoid on a set X is precisely the set of all binary trees whose leaves are elements of X, modulo tree rotation. So perhaps one can take Andreas Blass’ construction for T7 =T, insert some tree rotations into it, and represent it as the composition T7 =T4 =T, where each equality sign comes from F4=F?

Posted by: Dmitri Pavlov on April 4, 2013 9:49 AM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

That’s a really interesting idea!

Posted by: John Baez on April 4, 2013 7:30 PM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

The construction relating to trees is the free magma on a set; I suppose that iterating that seven times would give a similar result to iterating the free monoid three times.

Posted by: Mike Stay on April 5, 2013 2:40 AM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

@Mike Stay: I guess you are right, I looked at Blass’ construction a long time ago and forgot the precise statement.

Posted by: Dmitri Pavlov on April 5, 2013 7:37 AM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

Relevant to your idea is the notion of a generating function that mods out by the associator (what you call tree rotations). Bill Gosper gives the basic “all-1” generating function here.

Posted by: Mike Stay on April 10, 2013 8:29 PM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

Posted by: RodMcGuire on April 10, 2013 9:39 PM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

I’ve been thinking about iterating free commutative monoid construction recently because in Set, you get the natural numbers under addition on the first iteration an the positive naturals under multiplication on the second. I haven’t calculated the cube.

Free commutative monoids have implicit orders, so our first two sequence members are <= and divides. Furthermore the free commutative monoids are all countable with an isomorphic (as sets) with the isomorphism from the constructed monoid being monotonic. The function in the opposite direction is constructing an increasing sequence of countable ordinals.

My thinking hasn’t progressed much beyond this, yet.

Posted by: Roger Witte on April 5, 2013 11:57 PM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

Roger wrote:

I’ve been thinking about iterating the free commutative monoid construction recently because in Set, you get the natural numbers under addition on the first iteration an the positive naturals under multiplication on the second. I haven’t calculated the cube.

I’ve thought about that stuff a bit. In quantum mechanics, if we have a kind of bosonic particle with some Hilbert space $H$, the Hilbert space for finite collections of particles of this type is the Hilbert space closure of the symmetric algebra on $H$. This is called the Fock space of $H$. It’s a lot like the free commutative monoid on $H$ in the category of Hilbert spaces.

If particular, if we choose an orthonormal basis for $H$, say some set $P$, then the Fock space of $H$ has an orthonormal basis given by the free commutative monoid on $P$! Let’s call this $S P$.

So, people like to start with an imaginary particle called the primon, where $P$ is the set of prime numbers. The Fock space then describes the free Riemann gas, made of finite collections of primons. This has a basis given by the free commutative monoid $S P$. By the fundamental theorem of arithmetic, this is the set of positive natural numbers, with multiplication as the monoid operation.

People have pondered how the Riemann zeta function can be understood in physical terms this way. I explained this in week199 of This Week’s Finds.

However, you can repeat this process and look at $S S P$: the free commutative monoid on the free commutative monoid on the set of primes. This is the free commutative monoid on the set of positive natural numbers.

A positive natural number can be thought of as the state of a string with waves moving counterclockwise (or if you prefer, clockwise) around it. The wave can wiggle any positive natural number of times. Such a wave is called a ‘left-mover’ (or if you prefer, a ‘right-mover’.)

So, $S S P$ is nicely thought of as the Hilbert space for a finite collection of strings with only left-moving vibrations.

These are strings in 1-dimensional space. To describe a state of a string in $n$-dimensional space, we need an $n$-tuple of positive natural numbers. Also, things get a bit more complicated when we consider both left-movers and right-movers, as we ultimately should.

Still, there is something intriguing about this. If you like it, you might also peek at my webpage on nth quantization. I tell the story a bit differently here, since I wasn’t trying to work primes into the game.

The term ‘nth quantization’ alludes to the fact that people often use ‘2nd quantization’ for the second step of this sort of iterative process.

Posted by: John Baez on April 6, 2013 1:25 AM | Permalink | Reply to this

### Re: Iterating the Free Monoid Construction

People sometimes use ‘third quantization’ to describe a theory with operators describing the creation and annihilation of universes, which are themselves described by second quantization (i.e., quantum field theory). It’s a way to (try to) formalize the concept of ‘multiverse’.

Here Faizal uses fourth quantization to describe a theory with operators describing the creation and annihilation of multiverses!

I think that if one is going to go this far in this direction, one should go infinitely far in this direction.

Posted by: John Baez on April 7, 2013 3:41 AM | Permalink | Reply to this
Read the post Who Ordered That?
Weblog: The n-Category Café
Excerpt: A very odd and elementary conjecture of Kontsevich has now been proved.
Tracked: October 2, 2013 10:04 PM

Post a New Comment