I am currently reading a text where it is proved that the infinite Fibonacci Word $u$ defined as the limit of the sequence $$ u_n = \varphi^n(0) $$ where the morphism is given by $\varphi(0) = 01, \varphi(1) = 0$ is Sturmian, meaning for each $n$ there exists exactly one factor $u$ such that $u0$ and $u1$ are both factors of the word (such factors are called right special). Further the Fibonacci word is the unique fixed point of the morphism when extended to infinite words.

Now the proof goes like this ($F(f)$ denotes the set of factors of $f$))

We show that the Fibonacci word $$ f = 0100101001001010010100100101001001\ldots $$ defined in Chapter 1 is Sturmian. It will be convenient, in this chapter, to start the numeration of finite Fibonacci words differently, and to set $f_{-1} = 1, f_0 = 0$. Since $f = \varphi(f)$, it is a product of words $01$ and $0$. Thus the word $11$ is not a factor of $f$ and consequently $P(f,2) = 3$. The word $000$ is not a factor of $\varphi(f)$, since otherwise it is a prefix of some $\varphi(x)$ for a factor $x$ of $f$, and $x$ has to start with $11$. To show that $f$ is Sturmian, we prove that $f$ has exactly one right special factor of each length. We start by showing that, for no word $x$, both $0x0$ and $1x1$ are factors of $f$. This is clear if $x$ is the empty word and if $x$ is a single letter. Arguing by induction on the length, assume that $0x0$ and $1x1$ are in $F(f)$. Then $x$ starts and ends with $0$, and $x = 0y0$ for some $y$. Since $00y00$ and $10y01$ have to be factors of $\varphi(f)$, there exists a factor $z$ of $f$ such that $\varphi(z) = 0y$. Moreover, $00y0 = \varphi(1z1)$ and $010y01 = \varphi(0z0)$, showing that $1z1$ and $0z0$ are factors of $f$. This is a contradiction because $|z| \le |\varphi(z)| < |x|$. (and so on...)

I am not sure about the boldfaced part. Is it in general true that for an infinite word $w$ and a morphism, if $u = \varphi(v)$ where $u$ is some factor of $w$ we can conclude that $v$ is a factor of $w$? I am not sure, but maybe there is some property used about the Fibonacci word, can someone please explain the reasoning behind the boldfaced part?


1 Answer 1


Basically what is being used is that $\varphi$ is injective: if $\varphi(x) = \varphi(y)$ then $x = y$. From this it follows that given any factor of $f$, we can deduce the "break points" it has where it factors into images of different letters of $f$. For example $00100$ must factor like $(0)(01)(0)t$ where $t$ is either $0$ or $01$. So $00100$ in $f$ must arise as the image under $\varphi$ of $101u$ for some letter $u$.

Start with $00y00$ being a factor of $f = \varphi(f)$. Since it starts with a $0$, this $0$ can only arise as the image of $1$ under $\varphi$. On the other hand, it ends with $00$, which can only arise as the image of $10$ or $11$ under $\varphi$. It now follows that $0y$ has to be the image of some $z$, and so $00y00$ must arise as the image of $1z10$ or $1z11$ under $\varphi$.

Similar reasoning applies to $10y01$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .