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:
@johncarlosbaez @gregeganSF @rogers @sgf
if the elements of the free idempotent rig on n elements work how I *think* they do I suspect you can get an exact formula for the number of elements made up of terms containing all the generators (the equivalent of ab,ba,aba,bab)
@johncarlosbaez @gregeganSF @rogers @sgf
guess is 33538195 for n=3
and \((2*(2^p-1)^2+p^2+1))
where \(p=\prod_{i=1}^n i^{2^{n-i-1}}\) more generally
@johncarlosbaez @gregeganSF @rogers @sgf
F(3) seems probably computable with a lot of work, beyond that I'm not sure
@johncarlosbaez @gregeganSF @rogers @sgf
the trick is if you look at the initial substring until you've seen all n elements
so $t = f(a_1,...,a_{n-1})a_n g(a_1,...,a_n)$ say
and both what $a_n$ is and what $f(a_1,...,a_{n-1})$ is as a term containing (n-1) generators don't change with our rewrite rules (ok, f might change but it'll change to something equivalent)
and you do the same reasoning with terminal substrings
and build things up inductively, and you get the same formula as the OEIS
@johncarlosbaez @gregeganSF @rogers @sgf
why this is all there is to know about a term I'm not sure.
but assuming this is true if we're only looking at elements made up of these terms there's not that much structure, we're stuck with the set of initial and set of final substrings we start with but I suspect we can recombine them more or less how we like.
