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