A lower bound on the density of prefixes with maximal palindromic length

Abstract

The palindromic length $PL(u)$ of a nonempty finite word $u$ is the least number of nonempty palindromes whose concatenation is $u$. For an infinite word $w$, let $P_w(n)$ be the number of nonempty palindromic prefixes of $w[1,n]$, and let $T_w(n)$ consist of those prefixes $w[1,j]$, $1\le j\le n$, whose palindromic length equals the maximum attained among the nonempty prefixes of $w[1,j]$. We prove the finite inequality $|T_w(n)|\ge P_w(n)$ for every $n\ge 1$. In particular, if $w$ has infinitely many palindromic prefixes, then \[ \liminf_{n\to\infty}\frac{|T_w(n)|}{P_w(n)}\geq1. \] The coefficient $1$ is optimal, already for a nonconstant periodic word. The proof uses chains of occurrences connected by palindromic factors, together with trimming and reflection arguments that preserve lower bounds on palindromic length.