The palindrome-to-factor complexity ratio conjecture for non-ultimately periodic words

Less than 1 year old · traced to

Let x=(ai)i≥0{\bf x}=(a_i)_{i\geq 0} be an infinite word over a finite alphabet Σ\Sigma. Write ρx(n)\rho_{\bf x}(n) for the number of distinct length-nn factors of x{\bf x}, and let Pal⁡x(n)\operatorname{Pal}_{\bf x}(n) be the number of distinct length-nn palindromes occurring in x{\bf x}. Palindrome-to-factor complexity ratio conjecture. If x{\bf x} is not ultimately periodic, then

lim⁡n→∞Pal⁡x(n)ρx(n)=0.\lim_{n\to\infty}\frac{\operatorname{Pal}_{\bf x}(n)}{\rho_{\bf x}(n)}=0.

The conjecture proposes that, for every non-ultimately periodic infinite word, palindrome complexity is asymptotically negligible compared with factor complexity; the examples discussed include the Thue–Morse word and the binary concatenation word, for which this ratio tends to zero. Its general status is not specified in the source.

References

Primary source

Jeffrey Shallit, “Palindrome complexity versus factor complexity”, arXiv:2606.08127 (2026).

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.