PreprintCC BY 4.0arXiv
On the number of palindromic factors of low complexity words
Abstract
Factor complexity counts the distinct factors of each length in an infinite word, while palindromic complexity counts those invariant under reversal. For recurrent aperiodic words with reversal-closed language, the total number of palindromic factors in two consecutive lengths is at most the one-step growth of factor complexity plus two. We prove that equality is forced whenever the factor complexity at a given length does not exceed three halves of that length plus one. We construct examples showing that the bound is optimal. We also obtain an adaptive local criterion and consequences for reversal-closed quasi-Sturmian words and palindromic defect.
Related
- On the language of palindromic reduced words in a Coxeter group
- Abelian maximal pattern complexity of two-dimensional words
- The Tight Upper Bound on the Number of Distinct Squares in Circular Words
- Abelian maximal pattern complexity and extremal words
- Palindromic real-rooted polynomials and h-vectors of polytopes
BibTeX
@misc{kim2026number,
title = {{On the number of palindromic factors of low complexity words}},
author = {Dong Han Kim and Sanghoon Kwon},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.16596},
eprint = {2609.16596},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.16596},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the number of palindromic factors of low complexity words
AU - Dong Han Kim
AU - Sanghoon Kwon
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.16596
UR - https://arxiv.org/abs/2609.16596
AB - Factor complexity counts the distinct factors of each length in an infinite word, while palindromic complexity counts those invariant under reversal. For recurrent aperiodic words with reversal-closed language, the total number of palindromic factors in two consecutive lengths is at most the one-step growth of factor complexity plus two. We prove that equality is forced whenever the factor complexity at a given length does not exceed three halves of that length plus one. We construct examples showing that the bound is optimal. We also obtain an adaptive local criterion and consequences for reversal-closed quasi-Sturmian words and palindromic defect.
ER -