Road to Partition: Unveiling the Fractal Structure of Partition Numbers
This is a sample article from the April/May 2011 issue of MAA FOCUS.
Snowflakes can appear very complicated, but a closer look reveals underlying patterns that help us discern how snowflakes are put together. Sequences of numbers that arise out of simple mathematical operations or definitions can also seem complicated and mysterious, until we discover the patterns that allow us to understand them.
Ken Ono of Emory University and his collaborators have accomplished such a breakthrough for so-called partition numbers, long the subject of intense mathematical scrutiny. Initially very mysterious objects, partition numbers are now completely understood in terms of a finite formula and a fractal pattern. These discoveries were the subject of a recent three-day symposium held at Emory.
Ken Ono, left, and Zach Kent.(Photo courtesy of eScienceCommons)
For every natural number n, we define its partition number, p(n), as the number of ways in which we can break down n as a sum of positive integers. For example,
4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1.
Since we can write the number 4 as a sum in five different ways (including the number itself), p(4) = 5.
If we start computing p(n) for larger values of n, we find that these numbers grow very quickly. For instance, p(128) runs to ten digits. Many number-theoretic questions arise naturally from this simple idea of partition number: Can we compute p(n) for any n? How quickly does this sequence grow? Do these numbers follow some sort of divisibility pattern?
Although partition numbers involve nothing more than the simple ideas of adding and counting—something a child could follow—mathematicians have had great difficulty trying to compute and understand these mysterious numbers. As is common in number theory, Ono says, “sometimes the problems which are simplest to state are the hardest to solve.”
Over the centuries, partition numbers attracted the attention of a variety of prominent mathematicians—Euler, Jacobi, Hardy, Ramanujan, Rademacher, Atkin, and others, who developed interesting and useful methods for tackling problems in number theory along the way. But key questions about partition numbers themselves remained unanswered.
Last year, in a project funded by the American Institute of Mathematics (AIM) and the National Science Foundation, AIM assembled the world’s leading experts on partitions, including Ono, to attack these remaining questions. The group’s first task was to assemble a list of important problems, Ono says. The challenge then was to explain these interesting problems to people in related areas of mathematics who were not experts in partitions. This forced everyone to reformulate certain problems so that others could also contribute, he says. In the process, a lot of new ideas started taking shape.
A finite formula for the infinitely complex
Leonhard Euler, in the 1700s, was the first mathematician to come up with a clever way of computing partition numbers. He found a recursive formula, based on his pentagonal number theorem, which for a long time was the best known method for computing values of p(n). It led to the calculation of the first 200 partition numbers in 1915.
A few years later, G. H. Hardy and Srinivasa Ramanujan obtained a good approximation for much larger but difficult-to-compute values of p(n). This asymptotic behavior was proved using their famous “circle method,” still a fundamental tool in analytic number theory.
By bootstrapping Hardy and Ramanujan’s result, Hans Rademacher found a formula for partition numbers using Bessel functions and Kloosterman sums. The main drawback is that this formula is, as Ono puts it, a “crazy infinite sum of perfectly good integers.” To use the formula to obtain partition numbers in practice, we need to truncate the series and round the values obtained, but that leads to large errors in successive approximations.
For example, as Ono showed in his Emory seminar talk, in using Rademacher’s formula to compute p(1), which is 1, the tenth approximation is much worse than the second, which is contrary to what we would intuitively expect in making a series of approximations that should converge to the true value.
The breakthrough came when Ono, together with Jan Bruinier, a mathematician at Technische Universität Darmstadt in Germany, realized that machinery from another area of number theory—Mock modular forms and Maass forms—yields a handy function, which they denote P(z). Ono affectionately calls it the “oracle function.” It provides the finite formula for partition numbers that had eluded so many mathematicians in the past.
Ono and Bruinier are still working on details of the paper describing the results, which were finalized in December. The introduction to the paper, however, can already be found at the AIM website. [http://aimath.org/news/partition/brunier-ono]
(l-adic) space oddity
Ramanujan also studied the divisibility properties of partition numbers, and he found some interesting congruences. In a 1919 paper, he states:
“I have proved . . . that
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.”
In other words, the first congruence says that, starting with 4, every fifth partition number is a multiple of five. The curious thing, Ono points out, is that there are no simple properties like the ones mentioned above for any other primes.
But what about the simplest primes: 2 and 3? Silviu Radu recently showed that it’s impossible to find arithmetic progressions of the form An + B for which the partition numbers are always even or always a multiple of three.
In 2000, Ono proved that for all primes Q greater than or equal to 5, there are infinitely many arithmetic progressions of the form An + B for which the partition numbers are always a multiple of Q. However, Ono notes, the congruences that he found are “monstrosities,” like
Most partition numbers don’t fall into Ramanujan’s congruences or Ono’s monster congruences. So, even after Ono’s work, much remained mysterious.
In 1967, A. O. L. Atkin had proved some of Ramanujan’s conjectured “corresponding properties” for the prime 11, by using a clever alternating sequence of operators. Ono started playing with this approach at AIM, looking at certain sequences of partition numbers. He began with the sequence
and he noticed that the partition numbers are all multiples of 5. Indeed, ignoring the first term, the rest are all multiples of 52. Eventually, for any m, all the terms in the sequence are divisible by 5m.
Two numbers are said to be 5-adically close if their difference is divisible by a large power of 5. In terms of the number-theoretic picture for 5-adic distances for partition numbers, we’re zooming in closer and closer. So we are looking at a sequence that exhibits the same type of pattern as we zoom to higher resolutions.
This discovery led Ono to think about fractals, which are more often associated with geometric structures than with number-theoretic patterns. Ono wondered if other primes exhibited such a self-similar pattern. Using results by Atkin, he soon found it for the prime 13. In this case, self-similarity means that terms in the sequences mod some power of 13 can be found from the previous term in the sequence. In other words, the sequences are periodic with period 1.
Then came the hard part of justifying that this really works—that partition numbers in general exhibit self-similarity at increasing resolution, Ono says. He worked with Amanda Folsom of Yale University and Zachary Kent of Emory to develop these ideas. It took the group months of hard work, with moments of frustration, to get the results they wanted: a new picture of the universe of partition numbers as some sort of strange, number-theoretic Mandelbrot set.
The theorem proved by Folsom, Kent, and Ono simply states that for any prime number , the partition numbers are l-adically fractal (these particular sequences exhibit a periodicity that doesn’t change when we zoom in to the l-adic picture), and gives an upper bound for their Hausdorff dimension.
Magically, Ramanujan’s congruences for 5, 7, and 11 fall right out of this new theorem. The reason these are the only primes with “simple congruences” is that they are the only primes that give a 0-dimensional fractal structure to the partition numbers. A copy of the Folsom, Kent, Ono paper can be found at the AIM website (pdf).
To infinity and beyond
The results found by Ono and his collaborators were presented officially on January 21, 2011, at Emory, in a public lecture, which attracted so many people, some were left standing in the aisles and at the back of the room. A video of Ono’s talk can be found on YouTube. [http://www.youtube.com/watch?v=aj4FozCSg8g].
One attendee was David Bressoud of Macalester College. Even though Ono’s results with Bruinier, Kent, and Folsom were the stars of the symposium, Bressoud was struck by all the other promising young mathematicians who were also gathered there. It is really exciting to see this whole constellation of young people who have formed this intense orbit around Ono, he says, and have been inspired by him.
Indeed, there may be much more to come, with many opportunities to tackle related open problems, as discussions at the Emory symposium appeared to indicate.
Adriana Salerno is an Assistant Professor of mathematics at Bates College.