The palindrome-to-factor complexity ratio conjecture for non-ultimately periodic words
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.