## 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 2012 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 at 13:02

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 2012 at 12:56
Hi Johan, I hope I will earn overflow votes on my own merits soon :) – Urban Feb 19 2012 at 16:05
en.wikipedia.org/wiki/File:Helianthus_whorl.jpg – Urban Mar 2 2012 at 17:09
en.wikipedia.org/wiki/File:SunflowerModel.svg – Urban Mar 2 2012 at 17:11
The flower petals within the sunflower's cluster are in a spiral pattern similar to this one. – Urban Mar 2 2012 at 17:21

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 2012 at 7:15
that's really terrific. i would love to talk more about this – John Mangual Feb 19 2012 at 16:44

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

-