13
$\begingroup$

Bruinier and Ono have found an algebraic formula for the partition function, which was widely reported to be a breakthrough. I am unable to understand the paper, but does it have any algorithmic consequences for fast computation of the partition function?

$\endgroup$
  • $\begingroup$ Can you please provide a link to the statement about the breakthrough? I would like to see in what sense is it a breakthrough. $\endgroup$ – Jernej Oct 27 '12 at 8:10
  • $\begingroup$ @Jernej It is a finite explicit formula for $p(n)$. Previously we had the Rademacher expansion, which is an infinite series, and various recursion formulas. $\endgroup$ – Yuval Filmus Oct 27 '12 at 15:48
5
$\begingroup$

It is my uninformed belief that Rademacher's formula is faster in practice (and perhaps in theory also) than the Bruinier and Ono formula. While Rademacher's asymptotic expansion is an infinite sum, we know that $p(n)$ is an integer, so if we have bounds on the tails of the expansion, we can use the formula to compute $p(n)$. According to Calkin et al., "the exact formula of Rademacher yields a very fast algorithm".

Bruinier and Ono describe what would take to implement their algorithm in Section 5 of their paper. The first step is to determine representatives for $\mathcal{Q}_n$, of which there are $h(-24n+1)$. According to Soundararajan, we should expect $h(-24n+1) = \Theta(n)$, so the formula would involve $\Theta(n)$ summands. That makes it worse than Euler's formula for $p(n)$ (computationally speaking), though the latter admittedly requires $\Omega(n)$ memory.

$\endgroup$
  • 2
    $\begingroup$ Indeed, I show in (1) that the Rademacher formula is theoretically quasi-optimal (and, heuristically, practically optimal) if implemented very carefully. $\endgroup$ – Fredrik Johansson Jan 13 '13 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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