You are currently browsing the tag archive for the ‘Fibonacci’ tag.

In a letter to a German princess on “the twelve tones of the harpsichord” penned by Leonhard Euler on the 3rd of May 1760 (coincidentally exactly 213 years before my birth day (coincidentally 213 is the smallest number that is part of a consecutive triple, each a product of a pair of distinct prime numbers; 213=3×71, 214=2×107, 215=5×43)), the tension between equal temperament and harmony is highlighted as a central issue in music. Euler wrote “It is evident, therefore, that in fact all semitones are not equal, whatever efforts may be made by musicians to render them such; because true harmony resists the execution of a design contrary to its nature”.

What was Euler talking about?

Music is relative. With the exception of a handful of individuals who possess perfect pitch (as an aside, the genetics are interesting), we perceive music relatively. This is very similar to an RNA-Seq experiment. Transcript abundances are measured only relatively to each other (by comparing read counts), although of course a very relatively abundant transcript can also be inferred to be absolutely abundant, as one has prior knowledge about the abundances of housekeeping and other yardstick genes. So it is with music. We know when we are listening to high vs. low pitch, but within a register we hear combinations of notes as concordant or discordant, as melodic or not, based on the relative frequencies of the pitches.

Harmony is the use of simultaneous sounds in music, and is closely associated with the notion of consonance. Specifically, the perfect fifth is the consonant sound of two frequencies at a ratio of 3/2 (the question of why this ratio sounds “good” is an interesting one, and I recommend Helmholtz‘s “On the sensations of tone” as an excellent starting point for exploration). Harmony leads to a “rational” requirement of musical scales: for example, the ability to produce a perfect fifth requires that among notes corresponding to sounds at pre-specified frequencies, there are a pair at a frequency ratio of 3/2.  Other consonant harmonies correspond to other rational numbers with small denominators (e.g. 4/3). Equal temperament is a relative requirement: in a musical scale composed of N notes, it is desirable that any pair of consecutive notes are at the same frequency ratio, say r. This allows for a music to begin on any note.

The tension Euler described between harmony and equal temperament is the mathematical observation that if r^N = 2 and r^{k}=\frac{3}{2}, then k should be chosen so that \frac{k}{N} = log_2 \frac{3}{2}. This is because the first equation leads to Nlog_2 r = log_2 2 = 1 so that log_2 r = \frac{1}{N}, and the second equation then leads to k log_2 r = k \cdot \left( \frac{1}{N} \right) = log_2 \frac{3}{2}. However log_2 \frac{3}{2} is irrational. This is because if it were rational then log_2 3 would be rational, and that would mean that log_2 3 = \frac{a}{b} for some positive integers a,b, which in turn would be mean that 2^a = 3^b, which is impossible because powers of two are always even, and powers of three always odd. Ergo a problem.

The mathematics above shows that harmony is fundamental incompatible with equal temperament, but so what? If a very good rational approximation can be found for log_2 \frac{3}{2} then music might not be perfect, but perfect should not be the enemy of the good. For example, in a 12 note scale,  we find that the seventh note (e.g. G if we are in C major) produces a frequency ratio with the first of 2^{\frac{7}{12}} = 1.4983..., which is awfully close to 1.5. Does the difference in the third decimal really matter when one is listening to Rammstein?

Is 12 special? What about an 11 note scale? The following math provides the answer:

A (simple) continued fraction representation for an irrational number is an infinite expression of the form

x=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\cdots}}}

The convergents of are the rational numbers obtained by truncating the continued fraction expression at successively increasing finite points, i.e. the sequence \frac{a_0}{1}, \frac{a_0a_1+1}{a_1},\frac{a_2(a_1a_0+1)}{a_2a_1+1},\ldots

Theorem: Let r_i=\frac{n_i}{d_i} be the convergents of a number x. Then the rational number r_i is the best rational approximation to x with denominator \leq d_i.

The theorem is saying that if one approximates an irrational number with its continued fractions, then the denominators of those fractions are optimal in the sense that they provide rational approximations that improve on all lower denominators (an elementary proof is written up here). For example, the continued fraction approximation of log_2 \frac{3}{2} is given by the sequence [0,1,1,2,2,3,1,5,2,23,2,2,1,\ldots ] which translates to the expansion

log_2 \frac{3}{2} = 0+\frac{1}{1+\frac{1}{1+\frac{1}{2+\frac{1}{2+ \cdots}}}}

and leads to to the rational approximations 0,1,\frac{1}{2},\frac{3}{5},\frac{7}{12},\frac{24}{41},\frac{21}{53},\ldots

The fourth denominator is 5, and its interpretation in light of the theorem is that no rational number with 1,2,3 or in the denominator can provide an approximation as good as 3/5 to log_2 \frac{3}{2}. Similarly, with 12 being the next denominator, the theorem implies that no rational number with a denominator between and 11 can provide an approximation to log_2 \frac{3}{2} as good as 7/12. In fact, to improve on the accuracy of the perfect fifth a 29 note scale is required, a number which is much less practical than 12.There are of course other “rational” considerations in choosing a scale. Not only the perfect 5th must be approximated well, but also thirds and fourths. It turns out 12 provides a reasonably good approximation for all of these. In other words, the 12 note scale is not just a historical accident, it is a mathematical inevitability.

The question is did Princess Friederike Charlotte of Brandenburg-Schwedt realize that underlying the principle Euler was writing to her about was the key to understanding not only the theory of music, but also a fundamental design in nature?

The number of petals in flowers

An obvious question not addressed by the theorem stated above is how good are the rational approximations of irrational numbers? Obviously a rational number can always be chosen to be arbitrarily close to any irrational number (e.g. by truncating the decimal expansion arbitrarily far along). But the question is interesting when considered, in light of the theorem above, in terms of the accuracy of approximation as a function of its denominator. Hurwitz‘s theorem provides the answer:

Theorem [Hurwitz, 1891]: For every irrational number x, there are infinitely many rational approximations n/d such that

\left| x - \frac{n}{d} \right| < \frac{1}{\sqrt{5}d^2}.

Moreover, the constant \frac{1}{\sqrt{5}} is best possible.

In other words, the approximation can be as good as the inverse of the square of the denominator (this should be contrasted with using the decimal expansion to approximate, which provides accuracy only proportional to the inverse of the denominator). The fact that \frac{1}{\sqrt{5}} is the best possible constant means that there is some irrational number such that if one sets the constant to be smaller, then there are only finitely many rational approximations achieving the improved accuracy. One cannot get more accurate than \frac{1}{\sqrt{5}d^2} infinitely often, and it turns out that the irrational number that is the extremal example is the golden ratio \varphi = \frac{1+\sqrt{5}}{2}. In a sense made precise by the theorem above, the golden ratio is the hardest irrational number to approximate by rationals. 

Who would care about irrational numbers that are hard to approximate by rational numbers? Mothers of newborn twins?! However as whimsical as Ehud Friedgut‘s Murphy’s law sounds, evolution appears to have appropriated the principle of offsetting cycles to optimize branching patterns in plants and trees.

Tree branches around a trunk, or of flower petals around a stem, demand sunlight and ideally do not line up with each other. Suppose that they are equally spaced, separated by a fixed angle \theta. If \theta is rational, then the branches or petals will line up perfectly creating a pattern, viewed from above, of lines emanating from the trunk or main stem. An irrational angle ensures that branches never line up perfectly, however if the irrational number is well approximated by a rational number then the overlap will be extensive. That is, the branches will almost line up. The solution? Choose an irrational angle that is as hard as possible to approximate by rationals. The golden ratio! The angle turns out to be 137.5 degrees.

With the golden ratio, the branching pattern when viewed from above looks like a series of spirals. Depending on the time between the appearance of branches (or seeds at the center of a flower), the number of spirals varies. The numbers though will always correspond to one of the convergents of the (continued fraction expansion of the) golden ratio. These are

\frac{2}{3}, \frac{3}{5}, \frac{5}{8}, \frac{8}{13}, \frac{13}{21}, \ldots.

Note that the denominators are the Fibonacci numbers. Since flower petals typically form at the tips of the spirals, one frequently finds a Fibonacci number of petals on flowers. Fibonacci numbers are all over plants. Nature is irrational.

Georgia-O-Keeffe-Music-Pink-and-Blue-II-1918-us_large

Georgia O’Keeffe: Music Pink and Blue No. 2 (1918). Next time you are pondering what her flowers truly represent, think also of the tension between the rational and the irrational in music, and in nature.

I  learned today about a cute Fibonacci fact from my friend Federico Ardila:

1/89 = 0.011235
1/9899 = 0.0001010203050813213455
1/998999 = 0.000001001002003005008013021034055089144233377610...

\vdots

The pattern is explained in a note in the College Mathematics Journal (2003). Of course Fibonacci numbers are ubiquitous in biology, but in thinking about this pattern I was reminded of a lesser known connection between Fibonacci numbers and biology in the context of the combinatorics of splicing:

A stretch of DNA sequence with n \geq 1 acceptor sites and m \geq 1 donor sites can produce at most F_{n+m+1} distinct spliced transcripts, where the numbers F_i are the Fibonacci numbers.

The derivation is straightforward using induction: to simplify notation we denote acceptor sites with an open parenthesis “(” and donor sites with a closed parenthesis “)”. We  use the notation |S| for the length of a string S of open and closed parentheses, and denote the maximum number of transcripts that can be spliced from S by p(S). We assume that the theorem is true by induction for |S| \leq n-1 (the base case is trivial). Let S be a string with |S|=n. Observe that S must have an open parenthesis somewhere that is followed immediately be a closed parentheses. Otherwise we have that p(S)=1 (the empty string is considered to be a valid transcript). We therefore have S= S_1()S_2 where S_1 has open and r closed parentheses respectively, and S_2 has n-k-r-s-2 open and s closed parentheses respectively. Now notice that

p(S) \leq F_{r+k+1}F_{n-k-r}+F_{r+k+2}F_{n-k-r-1}+F_{n-1}-F_{r+k+1}F_{n-k-r-1}.

This can be seen by breaking down the terms as follows: One can take any transcript in S_1 and append to it a transcript in “(S_2“. Similarly, one can take a transcript in S_1) and append to it a transcript in S_2. Transcripts ommitting the interior pair () between S_1 and S_2 are counted twice, which is fine because one of the copies corresponds to all transcripts that include the interior pair () between S_1 and S_2. The last two terms account for all transcripts whose last element in S_1 is an open parenthesis, and whose first element in S_2 is a closed parenthesis. This is counted by considering all transcripts in S_1S_2 and subtracting transcripts that do not include a parentheses from each. Finally, using the Fibonacci recurrence and the identity

F_{n+m} = F_{n+1}F_m + F_nF_{m-1}

we have

p(S) \leq F_n + F_{r+k+1}F_{n-k-r-1}+F_{n-1}-F_{r+k+1}F_{n-k-r-1} = F_{n+1}.

The bound is attained for certain configurations, such as S = ()() \cdots () with acceptor and donor sites.

The combinatorics is elementary and it only establishes what is already intuitive and obvious: splicing combinatorics dictates that there are a lot of transcripts (exponentially many in the number of acceptor and donor sites) that can, in principle, be spliced together, even from short DNA sequences. The question, then, is why do most genes have so few isoforms? Or do they?

Blog Stats

  • 1,908,809 views
%d bloggers like this: