Posted on 01/20/2011 7:35:04 AM PST by decimon
Finite formula found for partition numbers
For centuries, some of the greatest names in math have tried to make sense of partition numbers, the basis for adding and counting. Many mathematicians added major pieces to the puzzle, but all of them fell short of a full theory to explain partitions. Instead, their work raised more questions about this fundamental area of math.
On Friday, Emory mathematician Ken Ono will unveil new theories that answer these famous old questions.
Ono and his research team have discovered that partition numbers behave like fractals. They have unlocked the divisibility properties of partitions, and developed a mathematical theory for "seeing" their infinitely repeating superstructure. And they have devised the first finite formula to calculate the partitions of any number.
"Our work brings completely new ideas to the problems," says Ono, who will explain the findings in a public lecture at 8 p.m. Friday on the Emory campus. "We prove that partition numbers are 'fractal' for every prime. These numbers, in a way we make precise, are self-similar in a shocking way. Our 'zooming' procedure resolves several open conjectures, and it will change how mathematicians study partitions."
The work was funded by the American Institute of Mathematics (AIM) and the National Science Foundation. Last year, AIM assembled the world's leading experts on partitions, including Ono, to attack some of the remaining big questions in the field. Ono, who is a chaired professor at both Emory and the University of Wisconsin at Madison, led a team consisting of Jan Bruinier, from the Technical University of Darmstadt in Germany; Amanda Folsom, from Yale; and Zach Kent, a post-doctoral fellow at Emory.
"Ken Ono has achieved absolutely breathtaking breakthroughs in the theory of partitions," says George Andrews, professor at Pennsylvania State University and president of the American Mathematical Society. "He proved divisibility properties of the basic partition function that are astounding. He went on to provide a superstructure that no one anticipated just a few years ago. He is a phenomenon."
Child's play
On the surface, partition numbers seem like mathematical child's play. A partition of a number is a sequence of positive integers that add up to that number. For example, 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1. So we say there are 5 partitions of the number 4.
It sounds simple, and yet the partition numbers grow at an incredible rate. The amount of partitions for the number 10 is 42. For the number 100, the partitions explode to more than 190,000,000.
"Partition numbers are a crazy sequence of integers which race rapidly off to infinity," Ono says. "This provocative sequence evokes wonder, and has long fascinated mathematicians."
By definition, partition numbers are tantalizingly simple. But until the breakthroughs by Ono's team, no one was unable to unlock the secret of the complex pattern underlying this rapid growth.
The work of 18th-century mathematician Leonhard Euler led to the first recursive technique for computing the partition values of numbers. The method was slow, however, and impractical for large numbers. For the next 150 years, the method was only successfully implemented to compute the first 200 partition numbers.
"In the mathematical universe, that's like not being able to see further than Mars," Ono says.
A mathematical telescope
In the early 20th century, Srinivasa Ramanujan and G. H. Hardy invented the circle method, which yielded the first good approximation of the partitions for numbers beyond 200. They essentially gave up on trying to find an exact answer, and settled for an approximation.
"This is like Galileo inventing the telescope, allowing you to see beyond what the naked eye can see, even though the view may be dim," Ono says.
Ramanujan also noted some strange patterns in partition numbers. In 1919 he wrote: "There appear to be corresponding properties in which the moduli are powers of 5, 7 or 11 … and no simple properties for any moduli involving primes other than these three."
The legendary Indian mathematician died at the age of 32 before he could explain what he meant by this mysterious quote, now known as Ramanujan's congruences.
In 1937, Hans Rademacher found an exact formula for calculating partition values. While the method was a big improvement over Euler's exact formula, it required adding together infinitely many numbers that have infinitely many decimal places. "These numbers are gruesome," Ono says.
In the ensuing decades, mathematicians have kept building on these breakthroughs, adding more pieces to the puzzle. Despite the advances, they were unable to understand Ramanujan's enigmatic words, or find a finite formula for the partition numbers.
Seeing the forest
Ono's "dream team" wrestled with the problems for months. "Everything we tried didn't work," he says.
A eureka moment happened in September, when Ono and Zach Kent were hiking to Tallulah Falls in northern Georgia. As they walked through the woods, noticing patterns in clumps of trees, Ono and Kent began thinking about what it would be like to "walk" through partition numbers.
"We were standing on some huge rocks, where we could see out over this valley and hear the falls, when we realized partition numbers are fractal," Ono says. "We both just started laughing."
The term fractal was invented in 1980 by Benoit Mandelbrot, to describe what seem like irregularities in the geometry of natural forms. The more a viewer zooms into "rough" natural forms, the clearer it becomes that they actually consist of repeating patterns. Not only are fractals beautiful, they have immense practical value in fields as diverse as art to medicine.
Their hike sparked a theory that reveals a new class of fractals, one that dispensed with the problem of infinity. "It's as though we no longer needed to see all the stars in the universe, because the pattern that keeps repeating forever can be seen on a three-mile walk to Tallulah Falls," Ono says.
Ramanujan's congruences are explained by their fractal theory. The team also demonstrated that the divisibility properties of partition numbers are "fractal" for every prime. "The sequences are all eventually periodic, and they repeat themselves over and over at precise intervals," Ono says. "It's like zooming in on the Mandelbrot set," he adds, referring to the most famous fractal of them all.
The oracle
But this extraordinary view into the superstructure of partition numbers was not enough. The team was determined go beyond mere theories and hit upon a formula that could be implemented in the real world.
The final eureka moment occurred near another Georgia landmark: Spaghetti Junction. Ono and Jan Bruinier were stuck in traffic near the notorious Atlanta interchange. While chatting in the car, they hit upon a way to overcome the infinite complexity of Rademacher's method. They went on to prove a formula that requires only finitely many simple numbers.
"We found a function, that we call P, that is like a magical oracle," Ono says. "I can take any number, plug it into P, and instantly calculate the partitions of that number. P does not return gruesome numbers with infinitely many decimal places. It's the finite, algebraic formula that we have all been looking for."
###
The work by Ono and his colleagues resulted in two papers that will be available soon on the AIM website.
For more sciences news from Emory, visit: www.emory.edu/esciencecommons.
Hear! Hear!
:’D
Cheers!
I hope you realize there are actually no fractals in nature. Fractals depend on having an infinitely divisible space, and actual physical space (as opposed to the abstractions we mathematicians deal with) is not infinitely divisible: no measurement finer than the Planck scale can be made.
There are a whole lot of natural recursive patterns that look like approximations to fractals (because if one works out how the recursion would go for infinitely many steps — assuming an infinitely divisible space — one gets a fractal), but there aren’t actually any fractals in the physical universe.
Off-hand, I don't know any. On the other hand, that's not really a relevant question. The mathematics underpinning RSA encryption was about 300 years old when it was finally put to practical use. The mathematics underlying general relativity had been done without any application in sight over the 30 years or so before Einstein used it (and w/o understanding general relativity, neither atomic energy nor the GPS system would be possible). The Radon transform uses in medical imaging was discovered in the 1930's w/o any practical application in mind.
Mathematical results (which oddly, as some fundamental level are all tautologies -- the weird thing is that there are non-obvious tautologies that have to be discovered) have an infinite shelf-life, and often turn out to be surprisingly useful years later.
Actually, we've been able to determine the number of partitions of a large number for years, the curious thing Ono claims to have done is give an ordinary formula for the number. (The term of art is a "closed formula", which basically is a formula made out of the operations on a calculator, with nothing like a sum whose number of terms depends on the value n, or a place where one uses one formula of something is true, and a different formula if it's not.)
It turns out p(n) is the coefficient of x^n when one computes the product of (1 - x^k)^(-1) for k=1,. . . n by writing each factor as a geometric series (1 + x^k + x^(2k) + . . .) then multiplying them and collecting terms. (If one is willing to allow infinitely many factors with k ranging over all the counting numbers one gets a product whose value is the series (1 + p(1)x + p(2)x^2 + p(3)x^3 +. . . .) .
For practical purposes, one is left with the question of whether evaluating Ono's formula has a lower computational complexity than the procedure I just described. Now that we have computers, a closed formula may not even be useful if it's slower to compute than some other algorithm that computes the same value.
At times FR really needs a “like” button for comments. This is one of them.
How do you know? Have you experienced that? How do you know no one else knows it? If the others knowing don't publicize it how do you know about their knowledge? Sort of a tree falling in the forest thing.
I prefer Churchill's comment: "There is nothing quite as exhilarating as being shot at and missed!" That, I have experienced and I agree.
It does get your blood racing, doesn’t it? The first time, I remember thinking, “What made him choose me as his target?” Just chance was my determination.
Yes, in a way ... there's something intoxicating about finding a relatively simple answer to a big question. Laughter is a common response.
Yes. Some of them were later patented. By the results of their efforts, if you know a simple technique that prevents certain defects in the final product, and your competitors' parts have those defects you can be fairly certain they don't know the cure.
Good for you. I think "new" ideas are simply new associations of old ideas. Was that your experience?
Sort of. Mostly pulling stuff from widely disparate and unrelated fields and combining and adapting them, some inspiration from The Great Inventor (it’s pretty hard to beat a couple billion years of evolution) and such.
Occasionally something really new happens, though.
You are answering the question I was asking and reinforcing my own thoughts. Associating ideas from disparate fields is what I had in mind. Intuition is also key.
I read a book called Connections, by John Burke, I think, which traced history just that way. He showed how history was not linear but that things in one area would lead to something else in another and then off society would go in that new area.
You should watch the Connections series.
Thank you. I didn't know there was one. I tracked it down and I will watch it. Thanks again.
I think you will love it. Enjoy!
Agree with HD. Thanks for taking the time ...
bttt
Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.