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

Let x=(ai)i0{\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 Palx(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

limnPalx(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.

Sources & referencesView supporting material

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.