Prefix palindromic length of the Thue-Morse word
Prefix palindromic length of the Thue-Morse word
复制标题
Thue-Morse 单词的前缀回文长度
作者：
A. Frid
无限字$u$的前缀回文长度$PPL_u(n)$是可以分解为$u$的长度$n$的前缀的最小回文数。在2013年与Puzynina和Zamboni合著的一篇论文中，我们提出了$PPL_u(n)$对于每个非最终周期的无限单词$u$是无界的猜想。到目前为止，这个猜想只在一些特殊情况下被证明，包括所有避免幂$k$的词。然而，即使在这种情况下，最小数$n$的现有上界使得$PPL_u(n)>K$大于任何常数的$K$次方。即使是像斐波那契数词这样最简单的例子，也不知道$PPL_u(n)$的精确值。
The prefix palindromic length $PPL_u(n)$ of an infinite word $u$ is the minimal number of palindromes to which the prefix of length $n$ of $u$ can be decomposed. In a 2013 paper with Puzynina and Zamboni we stated the conjecture that $PPL_u(n)$ is unbounded for every infinite word $u$ which is not ultimately periodic. Up to now, the conjecture has been proved only for some particular cases, including all words avoiding some power $k$. However, even in that 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 a 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 the sequence $(PPL_t(n))$ is $2$-regular, which raises the question if it is the case for all automatic sequences.