Integer Partitions M.V.N. Murthy, The Institute of Mathematical Sciences, Chennai Many of you may have seen the recent film The Man who knew Infinity. The film deals with the life of the famous mathematician, Srinivasa Ramanujan. In one dramatic sequence in the film there is a conversation between Ramanujan and another mathematician, Major P.A. MacMahon, in the presence of another mathematician, G.H. Hardy, about partitions. So what are these partitions and what were they talking about? What are partitions Integer partitions is an important part of a larger field in mathematics called Number Theory to which Hardy and Ramanujan made very important contributions. Let us first start with the definition of partitions. Consider any positive integer n, n=1,2,3,... This can always be written as a sum of positive integers less than n. The number of ways in which n can be written as a sum of positive integers less than n is called as the partition of n and is denoted as p(n). Here are some examples: Of course we take it for granted that 2+1 and 1+2 are the same and therefore the partitions are written as a non-increasing sum of positive integers. Here are a few more: You can easily check that number of possibilities and hence the partition, starts growing very fast, in fact exponentially. These are very large numbers which can be calculated in recent times using powerful computers but not during the time of Ramanujan nearly a century ago. Generating functions As it happens, Leonhard Euler had already made some progress in computing these partitions more than hundred years before Ramanujan. In number theory results for large n are usually expressed as formulae or generating functions. A generating function is represented as a power series: This is a series in powers of x and hence it is called---no marks for guessing this---a power series. The dots simply mean that you can go on adding terms in increasing powers of x with appropriate coefficients. The last part of the equation is a short-hand notation for writing the power series. The strange symbol is called Sigma and f(n) is the coefficient of each power which can be any real number. The symbol Sigma stands for summation, and the limits of the summation are given as n=1 to infinity. It indicates that the series is written by summing over terms where n goes from 1 to infinity. Here is an example of a series: The right hand side is true if and only if x lies between 0 and 1: 0 where we simply replaced x by x^2 and x^3 respectively. These series are examples of what is called a geometric series. Suppose we multiply these three series as follows: We get Notice that the coefficients of powers of x are 1,2,3, omitting the first entry which always 1. Let us continue in the same manner with four terms: Now the coefficients of powers of x up to x^4 are 1,2,3,5. With five terms we get Now the coefficients of powers of x up to x^5 are 1,2,3,5,7. You can see a pattern emerging. The coefficients are simply the partitions of integers up to 5 as given in the beginning. Therefore to get the partitions up to p(n), all we need to multiply in the denominator terms like (1-x) up to (1-x^n); since n can be as large as we want, we can write a very general formula like The middle part of the equation is just a short form of writing the products that are in the left hand side (LHS) of this equation. Just as there is a symbol for summation, there is also a symbol for product which is called Pi. The LHS is usually called the generating function of partitions since when expanded each power of x gives the partition of that power. Calculating the partitions Though Euler outlined the general method of generating functions, actual calculation of partitions was left to another mathematician, Percy Alexander MacMahon. MacMahon was a contemporary of Hardy but had earlier served in the army including a stint in Madras in the 1870s. He had the reputation of being a great calculator. He put his skills to good use for calculating the integer partitions using the method given by Euler. It was not straight forward as you can easily check by taking n to be even as small as 20, let us say. There were no calculators and every thing had to be done by hand. He did this by using yet another result of Euler related to what is called Euler's Pentagonal Numbers using which one can get a recursion relation for integer partitions. A recursion relation is one in which if you know some partitions for small n, it can be successively used to calculate partitions of larger integers. MacMahon laboriously prepared a table of integer partitions, up to about n=100 or so, which became a benchmark to check any result on partitions during his times. Approximation Methods Unlike most mathematicians of his time, Ramanujan was not averse to trying out approximations, especially when the answer involved large numbers like in integer partitions. You first start by getting the order of magnitude of the answer, to which you can keep on adding successively smaller corrections. With each correction term the error keeps reducing. This is now part of a well known field called Asymptotic Approximation Methods but was not very popular during the time of Ramanujan. Hardy and Ramanujan started with the Euler's generating function, using a method that they invented (which came to be known as the Circle Method) he obtained an approximation for integer partition p(n) given by where e=2.718281828459045... is the well-known constant called the Euler constant (see box for more details). It is one of the transcendental numbers like pi. The formula above, though approximate, is extremely simple. It gives increasingly better approximation as n increases and we call such formula as an asymptotic formula. More significantly the formula given above can be evaluated, even without a calculator, to get the order of magnitude of p(n) for any n. In fact as the story goes, Ramanujan surprised MacMahon by giving the answer for the partition of 200. He took less than a day to calculate that p(200) is approximately equal to 4x10^{12}. The exact result, p(200)=3,972,999,029,388, would have taken weeks if not months for MacMahon to calculate using recurrence relations. Restricted Partitions The method used by Hardy and Ramanujan allows us to provide such approximations for integer partitions even with some restrictions. The integer partitions discussed above are called unrestricted partitions. However, we may further improvise by putting restrictions. For example Ramanujan considered partitions in which no integer occurs more than once in the sums. For example consider Notice that each integer is written as a sum without repetitions unlike earlier. These are called distinct partitions. It is not difficult to write the generating function for distinct partitions. It is given by The coefficients of each power of x is a distinct partition of the power itself. Once again Ramanujan came up with an asymptotic formula for approximately evaluating q(n) given by This is also surprisingly simple. Partitions with odd numbers onlys Another interesting case of integer partitions is the question: In how many ways can an integer be written as a sum of only odd numbers? This is the same as writing You may be surprised that up to 5, we find q(n)=o(n) just by inspection. Actually this is a very general result and in fact it is true for all n. Partitions using primes only You may also ask if one can partition an integer into sums of prime numbers. This is the additive equivalent of the prime number theorem which states that every positive integer can be written uniquely as a product of prime numbers and their powers. However, the partition is not unique, and one can approach the problem the same way as we have done above. An asymptotic answer to this question was found long after Ramanujan and is still a field of active investigation. Ramanujan himself generalised many of the ideas of integer partitions. He derived asymptotic approximations for partitioning an integer into sums of squares with and without repetitions. He improved the asymptotic formula of unrestricted integer partitions by including corrections terms. He played with integers and infinite series with relish. As mathematician Littlewood commented, integers were like Ramanujan's friends. He could do any thing he wished with them. Partitions and Physics The analysis of integer partitions by Hardy, Ramanujan and later mathematicians has a deep connection to Physics. Suppose you consider a volume of gas whose total energy is some E. You can ask the question how this energy is distributed among the individual molecules of the gas. This then becomes a problem of partitioning energy E, usually a real number instead of integers alone, among its components just as how an integer is partitioned as a sum of integers. This is a central problem in the field of Statistical Mechanics. The generating function in number theory is called the partition function in statistical mechanics.