A zest of number theory

I just encountered an amazing number theoretic result. It is probably very well known, but for those who never saw it it’s quite something, so I thought I would share it.

Let n be a positive integer. A partition of n is a multiset of positive integers such that the sum of its elements is equal to n (for example \{1,1,2\} is a partition of 4). The partition function p(n) is defined as the number of partitions of n. The amazing result that I want to tell you about is the formula for the asymptotic equivalent of p(n). Before giving away the formula let’s try to get some intuition about the order of magnitude one can expect. For this let me first look at the simpler quantity q(n), defined as the number of multiset of [n] with n elements (for example q(2)=3). With the stars and bars argument (thanks to Luc Devroye for reminding me about this elementary combinatorial technique!) one can easily see that q(n) \geq 2^n-1. Moreover it is also easy to see that there is an injection from multisets of [\sqrt{n}] with \sqrt{n} elements to partitions of n (observe that the sum of the elements of such a multiset is necessarily smaller than n). Thus

    \[p(n) \geq q(\sqrt{n}) \geq 2^{\sqrt{n}}-1.\]

A more involved argument, based on Young Diagram representation of partitions, shows that p(n) \leq 2^{100 \sqrt{n}} (don’t quote me on the 100, I think it’s correct but I have only rough calculations here).

Now here we go for the asymptotic formula, discovered by Hardy and Ramanujan in 1918:

    \[p(n) \sim \frac{1}{4 \sqrt{3} n} \exp\left(\pi \sqrt{2 n /3}\right) .\]

In my opinion this is a beautiful connection between \pi, e, and a basic property of integers. The proof is based on the circle method, an elementary technique in complex analysis (see here for the details).

This entry was posted in Theoretical Computer Science. Bookmark the permalink.

Leave a reply