Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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 RR has a commutative associative addition, an associative multiplication that distributes over addition, an element 00 with r+0=rr+0 = r and 0r=0=r00r = 0 = r0 for all rRr \in R, and an element 11 with 1r=r=r11r = r = r1 for all rRr \in R.

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

Is the free idempotent rig on 22 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 aa and bb, has at most 4 74^7 elements. To see this, first consider the free idempotent monoid on 2 generators, say MM. This is the free monoid on 2 generators modulo relations saying that everything squared is itself. This has 7 elements:

M={1,a,b,ab,ba,aba,bab} 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 aa and bb by taking linear combinations. But notice that in an idempotent rig we have

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

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

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

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

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

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

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

a+ab+ba+b=a+b a + a b + b a + b = a + b

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

ab+ba=aba+bab a b + b a = a b a + b a b

because

ab+ba=(ab+ba) 2=(ab) 2+(ab)(ba)+(ba)(ab)+(ba) 2=ab+aba+bab+ba 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

aba+aba=(aba+aba) 2=(aba) 2+(aba)(bab)+(bab)(aba)+(bab) 2=aba+ab+ba+bab 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.M.

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

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

M={1,a,b,ab,ba,aba,bab} 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 abcbaa b c b a is a square-free word on 33 letters, while abcbca b c b c is not.

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

I don’t actually understand this. I would guess that a rewrite rule like WWWW 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 nn letters to a ‘normal form’ which is a square-free word. If this were true, I think the free idempotent monoid on nn generators would be infinite — because there are infinitely many square-free words on nn 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 4 160\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

6 Comments & 0 Trackbacks

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

bacbcabc=bacabc 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

bacbcabc=bacabc 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:

ababcbabcababcabc a b a b c b a b c \to a b a b c \to a b c

but also

ababcbabcabcbabc 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 “MM“s seems to have become a “latexM\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