Counting Ain’t Easy

Ken Ono (artist's rendition)

The first math thing a person learns is counting:


People have been counting for many thousands of years.  Probably the first function ever invented was the partition function.  In fact, it was probably invented even before people called functions functions!  So what is it?

The input is any number n = 1,2,3,4,5,6,… and the output is the number of ways to divvy (ie. partition) n objects into subgroups.

For example, p(3)=3 because 3 can be divided into 3 or 2 and 1 or 1 and 1 and 1.  That is, 3=3, 3= 2+1, and 3=1+1+1.

As another example, p(4)=5 because

4=4, 4=3+1, 4=2+2, 4=2+1+1, and 4= 1+1+1+1.

You can imagine a bunch of Cro-Magons standing around trying to decide how to divvy up 5 fish they’ve just caught.

Computing p(5)

The partition function is a classic example of a function where it is easy to describe the rule and anyone can calculate p(n), but there is no easy rule you can give.  That is, p(n) can’t be written as a polynomial or some other simple function.

Here are some more values of p(n) for you to look at:

  • p(1) = 1
  • p(2) = 2
  • p(3) = 3
  • p(4) = 5
  • p(5) = 7
  • p(6) = 11
  • p(7) = 15
  • p(8) = 22
  • p(9) = 30
  • p(10) = 42
  • p(20) = 627
  • p(50) = 204,226
  • p(100) = 190,569,292
  • p(200) = 3,972,999,029,388
  • p(1000) = 24,061,467,864,032,622,473,692,149,727,991 ≈ 2.4×1031
  • p(3000) ≈ 4.9 x 1056

The first thing to notice is p(n) gets big very fast.  The total mass of the observable universe is estimated to be around 3 x 1054 kg.  So how do you study such a function?

One approach is to write an infinite series using p(n) as the coefficents:

1+p(1)x+p(2)x^{2} + p(3)x^{3} + p(4)x^{4} + \dots

This is called the generating function for p(n).  We’re not so interested in convergence for the series.  Instead, we’d like to use algebra to rewrite this series in a more understandable form.  Euler showed that this works beautifully by obtaining:

The right hand side is an infinite product and each term in the product is a power series.  So to actually calculate the right hand side involves a whole bunch of FOILing.  But the equation looks very nice and is useful for proving many things.

It turns out that in number theory you often see equations which look like

infinite sum = infinite product

and it is a very handy tool once you’re used to it.  Dr. Pitale will talk in the Math Club later this semester and you’ll probably see similar formulas for the famous Riemann Zeta function.


Another approach to studying p(n) is to figure out what happens asymptotically (that is, what happens as n \to \infty.).

For example, another famous function without an easy rule is \pi(n).  This is the function which gives the number of prime numbers less than n.    The famous Prime Number Theorem is that

\lim_{n \to \infty} \frac{\pi(n)}{\left( n/\ln(n) \right)} = 1.

That is, as n gets very large, the ratio between \pi(n) and $n/\ln(n)$ becomes arbitrarily close to 1.

A nearly as famous result by G. H. Hardy and Ramanujan in 1918 is:

Here the squiggle ~ exactly means that the limit as n \to \infty of the left hand side divided by the right hand side is 1.  From this we see that p(n) grows as fast as an exponential type function.  Which is darn fast!


Another route to take is to see if p(n) satisfies any interesting equations.  In this case, equations means modular arithmetic where two numbers are equal if they have the same remainder when divided by some fixed number.  Srinivasa Ramanujan (who deserves a blog post of his own!) proved in 1915 that, for any k=1,2,3,4,…, we have the following congruences:

Even more mysteriously, Ramanujan also 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.

— Ramanujan

That is, there are similar congruences if you use 5 to a power, 7 to a power, or 11 to a power, but nothing similar for any other primes.  How strange!

Even though the partition function has long been studied, it still is a very active area of research. Our own Drs. Martin, Pitale, Schmidt, and Spallone all do research in areas close to the partition function.

Ken Ono at the whiteboard (recognize the second formula?)

One of the most well known mathematicians who currently does research on the partition function is Ken Ono of Emory University (and UW Madison).  He and his collaborators recently announced two amazing new results about this ancient function.

First, Bruiner and Ono found a “simple” formula for the partition function (here is a summary of their results from the AIM website).  Simple in that it doesn’t involve infinite series, infinite products, or other such things.   Rather, it is a finite sum of numbers which are straightforward to compute.  It looks like this:

p(n) = \frac{1}{24n-1}\left( P(\alpha_{n,1}) + \cdots + P(\alpha_{n,h_n})\right)

where the P function is an explicitly known function which isn’t hard to compute and the \alpha‘s are explicitly computable numbers.   If you watch the video below, you’ll see Dr. Ono explain how to use this formula on an example and you’ll agree that it’s remarkably easy to use.


The second result recently announced by Folsom, Kent, and Ono is that the numbers p(n) are fractal!  Wait, what?  If you are like us at HQ, you think of fractals looking like:

The Mandlebrot Set

Of course, the numbers given by the partition function don’t make a pretty picture, but they are fractal nonetheless.

What is a fractal?  It is something which is infinitely complex, but it is self-similar as you “zoom in” and is given by some simple recursive formula.

For the partition numbers, Folsom, Kent, and Ono prove that if you fix a prime number l bigger than or equal to 5, and look at the partition numbers modulo the powers of l, then as the powers get higher and higher (that’s your “zooming in”), then you discover a self-similar structure.

Saying it in a more fancy way, they show the partition numbers are a fractal in the l-adic topology.  This is a common topology to use in number theory.  Our own Dr. Spallone uses the l-adic topology in his own research all the time.

Here is an absolutely fantastic lecture by Dr. Ono where he explains all of this and much, much more.  He starts at the beginning and explains everything very clearly.  By the end, even the experts will learn something new!  It’s an excellent way to spend an hour on this snowy day.