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:


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!


1 Answer 1


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.


You must log in to answer this question.

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