Replies

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.