Palindromic length of words and morphisms in class \(\mathcal{P}\) (Q2420618)

The palindromic length of a finite word is the minimal number of concatenated palindromes needed to construct it. The paper contains several upper bounds for the palindromic length of factors of fixed points of morphisms from the class \(\mathcal{P}\), meaning that each letter \(a\) is sent by the morphism to a word of the form \(pq_a\), where \(p\) and \(q_a\) are palindromes, and \(p\) is the same for all letters. In particular, the class of such fixed points contains the Thue-Morse word, as the fixed point of the morphism \(a \mapsto abba, b \mapsto baab\), and the Fibonacci word, the fixed point of \(a \mapsto ab, b \mapsto a\). The main results of the paper are the following. First, for every fixed point of a primitive morphism from the class \(\mathcal{P}\) there exists a constant \(K\), precisely given in the paper, such that the palindromic length of every factor of length \(n\) is bounded by \(K \ln n\). Over the binary alphabet, this statement can be applied to every fixed point of a morphism containing infinitely many palindromes. Second, precise upper bounds, looking very close to the real situation, are given for factors of the Thue-Morse word and the Fibonacci word. The last result of the paper is that the word \(abaabb\cdots a^kb^k \cdots\) is rich in palindromes but its prefixes have with relatively big, growing as \(\sqrt{n}\), palindromic length. The paper ends by some computational data and a list of open problems on the palindromic length and morphisms from the class \(\mathcal{P}\).