Fractals, Fibonacci, and factorizations
The rule for generating the famous Fibonacci sequence
1, 1, 2, 3, 5, 8, 13, 21, ... is that each number (after the first two) is the sum of the previous two numbers. The Fibonacci word
is an infinite string of zeros and ones with properties reminiscent of the Fibonacci sequence, and the Fibonacci fractal
, shown in the picture, is a way to represent the Fibonacci word in the form of a fractal.
One way to generate the Fibonacci word is to define strings of zeros and ones by the rules S(0)=0, S(1)=01 and S(n)=S(n–1)S(n–2) when n is at least 2. This gives rise to the sequence of strings 0, 01, 010, 01001, 01001010, 0100101001001, ..., whose limit, as n tends to infinity, is the Fibonacci word
. There are other equivalent, but superficially very different, ways to generate this word, including (a) using an explicit formula for each digit given in terms of the golden ratio; (b) using a substitution rule; and (c) using the Zeckendorf representation of integers in terms of Fibonacci numbers.
By suitably interpreting the digits of the Fibonacci word as turtle graphics instructions in a Logo-like programming language, it is possible to represent the word as a fractal. More precisely, if one reads the digits in order, then the n-th digit corresponds to the following sequence of instructions:
1. draw a segment forwards;
2. if the digit is 0, then turn left 90 degrees is n is even, and turn right 90 degrees if n is odd.
The picture shows the result of this procedure after many iterations. The resulting curve has various interesting mathematical properties, some of which concern the square-shaped gaps. By inspection, we count one large square gap (in the middle, at the bottom); five smaller square gaps, and 21 square gaps of the next size down. The numbers of these gaps, sorted by size, turn out to be given by every third Fibonacci number starting with the second 1 (1, 5, 21, 89...) which means that there are 89 squares of the next size down. Furthermore, each square has a side length that is 1+√2 times the side length of the square of the next size down; the number 1+√2 is known as the silver ratio
The recent paper Factorizations of the Fibonacci Infinite Word
by Gabriele Fici
) surveys some factorizations of the Fibonacci word and shows how to derive these factorizations using elementary properties of the Fibonacci numbers. In some cases, this gives easier derivations of the results than were previously known. An example of such a factorization involves the sequences S(n) from earlier. Proposition 1 of the paper proves that the Fibonacci word can be factorized as the infinite product 0.1.S(0).S(1).S(2)..., where the symbol . is used to separate the factors.
One of the most surprising factorizations in the paper is Proposition 9, which involves the reversals, T(n), of the strings S(n). The strings T(0), T(1) and so on are then given by the sequence 0, 10, 010, 10010, 01010010, ... Remarkably, the concatenation of the strings T(n) also gives the Fibonacci word, even though the ingredients being used to construct it are backwards and generally not palindromic. Another way to say this is that the Fibonacci word can be factorized as the infinite product T(0).T(1).T(2)...Relevant links
The 2009 paper The Fibonacci Word fractal
by Alexis Monnerot-Dumaine
is an excellent guide to the mathematical properties of the fractal, and the picture of the fractal here comes from that paper. You can download the paper for free at https://hal.archives-ouvertes.fr/hal-00367972/document
Monnerot-Dumaine's paper explains how to construct the Fibonacci word using a substitution rule
, and explores what the fractal looks like if one makes turns at angles other than a right angle.
Fici's paper explains how to construct the word using the Zeckendorf representation
of natural numbers. It is a theorem that any positive integer can be expressed uniquely as the sum of one or more distinct non-consecutive Fibonacci numbers. This is called Zeckendorf's Theorem
, even though Zeckendorf was not the first to prove it: https://en.wikipedia.org/wiki/Zeckendorf's_theorem
Wikipedia's article on the Fibonacci word gives an explicit formula for the n-th digit of the word and mentions many other interesting properties. For example, the Fibonacci word is often cited as the worst case for algorithms detecting repetitions in a string. https://en.wikipedia.org/wiki/Fibonacci_word
The On-Line Encyclopedia of Integer Sequences
on the Fibonacci word: https://oeis.org/A003849
Wikipedia on turtle graphics: https://en.wikipedia.org/wiki/Turtle_graphics
I have posted about the Fibonacci word twice before, although not recently.
My post from March 2013 discusses the word in the context of self-shuffling words: https://plus.google.com/101584889282878921052/posts/YnUkZ986LMM
My post from December 2012 discusses Fibonacci snowflakes and some generalizations of the Fibonacci word: https://plus.google.com/101584889282878921052/posts/KSuUFJV6tyv
If you're disappointed that I didn't talk about the golden ratio, have a look at the aspect ratio of the accompanying picture.#mathematics #sciencesunday #spnetwork