Finite formula found for partition numbers

January 22, 2011 10:40 AM

New math theories reveal the nature of numbers [1,2] - "We prove that partition numbers are 'fractal' for every prime. These numbers, in a way we make precise, are self-similar in a shocking way. Our 'zooming' procedure resolves several open conjectures, and it will change how mathematicians study partitions." (/.|via)

BONUS

Fractals plus quantum mechanics equals chaos - "investigating the properties of light when it is confined to a fractal object"

Polynomial Time Code For 3-SAT Released - "This is not a P=NP paper."

posted by kliuless (45 comments total)

Nice post, that first eScienceCommons post does a good job explaining it if you give it a few paragraphs. I particularly like Ono's quotes making an analogy to astronomy.

What I'm missing is what the "fractal" part really means. I mean I understand conceptually, but what is the exact self-similarity in terms someone without a graduate degree in mathematics can understand? I didn't see any useful hints in the short paper.
posted by Nelson at 11:31 AM on January 22, 2011

The only thing I ever understood about partition numbers is:
The number of partitions of an integer into n addends is the same as the number of partitions of a number with greatest addend n.

This is because the Ferrers diagram of a partition can be read row-wise or column-wise.
posted by Obscure Reference at 11:36 AM on January 22, 2011

This kind of stuff is why I must learn some true mathematics before I die. I can sense the logic of what is going on here but I don't truly grasp it. However, the beauty inherent in these kinds of patterns is obvious to me.

Wonderful article, thank you!
posted by dubitable at 11:37 AM on January 22, 2011

They're fractal in the sense of being self-repeating in a precise way. There's structure to the way partitions grow, and Ono & Kent have defined it. A fractal may be infinitely complex, but you can still compute any arbitrary point of one exactly. Presuming this work holds, you can now exactly compute partitions for any given number.
posted by dephlogisticated at 11:46 AM on January 22, 2011

Any practical use for being able to compute partition numbers?
posted by empath at 11:49 AM on January 22, 2011 [1 favorite]

At the bottom of the second link:

*The physics tie in? Alright, so this is reaching, but here we go. Partitions are visualized using Young tableaus, and anyone in particle physics (see pdf for relevant introduction) has probably come across this, as well as other forms of group representation theory. Could an ability to always explicitly write down partition numbers translate to physics? I couldn’t ever imagine using groups so large that this could at all come into play… but, one could possibly draw some conclusions about the fractal nature of… ah, I give up.
posted by Blazecock Pileon at 11:56 AM on January 22, 2011

I've read about approximations of pi via an infinite series of added terms involving primes. So this appears to be a hint that you can map pi as a sum of fractals at different scales, and that suddenly makes the underpinnings of the universe feel more tangible than a patternless string of digits. A real mathematician should refute this and crush my dreams, please.
posted by hanoixan at 11:57 AM on January 22, 2011

Also, I'm reminded of Wolfram's "A New Kind of Science", which I never read, but the similar look of Young tableaus to cellular automata is interesting but probably nonsense.
posted by hanoixan at 12:01 PM on January 22, 2011

“We found a function, that we call P, that is like a magical oracle,” Ono says. “I can take any number, plug it into P, and instantly calculate the partitions of that number. P does not return gruesome numbers with infinitely many decimal places. It’s the finite, algebraic formula that we have all been looking for.”

Can someone identify this P function, and say how complex it is? What is its Big-O notation?
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 12:04 PM on January 22, 2011

"Any practical use for being able to compute partition numbers?"

Nah, this is just mathematicians dicking around, as usual.

Of course there are! But I'm afraid your tiny mind could never hope to comprehend them.
posted by Eideteker at 12:06 PM on January 22, 2011 [5 favorites]

Does it reveal the nature of numbers, or show a new pattern in an organizational attribute of numbers?
posted by StickyCarpet at 12:10 PM on January 22, 2011

That picture was somehow very heartening. Yay nerds!
posted by dunkadunc at 12:12 PM on January 22, 2011

Presuming this work holds, you can now exactly compute partitions for any given number.

Errata: for any given prime number.

Any practical use for being able to compute partition numbers?

Generally abstract mathematics doesn't concern itself much too much with practical applications. The field is generally about finding new relationships and developing mathematical tool sets. But every now and then, a theoretical physicist will use one of these tool sets to develop or advance a physical theory.
posted by dephlogisticated at 12:15 PM on January 22, 2011

Well yes, but often there are a lot of physicists sitting around going, well if only we could do 'X' and a whole bunch of things would follow from it.
posted by empath at 12:19 PM on January 22, 2011

I guess what I'm asking is if there are a bunch of isomorphic problems to this.
posted by empath at 12:21 PM on January 22, 2011 [1 favorite]

So this appears to be a hint that you can map pi as a sum of fractals at different scales

No.


Can someone identify this P function, and say how complex it is? What is its Big-O notation?

It appears in equation (1.3) of the Bruinier-Ono paper. It's an explicit function of a complex variable, which will grow exponentially fast as the imaginary part grows; when the imaginary part is held fixed and the real part varies, it's constant. The function is a modular form, though one of a rather exotic kind.


Does it reveal the nature of numbers, or show a new pattern in an organizational attribute of numbers?

Not totally sure what either question means, but I think it's more the latter.

Note that the "formula for the partition number" paper and the "fractal" paper are two separate papers.
posted by escabeche at 12:42 PM on January 22, 2011 [2 favorites]

So this appears to be a hint that you can map pi as a sum of fractals at different scales

What? What does this have to do with pi? This is about finding an algebraic solution to p(n) where p(n) is the number of ways you can partition n. But pi is not an integer, and not only that it's a transcendental number that is the root of no finite algebraic formula using rational numbers.

Anyway, I don't really know anything about this number theory stuff. I just started reading a book on the basics though.

This is one of those problems that people have been trying to solve for hundreds of years, in fact Euler worked on it and came up with a sum formation. But that would take a long time to do without a computer. I have no idea if this is important 'going forward' or just really impressive to other mathematicians.
posted by delmoi at 1:05 PM on January 22, 2011

Any practical use for being able to compute partition numbers?

Cryptography, data storage, network scheduling, and a host of other problems. this is a fundamentally important result in two ways. Combinatorics are at the heart of computer science, and until now counting/partition problems have relied on lookup tables and writing fast algorithms to give a reasonably good approximation. A proven method for calculating them correctly will not only save some computing time, but justifies a hardware implementation (ie getting built into chips rather than in software) because of its demonstrable mathematical correctness - it's not going to get further improved upon by a computer scientist any time soon, because it is already mathematically optimal.

The second way is the fractal nature of the result. I spent a longtime reading'/thinking about it yesterday and felt similarly frustrated by the difficulty of visualizing it - the press releases and blogs are too simplistic, while the math is too hard! Eventually I developed a basic understanding:-

1. the interesting numbers to partition are prime numbers.
1a. Compound numbers can be partitioned relatively easily once you know their prime factors, and
1b. Prime numbers are indivisible so the partition number of a prime is one way of looking 'inside' it. think of compound numbers as molecules and primes as atoms; partitioning is like splitting the atom and being able to make concrete statements about its interior structure.

2. Two numbers a and b are said to be congruent if they are both divisible by a third number c with no remainder. This is called modulo division, and is written as a ≡ b (mod c) = 0. For example, 15 ≡ 365 (mod 5) = 0; any number ending in 5 or 0 is evenly divisible by 5. Any number ending in 0 is evenly divisible by 10.
2a. Division by 10 is less interesting than division by 5, because the latter is a prime number.

3. The partition numbers of various different primes are congruent...
3a. ...not in random fashion, but forming distinct patterns...
3b. ...which repeat predictably...
3c. ...which means you can skip the time-consuming business of checking whether they are congruent or not.

A very simplistic example of the latter: you can look at 1,000,000 / 1,000 and quickly see 'oh a million divided by a thousand'. 986,049 / 993 = 993, but it's far less obvious even though 993 is only 7 less than 1000. You have to calculate it, whereas with the round numbers you can skip a lot of the arithmetic because you know that tens, hundreds, thousands etc. have a power relationship.

4. The fractal aspect means simply that if you plot the numbers on a chart, you will get the same shape whether the numbers are large or small. This has been extensively written about already, so I won't repeat it here.

5. The fractal congruency of prime partitions means that a predictable structure governs the distribution of the primes among the natural numbers. The structure has a shape that can be plotted on a chart. Such shapes are often referred to as strange attractors.

You know how there's a distinct 'mandelbrot' shape that many of us are familiar with? A new one is being feverishly plotted on computers in math departments right now, and will probably be known as the 'Ono set'. The significance of this will not be immediately apparent in the short term, but it answers such a basic question of number theory - how many different ways can you count up to the same number - that it will soon lead to a flood of new scientific results.
posted by anigbrowl at 1:13 PM on January 22, 2011 [28 favorites]

1. the interesting numbers to partition are prime numbers.
1a. Compound numbers can be partitioned relatively easily once you know their prime factors, and
1b. Prime numbers are indivisible so the partition number of a prime is one way of looking 'inside' it. think of compound numbers as molecules and primes as atoms; partitioning is like splitting the atom and being able to make concrete statements about its interior structure.

Not really. Partitioning is an additive thing, factorization into primes is a multiplicative thing. They don't play together very nicely. In particular, if you know the partition number of p and the partition number of q, this does not (as far as I know) help you determine the partition number of pq. I also know of no sense in which the list of partitions of a prime can be thought of as reflecting an "interior structure" -- for that matter, I don't know of any reasonable notion of "interior structure" of a prime.

Also, your definition of congruence in section 2 is incorrect; two numbers are congruent mod c if their DIFFERENCE is a multiple of c, not if BOTH are divisible by c.
posted by escabeche at 1:35 PM on January 22, 2011 [3 favorites]

escabeche, that was a much more elegant explanation than mine. I have some math software sitting about, but hadn't tried plotting this yet because my understanding of the 2 papers is obviously rudimentary - enough to id the trace and generative functions,, and understand the significance of the Hausdorff dimension bounding the periodicity in theorem 1.2 of the fractal paper, but...er...that's it. Reinstalling Mathematica or some fractal explorer and then plugging these functions in would probably take me a week.

To be blunt, have you tried plotting it yet - and if so, what does it look like? If not, what difficulties would you foresee?
posted by anigbrowl at 1:36 PM on January 22, 2011 [1 favorite]

I don't even know what you mean by "plotting it."
posted by escabeche at 1:43 PM on January 22, 2011

From the article: The physics tie in? Alright, so this is reaching, but here we go. Partitions are visualized using Young tableaus...

It's tableaux, dammit.

Also, as a combinatorialist who uses computer methods quite a lot, I'll just sat that this is most certainly a big deal, if/when it all pans out. I'm a little bit worried by the infinite sum/product formulas feeding into the simple formula in the three-page paper, so the usefulness of the final formula will come down to how computable those background functions are, which I admittedly have no idea about.
posted by kaibutsu at 2:00 PM on January 22, 2011

because the Ferrers diagram of a partition can be read row-wise or column-wise. factorization into primes is a multiplicative thing. an algebraic solution to p(n) where p(n) is the number of ways you can partition n. the significance of the Hausdorff dimension bounding the periodicity in theorem 1.2.

LOL WUT
posted by Makwa at 2:06 PM on January 22, 2011

escabeche Partitioning is an additive thing, factorization into primes is a multiplicative thing. They don't play together very nicely.

But:
x * y = x + x + x ... (repeated y times) = y + y + y ... (repeated x times)

Doesn't this imply that multiplication is just a particularly useful special case of addition? (And subtraction can of course be modelled as addition of negative numbers, and division can be modelled as multiplication by, or repeated addition of, 1/x.)

I also know of no sense in which the list of partitions of a prime can be thought of as reflecting an "interior structure" -- for that matter, I don't know of any reasonable notion of "interior structure" of a prime.

A prime is evenly divisible only by itself and 1. This implies that the list of partition numbers of a number N contains no string such that:
N = x + x + x ...
where all values x are of course equal.

So a method of easily generating the partition numbers of N, or as seems to be the case here, of displaying N vivisected in such a way that its partition numbers are obvious, is also a method of checking if N is prime. Isn't it? Perhaps the slowdown there is in the check stage, ie the question "does this line contain only identical partition numbers" may only be solvable by looking at the lines one at a time.
posted by aeschenkarnos at 2:06 PM on January 22, 2011

I'm not sure if there's really anything to plot. The mandlebrot set is on the complex plane, so that's a 2D surface to plot. But this is just in the natural numbers, so it's just on 1D line. There are ways to turn 1-D surfaces into 2D surfaces though.

But if there was something to look at, they would probably have included illustrations. But there might be some way represent the pattern visually, even if you have to 'cheat' somewhat...
posted by delmoi at 2:07 PM on January 22, 2011

Sorry about the stupid errors; I shouldn't try to explain things while I'm getting to grips with them. If you could humor me a little longer, is there anything to my intuition that the periodic orbits mentioned in remark (40 on Theorem 1.2 in the Folsom/Kent/Ono paper can be usefully mapped in the complex plane?
posted by anigbrowl at 2:08 PM on January 22, 2011

It should also be noted that the statement and proof of big results often simplify over time, partly as increased scrutiny helps find shorter paths through the proof, and also as the mathematical background changes to reflect the importance of the result in question. For example, Stokes' Theorem, which can be rather painful if proven in the language and methods available to, say, Stokes, has a two-line proof in Spivak's classic 'Calculus on Manifolds,' largely because the 'right' definitions were chosen in the preceeding pages.

It's hard to know at the moment, but this could be the kind of result that simplifies nicely over time, especially if it involves a fundamental new insight... Maybe less likely if it really is all just a pile of special functions theory...
posted by kaibutsu at 2:10 PM on January 22, 2011

'm not sure if there's really anything to plot. The mandlebrot set is on the complex plane, so that's a 2D surface to plot. But this is just in the natural numbers, so it's just on 1D line. There are ways to turn 1-D surfaces into 2D surfaces though.

You can just graph y=p(x), but from what I can tell, all that is going to be is a very steep curve.
posted by empath at 2:20 PM on January 22, 2011

I mentioned this to the math teacher wife, she then proceeded to give me a headache trying to explain it to me...

carry on..
posted by HuronBob at 2:43 PM on January 22, 2011 [1 favorite]

partitioning : addition :: factoring : multiplication
posted by LogicalDash at 2:54 PM on January 22, 2011 [1 favorite]

So partitions of prime numbers reveal a consistent pattern? Could this be used to calculate prime numbers?

Not math savvy, just trying to make conversation.
posted by jsturgill at 3:36 PM on January 22, 2011 [1 favorite]

I have no idea what any of you are talking about, but it sounds awesome.

If I'm grasping this correctly, would this potentially be a way to process large prime numbers more efficiently and possibly be of use in breaking certain kinds of cryptography?
posted by loquacious at 3:48 PM on January 22, 2011 [1 favorite]

So...no flying cars or antigravity devices yet, eh?

/goes back to ignoring math as much as possible
posted by Greg_Ace at 5:09 PM on January 22, 2011

aeschenkarnos: So a method of easily generating the partition numbers of N, or as seems to be the case here, of displaying N vivisected in such a way that its partition numbers are obvious, is also a method of checking if N is prime. Isn't it? Perhaps the slowdown there is in the check stage, ie the question "does this line contain only identical partition numbers" may only be solvable by looking at the lines one at a time.

Primality testing is something I know very, very little about, but generating all (really a subset) of partitions and checking those seems like it has to be one of the least efficient methods possible--it's probably slower than trying to divide n by everything (again a subset of everything) less than sqrt(n). Ono et al. haven't come up with a clever way of enumerating partitions, they've got a formula to tell you how many there are without enumerating (unless I missed the punchline entirely).
posted by hoyland at 5:14 PM on January 22, 2011

Generally abstract mathematics doesn't concern itself much too much with practical applications.

Luckily for math-heads, there are always a few physicists hanging around to realize enough practical applications from their fantasy worlds to keep the funds coming for a few more years. Like Lang Lang and Herbie Hancock, yet another example of symbiosis in the jaw-droppingly freaky zoo we call nature.
posted by Twang at 7:45 PM on January 22, 2011

Two numbers a and b are said to be congruent if they are both divisible by a third number c with no remainder

If their division has the same remainder. 6 is congruent to 11 mod 5.

a ≡ b mod m iff (∃x,y,z ∈ ℕ)(mx + z = a ∧ my + z = b)
posted by kenko at 8:06 PM on January 22, 2011

Analytic number theory is not my area of specialization, but I might be of some assistance in helping to clear up some questions upstream.

To say that something exhibits fractal behavior means that you can look at it at finer and finer scales or levels of resolution, infinitely fine, in fact, and the object will be self-similar at each scale. You see this in pictures of fractals like the Mandelbrot set, where no matter how much you zoom in, what you see at one resolution looks like what you would see at any other resolution.

In the case of the Folsom-Kent-Ono paper, they define a "stochastic process" to compute certain functions from which you can read off the partition numbers (for integers that are of a certain form). This means that you start at one state or initial step. Then to get to the next state/step, you have to make some sort of choice, which you make according to some probability distribution. You then repeat to get to each subsequent state/step.

I haven't read through the paper carefully enough to see exactly how the P_l(b;z) function they talk about is defined in terms of a stochastic process, nor how they get the partition function p(n) (at least for specific prime integers n) out of this generating function (a generating function, by the way, is any (usually nice continuous, real or complex variable) function that you can calculate and then read off some coefficients in order to get values of another thing that you are interested in, like a certain sequence of integers).

However, whenever you have stochastic processes, you can talk about orbits: what sequence of states you pass through if you start in a given initial state. You can talk about stuff like if the orbits tend to converge to some particular state (in the very, very long run), or if they keep alternating through some finite set of states, or if the orbits just hop around through all possible states without ever settling on one or a few preferred states.

To bring this back to fractals, if you have the same probabilities for your different choices at each step, then you get self-similarity: where, if all you know is your current state and the probability distribution for choosing the next state, you would have no idea what step you were at, because all of the steps look the same in that respect.

Hrm, was that at all helpful, or just creating more questions and confusion?

The new formula for the partition function is in the Brunier-Ono paper/announcement, on page 2, in the statement of Theorem 1.1, where it says "p(n) = ..." (p(n) is the partition number for an integer n). (It's defined in terms of all of the other previously listed functions, of course.)
posted by eviemath at 9:46 PM on January 22, 2011

This will make divvying up the bill at the restaurant easier, right? Ensures it's separated fairly among the diners?
posted by five fresh fish at 11:46 PM on January 22, 2011

Yes, it is obvious - this result is going to revolutionize Bistromatics.
posted by Dr Dracator at 12:33 AM on January 23, 2011 [1 favorite]

This result is a generalization of work by Funke and the first author...

And with the help of Teamocil.
posted by runcibleshaw at 3:29 AM on January 23, 2011

Two numbers a and b are said to be congruent if they are both divisible by a third number c with no remainder

If their division has the same remainder. 6 is congruent to 11 mod 5.

It sounds like a simpler way to say it would be that they belong to the same coset in the quotient group of ℤ/c. Unless I made a mistake.
posted by delmoi at 4:21 AM on January 23, 2011

delmoi, that's absolutely simpler, if you understand basic group theory. If you want to give a more elementary and accessible definition, eschabebe has a good one:

a ≡ b (mod c) if and only if c divides a - b,

which is, of course, equivalent to the definition you've given, since two integers would map to the same equivalence class in ℤ/cℤ if and only if their difference is in cℤ.

(Not trying to be snarky, just trying to bring it back to a level people not familiar with modern algebra can wrap their heads around. Incidentally, even though I'm a functional analyst by trade, I try to rephrase my problems in terms of algebra whenever I get the chance.)
posted by MidsizeBlowfish at 9:51 AM on January 23, 2011 [1 favorite]

go Ken Ono go!

The Rademacher formula is a wreck.
posted by oonh at 11:29 AM on January 23, 2011

Ken Ono: New Theories Reveal the Nature of Numbers (via mr)
posted by kliuless at 5:32 PM on February 3, 2011

I mentioned this to an acquaintance and he ended up writing an article-
Mathematics' Nearly Century-Old Partitions Enigma Spawns Fractals Solution
posted by bhnyc at 4:04 PM on February 8, 2011