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
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)
@johncarlosbaez @alexthecamel @ppscrv @gregeganSF @sgf
Specifically, \(p\) is a maximal prefix of \(x\) with this property and \(q\) is a maximal suffix (\(p\) and \(q\) may overlap). And they show that \(pabq\) represents the same element of the free idempotent monoid.
Crucially, \(pabq \sim p'a'b'q'\) if and only if \(a = a', b=b'\) and \(p,p'\) have the same letters and represent the same element in the free id-monoid on \(n-1\) elements (and similarly for \(q,q'\) ).
(4/n)
@johncarlosbaez @alexthecamel @ppscrv @gregeganSF @sgf
An observation I should have mentioned earlier is that the free id-monoid can be partitioned into subsets of elements containing a given subset of the generators, since this set \(\mathrm{alph}(x) \) is invariant between words representing the same element. If the number of elements on \(n\) generators is \(c_n\), the representation now gives that \(c_n = n^2c_{n-1}^2\)
We can now use induction to turn this relation into the formula.
(5/n)
@johncarlosbaez @alexthecamel @ppscrv @gregeganSF @sgf
Can we mimic this strategy for the id-semirigs? The observation about the alphabet of an element is still valid, at least. My main advance on this so far is as follows. Call the \((p,a,b,q)\) presentation a *Green-Rees form*, or GRF for brevity.
Let \(A\) be the set of generators. I can present an element of the free id-rig as,
\(\sum_{A' \subset A} r_{A'}\) where each \(r_{A'}\) is a sum of words \(x\) with \(\mathrm{alph}(x) = A'\)
(6/n)
@johncarlosbaez @alexthecamel @ppscrv @gregeganSF @sgf
To be continued in a while... I just realised that all of this was posted publicly; subsequent posts will be unlisted.
@johncarlosbaez @alexthecamel @ppscrv @gregeganSF @sgf
My claim is that each \(r_{A'}\) can be written as a sum \(\sum_{a,b \in A'}(P_{a,b},a,b,Q_{a,b}) \)
where \(P_{a,b}\) is a sum of words \(p\) with \(\mathrm{alph}(p) = A' - \{a\}\) and dually for \(Q_{a,b}\).
The key is to observe that if \(x,y\) have the same letters and GRFs \((p,a,b,q),(p',c,d,q')\) then \(xy\) has GRF \((p,a,d,q')\).
(7/n)
@johncarlosbaez @alexthecamel @ppscrv @gregeganSF @sgf
So if \(a=c\) and \(b=d\) we have \(x+y \sim x + xy + yx + y\)
\(\sim (p,a,b,q) + (p,a,b,q') + (p',a,b,q) + (p',a,b,q') \)
\(\sim (p+p',a,b,q+q') \)
where I have extended the convention for GRFs to allow for sums.
Unfortunately, the crucial fact of essential uniqueness of GRFs does not hold for *sums* of these extended GRFs. But this presentation at least gives a bound which I expect will be asymptotically smaller than \(4^{c_n}\).
(8/n)
@johncarlosbaez @alexthecamel @ppscrv @gregeganSF @sgf
(Note that you need to apply my argument above \(k(k-1)/2\) times to combine a sum of \(k\) similar GRFs)
To complete this to an exact count, we need to account for how lower-order terms affect higher order ones, via relations like \(a+b \sim a+ab+ba+b\).
I think that combining the extended GRFs into a list of big matrices and constraining those might be the way to go, but it's not yet clear to me what the constraints will look like.
(9/n)
@johncarlosbaez @alexthecamel @ppscrv @gregeganSF @sgf
Example:
\(1+a+2b+ab = 1 + (1,a,a,1) + (2,b,b,1)+(a,b,a,b)\)
Already this example illustrates that:
- the GRFs for constants are themselves (an exception I hadn't mentioned)
- the extended GRFs for individual terms are not unique up to separate equivalence of the left and right sums, since we could alternatively write \(2b=(1,b,b,2)\).
I'll let you discuss for a while, see if you can spot any systematic improvements!
(10/n) n=10
@johncarlosbaez @alexthecamel @ppscrv @gregeganSF @sgf
I pre-emptively opened a gitlab project for collaborative writing, although I've already done a decent chunk of the work. There's no standard protocol for write-ups of collaborations like this, but I would like everyone who participated in solving John's puzzle to have a chance to have their name on the paper.
Send me a private message with how you would like to be credited (and if you would like to be more involved in the write-up) please!
@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.
@johncarlosbaez @gregeganSF @rogers @sgf
F(3) seems probably computable with a lot of work, beyond that I'm not sure