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 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 and has at most 47 elements. To see this, first consider the free idempotent monoid on 2 generators, say This is the free monoid on 2 generators modulo relations saying that everything squared is itself. This has 7 elements:
Starting from this we can form the free idempotent rig on and by taking linear combinations. But notice that in an idempotent rig we have
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:
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:
Since 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
because both sides equal More surprisingly, MathCuddler discovered that
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
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:
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 is a square-free word on 3 letters, while is not.
But something more interesting happens for the free idempotent monoid generators. When 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?
Perhaps this answer at stackexchange is relevant for the (non-)equivalence of squarefree words? https://math.stackexchange.com/a/1371805/45179
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:
Dylan McDermott gave a much easier proof of nonconfluence on the Category Theory Community Server:
ababcbabc → ababc → abc
ababcbabc → abcbabc
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.
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):
I just learned that there’s a formula for the number of elements of the free monoid on letters:
So, the cardinality of the free idempotent rig on 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.
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”
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.