6
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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? $\endgroup$
    – Boris Bukh
    Commented Nov 8, 2009 at 8:49
  • $\begingroup$ 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)? $\endgroup$
    – Ilya Nikokoshev
    Commented Nov 8, 2009 at 13:46
  • $\begingroup$ As p(n) is an arithmetic function, he might be asking for the Dirichlet inverse (as in the Möbius inversion formula). $\endgroup$
    – Rob Harron
    Commented Nov 8, 2009 at 15:29
  • $\begingroup$ Not really relevant, but for the behavior of the asymptotic convergent formula in the complex plane, see mathoverflow.net/questions/366733. $\endgroup$
    – Richard Stanley
    Commented Sep 22, 2022 at 23:53

5 Answers 5

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – fedja
    Commented Nov 8, 2009 at 15:07
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

There was a question asking about extending the partition function to a continuous function on math.stackexchange a while ago. While there are infinitely many answers to this I believe "JM Ain't a Mathematician" was able to single out a particular sequence of such functions he felt was natural and in the limit of this sequence there appears to be a unique convex solution. See here: https://math.stackexchange.com/questions/34318/feeding-real-or-even-complex-numbers-to-the-integer-partition-function-pn

Now if you want to invert the partition function, what you could do is try to evaluate that limit function in the link as a taylor series and then apply the lagrange inversion theorem to get your inverse partition function.

You might even be able to end up with a relation on the entire complex plane this way.

Improve this answer
$\endgroup$
1
$\begingroup$

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?

Improve this answer
$\endgroup$
1
  • $\begingroup$ "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. $\endgroup$
    – Michael Lugo
    Commented Nov 8, 2009 at 17:45
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – fedja
    Commented Nov 8, 2009 at 19:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .