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?

  • $\begingroup$ yes consider $01001000100001....$ (once zero, one, twice zero, one, triple zero...) $\endgroup$
    – Yanko
    Sep 14, 2018 at 16:31
  • $\begingroup$ @Yanko but , isn't 00 a subword? $\endgroup$
    – jack jones
    Sep 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$
    – Yanko
    Sep 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$
    – bof
    Sep 14, 2018 at 17:31
  • 2
    $\begingroup$ But that has $00$. $\endgroup$ Sep 14, 2018 at 17:55

1 Answer 1


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$
    – bof
    Sep 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$
    – rici
    Sep 15, 2018 at 0:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .