## Devlin's Angle |

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.

Another way to express the same result is that the
*N*th Fibonacci number is approximately equal
to the *N*th power of the golden ratio. This gives
a way to calculate the *N*th 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 *N*th 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 *N*th number in any random
Fibonacci sequence generated as described is
approximately equal to the *N*th 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
*N*th number gets to the *N*th 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 *N*th member of the
sequence will, with probability 1, get closer to the
*N*th 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
*N*th number in any random Fibonacci
sequence will get closer and closer to the *N*th
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 e^{P},
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.

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

Devlin's Angle is updated at the beginning of each month.