Euler's Partition Function Theory Finished

universegeek writes "Mathematician Ken Ono, from Emory, has solved a 250-year-old problem: how to exactly and explicitly generate partition numbers. Ono and colleagues were able to finally do this by realizing that the pattern of partition numbers is fractal (PDF). This pattern allowed them to find a finite, algebraic formula, which is like striking oil in mathematics."

Ageism strikes again

[Dr. Gamera]

Well, Ono can't win the Fields medal for it -- he's too old. (Born in 1968; you can't win the Fields medal after 40.)

Re:In English

[martin-boundary]

Suppose you have a large amount of data, and you've turned it into a whole lot of integers. You might not want to store the integers each in a full byte/word/double word, as you'd be wasting a lot of memory that way.

So you come up with a scheme where small integers are stored in a slot that only takes up the number of bits that they actually need. For example, the number 5 can be stored in 3 bits or more, and the number 3 can be stored in two bits or more, which is a far cry from the "standard" size of 64 bits per integer used on many computers these days.

The Euler partition function tells you in how many ways you can split 64 bits up into differently sized slots, which is great if you want to design flexible encoding schemes that make good use of those 64 bits.

Better Link

[GlobalEcho]

Here is a link that explains the whole discovery process much better:

http://esciencecommons.blogspot.com/2011/01/new-theories-reveal-nature-of-numbers.html [blogspot.com]

Re:In English

[martin-boundary]

There's a nice book on variable length encoding schemes by David Salomon. What I was thinking of was Anh and Moffat's Simple9 code (couldn't find a direct link), which goes like this: [davidsalomon.name]

Suppose you have 32 bits to play with, and you reserve 4 bits for bookkeeping, then you have 28 bits available for data. In Simple9, you partition the 28 bits in 9 equal sized slots (9 fits in 4 bits).

28 x 1 bit -> 28 numbers in the range 0-1
14 x 2 bit -> 14 numbers in the range 0-3
9 x 3 bit -> 9 numbers in the range 0-7
7 x 4 bit -> 7 numbers in the range 0-15
5 x 5 bit -> 5 numbers in the range 0-31
4 x 7 bit -> 4 numbers in the range 0-127
3 x 9 bit -> 3 numbers in the range 0-511
2 x 14 bit -> 2 numbers in the range 0-16383
1 x 28 bit -> 1 number in the range 0-268435455
----
9 different encodings -> fits in 4 bookkeeping bits.

This isn't space optimal, but it's not bad because 28 is divisible without remainder in nearly all of the cases. Moreover, it's fast to decode because it's just bit masks, and it offers localized random access whereas a lot of more efficient codes can only extract the data in order.

However, the partition function tells us how to fill the slots exactly! So in principle, if we reserve B bookkeeping bits for a number which describes a partion of the R = 64 - B remaining databits, then we should be able to decode those R bits with a template which is a function of the value stored in B. So, take a list of Euler partition numbers [numericana.com], compute the log2 of the values of p(R), calling it B, then see when R + B = 64.

For example, with R = 47, p(R) = 105558 which fits in B = 17 bits. So you can encode 105558 different partitions exactly in 47 bits, and use 17 bits to identify the actual partition being used.

Anyway, this is getting too long for slashdot :)