## December 21, 2022

### Free Idempotent Rigs and Monoids

#### Posted by John Baez

I’ve been having a lot of fun on Mathstodon lately, and here’s an example.

A rig $R$ has a commutative associative addition, an associative multiplication that distributes over addition, an element $0$ with $r+0 = r$ and $0r = 0 = r0$ for all $r \in R$, and an element $1$ with $1r = r = r1$ for all $r \in R$.

A rig is idempotent if $r r = r$ for all $r \in R$.

Is the free idempotent rig on $2$ generators finite? If so, how many elements does it have?

Morgan Rogers raised this issue on the Category Theory Community server, and after a bit of progress I posed this as a puzzle on Mathstodon. By now three people there have independently figured out the answer.

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?

Posted at December 21, 2022 10:38 AM UTC

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

### Re: Free Idempotent Rigs and Monoids

Math Stackexchange gives a reference that — if it’s correct— should prove the rewrite rule I described is nonconfluent:

• M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics and its Applications 17, Addison-Wesley Publishing Co., Reading, Massachusetts, 1983.

Apparently this reference proves that

$b a c b c a b c = b a c a b c$

in the free commutative monoid on 3 generators, even though both sides are square-free words, so there is no way to further reduce them using the rewrite rule BB $\to$ B.

Posted by: John Baez on December 21, 2022 2:36 PM | Permalink | Reply to this

### Re: Free Idempotent Rigs and Monoids

It is a sort of example right before the proof of theorem 2.4.1 in Lothaire. If you want I can take a picture of it.

Posted by: Steve Huntsman on December 21, 2022 3:04 PM | Permalink | Reply to this

### Re: Free Idempotent Rigs and Monoids

Thanks! Someone else already did, and in fact I found the whole chapter online:

• Jean Berstel and Christophe Reuteneur, Square-free words and idempotent semigroups, in Combinatorics on Words, ed. M. Lothaire, Encyclopedia of Mathematics and its Applications volume 17, Addison-Wesley Publishing Co., Reading, Massachusetts, 1983.

They prove that

$b a c b c a b c = b a c a b c$

in the free commutative monoid on 3 generators, even though both sides are square-free words, so there is no way to further reduce them using the rewrite rule WW → W (where W is any word).

The proof is here:

Posted by: John Baez on December 22, 2022 1:10 PM | Permalink | Reply to this

### Re: Free Idempotent Rigs and Monoids

Dylan McDermott gave a much easier proof of non-confluence on the Category Theory Community Server:

$a b a b c b a b c \to a b a b c \to a b c$

but also

$a b a b c b a b c \to a b c b a b c$

Posted by: John Baez on December 24, 2022 5:49 PM | Permalink | Reply to this

### Re: Free Idempotent Rigs and Monoids

Two trivial formatting nits: One of your “$M$“s seems to have become a “$\latex M$”, and the URL for the Wiki page on confluence seems to have escaped its containing element.

Posted by: L Spice on December 23, 2022 9:06 PM | Permalink | Reply to this

### Re: Free Idempotent Rigs and Monoids

Thanks—fixed! Happy Holidays!

Posted by: John Baez on December 24, 2022 5:50 PM | Permalink | Reply to this

Post a New Comment