4

Consider the Thue-Morse sequence on the alphabet $\{0,1\}$ given by $T_0 = 0$ and $T_{n+1} = T_n \bar{T_n}$ where $\bar{T_n}$ is the bitwise negation of $T_n$. Then the Thue-Morse sequence is defined as $$TM:=\lim\limits_{n\to\infty}T_n$$ (this is just one of many equivalent definitions). It is widely known that this sequence is strongly cube-free but is riddled with squares due to the production $T_{n+2} = T_n\bar{T_n}\bar{T_n}T_n$.

My question is: How can we characterize the subsequences of the Thue-Morse sequence? We already know that they must be strongly cube-free.

I recently gave a talk about the Thue-Morse sequence and its many fascinating properties, and one of the people present asked the question: "Do all strongly cube-free sequences appear as a subsequence of the Thue-Morse sequence?", and I could not answer him.

I wrote a small C++ program that checks for reasonably small subsequences, and I noted that in the first $33554432$ ($=2^{25}$) iterations, the following subsequences were missing:

11011
100100
110110

I checked for sequences of length upto and including 5, and left out the subsequences that are strongly cube-free.

This by no means proves that these numbers will not show up at some later stage in TM, but I do not think they will.

Is there any known complete characterization of the binary subsequences that will appear?

Thanks in advance!

Slugger
  • 5,556

1 Answers1

3

Every word of length at least 5 has a unique decomposition into 1-words, either beginning with the last letter of a 1-word or ending with the first letter of a 1-word. Moreover, if we put bars to indicate the separations between the 1-words occurring at positions 2k in the sequence, the sum of each 1-word is 1 exactly.

Examples: $11010$ occurs since it can be decomposed into $1|10|10$, and the sum of each 1-word is 1: $1+0=1+0$.

$01100$ also occurs since it can be decomposed into $01|10|0$.

$11011$ cannot occur, because neither $1|10|11$ nor $11|01|1$ satisfies the second condition. The other two examples also follow.

Note that this condition is only a sufficient condition. More check should be applied to see whether the subsequence occurs.

Hang Wu
  • 1,576