The Analog of Overlap-Freeness for the Period-Doubling Sequence

James D. Currie Department of Mathematics and Statistics The University of Winnipeg Winnipeg, MB R3B 2E9 Canada

                     j.currie@uwinnipeg.ca

Abstract

Good words are defined to be binary words avoiding the factors 11 and 1001, and the patterns 0000 and 00010100. We show that good words bear the same relationship to the period-doubling sequence that overlap-free words bear to the Thue-Morse sequence. We prove an analog of Fife’s theorem for good words, exhibit the lexicographically least and greatest infinite good words, and determine the patterns avoided by the period doubling word.

1 Introduction

Let A be a finite set. A word over alphabet A is a finite or infinite sequence over A. We use lower case letters to denote finite words, writing, for example, word w = w_{1}w_{2} ⋯ w_{n}, where each w_{i} ∈ A. The length of w is denoted by |w| = n. The empty word, of length 0, is denoted by ϵ. A non-empty word is a word of positive length. The concatenation of two words u = u_{1}u_{2} ⋯ u_{n} and v = v_{1}v_{2} ⋯ v_{m} is given by uv = u_{1}u_{2} ⋯ u_{n}v_{1}v_{2} ⋯ v_{m}. If u, v, w, z are words and w = uzv, we say that word u is a prefix of w, word v is a suffix of w, and word z is a factor of w. We say that ⟨u, z, v⟩ is an occurrence of z in w, and that z occurs in w with index |u|. The set of finite words over A is denoted by A^{∗}.

Let A and B be alphabets. A morphism from A^{∗} to B^{∗} is a function respecting concatenation; i.e., f(xy) = f(x)f(y) for all x, y ∈ A^{∗}. Thus f is generated by its values on the elements of A. If f(x) is non-empty whenever x is non-empty, we call f non-erasing. Let p ∈ A^{∗} and w ∈ B^{∗}. We say that w encounters the pattern p if we can write w = uf(p)v for some u, v ∈ B^{∗}, and some non-erasing morphism f. Otherwise, we say that w avoids p. An overlap is a word v such that we can write v = xyxyx for words x and y where x is non-empty. If no factor of w is an overlap, then w is overlap-free. A word is overlap-free if and only if it avoids patterns xxx and xyxyx. If x is non-empty and k is a positive integer, we denote by x^{k} the word consisting of x repeated k times in a row. A fourth power is a word x^{4} where x ≠ ϵ. The reversal of finite word w = w_{1}w_{2} ⋯ w_{n} is the word w_{n}w_{n−1} ⋯ w_{1}. A word over {0, 1} is called a binary word. The complement of a binary word w is obtained by replacing 0’s with 1’s and vice versa.

Example 1. Consider the word u = αββγββγβαα ∈ {α, β, γ}^{∗}. Then u has the factor ββγ. There are two occurrences of ββγ in u, namely ⟨α, ββγ, ββγβαα⟩ and ⟨αββγ, ββγ, βαα⟩, so that ββγ occurs in u with index 1, and with index 4. Factor ββγββγβ of u is an overlap, with x = β, y = βγ. Thus u is not overlap-free.

The word v = 0101010101 = (01)^{5} contains overlaps 01010 and 10101, and fourth powers (01)^{4} and (10)^{4}. The reversal of v is 1010101010, which is also the complement of v.

The word bananas can be written bananas = uf(pear)v, where u = ba, f(p) = f(a) = n, f(e) = a, f(r) = as, v = ϵ. Thus bananas encounters the pattern pear. It also encounters apple, letting u = v = ϵ, f(a) = b, f(p) = an, f(l) = a, f(e) = s. However, apple avoids bananas (since the image of bananas under any non-erasing morphism has length 7 or more, whereas |apple| = 5).

We use bold-face letters for infinite words, writing w = w_{1}w_{2}w_{3} ⋯, where each w_{i} ∈ A. Thus we are concerned with infinite words where the domain is the positive integers, and we refer to them as one-way infinite words (in contrast to two-way infinite words where the domain would be the set of all integers). The set of finite words over A is denoted by A^{∗}, and the set of one-way infinite words is denoted by A^{ω}.

Iteration of a morphism f is denoted by exponentiation:

f^{i}(x) = \{ \begin{matrix}x, & if i = 0; \\ f(f^{i−1}(x)), & if i > 0. \end{matrix}

If f : A^{∗} → A^{∗} is a morphism such that for some a ∈ A, |f(a)| > 1 and the first letter of f(a) is a, then f^{n−1}(a) is a prefix of f^{n}(a) for every positive integer n. We can then define w = lim_{n→∞} f^{n}(a) to be the unique one-way infinite word such that for each n, word f^{n}(a) is a prefix of w; thus w is a fixed point of f.

The famous Thue-Morse sequence t is a fixed point of the binary morphism μ given by μ(0) = 01, μ(1) = 10, namely

t = lim_{n→∞} μ^{n}(0).

It is sequence \underline{A010060} in the On-Line Encyclopedia of Integer Sequences (OEIS) [16].

Thue [18] introduced t and proved that it is overlap-free. The sequence is also nascent in an earlier paper of Thue [17], where it could be obtained by applying Satz 6 to Satz 3. It is also implicit in an early memoir of Prouhet [12] on multigrades.

Theorem 2. Let w be an overlap-free binary word. Then μ(w) is overlap-free.

He also showed that, in the case of two-sided infinite words and circular words, every overlap-free binary word is the image under μ of an overlap-free word [18]. The analysis of words with ‘ends’ is more complicated, but finite overlap-free binary words also arise via iterating μ. (See Restivo and Salemi [14] for example.)

Theorem 3. Let w ∈ {0, 1}^{∗} be a finite overlap-free word. Then we can write w = aμ(u)b, where a, b ∈ {ϵ, 0, 00, 1, 11}, and u is overlap-free. If |w| ≥ 7 this factorization is unique. If w is a one-sided infinite overlap-free word, then we can write w = aμ(u), for some one-sided infinite overlap-free word u where a ∈ {ϵ, 0, 00, 1, 11}.

Restivo and Salemi used their version of Theorem 3 to give a rough enumeration of binary overlap-free words. Kobayashi [10] gave a better enumeration, obtaining a good lower bound by counting finite words which extend to infinite overlap-free words. For this, he used the deep theorem of Fife [7] characterizing the infinite overlap-free words. The problem of enumerating binary overlap-free words was finally completely solved by Jungers, Protasov, and Blondel [9], and by Guglielmi and Protasov [8].

Because of Theorem 3, the word t turns up frequently in the study of overlap-free binary words. An example is the following result of Berstel [1] (later greatly generalized by Allouche et al. [2]):

Theorem 4. The lexicographically greatest one-sided infinite overlap-free binary word starting with 0 is t.

The relationship between t and μ was also key to establishing the following theorem of Shur [15]:

Theorem 5. Suppose t encounters a pattern p ∈ {0, 1}^{∗}. Then either p is a factor of t, or p is one of 00100 and 11011.

Another famous binary sequence is the period-doubling sequence, which is the fixed point

d = 01000101010001000100010101000101 ⋯

of the binary morphism δ where δ(0) = 01, δ(1) = 00. This sequence has been much studied in the context of quasi-crystal spectral theory. (See Damanik [6], for example.) It is sequence \underline{A096268} in the On-Line Encyclopedia of Integer Sequences (OEIS) [16].

Call a binary word w good if it does not contain the factor 11 or 1001, and does not encounter either of the patterns 0000 or 00010100. We will show that d is good. In fact, we show that the period doubling morphism δ has the same relationship to good words that μ has to overlap-free words, namely Theorem 6. Suppose w is good. Then δ(w) is good.

Theorem 7. Let w be a finite good word. Then we can write w = aδ(u)b, where a ∈ {ϵ, 0, 1}, b ∈ {ϵ, 0}, and u is good. If |w| ≥ 4 this factorization is unique. If w is a one-sided infinite good word, then we can write w = aδ(u), for a one-sided infinite good word u where a ∈ {ϵ, 0, 1}.

We build on these theorems to

• Give a version of Fife’s theorem for good words, characterizing infinite good words;

• Exhibit lexicographically extremal one-sided infinite good words;

• Characterize the binary patterns avoided by d.

2 Good words

Unless otherwise specified, our words and morphisms are over the binary alphabet {0, 1}. We record morphisms inline, i.e., g = [g(0), g(1)].

Lemma 8. Let u be a finite binary word. Suppose δ(u) is good. Then u is good.

Proof. If u encounters pattern 0000 or 00010100, so does δ(u). If u has factor 11 or 1001, then δ(u) has factor δ(11) = 0000 or δ(1001) = 00010100, and thus encounters pattern 0000 or 00010100.

Remark 9. Let w = w_{1}w_{2}w_{3} ⋯ w_{2n} with w_{i} ∈ {0, 1}. Word w can be written as w = δ(u) for some u if and only if w_{i} = 0 for each odd index i.

Lemma 10. Let w be a finite binary word with no factor 11, 1001, or 0000. Then we can write w = aδ(u)b where a ∈ {ϵ, 0, 1} and b ∈ {ϵ, 0}. If |w| ≥ 4 this factorization is unique. If w is a one-sided infinite word with no factor 11, 1001, or 0000, then we can write w = aδ(u), some one-sided infinite word u where a ∈ {ϵ, 0, 1}.

Proof. First we demonstrate the existence of the factorization for finite words: If |w|_{1} ≤ 1 then w is a factor of 0001000, and the result is established by a finite check. Suppose |w|_{1} ≥ 2. If 10^{k}1 is a factor of w, the conditions on w force k = 1 or k = 3. By induction, if 1u1 is a factor of w then |1u| is even; therefore, all the 1’s in w have an index in w of the same parity. If the parity of the indices of 1’s is even, let |a| = 0; let |b| be 0 (resp., 1) if |w| is even (resp., odd). If the parity of the indices of 1’s is odd, let |a| = 1; let |b| be 1 (resp., 0) if |w| is even (resp., odd). By Remark 9 we can write a^{−1}wb^{−1} = δ(u) for some u.

We have shown that we can write w = aδ(u)b and a, b ∈ {ϵ, 0, 1}. Suppose that b = 1. Recall that |w|_{1} ≥ 2. The parity of the indices of a and b is different, so we cannot have a = 1. It follows that |δ(u)|_{1} ≥ 1. Then δ(u)1 must have suffix 011, 01001, or 00001, none of which are good. This is a contradiction so in fact b ∈ {ϵ, 0}.

Now we show the uniqueness of the factorization for finite words: Suppose |w| ≥ 4 and w has two factorizations w = a_{1}δ(u_{1})b_{1} = a_{2}δ(u_{2})b_{2}. If |a_{1}| = |a_{2}| we are forced to choose a_{1} = a_{2}, u_{1} = u_{2}, and b_{1} = b_{2}, so the factorizations are identical. Suppose without loss of generality then that |a_{1}| = 0, |a_{2}| = 1. Then by Remark 9, every 1 in a_{1}δ(u_{1})b_{1} has even index, but every 1 in a_{2}δ(u_{2})b_{2} has even index. Since a_{1}δ(u_{1})b_{1} = w = a_{2}δ(u_{2})b_{2}, we conclude that |w|_{1} = 0, so that w has 0000 as a prefix, which is impossible.

Now suppose that w is a one-sided infinite good word. For each non-negative n, let the length n prefix of w be p_{n}. We have proved that finite words can be factored, so write each p_{n} = a_{n}δ(u_{n})b_{n} where a_{n}, b_{n} ∈ {ϵ, 0, 1}. Word p_{4} cannot be 0000, so that |w_{4}|_{1} > 0. By Remark 9, the index of the first 1 in w_{4} determines a_{4} and all subsequent a_{n}, so that a_{n} = a_{4} for n ≥ 4. This implies that δ(u_{n}) is a prefix of δ(u_{n+1}) for n ≥ 4, so that u_{n+4} is a prefix of u_{n+5} for all n. Let u = lim_{n→∞} u_{n+4}. Then

w = lim_{n→∞} w_{n}

= lim_{n→∞} w_{n+4}

= lim_{n→∞} w_{n+4}b_{n+4}^{−1}

= lim_{n→∞} a_{4}δ(u_{n+4})

= a_{4} lim_{n→∞} δ(u_{n+4})

= a_{4}δ( lim_{n→∞} u_{n+4})

= a_{4}δ(u).

Proof of Theorem 7. This is immediate from Lemmas 8 and 10.

Call a non-erasing morphism g even if, for every letter u, |g(u)| is even.

Lemma 11. Let p be a pattern and let w be a binary word. Suppose that g(p) is a factor of δ(w) where g is an even morphism. Then w encounters pattern p.

Proof. Write p = u_{1} ⋯ u_{n} with the u_{i} letters. Write δ(w) = aU_{1} ⋯ U_{n}b, where U_{i} = g(u_{i}) for each i. If |a| is even, w = δ^{−1}(a)δ^{−1}(U_{1} ⋯ U_{n})δ^{−1}(b), and w contains the instance δ^{−1}(g(p)) of p.

If |a| is odd, then 0 is the last letter of a and of each U_{i}. Thus

δ(w) = a0^{−1}0U_{1}0^{−1}0U_{2}0^{−1}0 ⋯ U_{n}0^{−1}0b,

and w contains the instance δ^{−1}(h(p)) of p, where h is the morphism defined on the letters of p by h(u_{i}) = 0g(u_{i})0^{−1}.

Lemma 12. Let w, u, v be binary words and suppose that uvu is a factor of δ(w). If |u|_{1} > 0 then |uv| is even.

Proof. Since uvu has period |uv|, δ(w) has a factor 1z1 where |1z| = |uv|. The Lemma follows by Remark 9.

Proof of Theorem 6. To begin with, we show that δ(w) does not contain 11, 0000, 1001, or 00010100 as a factor. By Remark 9, δ(w) does not have a factor 11 or 1001. If δ(w) has factor 0000, write δ(w) = a0000b for words a and b. If |a| is even, then w has prefix δ^{−1}(a0000), which ends in 11. This is impossible; if |a| is odd, then the last letter of a is 0, so that w has prefix δ^{−1}((a0^{−1})0000), which again ends in 11. Finally, if 00010100 is a factor of δ(w), then w contains factor δ^{−1}(00010100) = 1001, which is impossible. (The index of 00010100 in δ(w) must be odd by Remark 9)

Suppose now that δ(w) encounters pattern p = 0000, so that XXXX is a factor of δ(w) for some non-empty X. Since δ(w) does not have 0000 as a factor, we must have |X|_{1} > 0. Using u = X and v = ϵ in Lemma 12, we conclude that |X| is even. Then Lemma 11 implies that w encounters 0000, which is a contradiction.

Suppose that δ(w) encounters pattern p = 00010100, so that X^{3}Y XY XX is a factor of δ(w) for some non-empty X and Y. Suppose that |X|_{1} > 0. Since XX is a factor of δ(w), letting u = X and v = ϵ in Lemma 12 implies that |X| is even. Again, since XY X is a factor of δ(w), letting u = X and v = Y in Lemma 12 implies that |XY | is even. It follows that |Y | is even. Then Lemma 11 implies that w encounters 00010100, which is a contradiction. We therefore conclude that |X|_{1} = 0, so that X = 0^{n} for some n ≥ 1. Since XX = 0^{2n} is a factor of δ(w), but 0000 is not, we conclude that n = 1 and X = 0. Thus δ(w) contains the factor XXXY XY XX = 000Y 0Y 00.

Since 0000 is not a factor of δ(w), the first letter of Y is 1. If Y = 1, then δ(w) has factor 00010100, which is impossible. Therefore |Y | > 1.

Suppose Y ends in 0. If Y ends in 10, then δ(w) contains factor 1001 (inside Y 0Y), which is impossible. If |Y | ends in 00, then 000Y 0Y 00 ends in Y 00, hence 0000, which is again impossible. Thus Y ends in 1, hence in 01. Write Y = 1Z1 for some non-empty word Z. Word δ(w) has the factor 0001Z101Z100.

If |1Z1| = 3, then δ(w) contains 01Z101Z1 = 01010101, an instance of 0000, already proved impossible. It follows that |1Z1| ≥ 4. If Z begins 01, then Z10 begins either 0101 or 0100. However, if Z10 begins 0101 then, since Z ends in 0, Z101Z10 again contains 01010101; if Z10 begins 0100 then 0001Z10 begins 00010100, which is not a factor of δ(w). We conclude that Z does not begin 01 and therefore begins 00.

If Z10 begins 001 then 1Z10 has the impossible factor 1001. Thus Z10 begins 0001. We now consider suffixes of Z. If Z ends 10, then 01Z ends either 1010 or 0010. However, if 01Z ends 1010 then, since Z begins with 0, 01Z101Z contains 10101010, an instance of 0000, which is impossible; if 01Z ends in 0010 then 101Z100 ends 00010100, which is not a factor of δ(w). We conclude that Z does not end 10 and therefore ends 00. If 01Z ends 0100 then δ(w) contains 01Z1, hence the impossible factor 1001. Thus 01Z ends in 1000. Since Z begins 00, this forces 01Z101Z to contain 00010100, which is impossible.

Corollary 13. The period-doubling word d is good.

Theorem 14. Let w be a one-sided infinite binary word. Then w is good if and only if δ(w) is good.

Proof. If w_{n} is the length n prefix of w then w = lim_{n→∞} w_{n} and δ(w) = lim_{n→∞} δ(w_{n}). By Theorem 6 and Lemma 8, w_{n} is good if and only if δ(w_{n}) is good.

w is good ⟺ each w_{n} is good
⟺ each δ(w_{n}) is good
⟺ lim_{n→∞} δ(w_{n}) = δ( lim_{n→∞} w_{n}) = δ(w) is good.

Remark 15. While the set of binary overlap-free words is closed under complementation and reversal, the same is not true of good words. For example, 00101000 is good, but neither its complement nor its reversal is good.

3 An analog of Fife’s theorem

We characterize the one-sided infinite good words, developing a theory analogous to Fife’s [7] theory for overlap-free binary words; however, we follow Rampersad’s [13] exposition of Fife, with appropriate modifications, rather than Fife’s original paper. Let G be the set of one-sided infinite good words.

Lemma 16. Suppose u is a one-sided infinite good word. Then 1u is good if and only if 01u is good.

Proof. Clearly if 01u is good then 1u is good. Suppose that 1u is good but 01u is not. By Theorem 7, write 1u = 1δ(v) for some v. Since 1u is good, 01u must have a prefix which is either factor 11 or 1001, or a pattern instance g(0000) or g(00010100) where g = [X, Y] is some non-erasing morphism. Clearly neither of 11 and 1001 can be a prefix of 01u, so 01u has a prefix XXXX or XXXY XY XX where X and Y are non-empty.

Suppose 01u has prefix XXXX. Write X = 0X′. Since |XXXX| is even, word 01u = δ(0v) has XXXX0 = 0X′0X′0X′0X′0 as a prefix. But now the good word 1u contains the fourth power X′0X′0X′0X′0, which is a contradiction.

Now suppose that 01u has prefix XXXY XY XX. Write X = 0X′. If X′ = ϵ, then X = 0. However then the length 2 prefix of 01u is XX = 00, which is impossible. Thus X′ ≠ ϵ, forcing 01 to be a prefix of X, so that |X|_{1} > 0. Since 01u = δ(0v), considering the second XX in XXXY XY XX, by Lemma 12 with u = X, v = ϵ we find that |X| is even. Again, XY X is a factor of δ(0v), so applying Lemma 12 with u = X, v = Y shows that |XY | is also even. Since both |X| and |XY | are even, |Y | is even. Since |XXX| is even, XXX0 is a prefix of 01u = δ(0v), so that we can write Y = 0Y′. Since |XXXY XY XX| is even, word 01u = δ(0v) has XXXY XY XX0 = 0X′0X′0X′0Y′0X′0Y′0X′0X′0 as a prefix. But now the good word 1u contains X′0X′0X′0Y′0X′0Y′0X′0X′0 = g′(00010100) where g′ = [X′0, Y′0]. This is a contradiction.

Remark 17. This result uses the fact that u is one-sided infinite. If u = 010101, then 1u is good, but 01u = (01)^{4} is not.

Let G be the set of one-sided infinite good words. For w ∈ {0, 1}^{∗}, let G_{w} = G∩w{0, 1}^{ω}.

Lemma 18. Let w be a one-sided infinite binary word.

(a) δ(w) ∈ G ⟺ w ∈ G;

(b) 1δ(w) ∈ G ⟺ 0w ∈ G;

(c) 0δ(w) ∈ G ⟺ (1w ∈ G) or (w ∈ G_{001}).

Remark 19. The cases in (c) are disjoint, since if 001 is a prefix of w, then 1w has prefix 1001 and is not good.

Proof of (a). This is just Theorem 14.

Proof of (b). If 0w ∈ G, then by Theorem 14, δ(0w) = 01δ(w) ∈ G, so in particular 1δ(w) ∈ G.

In the other direction, suppose 1δ(w) ∈ G. Applying Lemma 16 to prefixes gives 01δ(w) = δ(0w) ∈ G. By Theorem 14, 0w ∈ G.

Proof of (c). If 1w ∈ G, then by Theorem 14 δ(1w) = 00δ(w) ∈ G, so in particular 0δ(w) ∈ G.

Suppose w ∈ G_{001}. By Theorem 14, δ(w) ∈ G. Suppose 0δ(w) ∉ G. It, therefore, has a prefix XXXX or XXXY XY XX where X is non-empty. Since 001 is a prefix of w, p = 0010100 is a prefix of 0δ(w). The prefix XXX of 0δ(w) has period |X|. If |X| < |p|, then |X| is a period of p, which has least period 5. We conclude that |X| ≥ 5. This implies that, |X|_{1} > 0. The second XX in XXX is a factor of δ(w). By Lemma 12 with u = X, and v = ϵ, we conclude that |X| is even. Therefore |X| ≥ 6. Since 0^{−1}X is an odd-length prefix of δ(w), 0 is a suffix of X.

If |X| = 6 then the prefix 0^{−1}XXX of δ(w) ends in 0XX = 0 001010 001010, which has prefix 00010100. This is impossible, since δ(w) ∈ G. If |X| > 6, then p = 0010100 is a prefix of X, and 0 is a suffix of X, so factor XX of δ(w) contains 0 0010100, again an impossibility.

In the other direction, suppose that 0δ(w) ∈ G. Then w ∈ G by Theorem 14, and we show that either 1w ∈ G, or w ∈ 001{0, 1}^{∗}. Suppose that 1w ∉ G and 001 is not a prefix of w. It follows that a prefix of 1w has the form 11, 1001, XXXX, or XXXY XY XX with non-empty X and/or Y.

By Theorem 7, write w = aδ(u) where a ∈ {ϵ, 0, 1}.

If 11 is a prefix of 1w, then a = 1, and 10 is a prefix of w. However, then 0δ(w) has prefix 0δ(10) = 00001, and is not good.

If 1001 is a prefix of 1w, then 001 is a prefix of w, which is a contradiction.

Suppose XXXX is a non-empty prefix of 1w. Then the final XX of XXXX is a factor of δ(u) and |X|_{1} > 0, so by Lemma 12, |X| is even. Since X is a prefix of 1w, the first letter of X is 1. Since XX is a factor of w, and w has no factor 11, the last letter of X is 0. Write X = 1X′0.

Word w has prefix X′01X′01X′01X′0c for some c ∈ {0, 1}. This implies that 0δ(w) has prefix

0δ(X′01X′01X′01X′0c) = 0δ(X′0)δ(1)δ(X′0)δ(1)δ(X′0)δ(1)δ(X′0)δ(c)
= 0δ(X′0)00δ(X′0)00δ(X′0)00δ(X′0)0\overline{c}
= (0δ(X′0)0)^{4}\overline{c},

and 0δ(w) contains a fourth power. This is a contradiction, since 0δ(w) ∈ G.

Suppose XXXY XY XX is a prefix of 1w. This means that XX and XY X are factors of δ(u), and |X|_{1} > 0. We conclude by Lemma 12 that |X| and |Y | are even. The first letter of X is 1. Since XX and Y X are factors of w, and w has no factor 11, the last letter of each of X and Y is 0. Write X = 1X′0 and Y = cY′0 where c ∈ {0, 1}. Since X′01 is an even length prefix of aδ(u), Remark 9 forces a = ϵ.

Then w has prefix X′01X′01X′01Y′01X′01Y′01X′01X′0d for some d ∈ {0, 1}. Therefore 0δ(w) has prefix

0δ(X′01X′01X′0cY′01X′0cY′01X′01X′0d)
= 0X′′0X′′0X′′\overline{c}Y′′0X′′\overline{c}Y′′0X′′0X′′\overline{d}
= h(00010100)\overline{d},

where X′′ = δ(X′)010, Y′′ = δ(Y′)010, and h = [0δ(X′)010, \overline{c}δ(Y′)010]. This is a contradiction, since 0δ(w) ∈ G.

Suppose w ∈ {0, 1}^{∗} has a suffix δ^{n}(01), n ≥ 0, and let n be as large as possible. Write w = yδ^{n}(01). Define mappings α, β and γ on w by

α(w) = wδ^{n}(00) = yδ^{n+1}(01)
β(w) = wδ^{n}(0100) = yδ^{n+1}(001)
γ(w) = wδ^{n}(010100) = yδ^{n+1}(0001).

For example, if w = 0001000101, then y = 00, n = 2, δ^{n}(0) = 0100, δ^{n}(1) = 0101, so that

α(w) = 00 0100 0101 0100 0100
β(w) = 00 0100 0101 0100 0101 0100 0100
γ(w) = 00 0100 0101 0100 0101 0100 0101 0100 0100.

Let f = f_{1}f_{2}f_{3} ⋯, where each f_{i} ∈ B = {α, β, γ}. Suppose w has some suffix δ^{n}(01). Then w is a proper prefix of f_{1}(w), which is a proper prefix of f_{2}(f_{1}(w)), which is a proper prefix of f_{3}(f_{2}(f_{1}(w))), etc. We define the infinite composition x = (⋯ ∘ f_{3} ∘ f_{2} ∘ f_{1})(01) to be the one-sided infinite word

x = lim_{n→∞} f_{n}(f_{n−1}(⋯ f_{2}(f_{1}(w)) ⋯),

which has each f_{n}(f_{n−1}(⋯ f_{2}(f_{1}(w)) ⋯) as a prefix. Following Rampersad, we use the notation x = w • f.

Let u ∈ B^{k}. Then

01 • uf = (01 • u)δ^{k}(01)^{−1}δ^{k}(x).  (1)

Define the sets I and F by

I = (β + γ)(αα)^{∗}α(γ + ββ) ∪ γ(αβ)^{∗}αγ,
F = B^{ω} − B^{∗}IB^{ω}.

Theorem 20. Let x ∈ {0, 1}^{ω}. If x begins with 01, then x is good if and only if x = 01 • f for some f ∈ F.

We follow the notation of Berstel, also used by Rampersad. Here I stands for ‘ideal’, and B^{∗}IB^{ω} is the ideal generated by I, consisting of the forbidden factors for F.

Let W = {f ∈ B^{ω} : 01•f ∈ G}. To prove Theorem 20 it is enough to prove that W = F. Let L ⊆ Σ^{ω} and let x ∈ Σ^{∗}. We define the (left) quotient x^{−1}L by x^{−1}L = {y ∈ Σ^{ω} : xy ∈ L}. The next lemma establishes several identities concerning quotients of the set W. They are proved using (1) and Lemma 18. The identities demonstrate that W is precisely the set of infinite labeled paths through the automaton A_{01} given in Figure 1. These are just the labeled paths omitting factors in I, so that W = F. Thus, proving Lemma 21 establishes Theorem 20. Lemma 21. The following identities hold:

(a) W = α^{−1}W;

(b) (βαα)^{−1}W = (ββ)^{−1}W = β^{−1}W;

(c) (βαβ)^{−1}W = γ^{−1}W = (βγ)^{−1}W = (γγ)^{−1}W;

(d) (βα)^{−1}W = (γα)^{−1}W;

(e) (βαγ)^{−1}W = (γβ)^{−1}W = ∅.

Each set of identities corresponds to the state of A_{01} with the same label as the identities. The non-accepting sink (e) is not shown in the figure.

Proof. Suppose f ∈ B^{∗}. Let 01 • f = x. Thus 01 is a prefix of x.

(a) We have

αf ∈ W ⟺ 01 • αf ∈ G
⟺ (01 • α)δ(01)^{−1}δ(x) ∈ G
⟺ \overline{0100(0100)}^{−1}δ(x) ∈ G
⟺ x ∈ G
⟺ 01 • f ∈ G
⟺ f ∈ W,

\begin{matrix}a \\ start \end{matrix} ; b ; c ; d ; \begin{matrix}α \\ β \\ β \\ α \\ γ \\ β \\ γ \\ γ \\ α \\ α \end{matrix}

Figure 1: ‘Fife’ automaton A_{01} for G_{01}.

so that α^{−1}W = W.

(b) Here

βf ∈ W ⟺ 01 • βf ∈ G
⟺ (01 • β)δ(01)^{−1}δ(x) ∈ G
⟺ 01 \overline{0100(0100)}^{−1}δ(x) ∈ G
⟺ δ(0x) ∈ G ⟺ 0x ∈ G.

Similarly we find that

ββf ∈ W ⟺ 01 • ββf ∈ G

⟺ (01 • ββ)δ^{2}(01)^{−1}δ^{2}(x) ∈ G ⟺ 010100 \overline{01000101(01000101)}^{−1}δ^{2}(x) ∈ G ⟺ δ(0δ(0x)) ∈ G ⟺ 0δ(0x) ∈ G ⟺ 10x ∈ G or 0x ∈ G_{001} ⟺ 0x ∈ G.

Here we use the fact that 01 is a prefix of x, so that 10x ∉ G and 0x ∈ 001{0, 1}^{ω}.

Finally we get

βααf ∈ W ⟺ 01 • βααf ∈ G

⟺ (01 • βαα)δ^{3}(01)^{−1}δ^{3}(x) ∈ G ⟺ 01δ^{3}(x) ∈ G ⟺ δ(0δ^{2}(x)) ∈ G ⟺ 0δ^{2}(x) ∈ G ⟺ 1δ(x) ∈ G or δ(x) ∈ G_{001} ⟺ 1δ(x) ∈ G ⟺ 0x ∈ G.

Here again note that 01 is a prefix of δ(x). We have shown that (βαα)^{−1}W = (ββ)^{−1}W = β^{−1}W, as desired.

(c) We have

γf ∈ W ⟺ 01 • γf ∈ G

⟺ (01 • γ)δ(01)^{−1}δ(x) ∈ G

⟺ 0101 \overline{0100(0100)}^{−1}δ(x) ∈ G ⟺ δ(00x) ∈ G ⟺ 00x ∈ G.

We also find

βαβf ∈ W ⟺ 01 • βαβf ∈ G

⟺ (01 • βαβ)δ^{3}(01)^{−1}δ^{3}(x) ∈ G ⟺ 0101000101δ^{3}(x) ∈ G ⟺ δ(0δ^{2}(0x)) ∈ G ⟺ 0δ^{2}(0x) ∈ G ⟺ 1δ(0x) ∈ G or δ(0x) ∈ G_{001} ⟺ 1δ(0x) ∈ G ⟺ 00x ∈ G.

Similarly, we get

βγf ∈ W ⟺ 01 • βγf ∈ G
⟺ (01 • βγ)δ^{2}(01)^{−1}δ^{2}(x) ∈ G
⟺ 0101000100 \overline{01000101(01000101)}^{−1}δ^{2}(x) ∈ G
⟺ δ(0δ(00x)) ∈ G
⟺ 0δ(00x) ∈ G
⟺ 100x ∈ G or 00x ∈ G_{001}
⟺ 00x ∈ G.

We also have

γγf ∈ W ⟺ 01 • γγf ∈ G
⟺ (01 • γγ)δ^{2}(01)^{−1}δ^{2}(x) ∈ G
⟺ 010101000100 \overline{01000101(01000101)}^{−1}δ^{2}(x) ∈ G
⟺ δ^{2}(100x) ∈ G
⟺ 100x ∈ G.

Finally, suppose 00x ∈ G. Then 0001 is a prefix of 00x, and by Theorem 7 we can write 00x = δ(10y), some 10y ∈ G. Then by Lemma 16, 010y ∈ G. Thus δ(010y) = 0100x ∈ G, and in particular, 100x ∈ G. We conclude that 100x ∈ G ⟺ 00x ∈ G, which gives the desired result.

(d) In this case we see that

βαf ∈ W ⟺ 01 • βαf ∈ G
⟺ (01 • βα)δ^{2}(01)^{−1}δ^{2}(x) ∈ G
⟺ 01 \overline{01000101(01000101)}^{−1}δ^{2}(x) ∈ G
⟺ δ(0δ(x)) ∈ G
⟺ 0δ(x) ∈ G
⟺ 1x ∈ G or x ∈ G_{001}
⟺ 1x ∈ G.

Also we have

γαf ∈ W ⟺ 01 • γαf ∈ G
⟺ (01 • γα)δ^{2}(01)^{−1}δ^{2}(x) ∈ G
⟺ 0101 \overline{01000101(01000101)}^{−1}δ^{2}(x) ∈ G
⟺ δ(00δ(x)) ∈ G
⟺ δ^{2}(1x) ∈ G ⟺ 1x ∈ G.

Thus (βα)^{−1}W = (γα)^{−1}W.

(e) Here

βαγf ∈ W ⟺ 01 • βαγf ∈ G

⟺ (01 • βαγ)δ^{3}(01)^{−1}δ^{3}(x) ∈ G ⟺ 010100010101000101δ^{3}(x) ∈ G ⟺ δ(0δ^{2}(00x)) ∈ G ⟺ 0δ^{2}(00x) ∈ G ⟺ 1δ(00x) ∈ G or δ(00x) ∈ G_{001} ⟺ 1δ(00x) ∈ G ⟺ 000x ∈ G.

But 000x has prefix 0000. Thus (βαγ)^{−1}W = ∅. We also find

γβf ∈ W ⟺ 01 • γβf ∈ G

⟺ (01 • γβ)δ^{2}(01)^{−1}δ^{2}(x) ∈ G ⟺ 01010100 \overline{01000101(01000101)}^{−1}δ^{2}(x) ∈ G ⟺ δ^{2}(10x) ∈ G ⟺ 10x ∈ G.

But 10x has prefix 1001, so (γβ)^{−1}W = ∅. We have

G = G_{01} ∪ G_{001} ∪ G_{0001} ∪ G_{1}.

We can write Theorem 20 as

G_{01} = 01 • W.

By Lemma 16, x ∈ G_{1} if and only if 0x ∈ G_{01}, so that

G_{1} = 0^{−1}G_{01}.

Also, by Theorem 7 and Theorem 6,

G_{0001} = δ(G_{1}),

since G_{10} = G_{1}. If x ∈ G_{001}, we can write x = 0δ(0y) for some y. However, by Lemma 18 we get

0δ(0y) ∈ G ⟺ 10y ∈ G or 0y ∈ G_{001}
⟺ 010y ∈ G or 0y ∈ G_{001} by Lemma 16
⟺ 010y ∈ G_{01} or 0y ∈ G_{001}
⟺ 0y ∈ (01)^{−1}G_{01} or 0y ∈ G_{001}
⟺ 0δ(0y) ∈ 0δ((01)^{−1}G_{01} ∪ G_{001}), so that

G_{001} = 0δ((01)^{−1}G_{01} ∪ G_{001}).

We summarize these results in a theorem.

Theorem 22. The following identities hold:

G_{01} = 01 • W;
G_{001} = 0δ((01)^{−1}G_{01} ∪ G_{001});
G_{0001} = δ(G_{1});
G_{1} = 0^{−1}G_{01}.

Since I is a regular language one could give an enumeration of finite prefixes of G_{01} (and hence G_{0001}, G_{1}) following the approach of Kobayashi [10]. This would give a lower bound on good words of length n. Obtaining an enumeration of all prefixes of G would involve dealing with the recursion in the equation for G_{001}, and would give a better lower bound on the number of length n good words.

It would be nice to remove the recursion in the equation for G_{001}. With I, F, α̂, β̂, γ̂, ˆ•, etc., corresponding to I, F, α, β, γ, •, etc., but for overlaps, Rampersad’s formulation of Fife’s theorem has the following (nonrecursive) form:

Theorem 23. Let x ∈ {0, 1}^{ω}.

1. If x begins with 01, then x is overlap-free if and only if x = 01ˆ•f for some f ∈ F.

2. If x begins with 001, then x is overlap-free if and only if x = 01ˆ•f for some βf ∈ F.

Remark 24. In the second part of this theorem the condition can be rewritten as saying that x ∈ 001{0, 1}^{ω} is not overlap-free, if and only if β̂f has a factor in I, where f describes the canonical decomposition of x . In particular, if f has a factor in I, then x is not overlap-free. No result analogous to this seems possible for good words; we shall see that there are words x ∈ G_{001} with description x = 001 • f such that f has a factor βαββ ∈ I. On the other hand, αααγ ∉ I, but cannot be a factor of an infinite word f such that 001 • f ∈ G.

Let f ∈ B^{ω} such that 001 • f = x. Let w ∈ B^{k}. Then

001 • wf = (001 • w)δ^{k}(01)^{−1}δ^{k}(x).  (2)

Let F_{001} be the set of infinite words walkable on the automaton A_{001} of Figure 2.

Theorem 25. Let x ∈ {0, 1}^{ω}. If x begins with 001, then x is good if and only if x = 001•f for some f ∈ F_{001}.

Let W_{001} = {f ∈ B^{ω} : 001 • f ∈ G}. We prove that W_{001} = F_{001}.

The identities in the following lemma correspond to the states of A_{001}, except for state βγα, which is labeled for its shortest path from the state a. The non-accepting sink (d) is omitted from the figure. Proving the identities thus proves Theorem 25. One notes that βαββ ∈ I ∩ F_{001}. However, αααγ is a prefix of words in F, but cannot be a factor of a word f ∈ F_{001}.

\begin{matrix}a \\ start \end{matrix} ; b ; c ; βγα ; \begin{matrix}α \\ β \\ β \\ α \\ γ \\ α \\ β \\ γ \\ α \\ β \end{matrix}

Figure 2: ‘Fife’ automaton A_{001} for G_{001}.

Lemma 26. The following identities hold:

(a) (βα)^{−1}W_{001} = W_{001} = α^{−1}W_{001};

(b) (βγαα)^{−1}W_{001} = (βγβ)^{−1}W_{001} = (ββ)^{−1}W_{001} = β^{−1}W_{001};

(c) (βγαβ)^{−1}W_{001} = (βγγ)^{−1}W_{001} = (βγ)^{−1}W_{001};

(d) (βγαγ)^{−1}W_{001} = γ^{−1} = ∅.

Proof. Suppose f ∈ B^{∗}. Let 001 • f = x. Thus 001 is a prefix of x.

(a) We have

αf ∈ W_{001} ⟺ 001 • αf ∈ G

⟺ (001 • α)δ(01)^{−1}δ(x) ∈ G ⟺ 0 \overline{0100(0100)}^{−1}δ(x) ∈ G ⟺ 1x ∈ G or x ∈ G_{001} ⟺ x ∈ G ⟺ f ∈ W_{001}.

We also find that

βαf ∈ W_{001} ⟺ 001 • βαf ∈ G

⟺ (001 • βα)δ^{2}(01)^{−1}δ^{2}(x) ∈ G ⟺ 001 \overline{01000101(01000101)}^{−1}δ^{2}(x) ∈ G ⟺ 0δ(0δ(x)) ∈ G ⟺ 10δ(x) ∈ G or 0δ(x) ∈ G_{001} ⟺ 0δ(x) ∈ G ⟺ 1x ∈ G or x ∈ G_{001} ⟺ x ∈ G ⟺ f ∈ W_{001},

so that (βα)^{−1}W_{001} = α^{−1}W_{001} = W_{001}.

(b) Here we have

βf ∈ W_{001} ⟺ 001 • βf ∈ G
⟺ (001 • β)δ(01)^{−1}δ(x) ∈ G
⟺ 001 \overline{0100(0100)}^{−1}δ(x) ∈ G
⟺ 0δ(0x) ∈ G
⟺ 10x ∈ G or 0x ∈ G_{001}
⟺ 10x ∈ G.

In the same way we get

ββf ∈ W_{001} ⟺ 001 • ββf ∈ G

⟺ (01 • ββ)δ^{2}(01)^{−1}δ^{2}(x) ∈ G ⟺ 010100 \overline{01000101(01000101)}^{−1}δ^{2}(x) ∈ G ⟺ δ(0δ(0x)) ∈ G ⟺ 0δ(0x) ∈ G ⟺ 10x ∈ G or 0x ∈ G_{001} ⟺ 10x ∈ G.

Finally we find that

βγααf ∈ W_{001} ⟺ 001 • βγααf ∈ G

⟺ (01 • βγαα)δ^{4}(01)^{−1}δ^{4}(x) ∈ G ⟺ 00101000100δ^{4}(x) ∈ G ⟺ 0δ(0δ^{2}(1δ(x))) ∈ G ⟺ 10δ^{2}(1δ(x)) ∈ G or 0δ^{2}(1δ(x)) ∈ G_{001} ⟺ 0δ^{2}(1δ(x)) ∈ G ⟺ 1δ(1δ(x)) ∈ G or δ(1δ(x)) ∈ G_{001} ⟺ 1δ(1δ(x)) ∈ G ⟺ 01δ(x) ∈ G ⟺ δ(0x) ∈ G ⟺ 0x ∈ G ⟺ 10x ∈ G.

Thus (βγαα)^{−1}W_{001} = (βγβ)^{−1}W_{001} = (ββ)^{−1}W_{001} = (βα)^{−1}W_{001} = β^{−1}W_{001}. We have 0x ∈ G ⟺ 10x ∈ G by the same argument as at the end of case (c) of Lemma 21.

(c) Here we have

βγf ∈ W_{001} ⟺ 001 • βγf ∈ G

⟺ (001 • βγ)δ^{2}(01)^{−1}δ^{2}(x) ∈ G

⟺ 00101000100 \overline{01000101(01000101)}^{−1}δ^{2}(x) ∈ G ⟺ 0δ(0δ(00x)) ∈ G ⟺ 10δ(00x) ∈ G or 0δ(00x) ∈ G_{001} ⟺ 0δ(00x) ∈ G ⟺ 100x ∈ G or 00x ∈ G_{001} ⟺ 100x ∈ G.

We also have that

βγγf ∈ W_{001} ⟺ 001 • βγγf ∈ G

⟺ (001 • βγγ)δ^{3}(01)^{−1}δ^{3}(x) ∈ G ⟺ 001010001000100010101000101δ^{3}(x) ∈ G ⟺ 0δ(0δ^{2}(100x)) ∈ G ⟺ 0δ^{2}(100x) ∈ G or δ^{2}(100x) ∈ G_{001} ⟺ 0δ^{2}(100x) ∈ G ⟺ 1δ(100x) ∈ G or δ(100x) ∈ G_{001} ⟺ 1δ(100x) ∈ G ⟺ 0100x ∈ G ⟺ 100x ∈ G.

Finally we compute that

βγαβf ∈ W_{001} ⟺ 001 • βγαβf ∈ G

⟺ (001 • βγαβ)δ^{4}(01)^{−1}δ^{4}(x) ∈ G ⟺ 001010001000100010101000100δ^{4}(x) ∈ G ⟺ 0δ(0δ^{2}(1δ(0x))) ∈ G ⟺ 10δ^{2}(1δ(0x)) ∈ G or 0δ^{2}(1δ(0x)) ∈ G_{001} ⟺ 0δ^{2}(1δ(0x)) ∈ G ⟺ 1δ(1δ(0x)) ∈ G or δ(1δ(0x)) ∈ G_{001} ⟺ 1δ(1δ(0x)) ∈ G ⟺ 01δ(0x) ∈ G ⟺ δ(00x) ∈ G ⟺ 00x ∈ G ⟺ 100x ∈ G.

(d) In this instance we see that

γf ∈ W_{001} ⟺ 001 • γf ∈ G
⟺ (001 • γ)δ(01)^{−1}δ(x) ∈ G
⟺ 00101 \overline{0100(0100)}^{−1}δ(x) ∈ G
⟺ 0δ(00x)) ∈ G.

But 00x has prefix 0000. Thus γ^{−1}W_{001} = ∅.

In the same way we find that

βγαγf ∈ W_{001}
⟺ 001 • βγαγf ∈ G
⟺ (001 • βγαγ)δ^{4}(01)^{−1}δ^{4}(x) ∈ G
⟺ 0010100010001000101010001000100010101000100δ^{4}(x) ∈ G
⟺ 0δ(0δ(^{2}(1δ(00x))) ∈ G.

We see that 001 • βγαγf contains the prefix 0000 of 00x, so that (βγαγ)^{−1}W_{001} = ∅.

4 Lexicographically extremal good words

If u is a word of positive length we let u^{−} denote the word obtained from u by deleting its last letter. The lexicographic order on finite binary words is given recursively by

u < v ⟺ \{ \begin{matrix}v ≠ ϵ, & if u = ϵ; \\ (u^{−} < v^{−}) or ((u = u^{−}0) and (v = u^{−}1)), & otherwise. \end{matrix}

This extends to an ordering of one-sided infinite binary words; for infinite binary words u and v, we say that u < v exactly when there is a prefix u of u and a prefix v of v with |u| = |v| and u < v.

The morphism δ is order-reversing on infinite words: Let u and v be infinite binary words such that u < v. Write u = u′0u′, v = u′1v′ where u′ is the longest common prefix of u and v. Then δ(u′)01 is a prefix of δ(u), while δ(u′)00 is a prefix of δ(v), so that δ(u) > δ(v).

For each non-negative integer n, let ℓ_{n} (resp., m_{n}) be the lexicographically least (resp., greatest) word of length n such that ℓ_{n} (resp., m_{n}) is the prefix of a one-sided infinite good word.

Lemma 27. Let n be a non-negative integer. Word ℓ_{n} is a prefix of ℓ_{n+1}. Word m_{n} is a prefix of m_{n+1}.

Proof. We prove the result for the ℓ_{n}; the proof for the m_{n} is similar. Let ℓ_{n}r be a one-sided infinite good word. Let p be the length n + 1 prefix of ℓ_{n}r, and let q be the length n prefix of ℓ_{n+1}. We need to show that q = ℓ_{n}. Both p and q are prefixes of one-sided infinite good words. By definition we have ℓ_{n+1} ≤ p and ℓ_{n} ≤ q. If ℓ_{n} < q, then p^{−} = ℓ_{n} < q = ℓ_{n+1}^{−}, so that p < ℓ_{n+1}. This is a contradiction. Therefore ℓ_{n} = q, as desired.

Let ℓ = lim_{n→∞} ℓ_{n}, m = lim_{n→∞} m_{n}.

Lemma 28. Word ℓ is the lexicographically least one-sided infinite good word. Word m is the lexicographically greatest one-sided infinite good word.

Proof. We show that ℓ is lexicographically least. The proof that m is lexicographically greatest is similar. Let w be a one-sided infinite good word. For each n let w_{n} be the length n prefix of w, so that w = lim_{n→∞} w_{n}.

If for some n we have w_{n} > ℓ_{n}, then w > ℓ.

Otherwise w_{n} ≤ ℓ_{n} for all n. By the definition of the ℓ_{n} we have w_{n} ≥ ℓ_{n}, so that w_{n} = ℓ_{n} for all n. Thus w = lim_{n→∞} w_{n} = lim_{n→∞} ℓ_{n} = ℓ.

In all cases we find w ≥ ℓ.

Lemma 29. We have ℓ = δ(m).

Proof. Word 0001 is the least good word of length 4. Also, 0001 is a factor of d, so there are one-sided infinite good words (which are suffixes of d) with prefix 0001. Therefore, ℓ_{4} = 0001. Since 0001 is a prefix of ℓ, and ℓ is good, we can write ℓ = δ(m′) for some m′ by Theorem 7. Since ℓ is good, m′ is good by Lemma 8. It follows that m′ ≤ m. However if m′ < m then δ(m) < δ(m′) = ℓ since δ is order-reversing. This is impossible, since ℓ is least. Therefore m′ = m, and ℓ = δ(m).

Lemma 30. We have 0m = δ(ℓ).

Proof. Since 1 is the greatest good word of length 1, and d has suffixes that begin with 1, we have m_{1} = 1. By Lemma 16, 0m is good. Since 01 is a prefix of 0m, by Theorem 7 we can write 0m = δ(ℓ′) for some ℓ′. Since 0m is good, ℓ′ is good, so that ℓ′ ≥ ℓ. However, δ is order-reversing, so that if ℓ′ > ℓ, then δ(ℓ) > δ(ℓ′) = m, contradicting the maximality of m. Thus ℓ′ = ℓ and 0m = δ(ℓ).

Theorem 31. Word m is the fixed point

m = h_{1}(m),  (3)

where h_{1} = [1000, 1010]. Word ℓ is the fixed point

ℓ = h_{2}(ℓ),  (4)

where h_{2} = [0001, 0101].

Proof. From Lemma 29 and Lemma 30 we find m = 0^{−1}δ^{2}(m), so that for each n we have m_{4n−2} = 0^{−1}δ^{2}(m_{n}). However, δ^{2}(a) = 0h_{1}(a)0^{−1} for a ∈ {0, 1}, so that δ^{2}(w) = 0h_{1}(w)0^{−1} for w ∈ {0, 1}^{∗}. Thus m_{4n−2} = h_{1}(m_{n})0^{−1}. Then

m = lim_{n→∞} m_{n}

= lim_{n→∞} m_{4n−2}

= lim_{n→∞} h_{1}(m_{n})0^{−1}

= lim_{n→∞} h_{1}(m_{n})

= h_{1}( lim_{n→∞} m_{n})

= h_{1}(m).

The proof for ℓ is similar, using the fact that h_{2} = (01)^{−1}δ^{2}01.

Corollary 32. Every finite factor of ℓ or m is a factor of d, and vice versa. However, words ℓ, m, and d have no common suffix.

Proof. Because δ^{2}, h_{1}, and h_{2} are conjugates of each other, their fixed points have the same factors. For example, let u be a factor of d = lim_{n→∞} δ^{n}(0). Then for some n, u is a factor of δ^{2n}(0) = 0h_{1}^{2n}(0)0^{−1}, which is a factor of h_{1}^{2n}(1010) = h_{1}^{2n+1}(1), which is a prefix of m = lim_{n→∞} h_{1}^{n}(1). Thus u is a factor of m.

Now suppose d and ℓ have a common suffix s. (The proofs for the other pairs of fixed points are similar.) Write d = d_{i}s and ℓ = ℓ_{j}s for some i and j, where d_{n} is the prefix of d of length n. Then

d_{i}s = d
= δ^{2}(d)
= δ^{2}(d_{i})δ^{2}(s),

so that s = s_{3i}δ^{2}(s) where is s_{n} is the prefix of s of length n. Similarly,

ℓ_{j}s = ℓ
= h_{2}(ℓ)
= h_{2}(ℓ_{j})h_{2}(s),

so that s = s_{3j}h_{2}(s). Thus

s_{3j}h_{2}(s) = s
= s_{3i}δ^{2}(s)
= s_{3i}01h_{2}(s)
= s_{3i+2}h_{2}(s).

It follows that h_{2}(s) has period |3(i − j) + 2|. However, h_{2}(s) is good and does not contain fourth powers. Therefore, 3(i − j) + 2 = 0. This is impossible since i and j are integers.

5 Binary patterns in d

Every word encounters its factors as patterns. If a word encounters some binary pattern p, it necessarily encounters the complement \overline{p}. Shur [15] has shown that, up to complementation, the only binary patterns encountered by t are its factors and 00100. The situation with d is more complicated.

Lemma 33. Any factor 0u of d can be written as h_{1}(p) for some word p where h_{1} = [0, 01]. Any factor u0 of d can be written as h_{2}(p) for some word p where h_{2} = [0, 10]. Word d thus has an inverse image under each of h_{1} and h_{2}.

Proof. Every occurrence of 1 in d is preceded and followed by 0.

Corollary 34. Let 0u be a factor of d such that |0u| ≥ 13. Then 0u can be written as h_{1}(p) where p is neither a factor of d nor the complement of a factor of d. Thus d encounters infinitely many patterns p such that neither of p and \overline{p} is a factor of d.

Proof. The longest factor of d not containing 010001 is 100010101000, which has length 12. Therefore, 0u = h_{1}(p) has the factor 010001 = h_{1}(1001), and p has the factor 1001. Neither of 1001 and 0110 is a factor of d so neither p nor \overline{p} is a factor of d.

For every particular pattern p, the automatic proving system Walnut [11] can in theory, given enough computing power and time, determine whether d encounters p. However, in the next theorem, we effectively characterize all binary patterns p encountered by d. The remainder of this section is devoted to its proof.

Theorem 35. Word p is a binary pattern encountered by d if and only if one of the following holds:

1. One of p and \overline{p} is a factor of d, h_{1}^{−1}(d), or h_{2}^{−1}(d).

2. One of p and \overline{p} is among

0010100, 01001001000, 00100100100, 001001001000, 00010010010,

000100100100, 0010001000100, 00100010001000, 00010001000100, and 000100010001000.

The two possibilities are distinct.

The following analog of Lemma 12 will be useful for analyzing the patterns appearing in w:

Lemma 36. Let u, v be binary words such that uvu is a factor of d, |u| ≥ 3, and either

• we have |u|_{00} ≥ 1, or

• we have |u|_{10101} ≥ 1.

Then |uv| ≡ 0 (mod 4).

Proof. Suppose that 00 is a factor of u, and |u| ≥ 3. Then word u contains one of the factors 000, 001, and 100. These can only arise in d as suffixes of some prefix of d of the form δ^{2}(p0)0, δ^{2}(p0)01, and δ^{2}(p0), respectively. The index of every occurrence of factor 000, 001, or 100, and thus the index of every occurrence of u, in d is therefore fixed modulo 4, and the result follows.

Suppose |u|_{10101} ≥ 1. The factor 10101 only occurs in d as a suffix of some prefix of d of the form δ^{2}(p10)(00)^{−1} and the index of every occurrence of u in d is again fixed, modulo 4.

Theorem 37. Suppose that d encounters binary pattern p. Then one of p and \overline{p} either 1. is a factor of d, h_{1}^{−1}(d), or of h_{2}^{−1}(d), or

2. has the property that all its factors of the form 10^{k}1 have the same length.

Proof. Without loss of generality, replacing p by \overline{p} if necessary, assume that 0 is the first letter of p. Assume that neither p nor \overline{p} is a factor of d, h_{1}^{−1}(d), or h_{2}^{−1}(d). Since 000 is a factor of d and d does not encounter 0000, we must have |p|_{1} > 0. Let g(p) be a factor of δ^{n}(0) where g = [X, Y] is a non-erasing morphism, and n is as small as possible. By Lemma 11, |X| and |Y | are not both even. We consider cases based on |X|_{1} and |Y |_{1}.

Case 1 We have |X|_{1}, |Y |_{1} > 0: If XX (resp., Y Y, XY X, Y XY) is a factor of δ^{n}(0), then by Lemma 12, |X| (resp., |Y |, |XY |, |Y XY |) is even. It follows that not both XX and Y Y are factors of g(p). Also, not both XX and XY X are factors of g(p), or else |X| and |XY | are even, forcing |Y | to be even. Similarly, not both Y Y and Y XY are factors of g(p).

If neither of XX and Y Y is a factor of g(p), then g(p) is an alternating string of X’s and Y ’s, and thus a prefix of XY XY XY X. (Since d is good, the fourth power (XY)^{4} is not a factor of d.) But then p is a prefix of 0101010, which is a factor of d. This is a contradiction.

Suppose then, that XX is a factor of g(p). Then neither of Y Y and XY X is a factor of g(p). If |p|_{1} ≥ 2, then g(p) would have a prefix of the form X^{r}Y X^{s}Y, r, s ≥ 1. This contains a factor XY X, which is impossible. It follows that |p|_{1} ≤ 1. Because d is good, g(p) cannot have a factor XXXX, and we conclude that p is a factor of 0001000. But 0001000 is seen to be a factor of d.

Finally, suppose that Y Y is a factor of g(p). Then XX and Y XY are not factors of g(p). Therefore, p begins with 0, and has a factor 11, but not 00, 101, or 1111. (A factor 1111 in p would give a fourth power in the good word d.) It follows that p is one of 011, 0110, 0111, and 01110. However h_{1}(\overline{011}) = 0100, h_{1}(\overline{0110}) = 010001, \overline{0111} = 1000, and \overline{0111} = 1000 are all factors of d.

Case 2 We have |X|_{1} = |Y |_{1} = 0. This forces g(p) to be a factor of 000, so that p is a binary word of length 3 or less. Each such word, or its complement, is a factor of d.

Case 3 We have |X|_{1} > 0 but |Y |_{1} = 0. Write Y = 0^{n} where 1 ≤ n ≤ 3.

Case 3(a) We have |X| ≥ 3, and either |X|_{00} ≥ 1 or |X|_{10101} ≥ 1. If p contains only a single 0 (its first letter) then, since fourth powers do not appear in d, p must be a prefix of 0111, which is the complement of a factor of d. Otherwise, p has a factor of the form 01^{k}0 for some k, 0 ≤ k ≤ 3. Thus XY^{k}X = X0^{nk}X is a factor of d. By Lemma 36 with u = X, v = 0^{nk}, we have |X| ≡ −nk (mod 4). If n = 2, then since 0^{4} is not a factor of d, we have 0 ≤ k ≤ 1. Also, |X| ≡ −nk (mod 4), so |X| is even, giving k ≡ −|X|/2 (mod 2) and k is determined; each pair of 0’s in p is separated by the same number of 1’s. Then \overline{p} has the property that all its factors of the form 10^{k}1 have the same length. If n = 1 or n = 3, then since 0 ≤ k ≤ 3, k is determined by the congruence |X| ≡ −nk (mod 4), and again \overline{p} has the property that all its factors of the form 10^{k}1 have the same length.

Case 3(b) Either |X| < 3, or |X|_{00} = |X|_{10101} = 0. If |X|_{00} = 0, then X does not contain a factor 00 or 11, and is, therefore, an alternating string of 0’s and 1’s. Thus the given conditions imply that X = 00, or X is a factor of 01010. If X = 00, then g(p) must be a factor of 000, which is a factor of d. Suppose then that X is a factor of 01010. If p contained at most a single 0 (its first letter), then p would be a prefix of 0111, the complement of a factor of d. This is impossible. Therefore, assume that p has a factor of the form 01^{k}0. If |X| ≥ 3, then X is one of 010, 101, 0101, 1010, or 01010. One checks that for each of these possibilities for X there is exactly one value of k such that X0^{k}X is a factor of d:

• If X is 010 or 01010, k = 1.

• If X = 101, then a factor XX would imply d has factor 11; a factor X0X in d would extend on the right to a factor X0X0 = (10)^{4} in d; a factor X00X would imply d has factor 1001; thus k = 3.

• If X is 0101 or 1010, then XX is a fourth power, while X0X has the factor 1001; X000X contains 0000; thus k = 2.

Thus if |X| ≥ 3 then \overline{p} has the property that all its factors of the form 10^{k}1 have the same length. We are left with the cases where |X| ≤ 2 and X ≠ 00, i.e., word X is among 1, 01, and 10.

X = 1. Since d has a factor XY^{k}X, we cannot have Y = 00 or else d contains 0000 or 1001. Thus Y = 0. Then g = [1, 0], and p is the complement of a factor of d.

X = 01. Since |X| is even, we must have |Y | odd, so that n = 1 or n = 3. If n = 3, then Y X = 0^{4}1 and Y Y = 0^{6} are not factors of d, forcing |p|_{1} = 1, and p is a factor of 00010000, which is a factor of d. Suppose then that n = 1. Now, however g = [01, 0], and h_{1}(\overline{p}) = g(p) is a factor of d, so that \overline{p} is a factor of h_{1}^{−1}(d).

X = 10. Again |X| is even, so we find n = 3 or n = 1. In the first case, XY contains 0000, which is impossible. Thus p is a factor of 000, a factor of d. In the second case, g = [10, 0], and \overline{p} is a factor of h_{2}^{−1}(d).

Case 4 We have |X|_{1} = 0 but |Y |_{1} > 0. Write X = 0^{n} where 1 ≤ n ≤ 3.

Case 4(a) We have |Y | ≥ 3, and either |Y |_{00} ≥ 1 or |Y |_{10101} ≥ 1. If p contains at most a single 1 then, since fourth powers do not appear in d, p must be a factor of 0001000, which is a factor of d. Otherwise, p has some factor of the form 10^{k}1 for some k, 0 ≤ k ≤ 3. Thus Y X^{k}Y = Y 0^{nk}Y is a factor of d. By Lemma 36 with u = Y, v = 0^{nk}, we have |Y | ≡ −nk (mod 4). If n = 2, then since 0^{4} is not a factor of d, we have 0 ≤ k ≤ 1. Also, |Y | ≡ −nk so |Y | is even, giving k ≡ −|Y |/2 (mod 2) and k is determined. Therefore, p has the property that all its factors of the form 10^{k}1 have the same length. If n = 1 or n = 3, then since 0 ≤ k ≤ 3, k is determined by the congruence |Y | ≡ −nk (mod 4), and again p has the property that all its factors of the form 10^{k}1 have the same length.

Case 4(b) Either |Y | ≤ 3, or |Y |_{00} = |Y |_{10101} = 0. If |Y |_{00} = 0, then Y does not contain a factor 00 or 11, and is an alternating string of 0’s and 1’s. Thus the given conditions imply that Y = 00, or Y is a factor of 01010. If Y = 00, then g(p) must be a factor of 000, which is a factor of d. Suppose then that Y is a factor of 01010. If p contains at most a single 1, then p must be a factor of 0001000, a factor of d. Therefore, assume that p has a factor of the form 10^{k}1. If |Y | > 2, an analysis as in Case 3(a), shows that p has the property that all its factors of the form 10^{k}1 have the same length. The cases where |Y | ≤ 2 are impossible, with an analysis analogous to that of Case 3(a).

Lemma 38. The set of factors of d is closed under reversal.

Proof. To begin, we notice that if u is a binary word, then

(δ(u))^{R} = 0^{−1}δ(u^{R})0.

Suppose v is a factor of d. The set of length 2 factors of d is seen to be {00, 01, 10}, which is closed under reversal. Therefore, if |v| ≤ 2, then v^{R} is a factor of d. Suppose that |v| > 2, and for every shorter factor u of d, the reversal u^{R} is a factor of d. However, |v| > 2 implies that v is a factor of δ(u), for some factor u of d which is shorter than v. Thus u and u^{R} are factors of d. Then (δ(u))^{R} = 0^{−1}δ(u^{R})0 is also a factor of d, so that v^{R} is also. The result follows by induction.

Corollary 39. If d encounters pattern p, then d encounters pattern p^{R} also.

Theorem 40. The following are equivalent:

1. Word p is a binary pattern encountered by d, but neither p nor \overline{p} is a factor of d, h_{1}^{−1}(d), or h_{2}^{−1}(d).

2. One of p and \overline{p} is among

0010100, 01001001000, 00100100100, 001001001000, 00010010010, 000100100100, 0010001000100, 00100010001000, 00010001000100, and 000100010001000.

Proof. (1 ⇒ 2): Suppose that p is a binary pattern encountered by d, but neither p nor \overline{p} is a factor of d, h_{1}^{−1}(d), or h_{2}^{−1}(d). By Theorem 37, replacing p by \overline{p} if necessary, there is a number k such that there are exactly k 0’s between subsequent 1’s in p. Thus p = 0^{r}(10^{k})^{s}10^{t} for some k, r, s, t. Since d does not contain fourth powers, k, r, s, t ≤ 3. For the same reason, if s = 3, then r + s < k. If s = 0, then p is a factor of 0001000, which is a factor of d. We, therefore, have s ≥ 1. We consider cases based on the value of k:

k = 0: In this case, to avoid fourth powers, we must also have s ≤ 2, and p is a factor of 00011000 or 000111000. We note that h_{1}(\overline{00011000}) = 01010100010101 is a factor of d. Thus p cannot be a factor of 00011000, which would make \overline{p} a factor of h_{1}^{−1}(d). We conclude that p is a factor of 000111000. Note that, h_{2}(00011100) = h_{1}(00111000) = 00010101000 is a factor of d, so that p cannot be a proper factor of 000111000. It remains that we must have p = 000111000. To obtain a contradiction, we show that d does not encounter p.

Suppose g(p) is a factor of d, g = [X, Y] a non-erasing morphism. By Lemma 11 assume that one of |X| and |Y | is odd. Both XX and Y Y are factors of g(p) = XXXY Y Y XXX, so by Lemma 12 we must have |X|_{1} = 0 or |Y |_{1} = 0.

Suppose |X|_{1} = 0. Thus XXX ends in 000. Since XXXY is a factor of g(p), which is a factor of d, the first letter of Y is 1. Since XXX begins with 000 and Y XXX is a factor of g(p), the last letter of Y is 1. But then Y Y contains the factor 11, so that 11 is a factor of the good word d, which is impossible.

Suppose |Y |_{1} = 0. Switching X and Y in the argument of the previous paragraph shows that this is impossible also.

k = 1: We consider subcases based on whether s is 1, 2, or 3:

s = 1: If r + t ≥ 5, then p contains 00010100 or its reverse. However d is good, and therefore does not encounter 00010100. By Corollary 39, d does not encounter the reverse of d. We conclude that r + t ≤ 4, so that p is a factor of 0101000, 0010100, or 0001010. However, 0101000 and 0001010 are factors of d, so p cannot be a factor of one of these. Therefore p must be a factor of 0010100. Both 010100 and 010100 are factors of d, so p cannot be a proper factor of 0010100, forcing p = 0010100.

s = 2: In this case p is a factor of 00010101000, which is a factor of d.

s = 3: If r = t = 0, then p = 1010101 is the complement of a factor of d. However, if r > 0 or t > 0, then p contains one of the fourth powers 01010101 and 10101010, so that d does not encounter p, which is a contradiction.

k = 2: We consider subcases based on whether s is 1, 2, or 3:

s = 1: If r+t ≤ 5 then p is factor of 000100100 or of 001001000. However h_{2}(000100100) = 00010001000 = h_{1}(001001000) is a factor of d, so p is a factor of h_{1}^{−1}(d) or of h_{2}^{−1}(d), a contradiction. If r = t = 3, then p = 0001001000 = h_{2}(00010100), and d encounters 00010100. Since d is good, this is impossible.

s = 2: If r + t ≤ 3, then p is a factor of 1001001000, 0100100100, 0010010010, or 0001001001; however each of

h_{1}(1001001000) = 0100010001000,
h_{2}(0100100100) = 0100010001000,
h_{1}(0010010010) = 0001000100010, and
h_{2}(0001001001) = 0001000100010

is a factor of d, so that p is a factor of h_{1}^{−1}(d) or of h_{2}^{−1}(d).

If r = t = 3, then p = 0001001001000. To get a contradiction, we show that d does not encounter p. Otherwise, suppose without loss of generality that d has a factor g(p) where g = [X, Y] is a non-erasing morphism and |X|, |Y | are not both odd. Word d has the factor XXXY XXY XXY XXX. We cannot have |X|_{1} > 0, or since XX and XY X are factors of d, Lemma 12 would force both |X| and |Y | to be even. Write X = 0^{n}. Since XX is a factor of d, we must have n = 1 and X = 0. Since XXXY and Y XXX are factors of d, the first and last letters of Y are 1. Then Y XXY contains the factor 1001, which cannot be a factor of d. This is a contradiction.

We conclude that 4 ≤ r + t ≤ 5, so that p is one of 01001001001000, 00100100100100, 00010010010010, 001001001001000, and 000100100100100.

s = 3: If r + t ≤ 1, then p is a factor of 01001001001 or 10010010010. However h_{2}(01001001001) = 010001000100010 and h_{1}(010001000100010) are factors of d, so p is a factor of h_{1}^{−1}(d) or of h_{2}^{−1}(d), which is a contradiction. On the other hand, if r + t ≥ 2, then one of the fourth powers (001)^{4}), (010)^{4} and (100)^{4} is a factor of p, and d contains a fourth power, which is impossible.

k = 3: We consider subcases based on whether s is 1, 2, or 3:

s = 1: In this case p is a factor of 00010001000, which is a factor of d.

s = 2: If r ≤ 1 then p is a factor of 0100010001000 which is a factor of d. This is impossible. Similarly, t ≤ 1 is impossible. Thus p must be one of 0010001000100, 00010001000100, 00100010001000, and 000100010001000.

s = 3: If r, t ≤ 1 then p is a factor of 010001000100010, which is a factor of d, a contradiction. Suppose r ≥ 2 or t ≥ 2. Then p has q = 001000100010001 or its reverse as a factor. By Corollary 39, it suffices to show that d does not encounter q.

To get a contradiction, suppose that g(q) is a factor of d for some non-erasing morphism g = [X, Y] where one of |X| and Y is odd. Thus word d has the factor

XXY XXXY XXXY XXXY.

Since XX and XY X are factors of d, we must have X = 0^{n} for some n; otherwise, Lemma 12 implies that |X| and |Y | are even, a contradiction. Since XX is a factor of d, we have n = 1 and X = 0. Since Y XXX = Y 000 is a factor of d, the last letter of Y is 1. Therefore, Y is always followed by 0 in d, so XXY XXXY XXXY XXXY 0 is a factor of d. However XXY XXXY XXXY XXXY 0 = (00Y 0)^{4}, and d contains a fourth power. This is impossible.

(1 ⇐ 2): We show that d encounters each of the listed patterns, but none of these patterns or their complements is a factor of d, h_{1}^{−1}(d), or h_{2}^{−1}(d).

First we show that d encounters the listed patterns. Note that each of these patterns is a factor of 0010100, 001001001000, 000100100100, or 000100010001000. Since 001001001000 is the reverse of 000100100100, by Lemma 39 it suffices to show that d encounters 0010100, 001001001000, or 000100010001000.

• p = 0010100: Word d has the factor

00010001000 = g(0010100),

where g = [0, 010].

• p = 001001001000: Word d has the factor

0001010100010101000010101000 = g(001001001000),

where g = [0, 010101].

• p = 000100010001000: Word d has the factor

0001010100010101000010101000 = g(000100010001000),

where g = [0, 10101].

Next, we show that none of these patterns or their complements is a factor of d, h_{1}^{−1}(d), or h_{2}^{−1}(d). Notice that h_{1}(101) = 01001 and h_{2}(101) = 10010, and 1001 is not a factor of d, since d is good. The complements of all the listed patterns contain 101 as a factor, so none of the complements is a factor of h_{1}^{−1}(d), or h_{2}^{−1}(d). Further, all the complements of the listed factors contain 11 as a factor, so none of the complements is a factor of d. It therefore suffices to show that none of the listed patterns is a factor of d, h_{1}^{−1}(d), or h_{2}^{−1}(d).

Each of the listed patterns has one of 0010100, 01001001000, 00100100100, 00010010010, and 0010001000100 as a factor. It, therefore, suffices to show that none of these five patterns is a factor of d, h_{1}^{−1}(d), or h_{2}^{−1}(d).

Case 1: 0010100. If this was a factor of d, the 1’s would force it to appear in the context 00010100, which is impossible since d is good. Since 101 is a factor of 0010100, it is not a factor of h_{1}^{−1}(d), or h_{2}^{−1}(d) either.

Case 2: 01001001000. This has 1001 as a factor, and therefore is not a factor of d.

Word 00100010001000 = h_{1}(01001001000) cannot be a factor of d; if it preceded 0 then 0000 would be a factor of d; if it preceded 10 then (0100)^{4} is a factor of d, which is impossible.

Word h_{2}(01001001000) ends in the fourth power 0000 and cannot be a factor of d.

Case 3: 00100100100. This has 1001 as a factor, and therefore is not a factor of d.

Word h_{1}(00100100100) = 00010001000100 cannot be a factor of d; if it preceded 1 then 1001 would be a factor of d; if it preceded 00 then 0000 is a factor of d; if it preceded 01 then (0001)^{4} is a factor of d, which is impossible.

Word 00100010001000 = h_{2}(00100100100) cannot be a factor of d as argued in Case 2.

Case 4: 00010010010. This has 1001 as a factor, and therefore is not a factor of d. Word h_{1}(00010010010) begins with 0000 and cannot be a factor of d. Word 00010001000100 = h_{2}(00010010010) cannot be a factor of d as argued in Case 3.

Case 5: 0010001000100. This cannot be a factor of d. Recall that d is recurrent and does not contain factors 1001 or 0000. However, a second occurrence of this factor in d would be in the context 0001000100010001 = (0001)^{4}, which is impossible.

Word h_{1}(0010001000100) begins 00010000, containing 0000, and cannot be a factor of d. Word h_{2}(0010001000100) ends 00001000, containing 0000, and cannot be a factor of

d.

6 Acknowledgment

The author was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), funding reference number 2017-03901.

References

[1] J. Berstel, A rewriting of Fife’s theorem about overlap-free words, in J. Karhumäki, H. Maurer, and G. Rozenberg, eds., Results and Trends in Theoretical Computer Science, Lect. Notes in Comp. Sci., Vol. 812, Springer-Verlag, 1994, pp. 19–29.

[2] J.-P. Allouche, J. Currie, and J. Shallit, Extremal infinite overlap-free binary words, Electron. J. Combin. 5 (1998), #R27.

[3] J.-P. Allouche and J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in C. Ding, T. Helleseth, H. Niederreiter, eds., Sequences and their Applications, Proceedings of SETA ’98, Springer-Verlag, 1998, pp. 1–16.

[4] A. Carpi, Overlap-free words and finite automata, Theoret. Comput. Sci. 115 (1993), 243–260.

[5] J. Cassaigne, Counting overlap-free binary words, in P. Enjalbert, A. Finkel, and K. Wagner, eds., STACS 93, Proc. 10th Symp. Theoretical Aspects of Comp. Sci., Lect. Notes in Comp. Sci., Vol. 665, Springer-Verlag, 1993, pp. 216–225.

[6] D. Damanik, Local symmetries in the period-doubling sequence, Discrete Appl. Math. 100 (2000), 115–121.

[7] E. Fife, Binary sequences which contain no BBb, Trans. Amer. Math. Soc. 261 (1980), 115–136.

[8] N. Guglielmi and V. Protasov, Exact computation of joint spectral characteristics of linear operators. Found. Comput. Math. 13 (2013), 37–97.

[9] R. M. Jungers, V. Y. Protasov, and V. D. Blondel, Overlap-free words and spectra of matrices. Theoret. Comput. Sci. 410 (38-40), 3670–3684.

[10] Y. Kobayashi, Enumeration of irreducible binary words. Discrete Appl. Math. 20 (1988), 221–232.

[11] H. Mousavi, Automatic theorem proving in Walnut. Preprint, available at https://

arxiv.org/abs/1603.06017 .

[12] E. Prouhet, Mémoire sur quelques relations entre les puissances des nombres, C. R. Acad. Sci. Paris 33 (1851), 225.

[13] N. Rampersad, Overlap-Free Words and Generalizations, Ph.D. thesis, University of Waterloo, 2007.

[14] A. Restivo and S. Salemi, Overlap-free words on two symbols, in M. Nivat and D. Perrin, eds., Automata on Infinite Words, Vol. 192 of Lect. Notes in Comp. Sci., Springer-Verlag, 1984, pp. 198–206.

[15] A. M. Shur, Binary words avoided by the Thue-Morse sequence, Semigroup Forum 53 (1996), pp. 212–219.

[16] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2023. Available

at https://oeis.org.

[17] A. Thue, Über unendliche Zeichenreihen. Kra. Vidensk. Selsk. Skrifter. I. Mat. Nat. Kl. 7 (1906), pp. 1–22. Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell et al., editors, Universitetsforlaget, Oslo, 1977, pp. 139–158.

[18] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Kra. Vidensk. Selsk. Skrifter. I. Mat. Nat. Kl. 1 (1912), pp. 1–67. Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell et al., editors, Universitetsforlaget, Oslo, 1977, pp. 413–477.

2020 Mathematics Subject Classification: Primary 68R15. Keywords: combinatorics on words, word avoiding a pattern, period-doubling word, Thue-Morse word, Fife’s theorem.

(Concerned with sequences \underline{A010060} and \underline{A096268}.)

Received June 10 2023; revised version received September 18 2023; September 26 2023. Published in Journal of Integer Sequences, September 27 2023.

Return to Journal of Integer Sequences home page.