## Free Idempotent Rigs and Monoids

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 ∈ R and an element 1 with 1r = r = r1 for all r ∈ R

A rig is idempotent if r r = r for all r ∈ 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 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 47 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, and 3

Just 4 elements! It follows that when we start adding any element 4 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 47 = 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, three 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 WW → 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 generators 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 that the free idempotent rig on n generators is also finite. 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 ≤ 4160 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?

### 7 Responses to Free Idempotent Rigs and Monoids

1. Hendrik Jan says:

Perhaps this answer at stackexchange is relevant for the (non-)equivalence of squarefree words? https://math.stackexchange.com/a/1371805/45179

• John Baez says:

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

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

This reference proves that

bacbcabc = bacabc

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:

• John Baez says:

Dylan McDermott gave a much easier proof of nonconfluence on the Category Theory Community Server:

ababcbabc → ababc → abc

but also

ababcbabc → abcbabc

2. Allen Knutson says:

It feels like you should be able to filter based on number of letters necessary. I guess I’m less clear on what “associated graded” should mean in something that isn’t an abelian group, or else I’d want to solve the associated (graded) problem r^2=0 first.

3. Greg Egan says:

I’ve posted my own list of the 284 elements, and the full equivalence classes (i.e. all the ways of writing each element as a linear combination of the 7 monomials):

https://github.com/nagegerg/IdempotentRig

• John Baez says:

Thanks—that’s great!

I just learned that there’s a formula for the number of elements of the free monoid on $n$ letters:

$\displaystyle{ \sum_{k = 0}^n \binom{n}{k} \prod_{i = 1}^k (k - i + 1)^{2^i} }$

So, the cardinality of the free idempotent rig on $n$ letters is bounded by 4 to this power, but it’s a terribly bad bound.

I found this formula here:

• Todd Rowland and Eric W. Weisstein, Free idempotent monoid, MathWorld–A Wolfram Web Resource.

4. b_jonas says:

I believe “when we start adding any element 4 of the free idempotent rig on 2 generators to itself” is a typo for “when we start adding any element of the free idempotent rig on 2 generators to itself”

I would guess that a rewrite rule like WW → W to remove repeated subwords […] allow us to reduce any element of the free idempotent monoid on n generators to a ‘normal form’

The difficulty is that we’re allowed to apply the rewrite rule backwards too, as W → WW. Sometimes you can simplify a word only after you make it longer with the backwards rule. There was actually a very relevant problem posed in the KöMaL contest: A. 234., posed in 2000. “https://www.komal.hu/verseny/2000-03/A.h.shtml” has the solution, “https://www.komal.hu/verseny/2000-03/mat.e.shtml” has the English specification. This asks you to prove that the monoid is finite by proving that you can rewrite any word to a word that is not longer than 8 letters. The solution page also notes that there are multiple essentially different cases when you do need to make the word longer at first. The simplest example that it gives is:

abacbcacb = abacbca(cb) → abacbca(cbcb) = ab(acbcacbc)b → ab(acbc)b = aba(cbcb) → aba(cb) = abacb

I don’t really understand how this monoid works either though.

This site uses Akismet to reduce spam. Learn how your comment data is processed.