The n-Category Café

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.

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$$

Five years on, I think I can do better. I claim that the free monoid functor $F: \mathbf{Set} \to \mathbf{Set}$ satisfies

$$F^3(X) + F^3(X) \cong X + F^3(X)$$

naturally in $X \in \mathbf{Set}$. In other words,

$$2F^3 \cong id + F^3.$$

And I think this is about the closest true approximation to the false statement $F^3 \cong id$.

Previously, I proved the following. Let $R$ be a commutative rig (semiring) and $f: R \to R$ a map of sets satisfying

$$f(x) = 1 + x f(x)$$

for all $x \in R$. Then

$$f^3(x) + \Bigl[(x + f^2(x))f^3(x)\Bigr] = x + \Bigl[(x + f^2(x))f^3(x)\Bigr]$$

for all $x \in R$.

I’m now claiming that under the same hypotheses, a simpler conclusion is true:

$$2f^3(x) = x + f^3(x)$$

for all $x \in R$.

To prove this, let me introduce some notation. When $x, y \in R$, write $x \geq y$ to mean that $x = y + z$ for some $z \in R$. For instance, we have

$$f^n(x) = 1 + f^{n - 1}(x) f^n(x)$$

for all $n \geq 1$ and $x \in R$, so $f^n(x) \geq 1$ and

$$f^n(x) \geq f^{n - 1}(x) f^n(x).$$

Repeatedly using the observations in the last sentence, we have, for all $x \in R$:

$$\begin{aligned} f^3(x) & \geq f^2(x) f^3(x) \\ & \geq f(x) f^2(x) f^3(x) \\ & = (1 + x f(x)) f^2(x) f^3(x) \\ & = f^2(x) f^3(x) + x f(x) f^2(x) f^3(x) \\ & \geq f^2(x) f^3(x) + x \cdot 1 \cdot 1 \cdot f^3(x) \\ & = (x + f^2(x)) f^3(x). \end{aligned}$$

So

$$f^3(x) = (x + f^2(x)) f^3(x) + r$$

for some $r \in R$. Adding $r$ to each side of the equation proved five years ago — namely,

$$f^3(x) + \Bigl[(x + f^2(x))f^3(x)\Bigr] = x + \Bigl[(x + f^2(x))f^3(x)\Bigr]$$

— gives

$$f^3(x) + f^3(x) = x + f^3(x),$$

completing the proof.

Drop back in 2024 for the next update.

That’s a really interesting idea!

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.

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.

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.