[Solved]: Does every large enough string have repeats?

Problem Detail: 

Let $\Sigma$ be some finite set of characters of fixed size. Let $\alpha$ be some string over $\Sigma$. We say that a nonempty substring $\beta$ of $\alpha$ is a repeat if $\beta = \gamma \gamma$ for some string $\gamma$.

Now, my question is whether the following holds:

For every $\Sigma$, there exists some $n \in \mathbb{N}$ such that for every string $\alpha$ over $\Sigma$ of length at least $n$, $\alpha$ contains at least one repeat.

I've checked this over the binary alphabet, and this is quite easy for that case, but an alphabet of size 3 is already quite a bit harder to check, amd I'd like a proof for arbitrarily large grammars.

If the above conjecture is true, then I can (almost) remove the demand for inserting empty strings in my other question.

Asked By : Alex ten Brink

Answered By : Raphael

No, unfortunately not. There are even infinite square-free words if your alphabet has at least three symbols.

This apparently natural border (two-element alphabets have only finitely many square-free words) is observed in many places, for instance:

• $\{xyyz \mid x,y,z\in \Sigma^+\}$ is co-finite for $|\Sigma|\leq 2$ but not context-free for $\Sigma>2$.
• The class of languages generated by terminal-free patterns can be learned in the limit if $|\Sigma|>3$ but not so if $|\Sigma|=2$ [Reid2004].

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/757