1
$\begingroup$

What is an example of an infinite word(superword) w such that if a nonempty word v belongs to L = {1,2,3}*, v^2 isn't a subword of w?

For example if w = 123123123...123 and v = 123, v^2 = 123123 hence it's a subword of w, I can't seem to find a superword that fits the requirement.

$\endgroup$
  • $\begingroup$ I think 123111222333111112222233333... works? No? $\endgroup$ – Pavel Nov 15 '14 at 18:34
  • $\begingroup$ at first we have one 1, one 2, one 3, then three 1's, three 2's and three 3's, then 5 of each, then 7 of each, then 9 of each, etc $\endgroup$ – Pavel Nov 15 '14 at 18:35
  • $\begingroup$ But you have double letters - the word "1" repeats a lot as $1^2$ (same goes for 2 and 3) $\endgroup$ – Shaull Nov 15 '14 at 18:38
  • 1
    $\begingroup$ oh yeah, you're right, hmm, seems impossible $\endgroup$ – Pavel Nov 15 '14 at 18:39
  • $\begingroup$ Related question. $\endgroup$ – Raphael Nov 16 '14 at 13:36
5
$\begingroup$

There is a dedicated page on "square-free words" on wikipedia here, with references. As you can see, there is an exemple of a square-free word on a three lettre alphabet.

$\endgroup$
  • $\begingroup$ For some reason, the French version of this page gives even more examples. $\endgroup$ – J.-E. Pin Nov 16 '14 at 10:26
  • $\begingroup$ Russian version too, and I am Russian $\endgroup$ – Pavel Nov 16 '14 at 12:08

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.