Computing the \(k\)-binomial complexity of the Thue-Morse word (Q5918904)

The \(k\)-binomial complexity of infinite words was defined in [\textit{M. Rigo} and \textit{P. Salimov}, Theor. Comput. Sci. 601, 47--57 (2015; Zbl 1330.68243)] as the number of equivalence classes of factors of a given length, where the equivalence means the same number of occurrences of every (scattered) subword of length \(\leq k\). In particular, the \(1\)-binomial complexity is the abelian complexity, and for \(n \leq k\), the \(k\)-binomial complexity of \(n\) is just the number of different factors of length \(n\). Rigo and Salimov had proved that the \(k\)-binomial complexity of the Thue-Morse word, and of some other fixed points of morphisms, is bounded by a constant depending on \(k\). The main result of this paper is a precise formula for it: if \(b_{\mathbf{t},k}(n)\) is the \(k\)-binomial complexity of the Thue-Morse word \(\mathbf{t}\), then for all \(n\geq 2k\), we have \[b_{\mathbf{t},k}(n) = \begin{cases} 3\cdot 2k- 3, \mbox{if } n\equiv 0 \bmod{2k}\\ 3\cdot 2k - 4, \mbox{otherwise.}\end{cases}\] For \(n<2k\), the \(k\)-binomial complexity is just the number of factors of length \(n\) of the Thue-Morse word, which is well known. In particular, it is equal to \(3\cdot 2k-4 \) for \(n=2^k-1\). The paper also contains a more general result on any non-erasing morphism and its influence on the number of occurrences of subwords (Theorem 24).