Consider the alphabet $\mathcal{A}=\{0,1\}$ and the substitution $\phi$ given by $ \phi(0)=01$, $\phi(1)=10$. Let $t$ be the point given by $t=\lim_{n\rightarrow\infty}\phi^n(0)$. Then $t$ is the Thue-Morse sequence; its first couple of characters are $0110100110010\ldots$.

We define the complexity of a word $u$ as a map $F_u:\mathbb{N}\rightarrow\mathbb{N}$, such that for all $n\in\mathbb{N}$, $F_u(n)$ is equal to the number of distinct subwords of $u$ of length $n$.

Has anyone calculated the complexity function of the Thue-Morse sequence? I have tried to find some sources, but have not succeeded. Any references are most welcome.


According to the French Wikipedia page on the Prouhet-Thue-Morse sequence, the complexity function $c(n)$ of the Thue-Morse sequence is the sequence A005942 on OEIS. It can be computed as follows. For $n \geqslant 1$, let $k \geqslant 0$ be the integer such that $2^k + 1 \leqslant n \leqslant 2^{k + 1}$ and let $r$ be such that $n = 2^k + r$ with $1\leqslant r\leqslant 2^{k}$. Then $$ c(n)= \begin{cases} 3\cdot 2^{k}+4(r-1)&{\text{if }}1 \leqslant r \leqslant 2^{k-1},\\ 4\cdot 2^{k}+2(r-1)&{\text{if }}2^{k-1}+1\leqslant r \leqslant 2^{k}. \end{cases} $$ Moreover, $c(n) \leqslant \frac{10}{3}n$ for all $n$. Relevant references (from the OEIS):

[1] J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003. See Problem 10, p. 335.

[2] J. Berstel et al., Combinatorics on Words: Christoffel Words and Repetitions in Words, Amer. Math. Soc., 2008. See p. 83.

[3] S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Applied Math. 24 (1989), 83-96.

[4] A. De Luca, S. Varricchio, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups. Theoret. Comput. Sci. 63 (1989), no. 3, 333-348.

  • $\begingroup$ Thank you for both the complexity and the references. Wikipedia was my first point of reference, but it did not occur to me to look in French rather than English. $\endgroup$ – Simon_Peterson Jun 10 '16 at 16:42
  • 1
    $\begingroup$ Someone should translate this part in Wikipedia... $\endgroup$ – J.-E. Pin Jun 10 '16 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.