On a class of Thue-Morse type sequences

Ricardo Astudillo^{1} Department of Mathematics University of Illinois Urbana, IL 61801 USA

                    rastudil@math.uiuc.edu

Abstract

We consider a class of binary sequences that generalize the Thue-Morse sequence. In particular, we investigate the occurrences of palindromes in such sequences. We also introduce the notion of the first difference of a binary sequence and characterize first differences of our class of Thue-Morse type sequences. Finally, we define the concept of a “change sequence” of a given binary sequence, a sequence which encodes the positions at which a binary sequence changes values. We characterize the change sequences corresponding to our class of Thue-Morse type sequences.

1 Introduction

The Thue-Morse sequence

{t(n)}_{n=0}^{∞} = 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, …

is defined by t(n) = 0 if n has an even sum of binary digits, and t(n) = 1 otherwise. This sequence has attracted much attention since its discovery by Axel Thue in the early 1900’s, and is still the focus of much study. The Thue-Morse sequence can be constructed in a surprising variety of ways and has numerous applications in diverse fields such as differential geometry, algebra, number theory, and physics; see, for example, [3].

The Thue-Morse sequence can be generalized as follows: For k ≥ 2, define s_{k}(n) as the sum of digits in the base-k representation of a nonnegative integer n, and let t_{k}(n) = s_{k}(n) mod 2. The sequence {t_{k}(n)}_{n=0}^{∞} is thus a binary sequence, and the special case k = 2 yields the Thue-Morse sequence t_{2}(n) = t(n).

1This work was done while the author was supported by an NSF REU (Research Experience for Undergraduates) program at the University of Illinois in Summer 2001 and Spring 2002, and by the Ronald E.

McNair Scholars Program in Summer 2002. The author would like to thank the referee for a thorough and helpful report.

In a recent paper, Allouche and Shallit [4] investigated palindromes in the sequences {t_{k}(n)}. Here a palindrome is defined in the usual sense: a sequence digits is a palindrome if it reads the same forward and backward. For example, in the Thue-Morse sequence, the first four terms 0,1,1,0 form a palindrome, as do the first 16 terms. Allouche and Shallit proved the following result:

Theorem A (Allouche and Shallit [4]). For all k ≥ 2, the sequence {t_{k}(n)}_{n=0}^{∞} contains palindromes of arbitrary length.

In our main result, Theorem 5.1, we generalize this result to a larger class of binary sequences (which contains the sequences {t_{k}(n)}). These sequences also can be defined as fixed points of a class of mappings on binary words.

In the course of proving this result, we introduce the concept of the first difference of a binary sequence. In Theorem 4.1 we characterize the first differences of our class of Thue-Morse type sequences. The characterization involves another class of maps, so-called Toeplitz maps, which we study in Section 2.

We relate the first difference to another concept, that of a change sequence of a binary sequence. This is a sequence which encodes the positions at which the sequence changes values. In a recent paper, Allouche et al. [1] determined the change sequence of the Thue-Morse sequence and proved the following result:

Theorem B (Allouche et al. [1]). Let S be the set of integers n such that t_{2}(n−1) ≠ t_{2}(n), i.e.,

S = {1, 3, 4, 5, 7, 9, 11, 12, 13, 15, …}.

Then S is the set of integers n such that an even power of 2 exactly divides n.

In Theorem 3.1 we generalize this result to our class of Thue-Morse type sequences.

2 Notation and Preliminaries

We consider the set Σ^{∗} of finite words over the alphabet Σ = {0, 1}. We also consider the set Σ^{∞} of infinite and finite words over Σ. For a finite word w we let |w| denote the length of w, and we set |w| = ∞ if w is an infinite word. We denote the ith letter of w by w(i), i.e., w(i) = t_{i} if w = t_{1}t_{2} … t_{b}, where t_{k} ∈ Σ for all k. Given two words w_{1} and w_{2}, we let w_{1}w_{2} denote the word obtained by the concatenation of w_{2} to the right of w_{1}. The concatenation of an arbitrary finite or infinite sequence of words is denoted analogously. We define the complement of w to be the word obtained by interchanging the letters 0 and 1 in w, or equivalently, by adding 1 modulo 2 to each letter of w. We denote the complement of w by \overline{w}.

We next define two morphisms, ϕ_{w} and ψ_{w}, on Σ^{∞}.

Let w be a word with |w| ≥ 2. We let ϕ_{w} : Σ^{∞} → Σ^{∞} be the morphism defined by

ϕ_{w}(0) = w,
ϕ_{w}(1) = \overline{w}.

It is not hard to see that if |w| ≥ 2 and w(1) = 0, then there exists a unique fixed point beginning with 0 of the morphism ϕ_{w}; i.e., there is a unique infinite word w beginning with 0 such that

w = ϕ_{w}(w).

Furthermore, w can be obtained by iterating ϕ_{w}:

w = ϕ_{w}^{∞}(0) := lim_{n→∞} ϕ_{w}^{n}(0).

For example, if w = 01, then w is the Thue-Morse sequence mentioned in the introduction. The morphisms ϕ_{w} are special cases of so-called symmetric morphisms; see [7].

We also consider a second morphism ψ_{w} : Σ^{∞} → Σ^{∞} defined by

ψ_{w}(a) = wa,

where a ∈ Σ. Such a morphism is a special case of the Toeplitz morphisms (see [2, 5]). It is not hard to see that there is a unique fixed point of ψ_{w} beginning with w(1); i.e., there is a unique infinite word w_{∗} with w_{∗}(1) = w(1) such that

w_{∗} = ψ_{w}(w_{∗}),

and we can obtain w_{∗} by iterating ψ_{w}:

w_{∗} = ψ_{w}^{∞}(w(1)) := lim_{n→∞} ψ_{w}^{n}(w(1)).

The fixed point w_{∗} is of the form

w_{∗} = w w_{∗}(1) w w_{∗}(2) w w_{∗}(3) · · · .

This allows one to construct w_{∗} by starting with a sequence of the form

w w w ⋯

and successively filling in the “holes” with the terms of this sequence.

Allouche et al. [1, pp. 456–458] showed that if w = 101, then w_{∗} encodes the places at which the Thue-Morse sequence changes values, i.e., w_{∗}(n) = 1 if and only if t(n) ≠ t(n − 1).

In Sections 4 and 5 we shall need an operation ⊕ on the set Σ^{∗} that is defined as follows: Let w and v be binary words of the same length b. Then

w_{1} ⊕ w_{2} = (w_{1}(1) + w_{2}(1))(w_{1}(2) + w_{2}(2)) ⋯ (w_{1}(b) + w_{2}(b)),

where addition is taken modulo 2.

To conclude this section, we define a product operation × on Σ^{∗} as follows: For any words w, v ∈ Σ^{∗} with |v| = c, set

w × 0 = w, w × 1 = \overline{w},  (2.1)

and

w × v = (w × v(1))(w × v(2)) ⋯ (w × v(c)).  (2.2)

This operation was introduced by Jacobs in [11] and was generalized by Hoit [9, 10] to words over alphabets {0, 1, …, m}. This product is closely related to the morphisms ϕ_{w} defined above; indeed, it is clear that w × v = ϕ_{w}(v).

3 Change Sequences

Let C be the set of indices n such that t_{2}(n − 1) ≠ t_{2}(n), where

{t_{2}(n)}_{n=0}^{∞} = {0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, …}

is the Thue-Morse sequence. As stated in the Introduction (see Theorem B), the set C is characterized by the property that n ∈ C if and only if an even power of 2 exactly divides n. In this section we generalize this result to the class of all fixed points of the morphisms ϕ_{w}. To this end, we introduce the concept of a change sequence of a word as follows:

Definition 3.1. Let w be a finite or infinite word with |w| ≥ 2. We define the change sequence C_{w} of w as the sequence of n ∈ {1, 2, …, |w| − 1} such that w(n) ≠ w(n + 1).

For example, if w = 0010 and w is the associated infinite word, i.e.,

w = 0010001011010010 ⋯,

then C_{w} = {2, 3} and C_{w} = {2, 3, 6, 7, 8, 10, 11, 12, …}.

In the following theorem we give a general method for determining C_{w} for an arbitrary fixed points w.

Theorem 3.1. Let w be a word with |w| = b ≥ 2 such that w(1) = w(b) = 0, let w = ϕ_{w}^{∞}(0), and let C_{w} be the change sequence of w. Then C_{w} = {n ∈ ℕ : d_{b}(n) ∈ C_{w}}, where d_{b}(n) is the last non-zero digit in the base-b representation of n.

Proof. Let w = t_{1}t_{2} ⋯ t_{b}. Since for 1 ≤ r ≤ b − 1 we have d_{b}(n) = r if and only if n = b^{i}(bk + r) for some i, k ≥ 0, it suffices to show that

C_{w} = {b^{i}(bk + r) : i, k ≥ 0, r ∈ C_{w}}.  (3.1)

To prove this, it suffices to show the following two equivalences:

r ∈ C_{w} ⟺ bk + r ∈ C_{w} (k ≥ 0, 1 ≤ r ≤ b − 1).  (3.2)
m ∈ C_{w} ⟺ bm ∈ C_{w} (m ≥ 1).  (3.3)

To prove (3.2), notice that w = w_{0}w_{1}w_{2}w_{3} … with w_{k} ∈ \{w, \overline{w}\} for all k. Clearly we have C_{w} = C_{w_{k}} for all k. Since the words w_{k} all have length b, for 1 ≤ r ≤ b the (bk + r)th letter in w is equal to the rth letter in w_{k}. Hence, for 1 ≤ r ≤ b − 1 and all k, we have w(bk + r) ≠ w(bk + r + 1) if and only if w_{k}(r) ≠ w_{k}(r + 1); i.e., bk + r ∈ C_{w} if and only if r ∈ C_{w_{k}} = C_{w}. This proves (3.2).

To show that (3.3) holds, fix m ≥ 1 and choose j ≥ 1 such that 1 ≤ m ≤ b^{j}. We set

v = ϕ_{w}^{j}(t_{1}) = t_{1}t_{2} ⋯ t_{b^{j}}

and note that m ∈ C_{w} if and only if m ∈ C_{v}. By definition, m ∈ C_{v} if and only if t_{m} ≠ t_{m+1}, which is equivalent to

ϕ_{w}(t_{m}) = \overline{ϕ_{w}(t_{m+1})}.

Now consider

ϕ_{w}(v) = ϕ_{w}^{j+1}(t_{1})
= ϕ_{w}(t_{1})ϕ_{w}(t_{2}) ⋯ ϕ_{w}(t_{m})ϕ_{w}(t_{m+1}) ⋯ ϕ_{w}(t_{b^{j}})
= ϕ_{w}(t_{1})ϕ_{w}(t_{2}) ⋯ ϕ_{w}(t_{m})\overline{ϕ_{w}(t_{m})} ⋯ ϕ_{w}(t_{b^{j}}).

Since |ϕ_{w}(t_{i})| = b for all i and ϕ_{w}(t_{m}) begins and ends with the same letter, it follows that m ∈ C_{w} is equivalent to bm ∈ C_{ϕ_{w}(v)} ⊂ C_{w}.

Remark. Theorem 3.1 requires that w begins and ends with a 0. However, it is easy to check that for any word w with w(1) = 0, the word v = ϕ_{w}(w) = ϕ_{w}(ϕ_{w}(0)) both begins and ends with a 0. Thus we can find the change sequence of w by applying Theorem 3.1 to the word v and noting that v = lim_{n→∞} ϕ_{v}^{n}(0) = lim_{n→∞} ϕ_{w}^{n}(0) = w.

By the result of Allouche et al. quoted in the Introduction (Theorem B), the change sequence of 01 is given by

C_{01} = {n = 2^{2i}m : i ≥ 0, m odd}.  (3.4)

We now verify this with Theorem 3.1. Since w = 01 ends in a 1, we must apply the theorem to v = ϕ_{01}(01) = 0110. We have |v| = 4 and C_{v} = {1, 3}, and so by Theorem 3.1 it follows that

C_{01} = {n = 4^{i}(4k + r) : i, k ≥ 0, r ∈ {1, 3}}
= {n = 4^{i}m : i ≥ 0, m odd}
= {n = 2^{2i}m : i ≥ 0, m odd},

which proves (3.4).

4 First Differences

In this section we define the concept of the first difference of a word, and we determine the first differences of words ϕ_{w}^{∞}(0) for w(1) = 0. First Differences of words over a general alphabet have been used implicitly in a recent paper of Frid [7, pp. 359–360]. For first differences of infinite integer sequences in a different context, see Chalice [6].

Definition 4.1. We define the first difference of a finite or infinite word w to be the word

Δw = (w_{1}(2) − w_{1}(1))(w_{1}(3) − w_{1}(2)) ⋯,

where subtraction is interpreted modulo 2.

Note that |Δw| = |w| − 1 for w of finite length. The following lemma relates the concept of a first difference to that of the change sequence introduced in Section 3. The proof is trivial.

Lemma 4.1. Let w be a word. Then Δw(i) = 1 if and only if i ∈ C_{w}.

Recall the sum operator ⊕, defined in Section 2 as the term-wise addition of two words modulo 2. The next lemma states the relationship between the first difference of a sum and the sum of the first differences:

Lemma 4.2. Let w_{1} and w_{2} be finite words. Then Δ(w_{1} ⊕ w_{2}) = Δw_{1} ⊕ Δw_{2}.

We now turn to the first differences of fixed points w. Notice, for example, that if w = 011010, then Δw = 10111. Now consider

ϕ_{w}(w) = 011010 100101 100101 011010 100101 011010.

Computing the first difference of ϕ_{w}(w), we obtain

Δ(ϕ_{w}(w)) = 10111 \underline{1} 10111 \underline{0} 10111 \underline{1} 10111 \underline{1} 10111 \underline{1} 10111
= Δw \underline{Δw(1)} Δw \underline{Δw(2)} Δw \underline{Δw(3)} Δw \underline{Δw(4)} Δw \underline{Δw(5)} Δw
= ψ_{Δw}(Δw)Δw,

where ψ_{Δw} is the map introduced in Section 2. It is not hard to see that the latter word ψ_{Δw}(Δw)Δw agrees with the word ψ_{Δw}(ψ_{Δw}(Δw(1))) in all but the rightmost position. Since ϕ_{w}^{∞}(0) = w and ψ_{Δw}^{∞}(Δw(1)) = (Δw)_{∗}, this suggests the following connection between Δw and (Δw)_{∗}:

Theorem 4.1. Let w be a word with |w| = b ≥ 2 and w(1) = w(b) = 0. Then the first difference of the fixed point of the morphism ϕ_{w} is exactly the fixed point of ψ_{Δw}, i.e., Δw = (Δw)_{∗}.

Proof. It is sufficient to show that Δw(i) = 1 if and only if (Δw)_{∗}(i) = 1.

Case 1. i ≢ 0 (mod b). Then we have i = bk + r, where k ≥ 0 and 1 ≤ r ≤ b − 1. By the construction of (Δw)_{∗} we have (Δw)_{∗}(i) = 1 if and only if Δw(r) = 1. By Lemma 4.1 this holds if and only if r ∈ C_{w}. As in the proof of Theorem 3.1, we see that r ∈ C_{w} holds if and only if i = bk + r ∈ C_{w}. Hence, (Δw)_{∗}(i) = 1 holds if and only if i ∈ C_{w}, which by Lemma 4.1 is equivalent to Δw(i) = 1.

Case 2. i ≡ 0 (mod b). Then i = b^{j}m for some j ≥ 0, with m ≢ 0 (mod b). Now as in the proof of Theorem 3.1 we see that b^{j}m ∈ C_{w} (i.e., Δw(b^{j}m) = 1) if and only if m ∈ C_{w}. Since m ≢ 0 (mod b), by Case 1 we have m ∈ C_{w} if and only if (Δw)_{∗}(m) = 1. By the construction of (Δw)_{∗} we see that the latter is equivalent to (Δw)_{∗}(i) = 1.

5 Palindromes

We now turn our attention to palindromes. Recall that the complement \overline{w} is the word obtained by interchanging 0 and 1 in w. If |w| is finite, then we define the reversal w^{R} to be the word w written “backwards”; that is, for |w| = b,

w^{R} = w(b)w(b − 1) ⋯ w(2)w(1).

The complement and reversal operations have the following properties, whose proofs are immediate from the definitions.

Proposition 5.1.

(i) (\overline{w})^{R} = \overline{w^{R}}.

(ii) (w^{R})^{R} = \overline{\overline{w}} = w.

(iii) (Δw)^{R} = Δ(w^{R}) .

(iv) (w_{1}w_{2} ⋯ w_{n})^{R} = w_{n}^{R}w_{n−1}^{R} ⋯ w_{1}^{R}.

Definition 5.1. A palindrome is a word w such that w^{R} = w. A skew-palindrome is a word v such that v^{R} = \overline{v}. If a word is either a palindrome or a skew-palindrome, then it is said to be a quasi-palindrome. We denote the sets of palindromes, skew-palindromes, and quasi-palindromes by P, S, and Q, respectively.

For example, the words 0110110 and 011001 are both quasi-palindromes. Specifically, the word 0110110 is a palindrome and the word 011001 is a skew-palindrome.

Proposition 5.2. Let w and v be words of lengths b and c, respectively. Then:

(i) w ∈ P if and only if w(i) = w(b − i + 1) for 1 ≤ i ≤ b.

(ii) v ∈ S if and only if v(j) ≠ v(c − j + 1) for 1 ≤ j ≤ c.

(iii) v ∈ S implies that |v| is even.

(iv) w ∈ P if and only if w ⊕ w^{R} = 00 ⋯ 0; v ∈ S if and only if w ⊕ w^{R} = 11 ⋯ 1.

(v) P ∩ S = ∅.

Proof. (i) and (ii) follow from Definition 5.1. To prove (iii), observe that if |v| = c were odd, then v(j) = v(c − j + 1) for j = ⌈c/2⌉, which violates (ii). The last two properties follow from (i) and (ii).

Recall that the product of two words w and v is defined by

w × v = ϕ_{w}(v).

Given two sets of words U and V, we let U × V denote the set of all words u × v, with u ∈ U and v ∈ V. We show that quasi-palindromes are closed with respect to this product operation.

Proposition 5.3. Let w and v be finite words. Then w,v ∈ Q if and only if w × v ∈ Q. Moreover, we have the following containment relations:

P × P ⊂ P,  (5.1)
P × S ⊂ S,  (5.2)
S × P ⊂ S,  (5.3)
S × S ⊂ P.  (5.4)

Proof. Suppose first that w,v ∈ P with |w| = b and |v| = c. Then

w × v = ϕ_{w}(v) = w_{1}w_{2} ⋯ w_{c},

with w_{i} = ϕ_{w}(v(i)) for 1 ≤ i ≤ c. Notice for each i that we have w_{i} ∈ \{w, \overline{w}\} ⊂ P. Applying Proposition 5.1 (iv), we obtain

(ϕ_{w}(v)) ⊕ (ϕ_{w}(v))^{R} = w_{1}w_{2} ⋯ w_{c} ⊕ w_{c}^{R}w_{c−1}^{R} ⋯ w_{1}^{R}
= (w_{1} ⊕ w_{c}^{R})(w_{2} ⊕ w_{c−1}^{R}) ⋯ (w_{c} ⊕ w_{1}^{R}).

Since v ∈ P, Proposition 5.2 (i) implies

w_{i} = ϕ_{w}(v(i))
= ϕ_{w}(v(c − i + 1))
= w_{c−i+1}.

Since w_{i} ∈ P, it follows from this and Proposition 5.2 (iv) that

(w_{i} ⊕ w_{c−i+1}^{R}) = (w_{i} ⊕ w_{i}^{R})
= 00 ⋯ 0.

Hence

(ϕ_{w}(v)) ⊕ (ϕ_{w}(v))^{R} = 00 ⋯ 0,

which implies that ϕ_{w}(v) ∈ P. This proves (5.1). The relations (5.2)–(5.4) can be proved by similar arguments. It follows from (10.1)–(10.4) that ϕ_{w}(v) ∈ Q whenever w ∈ Q and v ∈ Q.

Conversely, suppose ϕ_{w}(v) ∈ Q. Then ϕ_{w}(v) is given by

ϕ_{w}(v) = ϕ_{w}(v(1))ϕ_{w}(v(2)) ⋯ ϕ_{w}(v(c)).

By definition ϕ_{w}(v) ∈ Q implies that either

ϕ_{w}(v) = (ϕ_{w}(v))^{R}

or

\overline{ϕ_{w}(v)} = (ϕ_{w}(v))^{R}.

In particular, we have

ϕ_{w}(v(1)) = (ϕ_{w}(v(c)))^{R}

or

\overline{ϕ_{w}(v(1))} = (ϕ_{w}(v(c)))^{R}.

It follows that either w = w^{R} or \overline{w} = w^{R}, and in any case we have w ∈ Q. It remains to be shown that v ∈ Q, and to do this we again distinguish several cases. Suppose first that w ∈ P and ϕ_{w}(v) ∈ S. Now ϕ_{w}(v) is of the form

ϕ_{w}(v) = ϕ_{w}(v(1))ϕ_{w}(v(2)) ⋯ ϕ_{w}(v(c)).

By our assumption that ϕ_{w}(v) ∈ S it follows that

\overline{ϕ_{w}(v(i))} = (ϕ_{w}(v(c − i + 1)))^{R}  (5.5)

for 1 ≤ i ≤ c. If v(i) = 0, then (5.5) and our assumption w ∈ P implies that v(c − i + 1) = 1. Likewise, v(i) = 1 implies that v(c − i + 1) = 0. Hence we have v(i) ≠ v(c − i + 1) for all i, so v ∈ S by Proposition 5.2 (ii). The proofs of the remaining cases are similar.

We now characterize first differences of palindromes.

Lemma 5.1. Given a finite word w ∈ Σ^{∗} with |w| ≥ 2, we have w ∈ Q if and only if Δw ∈ P.

Proof. Applying Proposition 5.2 (iv), it follows that Δw ∈ P is equivalent to

00 ⋯ 0 = Δw ⊕ (Δw)^{R}
= Δw ⊕ Δ(w^{R})  (Prop. 5.1(iii))
= Δ(w ⊕ w^{R})  (Lemma 4.2).

Hence w ⊕ w^{R} is either 00 ⋯ 0 or 11 ⋯ 1, and by Proposition 5.2 (iv) this is equivalent to w ∈ Q.

We now consider palindromes in infinite words of the form

w_{∗} = ψ_{w}^{∞}(w(1))

introduced in Section 2.

Lemma 5.2. Let w be a finite word. If w_{∗} contains arbitrarily long palindromes, then w itself is a palindrome.

Proof. Let v be a subword of w_{∗} that is a palindrome. Then v is of the form

v = x[u_{1}]w[u_{2}]w ⋯ w[u_{n}]y,  (5.6)

where [u_{i}] for 1 ≤ i ≤ n are the letters filling the “holes” arising in the construction of w_{∗}, and x and y are a suffix and prefix of w, respectively. (We allow the possibility that x or y or both are empty.)

Suppose first that |x| = |y|. If we subtract |x| + 1 letters from each side of (5.6), then the remaining word

v_{0} = w[u_{2}]w[u_{3}] ⋯ [u_{n−1}]w  (5.7)

is still a palindrome. Notice that v_{0} both begins and ends with w. Since v_{0} ∈ P, it follows that w = w^{R}, and hence w ∈ P.

Now assume without loss of generality that |x| > |y|. Let |w| = b, and let |x| = b − m for some m with 0 ≤ m < b. Then |y| = b − m − r for some r with 1 ≤ r ≤ b − m (since |x| > |y|). Now let x_{1} be the suffix of x of length |x| − |y| − 1, so that |x_{1}| = r − 1. If we remove |y| + 1 letters from each side of v, then the resulting word

v_{1} = x_{1}[u_{1}]w[u_{2}] ⋯ [u_{n−1}]w  (5.8)

must still be a palindrome. Since x_{1} is a suffix of w, we can write w as

w = aw(b − r + 1)x_{1},  (5.9)

where a is the prefix of w of length b − r, and w(b − r + 1) is the (b − r + 1)st letter of w. Substituting (5.9) into (5.8) we obtain

v_{1} = x_{1}[u_{1}]aw(b − r + 1)x_{1}[u_{2}] ⋯ [u_{n−1}]aw(b − r + 1)x_{1}.  (5.10)

Subtracting r − 1 letters from each side of (5.10), we obtain

v_{2} = [u_{1}]aw(b − r + 1)x_{1}[u_{2}] ⋯ [u_{n−1}]aw(b − r + 1),  (5.11)

which again is a palindrome. Since v_{2} ∈ P, it follows that

[u_{1}]aw(b − r + 1) = ([u_{n−1}]aw(b − r + 1))^{R}
= w(b − r + 1)a^{R}[u_{n−1}].

Hence [u_{1}] = w(b − r + 1) = [u_{n−1}]. Proceeding inductively (by removing at each step b + 1 letters from each side) we see that [u_{1}] = [u_{2}] = ⋯ = [u_{n−1}]. Since, by assumption, w_{∗} contains arbitrarily long palindromes, we can take n in (5.6) arbitrarily large. In particular, the “holes” arising in the construction of w_{∗} must include arbitrarily long strings of consecutive 0’s or consecutive 1’s. This is only possible if w = 00 ⋯ 0 or w = 11 ⋯ 1. Thus w is a palindrome.

Remark. The converse of the lemma is also true (though we will not need this fact here): If w is a palindrome, then w_{∗} contains arbitrarily long palindromes.

We are now ready to state and prove our main result, giving us a necessary and sufficient condition for a fixed point w to contain palindromes of arbitrary length. For similar subject matter, see Hof, Knill, and Simon [8].

Theorem 5.1. Let w be a finite word with |w| = b ≥ 2, and w(1) = 0. Then w contains arbitrarily long palindromes if and only if w is a quasi-palindrome.

Proof. Suppose first that w ∈ Q. Then by Proposition 5.3 we have ϕ_{w}(w) ∈ P, and hence ϕ_{w}^{2n+1}(w) ∈ P for all n. Thus ϕ_{w}^{∞}(w) = w contains arbitrarily long palindromes.

Conversely, if w contains arbitrarily long palindromes, then by Lemma 5.1 its first difference Δw also contains arbitrarily long palindromes. If w(b) = 0, then we can apply Theorem 4.1 to conclude that (Δw)_{∗} contains arbitrarily long palindromes. By Lemma 5.2 it follows that Δw ∈ P, which by Lemma 5.1 implies that w ∈ Q. If w(b) = 1, then we cannot apply Theorem 4.1 directly to w. However, we may apply the theorem to the word u = ϕ_{w}(w) to obtain Δw = Δu = (Δu)_{∗}. It follows that (Δu)_{∗} contains arbitrarily long palindromes. As before, this implies that ϕ_{w}(w) = u ∈ Q. By Proposition 5.3 it follows that w ∈ Q.

References

[1] Jean-Paul Allouche, André Arnold, Jean Berstel, Srečko Brlek, Simon Plouffe, and Bruce E. Sagan, A relative of the Thue-Morse sequence, Discrete Math. 139 (1995), 455–461.

[2] Jean-Paul Allouche and Roland Bacher, Toeplitz sequences, paperfolding, Towers of Hanoi and progression-free sequences of integers, Enseign. Math. 38 (1992), 315–327.

[3] Jean-Paul Allouche and Jeffrey Shallit, The ubiquitous Prouhet-Thue-Morse sequence, Sequences and Their Applications: Proceedings of SETA ’98, Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, London, 1999, pp. 1–16.

[4] Jean-Paul Allouche and Jeffrey Shallit, Sums of digits, overlaps, and palindromes, Discrete Math. Theor. Comp. Sci. 4 (2000), 1–10 (electronic).

[5] Julien Cassaigne and Juhani Karhumäki, Toeplitz words, generalized periodicity and periodically iterated morphisms, European J. Combin. 18 (1997), 497–510.

[6] D. Chalice, How to differentiate and integrate sequences, Amer. Math. Monthly 108 (2001), 911–921.

[7] Anna E. Frid, Overlap-free symmetric D0L words, Discrete Math. Theor. Comput. Sci. 4 (2001), 357–362.

[8] A. Hof, O. Knill, and B. Simon, Singular continuous spectrum for palindromic Schrödinger operators, Comm. Math. Phys. 174 (1995), 149–159.

[9] A. Hoit, The distribution of generalized sum-of-digits functions, Ph.D. thesis, Univ. of Illinois, Urbana-Champaign, 1999.

[10] A. Hoit, Block products, preprint, 2002.

[11] K. Jacobs, Maschinenerzeugte 0-1-folgen, Selecta Math. 1 (1969), 1–27.

2000 Mathematics Subject Classification: Primary 11B85; Secondary 68R15. Keywords: Thue-Morse, binary sequence, first difference, palindrome, skew-palindrome, quasi-palindrome, change sequence, cross product, block product, Toeplitz morphism.

(Concerned with sequence \underline{A010060}.)

Received September 6 2002; revised versions received April 28 2003; December 2 2003. Published in Journal of Integer Sequences, December 12 2003.

Return to Journal of Integer Sequences home page.