Inverting Ramanujan's partition function, p(N) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T03:34:22Z http://mathoverflow.net/feeds/question/4597 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/4597/inverting-ramanujans-partition-function-pn Inverting Ramanujan's partition function, p(N) Everett Johnston 2009-11-08T04:55:16Z 2009-11-08T18:25:41Z <p>Would someone be so kind as to enlighten me as to whether the integer partition function, p(N), can be (or has been) inverted and where the inversion is recorded? I'm trying to avoid reinventing the wheel, so to speak; I've searched quite awhile and no luck (this function's inversion seems possible on the face of it).</p> <p>[For those unfamiliar, the partition function, p(N), is that function which generates the characteristic number of integer partitions unique to every positive integer. For example, p(4) = 5 because the number 4 can be expressed as a sum of integers in 5 non-duplicated ways: (1 + 1 + 1 + 1), (1 + 1 + 2), (1 + 3), (2 + 2), and (4). One can view Rademacher's refinement of the Hardy-Ramanujan formula <a href="http://wapedia.mobi/en/Partition_(number_theory)" rel="nofollow">here</a> ]</p> <p>I tried to crunch the inversion using Mathematica and Maple, but both symbol processors returned null (I'm not the best at using them). I didn't get anywhere even when I attempted the inversion of alternative representations of p(N) such as that found in "Simple alternative to the Hardy-Ramanujan-Rademacher formula for p(N)" by N.M. Chase. </p> <p>What resources might be helpful? My apologies if I have missed something elementary.</p> http://mathoverflow.net/questions/4597/inverting-ramanujans-partition-function-pn/4617#4617 Answer by engelbrekt for Inverting Ramanujan's partition function, p(N) engelbrekt 2009-11-08T06:05:52Z 2009-11-08T06:05:52Z <p>Nobody knows, and presumably nobody will ever know, the set of values of the partition function. But that set is the domain of the inverse that you seek. So the inverse cannot be known in the sense familiar from calculus. Nor is it at all likely that you could grind out a formula for it, since its closed-form expression by an infinite series is quite complex. For comparison, the inverse of the simple polynomial p(x) = x^5 + 5x is a perfectly nice smooth strictly increasing function whose domain is the real line, yet if you want a formula for this inverse, you have to resort to elliptic modular (Hermite) or hypergeometric (Birkeland) functions.</p> http://mathoverflow.net/questions/4597/inverting-ramanujans-partition-function-pn/4632#4632 Answer by David Speyer for Inverting Ramanujan's partition function, p(N) David Speyer 2009-11-08T13:42:53Z 2009-11-08T13:42:53Z <p>I'm not sure what sort of answer you'd be looking for. The partition function is not surjective, because it grows like $e^{A \sqrt{ n}}$ where $A$ is a constant I don't remember. Are you look for a method to tell which numbers $m$ are values of the partition function, and for such a number compute the $n$ such that $p(n)=m$? There is no way that a question like that will be answered by a formula in the ordinary sense; I don't know how difficult a problem this is from an algorithmic standpoint.</p> http://mathoverflow.net/questions/4597/inverting-ramanujans-partition-function-pn/4651#4651 Answer by S. Carnahan for Inverting Ramanujan's partition function, p(N) S. Carnahan 2009-11-08T17:42:06Z 2009-11-08T17:42:06Z <p>I assume you're asking for an inverse function from a subset of the positive integers to all positive integers (just in case you're asking for the reciprocal of the partition generating function, it is essentially Dedekind's eta function - coefficients of this modular form count partitions with -1 colors). As others have mentioned, there is probably no hope of finding a "closed form" solution, but given a positive number m, there are efficient algorithms to find a value n such that p(n) is at least as close to m as p(k) for any k. This is because the Hardy-Ramanujan-Radmacher formula for p(n) (that you linked) converges quite rapidly.</p> <p>What sort of application do you have in mind?</p> http://mathoverflow.net/questions/4597/inverting-ramanujans-partition-function-pn/4660#4660 Answer by Michael Lugo for Inverting Ramanujan's partition function, p(N) Michael Lugo 2009-11-08T18:25:41Z 2009-11-08T18:25:41Z <p>Here's a partial solution. We want to find an approximate inverse of p(n). Recall the first term of the Hardy-Ramanujan-Rademacher expansion,</p> <p>p(n) ~ exp(a sqrt(n))/bn</p> <p>where a = Pi sqrt(2/3), b = 4 sqrt(3). So we want to solve x = exp(a sqrt(y))/(by) for y. Let z = a*sqrt(y), and this becomes</p> <p>x = exp(z)/(b/a^2 * z^2)</p> <p>Take logs of both sides to get</p> <p>log x = z - C - 2 log z</p> <p>where C = log(b/a^2) = log(6*sqrt(3)/Pi^2).</p> <p>Let t = x*exp(C); then</p> <p>log t = z - 2 log z.</p> <p>Now we want the inverse of f(z) = z - 2 log z, viewed as a function from [2, &infin;) to [2-2 log 2, &infin;). (The function z -> z - 2 log z is decreasing on [0,2] and increasing on [2,&infin;].) <b>Unfortunately I cannot find the right way to write this inverse.</b> Presumably it involves the <a href="http://en.wikipedia.org/wiki/Lambert_W_function" rel="nofollow">Lambert W function</a>. I have tried to use Maple to solve u = z - 2 log z, but for the values of u we're interested in this has two values of z as solutions and it keeps picking the wrong one.</p> <p>Anyway, say this inverse is the function g, i. e. g(f(z)) = z and f(z) &ge; 2 for all z. Then we get</p> <p>g(log t) = g(z - 2 log z) = z</p> <p>and now recall that z = a * sqrt(y) and t = x * exp(C) to get</p> <p>g(C + log x) = a*sqrt(y)</p> <p>and solving for y,</p> <p>y = (g(C + log x)/a)^2.</p> <p>This is the inverse of the first term of the H-R-R formula for p(n); that is, if you plug in p(n) for x, then you should get out something which is approximately n for y. </p>