Free idempotent semigroup with 3 generators

333 Views Asked by At

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?

1

There are 1 best solutions below

5
On BEST ANSWER

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.