## Euler's Partition Function Theory Finished 117

Posted
by
Soulskill

from the that-was-quick dept.

from the that-was-quick dept.

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."*
## Re: (Score:2, Offtopic)

## Re: (Score:3)

## Re:Mr. Ono... (Score:4, Funny)

## Re:Mr. Ono... (Score:5, Funny)

aaaand I can just hear my slashdot karma crashing down.

## Re: (Score:2)

Also, I'm geeky, but not geeky enough to understand all the math involved in this article. I just want to be able to contribute in some small way. Or something.

## Re: (Score:2)

## Re: (Score:2)

## It is about time (Score:3, Funny)

I was going crazy trying to figure a layout for the office.

## Fractal Euler (Score:2)

I was going crazy trying to figure a layout for the office.

I thought it was Fractal Euler's day off? Just relax.

## Re: (Score:2)

I was going crazy trying to figure a layout for the office.

Easy, just build around the pizza boxes.

## I guess I was using the wrong tool (Score:2, Funny)

Maybe fdisk wasn't the right approach to solve this problem.

## Re: (Score:2)

Maybe fdisk wasn't the right approach to solve this problem.

No one reads at 0 any more? Anonymous Coward made a funny!

## Re: (Score:2)

It's not that nobody ready it, it's that it wasn't that funny, and I am definitely a member of the target audience for the joke.

It got a "meh" from me, whereas the "Ono - Yoko - Apolo - Ohno" thread above produced a light chuckle.

## Fractals are sexy (Score:5, Funny)

Fractals are the mathematical thingie that turn me on the most in all of mathematics. The paisley pattern is natures tribute to the fractal, when executed correctly. Fractals make me hot, they really turn me on. Striking oil, even hotter.

## Re: (Score:2)

## Re: (Score:2)

ROFL, read the profile ;)

## Re: (Score:2)

## Re: (Score:2)

I will be too, when we get done having all this engagement fun ;)

## ASL is a sign of... (Score:2)

## Re: (Score:2)

Paizley did you say? Quite hot indeed.

;)

## Re: (Score:2)

Striking oil, even hotter.

Especially Mathematic Oil.

## Re: (Score:2)

What, no one is making the obvious oil / Euler joke? Tough crowd.

## Re: (Score:1)

paisley pattern?

Not sure what you're thinking of...

Not my fault that you are doing it wrong. ;)

## In English (Score:2)

## Re:In English (Score:5, Insightful)

So what does this mean and what does this give us in practical applications?

A new textbook version for another $150.00.

## Re:In English (Score:5, Informative)

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.

## Re: (Score:3)

Sorry, couldn't resist

## Re: (Score:1)

"flexible encoding schemes that make good use of those 64 bits." -- oh? do tell.

## Re:In English (Score:5, Informative)

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 :)

## Re:In English (Score:5, Insightful)

All pratical things begin with someone dreaming and working on useless things otherwise these discoveries wouldn't have been done if only practical purpose and necessity was the rule. I'm tired reading peoples always asking what it's for as if everything should have a pratical usage right away. We are talking about the foundations of reasoning here, we are talking about mathematics, not about engineering in case you didn't notice.

## Re: (Score:2)

Welcome to 2011, where instant gratification is 'everything' for better (or most likely) for worse.

## Re: (Score:2)

And this hunt for practical uses asap is what basically killed blue sky research in our post cold war world.

If it can not be packaged and sold for a profit 24 hours after it is discovered, it is ignored as worthless.

Oh, and was not the laser considered a usless exercise in physics once? The net of today would be very different without it...

## Re: (Score:2)

...was not the laser considered a usless exercise in physics once? The net of today would be very different without it...

Right, there wouldn't be any Youtube videos of cats chasing the little red dot from a laser pointer!~

## Re: (Score:3)

There's a brilliant historical example of this. G.H. Hardy, one of the foremost mathematicians of his day, once gave number theory and general relativity as examples of mathematical disciplines that were interesting in their own right, but which were unlikely to ever produce anything useful. Nowadays, relativity underpins the GPS system, and number theory provides the basis for a large amount of cryptography.

It just goes to show that you never can tell...

## Re: (Score:2)

Pfft. Who uses that stuff, anyway? Hardy was right.

## Re: (Score:1)

## Re:In English (Score:5, Interesting)

Well, in statistics it's pretty common to fit models to partitions of data, and the partitioning process gets ugly when the data set is large (in terms of classes of data, not in terms of the number of points in the data.) And translating from partition numbers to actual partitions is trivial. Speaking as a statistician who only deals with number theory on the (rare) occasions that it's directly relevant to my work, I have to say that the existing partitioning algorithms, although they work, strike me as inelegant, and I'd be happy to have something cleaner that can deal with an arbitrarily large number of classes of data in "O(something small)" time. I can see this speeding up model selection problems at least somewhat, although most of the computational expense will still be in actually fitting the models and calculating the relevant performance criteria.

## Re: (Score:2)

## Re: (Score:2)

If you have a set of k elements, and you know the set of all sequences (k_1, ..., k_m) such that k_1 + ... + k_m = k for all integers m between 1 and k, then it's pretty easy to go from that to the set of all partitions of the set. Finding the partition function of the size of the set is the first step in the set-partitioning algorithms I know of; there may be other ways to do it, of course, but I don't know what they are.

## Re: (Score:3)

No, it's exactly the same thing. It just looks different because in mathematics you aren't partitioning a pie, you are partitioning a number.

For example, the number 3 has the following positive integer partitions:

3

2+1

1+1+1

You can also define your partition in a decimal fraction if you wanted, in which case you would have an almost infinite number of partitions. It's basically just breaking a number up into related (but not necessarily equal) portions. The relation is determined by the smallest allowed un

## Ageism strikes again (Score:5, Informative)

## Re: (Score:1)

## Re:Ageism strikes again (Score:5, Funny)

He's too old? Is it time to start writing his eulergy?

## Common mispronounciation (Score:2)

He's too old? Is it time to start writing his eulergy?

Huh, I don't get it. The hell is an oil-er-gy?

I'm also not clear on why Ken Ono would be described as hitting good ol' Eul just for completing a theory of his:

...which is like striking oil in mathematics."

## Re: (Score:3)

but it's good news about ageism in another way: it has been said that if you don't make a contribution to mathematics by age 40, you never will (all the great discoveries in mathematics are by young mathematicians)

http://www.slate.com/id/2082960/ [slate.com]

so ono at least proves that geezer mathematicians can still do some groundbreaking stuff

## Re: (Score:2)

plaque[wikipedia.org]?## Re: (Score:1)

Which must be frustrating for him. As human life-span increases and anti-senescence treatments are found, how long before people give up on the idea that only young people can have good ideas?

## A Partician is: (Score:5, Interesting)

"a partition is a way of representing a natural number n as the sum of natural numbers (ie. for n = 3, we have three partitions, 3, 2 + 1, and 1 + 1 + 1, independent of order). Thus, the partition function, p(n), represents the number of possible partitions of n. So, p(3) = 3, p(4) = 5 (for n = 4, we have: 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1) , etc.."

Very interesting read.

## Re: (Score:1)

...Somebody who throws killer parties?

## Re: (Score:2)

## I believe you mean 'paTRician'... (Score:2)

http://en.wikipedia.org/wiki/Patrician [wikipedia.org]

## Re: (Score:2)

## Ah, you know... (Score:2)

Never ascribe to malice... and all that.

Partician-plebiean vs patrician-plebeian is a bit of a too subtle a joke for Slashdot.

Now, had you said something like "In Soviet Russia all particians are communist particians" or "I for one welcome our new partician overlords..."

## Re: (Score:2)

## Re: (Score:3)

I remember doing some stuff like that for Project Euler [projecteuler.net]. Man, if only I'd known there was an algebraic solution!

## Re: (Score:2)

too bad they turned off public profiles.. but here [projecteuler.net]

## Re: (Score:1)

Thanks for the explaination.

## Re: (Score:2)

A Partician is:A Roman nobleman? No, wait...

## Re: (Score:3)

A patrician is:

VetinariBitch.

## Re: (Score:2)

## Hooo!EEEE! (Score:1)

Sabres/Islandersgame tonight!Good thing, 'cause the economic impact of Hu Jintao's visit had pretty been hashed out already.

## Re: (Score:2)

You know, some of us actually enjoy having meaningful discussions with others.

## Re: (Score:2)

## Boy... (Score:3, Interesting)

This pattern allowed them to find a finite, algebraic formula...Yeah, but looking at the paper, still not that simple. Eventually someone will be able to program it into a function and I'll be able to call it in Matlab, but until then, I'd still be worried about making calculation errors. On the other hand, that may be saying more about my calculation skills than about the work...

## You're all missing the real story here (Score:1, Offtopic)

That being the blog author, Sarah Kavassalis, is insanely hot. I can't even tell what this theory means anyway.

## Re: (Score:1)

That's why she's hot.

## Re: (Score:1)

## Re: (Score:1)

## Re: (Score:1)

## Re: (Score:1)

## Re: (Score:2)

## Okay (Score:1)

Sooooo. Not being an uber math geek.... what the hell is this good for?

## Re: (Score:1)

## Ken Ono is a great guy (Score:5, Interesting)

Couldn't happen to a harder-working guy BTW, or a nicer one. I'll never forget him desperately writing the final draft of his wedding vows on the day of the ceremony.

## Re: (Score:3)

## Re: (Score:2)

Yeah, I think he fiddled with the margins and put them at 2.1 spacing to reach the page count, too.

## Striking oil? (Score:2)

Surely you meant, "striking Eul".

HTH.

## Striking oil? (Score:1)

"striking?Eul(er)in mathematics"Thang you, thang you, I'll be here all week...

## Who solved it? (Score:2)

## Better Link (Score:5, Informative)

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]

## But the important question is... (Score:1)

Does the solution fit in the margin? (I know different problem but it's ok :)

## They need to speak more clearly (Score:2)

Why must they repeatedly conflate partitions, partition counts, and sequences of partition counts? I can't tell what they're actually saying. First the article reads, "To be slightly more technical, from Ken Ono and Kathrin Bringman, 'A partition of a non-negative integer n is a non-increasing sequence of positive integers whose sum is n.' The concept is straight forward, but how to obtain these partition numbers, in general, is actually no trivial matter."

Then later, "...a finite, algebraic formula for p

## Re: (Score:2)