Fibonacci word fractal

<h2 id="definition">Definition</h2>

<p>This curve is built iteratively by applying the Odd–Even Drawing rule to the <a href="/facts/Fibonacci_word/DfhEMX8P">Fibonacci word</a> 0100101001001...:
</p><p>For each digit at position <i>k</i>:
</p>
<ol><li>If the digit is 0:
<ul><li>Draw a line segment then turn 90° to the left if <i>k</i> is <a href="/facts/Parity_(mathematics)/7zq2UM4V">even</a></li>
<li>Draw a line segment then Turn 90° to the right if <i>k</i> is <a href="/facts/Parity_(mathematics)/7zq2UM4V">odd</a></li></ul></li>
<li>If the digit is 1:
<ul><li>Draw a line segment and stay straight</li></ul></li></ol>
<p>To a Fibonacci word of length 
  
    
      
        
          F
          
            n
          
        
      
    
    {\displaystyle F_{n}}
  
 (the <i>n</i>th <a href="/facts/Fibonacci_number/mqxpAUQD">Fibonacci number</a>) is associated a curve 
  
    
      
        
          
            
              F
            
          
          
            n
          
        
      
    
    {\displaystyle {\mathcal {F}}_{n}}
  
 made of 
  
    
      
        
          F
          
            n
          
        
      
    
    {\displaystyle F_{n}}
  
 segments. The curve displays three different aspects whether <i>n</i> is in the form 3<i>k</i>, 3<i>k</i> + 1, or 3<i>k</i> + 2.
</p>
<h2 id="properties">Properties</h2>

<p>Some of the Fibonacci word fractal's properties include:<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>
<ul><li>The curve 
  
    
      
        
          
            
              F
              
                n
              
            
          
        
      
    
    {\displaystyle {\mathcal {F_{n}}}}
  
 contains 
  
    
      
        
          F
          
            n
          
        
      
    
    {\displaystyle F_{n}}
  
 segments, 
  
    
      
        
          F
          
            n
            −
            1
          
        
      
    
    {\displaystyle F_{n-1}}
  
 right angles and 
  
    
      
        
          F
          
            n
            −
            2
          
        
      
    
    {\displaystyle F_{n-2}}
  
 flat angles.</li>
<li>The curve never self-intersects and does not contain double points. At the limit, it contains an infinity of points asymptotically close.</li>
<li>The curve presents self-similarities at all scales. The reduction ratio is 
  
    
      
        1
        +
        
          
            2
          
        
      
    
    {\displaystyle 1+{\sqrt {2}}}
  
. This number, also called the <a href="/facts/Silver_ratio/EwKW66Er">silver ratio</a>, is present in a great number of properties listed below.</li>
<li>The number of self-similarities at level <i>n</i> is a <a href="/facts/Fibonacci_number/mqxpAUQD">Fibonacci number</a> \ −1. (more precisely: 
  
    
      
        
          F
          
            3
            n
            +
            3
          
        
        −
        1
      
    
    {\displaystyle F_{3n+3}-1}
  
).</li>
<li>The curve encloses an infinity of square structures of decreasing sizes in a ratio 
  
    
      
        1
        +
        
          
            2
          
        
      
    
    {\displaystyle 1+{\sqrt {2}}}
  
 (see figure). The number of those square structures is a Fibonacci number.</li>
<li>The curve 
  
    
      
        
          
            
              F
            
          
          
            n
          
        
      
    
    {\displaystyle {\mathcal {F}}_{n}}
  
can also be constructed in different ways (see gallery below):
<ul><li><a href="/facts/Iterated_function_system/j56g6yEM">Iterated function system</a>  of 4 and 1 homothety of ratio 
  
    
      
        1
        
          /
        
        (
        1
        +
        
          
            2
          
        
        )
      
    
    {\displaystyle 1/(1+{\sqrt {2}})}
  
 and 
  
    
      
        1
        
          /
        
        (
        1
        +
        
          
            2
          
        
        
          )
          
            2
          
        
      
    
    {\displaystyle 1/(1+{\sqrt {2}})^{2}}
  
</li>
<li>By joining together the curves 
  
    
      
        
          
            
              F
            
          
          
            n
            −
            1
          
        
      
    
    {\displaystyle {\mathcal {F}}_{n-1}}
  
 and 
  
    
      
        
          
            
              F
            
          
          
            n
            −
            2
          
        
      
    
    {\displaystyle {\mathcal {F}}_{n-2}}
  
</li>
<li><a href="/facts/L-system/SGfQ416R">Lindenmayer system</a></li>
<li>By an iterated construction of 8 square patterns around each square pattern.</li>
<li>By an iterated construction of <a href="/facts/Octagon/H5PuP3wP">octagons</a></li></ul></li>
<li>The <a href="/facts/Hausdorff_dimension/rtX9ryrp">Hausdorff dimension</a> of the Fibonacci word fractal is 
  
    
      
        3
        
        
          
            
              log
              ⁡
              φ
            
            
              log
              ⁡
              (
              1
              +
              
                
                  2
                
              
              )
            
          
        
        ≈
        1.6379
      
    
    {\displaystyle 3\,{\frac {\log \varphi }{\log(1+{\sqrt {2}})}}\approx 1.6379}
  
, with 
  
    
      
        φ
        =
        
          
            
              1
              +
              
                
                  5
                
              
            
            2
          
        
      
    
    {\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}
  
 the <a href="/facts/Golden_ratio/anloSRmD">golden ratio</a>.</li>
<li>Generalizing to an angle 
  
    
      
        α
      
    
    {\displaystyle \alpha }
  
 between 0 and 
  
    
      
        π
        
          /
        
        2
      
    
    {\displaystyle \pi /2}
  
, its Hausdorff dimension is 
  
    
      
        3
        
        
          
            
              log
              ⁡
              φ
            
            
              log
              ⁡
              (
              1
              +
              a
              +
              
                
                  (
                  1
                  +
                  a
                  
                    )
                    
                      2
                    
                  
                  +
                  1
                
              
              )
            
          
        
      
    
    {\displaystyle 3\,{\frac {\log \varphi }{\log(1+a+{\sqrt {(1+a)^{2}+1}})}}}
  
, with 
  
    
      
        a
        =
        cos
        ⁡
        α
      
    
    {\displaystyle a=\cos \alpha }
  
.</li>
<li>The Hausdorff dimension of its frontier is 
  
    
      
        
          
            
              log
              ⁡
              3
            
            
              
                log
                ⁡
                (
                1
                +
                
                  
                    2
                  
                
              
              )
            
          
        
        ≈
        1.2465
      
    
    {\displaystyle {\frac {\log 3}{{\log(1+{\sqrt {2}}})}}\approx 1.2465}
  
.</li>
<li>Exchanging the roles of "0" and "1" in the Fibonacci word, or in the drawing rule yields a similar curve, but oriented 45°.</li>
<li>From the Fibonacci word, one can define the «dense Fibonacci word», on an alphabet of 3 letters: 102210221102110211022102211021102110221022102211021... (sequence A143667 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>). The usage, on this word, of a more simple drawing rule, defines an infinite set of variants of the curve, among which:
<ul><li>a "diagonal variant"</li>
<li>a "svastika variant"</li>
<li>a "compact variant"</li></ul></li>
<li>It is <a href="/facts/Conjecture/oPWUb7SF">conjectured</a> that the Fibonacci word fractal appears for every <a href="/facts/Sturmian_word/tbwHJPb6">sturmian word</a> for which the slope, written in <a href="/facts/Continued_fraction/Wg1cMPxN">continued fraction expansion</a>, ends with an infinite sequence of "1"s.</li></ul>
<h2 id="gallery">Gallery</h2>

<h2 id="the-fibonacci-tile">The Fibonacci tile</h2>

<p>The juxtaposition of four 
  
    
      
        
          F
          
            3
            k
          
        
      
    
    {\displaystyle F_{3k}}
  
 curves allows the construction of a closed curve enclosing a surface whose <a href="/facts/Area/KsNG1G9t">area</a> is not null. This curve is called a "Fibonacci tile".
</p>
<ul><li>The Fibonacci tile almost tiles the plane. The juxtaposition of 4 tiles (see illustration) leaves at the center a free square whose area tends to zero as <i>k</i> tends to infinity. At the limit, the infinite Fibonacci tile tiles the plane.</li>
<li>If the tile is enclosed in a square of side 1, then its area tends to 
  
    
      
        2
        −
        
          
            2
          
        
        =
        0.5857
      
    
    {\displaystyle 2-{\sqrt {2}}=0.5857}
  
.</li></ul>

<h3>Fibonacci snowflake</h3>

<p>The Fibonacci snowflake is a Fibonacci tile defined by:<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<ul><li>
  
    
      
        
          q
          
            n
          
        
        =
        
          q
          
            n
            −
            1
          
        
        
          q
          
            n
            −
            2
          
        
      
    
    {\displaystyle q_{n}=q_{n-1}q_{n-2}}
  
 if 
  
    
      
        n
        ≡
        2
        
          
          (
          mod
          
          3
          )
        
      
    
    {\displaystyle n\equiv 2{\pmod {3}}}
  
</li>
<li>
  
    
      
        
          q
          
            n
          
        
        =
        
          q
          
            n
            −
            1
          
        
        
          
            
              q
              ¯
            
          
          
            n
            −
            2
          
        
      
    
    {\displaystyle q_{n}=q_{n-1}{\overline {q}}_{n-2}}
  
 otherwise.</li></ul>
<p>with 
  
    
      
        
          q
          
            0
          
        
        =
        ϵ
      
    
    {\displaystyle q_{0}=\epsilon }
  
 and 
  
    
      
        
          q
          
            1
          
        
        =
        R
      
    
    {\displaystyle q_{1}=R}
  
, 
  
    
      
        L
        =
      
    
    {\displaystyle L=}
  
 "turn left" and 
  
    
      
        R
        =
      
    
    {\displaystyle R=}
  
 "turn right", and 
  
    
      
        
          
            R
            ¯
          
        
        =
        L
      
    
    {\displaystyle {\overline {R}}=L}
  
.
</p><p>Several remarkable properties:<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
<ul><li>It is the Fibonacci tile associated to the "diagonal variant" previously defined.</li>
<li>It tiles the plane at any order.</li>
<li>It tiles the plane by translation in two different ways.</li>
<li>its <a href="/facts/Perimeter/yQv1AajA">perimeter</a> at order <i>n</i> equals 
  
    
      
        4
        F
        (
        3
        n
        +
        1
        )
      
    
    {\displaystyle 4F(3n+1)}
  
, where 
  
    
      
        F
        (
        n
        )
      
    
    {\displaystyle F(n)}
  
 is the <i>n</i>th <a href="/facts/Fibonacci_number/mqxpAUQD">Fibonacci number</a>.</li>
<li>its area at order <i>n</i> follows the successive indexes of odd row of the <a href="/facts/Pell_number/VMu7fXmx">Pell sequence</a> (defined by 
  
    
      
        P
        (
        n
        )
        =
        2
        P
        (
        n
        −
        1
        )
        +
        P
        (
        n
        −
        2
        )
      
    
    {\displaystyle P(n)=2P(n-1)+P(n-2)}
  
).</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Golden_ratio/anloSRmD">Golden ratio</a></li>
<li><a href="/facts/Fibonacci_number/mqxpAUQD">Fibonacci number</a></li>
<li><a href="/facts/Fibonacci_word/DfhEMX8P">Fibonacci word</a></li>
<li><a href="/facts/List_of_fractals_by_Hausdorff_dimension/THnqUPeF">List of fractals by Hausdorff dimension</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li>"<a href="https://onlinemathtools.com/generate-fibonacci-word-fractal">Generate a Fibonacci word fractal</a>", <i>OnlineMathTools.com</i>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Monnerot-Dumaine, Alexis (February 2009). "The Fibonacci word fractal", independent (hal.archives-ouvertes.fr). <a href="http://hal.archives-ouvertes.fr/hal-00367972/fr/" target="_blank">http://hal.archives-ouvertes.fr/hal-00367972/fr/</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Hoffman, Tyler; Steinhurst, Benjamin (2016). "Hausdorff Dimension of Generalized Fibonacci Word Fractals". arXiv:1601.04786 [math.MG]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Blondin-Massé, Alexandre; Brlek, Srečko; Garon, Ariane; and Labbé, Sébastien (2009). "Christoffel and Fibonacci tiles", Lecture Notes in Computer Science: Discrete Geometry for Computer Imagery, p.67-8. Springer. ISBN 9783642043963. <a href="https://doi.org/10.1007%2F978-3-642-04397-0_7" target="_blank">https://doi.org/10.1007%2F978-3-642-04397-0_7</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Blondin-Massé, Alexandre; Brlek, Srečko; Garon, Ariane; and Labbé, Sébastien (2009). "Christoffel and Fibonacci tiles", Lecture Notes in Computer Science: Discrete Geometry for Computer Imagery, p.67-8. Springer. ISBN 9783642043963. <a href="https://doi.org/10.1007%2F978-3-642-04397-0_7" target="_blank">https://doi.org/10.1007%2F978-3-642-04397-0_7</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>A. Blondin-Massé, S. Labbé, S. Brlek, M. Mendès-France (2011). "Fibonacci snowflakes". <a href="http://www.slabbe.org/Publications/2011-fibo-snowflakes.pdf" target="_blank">http://www.slabbe.org/Publications/2011-fibo-snowflakes.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

Fibonacci word fractal open-in-new

Fibonacci word fractal