Prefix Palindromic Length of the Thue-Morse Word
Anna E. Frid
Aix Marseille Univ., CNRS
Centrale Marseille, I2M
The prefix palindromic length PPLu
of an infinite word u
minimal number of concatenated palindromes needed to express the prefix
of length n
In a 2013 paper with Puzynina and Zamboni we stated
the conjecture that PPLu
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
. However, even in that simple case the existing upper bound for the
minimal number n
such that PPLu
is greater than any constant to
the power K
. Precise values of PPLu
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,
(Concerned with sequences
Received August 28 2019;
revised version received November 28 2019.
Published in Journal of Integer Sequences,
November 30 2019.
Journal of Integer Sequences home page