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.
“So, what are the practical, real world applications/uses of being able to determine the number of partitions of large number?”
It gives us ADD kids another way to count numbers and now I don’t have to remember up to 65536 as I double numbers from 2.
Doesn’t everybody know this?
The Laplace transform is used frequently in engineering and physics; the output of a linear time invariant system can be calculated by convolving its unit impulse response with the input signal. Performing this calculation in Laplace space turns the convolution into a multiplication; the latter being easier to solve because of its algebraic form. For more information, see control theory.
The Laplace transform can also be used to solve differential equations and is used extensively in electrical engineering. The Laplace transform reduces a linear differential equation to an algebraic equation, which can then be solved by the formal rules of algebra. The original differential equation can then be solved by applying the inverse Laplace transform. The English electrical engineer Oliver Heaviside first proposed a similar scheme, although without using the Laplace transform; and the resulting operational calculus is credited as the Heaviside calculus.
wikipedia.com
As a side note, this is why I have always liked the English based system of measurement, because the number 12 (1 foot) has several equal partitions (i.e. 6+6, 4+4+4, 3+3+3+3, 2+2+2+2+2+2), the yard (divisible in inches to an integer by 1,2,3,4,6,9,12,18) and the mile (divisible in feet by every number from 1 to 12 except for 7 and 9).
If you need to, you can multiply feet by inches to give you even more divisible numbers for greater flexibility. That also equals out to fractions the brain understands, like 1/2, 1/4, 1/8, 1/3, 1/6, 1/9 etc. It’s so much easier for me anyway to think in those terms v. the crappy decimal system, which I despise.
I think someone asked a similar question to Einstein when he came up with his Theory of Relativity.
Maybe there is a pattern to the number of partitins of prime numbers, which would help in the search for larger prime numers?
He probably has to beat the babes off with a stick.
I love partitions and rarely post, so please forgive my long explanation of this article.
What is a partition? As already explained by previous posters, given any positive whole number n=1,2,3,... it is possible to write it as the sum of smaller positive whole numbers in different ways. This is called “partitioning” the number. For example, there are 3 ways to partition n=3:
3 = 2+1 = 1+1+1.
Note that the number n is counted as a trivial partition of itself, so 3 is a partition of 3; and the order of the summands is neglected in calculating partitions, so 2+1=1+2 are not considered different partitions.
The number of different partitions of n is called p(n).
The first few values of p(n) and the corresponding partitions it counts are
p(1) = 1, counts 1
p(2) = 2, counts 2 = 1+1
p(3) = 3, counts 3 = 2+1 = 1+1+1
p(4) = 5, counts 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1
p(5) = 7, counts 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1
and so forth...
Unfortunately the number of partitions p(n) gets unwieldly large very quickly.
P(1) = 1
...
p(100) = 190,569,292
...
p(1000) = 24,061,467,864,032,622,473,692,149,727,991 (Wikipedia)
...
Around the time of WWI Hardy and Ramanujan found an asymptotic approximation for p(n), but they failed to find an exact formula. In the 1930s Rademacher did find an exact formula for p(n), but it involved a complicated infinite series of irrational numbers that only converged to p(n). Ken Ono claims that he has found a *finite* formula for p(n). If so, in the words of VP Biden, that’s a Big F’ing Deal.
Finding an exact result for p(n) is so hard that mathematicians have been happy merely to find certain general patterns true about p(n). For example, Ramanujan found some division “congruences” in p(n) for special values of n:
For any k=0,1,2,...
p(5*k+4) is always divisible by 5.
p(7*k+5) is always divisible by 7.
p(11*k+6) is always divisible by 11.
For example, in the simplest case, p(4)=5 and p(5+4)=p(9)=30, and both are divisible by 5.
The values 5,7,11 turn out to be very special: It can be shown that there is no similar divisibility congruence statement of the form
p(A*k+B) is always divisible by A.
for any prime number A other than A=5,7, or 11. This is the content of Ramanujan’s “mysterious quote”.
In the past, Ono has proved there are more complicated divisibility congruences for every prime number, and later he showed that there are congruences for every number not divisible by both 2 and 3. So Ono generally knows what he is talking about when it comes to partitions. For example, one of his complicated congruences is
p(4063467631*k + 30064597) is always divisible by 31.
The article says that Ono has found a systematic way of finding/explaining these divisibility congruences.
The one aspect of this article that I consider to be slightly incorrect is saying that the “partition numbers are fractal”. I know that Ono means he has a recursive proscription for the partitions, but in my opinion the term “fractal” (used to describe geometric objects of fractional dimension) is not exactly right here.
So, what are the practical, real world applications/uses of being able to determine the number of partitions of large number?
Although advances in number theory generally won’t help us do things like build a better door hinge, partitions are fundamental to many problems in combinatorics. The “practical” applications that may benefit from advances in our understanding of partitions are things like algorithm theory in computer science, elliptic curve cryptography, solutions to certain types of problems in statistical physics such as the Ising Model, and Feynman diagram expansions in quantum field theory.
||||||||||
How many ways can those tally marks be grouped or partitioned, keeping the total number at ten?
He probably has to beat the babes off with a stick.
solitinic's cast-offs. ;-)
Wow. I just had a deja vu. I felt like I was reliving a high school moment. By the third paragraph I could barely stay awake.
He does it with fractals. Nature is a series of repeating patterns that appear even in things that appear to be random.
What these guys did was tie yet something else that seemed to spin off into infinity into something that could be understood through a pattern that repeats.
The golden ratio is something you’ll be able to ‘hook into’ mentally. You’ll find this ratio in everything from how a sunflower’s seeds sit in the center of the flower to how a nautilus shell’s growth from it’s center has the same proportions.
It appears this legendary East Indian mathmatician understood this, but hadn’t explained it fully on paper. Tesla was notorious for this failing. What these guys might find is that the moduli consisting of these three primes - 5, 7, and 11 are at the heart of the pattern.
What fascinates me is that we have a term for numbers called ‘the partition’ and that we’ve discovered a significance for it in nature and science. I love that.
If you are not doing math at 8PM on Friday night you do not have what it takes to be a great mathematician. Of course that probably means you are a normal human being.
If you’re not sleeping wioth your calculator, you’re not a mathematician.
I wasn't asking mockingly. I really was curious.
My understanding is that if someone were to discover a quick and easy method to determine the prime factors of very large numbers, our current methods of public-key cryptography would become obsolete. I wanted to know if this discovery had similar implications.
the Pythagorean says, "all is number", I say...
- What about letters?
- Must have been a big number that you smoked.
- How many finger am I holding up?
- What's the number for 9-1-1?
- Other(please specify)
Though tests said I should be highly otherwise, my performance was not great in math.
Would you be willing to relate, in simple terms, perhaps graphically??? the golden ration with the 5, 7, 11 thing you were mentioning?
I'm going to begin an immediate study of flocks of demoncrats...(Or is that "Flocks of flockers"?)
I'm glad I'm not the only one to ask that question. Somehow I doubt it has any real world use.
Brilliant!
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.