Characterizations of families of morphisms and words via binomial complexities

Two words are $k$-binomially equivalent if each subword of length at most $k$ occurs the same number of times in both words. The $k$-binomial complexity of an infinite word is a counting function that maps $n$ to the number of $k$-binomial equivalence classes represented by its factors of length $n$. Cassaigne et al. [Int. J. Found. Comput. S., 22(4) (2011)] characterized a family of morphisms, which we call Parikh-collinear, as those morphisms that map all words to words with bounded $1$-binomial complexity. Firstly, we extend this characterization: they map words with bounded $k$-binomial complexity to words with bounded $(k+1)$-binomial complexity. As a consequence, fixed points of Parikh-collinear morphisms are shown to have bounded $k$-binomial complexity for all $k$. Secondly, we give a new characterization of Sturmian words with respect to their $k$-binomial complexity. Then we characterize recurrent words having, for some $k$, the same $j$-binomial complexity as the Thue-Morse word for all $j\le k$. Finally, inspired by questions raised by Lejeune, we study the relationships between the $k$- and $(k+1)$-binomial complexities of infinite words; as well as the link with the usual factor complexity.Comment: 35 pages, 2 figures. Short version under a different title: M. Rigo, M. Stipulanti, and M. A. Whiteland. Binomial complexities and Parikh-collinear morphisms. In V. Diekert and M. V. Volkov, editors, DLT 2022, volume 13257 of LNCS, 251-262. Springer, 2022. doi:10.1007/978-3-031-05578-2\_2