Computing the k-binomial complextiy of the Thue-Morse word

Two finite words are k-binomially equivalent whenever they share the same subwords, i.e., subsequences, of length at most k with the same multiplicities. This is a refinement of both abelian equivalence and the Simon congruence. The k-binomial complexity of an infinite word 𝐱 maps the integer n to the number of classes in the quotient, by this k-binomial equivalence relation, of the set of factors of length n occurring in 𝐱. This complexity measure has not been investigated very much. In this paper, we characterize the k-binomial complexity of the Thue–Morse word. The result is striking, compared to more familiar complexity functions. Although the Thue–Morse word is aperiodic, its k-binomial complexity eventually takes only two values. In this paper, we first express the number of occurrences of subwords appearing in iterates of the form 𝛹^ℓ(𝑤) for an arbitrary morphism 𝛹. We also thoroughly describe the factors of the Thue–Morse word by introducing a relevant new equivalence relation.