Some Properties of the singular words of the Fibonacci word

WEN Zhi-Xiong ^{1} and WEN Zhi-Ying ^{2}

Abstract

The combinatorial properties of the Fibonacci infinite word are of great interest in some aspects of mathematics and physics, such as number theory, fractal geometry, formal language, computational complexity, quasicrystals etc.

In this note, we introduce the singular words of the Fibonacci infinite word and discuss their properties. We establish two decompositions of the Fibonacci word in singular words and their consequences. By using these results, we discuss the local isomorphism of the Fibonacci word and the overlap properties of the factors. Moreover, we also give new proofs for the results on special words and the power of the factors.

The combinatorial properties of the Fibonacci infinite word are of great interest in some aspects of mathematics and physics, such as number theory, fractal geometry, formal language, computational complexity, quasicrystals etc. See [1, 3, 8, 9, 11]. Moreover, the properties of the subwords of the Fibonacci infinite word have been studied extensively by many authors [2, 4, 5, 6, 9, 10]. In this note, we shall present some new properties of the subwords of the Fibonacci word: as we shall see, the most striking of these properties is that the adjacent singular words of the same order are positively separated.

This note is organized as follows. After recalling some preliminary remarks on the Fibonacci word, we introduce the singular words and discuss their elementary properties. Then we establish two decompositions of the Fibonacci word in singular words (Theorems 1 and 2) and their consequences. By using these results, we discuss the local isomorphism of the Fibonacci word (Theorem 4) and the overlap properties of the factors (Theorem 6). Moreover, we also give new proofs for the results on special words (Theorem 5) and the power of the factors (Theorem 3).

In this note, we use the following definitions and terminology.

Let A = {a, b} be an alphabet of two letters, let A^{∗} be the free monoid on A, and let F be the free group generated by A. The elements of A^{∗} are called words. The neutral element of A^{∗} is called the empty word which we denote by ε. Let w be a word: we denote by |w| the length of w, we denote by |w|_{a} (resp. |w|_{b}) the number of letters of a (resp. b) appearing in w, we denote by L(w) the vector (|w|_{a}, |w|_{b}).

1Department of Physics, Wuhan University, Wuhan 430072 (P. R. China)

2Institute for Theoretical Physics, University of Nimegen, Toernooiveld 6525 ED Nimegen, The Netherlands and Department of Mathematics, Wuhan University, Wuhan 430072 (P. R. China)

An infinite word on A is a mapping x : IN ⟶ A, and we write x = x_{1}x_{2} ⋯ x_{n} ⋯, where x_{i} ∈ A. The set of infinite words is denoted by A^{ω}.

A word v is a factor of word w and we write v ≺ w, if there exist u, u′ ∈ A^{∗}, such that w = uvu′. We say that v is a left (resp. right) factor of a word w and we note that v ◁ w (resp. v ▷ w), if there exists u ∈ A^{∗} such that w = vu (resp. w = uv). The notions of left factors and right factors are extended in a natural way to A^{ω}.

Let w = x_{1}x_{2} ⋯ x_{n}. We denote by \overline{w} the mirror image of w; that is, \overline{w} = x_{n} ⋯ x_{2}x_{1}. If w = \overline{w}, the word will be called a palindrome, and the set of the palindromes is denoted by P. A word w ∈ A^{∗} is called primitive if u = v^{p}, v ∈ A^{∗}, p > 0, implies u = v.

Let w = x_{1}x_{2} ⋯ x_{n} ∈ A^{∗}, and let 1 ≤ k ≤ n. We define C_{k}(w) = x_{k+1} ⋯ x_{n}x_{1} ⋯ x_{k}, the k-th conjugation of the word w, and we note that C(w) = {C_{k}(w); 1 ≤ k ≤ |w|}. By convention, C_{−k}(w) = C_{|w|−k}(w).

Now let σ : A ⟶ A^{∗} be a morphism defined by σ(a) = ab, σ(b) = a. We define the n-th iteration of σ by σ^{n}(a) = σ(σ^{n−1}), n ≥ 2 and we denote F_{n} = σ^{n}(a) (by convention, we define σ^{0}(a) = a, σ^{0}(b) = b). Then the Fibonacci word F_{∞} is obtained by iterating σ with the letter a (see [2]).

Let w be a word. We denote by Ω_{n}(w) the set of factors of w of length n, where |w| ≥ n, and we simply note that Ω_{n} := Ω_{n}(F_{∞}).

By a natural embedding, we can regard the A^{∗} as a subset of F, and if we say that w is in F, this means that is reduced (see [7] and therein). Let w = x_{1}x_{2} ⋯ x_{n} ∈ A^{∗}. We denote by w^{−1} the inverse word of w, that is w^{−1} = x_{n}^{−1} ⋯ x_{2}^{−1}x_{1}^{−1}. Let w = uv, u, v ∈ A^{∗}, then wv^{−1} := u and u^{−1}w := v by convention.

One of the motivations of this note is as follows: we know that the Fibonacci word is related closely to the Fibonacci numbers (the Fibonacci number is defined by the recurrence formula f_{n+2} = f_{n+1} + f_{n} with the initial condition f_{−1} = f_{0} = 1). Consider the following decomposition of the Fibonacci word

\underline{a} \underline{b} \underline{aa} \underline{bab} \underline{aabaa} \underline{babaabab} \underline{aabaababaabaa} \underline{babaababaabaababaabab} ⋯

that is, the length of the n-th block in the decomposition is f_{n}, n ≥ −1. Then a question is posed naturally: What are these blocks? As we shall see, Theorem 1 will answer this question completely.

In this note, we shall use the following known facts which can be found in [2, 4, 8, 9].

Property 1 1) |σ^{n}(a)| = f_{n} and |C_{n}(F_{n})| = f_{n}, where f_{n} is the n-th Fibonacci number. That is, all conjugations of F_{n} are different each other. In particular, for any w ∈ C(F_{n}), we have

L(w) = L(F_{n}) = (f_{n−1}, f_{n−2}),

and moreover,

C(F_{n}) = \{\overline{w}; w ∈ C(F_{n})\}.

2) F_{n+1} = F_{n}F_{n−1}.

3) For any k ≥ 1, σ^{k}(F_{∞}) = F_{∞}, that is

F_{∞} = F_{k}F_{k−1}F_{k}F_{k}F_{k−1} · · · .

4) ab is a suffix of F_{n} for odd positive n, and ba is a suffix of F_{n} for even positive n.

5) b^{2} ⊀ F_{∞}, a^{3} ⊀ F_{∞}.

6) Any factor of F_{∞} will appear infinitely many times in F_{∞}.

7) w ≺ F_{∞} if and only if \overline{w} ≺ F_{∞}.

Remark 1 In this note, we shall only use Property 1 and not the other known results of the Fibonacci word. In particular, we shall again prove Theorems 3 and 5 by using singular words.

Let α and β be two words. Note that, by Property 1.4), if αβ ▷ F_{n}, then α ≠ β.

Lemma 1 Let n ≥ 2, and assume that αβ is a suffix of F_{n}. Then

F_{n} = F_{n−2}F_{n−1}α^{−1}β^{−1}αβ,
F_{n−2}F_{n−1} = F_{n}β^{−1}α^{−1}βα.

Proof. Note that αβ ▷ F_{n}, so βα ▷ F_{n−1} by property 1.4). It is easy to check the case of n = 2 directly. Suppose that the lemma is true for n. Then, by the hypothesis of the induction, we obtain

F_{n+1} = F_{n}F_{n−1} = F_{n−1}F_{n−2}F_{n−1} = F_{n−1}F_{n}α^{−1}β^{−1}αβ,
F_{n−1}F_{n} = F_{n−1}F_{n−2}F_{n−1}β^{−1}α^{−1}βα = F_{n+1}β^{−1}α^{−1}βα.

Now let |w| = f_{n}. Then by Property 1.3), w will be a factor of the following words: F_{n}F_{n}, F_{n}F_{n−1}F_{n}, F_{n}F_{n−1} and F_{n−1}F_{n}. If w = uF_{n−1}v with u ▷ F_{n}, v ◁ F_{n} and |v| ≤ f_{n−2}, then w ≺ F_{n}F_{n−1}F_{n−2} = F_{n}F_{n}. On the other hand, evidently, F_{n}F_{n−1} ≺ F_{n}F_{n}, and thus the four cases above will be reduced to the cases F_{n}F_{n} and F_{n−1}F_{n}.

On the other hand, by Property 1.1), Ω_{f_{n}}(F_{n}F_{n}) = C(F_{n}). Therefore it is sufficient to determine the factors of F_{n−1}F_{n}.

Let α and β be two words such that αβ is a suffix of F_{n}. We denote the word αF_{n}β^{−1} by w_{n}.

Lemma 2 We have the following:

1) w_{n} ∉ C(F_{n});

2) Ω_{f_{n}}(F_{n−1}F_{n}) = w_{n} ⋃{C_{k}(F_{n}); 0 ≤ k ≤ f_{n−2} −2}. In particular, as a factor, w_{n} appears only once in F_{n−1}F_{n}.

Proof. 1) Since α ≠ β, L(w_{n}) ≠ L(F_{n}), which yields 1).

2) By Lemma 1: if αβ ▷ F_{n}, then we have f_{n−1}F_{n} = F_{n}F_{n−1}α^{−1}β^{−1}αβ. Since F_{n−1} ◁ F_{n}, the first f_{n−1} factors of length f_{n} of the word F_{n−1}F_{n} are exactly C_{k}(F_{n}), 1 ≤ k ≤ f_{n−1}−2, and the last factor is F_{n} = C_{f_{n}}(F_{n}), the (f_{n−1}−1)-th factor is αF_{n}β^{−1} = w_{n}.

As we have seen, for any n ≥ 1, the set Ω_{f_{n}} consists of two parts: the first part consists exactly of all conjugations of F_{n}, the other is w_{n}. As we shall see, w_{n} possesses some interesting properties, which play an important role in the studies of the factors of F_{∞}.

The word w_{n} is called the n-th singular word of the Fibonacci word F_{∞}. For convenience, we define w_{−2} = ε, w_{−1} = a and w_{0} = b, and we denote by S the set of singular words of F_{∞}.

Now we discuss the properties of the singular words:

Property 2 We have the following:

1) If n ≥ 1, then

L(w_{n}) = \{ \begin{matrix}(f_{n−1} + 1, f_{n−2} − 1) & if n is odd; \\ (f_{n−1} − 1, f_{n−2} + 1) & if n is even. \end{matrix}

2) w_{n} ⊀ w_{n+1}.

3) If α ▷ w_{n+1}, then w_{n+2} = w_{n}w_{n+1}α^{−1}β.

4) w_{n} = w_{n−2}w_{n−3}w_{n−2}, n ≥ 1.

5) For n ≥ 1,

C_{f_{n−1}−1}(F_{n}) = w_{n−2}w_{n−1},
C_{f_{n}−1}(F_{n}) = w_{n−1}w_{n−2};

In particular,

w_{n−2} ≺ C_{k}(F_{n}) if and only if 0 ≤ k ≤ f_{n−1} − 1;
w_{n−1} ≺ C_{k}(F_{n}) if and only if f_{n−1} − 1 ≤ k ≤ f_{n} − 1.

6) For n ≥ 1, w_{2n−1} = aauaa, w_{2n} = bvb, where u, v ∈ A^{∗}.

7) For n ≥ 2, 1 < k < f_{n}, no proper conjugate of w_{n} is a subword of F_{∞}.

8) For n ≥ 0, w_{n}^{2} ⊀ F_{∞}.

9) For n ≥ −1, w_{n} is a palindrome.

10) w_{n} is not the product of two palindromes for n ≥ 2.

11) If n ≥ 2, then w_{n} is primitive.

12) For n ≥ 1, we have

w_{n} = w_{n}^{∗} ( ∏_{j=−1}^{n−2} w_{j}) = ( ∏_{j=−1}^{n−2} w_{n−j−3}) w_{n}^{∗}, where w_{n}^{∗} = \{ \begin{matrix}a & if n is odd, \\ b & if n is even; \end{matrix}

13) w_{n} ⊀ ∏_{j=−1}^{n−1} w_{j};

14) Let k ≥ −1 and p ≥ 1, and let u = ∏_{j=k}^{k+p} w_{j}. Then u ∉ S.

Proof. 1) If n is odd, then a ▷ F_{n−1}, b ▷ F_{n}. Thus

L(w_{n}) = L(aF_{n}b^{−1}) = (f_{n−1} + 1, f_{n−2} − 1),

and the case of n being even can be proved in the same way.

2) Let α ▷ F_{n}: then β ▷ F_{n+1}. By the definition of w_{n}, it is easi to see that w_{n} ⊀ F_{n+1}, so w_{n} ⊀ F_{n+1}β^{−1}. On the other hand w_{n} = βF_{n}α^{−1} ≠ αF_{n}β^{−1}. Since w_{n+1} = αF_{n+1}α^{−1}, thus w_{n} ⊀ w_{n+1}.

3) By definition, w_{n+2} = βF_{n}α^{−1}. Then by Lemma 1, we have

w_{n+2} = βF_{n}F_{n+1}β^{−1}α^{−1}β = w_{n}w_{n+1}α^{−1}β.

4) Let α ▷ F_{n}: then α ▷ F_{n−2} and β ▷ F_{n+1}, β ▷ F_{n−1}. Thus

w_{n+1} = αF_{n+1}β^{−1} = αF_{n−1}F_{n−2}F_{n−1}β^{−1}
= (αF_{n−1}β^{−1})(βF_{n−2}α^{−1})(αF_{n−1}β^{−1})
= w_{n−1}w_{n−2}w_{n−1}.

5) Let α ▷ F_{n}: then

F_{n} = F_{n−1}F_{n−2} = (F_{n−1}α^{−1})(αF_{n−2}β^{−1})β,

and so the results follow from the definitions of singular word and conjugation of word.

6) This follows immediately from the definition of w_{n} and 9).

7) and 8) follow from Property 1.5) and Property 2.9).

9) We prove by induction. It is checked directly that the conclusion is true for n ≤ 2. Now suppose that the conclusion is true for k ≤ n. Then, by 5),

\overline{w_{n+1}} = \overline{w_{n−1}w_{n−2}w_{n−1}} = \overline{w_{n−1}} \overline{w_{n−2}} \overline{w_{n−1}} = w_{n−1}w_{n−2}w_{n−1} = w_{n+1},

that is, w_{n+1} ∈ P.

10) Let w_{n} = uv, where u, v ∈ P. Since w_{n} is a palindrome, so

w_{n} = \overline{w_{n}} = \overline{uv} = uv = vu.

Therefore, the |u|-th conjugation of w_{n} will be a factor of F_{∞}. Then, by 6), if n ≥ 2, we have a^{4} ≺ F_{∞}, or b^{2} ≺ F_{∞}, which will contradict Property 1.5).

11) Let w_{n} = u^{p}, with u ∈ A^{∗}, and p ≥ 2. Since w_{n} ∈ P, so do u and u^{p−1}, and hence w_{n} = u^{p} = uu^{p−1} will be a product of two palindromes; but, by 10), that is impossible.

12) It is easy to verify that F_{n} = abF_{0}F_{1} ⋯ F_{n−3}F_{n−2}. If n is odd, then b ▷ F_{n}. Therefore

w_{n} = aF_{n}b^{−1} = aab(aF_{1}b^{−1})(bF_{2}a^{−1}) ⋯ (bF_{n−3}a^{−1})(aF_{n−2}b^{−1})
= aw_{−1}w_{0}w_{1} ⋯ w_{n−3}w_{n−2},

and the case of n being even may be proved in the same manner.

13) If w_{n} ≺ ∏_{j=−1}^{n−1} w_{j}, then by 12), w_{n} ≺ w_{n}^{∗} ∏_{j=−1}^{n−1} w_{j} = w_{n+1}, which will contra-

dict 2).

14) Assume that u = ∏_{j=k}^{k+p} w_{j} = w_{m} for some m ≥ 0. Since w_{k+p} is a factor,

m > k + p. On the other hand, by 12), w_{m} ≺ w_{k+p}^{∗} ∏_{j=−1}^{k+p} w_{j} = w_{k+p+2}, so

m = k + p + 1. By 13), this is impossible.

By an argument analogous to that of Property 2.12), we obtain the following result, which answers the question posed in the introduction.

Theorem 1 F_{∞} = ∏_{j=−1}^{∞} w_{j}.

Proof. The proof is similar that of Property 2.12).

Now we are going to introduce another decomposition of F_{∞} which will show the positively separate property of the singular words. To this end, we first establish some lemmas.

Lemma 3 Let w_{n}w_{n+1} = u_{1}u_{2}u_{3} (or w_{n+1}w_{n} = u_{1}u_{2}u_{3}) with 0 < |u_{1}| < f_{n} and 0 < |u_{3}| < f_{n+1}, then u_{2} ∉ S.

Proof. i) By the condition of the lemma, 2 < |u_{2}| < f_{n+2} − 2, so u_{2} ≠ w_{n+2}.

ii) Let α▷F_{n}, then w_{n}w_{n+1} = βF_{n}F_{n−1}β^{−1}. By Lemma 2, w_{n+1} = αF_{n+1}β^{−1} appears only once in F_{n}F_{n+1}. Note that |u_{3}| ≥ 1, we obtain u_{2} ≠ w_{n+1}.

iii) Let |u_{2}| = f_{n} and F_{n+1} = F_{n}F_{n−1}, u_{2} ≺ F_{n}F_{n}. But by lemma 2, w_{n} ⊀ F_{n}F_{n}, and thus u_{2} ≠ w_{n}.

iv) Let |u_{2}| = f_{n−1}. Since w_{n}w_{n+1} = w_{n}w_{n−1}w_{n−2}w_{n−1}, then we must have u_{2} ≺ αF_{n}F_{n−1}α^{−1}. By using lemma 2, a discussion as in ii) yields u_{2} ≠ w_{n−1}.

The other cases will be reduced to one of the four cases above, so by repeating this argument, we prove that, for any k ≥ 1, u_{2} ≠ w_{k}, that is, u_{2} ∉ S.

Now let n ≥ 0 be fixed. We define a substitution ϕ_{n} : A ⟶ A^{∗} by ϕ_{n}(a) = w_{n+1}, ϕ_{n}(b) = w_{n−1}. Let Σ_{n} = {w_{n+1}, w_{n−1}}. For a singular word w_{k}, we say W_{k}(Σ_{n}) := ϕ_{n}(w_{k}) (if there is no confusion, we simply write W_{k}), the k-th singular word over Σ_{n}.

Lemma 4 Let n ≥ 0 and k ≥ 1. Then we have

w_{n+2k} = w_{n}x_{1}w_{n}x_{2} ⋯ w_{n}x_{f_{2k−2}}w_{n},
w_{2k+1} = y_{1}w_{n}y_{2}w_{n} ⋯ y_{f_{2k−1}−1}w_{n}y_{f_{2k−1}},

where x_{j}, y_{j} ∈ Σ_{n}. Moreover,

x_{1}x_{2} ⋯ x_{f_{2k−2}} = W_{2k−2} and y_{1}y_{2} ⋯ y_{f_{2k−1}} = W_{2k−1}

are, respectively, the (2k − 2)-th and (2k − 1)-th singular words over Σ_{n}.

Proof. For any fixed n, we prove the lemma by induction. We have, by Property 2.4),

w_{n+2} = w_{n}w_{n−1}w_{n},
w_{n+3} = w_{n+1}w_{n}w_{n+1},
w_{n+4} = w_{n}w_{n−1}w_{n}w_{n+1}w_{n}w_{n−1}w_{n},
w_{n+5} = w_{n+1}w_{n}w_{n+1}w_{n}w_{n−1}w_{n}w_{n+1}w_{n}w_{n+1},

and hence the conclusion is true for k = 1, 2. Now suppose that the conclusion is true for k − 1 and k. Then

w_{n+2(k+1)} = w_{n+2k}w_{n+2k−1}w_{n+2k}
= w_{n}x_{1} ⋯ w_{n}x_{f_{2k−2}}w_{n}y_{1}w_{n} ⋯ w_{n}y_{f_{2k−3}}w_{n} ⋯ w_{n}x_{f_{2k−2}},

since x_{1}x_{2} ⋯ x_{f_{2k−2}} and y_{1}y_{2} ⋯ y_{f_{2k−3}} are, respectively, the (2k − 2)-th and (2k − 3)-th singular words W_{2k−2} and W_{2k−3} on Σ_{n} by the assumption of the induction. So, by Property 2.4),

x_{1}x_{2} ⋯ x_{f_{2k−2}}y_{1}y_{2} ⋯ y_{f_{2k−3}}x_{1}x_{2} ⋯ x_{f_{2k−2}} = W_{2k−2}W_{2k−3}W_{2k−2} = W_{2k}

is the (2k)-th singular word. The same discussion gives the proof for w_{n+2k+3}. ¿From Lemmas 3 and 4, we immediately obtain the following.

Corollary 1 Let m ≥ n + 2. Then there are exactly m − n − 2 factors w_{n} appearing in w_{n} which are separated by w_{n−1} and w_{n+1} as in Lemma 4.

Let n be fixed, then by Property 1.6), the word w_{n} will appear in F_{∞} infinitely many times. We arrange these words as a sequence w_{n,k} the k-th singular word of the order n.

Lemma 5 Let F_{∞} = ∏_{j=−1}^{∞} w_{j} be the decomposition as in Theorem 1. Let u be

any singular word of order n (that is, u = w_{n,k} for some k). Then u must be contained completely in some w_{m}, where m ≥ n.

Proof. i) From Property 2.13), w_{n} ⊀ ∏_{j=−1}^{n−1} w_{j}. ii) If u ≺ ∏_{j=−1}^{n} w_{j}, then by Property 2.12),

u ≺ (w_{n−1}^{∗} ∏_{j=−1}^{n−1} w_{j}) w_{n} = w_{n+1}w_{n},

so by Lemma 3, u must be w_{n}.

¿From i) and ii), we only need to consider u ≺ ∏_{j=n}^{∞} w_{j}. Since |u| = |w_{n}|,

there exists m, m ≥ n, such that, either u ≺ w_{m}, or u ≺ w_{m}w_{m+1} with u ⊀ w_{n} and u ⊀ w_{n+1}. But by lemma 3, the later case is impossible.

We thus finish the proof from the discussions above.

Now we can state our main result of this note.

Theorem 2 For any n ≥ 0, we have

F_{∞} = ( ∏_{j=−1}^{n−1} w_{j}) w_{n,1}z_{1}w_{n,2}z_{2} ⋯ w_{n,k}z_{k}w_{n,k+1} ⋯

where z = z_{1}z_{2} ⋯ z_{n} ⋯ is the Fibonacci word over Σ_{n}.

Proof. From theorem 1 and lemma 4, we get

F_{∞} = ( ∏_{j=−1}^{n−1} w_{j}) w_{n}w_{n+1} ( ∏_{j=n+2}^{∞} w_{j})

= ( ∏_{j=−1}^{n−1} w_{j}) w_{n}w_{n+1}(w_{n}w_{n−1}w_{n})(w_{n+1}w_{n}w_{n+1}) ⋯
(w_{n}x_{1}w_{n} ⋯ x_{f_{2k−2}}w_{n})(y_{1}w_{n}y_{2} ⋯ w_{n}y_{f_{2k−1}}) ⋯

Note that

i) by lemma 4, lemma 5 and corollary 1, all factor w_{n} of F_{∞} (or the sequence w_{n,k}, k ≥ 1) appear in the formula above; ii) by lemma 4,

x_{1} ⋯ x_{f_{2k−2}} = W_{2k−2},
y_{1} ⋯ y_{f_{2k−1}} = W_{2k−1},

thus ∏_{j=1}^{∞} z_{j} = ∏_{j=−1}^{∞} W_{j} is the Fibonacci word on Σ_{n}.

i) and ii) follow the theorem.

The following example illustrates the decomposition of F_{∞} of the words w_{1}, w_{2}:

abaa(bab)\underline{aabaa}(bab)\underline{aa}(bab)\underline{aabaa}(bab)\underline{aabaa}(bab)\underline{aa}(bab)\underline{aabaa}(bab)\underline{aa}(bab)\underline{aabaa}···

Let y = y_{1}y_{2} ⋯ y_{n} ⋯ be an infinite word over {a, b}. Let u, v ≺ y, u = y_{k}y_{k+1} ⋯ y_{k+p} and v = y_{l}y_{l+1} ⋯ y_{l+m}, where l ≥ k, then the distance of the words u and v define by

d(u, v) = \{ \begin{matrix}l − k − p & if l > k − p; \\ 0 & otherwise. \end{matrix}

If d(u, v) > 0, we say that the words u and v are positively separate.

The theorem 2 has the following direct consequences:

Corollary 2 The adjacent singular words of the same order are positively separate. More precisely, for any n and k, we have

d(w_{n,k}, w_{n,k+1}) ∈ {f_{n+1}, f_{n−1}}.

Moreover, one of d(w_{n,k}, w_{n,k+1}) and d(w_{n,k+1}, w_{n,k+2}) is f_{n+1}.

Corollary 3 The left and the right adjacent word of the length f_{n−2k} of the singular word w_{n+1} are exactly w_{n−2k}.

Let w = x_{k}x_{k+1} ⋯ x_{k+p} (k, p ≥ 1) be a factor of F_{∞}. If there is an integer l, 1 ≤ l ≤ p, such that w = x_{k+l}x_{k+l+1} ⋯ x_{k+l+p}, then we say that w has overlap with p − l as length of overlap. The above definition is equivalent to the following assertion: Let u ≺ F_{∞}, if there exist words x, y and z such that u = xy = yz and u(y) := uz = xyz ≺ F_{∞}. From corollary 2, we obtain immediately

Corollary 4 For n ≥ 1, w_{n} has no overlap.

Corollary 5 Let u ≺ F_{∞} and let f_{n} < |u| ≤ f_{n+1}, let w be one of the largest singular words contained in u (in the sense of order), then w appears only once in u, moreover, w must be one of the three following singular words: w_{n−1}, w_{n} and w_{n+1}.

Proof. Suppose that the conclusion is not true. Then there will be another singular word of the same order contained in u which is adjacent to w and we denote by w′. Thus there is a word v, such that wvw′ ≺ u (or w′vw ≺ u). By theorem 2, either v, or wvw′, will be a singular word which has higher order than w, this is in contradiction with the hypothesis of w.

The second conclusion of the corollary follows from directly the property 2.5).

As applications of singular word, in particular, the positively separate property of the singular words, we are going to illustrate some examples in the following. Although some results are known (example 1 and example 3), but the proofs are new. Moreover, these proofs show that the singular words play an important role in the studies of the factor of the Fibonacci word.

Example 1. Power of the factors. [2, 5, 6, 9]

Theorem 3 We have

1) For any n, w_{n}^{2} ⊀ F_{∞};

2) For 0 ≤ k ≤ f_{n} − 1, (C_{k}(F_{n}))^{2} ≺ F_{∞};

3) If u ≺ F_{∞} with f_{n−1} < |u| < f_{n}, then u^{2} ⊀ F_{∞};

4) If 0 ≤ k ≤ f_{n−1} − 2, then (C_{k}(F_{n}))^{3} ≺ F_{∞};

5) If f_{n−1} − 2 < k < f_{n}, then (C_{k}(F_{n}))^{3} ⊀ F_{∞};

6) For any u ≺ F_{∞}, u^{4} ⊀ F_{∞}.

Proof. 1) It follows from the properties 1.5) and 2.6), w_{n}^{2} ⊀ F_{∞}; 2) Let C_{k}(F_{n}) = uv with F_{n} = vu. Then u ▷ F_{n} and v ◁ F_{n}. Since

(C_{k}(F_{n}))^{2} = uvuv = uF_{n}v ≺ (F_{n})^{3},

the conclusion (C_{k}(F_{n}))^{2} ≺ F_{∞} will follow from F_{n}^{3} ≺ F_{∞}.

3) Suppose that w_{k} be the largest singular word contained in u as in corollary 5, and let u = v_{1}w_{k}v_{2}. Assume that u^{2} = v_{1}w_{k}v_{2}v_{1}w_{k}v_{2} ≺ F_{∞}, then w_{k} ⊀ v_{2}v_{1}, otherwise by theorem 2 we shall have either w_{k+1} ≺ v_{1}, or w_{k+1} ≺ v_{2}, that will be in contradiction with the hypothesis of w_{k}. Thus two singular words of the order k above are adjacent, so by theorem 2 again, v_{2}v_{1} must be either w_{k+1} or w_{k−1}. By property 2.5), u will be either a conjugation of F_{k+2}, or of F_{k+1}. But these two cases are impossible because of the hypothesis of u.

4) Since aaba ≺ f_{∞}, so dose F_{n}F_{n}F_{n−1}F_{n}. Let αβ ▷ F_{n−1}, then by lemma 1, we have

F_{n}^{2}F_{n−1}F_{n} = F_{n}^{2}F_{n−1}F_{n−2}F_{n−1}α^{−1}β^{−1}αβ = F_{n}^{3}F_{n−1}α^{−1}β^{−1}αβ ≺ F_{∞},

notice that F_{n−1} ◁ F_{n}, hence if 0 ≤ k ≤ f_{n−1} − 2, then

(C_{k}(F_{n}))^{3} ≺ F_{n}^{3}F_{n−1}α^{−1}β^{−1} ≺ F_{∞}.

5) Now suppose that f_{n−1} − 1 < k < f_{n}, then by property 2.5), w_{n−1} ≺ C_{k}(F_{n}). Let C_{k}(F_{n}) = uw_{n−1}v, then vu = w_{n−2}, thus

(C_{k}(F_{n}))^{3} = uw_{n−1}w_{n−2}w_{n−1}w_{n−2}w_{n−1}v.

Hence if (C_{k}(F_{n}))^{3} ≺ F_{∞}, then the word w_{n−1}w_{n−2}w_{n−1} = w_{n+1} will have overlap, but by corollary 5, this is impossible.

6) The conclusion follows from an analogous argument with 5).

Remark 2 ¿From theorem 3.2), we see that, any conjugation of F_{n}, n ≥ 0, is not separated positively. This is an important difference between the conjugations of F_{n} and w_{n}.

Example 2. Local isomorphism

Let u = u_{1}u_{2} ⋯ u_{n} ⋯ and v = v_{1}v_{2} ⋯ v_{n} ⋯ be two infinite words over the alphabet {a, b}. We say that u and v are locally isomorphic if any factor (or its mirror image) of u is also factor of v and vice versa (By the property 1.7), for the Fibonacci word, we don’t need to consider mirror images of the factors). If u and v are locally isomorphic, we shall write u ≃ v. The notion of local isomorphism is very useful in the studies of the energy spectra of one-dimensional quasicrystals [12].

For an infinite word u = u_{1}u_{2} ⋯ u_{n} ⋯, we define the translation T (u) of u by T u = u_{2}u_{3} ⋯ and define T^{k} = T (T^{k−1}) by recurrence. By using the properties of the singular words of the Fibonacci word, we can easily obtain the following results of the local isomorphism of the Fibonacci word.

Theorem 4 We have

1) If we change a finite number of letters of F_{∞}, then the obtained infinite word F′_{∞} is not locally isomorphic to F_{∞}.

2) Let u ∈ A^{∗}, then F_{∞} ≃ uF_{∞} if and only if there exists m > −1, such that u ▷ w_{m}w_{m}^{∗}, where w_{m}^{∗} is defined as in property 2.12).

3) For any k ≥ 1, T^{k}(F_{∞}) ≃ F_{∞}.

Proof. 1) Let F_{∞} = ∏_{j=−1}^{∞} as in theorem 1, because we only change a finite

number of letters of F_{∞}, we can find an integer m and words u, v ∈ A^{∗}, such that

F′_{∞} = uv ∏_{j=m}^{∞} w_{j},

where |v| = f_{m−1}, v ≠ w_{m−1}. Therefore by corollary 3, vw_{m} ⊀ F_{∞}, that is F_{∞} ≄ F′_{∞}.

2) From theorem 1 and property 2.12), for any k > 0 and m ≥ 0,

w_{2m}aF_{∞} = w_{2m}a ( ∏_{j=−1}^{2m+2k−1} w_{j}) ( ∏_{j=2m+2k}^{∞} w_{j}) = w_{2m}w_{2m+2k+1} ( ∏_{j=2m+2k}^{∞} w_{j}) ,

then, by corollary 3, w_{2m}w_{2m+2k+1} ≺ F_{∞}, that is, for any v ≺ w_{2m}aF_{∞}, we can find an integer k, such that v ≺ w_{2m}w_{2m+2k+1}, so v ≺ F_{∞}. The case of w_{2m+1}b can be proved in the same way. That is, if u ▷ w_{m}w_{m}^{∗} for some m, then F_{∞} ≃ uF_{∞}. If u is not a right factor of any w_{m}w_{m}^{∗}, then by the discussion similar that of 1), we see that uF_{∞} ≄ F_{∞}.

3) The proof follows from the property 1.6).

Example 3. Study of special words of F_{∞}

Berstel [2] introduced the special words of F_{∞} as follows: if ua, ub ≺ F_{∞}, then the word u is called a special word of F_{∞}. The following theorem is due to Berstel [2] which we shall give another proof by using singular word.

Theorem 5 A word w ≺ F_{∞} is a special word if and only if, for some n ≥ 0, w ▷ \overline{F_{n}}.

Proof. It is easily checked that, for any n ≥ 0, \overline{F_{n}} is a special word, therefore the theorem is reduced to show that, for any n ≥ 0, |Ω_{n}| = n + 1.

Now let u ≺ F_{∞} and let f_{k} < |u| ≤ f_{k+1}. By an analogous argument with that for lemma 2, it is readily to see that the word u must be one of the three following forms:

• u = sw_{n}t, |st| ≤ f_{n−1};

• u = sF_{n}t, s, t ≠ ε, |st| ≤ f_{n−1}, s ▷ F_{n}, t ◁ F_{n};

• u = st, s ▷ F_{n}, t ◁ F_{n}.

In the first case, by corollary 3, the factor s ▷ w_{n−1}, (resp. t) are determined uniquely. Moreover, since w_{n} has no overlap, if s ≠ s′, then sw_{n}t ≠ s′w_{n}t′. Hence there are exactly |u| − f_{k} + 1 different words sw_{n}t which correspond with |s| = 0, 1, …, n − f_{k}.

In the two later cases, from property 1.1), it is readily to prove that there are exactly f_{k} different factors of length |u| of F_{k}^{3}.

Summarize the discussions above, we get |Ω_{|u|}| = f_{k}+(|u|−f_{k}+1) = |u|+1.

Example 4. Overlap of the subwords of the Fibonacci word

In this example, we shall determine the factors which have overlap.

Recall that: Let u ≺ F_{∞}, if there exist words x, y and z such that u = xy = yz and û(y) := uz = xyz ≺ F_{∞}. Then we shall say that the word u has overlap with the overlap factor y (or overlap length |y|), the word û(y) is called the overlap of u with the overlap factor y. We denote by O(F_{∞}) = O the set of factors having overlap.

Evidently, if u ∈ O, we have

|u| + 1 ≤ |û(y)| ≤ 2|u| − 1,  (∗)

where y is any overlap factor of u.

Lemma 6 Let f_{n} < |u| ≤ f_{n+1}, and let u ≠ w_{n+1}, then u ∈ O if and only if w_{n} ⊀ u.

Proof. Let w_{n} ≺ u and write u = sw_{n}t. If u ∈ O, notice that w_{n} ∉ O, thus overlap of u must be of the form sw_{n}vw_{n}t. By corollary 4,

|sw_{n}vw_{n}t| ≥ |s| + |t| + 2f_{n} + f_{n−1} = |u| + f_{n+1} ≥ 2|u|,

which is in contradiction with the inequality (∗).

Now suppose that w_{n} ⊀ u, then discuss as in theorem 5, we have either

• u = sF_{n}t, where s, t ≠ ε, |s| + |t| ≤ f_{n−1}, s ▷ F_{n}, t ◁ F_{n};

• or u ≺ F_{n}^{2}.

In the first case, if |t| = f_{n} − 1, then u = w_{n+1} ∉ O. Now consider |t| < f_{n} − 1. Since |s| + |t| ≤ f_{n−1}, s ▷ F_{n}, t ◁ F_{n}, we can write F_{n} = txs. Since |t| < f_{n} − 1, by theorem 3.4),

(C_{|t|}(F_{n}))^{3} = (xst)^{3} = xstxstxst ≺ F_{∞},

that is, u = sF_{n}t = stxst has overlap with factor st.

In the second case, notice that u ≺ F_{n}^{2} and |u| > f_{n}, so if we write u = st, with |t| = f_{n}, then t = C_{k}(F_{n}) for some k, and s ▷ t, thus u = sxs. On the other hand, since u = sC_{k}(F_{n}) ≺ F_{n}^{2}, so sxsxs = s(C_{k}(F_{n}))^{2} ≺ F_{n}^{3} ≺ F_{∞}, that is u = sxs has overlap with overlap factor s.

Lemma 7 If u ∈ O, then the overlap of u is unique.

Proof. Let f_{n} < |u| ≤ f_{n+1}, and let w be the largest singular word contained in u. By corollary 6, w is one of w_{n−1}, w_{n} and w_{n+1}. Since u ∈ O, w must be w_{n−1} from lemma 6, so we can write u = sw_{n−1}t. Now suppose that there are two different overlaps of u, then w_{n−1} will appear three times in one of these two overlaps. Since w_{n−1} ∉ O, this overlap must be of the form sw_{n−1}v_{1}w_{n−1}v_{2}w_{n−1}t, then by an analogous argument with lemma 6, we shall get a contradiction of (∗).

¿From lemma 7 and the proof of the lemma 6, we obtain immediately

Corollary 6 Let f_{n} < |u| ≤ f_{n+1}, and let u ∈ O, then u = vv′v, where |v| is the overlap length.

Summarize the results above, we have

Theorem 6 Let f_{n} < |u| ≤ f_{n+1} and let u ≠ w_{n+1}, u ≺ F_{∞}, then u ∈ O if and only if w_{n} ⊀ u. If u ∈ O, then the overlap of u is unique and u = vv′v, where v is the factor of overlap and |v| = |u| − f_{n}.

In particular, C_{k}(F_{n}) ∈ O if and only if 0 ≤ k ≤ f_{n} − 2.

Note that:

i) f_{n+1} < 2f_{n} < f_{n+2} < 3f_{n} < f_{n+3}; ii) for any k, w_{n+1} ⊀ (C_{k}(F_{n}))^{2}; iii) for any k, w_{n+2} ⊀ (C_{k}(F_{n}))^{3}. We get immediately from theorem 6

Corollary 7 For any k, (C_{k}(F_{n}))^{2} ∈ O, (C_{k}(F_{n}))^{3} ∈ O.

Remark 3 If w^{2} ⊀ F_{∞} and w has no overlap, then the adjacent words of w will be positively separate. Moreover we can prove that for these words, there is a decomposition similar to the singular words.

Let w = abab, by theorem 3.3) and theorem 6, w^{2} ≺ F_{∞} and w ∉ O, so w is separated positively. the following decomposition illustrates the remark above:

aba(abab)\underline{aaba}(abab)\underline{a}(abab)\underline{aaba}(abab)\underline{aaba}(abab)\underline{a}(abab)\underline{aaba}(abab)\underline{a}(abab) ⋯

Acknowledgement The second author is grateful to J. Peyrière for interesting discussions when he visited ORSAY and to T. Janssen for his kind helps. This work was supported partially by NSFC of China for WZX and by the Dutch Stichting Fundamenteel Onderzoek der Materie (FOM) for WZY.

References

[1] J.-P. Allouche, Arithmétique et automate finis, Asthérisque, 147-148 (1987) 13–26.

[2] J. Berstel, Mot de Fibonacci, Séminaire d’informatique théorique, L. I. T. P., Paris, Année (1980/1981) 57–78.

[3] E. Bombieri and J. E. Taylor, Which distribution of matter diffract? An initial investigation, J. Physique, 47 (1987) 19–28.

[4] A. de Luca, A combinatorial properly of the Fibonacci words, Inform. Process. Lett., 12, n^{∘} 4 (1981) 193–195.

[5] J. Karhumäki, On the cube-free ω-words generated by binary morphism, Discr. Appl. Math. 5 (1983) 279–297.

[6] F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word, Infor. Théor. et Appl. vol. 26, n^{∘} 3 (1992) 199–204.

[7] J. Peyrière, Z.-Y. Wen et Z.-X. Wen, Polynômes associés aux endomorphismes de groupes libres, L’Enseignement Mathématique, t. 39:153–175 (1993).

[8] M. Queffélec, Substitution dynamical systems-spectral analysis, Lecture Notes in Math. 1294., 1987, Springer-Verlag.

[9] P. Séébold, Propriétés combinatoire des mots infinis engendré par certains morphism, Thèse de doctorat, Rapp. Tec. L. I. T. P., 85-14 (1985).

[10] P. Séébold, Fibonacci morphisms and sturmian words, Theor. Comput. Sci, 88 (1991) 365–384.

[11] Z. Y. Wen and Z. X. Wen, The sequences of substitution and related topics, Adv. Math. (China), (1989) 123–145.

[12] F. Wijnands, Energy spectra and local isomorphism for one-dimensional quasiperiodic potentials, J. Phys. A: Math. Gen. 22 (1989) 3267–3282.