Palindromic factorization of rich words

Abstract

A finite word $w$ is called \emph{rich} if it contains $|w|+1$ distinct palindromic factors including the empty word. For every finite rich word $w$ there are distinct nonempty palindromes $w_1,w_2,\dots ,w_p$ such that $w=w_p{w}_{p-1}\cdots w_1$ and $w_i$ is the longest palindromic suffix of $w_p{w}_{p-1}\cdots w_i$, where $1\le i\le p$. This palindromic factorization is called \emph{UPS-factorization}. Let $luf(w)=p$ be \emph{the length of UPS-factorization} of $w$. In 2017, it was proved that there is a constant $c$ such that if $w$ is a finite rich word and $n=|w|$ then $luf(w)\le c\frac{n}{\ln n}$. We improve this result as follows: There are constants $\mu ,\pi$ such that if $w$ is a finite rich word and $n=|w|$ then \[luf(w)\leq μ\frac{n}{e^{π\sqrt{\ln{n}}}}\mbox{.}\] The constants $c,\mu ,\pi$ depend on the size of the alphabet.