The n-Category Café

I’ll let you think about the free idempotent rig on 1 generator.

The free idempotent rig on 2 generators, say $a$ and $b$, has at most $4^7$ elements. To see this, first consider the free idempotent monoid on 2 generators, say $M$. This is the free monoid on 2 generators modulo relations saying that everything squared is itself. This has 7 elements:

$$M = \{ 1, a, b, a b, b a, a b a, b a b \}$$

Starting from this we can form the free idempotent rig on $a$ and $b$ by taking linear combinations. But notice that in an idempotent rig we have

$$1 + 1 + 1 + 1 = (1+1)^2 = 1 + 1$$

or $4 = 2$, for short. We thus get $5 = 3$, $6 = 4 = 2$, etc. So, these are all the elements we get by repeatedly adding $1$:

$$0, \; 1, \; 2 = 1 + 1, \; and \; 3 = 1 + 1 + 1$$

Just 4 elements! It follows that when we start adding any element $r$ of the free idempotent rig on 2 generators to itself, we get at most 4 different elements:

$$0, \; r , \; 2r \; and \; 3r$$

Since $M$ has 7 elements, it follows that the free idempotent rig on 2 generators has at most $4^7 = 16384$ elements.

But in fact it has far fewer, because there are a lot of other relations. For example we have

$$a + a b + b a + b = a + b$$

because both sides equal $(a + b)^2$. More surprisingly, MathCuddler discovered that

$$a b + b a = a b a + b a b$$

because

$$a b+b a = (a b+b a)^2 = (a b)^2 + (a b)(b a) + (b a)(a b) + (b a)^2 = a b + a b a + b a b + b a$$

but also

$$a b a + a b a = (a b a + a b a)^2 = (a b a)^2 + (a b a)(b a b) + (b a b)(a b a) + (b a b)^2 = a b a + a b + b a + b a b$$

so they’re equal.

Nonetheless, 3 people on Mastodon have worked through the maze of relations with the help of a computer: Alex Gunning, Greg Egan and Simon Frankau.

They all concluded that the free idempotent rig on 2 generators has 284 elements!

You can see a list of the elements on Simon’s github, along with his code, and another list of the elements on Alex’s github. On his github, Greg Egan has posted a list of the elements together with all ways of writing each element as a linear combination of the 7 elements of $M.$

The next question: how many elements does the free idempotent rig on $3$ generators have?

This is more interesting. When I said the free idempotent monoid on $2$ generators has 7 elements, you may have just looked at this:

$$M = \{ 1, a, b, a b, b a, a b a, b a b \}$$

and accepted it, because these are clearly all the 7 ‘square-free words’ on two letters. A square-free word is one that don’t contain a nonempty repeated subword. For example $a b c b a$ is a square-free word on $3$ letters, while $a b c b c$ is not.

But something more interesting happens for the free idempotent monoid $n \ge 3$ generators. When $n \ge 3$, there are infinitely many square-free words on $n$ letters, and yet the the free idempotent monoid on $n$ generators is still finite!

I don’t actually understand this. I would guess that a rewrite rule like $W W \to W$ to remove repeated subwords would be terminating and confluent and thus allow us to reduce any element of the free idempotent monoid on $n$ letters to a ‘normal form’ which is a square-free word. If this were true, I think the free idempotent monoid on $n$ generators would be infinite — because there are infinitely many square-free words on $n$ letters. So it seems this algorithm cannot actually be confluent! But I haven’t found a case of non-confluence. Can you help straighten me out here?

Anyway, the fact that the free idempotent monoid on n generators is finite implies the same for the free idempotent rig on n generators. For example, the Online Encyclopedia of Integer Sequences assures us that the free idempotent monoid on 3 generators has 160 elements. Given this, the free idempotent rig on 3 generators must have $\le 4^{160}$ elements, by the same argument I gave for 2 generators. But in fact it should have far fewer.

Is anyone brave enough to compute the number?