Palindromic Length of Words with Many Periodic Palindromes

Abstract

The palindromic length $\text{PL}(v)$ of a finite word $v$ is the minimal number of palindromes whose concatenation is equal to $v$. In 2013, Frid, Puzynina, and Zamboni conjectured that: If $w$ is an infinite word and $k$ is an integer such that $\text{PL}(u)\le k$ for every factor $u$ of $w$ then $w$ is ultimately periodic. Suppose that $w$ is an infinite word and $k$ is an integer such $\text{PL}(u)\le k$ for every factor $u$ of $w$. Let $\Omega (w,k)$ be the set of all factors $u$ of $w$ that have more than $\sqrt[k]{k^{-1}|u|}$ palindromic prefixes. We show that $\Omega (w,k)$ is an infinite set and we show that for each positive integer $j$ there are palindromes $a,b$ and a word $u\in \Omega (w,k)$ such that $(ab{)}^j$ is a factor of $u$ and $b$ is nonempty. Note that $(ab{)}^j$ is a periodic word and $(ab{)}^{i}a$ is a palindrome for each $i\le j$. These results justify the following question: What is the palindromic length of a concatenation of a suffix of $b$ and a periodic word $(ab{)}^j$ with "many" periodic palindromes? It is known that $|\text{PL}(uv)-\text{PL}(u)|\le \text{PL}(v)$, where $u$ and $v$ are nonempty words. The main result of our article shows that if $a,b$ are palindromes, $b$ is nonempty, $u$ is a nonempty suffix of $b$, $|ab|$ is the minimal period of $aba$, and $j$ is a positive integer with $j\ge 3\text{PL}(u)$ then $\text{PL}(u(ab{)}^j)-\text{PL}(u)\ge 0$.