Subword-complexity difference conjecture for the generalized Thue–Morse words

For each integer k1k\geq 1, let xk{\bf x}_k be the infinite word defined as the limit of the locally catenative sequence described above, and let ρxk(n)\rho_{{\bf x}_k}(n) denote its subword complexity. The subword-complexity difference conjecture for xk{\bf x}_k. For all sufficiently large nn, the first difference

ρxk(n+1)ρxk(n)\rho_{{\bf x}_k}(n+1)-\rho_{{\bf x}_k}(n)

takes only the values 4k24k-2 and 4k4k. The cases k=1k=1, k=2k=2, and k=3k=3 are supported by known results, but the assertion for arbitrary kk remains open.

Sources & referencesView supporting material

Primary source

Jeffrey Shallit, “The Narayana Morphism and Related Words”, arXiv:2503.01026 (2025).

Additional references

2 papers in this index state this conjecture (2019–2025). The statement above is taken from the most recent of them; the others are arXiv:1911.01687.

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.