Friday, February 11, 2011

Seeing into the Fractal Future

Mathematics' Nearly Century-Old Partitions Enigma Spawns Fractals Solution

Newly discovered counting patterns explain and elaborate cryptic claims made by the self-taught mathematician Srinivasa Ramanujan in 1919

PARTITION PROBLEM: The Mandelbrot set, above, is the most famous fractal of them all, and demonstrates the endlessly repeating patterns of forms in nature. Ono and his colleagues discovered a new class of fractals, one that reveals the endlessly repeating superstructure of partition numbersImage: Wikipedia Commons/Wolfgang Beyer

For someone who died at the age of 32 the largely self-taught Indian mathematicianSrinivasa Ramanujan left behind an impressive legacy of insights into the theory of numbers—including many claims that he did not support with proof. One of his more enigmatic statements, made nearly a century ago, about counting the number of ways in which a number can be expressed as a sum, has now helped researchers find unexpected fractal structures in the landscape of counting.

Ramanujan's statement concerned the deceptively simple concept of partitions—the different ways in which a whole number can be subdivided into smaller numbers. Ken Ono of Emory University and his collaborators have now figured out new ways of counting all possible partitions, and found that the results form fractals—namely, structures in which patterns or shapes repeat identically at multiple different scales. "The fractal theory we've discovered completely answers Ramanujan's enigmatic statement," Ono says. The problems his team cracked were seen as holy grails of number theory, and its solutions may have repercussions throughout mathematics.

One way to think of partitions is to consider how a set of any (indistinguishable) objects can be divided into subsets. For example, if you need to store five boxes in your basement, you can pile them all into a single stack; lay them individually on the floor as five subsets containing one box apiece; put them in one pile, or subset, of three plus one pile of two; and so on—you have a total of 7 options:

5, 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+4, 1+2+2 or 2+3.

Mathematicians express this by saying p(5) = 7, where p is short for partition. For the number 6 there are 11 options: p(6) = 11. As the number n increases, p(n) soon starts to grow very fast, so that for example p(100) = 190,569,292 and p(1,000) is a 32-figure number. (The WolframAlpha knowledge engine calculates partitions for numbers as large as one million.)

The concept is so basic and fundamental that it is central to number theory and pops up in most other fields of math as well. Mathematicians have long known that the sequence of numbers made by the p(n)'s for all values of n is far from being random. Ramanujan and others after him found formulas to predict the value of any p(n) with good approximation, for example. And general "recursive" formulas have long existed to calculate p(n), but they don't speed up calculations very much because to find p(n) you first need to know p(n – 1), p(n – 2) and so on. "That's impractical even with the help of a computer today," Ono says. 

A direct formula for calculating the exact value of p(n) could in principle be faster. Another advantage of a direct formula would be the ability to compare values of p(n) for arbitrarily large n's and thus to prove the existence of patterns, such as properties that repeat along an entire infinite sequence.

Ramanujan's original statement, in fact, stemmed from the observation of patterns, such as the fact that p(9) = 30, p(9 + 5) = 135, p(9 + 10) = 490, p(9 + 15) = 1,575 and so on are all divisible by 5. Note that here the n's come at intervals of five units.

Ramanujan posited that this pattern should go on forever, and that similar patterns exist when 5 is replaced by 7 or 11—there are infinite sequences of p(n) that are all divisible by 7 or 11, or, as mathematicians say, in which the "moduli" are 7 or 11. 

Then, in nearly oracular tone Ramanujan went on: "There appear to be corresponding properties," he wrote in his 1919 paper, "in which the moduli are powers of 5, 7 or 11...and no simple properties for any moduli involving primes other than these three." (Primes are whole numbers that are only divisible by themselves or by 1.) Thus, for instance, there should be formulas for an infinity of n's separated by 5^3 = 125 units, saying that the corresponding p(n)'s should all be divisible by 125.

In the years since, mathematicians were able to prove the simple cases based on Ramanujan's statement. As to what "no simple properties" could mean, that was anybody's guess—until now.

Working with Jan Hendrik Bruinier of Darmstadt Technical University in Germany, Ono has developed the first exact formula for calculating p(n) for any n. And in a separate paper with Zachary A. Kent, also at Emory, and Amanda Folsom of Yale University, he has identified patterns that probably even Ramanujan could not have dreamed of.
 
The patterns link certain sequences of p(n) where the n's are separated by powers of any prime number beyond 11. For example, take the next prime up, 13, and the sequence p(6), p(6 + 13), p(6 + 13 + 13) and so on. Ono's formulas link these values with those of p(1,007), p(1,007 + 13^2), p(1007 + 13^2 + 13^2) and so on. The same formulas link the latter sequence with one where the n's come at intervals of 13^3—and so on for larger and larger exponents. (The formulas are slightly more subtle than just saying that the p(n) are multiples of a prime.) Such recurrence is typical of fractal structures such as a Mandelbrot set [see the video above], and is the number theory equivalent of zooming into a fractal, Ono explains.

Ono unveiled the discoveries January 21 at a specially convened symposium at Emory. By that afternoon the news had made waves across the math world, and his in-box had filled with 1,500 e-mails from mathematicians, reporters and "cranks," he says. (Ono, Folsom and Kent posted their proof on the Web site of the American Institute of Mathematics and also submitted it to a journal. The full proof of Ono and Bruinier's new formula is still being written up, Ono says.)

"Ken is a phenomenon," comments George E. Andrews, a partitions expert at The Pennsylvania State University. The new fractal view of partitions, Andrews adds, "provides a superstructure that no one anticipated just a few years ago."

Do Ono et al.'s discoveries have any practical use? Hard to predict, Andrews says. "Often deep understanding of underlying pure mathematics takes awhile to filter into applications." In the past methods developed to understand partitions have later been applied to physics problems such as the theory of the strong nuclear force or the entropy of black holes.

Meanwhile, mathematicians are left to contemplate Ramanujan's mind. Many of his claims, Ono points out, have turned out to be incorrect, but his work still illuminates so much of what number theorists study today. "All of this stuff that we're studying right now for some crazy reason was anticipated by Ramanujan," he says.

"He was a magical genius," Andrews adds, "and the rest of us wish we knew how he was able to see so deeply."