Palindrome complexity versus factor complexity

Summary · qwen2.5:32b

The study establishes a new relationship indicating that for non-ultimately periodic infinite words, the limit of the ratio of palindrome complexity adjusted logarithmically to factor complexity approaches zero as n increases. This finding highlights a fundamental connection between palindromic and general subsequential structures in infinite sequences; notably, the study also confirms the essential optimality of the numerator in this limiting expression.

Excerpt

arXiv:2606.08127v3 Announce Type: replace Abstract: Let ${\bf x} = (a_i)_{i \geq 0}$ be an infinite word over a finite alphabet $\Sigma$. Let $\rho (n)$ be the factor complexity function for $\bf x$ and ${\rm Pal}(n)$ be the palindrome complexity function for $\bf x$. We give a new relationship between these two quantities; namely, if $\bf x$ is not ultimately periodic, then $$ \lim_{n \rightarrow \infty} {{ {\rm Pal} (n) \log ({\rm Pal} (n) + 1)} \over {\rho (n)}} = 0. $$ Furthermore, we prove that the numerator in this result is essentially optimal.