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)

#algebra

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:

en.wikipedia.org/wiki/Square-f

(3/n, n = 3)

@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
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:

mathstodon.xyz/@rogers@lipn.in

and @gregeganSF is getting 1615:

mathstodon.xyz/@gregeganSF/109

@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:

oeis.org/A005345

@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

Follow

@robinhouston @rogers @gregeganSF @johncarlosbaez @sgf
still not exactly sure how to do this systematically i think i've gotten to "looking at the formula for the number of elements of the monoid i can find this many elements and i think i can prove they're different but i'm not sure why I can reduce everything to them"

@alexthecamel @robinhouston @rogers @gregeganSF @johncarlosbaez Still trying to work out a nice approach to compute all the monoid entries and not miss any equivalences. I'm wondering if I can represent all the equivalence classes as regular expressions, and discover further equivalence classes by finding pairs of REs that accept the same string?

@sgf @alexthecamel @robinhouston @rogers @johncarlosbaez

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):

github.com/nagegerg/Idempotent

@gregeganSF @sgf @alexthecamel @robinhouston @johncarlosbaez
Getting to the point where it would be neat to tie this together into a short paper. I've probably failed to tag someone on this post who might like to be included, let me know if so, and conversely if you do not wish to be included tell me. I won't start on this right away (I'll wait until after the holidays, since I have a job app to complete by Jan 6th); I'll make a git project for it then.

@rogers - I'm not sure what we've done that's paper-worthy. Three of us have shown that there are 284 elements in the free idempotent rig on 2 generators, which is cool, but is it worth a paper? I wrote a blog article about it:

johncarlosbaez.wordpress.com/2

which might be enough. If someone else wants to bump it up to a paper, I'd happily contribute the material in my blog.

Sign in to participate in the conversation
Mastodon

a Schelling point for those who seek one