![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Thoughts on Ramanujan's Birthday
Dec. 22nd, 2021 10:56 amToday was mathematician Srinivasa Ramanujan's birthday. A lot of people have heard of him (especially in the context of the 1729 story). I want to talk about a different result of his, and then ask a related question.
A partition of a natural number is a way of writing a natural number as the sum of a bunch of numbers where we do not care about the order of the sum. For example, 8 = 4 + 2 + 2 gives a partition of 8, and we regard 2 + 4 +2 and 2 + 2 + 4 as the same partition. (Exercise: Find all the partitions of 5. You should find 7 of them.) Ramanujan studied the number of partitions of a given number n, which we write as p(n).
Ramanujan noticed, and proved an intriguing pattern about partitions. In particular, he proved that if you have a number n which leaves a remainder of 4 when divided by 5, then p(n) is divisible by 5. For example, p(4) = 5, and p(9) = 30.) Since that discovery, Ramanujan and then other people went gone on to prove similar relationships with other numbers other than 5. For example, Ramanujan proved that p(7t + 5) leaves a remainder of 0 when divided by 7. Frustratingly, we don't have any similar results for 2 or 3 although we have similar results for other primes. We can't even prove that there are infinitely many n where p(n) is even.
Another aspect where Ramanujan worked on the partition function was approximating p(n). When a function grows, mathematicians like to estimate its growth rate. For example, there's a famous result that the nth prime number for large n is very close to n ln n . Ramanujan with G. H. Hardy proved a result that says that essentially p(n) grows roughly like an exponential to a square root of n.
This is weird. Growth rates don't normally look like that. To some extent though, the partition function is forced to have a weird growth rate because it must have a growth faster than any polynomial but slower than any exponential. To see why it has to grow faster than polynomial think about the function p(k,n) which looks at how many partitions n has into numbers which are at most k. Note that p(1, n) = 1, since, the only way to write n as a sum of 1s is to just write n = 1 + 1 +1 ... +1. But, now, p(2,n) will grow roughly like n/2, because we have p(2,n) = p(1,n) + p(1, n-2) + p(1, n-(2+2)) ... . Similarly, then p(3,n) will grow quadratically, like a constant times n^2, since p(3,n) = p(2, n) + p(2,n-3) + p(2, n - (3+3+3))... In general then p(k,n) will grow roughly like n^(k-1).
Here's my question then: Is there any similarly straightforward and simple proof that p(n) grows slower than any exponential? It is trivially bounded above by 2^n, since the number of ways of breaking n down into a sum where we do care about the order is 2^n. However, I don't know of a similarly simple argument that it has to grow slower than any exponential. There's a not too difficult proof in Apostol's "Introduction to Analytic Number Theory" that shows that the growth is at most roughly the correct growth rate, but that involves using generating functions and then doing calculus on the generating functions. I'm hoping for some simple combinatorial argument here.
A partition of a natural number is a way of writing a natural number as the sum of a bunch of numbers where we do not care about the order of the sum. For example, 8 = 4 + 2 + 2 gives a partition of 8, and we regard 2 + 4 +2 and 2 + 2 + 4 as the same partition. (Exercise: Find all the partitions of 5. You should find 7 of them.) Ramanujan studied the number of partitions of a given number n, which we write as p(n).
Ramanujan noticed, and proved an intriguing pattern about partitions. In particular, he proved that if you have a number n which leaves a remainder of 4 when divided by 5, then p(n) is divisible by 5. For example, p(4) = 5, and p(9) = 30.) Since that discovery, Ramanujan and then other people went gone on to prove similar relationships with other numbers other than 5. For example, Ramanujan proved that p(7t + 5) leaves a remainder of 0 when divided by 7. Frustratingly, we don't have any similar results for 2 or 3 although we have similar results for other primes. We can't even prove that there are infinitely many n where p(n) is even.
Another aspect where Ramanujan worked on the partition function was approximating p(n). When a function grows, mathematicians like to estimate its growth rate. For example, there's a famous result that the nth prime number for large n is very close to n ln n . Ramanujan with G. H. Hardy proved a result that says that essentially p(n) grows roughly like an exponential to a square root of n.
This is weird. Growth rates don't normally look like that. To some extent though, the partition function is forced to have a weird growth rate because it must have a growth faster than any polynomial but slower than any exponential. To see why it has to grow faster than polynomial think about the function p(k,n) which looks at how many partitions n has into numbers which are at most k. Note that p(1, n) = 1, since, the only way to write n as a sum of 1s is to just write n = 1 + 1 +1 ... +1. But, now, p(2,n) will grow roughly like n/2, because we have p(2,n) = p(1,n) + p(1, n-2) + p(1, n-(2+2)) ... . Similarly, then p(3,n) will grow quadratically, like a constant times n^2, since p(3,n) = p(2, n) + p(2,n-3) + p(2, n - (3+3+3))... In general then p(k,n) will grow roughly like n^(k-1).
Here's my question then: Is there any similarly straightforward and simple proof that p(n) grows slower than any exponential? It is trivially bounded above by 2^n, since the number of ways of breaking n down into a sum where we do care about the order is 2^n. However, I don't know of a similarly simple argument that it has to grow slower than any exponential. There's a not too difficult proof in Apostol's "Introduction to Analytic Number Theory" that shows that the growth is at most roughly the correct growth rate, but that involves using generating functions and then doing calculus on the generating functions. I'm hoping for some simple combinatorial argument here.
