2018/08/27 by Ambrož, Petr, Pelantová, Edita
#68R15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1808.08879
Frid, Puzynina and Zamboni (2013) defined the palindromic length of a finite word w as the minimal number of palindromes whose concatenation is equal to w. For an infinite word u we study PLu, that is, the function that assigns to each positive integer n, the maximal palindromic length of factors of length n in u. Recently, Frid (2018) proved that \limsupn→∞ PLu(n)=+∞ for any Sturmian word u. We show that there is a constant K>0 such that PLu(n)≤ Kln n for every Sturmian word u, and that for each non-decreasing function f with property limn→∞f(n)=+∞ there is a Sturmian word u such that PLu(n)=O(f(n)).