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$
5
  • $\begingroup$ I think 123111222333111112222233333... works? No? $\endgroup$
    – Pavel
    Commented Nov 15, 2014 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
    Commented Nov 15, 2014 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
    Commented Nov 15, 2014 at 18:38
  • 1
    $\begingroup$ oh yeah, you're right, hmm, seems impossible $\endgroup$
    – Pavel
    Commented Nov 15, 2014 at 18:39
  • $\begingroup$ Related question. $\endgroup$
    – Raphael
    Commented Nov 16, 2014 at 13:36

1 Answer 1

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$
2
  • $\begingroup$ For some reason, the French version of this page gives even more examples. $\endgroup$
    – J.-E. Pin
    Commented Nov 16, 2014 at 10:26
  • $\begingroup$ Russian version too, and I am Russian $\endgroup$
    – Pavel
    Commented Nov 16, 2014 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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