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.

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

1 Answer 1

Reset to default
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.

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

Your Answer

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

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