17
$\begingroup$

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
Improve this question
$\endgroup$
3
  • $\begingroup$ This is interesting. Do you have a reference to "thin ∞-ominos"? $\endgroup$
    – Urban
    Feb 18, 2012 at 9:49
  • $\begingroup$ The Fibonacci shift is not sofic so your tree is not rational (i.e.it has infinitely many cone types). $\endgroup$
    – Benjamin Steinberg
    Feb 21, 2012 at 2:23
  • $\begingroup$ 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? $\endgroup$
    – Andreas Blass
    Oct 28, 2012 at 13:02

2 Answers 2

Reset to default
13
$\begingroup$

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.

Fibonnacci word tree

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.

Improve this answer
$\endgroup$
4
  • 6
    $\begingroup$ No need to apologize! An answer doesn't have to be complete. $\endgroup$
    – Johan Wästlund
    Feb 19, 2012 at 7:15
  • $\begingroup$ that's really terrific. i would love to talk more about this $\endgroup$
    – john mangual
    Feb 19, 2012 at 16:44
  • $\begingroup$ Presumably because of a dead link, I see a blank box in this answer where a picture would go. $\endgroup$
    – Ian Morris
    May 4, 2017 at 11:55
  • $\begingroup$ @IanMorris The link should work now. $\endgroup$
    – Martin Sleziak
    May 4, 2017 at 15:38
3
$\begingroup$

I was having difficulty seeing Nathaniel Shar's (interesting!) pattern. This might be easier to interpret:
      fib500 inverted
(I thought it too intrusive to add this directly to his answer.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.