5

On Finite free objects I asked examples of finite free objects. I got answer "The free idempotent semigroup satisfies $x^2=x$ for each element $x$. And I confirm it is finite if it is finitely generated." with reference to a paper.

If I understood correctly the concept of free object, then elements of free idempotent semigroup of three generators can be seen as strings like "abaca" with "non-repeating" property: do not count for example "abcbc" because has "bc" repeats. Well, on The longest string of none consecutive repeated pattern it is said that there is infinitely many strings of three letters with that property.

So either at least one of the answers is wrong, or then I have understood this wrong.

If given semigroup is finite, how many elements it has?

Community
  • 1
Jori Mäntysalo
  • 325
  • Non-repeating strings are not necessarily pairwise distinct in this monoid. For example, $abaaba$ can be simplified both to $\emptyset$ and to $aba$. Removing repeated substrings is not a confluent rewriting system. – darij grinberg Jul 23 '15 at 12:52
  • I don't quite undestand... If I have a string like $aba$ and I add a letter, then I either will have new non-reducible string or not. In the example, if I add $a$, then not, if I add $c$ then yes. – Jori Mäntysalo Jul 23 '15 at 13:19
  • Oops, I mistook $x^2 = x$ for $x^2 = 1$ at one point. But I suspect examples like this still exist. – darij grinberg Jul 23 '15 at 13:27

1 Answers1

11

There are indeed infinite square-free words, but it does not prove that two distinct prefixes of an infinite square-free word cannot be equivalent under the congruence generated by the congruence $x = x^2$. Here you just considered the rewriting system $x^2 \to x$ and simply ignored the possibility $x \to x^2$. For instance, you will find in [2] a detailed proof that $bacbcabc \sim bacabc$, although these two words are square-free.

As proved in [1], the number of elements of the free idempotent monoid on $n$ generators is $$ \sum_{k=0}^n \binom{n}{k} \prod_{i=1}^k\ (k-i+1)^{2^i} $$ See [2, Chapter 2] for another proof. For $n = 0, 1, 2, 3, 4$, one gets successively the values $1, 2, 7, 160, 332381$. This is A005345 in the on-line encyclopedia of integer sequences.

[1] Green, J.A., Rees, D.: On semigroups in which $x^r=x$, Math. Proc. Camb. Phil. Soc. 48, 35–40 (1952)

[2] Lothaire, M., Combinatorics on words, Encyclopedia of Mathematics and its Applications 17, (1983), Addison-Wesley Publishing Co., Reading, Mass. New edition (1987), Cambridge University Press, ISBN 978-0-521-59924-5.

J.-E. Pin
  • 40,163
  • So, there must be a sequence of expands and shrinks between $bacbcabc$ and $bacabc$. I didn't invent what it is, but I'll try to code a program to find it. And if it don't work, I'll try to get the paper you refer to. – Jori Mäntysalo Jul 25 '15 at 08:26
  • 3
    You can also play around with these things in GAP as described here – James Mitchell Jul 27 '15 at 14:02
  • @james-mitchell, I got GAP working and it confirms the answer given above. But can it also show the shrink-expand -serie showing the equivalence of "bacbcabc" and "bacabc"? – Jori Mäntysalo Aug 10 '15 at 12:02
  • This came up in discussion recently on Mastodon. Here's a link for the first reference. Could anyone give a more precise reference for the Lothaire textbook? The freely available version has "Sturmian Words" as the second chapter, which aren't relevant in any obvious way. – Morgan Rogers Dec 22 '22 at 08:26
  • 1
    @morgan-rogers Your refer to another Lothaire's book, which is not the one I gave in the references. I can only confirm that the reference I gave is the correct one. Chapter 2 is entitled "Square-free words and idempotent semigroups" and is written by J. Berstel and C. Reutenauer. – J.-E. Pin Dec 24 '22 at 17:19