Chen–Wen–Wu conjecture on generalized Thue–Morse k-binomial complexity
Chen–Wen–Wu conjecture on generalized Thue–Morse k-binomial complexity
Let and let be the generalized Thue--Morse word over an -letter alphabet. For , write for the number of -binomial equivalence classes represented by factors of length , where two finite words are -binomially equivalent when every subword of length at most occurs the same number of times in both words.
Chen–Wen–Wu conjecture. For every , the function is ultimately periodic with period .
The -binomial complexity is known explicitly for the two-letter Thue--Morse word and, for , for generalized Thue--Morse words of arbitrary alphabet size. The conjecture proposes the corresponding eventual periodicity for all higher orders; the supplied source does not establish it.
Sources & referencesView supporting material
Primary source
M. Golafshan, M. Rigo and M. Whiteland, “Computing the k-binomial complexity of generalized Thue–Morse words”, arXiv:2412.18425 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.