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
@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?
@ppscrv @johncarlosbaez @gregeganSF @rogers @sgf
I've been thinking of this as a "canonical form" of say
$f(a_1,...,a_{n-1})a_na_{n-1}g(a_1,...,a_{n-2},a_n$ or similarly with f and g both missing the same variable
and wondering if when you left-multiply or right multipy this by stuff you still get something of this form
@ppscrv @johncarlosbaez @gregeganSF @rogers @sgf
I guess a useful thing is we now can work out what canonical form a term *should* reduce to
@alexthecamel @johncarlosbaez @gregeganSF @rogers @sgf
But \(g\) can contain \(a_n\), so I suppose we look for the last occurrence of \(a_n\) and get something like \(t=f(a_1,...,a_{n-1})a_nP(a_1,...a_n)a_ng(a_1,...a_{n-1}\) with some condition on \(P\) that means there are finitely many.
@alexthecamel @ppscrv @johncarlosbaez @gregeganSF @rogers FWIW, I've now brute-force generated the 160 elements of the 3 letter free idempotent monoid, and looking at what's come out it would probably have been easier to do by hand - but might be useful for cross-checking someone else's work?
https://github.com/simon-frankau/monoid-gen
(And now I can try to catch up on how taking a more mathematical approach compares!)
@sgf @ppscrv @johncarlosbaez @gregeganSF @rogers
Hmm, if you know the multiplication operation you've got here is associative you've got an idempotent monoid generated by 3 elements, which must be a surjective image of the free such monad, right?
@alexthecamel - yes, you're right (but "monoid", not "monad").
@alexthecamel @ppscrv @gregeganSF @rogers
@sgf wrote: "I've now brute-force generated the 160 elements of the 3 letter free idempotent monoid."
Nice! Maybe we can figure out how people know the free idempotent monoid on \(n\) elements has
\[ \displaystyle{ \sum_{k = 0}^n \binom{n}{k} \prod_{i = 1}^k (k - i + 1)^{2^i} } \]
elements! Understanding this might shed some light on the structure of these monoids.
@johncarlosbaez @alexthecamel @ppscrv @gregeganSF @sgf
Hi all, I've started writing this up, and so I would like to continue the collaboration to "finish off" the work, which in my mind means finding a formula for the number of elements of the free idempotent rig on n elements!
(1/n)
@johncarlosbaez @alexthecamel @ppscrv @gregeganSF @sgf
(If I'm missing anyone that was involved last month, let me know!)
So first, let me review how the formula for the number of elements of the free idempotent *monoid* which John quoted was obtained by Green and Rees.
When we were bounding the number of elements of the free idempotent rig, we tried to obtain *minimal* presentations (in terms of coefficients and degrees of terms). Surprisingly, this is not what Green and Rees do!
(2/n)
@johncarlosbaez @alexthecamel @ppscrv @gregeganSF @sgf
Elements of the free id-monoid have many representatives as words (elements of the free monoid). The idea is to choose representatives which are divided into words containing a smaller number of generators.
The form they find is
\( x \sim (p,a,b,q) \)
where \(x\) is a representing word, \(a,b\) are generators (not necessarily distinct) and \(p,q\) are words respectively containing all of the letters of \(x\) except \(a\) and \(b\).
(3/n)
@alexthecamel @ppscrv @johncarlosbaez @gregeganSF @sgf
@robinhouston
Here is the paper that gets referenced, where the formula for the size of the free idempotent semigroup is given:
https://doi.org/10.1017/S0305004100027341
The strategy for decomposing words seems a lot like @alexthecamel 's, and the formula for the size is a smarter version of my inclusion-exclusion formula where one avoids the need for exclusion!
@rogers @alexthecamel @johncarlosbaez @gregeganSF @sgf @robinhouston Thank you very much for this.
@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):
@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:
https://johncarlosbaez.wordpress.com/2022/12/21/free-idempotent-rigs-and-monoids/
which might be enough. If someone else wants to bump it up to a paper, I'd happily contribute the material in my blog.
@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 @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