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)

Follow

@johncarlosbaez
there are only a few things that distinguish elements
-the number of 1s, as,bs (adjusting for 1+a=1+3a)
- the parity of the number of terms
- whether there is a term with an initial/final a/b
(and also any a/b at all)
only elements these don't distinguish is ab vs 3ab, aba vs 3aba and symmetrically

@alexthecamel @johncarlosbaez Are you saying you get a lower bound of 278 using these invariants?

I've noticed that the requirement of idempotence can be reduced to x+y = x + xy + yx + y where x and y are of the 7 monomials (together with x²=x)

Namely
x+y+z +xy+yx+xz+zx+yz+zy=(x+y+z)² = x+y+z
follows from that rule.

If you can show, that the invariants you are writing down (as functions on the free rig on 2 generators) respect these relations, they descend to the free idempotent rig.

@julianquast @johncarlosbaez
unless I've done something wrong both lower and upper bound

probably the easiest way to prove these invariants is to construct homs to simpler rigs e.g
-to F_2 with f(a)=f(b)=f(1)=1
-setting ab=ba=0
-the rig {0,1,a,b,ab,ba} with a+b=ab+ba=1, a+a=a,b+b=b

@julianquast @johncarlosbaez but this is essentially how I came up with these invariants

@julianquast @johncarlosbaez
[oops: i have discovered a calculation error, my current figure is 305]

Sign in to participate in the conversation
Mastodon

a Schelling point for those who seek one