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?

This entry was posted on Wednesday, December 21st, 2022 at 12:51 pm and is filed under mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

7 Responses to Free Idempotent Rigs and Monoids

  1. Hendrik Jan says:
    21 December, 2022 at 2:13 pm

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

    Reply
    • John Baez says:
      21 December, 2022 at 2:30 pm

      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:

      Reply
    • John Baez says:
      23 December, 2022 at 6:05 pm

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

      ababcbabc → ababc → abc

      but also

      ababcbabc → abcbabc

      Reply
  2. Allen Knutson says:
    21 December, 2022 at 10:29 pm

    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.

    Reply
  3. Greg Egan says:
    22 December, 2022 at 4:50 am

    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

    Reply
    • John Baez says:
      22 December, 2022 at 10:12 am

      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.

      Reply
  4. b_jonas says:
    11 January, 2023 at 3:00 pm

    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.

    Reply

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

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