Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Check if I understand the question correctly: The convergent asymptotic expansion for p(n) presumably converges at non-integer values of n, it is that function, whose inverse is being sought, in a form some kind of asymptotic convergent formula. If my interpretation is correct, then is the question a pure curiosity, or is there a deeper reason for asking it? –  Boris Bukh Nov 8 '09 at 8:49
    
I'm really curious whether it's a question in itself or if you need to prove some other result (and what could it be)? –  Ilya Nikokoshev Nov 8 '09 at 13:46
    
As p(n) is an arithmetic function, he might be asking for the Dirichlet inverse (as in the Möbius inversion formula). –  Rob Harron Nov 8 '09 at 15:29
add comment

4 Answers

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.

share|improve this answer
    
The problem is exclusively how to figure out the domain. The "formula" for the inverse is as easy as the integer closest to the rough approximation you can get from the asymptotics. It is the same as with $x^5+5x$: if you want to invert it on positive integers, the formula for the inverse function is merely $y\mapsto [\sqrt[5]y]$ for all sufficiently large $y$. –  fedja Nov 8 '09 at 15:07
add comment

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.

share|improve this answer
add comment

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?

share|improve this answer
    
"Partitions with -1 colors" is a bit hard to interpret, although it's certainly correct. I'd call the coefficient of z^n in (1-z)(1-z^2)(1-z^3)... the (signed) difference between the number of partitions of n with an even number of parts and with an odd number of parts. –  Michael Lugo Nov 8 '09 at 17:45
add comment

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.

share|improve this answer
1  
You do not need to invert $z-2\log z$ exactly because the distances between integers are bounded from below, so it is enough to know $z$ up to $o(z^{-1})$ for large $u$, but $u+2\log u$ is accurate up to $u^{-1}\log u$ already and making just one more iteration, we get $z=u+2\log u+\frac {4\log u}{u}+O(u^-2\log u^2)$. What you really need to check is that other terms in the H-R-R are sufficiently small compared to the leading one to ensure that inverting the leading term is enough. –  fedja Nov 8 '09 at 19:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.