3
$\begingroup$

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?

$\endgroup$

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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