Toda string grande o suficiente tem repetições?

Vamos haver algum conjunto finito de caracteres de tamanho fixo. Seja α um fio acima de Σ . Dizemos que um substrato não vazio β de α é uma repetição se β = γ γ para alguma cadeia γ .$\Sigma$$\alpha$$\Sigma$$\beta$$\alpha$$\beta = \gamma \gamma$$\gamma$

Agora, minha pergunta é se o seguinte vale:

Para cada , existe algum n ∈ N, de modo que, para cada string α acima de Σ de comprimento, pelo menos n , α contenha pelo menos uma repetição.$\Sigma$$n \in \mathbb{N}$$\alpha$$\Sigma$$n$$\alpha$

Eu verifiquei isso no alfabeto binário, e isso é bastante fácil para esse caso, mas um alfabeto de tamanho 3 já é um pouco mais difícil de verificar, e eu gostaria de uma prova de gramáticas arbitrariamente grandes.

Se a conjectura acima for verdadeira, eu posso (quase) remover a demanda por inserir cadeias vazias na minha outra pergunta .

Não, infelizmente não. Existem até infinitas palavras livres de quadrados se o seu alfabeto tiver pelo menos três símbolos.

Essa borda aparentemente natural (alfabetos de dois elementos tem apenas finitas palavras sem quadrados) é observada em muitos lugares, por exemplo:

• é co-finito para | Σ | ≤ 2, mas não isento de contexto para Σ > 2 .$\{xyyz \mid x,y,z\in \Sigma^+\}$$|\Sigma|\leq 2$$\Sigma>2$
• $|\Sigma|>3$$|\Sigma|=2$