7
$\begingroup$

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.)

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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