Palindrome complexity versus factor complexity

Abstract

Let $\mathbf{x}=(a_i{)}_{i\ge 0}$ be an infinite word over a finite alphabet $\hat{I}\pounds$. Let $\ddot{I}(n)$ be the factor complexity function for $\mathbf{x}$ and $\mathrm{Pal}(n)$ be the palindrome complexity function for $\mathbf{x}$. We give a new relationship between these two quantities; namely, if $\mathbf{x}$ is not ultimately periodic, then $$\underset{n\to \infty }{\lim }\frac{\mathrm{Pal}(n)\log (\mathrm{Pal}(n)+1)}{\ddot{I}(n)}=0.$$ Furthermore, we prove that the numerator in this result is essentially optimal.