Chen–Wen–Wu conjecture on generalized Thue–Morse k-binomial complexity

Let m2m\geqslant 2 and let tm\mathbf{t}_m be the generalized Thue--Morse word over an mm-letter alphabet. For k1k\geqslant 1, write btm(k)(n)\mathsf{b}_{\mathbf{t}_m}^{(k)}(n) for the number of kk-binomial equivalence classes represented by factors of length nn, where two finite words are kk-binomially equivalent when every subword of length at most kk occurs the same number of times in both words.

Chen–Wen–Wu conjecture. For every k3k\geqslant 3, the function btm(k)\mathsf{b}_{\mathbf{t}_m}^{(k)} is ultimately periodic with period mkm^k.

The kk-binomial complexity is known explicitly for the two-letter Thue--Morse word and, for k=2k=2, 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.