Devlin's Angle

March 1999

New Mathematical Constant Discovered

Descendent of Two Thirteenth Century Rabbits

A recent mathematical result by Divakar Viswanath, a young computer scientist at the Mathematical Sciences Research Institute (MSRI) in Berkeley, California, has put the Fibonacci numbers back in the news and shown a connection between rabbits and the number 1.13198824 . . . .

The story begins in the early 13th century, when the great Italian mathematician Fibonacci posed the following simple problem. A man puts a pair of baby rabbits into an enclosed garden. Assuming that each pair of rabbits in the garden bears a new pair every month, which from the second month on itself becomes productive, how many pairs of rabbits will there be in the garden after one year? Like most mathematics problems, you are supposed to ignore such realistic happenings as death, escape, impotence, or whatever. It is not hard to see that the number of pairs of rabbits in the garden in each month is given by the numbers in the sequence 1, 1, 2, 3, 5, 8, 13, etc. This sequence of numbers is called the Fibonacci sequence. The general rule that produces it is that each number after the second one is equal to the sum of the two previous numbers. (So 1+1 = 2, 1+2 = 3, 2+3 = 5, etc.) This corresponds to the fact that each month, the new rabbit births consists of one pair to each of the newly adult pairs plus one pair for each of the earlier adult pairs. Once you have the sequence, you can simply read off that after one year there will be 377 pairs.

Most popular expositions of mathematics mention the Fibonacci sequence, usually observing that the Fibonacci numbers arise frequently in nature. For example, if you count the number of petals in various flowers you will find that the answer is often a Fibonacci number (much more frequently than you would get by chance). For instance, an iris has 3 petals, a primrose 5, a delphinium 8, ragwort 13, an aster 21, a daisy 34, and michaelmas daisies 55 or 89 petals -- all Fibonacci numbers.

For another example from the botanical world, if you look at a sunflower you will see a beautiful pattern of two spirals, one running clockwise, the other counterclockwise. Count those spirals and you will find that there are 21 running clockwise and 34 counterclockwise -- both Fibonacci numbers. Similarly, pine cones have 5 clockwise spirals and 8 counterclockwise spirals; and the pineapple has 8 clockwise spirals and 13 going counterclockwise.

One further example concerns the way the leaves are located on the stems of trees and plants. If you take a look, you will see that, in many cases, as you progress up along a stem, the leaves are located on a spiral path that winds around the stem. The spiral pattern is sufficiently regular that it leads to a numerical parameter characteristic for the species, called its divergence. Start at one leaf and let p be the number of complete turns of the spiral before you find a second leaf directly above the first, and let q be the number of leaves you encounter going from that first one to the last in the process (excluding the first one itself). The quotient p/q is the divergence of the plant.

If you calculate the divergence for different species of plants, you find that both the numerator and the denominator tend to be Fibonacci numbers. In particular, 1/2, 1/3, 2/5, 3/8, 5/13, and 8/21 are all common divergence ratios. For instance, common grasses have a divergence of 1/2, sedges have 1/3, many fruit trees (including the apple) have a divergence of 2/5, plantains have 3/8, and leeks come in at 5/13.

None of the examples I have given are numerological coincidences. Rather they are consequences of the way plants grow. (For instance, the leaves on a plant stem should be situated so that each has a maximum opportunity of receiving sunlight, without being obscured by other leaves.) The Fibonacci sequence is one of a number of very simple mathematical models of growth processes that happens to fit a large variety of real-life growth processes.

The Fibonacci numbers also arise in computer science -- in database structures, sorting techniques, and random number generation, to name three examples. In this case, the explanation is that, in certain instances, the Fibonacci sequence models information growth.

Fibonacci numbers, the golden ratio, and the world of chance

In addition to its connections with the natural world, the Fibonacci sequence has a number of curious mathematical properties. Perhaps the most amazing is that, as you proceed along the sequence, the ratios of the successive terms get closer and closer to the famous "golden ratio" number 1.61803 . . . , the "perfect proportion" ratio much beloved by the ancient Greeks.

Another way to express the same result is that the Nth Fibonacci number is approximately equal to the Nth power of the golden ratio. This gives a way to calculate the Nth Fibonacci number without generating the entire sequence of preceding Fibonacci numbers: Take the golden ratio, raise it to the power N, divide by the square root of 5, and round off the result to the nearest whole number. The answer you get will be the Nth Fibonacci number.

Faced with such a result, most numerically minded citizens will nod appreciatively and move on to something else. But mathematicians ask "What if?" questions. For example, suppose that, when you generate the Fibonacci sequence, you flip a coin at each stage. If it comes up heads, you add the last number to the one before it to give the next number, just as Fibonacci did. But if it comes up tails, you subtract.

For example, one possible sequence you could get in this way is:

1, 1, 2 (H), 3 (H), -1 (T), 4(T), -5 (T), -1 (H), . . .

Another is:

1, 1, 0 (T), 1 (H), -1 (T), 2 (T), 1 (H), 1 (T), . . .

The random sign changes can lead to sequences that suddenly switch from large positive to large negative, such as:

1, 1, 2, 3, 5, 8, 13, 21, -8, 13, -21, . . .

as well as to sequences that cycle endlessly through a particular pattern, such as:

1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, . . .

or

1, 1, 0, 1, -1, 0, -1, 1, 0, 1, -1, . . .

If you are like the character Rosenkrantz in Tom Stoppard's play "Rosenkrantz and Guildenstern are Dead" and your coin keeps coming up heads every time, you can even get the original Fibonacci sequence

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . . .

With such a variety of behavior, it's not obvious that such sequences follow the nice kind of growth pattern of the Fibonacci sequence.

But they do. Last fall, Viswanath, who recently finished a Ph.D. in computer science at Cornell University in New York, showed that the absolute value of the Nth number in any random Fibonacci sequence generated as described is approximately equal to the Nth power of the number 1.13198824 . . . .

Actually, that's not quite accurate. Because the sequences are generated randomly, there are infinitely many possibilities. Some of them will not have the 1.13198824 property. For example, the sequence that cycles endlessly through 1, 1, 0 does not have the property, nor does the original Fibonacci sequence. But those are special cases. What Viswanath showed is that if you actually start to generate such a sequence, then with probability 1 the sequence you get will have the 1.13198824 property. In other words, you can safely bet your life on the fact that for your sequence, the bigger N is, the closer the absolute value of the Nth number gets to the Nth power of 1.13198824 . . .

To give some idea of what this result says, the way the randomized Fibonacci sequence is generated is a bit like the daily weather at a particular location. Today's weather can be assumed to depend on the weather the previous two days, but there is a large element of chance. The analog of the number 1.13198824 . . . for the weather would give a quantitative measure of the unpredictability of weather. It measures the rate at which small disturbances explode exponentially in time. It would tell you for exactly how many days high-speed computers can forecast weather reliably. Unfortunately, nobody knows this number for global weather, and probably never will.

Viswanath's result brings to an end a puzzle that has its origins in 1960. In that year, Hillel Furstenberg (now at the Hebrew University) and Harry Kesten (at Cornell University) showed that for a general class of random-sequence generating processes that includes the random Fibonacci sequence, the absolute value of the Nth member of the sequence will, with probability 1, get closer to the Nth power of some fixed number. (The exact formulation of their result is in terms of random matrix products, and is not for the faint-hearted. See Viswanath's paper -- cited below -- for an exact statement, or read the whole story in the book Random Products of Matrices With Applications to Infinite-Dimensional Schrödinger Operators, by P. Bougerol and J. Lacroix, published by Birkhauser, Basel, in 1984.)

Since Furstenberg and Kesten's deep result applied to the randomized Fibonacci process, it followed that, with probability 1, the absolute value of the Nth number in any random Fibonacci sequence will get closer and closer to the Nth power of some fixed number K. But no one knew the value of the number K, or even how to calculate it.

What Viswanath did was find a way to compute K. At least, he computed the first eight decimal places. Almost certainly, K is irrational, so cannot be computed exactly. Viswanath presented his new result at a colloquium at MSRI last month.

Since there is no known algorithm to compute K, Viswanath had to adopt a circuitous route, showing that K equals eP, where P lies somewhere between 0.1239755980 and 0.1239755995 (and, as usual, e is the base for natural logarithms). Since those two numbers are equal in their first eight decimal places, that meant he could calculate K to eight decimal places.

The process involved large doses of mathematics and some heavy duty computing. Since his computation made use of floating point arithmetic -- which is not exact -- Viswanath had to carry out a detailed mathematical analysis to obtain an upper bound on any possible errors in the computation. He describes the key to his new result this way: "The problem was that fractals were coming in the way of an exact analysis. What I did was to guess the fractal and use it to find K. To do this, I made use of some devilishly clever work carried out by Furstenberg in the early 1960s."

And with that computation, mathematics has a new constant, a direct descendent of a pair of rabbits in thirteenth century Italy.

Yes, but what's it good for?

Does Viswanath's new result have any applications? Probably not -- unless you count the fact that an easily understood, cute, counter-intuitive result about elementary integer arithmetic can motivate a great many individuals (your present columnist included) to take a look at an area of advanced mathematics full of deep and fascinating results that has perhaps not hitherto had the attention it deserves. Indeed, in that respect, the randomized Fibonacci sequence problem resembles Fermat's Last Theorem. It too is easy to state and to understand, and yet it's only a hairsbreadth away from some of the deepest and most profound mathematics of all time. Over the years, Fermat's Last Theorem attracted many people -- both professional and amateur -- to learn about analytic number theory (including a young man in England by the name of Andrew Wiles, who would go on to solve the problem in 1994). When we talk about "applications," we often overlook the very important application of attracting people to mathematics in the first place.

If it's "real" applications you want, however, then you don't have to go any further than the work of Furstenberg and Kesten that lays behind Viswanath's recent result. Applications of that work have led to advances in lasers, new industrial uses of glass, and to development of the copper spirals used in birth control devices. The research which led to those advances earned the 1977 Nobel Prize in physics for the three individuals involved: Philip Anderson of Bell Laboratories, Sir Neville Mott of Cambridge University in England, and John van Vleck of Harvard.

The citation that accompanied the Nobel Prize to the three researchers declared it to be "for their fundamental theoretical investigations of the electronic structure of magnetic and disordered systems."

"Disordered systems" exists within noncrystallic materials that have irregular atomic structures, making it difficult to theorize about them. The key starting point for their work was to realize the importance of electron correlation -- the interaction between the motions of the electrons.

Anderson's main contribution was the discovery a phenomenon known as Anderson localization, and this is where the random matrix multiplication comes in. Imagine you have a material, say a semiconductor, with some impurities. If you pass a current through it, you might expect it to get dispersed and diffracted in a random fashion by the impurities. But in fact, at certain energies, it stays localized. The first rigorous explanation of this used Furstenberg and Kesten's work. (Moreover, the application came long after the mathematics had been worked out -- yet another example of the practical importance of "pure, curiosity driven research.")

A similar explanation shows why you can see through glass. The irregular molecular structure of glass -- it's really a "liquid" -- should surely cause some of the incident light rays to bounce around in a seemingly random fashion, resulting in a blurred emergent image. But as we all know, that's not what happens. Somehow, the repeated random movements lead to orderly behavior. Furstenberg and Kesten's work on random matrix multiplication provides the mathematical machinery required to explain how this happens.

On a final note, Viswanath's paper, in which he describes his new result, has just been accepted for publication in the journal Mathematics of Computation. His email address is divakar@msri.org. To download a Postscript file of his paper, go to the MSRI web site, click on "People", then on "Current visitors", and then on "Viswanath".

- Keith Devlin


NOTE: Keith Devlin discussed the Fibonacci sequence in a nationally broadcast radio interview with Scott Simon on NPR's Weekend Edition on Saturday February 27. Click here to listen to the interview. (This requires that your computer has RealAudio installed.)
Devlin's Angle is updated at the beginning of each month.
Keith Devlin ( devlin@stmarys-ca.edu) is Dean of Science at Saint Mary's College of California, in Moraga, California, and a Senior Researcher at Stanford University. His latest book The Language of Mathematics: Making the Invisible Visible, has just been published by W. H. Freeman.