# Branches of the Fibonacci Word Tree

The Fibonacci word starts from $0$ subject to the rules $0 \mapsto 1, 1 \mapsto 01$ (or some variant thereof). The come from cutting sequences of the torus of a line of golden ratio slope. It is a 1D version of the Penrose Tiling.

...1010110101101101011010110110101101101011010110110101101...

The Fibonacci word is has minimal complexity above a periodic word -- there are n+1 subwords of length n, making it a Sturmian word.

• 5 subwords of length 4: "0101", "0110", "1010", "1011", "1101"
• 8 subwords of length 7: "0101101", "0110101", "0110110", "1010110", "1011010", "1011011", "1101011", "1101101"

As an experiment, I sorted the subwords of length n alphabetically The words are arranged in an infinite tree, where each word is descendant of its subword.

As a shorthand, I only placed the last letter of each word on each diagonal. Edges represent inclusion... drawn so any path from the top left corner "." appears in the Fibonacci word. Each Fibonacci subword corresponds to a path.

What is the structure of this tree? Is there any regularity to the location of the branches?

The complement of the tree becomes a tesselation of the Euclidean plane by "ribbon $\infty$-ominos", which is amusing.

.-1-1-0-1-1-0-1-0-1-1-0
| |     |
0 0-1-1 0-1-1-0-1-1-0
|   | |         |
1-1 0 0-1-1-0-1 0-1
| | |   |     |
0 0 1-1 0-1-1 0-1
| |   |     |
1 1-1 0-1-1 0-1
| | |     |
1 0 0-1-1 0-1
| |   | |
0 1-1 0 1-1
|   | |
1-1 0 1-1
| | |
0 0 1-1
| | |
1 1 0
| |
1 0
|
0

-
The Fibonacci shift is not sofic so your tree is not rational (i.e.it has infinitely many cone types). – Benjamin Steinberg Feb 21 '12 at 2:23
The picture in the question seems not to match the text's description of the Fibonacci word. For example, the picture will never have two consecutive 1's whereas the text will never produce two consecutive 0's. Should I just imagine 0's and 1's interchanged in the picture, or is something more complicated going on? – Andreas Blass Oct 28 '12 at 13:02

The answer to the question "Is there any regularity to the location of the branches?" appears to be yes. Here is a diagram of the first 500 branches (a black pixel denotes a branch, and a white pixel denotes no branch, with the root in the upper-left-hand corner just like in your diagram). The regularity is apparent. You might need to zoom in if the pixels are too small.

Of course, I say "appears to be" because I haven't yet proved that the pattern continues, or even described precisely what the pattern is.

P.S.: I would have left this as a comment, since I doubt it qualifies as a full "answer", but apparently I need more reputation to do that. My apologies.

-
No need to apologize! An answer doesn't have to be complete. – Johan Wästlund Feb 19 '12 at 7:15
that's really terrific. i would love to talk more about this – john mangual Feb 19 '12 at 16:44

This is interesting. Do you have a reference to "thin ∞-ominos"?

-
Hi Urban, I was considering voting this up to enable you to leave comments, but perhaps that wouldn't be entirely correct, in particular since I strongly suspect I might be your thesis advisor:) – Johan Wästlund Feb 18 '12 at 12:56
Hi Johan, I hope I will earn overflow votes on my own merits soon :) – Urban Feb 19 '12 at 16:05
The flower petals within the sunflower's cluster are in a spiral pattern similar to this one. – Urban Mar 2 '12 at 17:21

I was having difficulty seeing Nathaniel Shar's (interesting!) pattern. This might be easier to interpret:

(I thought it too intrusive to add this directly to his answer.)

-