Here's a puzzle about rigs I don't know the answer to!
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 rr = r for all r ∈ R.
The free idempotent rig on two generators is finite. But how many elements does it have?
It has at most 4⁷ elements, but in fact far fewer.
(1/n)
We can start by taking two elements a and b and multiplying them in all ways subject to associativity and the idempotent law. We get just 7 elements:
1, a, b, ab, ba, aba, bab
Then we start adding these. In an idempotent rig r + r + r + r = r + r for any element r, so we get at most 4⁷ elements.
Why is that equation true? Because
(1+1)² = 1 + 1
(2/n)
But the free idempotent rig on two generators has far fewer than 4⁷ elements! After all, it obeys many more relations, like
a + ab + ba + b = a + b
(Notice that we can't get from this to ab + ba = 0, since we can't subtract.)
So, how many elements does it have?
By the way, the free idempotent rig on 3 generators is probably infinite, since there are infinitely many 'square-free words' with 3 letters:
https://en.wikipedia.org/wiki/Square-free_word
(3/n, n = 3)
@johncarlosbaez hang on do you mean a +ab +ba+b=a+b?
@johncarlosbaez
I believe the number is small enough that it's hand-countable (the figure I've gotten is 278 though it's bashy enough I've likely made a mistake)
@alexthecamel @johncarlosbaez
Taking the last few observations into account, my current upper bound count contains at least...
Terms where at most one term of each degree appears,
\(1+3 \times 2^3 \times 3^3 + (2 \times 3) \times 2^2 \times 3^2 + (2\times 3) \times 2 \times 3 + 2 \times 3 = 907\)
That's "0", terms with non-zero deg 1 coeff, terms with non-zero deg two coeff etc.
... that's already more than @alex counted, are there identities for terms like \(1 + a + ab + aba\) I'm missing?
@rogers @johncarlosbaez
you do have ab+ba=(ab+ba)^2=ab+ba+bab+aba=(aba+bab)^2=aba+bab, right?
@alexthecamel @johncarlosbaez that specific one wouldn't affect this count, but maybe there's a similar one for \(ab + aba\)?
@rogers @johncarlosbaez
will get a picture of the categories I have when my phone charges enough
@rogers @johncarlosbaez
hopefully it is not too unclear what I mean here
@rogers @johncarlosbaez
of course 4^7 is a small enough number that you could just computationally build a graph with vertices connected with the x+y=x+xy+yx+y eq relation and find connected components
@rogers @johncarlosbaez
the a+b vs - and 1+a+b vs - entries should be 0, giving us a figure of 284, and i seem to have gotten some python code to spit out the same number, so I'll call that probably correct
It makes me nervous that @alexthecamel is getting 284 elements in the free idempotent rig on two generators, @rogers is getting an upper bound of 907:
https://mathstodon.xyz/@rogers@lipn.info/109546815378501526
and @gregeganSF is getting 1615:
@johncarlosbaez @alexthecamel @rogers My count is definitely wrong, I’ll be doing a fresh calculation later today.
@gregeganSF @johncarlosbaez @alexthecamel My 907 was a lower bound on my upper bound 😂 I stopped counting because my number was already much bigger than alex's. 1615 seems reasonable, but I'll finish counting once I suspect I have accounted for all the relations.
@rogers @johncarlosbaez @alexthecamel FWIW, my current brute-force calculation is down to 284 but still in progress, so might well go lower.
@rogers @johncarlosbaez @alexthecamel
I just realised that *both* @alexthecamel and @sgf have done computations that give 284 elements, so if my own program doesn’t find any more reductions, that will make three votes for 284.
I followed the same broad strategy as @sgf described, but coded it independently, so if the theory is sound the result is probably correct.
@gregeganSF @rogers @alexthecamel @sgf - great! If someone can put a list of the 284 elements somewhere, or their code, I can try to publicize this enough so that someone else picks it up and goes further later.
By the way, I made a mistake: the free idempotent rig on n generators is finite for all n, so sufficiently brave people could someday try n = 4.
The evidence for this:
@rogers @gregeganSF @johncarlosbaez @alexthecamel @sgf Wow, this is quite surprising! The OEIS entry helpfully explains that “A squarefree word may be equivalent to a smaller or larger word as a consequence of the idempotent equation.”, but it doesn't say how. Do you know an example?
@robinhouston @rogers @gregeganSF @johncarlosbaez @sgf
ok pulling the example of square free words of wikipedia I'm guessing something like
(012)1021201(210)->
01(20121021)(20121021)0->
01201210210->
01210210->01210
@gregeganSF @sgf @johncarlosbaez @rogers @alexthecamel Very nice! Thank you
@robinhouston @gregeganSF @sgf @johncarlosbaez @rogers
I'm as surprised as you!
