I am trying to understand one concept. Is it possible to have a square-free(no subwords ss) word in a language of just $\{0,1\}$ of any given length ( $10^{100}$ for instance). I found out a Thue–Morse sequence , but it is still not really the thing. If there is no such word , how to prove it?
11
-
$\begingroup$ yes consider $01001000100001....$ (once zero, one, twice zero, one, triple zero...) $\endgroup$– YankoSep 14, 2018 at 16:31
-
$\begingroup$ @Yanko but , isn't 00 a subword? $\endgroup$– jack jonesSep 14, 2018 at 16:33
-
$\begingroup$ It is, what is your definition for square-free? I understand it as "a word $w$ is square free if there is no sub-word $s$ such that $w=ss$" Is that what you mean? $\endgroup$– YankoSep 14, 2018 at 16:35
-
1$\begingroup$ Is there a square-free word of lenth $4$? If there is no square-free word of length $4$, how can there be a square-free word of length $10^{100}$? $\endgroup$– bofSep 14, 2018 at 17:31
-
2$\begingroup$ But that has $00$. $\endgroup$– Robert IsraelSep 14, 2018 at 17:55
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
2
The longest square-free word for a language with a binary alphabet is of length 3. However, for alphabets of at least three symbols, there are infinitely many square-free words.
It's easy to prove the first assertion simply by enumerating all binary sequences of length four and observing that all of them contain a square. Since every word of length greater than four contains a subword of length 4, it must also contain a square (the one in the subword, at least).
-
$\begingroup$ For an alphabet of $3$ symbols, there are infinitely many square-free words — equivalently, there is an infinitely long square-free word. $\endgroup$– bofSep 14, 2018 at 23:09
-
$\begingroup$ @bof: i feel like the word "equivalently" is doing an awful lot of work there, since once you admit the existence of infinite strings, you may be in a different calculus. But, ok. $\endgroup$– riciSep 15, 2018 at 0:36