Words with many palindrome pair factors (Q888638): Difference between revisions

\textit{A. E. Frid} et al. [Adv. Appl. Math. 50, No. 5, 737--748 (2013; Zbl 1285.68133)] came with a conjecture that an infinite word each of whose factors can be expressed as concatenation of a limited number of (not necessarily distinct) palindromes is ultimately periodic. This conjecture inspired the current authors to focus on the simplest case of palindrome products of length two, called palindrome pairs. They investigate infinite words where, for infinitely many \(n\), each factor of length \(n\) is a palindrome pair. They show that every Sturmian word -- an infinite binary word with exactly \(n+1\) distinct factors for each \(n\geq0\) -- has this property. However, they show that other infinite words have this property as well, and the well-known word of Thue-Morse does not have this property. Finally, they provide a characterization of minimal non-palindrome pairs. These are binary words that are not palindrome pairs, but each of their proper factors is a palindrome pair.