Do infinite sequences always contain consecutive repeated subsequences?

Question

Suppose we have some finite set $S$. Suppose we generate an infinitely long sequence $s_n$ from the elements of this set. Is there guaranteed to exist a ''phrase'' from the set $S$ that repeats an arbitrary (but finitely many) times?

More explicitly: is $s_n$ guaranteed to contain a subsequence of length $mk$ where some phrase of length $m$ occurs $k$ times in a row, for arbitrary but finite $m$ and $k$?

For example if $S = \{0,1\}$, for $m=2$, $k=3$, can we be sure that any sequence generated contains at least one of:

• (0,1) repeated: $0, 1, 0, 1, 0, 1$
• (1,0) repeated: $1, 0, 1, 0, 1, 0$
• (0,0) repeated: $0, 0, 0, 0, 0, 0$
• (1,1) repeated: $1, 1, 1, 1, 1, 1$

It seems to be correct intuitively but can't find an obvious proof (or disproof).

Answer 1

No. Consider the Thue-Morse sequence, whose $n^{th}$ term is $0$ if $n-1$ has an even number of ones in its binary representation, and is $1$ if there are an odd number of ones. This starts like $$ 0,1,1,0,1,0,0,\boxed{1},1,0,0,1,0,1,1,0,\dots $$ For example, the eighth term (boxed above) is a one because $8-1=7$ in binary is $111$, which has an odd number of ones.

It can be shown that the Thue-Morse sequence has no pattern which repeats itself three times consecutively. Therefore, this is a counter-example for any $k\ge 3$.

Answer 2

Here's the case $m=2$.

Consider the first $8k$ terms of your sequence, divided in $4k$ pairs. At least one of the four pairs $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ must occur at least $k$ times, otherwise you'd have at most $4(k-1)$ pairs. Selecting those $k$ pairs, you have a subsequence of length $2k$ in which one of the four occurs $k$ times.

Generalize to any $m$.

Answer 3

I think we can prove this by common sense and induction.

Take the set $A = \{s_1,......,s_k\}\subset S$ where $s_i$ are the elements of $S$ that occur an infinite number of times in the sequence, $\{a_i\}$.

Claim: $A$ is not empty. Pf: If it were then all elements of $S$ only occur finitely many times and the sequence would hve to be finite.

If $s_i$ occurs infinitely many times then for any $N$ there is an $n> N$ so that the $n$th term of the sequence, $a_n$, is equal to $s_i$.

Let $\{v_i\}$ be any sequence of $A$, repeating or or not.

Claim: There is a subsequence $\{a_{i_m}\} \subset \{a_i\}$ so that $\{a_{i_m}\}=\{v_i\}$.

Pf: As there are infinite number of $v_1 \in \{a_i\}$, ther is an $a_p = v_i$. Label that as $a_{i_1}$ the first term of the subsequence.

As there are infinite number of $v_2 \in \{a_i\}$ there is an $a_q; p > p$ so that $a_q = v_2$. Label that as $a_{i_2}$.

When we have gotten any $v_1, v_2,......., v_j = a_{i_1}, a_{i_2},......, a_{i_j}$ terms of the sequence as a subsequence, we just continue: there are infinitely many terms equal to $v_{j+1}$ so there is an $a_\beta \in \{a_i\}$ where $\beta > i_j$ and $a_\beta = v_{j+1}$. Label that as $a_{i_{j+1}}$ to get the $j+1$st term of the subsequence. By induction we can get the entire subsequence.