most recent 30 from http://mathoverflow.net 2013-05-24T03:30:18Z http://mathoverflow.net/feeds/question/88773 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/88773/branches-of-the-fibonacci-word-tree John Mangual 2012-02-17T21:33:33Z 2012-10-28T12:04:06Z

<p>The <a href="http://en.wikipedia.org/wiki/Fibonacci_word" rel="nofollow">Fibonacci word</a> 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 <a href="http://en.wikipedia.org/wiki/Penrose_tiling" rel="nofollow">Penrose Tiling</a>.</p> <p>...1010110101101101011010110110101101101011010110110101101...</p> <p><img src="http://upload.wikimedia.org/wikipedia/commons/2/2d/Fibonacci_word_cutting_sequence.png" width="500"></p> <p>The Fibonacci word is has minimal complexity above a periodic word -- there are <strong>n+1</strong> subwords of length <strong>n</strong>, making it a <a href="http://en.wikipedia.org/wiki/Sturmian_word" rel="nofollow">Sturmian word</a>. </p> <ul> <li><strong>5</strong> subwords of length <strong>4</strong>: "0101", "0110", "1010", "1011", "1101"</li> <li><strong>8</strong> subwords of length <strong>7</strong>: "0101101", "0110101", "0110110", "1010110", "1011010", "1011011", "1101011", "1101101"</li> </ul> <p>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.</p> <p>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.</p> <p><strong>What is the structure of this tree? Is there any regularity to the location of the branches?</strong></p> <p>The complement of the tree becomes a tesselation of the Euclidean plane by "ribbon $\infty$-ominos", which is amusing.</p> <pre><code>.-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 </code></pre>

http://mathoverflow.net/questions/88773/branches-of-the-fibonacci-word-tree/88819#88819 Urban 2012-02-18T09:49:55Z 2012-02-18T09:49:55Z

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

http://mathoverflow.net/questions/88773/branches-of-the-fibonacci-word-tree/88901#88901 Nathaniel Shar 2012-02-19T06:39:33Z 2012-02-19T19:26:18Z

<p>The answer to the question "Is there any regularity to the location of the branches?" appears to be yes. Here is <a href="http://math.rutgers.edu/~nbs48/fibonacci-word-tree/fib500.png" rel="nofollow">a diagram of the first 500 branches</a> (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.</p> <p>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> <p><img src="http://math.rutgers.edu/~nbs48/fibonacci-word-tree/fib500.png" width="300"/></p> <p>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.</p>

http://mathoverflow.net/questions/88773/branches-of-the-fibonacci-word-tree/89068#89068 Joseph O'Rourke 2012-02-21T02:08:11Z 2012-02-21T02:08:11Z

<p>I was having difficulty seeing Nathaniel Shar's (interesting!) pattern. This might be easier to interpret: <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/fib500.gif" alt="fib500 inverted"><br /> (I thought it too intrusive to add this directly to his answer.)</p>