Math News Note

[Spherical Cow]

An interesting article, in case you missed it-

http://www.sciencedaily.com/releases...0120090950.htm

Norm

[CRGreathouse]

Yes, I saw that last week. Has anyone implemented their formula?

Personally (as much as I admire the mathematicians involved, esp. Ono) I find the hype overblown. The "finite formula" the article mentions is a sum of finitely many infinite sums, as far as I can tell. As to computational efficiency (theoretical or practical), I don't know.

[ATH]

Also P==NP ?
http://science.slashdot.org/story/11...T-Released-PNP


And in Physics, cold fusion?
http://www.physorg.com/news/2011-01-...ion-video.html

[fivemack]

Originally Posted by CRGreathouse

Yes, I saw that last week. Has anyone implemented their formula?

Personally (as much as I admire the mathematicians involved, esp. Ono) I find the hype overblown. The "finite formula" the article mentions is a sum of finitely many infinite sums, as far as I can tell. As to computational efficiency (theoretical or practical), I don't know.

It's a sum of finitely many things like modular functions, and modular functions can often be evaluated in terms of theta functions, which can be evaluated in terms of elliptic integrals, which can be evaluated very quickly using arithmetic-geometric mean techniques.

It looks as if the Euler recurrence takes about O(n^1.5) time to compute P(n); the partition numbers don't grow all that fast and all you need for the recurrence is addition and subtraction, but I'd still rather take my chances with the theta functions for PartitionNumber(10^10), which is of no more than about a hundred thousand digits.

[CRGreathouse]

Originally Posted by fivemack

It's a sum of finitely many things like modular functions, and modular functions can often be evaluated in terms of theta functions, which can be evaluated in terms of elliptic integrals, which can be evaluated very quickly using arithmetic-geometric mean techniques.

I just don't understand what makes it so philosophically special (the amount of words used in the article to talk about it as a "finite formula"). Like the Rademacher formula it uses infinite objects and inexact computation (that can, with numerical analysis, be made precise). And it's not like there was no finite, integer-only solution before -- consider the Euler's recurrence.

What practical importance it will have remains to be seen.

[fivemack]

I think the important result is that it doesn't intrinsically require inexact computation; if I read it correctly, you're evaluating modular functions at a finite number of special points where their values are exact algebraic numbers, and you can in principle work out the algebraic numbers by pure computational Galois theory, rather than (as Ono does in http://www.aimath.org/news/partition/brunier-ono) by calculating them to enough precision and doing lattice reduction to work out what the minimal polynomials are.

I'll admit that the Hilbert class field is a difficult object to work in, but there's a lot of work on computing efficiently with such objects that appeared in the nineties as a consequence of point-counting on elliptic curves.

[R.D. Silverman]

Originally Posted by fivemack

I think the important result is that it doesn't intrinsically require inexact computation; if I read it correctly, you're evaluating modular functions at a finite number of special points where their values are exact algebraic numbers, and you can in principle work out the algebraic numbers by pure computational Galois theory, rather than (as Ono does in http://www.aimath.org/news/partition/brunier-ono) by calculating them to enough precision and doing lattice reduction to work out what the minimal polynomials are.

I'll admit that the Hilbert class field is a difficult object to work in, but there's a lot of work on computing efficiently with such objects that appeared in the nineties as a consequence of point-counting on elliptic curves.

In particular, see:

http://www.jstor.org/pss/2153690

On the use of Weber modular forms. The Weber polynomials (as generators
of the class group) are very useful as well.

[fivemack]

Thanks very much for pointing me at that.

http://www.ams.org/journals/mcom/199...97-00854-5.pdf is a more useful reference since that's the whole text rather than the first page