Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
Math Science

Euler's Partition Function Theory Finished 117

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 More

Euler's Partition Function Theory Finished

Comments Filter:

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

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

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

  • 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.

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

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

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

    by Suki I ( 1546431 ) 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.

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

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

      by masterwit ( 1800118 ) * 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)

      by martin-boundary ( 547041 ) 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)

        by Longjmp ( 632577 )
        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 ;-)

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

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

          by martin-boundary ( 547041 ) 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)

      by AchilleTalon ( 540925 ) 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.

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

      • Re: (Score:2)

        by hitmark ( 640295 )

        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...

        • ...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!~

      • 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...

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

      by Daniel Dvorkin ( 106857 ) * 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.

      • 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]

        • 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.

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

    by Dr. Gamera ( 1548195 ) 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.)

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

    by Charliemopps ( 1157495 ) 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.."

    Very interesting read.
  • 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.

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

    by frank_adrian314159 ( 469671 ) 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...

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

  • Okay (Score:1)

    by kryliss ( 72493 )

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

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

    by GlobalEcho ( 26240 ) 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.

  • Surely you meant, "striking Eul".

    HTH.

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

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

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

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

    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]

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

  • 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

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

Slashdot Top Deals

This is clearly another case of too many mad scientists, and not enough hunchbacks.

Close