## subwords of the fibonacci word

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.

-
Some additional info: the Fibonacci word is not cube-free. For example, it contains the subword "10010 10010 10010". (Another comment: perhaps someone should make a "combinatorics-on-words" tag.) – Joel Reyes Noche Apr 4 2011 at 6:14
According to oeis.org/A003849, the first 24 terms are "010010100 10010 10010 10010". But the 10th to 24th terms are a cube. – Joel Reyes Noche Apr 4 2011 at 6:35
A list of the first 1652 subwords by T.D. Noe (according to oeis.org/A003849) can be found at oeis.org/A003849/a003849.txt – Joel Reyes Noche Apr 4 2011 at 6:51
@Joel: You are right. Was it $n+3$ instead of $n+2$. I guess I did not remember correctly. – Mark Sapir Apr 4 2011 at 7:20
@Mark. Thanks for the references and info. – Joel Reyes Noche Apr 4 2011 at 7:45

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

-
A proof that the Fibonacci word's subword complexity is p_f(n)=n+1 can be found in Section 10.5 of Allouche and Shallit's Automatic Sequences (2003, Cambridge University Press). – Joel Reyes Noche Apr 4 2011 at 6:24

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

-

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

-