Does every sufficiently long string contain many repetitions of a string of bounded length?

72 Views Asked by At

Let $S$ be a finite set and $d > 0$. Does there exist $\ell > 0$ such that the following holds?

Every sufficiently long string with letters in $S$ contains at least $d$ consecutive copies of some string of length at most $\ell$.

For example, when $S = \{0, 1\}$ and $d = 2$, we can take $\ell = 2$: every string of length at least $4$ contains one of $00, 11, 0101, 1010$.

(I wondered about this when dealing with certain nilpotent elements in a certain ring.)

1

There are 1 best solutions below

0
On BEST ANSWER

No, since the Prouhet–Thue–Morse sequence $t$ is an infinite cube-free sequence on a two-letter alphabet.

Thus, for each $N > 0$, the prefix of length $N$ of $t$ contains no factor of the form $uuu$, with $|u| > 0$, and a fortiori no factor of the form $u^d$, with $d \geqslant 3$, of any length.