[math-fun] approximate partition formula
I always have trouble recalling the formula for the number of partitions of N. Here's a simple approximation: partition(N) ~= 13^sqrt(N) / 7N Rich
Nice approximation. Speaking of which, is there some heuristic reason the Hardy-Ramanujan asymptotic formula for the partition function p(n) ~ exp(pi sqrt(2n/3)) / (4 sqrt(3) n). or its general form p(n) ~ A^sqrt(n) / (B*n) for some A, B in (0,oo) ought to be true? --Dan On Jun 4, 2014, at 5:04 PM, rcs@xmission.com wrote:
I always have trouble recalling the formula for the number of partitions of N. Here's a simple approximation:
partition(N) ~= 13^sqrt(N) / 7N
On 05/06/2014 07:15, Dan Asimov wrote:
Speaking of which, is there some heuristic reason the Hardy-Ramanujan asymptotic formula for the partition function
p(n) ~ exp(pi sqrt(2n/3)) / (4 sqrt(3) n).
or its general form
p(n) ~ A^sqrt(n) / (B*n) for some A, B in (0,oo)
ought to be true?
It seems to me that any argument that doesn't pin down the value of A is going to have real trouble seeing that the 1/n factor is there. If that intuition is right then I think you have to either shoot for something that gets the right A (which seems kinda unlikely to drop out of anything easy) or else accept, e.g., an argument that merely explains why log p(n) is roughly proportional to sqrt(n). Is there such an argument? Maybe it goes like this: "Most" partitions of n are into "about sqrt(n)" parts of size "about sqrt(n)" (is that true? it seems like it might be, on the basis of super-handwavy intuitions about Ferrers diagrams). The number of ways to choose about sqrt(n) numbers of size about sqrt(n) is about sqrt(n)^sqrt(n), whose log is of order sqrt(n) log(n). Now, that's too big for two reasons: firstly, order doesn't matter so we need to divide by about sqrt(n)! which is about sqrt(n)^sqrt(n)/exp(sqrt(n)); secondly, the sum needs to be exactly n rather than some arbitrary thing of order about n, so we need to divide by about n. On the face of it this gives you exp(sqrt(n))/n (!) but I think that's mostly (perhaps entirely) bullshit -- everything here arises from quotients of much bigger things, and I suspect that if you do the calculations correctly but without lots of sophisticated analysis what actually happens is that all you have is an error term :-). -- g
On Jun 5, 2014, at 2:15 AM, Dan Asimov <dasimov@earthlink.net> wrote:
Nice approximation.
Speaking of which, is there some heuristic reason the Hardy-Ramanujan asymptotic formula for the partition function
p(n) ~ exp(pi sqrt(2n/3)) / (4 sqrt(3) n).
or its general form
p(n) ~ A^sqrt(n) / (B*n) for some A, B in (0,oo)
ought to be true?
--Dan
A and B are related to the asymptotic behavior of an analytic function at a particular point where its first derivative vanishes, a “saddle point”. A is related to the location of the saddle, and B is related to the second derivative at that point. Here is the function: f(z) = 1/z^(n+1) \prod_{k=1}^\infty 1/(1-z^k) The infinite product is Euler’s generating function for partitions. By integrating f(z) on a closed contour that circles around the origin (and dividing out 2 pi i) you get p(n). For asymptotics you deform the contour so that it passes over the saddle point z*, f’(z*)=0, on the real axis between 0 and 1. For large n you find z* ~ exp(-sqrt(pi^2/(6n))). From that you get A, and with a bit more work (Taylor expanding log f(z) to second order about z*) you get B. The pi^2/6 comes from the sum 1+1/2^2+1/3^2+ … This asymptotic math is mirrored in a statistical analysis where you say partitions for large n have a typical “shape”, and you maximize the entropy with respect to that shape. -Veit
participants (4)
-
Dan Asimov -
Gareth McCaughan -
rcs＠xmission.com -
Veit Elser