2024/12/24 by Mehdi Golafshan, Golafshan, M., Michel Rigo +3 · 1 citation
Computer Science · #68R15 #Coding theory and cryptography #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2412.18425
openalex publication_date 2024/12/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Two finite words are k-binomially equivalent if each subword (i.e., subsequence) of length at most k occurs the same number of times in both words. The k-binomial complexity of an infinite word is a function that maps the integer n≥ 0 to the number of k-binomial equivalence classes represented by its factors of length n. The Thue--Morse (TM) word and its generalization to larger alphabets are ubiquitous in mathematics due to their rich combinatorial properties. This work addresses the k-binomial complexities of generalized TM words. Prior research by Lejeune, Leroy, and Rigo determined the k-binomial complexities of the 2-letter TM word. For larger alphabets, work by Lü, Chen, Wen, and Wu determined the 2-binomial complexity for m-letter TM words, for arbitrary m, but the exact behavior for k≥ 3 remained unresolved. They conjectured that the k-binomial complexity function of the m-letter TM word is eventually periodic with period mk. We resolve the conjecture positively by deriving explicit formulae for the k-binomial complexity functions for any generalized TM word. We do this by characterizing k-binomial equivalence among factors of generalized TM words. This comprehensive analysis not only solves the open conjecture, but also develops tools such as abelian Rauzy graphs.