32 ms·

Is there a simple/intuitive explanation why there is no simple closed form for p(n)?

by 3rd3 13y ago

j2kun 13y ago
This was considered a big breakthrough: http://www.aimath.org/news/partition/brunier-ono.pdf http://www.aimath.org/news/partition/brunier-ono.pdf Notice Theorem 1.1 gives a nice formulation, but unfortunately Tr(n) is really difficult to describe.
monochromatic 13y ago
In general, it is only by coincidence when something does have a nice closed form.
- 3rd3 13y ago
  But finding all partitions seems like a simple combinatorial problem at first sight.
  - Someone 13y ago
    Firstly, "closed form" is not objectively defined. Do you include infinite sums? Bernoulli numbers? Euler's constant? etc (http://www.ams.org/notices/201301/rnoti-p50.pdf http://www.ams.org/notices/201301/rnoti-p50.pdf). If you wanted to, you could call p(n) a closed form for p(n). You cannot call that cheating. In the past, we similarly introduced n!, n^n, and n!!!!!!!!!n and, going further back, even n*n and n+n as shorthands for more cumbersome expressions (n^2 is sum(1,n;n)) So, I think you aren't asking for a closed form, but for an easy way to compute p(n). p(n) is trivially defined recursively (a way is with a helper function p(n,m) for the number of partitions of n where each number in the partition is at least equal to m). The only difference is that that trivial definition has an enormous branching factor. That's where number theorists come in. They manage to replace that rapidly branching method with easier ones, where it often isn't clear that For example, see https://oeis.org/wiki/Partition_function#Partition_function_formula https://oeis.org/wiki/Partition_function#Partition_function_.... It states p(n) equals an infinite sum of some seemingly hideous function containing derivatives, sinh, square roots, etc. Evaluating that does not involve branching, though. That can make it much faster to approximate such a function by 'only' iterating until you know you are within 0.5 of the real answer. That must be an integer, so if you are within 0.5, rounding gives you the correct answer. That's what this computation did, too, for a different formula.
IsTom 13y ago
Generally, there are infinitely more things that don't have a closed form at all than things that do.

Is there a simple/intuitive explanation why there is no simple closed form for p(n)?

by 3rd3 13y ago

Is there a simple/intuitive explanation why there is no simple closed form for p(n)?

j2kun 13y ago

This was considered a big breakthrough: http://www.aimath.org/news/partition/brunier-ono.pdf http://www.aimath.org/news/partition/brunier-ono.pdf Notice Theorem 1.1 gives a nice formulation, but unfortunately Tr(n) is really difficult to describe.

monochromatic 13y ago

In general, it is only by coincidence when something does have a nice closed form.

3rd3 13y ago
But finding all partitions seems like a simple combinatorial problem at first sight.
- Someone 13y ago
  Firstly, "closed form" is not objectively defined. Do you include infinite sums? Bernoulli numbers? Euler's constant? etc (http://www.ams.org/notices/201301/rnoti-p50.pdf http://www.ams.org/notices/201301/rnoti-p50.pdf). If you wanted to, you could call p(n) a closed form for p(n). You cannot call that cheating. In the past, we similarly introduced n!, n^n, and n!!!!!!!!!n and, going further back, even n*n and n+n as shorthands for more cumbersome expressions (n^2 is sum(1,n;n)) So, I think you aren't asking for a closed form, but for an easy way to compute p(n). p(n) is trivially defined recursively (a way is with a helper function p(n,m) for the number of partitions of n where each number in the partition is at least equal to m). The only difference is that that trivial definition has an enormous branching factor. That's where number theorists come in. They manage to replace that rapidly branching method with easier ones, where it often isn't clear that For example, see https://oeis.org/wiki/Partition_function#Partition_function_formula https://oeis.org/wiki/Partition_function#Partition_function_.... It states p(n) equals an infinite sum of some seemingly hideous function containing derivatives, sinh, square roots, etc. Evaluating that does not involve branching, though. That can make it much faster to approximate such a function by 'only' iterating until you know you are within 0.5 of the real answer. That must be an integer, so if you are within 0.5, rounding gives you the correct answer. That's what this computation did, too, for a different formula.

IsTom 13y ago

Generally, there are infinitely more things that don't have a closed form at all than things that do.