Palindromic Prefixes and Episturmian Words

Abstract

Let $w$ be an infinite word on an alphabet $A$. We denote by $(n_i{)}_{i\ge 1}$ the increasing sequence (assumed to be infinite) of all lengths of palindrome prefixes of $w$. In this text, we give an explicit construction of all words $w$ such that $n_{i+1}\le 2n_i+1$ for any $i$, and study these words. Special examples include characteristic Sturmian words, and more generally standard episturmian words. As an application, we study the values taken by the quantity $\mathrm{limsup}{n}_{i+1}/n_i$, and prove that it is minimal (among all non-periodic words) for the Fibonacci word.

27 pages; many minor changes; to appear in J. Comb. Th. Series A