Counting triple-free sequences

Question

The Thue-Morse sequence is a triple-free element $(a_i)\in\{0,1\}^\mathbb{N}$ which can be constructed by iterating the transformations $0\to 01$ and $1\to 10$ starting from $0$.

The beginning of the sequence reads $0110100110010110\dots$

I would like a lower bound on the cardinality of the set of consecutive length $n$ subsequences, $\{a_ia_{i+1}\dots a_{i+n-1}|i\in\mathbb{N}\}$.

For instance, does it grow exponentially in $n$?

By Cube-free infinite binary words the number of length $n$ cube-free words in $\{0,1\}^\mathbb{N}$ grows exponentially in $n$, but is this already true for subsequences of the Thue-Morse sequence?

Answer 1

The number of distinct consecutive subwords of length $n$ in the Thue-Morse sequence is actually bounded above by a linear function in $n$.

In fact, there is an explicit formula to count this found independently in these three papers:

S.V. Avgustinovich, The number of different subwords of given length in the Morse–Hedlund sequence, Sibirsk. Zh. Issled. Oper. 1 (1994)

S. Brlek, Enumeration of factors in the Thue–Morse word, Discrete Appl. Math. 24 (1989) 83–96

A. de Luca, S. Varricchio, Some combinatorial properties of the Thue–Morse sequence and a problem in semigroups, Theoret. Comput. Sci. 63 (1989) 333–348.