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
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]
@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
@alexthecamel @rogers @johncarlosbaez Can you share a link to the code?
@highergeometer@mathstodon.xy@rogers@lipn.info @johncarlosbaez
it's a bit code-golfy I'm afraid
https://github.com/agunning/freerig
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 @alexthecamel @sgf
I should mention an inclusion-exclusion lower bound so we can see how realistic going higher might be. Write \(F(n)\) for the size of the free idempotent rig on \(n\) generators. Then just counting the elements which contain smaller numbers of generators, *I think* \(F(n) \geq \sum_{k=1}^n (-1)^{k+1}\binom{n}{n-k}F(n-k) \)
Taking \(F(2) = 284\) this gives \(F(3) \geq 3 \times 284 - 3 \times 13 + 4 = 817,\)
but that's just a first bound.
@johncarlosbaez @gregeganSF @alexthecamel @sgf
(Please beware that I only worked out the combinatorics of this for the first two coefficients, so I might have poorly pattern-matched)
@sgf - cool! Thanks! I'll blog about this.
By the way, I noticed a little typo on your github. You wrote:
As John Carlos Baez points out, x^4 = x^2,
but you meant
As John Carlos Baez points out, x+x+x+x = x+x,
or maybe
As John Carlos Baez points out, 4x = 2x,
@sgf - @gregeganSF says he and @alexthecamel and you got 284 elements, but your github says
"The answer, if I haven't made enough mistakes, is 243."
Did you find 284 or 243?
@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.
@alexthecamel @johncarlosbaez
@gregeganSF
@rogers
@sgf
So \( t = f(a_1,...,a_{n-1})a_n g(a_1,...,a_n)\),
where \( f \) is a square-free term in \( {a_1, ..., a_{n-1}}\) and \(g\) is a square-free term in \( {a_1, ..., a_n}\) that does not start with a power of a terminal string of \( f(a_1, ..., a_{n-1})a_n \) .
Something like that.
Induction is on \(n\), and we know we are finite for \(n = 0, 1\) or \(2\). The induction step gives is finitely many \(f\)-s, so we need to work on g?
@alexthecamel Having now read http://www.math.ucla.edu/~pak/hidden/Courses/Lothaire-Ch2.pdf , I just wanted to say thanks, I think I finally get this!
From here, it should be fairly simple to write code to generate all elements, reduce arbitrary words to canonical form, etc.
@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!
@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):
@robinhouston wrote: "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."
It's explained here:
https://johncarlosbaez.wordpress.com/2022/12/21/free-idempotent-rigs-and-monoids/#comment-179816
@johncarlosbaez Thanks!
@alexthecamel also gave a different example here: https://schelling.pt/@alexthecamel/109551691788943540
@sgf @johncarlosbaez @gregeganSF @alexthecamel @rogers is there a ref for this? I’m wondering how it squares (pun not intended) with the existence of arbitrarily long square-free sequences on 3 letters…?
@sgf @johncarlosbaez @gregeganSF @alexthecamel @rogers - the free commutative monoid on free generators is finite even though there are arbitrarily long square-free words on 3 letters. This is discussed here:
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 32.
and the relevant page was shown to us by @Jochgem.
I discuss this in this blog article and the comments:
https://johncarlosbaez.wordpress.com/2022/12/21/free-idempotent-rigs-and-monoids/#comments
@alexthecamel @johncarlosbaez so far we have only been using two-term relations. Many of the three-or-more term relations are already accounted for that way, but there are enough possibilities that one should probably try to prove that there are no extra reductions?
@rogers @johncarlosbaez
i think >2 term relations don't add any more constraints: eg
x+y+z=x+y+xy+yx+z=x+y+z+xy+yx+xz+zx=x+y+z+xy+yx+xz+zx+zy+yz=(x+y+z)^2
@rogers @johncarlosbaez
I guess I've not accounted for relations of the form
x(y+z)^2=x(y+z)? I don't think I'm missing any which are nontrivial but that is a bit of an oversight
@rogers @johncarlosbaez
ok i've updated my code to just brute force check + and * are well defined, so there's no problems here
if i'm doing the free rig on n variables i'd have to be more subtle I assume.
https://github.com/agunning/freerig
@alexthecamel @johncarlosbaez We can apply that argument inductively! That will be useful if we attempt to compute bigger ones.
@rogers
should be two terms of the form xab+yaba for x,y>0 (depending on parity of x+y)
adding multiples of 1 and a shouldn't change this
@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)