7
$\begingroup$

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.

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

1 Answer 1

7
$\begingroup$

$W_n$ is infinite for all $n \geq 3$.

There is an infinite binary word called the Thue–Morse sequence which is cube-free (among other properties). It can be constructed recursively as follows:

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

The Thue–Morse sequence is the natural limit of these finite words.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .