First lower bounds for palindromic length (Q2327559)

The \textit{prefix palindromic length} of an infinite word \(\mathbf{u}\) is a function PPL that maps \(n\ge 0\) to the minimal number of palindromes required to factorize the prefix of length \(n\) of \(\mathbf{u}\). Optimal decomposition of a prefix into palindromes can be considered as a hard question. In this paper, the prefix palindromic length of the Thue-Morse word is precisely described. The author has obtained recurrence relations expressing \(\operatorname{PPL}(4n+r)\), \(r=0,1,2,3\), in terms of \(\operatorname{PPL}(n)\) and \(\operatorname{PPL}(n+1)\). Consequently this function is \(4\)-regular (in the sense of Allouche and Shallit). Next, the author naturally tries to extend her result about the Thue-Morse word to a larger family of infinite words. A lower bound (in terms of \(\limsup \operatorname{PPL}(n)\)) is discussed for words with some prescribed conditions. For instance, for the period-doubling word, the problem seems to remain out of reach. The paper ends with a list of natural open problems. Note that similar results have been independently obtained by \textit{S. Li} [``Palindromic length complexity and a generalization of Thue-Morse sequences'', Preprint, \url{arXiv:1907.12543}]. For the entire collection see [Zbl 1416.68011].