Journal of Integer Sequences, Vol. 22 (2019), Article 19.7.8

Prefix Palindromic Length of the Thue-Morse Word

Anna E. Frid
Aix Marseille Univ., CNRS
Centrale Marseille, I2M


The prefix palindromic length PPLu(n) of an infinite word u is the minimal number of concatenated palindromes needed to express the prefix of length n of u. In a 2013 paper with Puzynina and Zamboni we stated the conjecture that PPLu(n) is unbounded for every infinite word u that is not ultimately periodic. Up to now, the conjecture has been proven for almost all words, including all words avoiding some power p. However, even in that simple case the existing upper bound for the minimal number n such that PPLu(n) > K is greater than any constant to the power K. Precise values of PPLu(n) are not known even for simplest examples like the Fibonacci word.

In this paper, we give the first example of such a precise computation and compute the function of the prefix palindromic length of the Thue-Morse word, a famous test object for all functions on infinite words. It happens that this sequence is 2-regular, which raises the question if this fact can be generalized to all automatic sequences.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A003849 A010060 A096268 A307319 A320429.)

Received August 28 2019; revised version received November 28 2019. Published in Journal of Integer Sequences, November 30 2019.

Return to Journal of Integer Sequences home page