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

Aix Marseille Univ., CNRS

Centrale Marseille, I2M

Marseille

France

**Abstract:**

The prefix palindromic length PPL_{u}(*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 PPL_{u}(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 PPL_{u}(*n*) >
*K* is greater than any constant to
the power *K*. Precise values of PPL_{u}(*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.

(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