# When will a string have a repeating substring?

What's the minimum number M such that any string with M elements taking values from 1 to N will have a substring repeating itself at least 2 times in a row? The case where N=2 is trivial, you have M=4: 1212 for example the substring 12 repeats itself 2 times in a row, or 1111 where the substring 1 reapeats itself 4 times in a row. It's difficult to find the number even for N=3...

• The question is if there's a number of elements such that any string with this number of elements will have a substring repeating itself 2 times in a row – Marcelo Campos Dec 5 '15 at 20:24
• You already showed that $4$ works. I think, I'm really not clear on what the question is. These are binary strings? You say "string where values from $1$ to $N$" . Anyway, if it's binary then you have to have a repeat within any four consecutive entries. – lulu Dec 5 '15 at 20:27
• i think i made the question more clear, sorry for the mess – Marcelo Campos Dec 5 '15 at 20:29
• Oh. There is no length $M$ that works, even for $N=3$. en.wikipedia.org/wiki/Square-free_word – lulu Dec 5 '15 at 20:36
• I think that is $$M=N+1$$ – AsdrubalBeltran Dec 5 '15 at 20:38

Words of the desired type are said to be "square free". As the OP correctly observes, for binary strings there aren't many instances. $0,1,01,10,101,010$ are the only examples. Somewhat surprisingly, however, even for ternary strings there are infinitely long examples. Wikipedia has a good survey here

Perhaps the simplest, and so far as I know the first, example of an infinite square free ternary word was produced by Thue. It begins with the so-called Thue-Morse binary string, obtained by starting with either character and then successively appending the complement of what's come before. Thus:

$$1,\;10,\;1001,\;10010110,\;1001011001101001,\dots$$

Thue's square free example is then derived from this by taking successive differences. Thus:

$$-1,0,1,-1,1,0,-1,\dots$$

References for these and related results can be found in the Wikipedia article linked to earlier. The proof that the difference sequence of the Thue-Morse word is square free is somewhat lengthy, but it isn't difficult. A good reference for that can be found here.