Slashdot stories can be listened to in audio form via an RSS feed, as read by our own robotic overlord.

typodupeerror

## Euler's Partition Function Theory Finished117

Posted by Soulskill
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."
This discussion has been archived. No new comments can be posted.

## Euler's Partition Function Theory Finished

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

on Friday January 21, 2011 @04:33PM (#34959268)

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)

by Anonymous Coward

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)

on Friday January 21, 2011 @04:35PM (#34959318) Homepage Journal

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.

ASL?

• #### Re: (Score:2)

Just being funny. Im married myself.
• #### Re: (Score:2)

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

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

Nope, haven't had a reason to learn it [wikipedia.org]; no deaf people in the family.
• #### 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.

• #### In English (Score:2)

So what does this mean and what does this give us in practical applications?
• #### Re:In English (Score:5, Insightful)

on Friday January 21, 2011 @04:46PM (#34959540) Journal

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)

on Friday January 21, 2011 @05:10PM (#34959916)
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.

• #### Re: (Score:3)

So, what you are saying is, I could use a 64bit int, fill it up with "1"s and I would know I have stored exactly 32 "3"s...

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)

on Saturday January 22, 2011 @01:17AM (#34963150)
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 :)

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

on Friday January 21, 2011 @06:28PM (#34960906) Homepage
Why should it gives us any practical applications right now or tomorrow? Do you know Boole was considered wasting his time when he put together the fundation of the boolean algebra which is a cornerstone of the logical circuitry? Do you know Maxwell was also considered wasting his time working on the unification of electrical and magnetic forces? Do you know Faraday was asked what the heck the electricity was for?

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)

Half of science is useless (but we never know which half until many centuries later. Far more than half of most other human endeavors are useless so science/math still is our best option.
• #### Re:In English (Score:5, Interesting)

on Friday January 21, 2011 @08:14PM (#34961756) Homepage Journal

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)

I think (and according to the article) this is a different partitioning algorithm they are talking about. Here partitioning represents a way of representing a number as a sum of other positive numbers. I can't see how this is relevant to statistics - this seems to be a pure number theory problem. Though, I suspect someone somewhere will connect this to cryptography or something. http://en.wikipedia.org/wiki/Partition_(number_theory) [wikipedia.org]
• #### 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)

on Friday January 21, 2011 @04:39PM (#34959396)
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: (Score:1)

Ono is one of 5 people responsible though, and the others were all postdocs (I think), so it's not out of the question for the work to lead to a Fields medal for someone.
• #### Re:Ageism strikes again (Score:5, Funny)

on Friday January 21, 2011 @05:36PM (#34960232) Homepage

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)

time to issue another fields 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)

on Friday January 21, 2011 @04:41PM (#34959432)
From the article:
"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.."

• #### Re: (Score:1)

by Anonymous Coward

...Somebody who throws killer parties?

• #### Re: (Score:2)

Also, somebody who is not a plebiean.

• #### Re: (Score:2)

*sigh* *whoosh* Why do you think I intentionally misspelled "plebeian"?
• #### 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)

I thought he meant this guy. [wikipedia.org]
• #### 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)

by Anonymous Coward

Thanks for the explaination.

• #### Re: (Score:2)

A Partician is:

A Roman nobleman? No, wait...
• #### Re: (Score:3)

A patrician is:

Vetinari

Bitch.

• #### Re: (Score:2)

So if we have a way to generate exact partition numbers, does any of this mean there might be an efficient way to find the partition number of for a value where each part is equal to the others? There's potential for an easier way to find prime numbers here.
• #### Hooo!EEEE! (Score:1)

Wow! Now I have something to talk about over brewskis between periods while we watch the Sabres/Islanders game 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)

I'll have you know, some of my best friends are mathematicians!
• #### Boy... (Score:3, Interesting)

on Friday January 21, 2011 @04:49PM (#34959586) Homepage

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.

• #### Okay (Score:1)

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

• #### Re: (Score:1)

Solving problems like this (#P problems that is) efficiently always involves counting solutions without actually enumerating them. Results like this might give insight into how to solve other #P problems or maybe even an efficient solution to a #P-complete problem, which would give us P=NP. Heady stuff, actually.
• #### Ken Ono is a great guy (Score:5, Interesting)

on Friday January 21, 2011 @05:05PM (#34959854)

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)

His wife will be so glad to hear that he spent so much time on them >_>
• #### 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)

Ha! Shouldn't that be "striking Eul(er) in mathematics"?

Thang you, thang you, I'll be here all week...

• #### Who solved it? (Score:2)

We say Ono, but he played a big part in it. Was one of the people in the group a janitor who felt he was smarter than everybody else and then walked in and solved the equation? I am pretty sure that is exactly how it went down. And the janitor's friend is Ben Affleck. I have no clue why Ben Affleck is friends with a janitor, but he is
• #### Better Link (Score:5, Informative)

on Friday January 21, 2011 @08:04PM (#34961690)

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

• #### 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)

I imagine most mathematicians would argue that anything that can be said in a single sentence in isolation is imprecise enough that they don't really care. I imagine the published paper will be more precise, and I encourage you to read it if you are interested in specifics. Otherwise, the point of the article is that fractals are useful, number theory has interesting and unsolved problems, and that mathematics requires more than sitting at a desk calculating things (as vague as these ideas might be).

#### Related LinksTop of the: day, week, month.

I have never seen anything fill up a vacuum so fast and still suck. -- Rob Pike, on X.

Working...