# For what $n$ is $W_n$ finite?

Suppose, $$W_n$$ is the set of all words formed by letters '$$a$$' and '$$b$$', that do not contain $$n$$ same consecutive nonempty subwords (that means that for any nonempty word $$u$$, the word $$u^n$$ is not a subword of words from $$W_n$$) For example "$$bababab$$" is not in $$W_3$$, as it contains three consecutive "$$ba$$" subwords, but it obviously is in $$W_4$$. For what $$n$$ is $$W_n$$ finite?

It is easy to see, that $$W_n \subset W_{n+1}$$ and thus the sequence of cardinals $$\{|W_n|\}_{n=1}^{\infty}$$ is monotonously non-decreasing. Thus either $$W_n$$ is finite for all $$n$$, or it is infinite for all $$n$$, or there exists $$n_0$$, such that $$W_n$$ is finite for all $$n < n_0$$ and infinite for all $$n \geq n_0$$.

One can also see, that $$W_2 = \{a, b, ab, ba, aba, bab\}$$ is finite. One can prove that just by looking at all 16 words of length 4 and seeing that none of them lies in $$W_2$$.

However, $$W_{665}$$ is already infinite. Suppose $$G$$ is an infinite $$2$$-generated group of exponent $$665$$ (such group exists according to Adyan-Novikov theorem). Then any element of it can be expressed as a multiple product of those two generators (which can be written as a word formed by letters '$$a$$' and '$$b$$' (that denote the first and the second generator respectively). Due to the group having exponent $$665$$, any such word can be "reduced" to a word from $$W_{665}$$. One can see that two elements that can be written as the same word are equal. And in $$G$$ there is infinitely many pairwise not equal elements. Thus $$W_{665}$$ is infinite by pigeonhole principle.

So we can say that there exists such $$n_0$$, that $$W_n$$ is finite for all $$n < n_0$$ and infinite for all $$n \geq n_0$$. And that aforementioned $$n_0$$ satisfies the inequality $$2 < n_0 \leq 665$$. However I failed to determine anything else about that number.

Any help will be appreciated.

• The main subject of the question is symbolic dynamics.
– YCor
Dec 13, 2018 at 22:59

$$W_n$$ is infinite for all $$n \geq 3$$.
• $$w_1 = a$$
• $$w_{n+1} = w_n \overline{w_n}$$ where for word $$w \in \{ a,b \}^*$$ by $$\overline{w}$$ we denote the "Boolean complement" of $$w$$ (e.g., $$\overline{a} = b$$, $$\overline{ab} = ba$$, $$\overline{aabaa} = bbabb$$).