Prefix Palindromic Length of the Thue-Morse Word

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

                 anna.frid@univ-amu.fr

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.

1 Introduction

By the usual definition, a palindrome is a finite word p = p[1] ⋯ p[n] over a finite alphabet such that p[i] = p[n − i + 1] for every i, like level or abba. We consider decompositions, or factorizations, of a finite word into a concatenation of palindromes: for example, acbcadd = (a)(cbc)(a)(dd) and, at the same time, acbcadd = (acbca)(dd). In particular, we are interested in the minimal number of palindromes needed for such a decomposition, which we call a palindromic length of a word. For example, the palindromic length of abbaba is equal to 3, since this word is not a concatenation of two palindromes, but abbaba = (abba)(b)(a) = (a)(bb)(aba).

A decomposition into a minimal possible number of palindromes is called optimal.

In this paper, we are interested in the palindromic length of prefixes of an infinite word u = u[1] ⋯ u[n] ⋯, denoted by PPL_{u}(n). The length of the shortest prefix of u of palindromic length k is denoted by SP_{u}(k) and can be considered as a kind of an inverse function to PPL_{u}(n). Clearly, SP_{u}(k) can be infinite: for example, if u = abababab ⋯, SP_{u}(k) = ∞ for every k ≥ 3.

The following conjecture was first formulated, in slightly different terms, in our 2013 paper with Puzynina and Zamboni [13].

Conjecture 1. For every non ultimately periodic word u, the function PPL_{u}(n) is unbounded, or equivalently, SP_{u}(k) < ∞ for every k ∈ ℕ.

In fact, there were two versions of the conjecture considered in our paper [13], one concerning the prefix palindromic length and the other concerning the palindromic length of any factor of u. However, Saarela [15] later proved the equivalence of these two statements.

In the same initial paper [13], the conjecture was proved for the case when u is p-power-free for some p, as well as for the more general case when a so-called (p, l)-condition holds for some p and l. Due to the above-mentioned result by Saarela, this means that the conjecture is proven for almost all words, since almost all words contain as long p-power-free factors as needed. However, for some cases, the conjecture remains unsolved, and, for example, its proof for all Sturmian words [11] required a special technique.

Most published papers on palindromic length concern algorithmic aspects; in particular, there are several fast effective algorithms for computing PPL_{u}(n) [9, 5, 14].

The original proof of Conjecture 1 for the p-power-free words is not constructive. The upper bound for a length N such that PPL(N) ≥ K for a given K is given as a solution of a transcendental equation and grows with K faster than any exponential function. However, this does not look to be the best possible bound. So, it is reasonable to state the following conjecture:

Conjecture 2. If a word u is p-power free for some p, then

lim sup \frac{PPL_{u}(n)}{ln n} > 0,

or, equivalently, SP_{u}(k) ≤ C^{k} for some C. The constant C can be chosen independently of u as a function of p.

In this paper, we consider in detail the case of the Thue-Morse word \underline{A010060}, a classical example of a word avoiding powers greater than 2 [3]. We give precise formulas for its prefix palindromic length and discuss its properties. This is a simple but necessary step before considering all p-power-free words, or all fixed points of uniform morphisms, or any other family of words containing the Thue-Morse word.

The results of this paper, in less detail, have been announced in the proceedings of DLT 2019 [10], together with some other results on the prefix palindromic length.

Throughout this paper, we use the notation w(i..j] = w[i + 1]..w[j] for a factor of a finite or infinite word w starting at position i + 1 and ending at j.

The following lemma is a particular case of a statement by Saarela [15, L. 6]. We give its proof for the sake of completeness.

Lemma 3. For every word u and for every n ≥ 0, we have

PPL_{u}(n) − 1 ≤ PPL_{u}(n + 1) ≤ PPL_{u}(n) + 1.

Proof. Consider the prefixes v and va of u of length n and n + 1 respectively. Clearly, for any decomposition u = p_{1} ⋯ p_{k} into k palindromes ua = p_{1} ⋯ p_{k}a is a decomposition of ua into k + 1 palindrome. On the other hand, for any palindromic decomposition ua = q_{1} ⋯ q_{k}, we have either q_{k} = a, and then u = q_{1} ⋯ q_{k−1}, or q_{k} = ap_{k}a, for a (possibly empty) palindrome p_{k}, and then u = q_{1} ⋯ q_{k−1}ap_{k} is a decomposition of u into k + 1 palindromes. If initial decompositions were optimal, this gives PPL_{u}(n + 1) ≤ PPL_{u}(n) + 1 and PPL_{u}(n) ≤ PPL_{u}(n + 1) + 1.

So, the first differences of the prefix palindromic length can be equal only to −1, 0, or 1, and the graph never jumps.

In this paper, it is convenient to consider the famous Thue-Morse word \underline{A010060}

t = abbabaabbaababba ⋯

as the fixed point starting with a of the morphism

τ : \begin{cases}a → abba, \\ b → baab. \end{cases}

Both images of letters under this morphism, which is the square of the usual Thue-Morse morphism a → ab, b → ba, are palindromes.

It is thus easy to see that every prefix of the Thue-Morse word of length 4^{k} is a palindrome, so that PPL_{t}(4^{k}) = 1 for all k ≥ 0. The first values of PPL_{t}(n) and of SP_{t}(k) are given below; also see the \underline{A307319} entry of the On-Line Encyclopedia of Integer Sequences (OEIS) [16].

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ PPL_{t}(n) & 1 & 2 & 2 & 1 & 2 & 3 & 3 & 2 & 3 & 4 & 3 & 2 & 3 & 3 & 2 & 1 \end{matrix}

As for the shortest prefix of a given palindromic length, we give its length in decimal and quaternary notation; also see \underline{A320429} in the OEIS [16].

\begin{matrix}k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ SP_{t}(k) & 1 & 2 & 6 & 10 & 26 & 90 & 154 & 410 \\ 4-ary & 1 & 2 & 12 & 22 & 122 & 1122 & 2122 & 12122 \end{matrix}

Now we are going to prove the self-similarity properties which we observe.

2 Recurrence relations

Theorem 4. The following identities hold for all n ≥ 0:

PPL_{t}(4n) = PPL_{t}(n),  (1)
PPL_{t}(4n + 1) = PPL_{t}(n) + 1,  (2)
PPL_{t}(4n + 2) = min(PPL_{t}(n), PPL_{t}(n + 1)) + 2,  (3)
PPL_{t}(4n + 3) = PPL_{t}(n + 1) + 1.  (4)

To prove Theorem 4, we need several observations. First of all, the shortest non-empty palindrome factors in the Thue-Morse word are a, b, aa, bb, aba, bab, abba, baab. All palindromes of length more than 3 are of even length and have aa or bb in the center: if t(i..i + 2k] is a palindrome, then t(i + k − 1, i + k + 1] = aa or bb.

Let us say that an occurrence of a palindrome t(i..j] is of type (i′, j′) if i′ is the residue of i and j′ is the residue of j modulo 4. For example, the palindrome t(5..7] = aa is of type (1, 3), the palindrome t(4, 8] = baab is of type (0, 0), and the palindrome t(7..9] = bb is of type (3, 1).

Proposition 5. Every occurrence of a palindromic factor of length not equal to one or three in the Thue-Morse word is of a type (m, 4 − m) for some m ∈ {0, 1, 2, 3}.

Proof. Every such palindrome in the Thue-Morse word is of even length which we denote by 2k, and every occurrence of it is of the form t(i..i+2k]. Its center t(i+k−1, i+k+1] is equal to aa or bb, and these two words always appear in t at positions of the form t(2l − 1, 2l + 1] for some l ≥ 1. So, i + k − 1 = 2l − 1, meaning that i = 2l − k and i + 2k = 2l + k. So, modulo 4, we have i + (i + 2k) = 4l ≡ 0, that is, i ≡ −(i + 2k).

Note that the palindromes of odd length in the Thue-Morse word are, first, a and b, which can be of type (0, 1), (1, 2), (2, 3) or (3, 0), and second, aba and bab, which can only be of type (2, 1) or (3, 2).

Proposition 6. Let t(i..i+k] for i > 0 be a palindrome of length k > 0 and of type (m, 4−m) for some m ≠ 0. Then t(i − 1..i + k + 1] is also a palindrome, as well as t(i + 1..i + k − 1].

Proof. The type of the palindrome is not (0, 0), meaning that its first and last letters t[i + 1] and t[i + k] are not the first and the last letters of τ-images of letters. Since these first and last letters are equal and their positions in τ-images of letters are symmetric and determine their four-blocks abba or baab, the letters t[i] and t[i + k + 1] are also equal, and thus t(i−1..i+k +1] is a palindrome. As for t(i+1..i+k −1], it is a palindrome since is obtained from the palindrome t(i..i + k] by erasing the first and the last letters.

Let us say that a decomposition of t(0..4n] into palindromes is a 0-decomposition if all palindromes in it are of type (0, 0). The minimal number of palindromes in a 0-decomposition is denoted by PPL_{t}^{0}(4n).

Proposition 7. For every n ≥ 1, we have PPL_{t}(n) = PPL_{t}^{0}(4n) ≥ PPL_{t}(4n).

Proof. It is sufficient to note that τ is a bijection between all palindromic decompositions of t(0..n] and 0-decompositions of t(0..4n].

Proposition 8. If (3) holds for n = N − 1, then

PPL_{t}(4N − 2) > PPL_{t}(4N).  (5)

Proof. The equality (3) means that PPL_{t}(4N − 2) = min(PPL_{t}(N − 1), PPL_{t}(N)) + 2, but since due to Lemma 3 we have PPL_{t}(N) ≤ PPL_{t}(N − 1) + 1, we also have min(PPL_{t}(N − 1), PPL_{t}(N)) + 2 ≥ PPL_{t}(4N) + 1.

Now we can start the main proof of Theorem 4.

The proof is done by induction on n. Clearly, PPL_{t}(0) = 0, PPL_{t}(1) = PPL_{t}(4) = 1, and PPL_{t}(2) = PPL_{t}(3) = 2, the equalities (1)–(4) hold for n = 0, and moreover, (1) is true for n = 1. Now suppose that they all, and, by Proposition 8, the equality (5), hold for all n < N, and (1) holds also for n = N. We fix an N > 0 and prove for it the following sequence of propositions.

Proposition 9. An optimal decomposition into palindromes of the prefix t(0..4N +1] cannot end with a palindrome of length 3.

Proof. Suppose the opposite: some optimal decomposition of t(0..4N + 1] ends with the palindrome t(4N − 2..4N + 1]. This palindrome is preceded by an optimal decomposition of t(0..4N − 2]. So, PPL_{t}(4N + 1) = PPL_{t}(4N − 2) + 1; but by (5) applied to N − 1, which we can use by the induction hypothesis, PPL_{t}(4N − 2) > PPL_{t}(4N). So, PPL_{t}(4N + 1) > PPL_{t}(4N) + 1, contradicting to Lemma 3.

Proposition 10. There exists an optimal decomposition into palindromes of the prefix t(0..4N + 2] that does not end with a palindrome of length 3.

Proof. The opposite would mean that all optimal decompositions of t(0..4N + 2] end with the palindrome t(4N − 1..4N + 2] preceded by an optimal decomposition of t(0..4N − 1]. So, PPL_{t}(4N + 2) = PPL_{t}(4N − 1) + 1; by the induction hypothesis, PPL_{t}(4N − 1) = PPL_{t}(4N) + 1. So, PPL_{t}(4N + 2) = PPL_{t}(4N) + 2, and thus another optimal decomposition of t(0..4N + 2] can be obtained as an optimal decomposition of t(0..4N] followed by two palindromes of length 1. A contradiction.

Proposition 11. For every m ∈ {1, 2, 3}, the equality holds

PPL_{t}(4N + m) = min(PPL_{t}(4N + m − 1), PPL_{t}(4N + m + 1)) + 1.

Proof. Consider an optimal decomposition t(0..4N+m] = p_{1} ⋯ p_{k}, where k = PPL_{t}(4N+m). Denote the ends of palindromes as 0 = e_{0} < e_{1} < ⋯ < e_{k} = 4N + m, so that p_{i} = t(e_{i−1}, e_{i}] for each i. Since m ≠ 0 and due to Proposition 5, there exist some palindromes of length 1 or 3 in this decomposition. Let p_{j} be the last of them.

Suppose first that j = k. Then due to the two previous propositions, p_{k} can be taken of length 1 not 3, so that t(0..4N + m − 1] = p_{1} ⋯ p_{k−1} is decomposable to k − 1 palindromes. Due to Lemma 3, we have PPL_{t}(4N +m−1) = k −1, and thus PPL_{t}(4N +m) = PPL_{t}(4N + m − 1) + 1. Again due to Lemma 3, we have PPL_{t}(4N + m + 1) ≥ PPL_{t}(4N + m) − 1 = PPL_{t}(4N + m − 1), and so the statement holds.

Now suppose that j < k, so that e_{j} ≡ −e_{j+1} ≡ e_{j+2} ≡ ⋯ ≡ (−1)^{k−j}e_{k} (mod 4). Here p_{j} is the last palindrome in an optimal decomposition of p_{1} ⋯ p_{j} and it is of length 1 or 3. But if e_{j} ≡ 1 or 2 (mod 4), p_{j} can be taken of length 1 due to the two previous propositions applied to some smaller length; and if e_{j} ≡ 3 (mod 4), it is of length 1 since the suffix of length 3 of t(0..4n + 3]) is equal to abb or to baa, so, it is not a palindrome. So, anyway, we can take p_{j} of length one: p_{j} = t(e_{j} − 1, e_{j}].

Since e_{j} ≡ ±e_{k} and e_{k} ≡ m ≠ 0 (mod 4), we may apply Proposition 6 and see that p′_{j} = t(e_{j} − 1..e_{j+1} + 1] is a palindrome, as well as p′_{j+1} = t(e_{j+1} + 1..e_{j+2} − 1] and so on up to p′_{k−1} = t(e_{k−1} + (−1)^{k−j}..e_{k} − (−1)^{k−j}]. So, p_{1} ⋯ p_{j−1}p′_{j} ⋯ p′_{k−1} is a decomposition of t(0..4N + m − (−1)^{k−j}] into k − 1 palindromes. So, as above, PPL_{t}(4N + m) = PPL_{t}(4N + m − (−1)^{k−j}) + 1, and since PPL_{t}(4N + m + (−1)^{k−j}) ≥ PPL_{t}(4N + m) − 1 = PPL_{t}(4N + m − (−1)^{k−j}), the proposition holds.

Proposition 12. Every optimal palindromic decomposition of t(0..4N+4] is a 0-decomposition, and thus PPL_{t}(4N + 4) = PPL_{t}(N + 1).

Proof. Suppose the opposite; then the last palindrome in the optimal decomposition that is not of type (0, 0) is of type (m, 0) and thus is of length 1 or 3. Since the proof of Theorem 4 proceeds by induction on N, this proposition is true for all n < N, and thus the palindrome of type (m, 0) is the very last palindrome of the optimal decomposition. Since the suffix of length 3 of t(0..4N + 4] is equal to bba or aab and thus is not a palindrome, the last palindrome of the optimal decomposition is of length 1, meaning that PPL_{t}(4N + 4) = PPL_{t}(4N + 3) + 1. Now let us use Proposition 11 applied to m = 3, 2, 1; every time we get PPL_{t}(4N + m) = PPL_{t}(4N + m − 1) + 1. Using all these equalities together, we get PPL_{t}(4N + 4) = PPL_{t}(4N) + 4, which is impossible since PPL_{t}(4N) = PPL_{t}(N) and PPL_{t}(4N + 4) ≤ PPL_{t}(N + 1) ≤ PPL_{t}(N) + 1. A contradiction.

We have proven (1) for n = N + 1. It remains to prove (2)–(4) for n = N. Indeed, we know that

− 1 ≤ PPL_{t}(4N + 4) − PPL_{t}(4N) = PPL_{t}(N + 1) − PPL_{t}(N) ≤ 1.  (6)

Now to prove (2) suppose by contrary that PPL_{t}(4N + 1) ≤ PPL_{t}(4N) = PPL_{t}(N). Due to Proposition 11, this means that PPL_{t}(4N + 1) = PPL_{t}(4N + 2) + 1, that is, PPL_{t}(4N + 2) < PPL_{t}(4N), and, again by Proposition 11, PPL_{t}(N + 1) = PPL_{t}(4N + 2) − 2. Thus, PPL_{t}(N) − PPL_{t}(N + 1) ≥ 3, a contradiction to (6). So, (2) is proven.

The equality (4) is proven symmetrically. Now (3) follows from both these equalities in combination with Proposition 11, completing the proof of Theorem 4.

3 Corollaries

The first differences (d_{t}(n))_{n=0}^{∞} of the prefix palindromic length are defined by d_{t}(n) = PPL_{t}(n + 1) − PPL_{t}(n); here we set PPL_{t}(0) = 0. Due to Lemma 3, d_{t}(n) ∈ {−1, 0, +1} for every n; so, it is a sequence over a finite alphabet, which we prefer to denote by { , , }. We write these symbols joining the ends of intervals from left to right, so that the sequence (d_{t}(n)) becomes the plot of PPL_{t}(n).

The following corollary of Theorem 4 is more or less straightforward.

Corollary 13. The sequence (d_{t}(n)) is the fixed point of the morphism

δ : \{ \begin{matrix}→ \\ → \\ → \end{matrix}

Proof. Theorem 4 immediately means that PPL_{t}(4n), …, PPL_{t}(4n + 4) are determined by PPL_{t}(n) and PPL_{t}(n + 1), and moreover, d_{t}(4n), …, d_{t}(4n + 3) are determined by d_{t}(n). This means exactly that the sequence d_{t}(n) is a fixed point of a morphism of length 4. The equality (2) means that the first symbol of any morphic image of δ is ; the equality (4) means that the last symbol of any morphic image of δ is ; the two symbols in the middle can be found from (3) and depend on d_{t}(n).

With the previous corollary, we can draw the plot of PPL_{t}(n) as the fixed point of δ.

\begin{matrix}PPL_{t}(n) \\ n \end{matrix} ; 4 ; 16 ; 64

Figure 1: PPL_{t}(n)

The next proposition can be obtained from Theorem 4 by elementary computations. Recall that SP(k) = SP_{t}(k) is the length n of the shortest prefix of t such that its palindromic length PPL_{t}(n) is equal to k.

Proposition 14. We have SP(1) = 1, SP(2) = 2, SP(3) = 6 and for all k > 0,

SP(k + 3) = 16 SP(k) − 6.

Proof. Let us introduce SP_{2}(k) as the minimal number n such that PPL_{t}(n) = PPL_{t}(n+1) = k. By definition, SP_{2}(k) ≥ SP(k). The first values of SP(k) and SP_{2}(k) are given below.

\begin{matrix}k & 1 & 2 & 3 & 4 & 5 \\ SP(k) & 1 & 2 & 6 & 10 & 26 \\ SP_{2}(k) & ∞ & 2 & 6 & 22 & 38 \end{matrix}

From the definition of the morphism δ we immediately see that a new value n = SP(k) can appear either in the middle of the δ-image of d_{t}(n′) = d_{t}(SP_{2}(k − 2)), or in the middle of the δ-image of d_{t}(n′′), where n′′ = SP(k − 1) − 1. The latter case is also the only possible way to get a new value n = SP_{2}(k). So,

SP(k) = min(4 SP_{2}(k − 2) + 2, 4 SP(k − 1) − 2),  (7)
SP_{2}(k) = 4 SP(k − 1) − 2.  (8)

As we see from the table, for 3 ≤ k ≤ 5, we have SP(k − 1) ≤ SP_{2}(k − 1) < SP(k). The first inequality is obvious, but let us prove the second one by induction. Its base is observed for 3 ≤ k ≤ 5, so, consider k ≥ 6 such that for all k′ = k − 3, k − 2, k − 1 we have SP_{2}(k′ − 1) < SP(k′).

In particular, SP_{2}(k −4) < SP(k −3), so due to (7), we have SP(k −2) = 4 SP_{2}(k −4)+2, and so due to (8),

SP_{2}(k − 1) = 16 SP_{2}(k − 4) + 6.  (9)

On the other hand, we have SP_{2}(k−2) < SP(k−1), so, (7) becomes SP(k) = 4 SP_{2}(k−2)+2, and together with (8) this gives

SP(k) = 16 SP(k − 3) − 6.  (10)

Combining (9), (10), the induction base SP_{2}(k − 4) < SP(k − 3) and the fact that all the values are integers, we obtain that SP_{2}(k − 1) < SP(k) for all k ≥ 3. We also see that (10) is true for all k ≥ 4, proving this proposition.

The following corollary of the previous proposition can be proved by straightforward induction.

Corollary 15. In the 4-ary numeration system, we have SP(3k + 2) = ((12)^{k}2)_{4} for all k ≥ 0; SP(3k) = (1(12)^{k−1}2)_{4} for all k ≥ 1; SP(3k + 1) = (2(12)^{k−1}2)_{4} for all k ≥ 1.

Another direct consequence of Proposition 14 is

Corollary 16. We have

lim sup \frac{PPL_{t}(n)}{ln n} = \frac{3}{4 ln 2},

whereas lim inf \frac{PPL_{t}(n)}{ln n} = 0 since PPL_{t}(4^{m}) = 1 for all m.

4 Regularity

The sequence (PPL_{t}(n)) is closely related to the Thue-Morse word, the most classical example of a 2-automatic sequence. In general, a sequence w = (w[n]) is called k-automatic if there exists a finite automaton such that for the input equal to the k-ary representation of n, the output is equal to w[n]. Equivalently, due to a theorem by Cobham [7], a sequence is k-automatic if and only if it is an image under a coding c : Σ → Δ of a fixed point of a k-uniform morphism φ: w = c(w′), where w′ = φ(w′) [1, Ch. 6]. So, the Thue-Morse word is 2-automatic since it is a fixed point of the 2-uniform morphism a → ab, b → ba, and the sequence (d_{t}(n)) is 4-automatic since it is a fixed point of δ. In both cases, the coding can be taken to be trivial: c(x) = x for every letter x. It is also well-known that a sequence is k-automatic if and only if it is k^{m}-automatic for any integer m, so, in particular, being 2and 4-automatic is the same property. So, the Thue-Morse word is also 4-automatic and the sequence (d_{t}(n)) is 2-automatic.

A more general notion of a k-regular sequence was introduced by Allouche and Shallit [2]; also see [1, Ch. 16]. A sequence (a(n)) is called k-regular (on ℤ) if there exists a finite number of sequences {(a_{1}(n)), …, (a_{s}(n))} such that for every integer i ≥ 0 and 0 ≤ b < k^{i} there exist c_{1}, …, c_{s} ∈ ℤ such that for all n ≥ 0 we have

a(k^{i}n + b) = ∑_{1≤j≤s} c_{j}a_{j}(n).

It is also known that a sequence is k-automatic if and only if it is k-regular and takes on finitely many values [1, Thm. 16.1.4]. Moreover, a sequence a = (a(n)) is k-regular if and only if there exist r sequences a_{1} = a, …, a_{r} and a matrix-valued morphism μ such that if

V (n) = (\begin{matrix}a_{1}(n) \\ a_{2}(n) \\ ⋯ \\ a_{r}(n) \end{matrix}) ,

then

V (kn + b) = μ(b)V (n)

for 0 ≤ b < k [1, Thm. 16.1.3]. Many sequences related to k-automatic words are k-regular, as it was shown by Charlier, Rampersad and Shallit [6]. However, it seems that the general approach from the mentioned paper does not directly work for the palindromic length, so, we have to prove the following corollary only for the Thue-Morse word.

Corollary 17. The sequence PPL_{t}(n) is 4-regular.

Proof. Consider the auxiliary sequences (d(n)), which is (d_{t}(n)) interpreted as a sequence over the alphabet {−1, 0, 1}; (e(n)) defined by

e(n) = \begin{cases}0, if d(n) = −1; \\ 1, otherwise, \end{cases}

and (h(n)) defined by

h(n) = \begin{cases}1, if d(n) = 1; \\ 0, otherwise. \end{cases}

Consider the vector

V (n) = (\begin{matrix}P P L_{t}(n) \\ d(n) \\ e(n) \\ h(n) \\ 1 \end{matrix}) .

Then Theorem 4 and Corollary 13 immediately imply that

V (4n + b) = μ(b)V (n)

for every b = 0, …, 3, where

μ(0) = (\begin{matrix}1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}) , μ(1) = (\begin{matrix}1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}) ,

μ(2) = (\begin{matrix}1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}) , μ(3) = (\begin{matrix}1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & −1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}) .

As it is discussed above, these equalities are sufficient to claim that the first sequence in the vector, P P L_{t}(n), is 4-regular.

Remark 18. In fact, every sequence with k-automatic first differences is k-regular, which can be proven with a similar construction, perhaps with more auxiliary sequences like (e(n)) and (h(n)).

5 Conclusion

To my knowledge, the results of this paper are thus far, the only precise formulas for the prefix palindromic length of a non-trivial infinite word not constructed especially for that purpose.

Even for famous and simple examples like Toeplitz words or the Fibonacci word \underline{A003849}, lower bounds for the prefix palindromic length are difficult [12, 10]. The only more or less universal lower bounds for all p-power-free words are those from the first paper on the subject [13], with SP(k) growing faster than any constant to the power k. Later [12], some calculations allowed a reasonable exponential conjecture on the SP(k) of the Fibonacci word, but it is not clear how to prove it. So, the following more particular open questions can be added to general Conjectures 1 and 2.

Problem 19. Find a precise formula for the prefix palindromic length of the period-doubling word \underline{A096268}, or a lower bound for its lim sup.

Problem 20. Find a precise formula for the prefix palindromic length of the Fibonacci word \underline{A003849}, or a lower bound for its lim sup.

Problem 21. Is it true that the function PPL_{u}(n) is k-regular for any k-automatic word u? Fibonacci-regular for the Fibonacci word? For the definition and discussions of Fibonacciregular sequences, see [8] and references therein.

References

[1] J.-P. Allouche and J. Shallit. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003.

[2] J.-P. Allouche and J. Shallit, The ring of k-regular sequences. Theoret. Comput. Sci. 98 (1992), 163–197.

[3] J.-P. Allouche and J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence. In: C. Ding, T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proc. SETA 1998, Springer, 1999, pp. 1–16.

[4] P. Ambrož, O. Kadlec, Z. Masáková, and E. Pelantová, Palindromic length of words and morphisms in class P. Theoret. Comp. Sci. 780 (2019), 74–83.

[5] K. Borozdin, D. Kosolobov, M. Rubinchik, and A. M. Shur, Palindromic length in linear time. In: J. Kärkkäinen, J. Radoszewski, and W. Rytter, eds., Proc. CPM 2017, Dagstuhl Publishing, 2017, pp. 23:1–23:12.

[6] E. Charlier, N. Rampersad, and J. Shallit, Enumeration and decidable properties of automatic sequences, Int. J. Found. Comput. Sci. 23 (2012), 1035–1066.

[7] A. Cobham. Uniform tag sequences. Math. Systems Theory 6 (1972), 164–192.

[8] Chen Fei Du, H. Mousavi, L. Schaeffer, and J. Shallit, Decision Algorithms for Fibonacci-Automatic Words, III: Enumeration and Abelian Properties, Int. J. Found. Comput. Sci. 27 (2016), 943–963.

[9] G. Fici, T. Gagie, J. Kärkkäinen, and D. Kempa, A subquadratic algorithm for minimum palindromic factorization. J. Discr. Alg. 28 (2014), 41–48.

[10] A. E. Frid, First lower bounds on palindromic length, in Developments in Language Theory: Proc. DLT 2019, Lect. Notes in Comp. Sci., Vol. 11647, Springer, 2019, pp. 234– 243.

[11] A. E. Frid, Sturmian numeration systems and decompositions to palindromes. European J. Combin. 71 (2018), 202–212.

[12] A. Frid, Representations of palindromes in the Fibonacci word, in Proc.

    Numeration 2018,https://numeration2018.sciencesconf.org/data/pages/num18_
    abstracts.pdf, pp. 9–12.

[13] A. Frid, S. Puzynina, and L. Zamboni. On palindromic factorization of words. Advances in Appl. Math. 50 (2013), 737–748.

[14] M. Rubinchik and A. M. Shur, EERTREE: An efficient data structure for processing palindromes in strings. European J. Combin. 68 (2018), 249–265.

[15] A. Saarela, Palindromic length in free monoids and free groups, in: Proc. WORDS 2017, Lect. Notes in Comp. Sci., Vol. 10432, Springer 2017, pp. 203–213.

[16] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, https://oeis.

    org.

2010 Mathematics Subject Classification: Primary 68R15. Keywords: Thue-Morse word, palindrome, palindromic length, k-automatic word, k-regular sequence.

(Concerned with sequences \underline{A003849}, \underline{A010060}, \underline{A096268}, \underline{A307319}, and \underline{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.