Inverting Ramanujan's partition function, p(N) - MathOverflow

Inverting Ramanujan's partition function, p(N)

2009-11-08T04:55:16Z

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).

[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 here ]

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.

What resources might be helpful? My apologies if I have missed something elementary.

Answer by engelbrekt for Inverting Ramanujan's partition function, p(N)

2009-11-08T06:05:52Z

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.

Answer by David Speyer for Inverting Ramanujan's partition function, p(N)

2009-11-08T13:42:53Z

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.

Answer by S. Carnahan for Inverting Ramanujan's partition function, p(N)

2009-11-08T17:42:06Z

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.

What sort of application do you have in mind?

Answer by Michael Lugo for Inverting Ramanujan's partition function, p(N)

2009-11-08T18:25:41Z

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(n) ~ exp(a sqrt(n))/bn

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

x = exp(z)/(b/a^2 * z^2)

Take logs of both sides to get

log x = z - C - 2 log z

where C = log(b/a^2) = log(6*sqrt(3)/Pi^2).

Let t = x*exp(C); then

log t = z - 2 log z.

Now we want the inverse of f(z) = z - 2 log z, viewed as a function from [2, ∞) to [2-2 log 2, ∞). (The function z -> z - 2 log z is decreasing on [0,2] and increasing on [2,∞].) Unfortunately I cannot find the right way to write this inverse. Presumably it involves the Lambert W function. 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.

Anyway, say this inverse is the function g, i. e. g(f(z)) = z and f(z) ≥ 2 for all z. Then we get

g(log t) = g(z - 2 log z) = z

and now recall that z = a * sqrt(y) and t = x * exp(C) to get

g(C + log x) = a*sqrt(y)

and solving for y,

y = (g(C + log x)/a)^2.

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.