The palindrome-to-factor complexity ratio conjecture for non-ultimately periodic words
Let be an infinite word over a finite alphabet . Write for the number of distinct length- factors of , and let be the number of distinct length- palindromes occurring in . Palindrome-to-factor complexity ratio conjecture. If is not ultimately periodic, then
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
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.