Slashdot Mirror
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."
I was going crazy trying to figure a layout for the office.
Maybe fdisk wasn't the right approach to solve this problem.
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.
Home of The Suki Series
I think Apolo Anton spells his last name "Ohno" anyway..
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.)
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.."
Very interesting read.
Ohno, I sure screwed that one up!
I've abandoned my search for truth; now I'm just looking for some useful delusions.
So what does this mean and what does this give us in practical applications?
A new textbook version for another $150.00.
We should start a new Slashdot and return control to the geeks. It actually wouldn't be that hard to get some users to
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...
That is all.
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.
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.
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
There are fewer illiterates than people who can't read.
Surely you meant, "striking Eul".
HTH.
2*3*3*3*3*11*251
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.
Achille Talon
Hop!
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
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.
The correlation between ignorance of statistics and using "correlation is not causation" as an argument is close to 1.
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...
Slashdot: news for Apple. Stuff that Apple.
I think you need to APOLOgize..
:)
aaaand I can just hear my slashdot karma crashing down.
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, 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 :)
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 unit (in the example above, a positive integer). This is how any non-random form of partitioning, mathematical in nature or not, works.
I frankly have a very hard time believing that the data partitions created for statistical modeling are going to be created at random, so the algorithm in TFA can almost certainly apply.
Partitions are a very elementary mathematical principle and therefore have a very wide range of applications. The problem with calculating them has always been similar to prime numbers (another elementary principle with very broad applications). "Solving" the partition problem is like writing an algorithm that can reliably and precisely generate prime numbers. It's huge.
Security is mostly a superstition... Avoiding danger is no safer in the long run than outright exposure. - Helen Keller
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).