\documentstyle[12pt]{article}

\setlength{\textheight}{21.5cm}
\setlength{\textwidth}{14cm}
\evensidemargin 11mm%.4cm
\oddsidemargin 11mm%.4cm
\setlength{\topmargin}{-.7cm}
\headsep 0.3cm
\topmargin 0pt
%\oddsidemargin 0pt
%\evensidemargin 0pt
%\textheight 22 true cm
%\textwidth 15 true cm
%\nofiles
\pagestyle{plain}

\def\eps{{\varepsilon}}
\def\ul{\underline}
\def\N{\mbox{I}\!\mbox{N}}

\begin{document}
%\maketitle
%\load{\normalsize}{\boldmath}
\def\prf{{\bf Proof.\ \ }}
\def\dps{\displaystyle}
\newtheorem{lem}{Lemma}
\newtheorem{th}{Theorem}
\newtheorem{rem}{Remark}
\newtheorem{cor}{Corollary}
\newtheorem{pty}{Property}

\baselineskip=13pt

\begin{center}
{\bf\Large Some Properties of the singular words of the Fibonacci word} 
\end{center}

\begin{center}
{\footnotesize \baselineskip=10pt
WEN Zhi-Xiong 
\footnote{Department of Physics, Wuhan University, Wuhan 430072 (P. R. China)} 
and WEN Zhi-Ying \footnote
{Institute for Theoretical Physics, University of Nimegen, 
Toernooiveld 6525 ED Nimegen, The Netherlands and Department of Mathematics, 
Wuhan University, Wuhan 430072 (P. R. China)}
}
\end{center}

\begin{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.
\end{abstract}

\bigskip

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 \cite{1,3,7,8,10}. Moreover, the properties of the subwords of the
Fibonacci infinite word have been studied extensively by many authors 
\cite{2,4,5,6,8,9}. 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.
\bigskip

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).
\bigskip

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 $\eps$. 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)$.

An infinite word on $A$ is a mapping 
${\mbox{\boldmath $x$}}: \N\longrightarrow A$,
and we write ${\mbox{\boldmath $x$}}=x_1x_2\cdots x_n\cdots$, where $x_i\in A$.
The set of infinite words is denoted by $A^\omega$.

A word $v$ is a factor of word $w$ and we write $v\prec w$, if there exist
$u,u'\in A^*$, such that $w=uvu'$. We say that $v$ is a left (resp. right)
factor of a word $w$ and we note that $v\triangleleft w$ (resp.
$v\triangleright w$), if there exists $u\in A^*$ such that $w=vu$ (resp. 
$w=uv$). The notions of left factors and right factors are extended in a 
natural way to $A^\omega$.

Let $w=x_1x_2\cdots x_n$. We denote by $\overline w$ the mirror image of $w$;
that is, $\overline w=x_n\cdots x_2x_1$. If $w=\overline w$, the word will be
called a palindrome, and the set of the palindromes is denoted by $\cal P$.
A word $w\in A^*$ is called primitive if $u=v^p,\ v\in A^*,\ p>0$, implies
$u=v$.

Let $w=x_1x_2\cdots x_n\in A^*$, and let $1\le k\le n$. We define 
$C_k(w)=x_{k+1}\cdots x_nx_1\cdots x_k$, the $k$-th conjugation of the word 
$w$, and we note that $C(w)=\{C_k(w);\ 1\le k\le|w|\}$. By convention,
$C_{-k}(w)=C_{|w|-k}(w)$.

Now let $\sigma: A\longrightarrow A^*$ be a morphism defined by $\sigma(a)=ab$,
$\sigma(b)=a$. We define the $n$-th iteration of $\sigma$ by 
$\sigma^n(a)=\sigma(\sigma^{n-1}),\ n\ge 2$ and we denote $F_n=\sigma^n(a)$
(by convention, we define
$\sigma^0(a)=a$, $\sigma^0(b)=b$). Then the Fibonacci word $F_\infty$ is
obtained by iterating $\sigma$ with the letter $a$ (see \cite{2}).

Let $w$ be a word. We denote by $\Omega_n(w)$ the set of factors of $w$ of
length $n$, where $|w|\ge n$, and we simply note that
$\Omega_n:=\Omega_n(F_\infty)$.

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 \cite{12} and therein).
Let $w=x_1x_2\cdots x_n\in A^*$. We denote by $w^{-1}$ the inverse word of
$w$, that is $w^{-1}=x_n^{-1}\cdots x_2^{-1}x_1^{-1}$. Let $w=uv$, 
$u,v\in A^*$, then $wv^{-1}:=u$ and $u^{-1}w:=v$ by convention.
\bigskip

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
$$\ul{a}\,\ul{b}\,\ul{aa}\,\ul{bab}\,\ul{aabaa}\,\ul{babaabab}\,
\ul{aabaababaabaa}\,\ul{babaababaabaababaabab}\,\cdots$$
that is, the length of the $n$-th block in the decomposition is $f_n$,
$n\ge -1$. Then a question is posed naturally: What are these blocks?
As we shall see, Theorem 1 will answer this question completely.
\bigskip

In this note, we shall use the following known facts which can be found in
\cite{2,4,7,8}.

\begin{pty}\label{pty1}
1) $|\sigma^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\in C(F_n)$, we have
$$L(w)=L(F_n)=(f_{n-1},f_{n-2}),$$
and moreover,
$$C(F_n)=\{\overline w;\ w\in C(F_n)\}.$$
2) $F_{n+1}=F_{n}F_{n-1}$.\\
3) For any $k\ge 1$, $\sigma^k(F_\infty)=F_\infty$, that is
$$F_\infty=F_kF_{k-1}F_kF_kF_{k-1}\cdots.$$
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\not\prec F_\infty,\ a^3\not\prec F_\infty$.\\ 
6) Any factor of $F_\infty$ will appear infinitely many times in $F_\infty$.\\
7) $w\prec F_\infty$ if and only if $\overline w\prec F_\infty$.
\end{pty}

\begin{rem}\label{rem1}
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.
\end{rem}

Let $\alpha$ and $\beta$ be two words.
Note that, by Property 1.4), if $\alpha\beta\triangleright F_n$, then
$\alpha\not=\beta$.

\begin{lem}\label{lem1}
Let $n\ge 2$, and assume that $\alpha\beta$ is a suffix of $F_n$. Then
\begin{eqnarray*}
F_n&=&F_{n-2}F_{n-1}\alpha^{-1}\beta^{-1}\alpha\beta,\\
F_{n-2}F_{n-1}&=&F_n\beta^{-1}\alpha^{-1}\beta\alpha.
\end{eqnarray*}
\end{lem}
\prf Note that $\alpha\beta\triangleright F_n$, so 
$\beta\alpha\triangleright 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
\begin{eqnarray*}
F_{n+1}&=&F_nF_{n-1}=F_{n-1}F_{n-2}F_{n-1}
=F_{n-1}F_{n}\alpha^{-1}\beta^{-1}\alpha\beta,\\
F_{n-1}F_{n}&=&F_{n-1}F_{n-2}F_{n-1}\beta^{-1}\alpha^{-1}\beta\alpha
=F_{n+1}\beta^{-1}\alpha^{-1}\beta\alpha.
\end{eqnarray*}
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\triangleright F_n$, $v\triangleleft F_n$ and 
$|v|\le f_{n-2}$, then $w\prec F_{n}F_{n-1}F_{n-2}=F_{n}F_{n}$. On the 
other hand, evidently, $F_nF_{n-1}\prec 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), $\Omega_{f_n}(F_nF_n)=C(F_n)$.
Therefore it is sufficient to determine the factors of $F_{n-1}F_{n}$.
\bigskip

Let $\alpha$ and $\beta$ be two words such that $\alpha\beta$ is a suffix of
$F_n$. We denote the word $\alpha F_n\beta^{-1}$ by $w_n$.

\begin{lem}\label{lem2}
We have the following:\\
1) $w_n\not\in C(F_n)$;\\
2) $\Omega_{f_n}(F_{n-1}F_n)=w_n\bigcup\{C_k(F_n);\ 0\le k\le f_{n-2}-2\}$.
In particular, as a factor, $w_n$ appears only once in $F_{n-1}F_n$.
\end{lem}
\prf 1) Since $\alpha\not=\beta,\ L(w_n)\not=L(F_n)$, which yields 1).\\
2) By Lemma 1: if $\alpha\beta\triangleright F_n$, then we have
$f_{n-1}F_n=F_{n}F_{n-1}\alpha^{-1}\beta^{-1}\alpha\beta$. Since 
$F_{n-1}\triangleleft 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\le k\le f_{n-1}-2$,
and the last factor is $F_n=C_{f_n}(F_n)$, the $(f_{n-1}-1)$-th factor is
$\alpha F_n\beta^{-1}=w_n$.
\bigskip

As we have seen, for any $n\ge 1$, the set $\Omega_{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_\infty$.

The word $w_n$ is called the $n$-th singular word of the Fibonacci word
$F_\infty$. For convenience, we define $w_{-2}=\eps$, $w_{-1}=a$ and
$w_{0}=b$, and we denote by $\cal S$ the set of singular words of $F_\infty$.

Now we discuss the properties of the singular words:

\begin{pty}\label{pty2}We have the following:\\
1) If $n\ge 1$, then
$$L(w_n)=\left\{\begin{array}{ll}
(f_{n-1}+1,f_{n-2}-1)&\mbox{if $n$ is odd;}\\
(f_{n-1}-1,f_{n-2}+1)&\mbox{if $n$ is even.} \end{array}
\right.$$
2) $w_n\not\prec w_{n+1}$.\\
3) If $\alpha\triangleright w_{n+1}$, then 
$w_{n+2}=w_{n}w_{n+1}\alpha^{-1}\beta$.\\
4) $w_{n}=w_{n-2}w_{n-3}w_{n-2},\ n\ge 1$.\\
5) For $n\ge 1$,
\begin{eqnarray*}
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};
\end{eqnarray*}
In particular, 
\begin{eqnarray*}
w_{n-2}\prec C_k(F_n)&\mbox{if and only if}&0\le k\le f_{n-1}-1;\\
w_{n-1}\prec C_k(F_n)&\mbox{if and only if}&f_{n-1}-1\le k\le f_{n}-1.
\end{eqnarray*}
6) For $n\ge 1$, $w_{2n-1}=aauaa,\ w_{2n}=bvb$, where $u,v\in A^*$.\\
7) For $n\ge 2,\ 1<k<f_n$, no proper conjugate of $w_n$ is a subword of 
$F_{\infty}$.\\
8) For $n\ge 0,\ w_n^2\not\prec F_{\infty}$.\\
9) For $n\ge -1$, $w_n$ is a palindrome.\\
10) $w_n$ is not the product of two palindromes for $n\ge 2$.\\
11) If $n\ge 2$, then $w_n$ is primitive.\\
12) For $n\ge 1$, we have
$$w_n=w^*_n\left(\prod_{j=-1}^{n-2}w_j\right)
=\left(\prod_{j=-1}^{n-2}w_{n-j-3}\right)w_n^*,
{\mbox {where }}w_n^*=\left\{\begin{array}{ll}
a& {\mbox{if $n$ is odd}},\\
b& {\mbox{if $n$ is even}};\end{array}\right.$$
13) $w_n\not\prec\dps\prod_{j=-1}^{n-1}w_j$;\\
14) Let $k\ge -1$ and $p\ge 1$, and let $u=\dps\prod_{j=k}^{k+p}w_j$. Then
$u\not\in \cal S$.
\end{pty} 
\prf 1) If $n$ is odd, then $a\triangleright F_{n-1},\ b\triangleright F_n$.
Thus 
$$L(w_n)=L(aF_nb^{-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 $\alpha\triangleright F_n$: then $\beta\triangleright F_{n+1}$.
By the definition of $w_n$, it is easi to see that $w_n\not\prec F_{n+1}$,
so $w_n\not\prec F_{n+1}\beta^{-1}$. On the other hand
$w_n=\beta F_{n}\alpha^{-1}\not=\alpha F_{n}\beta^{-1}$. Since
$w_{n+1}=\alpha F_{n+1}\alpha^{-1}$, thus $w_n\not\prec w_{n+1}$.\\
3) By definition, $w_{n+2}=\beta F_{n}\alpha^{-1}$. Then by Lemma 1, we have
$$w_{n+2}=\beta F_nF_{n+1}\beta^{-1}\alpha^{-1}\beta
=w_nw_{n+1}\alpha^{-1}\beta.$$
4) Let $\alpha\triangleright F_n$: then $\alpha\triangleright F_{n-2}$
and $\beta\triangleright F_{n+1}$, $\beta\triangleright F_{n-1}$. Thus
\begin{eqnarray*}
w_{n+1}&=&\alpha F_{n+1}\beta^{-1}=\alpha F_{n-1}F_{n-2}F_{n-1}\beta^{-1}\\
&=&(\alpha F_{n-1}\beta^{-1})
(\beta F_{n-2}\alpha^{-1})(\alpha F_{n-1}\beta^{-1})\\
&=&w_{n-1}w_{n-2}w_{n-1}.
\end{eqnarray*}
%where $\alpha\triangleright F_{n}$, thus $\alpha\triangleright F_{n-2}$
%and $\beta\triangleright F_{n+1}$, $\beta\triangleright F_{n-1}$.\\
5) Let $\alpha\triangleright F_n$: then 
$$F_n=F_{n-1}F_{n-2}=(F_{n-1}\alpha^{-1})(\alpha F_{n-2}\beta^{-1})\beta,$$
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\le 2$. Now suppose that the conclusion is true for $k\le 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}\in\cal P$.\\
10) Let $w_n=uv$, where $u,v\in\cal 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_\infty$.
Then, by 6), if $n\ge 2$, we have $a^4\prec F_\infty$, or $b^2\prec F_\infty$,
which will contradict Property 1.5).\\
11) Let $w_n=u^p$, with $u\in A^*$, and $p\ge 2$. Since $w_n\in\cal 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_0F_1\cdots F_{n-3}F_{n-2}$. If $n$
is odd, then $b\triangleright F_n$. Therefore 
\begin{eqnarray*}
w_{n}&=&a F_{n}b^{-1}=aab(aF_{1}b^{-1})(bF_2a^{-1})\cdots
(bF_{n-3}a^{-1})(aF_{n-2}b^{-1})\\
&=&aw_{-1}w_0w_{1}\cdots w_{n-3}w_{n-2},
\end{eqnarray*}
and the case of $n$ being even may be proved in the same manner.\\
13) If $w_n\prec\dps\prod_{j=-1}^{n-1}w_j$, then by 12), 
$w_n\prec w_n^*\dps\prod_{j=-1}^{n-1}w_j=w_{n+1}$, 
which will contradict 2).\\
14) Assume that $u=\dps\prod_{j=k}^{k+p}w_j=w_m$ for some $m\ge 0$.
Since $w_{k+p}$ is a factor, $m>k+p$. On the other hand, by 12),
$w_m\prec w_{k+p}^*\dps\prod_{j=-1}^{k+p}w_j=w_{k+p+2}$, so $m=k+p+1$.
By 13), this is impossible.
\bigskip

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

\begin{th}\label{th1}
$F_\infty=\dps\prod_{j=-1}^{\infty} w_j$.
\end{th}
\prf The proof is similar that of Property 2.12).
\bigskip

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

\begin{lem}\label{lem3}
Let $w_nw_{n+1}=u_1u_2u_3$ (or $w_{n+1}w_{n}=u_1u_2u_3$) with 
$0<|u_1|<f_n$ and $0<|u_3|<f_{n+1}$, then $u_2\not\in \cal S$.
\end{lem}
\prf i) By the condition of the lemma, $2<|u_2|<f_{n+2}-2$, 
so $u_2\not=w_{n+2}$.

ii) Let $\alpha\triangleright F_n$, then 
$w_nw_{n+1}=\beta F_nF_{n-1}\beta^{-1}$. By Lemma 2, 
$w_{n+1}=\alpha F_{n+1}\beta^{-1}$ appears only once in $F_nF_{n+1}$. Note
that $|u_3|\ge 1$, we obtain $u_2\not=w_{n+1}$.

iii) Let $|u_2|=f_n$ and $F_{n+1}=F_nF_{n-1}$, $u_2\prec F_nF_n$. But by
lemma 2, $w_n\not\prec F_nF_n$, and thus $u_2\not=w_n$.

iv) Let $|u_2|=f_{n-1}$. Since $w_nw_{n+1}=w_nw_{n-1}w_{n-2}w_{n-1}$,
then we must have $u_2\prec\alpha F_nF_{n-1}\alpha^{-1}$. 
By using lemma 2, a discussion as in ii) yields $u_2\not=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\ge 1,\ u_2\not=w_k$, that is,
$u_2\not\in\cal S$.
\bigskip

Now let $n\ge 0$ be fixed. We define a substitution 
$\phi_n:A\longrightarrow A^*$ by $\phi_n(a)=w_{n+1}$, $\phi_n(b)=w_{n-1}$. 
Let $\Sigma_n=\{w_{n+1}, w_{n-1}\}$. For a singular word $w_k$, 
we say $W_k(\Sigma_n):=\phi_n(w_k)$ (if there is no confusion,
we simply write $W_k$), the $k$-th singular word over $\Sigma_n$.

\begin{lem}\label{lem4}
Let $n\ge 0$ and $k\ge 1$. Then we have 
\begin{eqnarray*}
w_{n+2k}&=&w_nx_1w_{n}x_2\cdots w_nx_{f_{2k-2}}w_n,\\
w_{2k+1}&=&y_1w_ny_2w_{n}\cdots y_{f_{2k-1}-1}w_ny_{f_{2k-1}},
\end{eqnarray*}
where $x_j,y_j\in\Sigma_n$. Moreover,
$$ x_1x_2\cdots x_{f_{2k-2}}=W_{2k-2}\mbox{ and }
y_1y_2\cdots y_{f_{2k-1}}=W_{2k-1}$$
are, respectively, the 
$(2k-2)$-th and $(2k-1)$-th singular words over $\Sigma_n$.
\end{lem}
\prf For any fixed $n$, we prove the lemma by induction. We have, by 
Property 2.4),
\begin{eqnarray*}
w_{n+2}&=&w_nw_{n-1}w_{n},\\
w_{n+3}&=&w_{n+1}w_{n}w_{n+1},\\
w_{n+4}&=&w_nw_{n-1}w_{n}w_{n+1}w_nw_{n-1}w_{n},\\
w_{n+5}&=&w_{n+1}w_nw_{n+1}w_{n}w_{n-1}w_nw_{n+1}w_nw_{n+1},
\end{eqnarray*}
and hence the conclusion is true for $k=1,2$. Now suppose that the conclusion 
is true for $k-1$ and $k$. Then
\begin{eqnarray*}
w_{n+2(k+1)}&=&w_{n+2k}w_{n+2k-1}w_{n+2k}\\
&=&w_nx_1\cdots w_{n}x_{f_{2k-2}}w_ny_1w_n\cdots 
w_ny_{f_{2k-3}}w_n\cdots w_nx_{f_{2k-2}},
\end{eqnarray*}
since $x_1x_2\cdots x_{f_{2k-2}}$ and $y_1y_2\cdots y_{f_{2k-3}}$ are,
respectively, the $(2k-2)$-th and $(2k-3)$-th singular words $W_{2k-2}$
and $W_{2k-3}$ on $\Sigma_n$ by the assumption of the induction. So, by 
Property 2.4),
$$x_1x_2\cdots x_{f_{2k-2}}y_1y_2\cdots y_{f_{2k-3}}x_1x_2\cdots 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}$.
\bigskip
>From Lemmas 3 and 4, we immediately obtain the following.

\begin{cor}\label{cor1}
Let $m\ge 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.
\end{cor}
\bigskip

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

\begin{lem}\label{lem5}
Let $F_\infty=\dps\prod_{j=-1}^\infty 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\ge n$.
\end{lem}
\prf i) From Property 2.13), $w_n\not\prec\dps\prod_{j=-1}^{n-1}w_j$.

ii) If $u\prec\dps\prod_{j=-1}^{n}w_j$, then by Property 2.12),
$$u\prec\left(w_{n-1}^*\prod_{j=-1}^{n-1}w_j\right)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\prec\dps\prod_{j=n}^{\infty}w_j$.
Since $|u|=|w_n|$, there exists $m$, $m\ge n$, such that, either
$u\prec w_m$, or $u\prec w_mw_{m+1}$ with $u\not\prec w_n$ and 
$u\not\prec w_{n+1}$. But by lemma 3, the later case is impossible.

We thus finish the proof from the discussions above.
\bigskip

Now we can state our main result of this note.

\begin{th}\label{th2}
For any $n\ge 0$, we have
$$F_\infty=\left(\prod_{j=-1}^{n-1}w_j\right)w_{n,1}z_1w_{n,2}z_2
\cdots w_{n,k}z_kw_{n,k+1}\cdots$$
where $\mbox{{\boldmath $z$}}=z_1z_2\cdots z_n\cdots$ is the Fibonacci 
word over $\Sigma_n$.
\end{th}
\prf From theorem 1 and lemma 4, we get
\begin{eqnarray*}
F_\infty&=&\left(\prod_{j=-1}^{n-1}w_j\right)w_nw_{n+1}
\left(\prod_{j=n+2}^{\infty}w_j\right)\\
&=&\left(\prod_{j=-1}^{n-1}w_j\right)w_nw_{n+1}
(w_nw_{n-1}w_n)(w_{n+1}w_nw_{n+1})\cdots\\
&&(w_nx_1w_n\cdots x_{f_{2k-2}}w_n)(y_1w_ny_2\cdots w_ny_{f_{2k-1}})\cdots
\end{eqnarray*}
Note that\\
i) by lemma 4, lemma 5 and corollary 1, all factor $w_n$ of $F_\infty$ (or the 
sequence $w_{n,k}$, $k\ge 1$) appear in the formula above;\\
ii) by lemma 4, 
\begin{eqnarray*}
x_1\cdots x_{f_{2k-2}}&=&W_{2k-2},\\
y_1\cdots y_{f_{2k-1}}&=&W_{2k-1},
\end{eqnarray*}
thus $\dps\prod_{j=1}^{\infty}z_j=\prod_{j=-1}^{\infty}W_j$ is the 
Fibonacci word on $\Sigma_n$.

i) and ii) follow the theorem.
\bigskip

The following example illustrates the decomposition of $F_\infty$ of the words
$w_1,\ w_2$:
\medskip

\centerline{$\scriptstyle abaa(bab)\ul{aabaa}(bab)\ul{aa}(bab)\ul{aabaa}(bab)\ul{aabaa}(bab)
\ul{aa}(bab)\ul{aabaa}(bab)\ul{aa}(bab)\ul{aabaa}\cdots$} 
\bigskip

Let ${\mbox{\boldmath $y$}}=y_1y_2\cdots y_n\cdots$ be an infinite word over 
$\{a,b\}$. Let $u,v\prec{\mbox{\boldmath $y$}}$, $u=y_ky_{k+1}\cdots y_{k+p}$ 
and $v=y_{l}y_{l+1}\cdots y_{l+m}$, where $l\ge k$, then the distance of the 
words $u$ and $v$ define by
$$d(u,v)=\left\{\begin{array}{ll}
l-k-p&{\mbox {if }}l> k-p;\\
0    &{\mbox {otherwise}}.\end{array}\right.$$

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

The theorem 2 has the following direct consequences:

\begin{cor}\label{cor2}
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})\in\{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}$.
\end{cor}

\begin{cor}\label{cor3}
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}$.
\end{cor}
\bigskip

Let $w=x_kx_{k+1}\cdots x_{k+p}$ ($k,p\ge 1$) be a factor of $F_\infty$.
If there is an integer $l$, $1\le l\le p$, such that 
$w=x_{k+l}x_{k+l+1}\cdots 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\prec F_\infty$, if there exist words $x,y$ and
$z$ such that $u=xy=yz$ and $u(y):=uz=xyz\prec F_\infty$. From corollary 2,
we obtain immediately

\begin{cor}\label{cor4}
For $n\ge 1$, $w_n$ has no overlap.
\end{cor}

\begin{cor}\label{cor5}
Let $u\prec F_\infty$ and let $f_n<|u|\le 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}$.
\end{cor}
\prf 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'\prec u$
(or $w'vw\prec 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).
\bigskip

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.

\section*{\normalsize{\bf Example 1. Power of the factors.} \rm \cite{2,5,6,8}}

\begin{th}\label{th3}
We have\\
1) For any $n,\ w_n^2\not\prec F_\infty$;\\
2) For $0\le k\le f_{n}-1,\ \big(C_k(F_n)\big)^2\prec F_\infty$;\\
3) If $u\prec F_\infty$ with $f_{n-1}<|u|<f_n$, then $u^2\not\prec F_\infty$;\\
4) If $0\le k\le f_{n-1}-2$, then $\big(C_k(F_n)\big)^3\prec F_\infty$;\\
5) If $f_{n-1}-2<k<f_n$, then $\big(C_k(F_n)\big)^3\not\prec F_\infty$;\\
6) For any $u\prec F_\infty,\ u^4\not\prec F_\infty$.
\end{th}
\prf 1) It follows from the properties 1.5) and 2.6), 
$w_n^2\not\prec F_\infty$;

2) Let $C_k(F_n)=uv$ with $F_n=vu$. Then $u\triangleright F_n$ and
$v\triangleleft F_n$. Since 
$$\big(C_k(F_n)\big)^2=uvuv=uF_nv\prec(F_n)^3,$$
the conclusion $\big(C_k(F_n)\big)^2\prec F_\infty$ will follow from 
$F_n^3\prec F_\infty$.

3) Suppose that $w_k$ be the largest singular word contained in $u$ as in
corollary 5, and let $u=v_1w_kv_2$. Assume that 
$u^2=v_1w_kv_2v_1w_kv_2\prec F_\infty$, then $w_k\not\prec v_2v_1$, otherwise
by theorem 2 we shall have either $w_{k+1}\prec v_1$, or $w_{k+1}\prec 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_2v_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\prec f_\infty$, so dose $F_nF_nF_{n-1}F_n$. Let 
$\alpha\beta\triangleright F_{n-1}$, then by lemma 1, we have
$$F_n^2F_{n-1}F_{n}=F_n^2F_{n-1}F_{n-2}F_{n-1}\alpha^{-1}\beta^{-1}\alpha\beta
=F_n^3F_{n-1}\alpha^{-1}\beta^{-1}\alpha\beta\prec F_\infty,$$
notice that $F_{n-1}\triangleleft F_n$, hence if $0\le k\le f_{n-1}-2$, then
$$\big(C_k(F_n)\big)^3\prec F_n^3F_{n-1}\alpha^{-1}\beta^{-1}\prec F_\infty.$$

5) Now suppose that $f_{n-1}-1<k<f_n$, then by property 2.5), 
$w_{n-1}\prec C_k(F_n)$. Let $C_k(F_n)=uw_{n-1}v$, then $vu=w_{n-2}$, thus
$$\big(C_k(F_n)\big)^3=uw_{n-1}w_{n-2}w_{n-1}w_{n-2}w_{n-1}v.$$
Hence if $\big(C_k(F_n)\big)^3\prec F_\infty$, 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).

\begin{rem}\label{rem2}
>From theorem 3.2), we see that, any conjugation of $F_n,\ n\ge 0$, is not 
separated positively. This is an important difference between the
conjugations of $F_n$ and $w_n$.
\end{rem}

\section*{\normalsize\bf Example 2. Local isomorphism}

Let $u=u_1u_2\cdots u_n\cdots$ and $v=v_1v_2\cdots v_n\cdots$ 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\simeq v$. The 
notion of local isomorphism is very useful in the studies of the energy
spectra of one-dimensional quasicrystals \cite{11}.

For an infinite word $u=u_1u_2\cdots u_n\cdots$, we define the translation 
$T(u)$ of $u$ by $Tu=u_2u_3\cdots$ 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.

\begin{th}\label{th4}
We have\\
1) If we change a finite number of letters of $F_\infty$, then the obtained
infinite word $F_{\infty}'$ is not locally isomorphic to $F_\infty$.\\
2) Let $u\in A^*$, then $F_\infty\simeq uF_\infty$ if and only if there
exists $m>-1$, such that $u\triangleright w_mw_m^*$, where $w_m^*$ is defined
as in property 2.12).\\
3) For any $k\ge 1$, $T^k(F_\infty)\simeq F_\infty$.
\end{th}
\prf 1) Let $F_\infty=\dps\prod_{j=-1}^{\infty}$ as in theorem 1, because we
only change a finite number of letters of $F_\infty$, we can find an integer
$m$ and words $u,v\in A^*$, such that
$$F'_\infty =uv\prod_{j=m}^{\infty}w_j,$$
where $|v|=f_{m-1},\ v\not=w_{m-1}$. Therefore by corollary 3, 
$vw_m\not\prec F_\infty$, that is $F_\infty\not\simeq F'_\infty$.

2) From theorem 1 and property 2.12), for any $k>0$ and $m\ge 0$,
$$w_{2m}aF_\infty=w_{2m}a\left(\prod_{j=-1}^{2m+2k-1}w_j\right)
\left(\prod_{j=2m+2k}^{\infty}w_j\right)
=w_{2m}w_{2m+2k+1}\left(\prod_{j=2m+2k}^{\infty}w_j\right),$$
then, by corollary 3, $w_{2m}w_{2m+2k+1}\prec F_\infty$, that is, for any
$v\prec w_{2m}aF_\infty$, we can find an integer $k$, such that 
$v\prec w_{2m}w_{2m+2k+1}$, so $v\prec F_\infty$. The case of $w_{2m+1}b$
can be proved in the same way. That is, if $u\triangleright w_mw_m^*$ for
some $m$, then $F_\infty\simeq uF_\infty$. If $u$ is not a right factor
of any $w_mw_m^*$, then by the discussion similar that of 1), we see that
$uF_\infty\not\simeq F_\infty$.

3) The proof follows from the property 1.6).

\section*{\normalsize\bf Example 3. Study of special words of $F_\infty$}

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

\begin{th}\label{th5}
A word $w\prec F_\infty$ is a special word if and only if, for some $n\ge 0$,
$w\triangleright \overline{F_n}$.
\end{th}
\prf It is easily checked that, for any $n\ge 0$, $\overline{F_n}$ is a 
special word, therefore the theorem is reduced to show that, for any $n\ge 0$,
$|\Omega_n|=n+1$.

Now let $u\prec F_\infty$ and let $f_k<|u|\le 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: 
\begin{itemize}
\item $u=sw_nt,\ |st|\le f_{n-1}$;
\item $u=sF_nt,\ s,t\not=\eps,\ |st|\le f_{n-1},\ 
s\triangleright F_n,\ t\triangleleft F_n$;
\item $u=st,\ s\triangleright F_n,\ t\triangleleft F_n$.
\end{itemize}
In the first case, by corollary 3, the factor $s\triangleright w_{n-1}$,
(resp. $t$) are determined uniquely. Moreover, since $w_n$ has no overlap,
if $s\not=s'$, then $sw_nt\not=s'w_nt'$. Hence there are
exactly $|u|-f_k+1$ different words $sw_nt$ which correspond
with $|s|=0,1,\ldots,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 
$|\Omega_{|u|}|=f_k+(|u|-f_k+1)=|u|+1$.

\section*{\normalsize\bf 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\prec F_\infty$, if there exist words $x,y$ and $z$ such
that $u=xy=yz$ and $\hat u(y):=uz=xyz\prec F_\infty$. Then we shall say that
the word $u$ has overlap with the overlap factor $y$ (or overlap length $|y|$),
the word $\hat u(y)$ is called the overlap of $u$ with the overlap factor $y$.
We denote by $\cal O(\cal F_\infty)=\cal O$ the set of factors having overlap.

Evidently, if $u\in\cal O$, we have
$$|u|+1\le |\hat u(y)|\le 2|u|-1, \eqno{(*)}$$
where $y$ is any overlap factor of $u$.

\begin{lem}\label{lem6}
Let $f_n<|u|\le f_{n+1}$, and let $u\not=w_{n+1}$, then $u\in\cal O$ 
if and only if $w_n\not\prec u$.
\end{lem}
\prf Let $w_n\prec u$ and write $u=sw_nt$. If $u\in\cal O$, notice that 
$w_n\not\in\cal O$, thus overlap of $u$ must be of the form $sw_nvw_nt$.
By corollary 4,
$$|sw_nvw_nt|\ge |s|+|t|+2f_{n}+f_{n-1}=|u|+f_{n+1}\ge 2|u|,$$
which is in contradiction with the inequality $(*)$.

Now suppose that $w_n\not\prec u$, then discuss as in theorem 5, we have
either 
\begin{itemize}
\item $u=sF_nt$, where $s,t\not=\eps$, $|s|+|t|\le f_{n-1}$, 
$s\triangleright F_n$, $t\triangleleft F_n$; 
\item or $u\prec F_n^2$.
\end{itemize}
In the first case, if $|t|=f_n-1$, then $u=w_{n+1}\not\in\cal O$. Now consider
$|t|<f_n-1$. Since $|s|+|t|\le f_{n-1}$, 
$s\triangleright F_n$, $t\triangleleft F_n$, we can write $F_n=txs$.
Since $|t|<f_n-1$, by theorem 3.4),
$$\big(C_{|t|}(F_n)\big)^3=(xst)^3=xstxstxst\prec F_\infty,$$
that is, $u=sF_nt=stxst$ has overlap with factor $st$.

In the second case, notice that $u\prec 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\triangleright t$, thus $u=sxs$. On the other hand, since 
$u=sC_k(F_n)\prec F_n^2$, so 
$sxsxs=s\big(C_k(F_n)\big)^2\prec F_n^3\prec F_\infty$, that is $u=sxs$
has overlap with overlap factor $s$.

\begin{lem}\label{lem7}
If $u\in\cal O$, then the overlap of $u$ is unique.
\end{lem}
\prf Let $f_n<|u|\le f_{n+1}$, and let $w$ be the largest singular word
contained in $u$. By corollary \ref{cor6}, $w$ is one of $w_{n-1}$, $w_n$
and $w_{n+1}$. Since $u\in\cal O$, $w$ must be $w_{n-1}$ from lemma \ref{lem6},
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}\not\in\cal O$, this overlap must be of the form 
$sw_{n-1}v_1w_{n-1}v_2w_{n-1}t$, then by an analogous argument with 
lemma \ref{lem6}, we shall get a contradiction of $(*)$.
\bigskip

>From lemma \ref{lem7} and the proof of the lemma \ref{lem6}, we obtain
immediately

\begin{cor}\label{cor6}
Let $f_n<|u|\le f_{n+1}$, and let $u\in \cal O$, then $u=vv'v$, where
$|v|$ is the overlap length.
\end{cor}
\bigskip

Summarize the results above, we have

\begin{th}\label{th6}
Let $f_n<|u|\le f_{n+1}$ and let $u\not=w_{n+1},\ u\prec F_\infty$, then
$u\in\cal O$ if and only if $w_n\not\prec u$. If
$u\in\cal 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)\in\cal O$ if and only if $0\le k\le f_n-2$.
\end{th}
\bigskip

Note that:\\
i) $f_{n+1}<2f_n<f_{n+2}<3f_n<f_{n+3}$;\\
ii) for any $k$, $w_{n+1}\not\prec\big(C_k(F_n)\big)^2$;\\
iii) for any $k$, $w_{n+2}\not\prec\big(C_k(F_n)\big)^3$.\\
We get immediately from theorem \ref{th6}

\begin{cor}\label{cor7}
For any $k,\ \big(C_k(F_n)\big)^2\in\cal O$, $\big(C_k(F_n)\big)^3\in\cal O$.
\end{cor}

\begin{rem}
If $w^2\not\prec F_\infty$ 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.
\end{rem}

Let $w=abab$, by theorem \ref{th3}.3) and theorem \ref{th6}, 
$w^2\prec F_\infty$ and $w\not\in\cal O$, so $w$ is separated positively. the
following decomposition illustrates the remark above:
$$aba(abab)\ul{aaba}(abab)\ul{a}(abab)\ul{aaba}(abab)\ul{aaba}(abab)
\ul{a}(abab)\ul{aaba}(abab)\ul{a}(abab)\cdots$$

\bigskip
\baselineskip=13pt
{\bf Acknowledgement} The second author is grateful to J. Peyri\`ere
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.

\begin{thebibliography}{10}
\bibitem{1} J.-P. Allouche, {\em Arithm\'etique et automate finis},
Asth\'erisque, 147-148 (1987) 13--26.

\bibitem{2} J. Berstel, {\em Mot de Fibonacci}, 
S\'{e}minaire d'informatique th\'{e}orique,
L. I. T. P., Paris, Ann\'{e}e (1980/1981) 57--78.

\bibitem{3} E. Bombieri and J. E. Taylor,
{\em Which distribution of matter diffract? An initial investigation},
J. Physique, 47 (1987) 19--28.

\bibitem{4} A. de Luca, {\em A combinatorial properly of the Fibonacci words},
Inform. Process. Lett., 12, n$^\circ$ 4 (1981) 193--195.

\bibitem{5} J. Karhum\"aki,
{\em On the cube-free $\omega$-words generated by binary morphism},
Discr. Appl. Math. 5 (1983) 279--297.

\bibitem{6} F. Mignosi and G. Pirillo,
{\em Repetitions in the Fibonacci infinite word},
Infor. Th\'eor. et Appl. vol. 26, n$^\circ$ 3 (1992) 199--204.

\bibitem{12} J. Peyri\`ere, Z.-Y. Wen et Z.-X. Wen, 
Polyn\^omes associ\'es aux endomorphismes de groupes libres, 
L'Enseignement Math\'ematique, t. 39:153--175 (1993).

\bibitem{7} M. Queff\'{e}lec, 
{\em Substitution dynamical systems-spectral analysis,} 
Lecture Notes in Math. 1294., 1987, Springer-Verlag.

\bibitem{8} P. S\'e\'ebold, 
{\em Propri\'et\'es combinatoire des mots infinis engendr\'e par certains
morphism}, Th\`ese de doctorat, Rapp. Tec. L. I. T. P., 85-14 (1985).

\bibitem{9} P. S\'{e}\'{e}bold, {\em Fibonacci morphisms and sturmian words},
Theor. Comput. Sci, 88 (1991) 365--384.

\bibitem{10} Z. Y. Wen and Z. X. Wen, 
{\em The sequences of substitution and related topics},
Adv. Math. (China), (1989) 123--145.

\bibitem{11} F. Wijnands, {\em Energy spectra and local isomorphism for 
one-dimensional quasiperiodic potentials},
J. Phys. A: Math. Gen. 22 (1989) 3267--3282.

\end{thebibliography}


\end{document}

