3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – darij grinberg Jul 23 '15 at 12:52
  • $\begingroup$ 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. $\endgroup$ – Jori Mäntysalo Jul 23 '15 at 13:19
  • $\begingroup$ Oops, I mistook $x^2 = x$ for $x^2 = 1$ at one point. But I suspect examples like this still exist. $\endgroup$ – darij grinberg Jul 23 '15 at 13:27
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jori Mäntysalo Jul 25 '15 at 8:26
  • 3
    $\begingroup$ You can also play around with these things in GAP as described here $\endgroup$ – James Mitchell Jul 27 '15 at 14:02
  • $\begingroup$ @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"? $\endgroup$ – Jori Mäntysalo Aug 10 '15 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.