Question

The Fibonacci word is the limit of the sequence of words starting with "0" and satisfying rules $0 \to 01, 1 \to 0$. It's equivalent to have initial conditions $S_0 = 0, S_1 = 01$ and then recursion $S_n= S_{n-1}S_{n-2}$.

I want to know what words cannot appear as subwords in the limit $S_\infty$. At first I thought 000 and 11 were the only two that could not appear. Then I noticed 010101. Is there any characterization of which words can or cannot appear as subwords of the Fibonacci word?

Loosely related, this word appears as the cut sequence of the line of slope $\phi = (1 + \sqrt{5})/2$ though the origin.

Answer 1

The Fibonacci word is one of the Sturmian words, so its complexity is $n+1$, that is the number of different subwords of length $n$ is $n+1$. So most words are not subwords of the Fibonacci word. There are, as far as I remember 12 different but equivalent definitions of Sturmian words. Some of them give restrictions on possible subwords (see Algebraic combinatorics on words by Lothaire, and an article by Berstel there).

Answer 2

The easiest way (linear-time, computationally speaking) to determine whether a finite word $w$ is a factor (a subword) of the Fibonacci word $S_\infty$ is the following:

• Remove a trailing 0 from $w$, if present (just one); if $w$ begins with 1, add a leading 0;
• The word thus obtained should be uniquely parsed with (written as a concatenation of) 0 and 01; if not, then $w$ is not a factor of $S_\infty$ and you are done. If $w=x_1x_2\cdots x_k$ is such a parsing, let $y_i=0$ for all $i$ such that $x_i=01$, and $y_i=1$ otherwise (that is, if $x_i=0$).
• Apply the same algorithm on the new word $w'=y_1\cdots y_k$
• The original $w$ is a factor of $S_\infty$ if and only if you eventually reach the word 0 or 1 by recursively applying the above procedure.

Correctness can be easily proved, as the Fibonacci word is the limit of the substitution $0\to 01$, $1\to 0$ (folklore, see e.g. Lothaire's Algebraic combinatorics on words). For instance, $w=1010010010100$ is a factor since the sequence of words generated by the above algorithm is: $$w,\: 00101001,\: 10010,\: 010,\: 0\;.$$

If you need a more dynamical point of view, Sturmian shifts (such as Fibonacci) are neither of finite type nor sofic. However, it is not hard to get the list of minimal forbidden factors of the Fibonacci word, as follows. Let $S_i'$ be the $i$-th palindromic prefix of $S_\infty$, which you can obtain by removing the last two characters in $S_i$. Then a finite word $w$ is a factor of the Fibonacci word if and only if it does not contain any of the following as factors, for all $k\geq 1$: $$1S_{2k-1}'1,\quad 0S_{2k}'0\;.$$ In other terms, the sequence of minimal forbidden factors is 11, 000, 10101, 00100100, 1010010100101, … See for instance Mignosi et al., Words and forbidden factors

Answer 3

I don't know if there is a simple characterization, but it seems there is a simple algorithm. See Bartosz Walczak, A simple representation of subwords of the Fibonacci word, available at http://tcs.uj.edu.pl/~walczak/fibonacci.pdf