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 Pw(n) be the number of nonempty palindromic prefixes of w[1,n], and let Tw(n) consist of those prefixes w[1,j], 1≤ j≤ n, whose palindromic length equals the maximum attained among the nonempty prefixes of w[1,j]. We prove the finite inequality |Tw(n)|≥ Pw(n) for every n≥1. In particular, if w has infinitely many palindromic prefixes, then liminfn→∞|Tw(n)|/Pw(n)≥1. 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.
Related
- Palindromic Length in Free Groups: Reflections, Noncrossing Matchings, and Catalan Forms
- An improved lower bound for maximal partial Room squares
- Sharp lower bounds for the periodic maximal Schrödinger operator in higher dimensions
- ON THE GENERALIZED RUN LENGTH-DENSITY THEOREM
- Uniform lower bounds for the average length of finite Pierce expansions
BibTeX
@misc{rukavicka2026lower,
title = {{A lower bound on the density of prefixes with maximal palindromic length}},
author = {Josef Rukavicka},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15146},
eprint = {2609.15146},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15146},
}
RIS
TY - UNPB
TI - A lower bound on the density of prefixes with maximal palindromic length
AU - Josef Rukavicka
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15146
UR - https://arxiv.org/abs/2609.15146
AB - 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≤ j≤ n, whose palindromic length equals the maximum attained among the nonempty prefixes of w[1,j]. We prove the finite inequality |T_w(n)|≥ P_w(n) for every n≥1. In particular, if w has infinitely many palindromic prefixes, then liminf_n→∞|T_w(n)|/P_w(n)≥1. 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.
ER -