Partition function (number theory): Difference between revisions

Revision as of 16:33, 13 September 2023

Latest revision as of 08:03, 10 August 2025

(21 intermediate revisions by 12 users not shown)

Line 1:

{{Short description|The number of partitions of an integer}}

{{CS1 config|mode=cs2}}

[[File:Ferrer partitioning diagrams.svg|thumb|The values <math>p(1), \dots, p(8)</math> of the partition function (1, 2, 3, 5, 7, 11, 15, and 22) can be determined by counting the [[Young diagram]]s for the partitions of the numbers from 1 to 8.]]

In [[number theory]], the '''partition function''' {{math|''p''(''n'')}} represents the [[number]] of possible [[PartitionInteger (number theory)partition|partitions]] of a non-negative integer {{mvar|n}}. For instance, {{math|1=''p''(4) = 5}} because the integer 4 has the five partitions {{math|1 + 1 + 1 + 1}}, {{math|1 + 1 + 2}}, {{math|1 + 3}}, {{math|2 + 2}}, and {{math|4}}.

No [[closed-form expression]] for the partition function is known, but it has both [[asymptotic analysis|asymptotic expansions]] that accurately approximate it and [[recurrence relation]]s by which it can be calculated exactly. It grows as an [[exponential function]] of the [[square root]] of its argument. The [[multiplicative inverse]] of its [[generating function]] is the [[Euler function]]; by Euler's [[pentagonal number theorem]] this function is an alternating sum of [[pentagonal number]] powers of its argument.

Line 8 ⟶ 9:

==Definition and examples==

For a positive integer {{math|''n''}}, {{math|''p''(''n'')}} is the number of distinct ways of representing {{mvar|n}} as a [[summation|sum]] of positive integers. For the purposes of this definition, the order of the terms in the sum is irrelevant: two sums with the same terms in a different order (e.g., {{math|1 + 1 + 2}} and {{math|1 + 2 + 1}}) are not considered to be distinct.

By convention {{math|1=''p''(0) = 1}}, as there is one way (the [[empty sum]]) of representing zero as a sum of positive integers. Furthermore {{math|1=''p''(''n'') = 0}} when {{mvar|n}} is negative.

Line 21 ⟶ 22:

p(10000) &= 36,\!167,\!251,\!325,\!\dots,\!906,\!916,\!435,\!144 \approx 3.61673\times 10^{106}

\end{align}</math>

{{As of|2022|June}}, the largest known [[prime number]] among the values of {{math|''p''(''n'')}} is {{math|''p''(1289844341)}}, with 40,000 decimal digits.{{r|caldwell}}<ref>{{citation |title=PrimePage Primes: p(1289844341) |url=https://primes.utm.edu/primes/page.php?id=130336 |website=primes.utm.edu |access-date=30 June 2022}}</ref> Until March 2022, this was also the largest prime that has been proved using [[elliptic curve primality proving]].<ref>{{citation |title=The Top Twenty: Elliptic Curve Primality Proof |url=https://primes.utm.edu/top20/page.php?id=27 |website=primes.utm.edu |access-date=30 June 2022}}</ref>

==Generating function==

Line 30 ⟶ 29:

<math display="block">\begin{align}

\sum_{n=0}^\infty p(n)x^n &= \prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right)\\

&=\left(1+x+x^2+x^3+\cdots\right) \left(1+x^2+x^4+x^6+\cdots\right)
\left(1+x^3+x^6+x^9+\cdots\right) \cdots \\

&=\frac{1}{1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - \cdots}\\

&=1 \Big/ \sum_{k=-\infty}^{\infty} (-1)^k x^{k(3k-1)/2}.

\end{align}</math>The equality between the products on the first and second lines of this formula is obtained by expanding each factor <math>1/(1-x^k)</math> into the [[geometric series]] <math>(1+x^k+x^{2k}+x^{3k}+\cdots).</math> To see that the expanded product equals the sum on the first line, apply the [[distributive law]] to the product. This expands the product into a sum of [[monomial]]s of the form <math>x^{a_1} x^{2a_2} x^{3a_3} \cdots</math> for some sequence of coefficients <math>a_i</math>, only finitely many of which can be non-zero. The exponent of the term is <math display="inline">n = \sum i a_i</math>, and this sum can be interpreted as a representation of <math>n</math> as a partition into <math>a_i</math> copies of each number <math>i</math>. Therefore, the number of terms of the product that have exponent <math>n</math> is exactly <math>p(n)</math>, the same as the coefficient of <math>x^n</math> in the sum on the left. Therefore, the sum equals the product.

\end{align}</math>

The equality between the products on the first and second lines of this formula

is obtained by expanding each factor <math>1/(1-x^k)</math> into the [[geometric series]] <math>(1+x^k+x^{2k}+x^{3k}+\cdots).</math>

To see that the expanded product equals the sum on the first line,

apply the [[distributive law]] to the product. This expands the product into a sum of [[monomial]]s of the form <math>x^{a_1} x^{2a_2} x^{3a_3} \cdots</math> for some sequence of coefficients

<math>a_i</math>, only finitely many of which can be non-zero.

The exponent of the term is <math display="inline">n = \sum i a_i</math>, and this sum can be interpreted as a representation of <math>n</math> as a partition into <math>a_i</math> copies of each number <math>i</math>. Therefore, the number of terms of the product that have exponent <math>n</math> is exactly <math>p(n)</math>, the same as the coefficient of <math>x^n</math> in the sum on the left.

Therefore, the sum equals the product.

The function that appears in the denominator in the third and fourth lines of the formula is the [[Euler function]]. The equality between the product on the first line and the formulas in the third and fourth lines is Euler's [[pentagonal number theorem]].

The exponents of <math>x</math> in these lines are the [[pentagonal number]]s <math>P_k = k(3k-1)/2</math> for <math>k \in \{ 0, 1,-1,2,-2,\dots\}</math> (generalized somewhat from the usual pentagonal numbers, which come from the same formula for the positive values {{nowrap|of <math>k</math>).}} The pattern of positive and negative signs in the third line comes from the term <math>(-1)^k</math> in the fourth line: even choices of <math>k</math> produce positive terms, and odd choices produce negative terms.

More generally, the generating function for the partitions of <math>n</math> into numbers selected from a set <math>A</math> of positive integers can be found by taking only those terms in the first product for which <math>k\in A</math>. This result is due to [[Leonhard Euler]].{{r|e}} The formulation of Euler's generating function is a special case of a [[q-Pochhammer symbol|<math>q</math>-Pochhammer symbol]] and is similar to the product formulation of many [[modular form]]s, and specifically the [[Dedekind eta function]].

Line 57 ⟶ 50:

coming from the nonzero values of <math>k</math> in the range

<math display="block"> - \frac{\sqrt{24n+1}-1}{6} \leq k \leq \frac{\sqrt{24n+1}+1}{6}.</math>

The recurrence relation can also be written in the equivalent form

<math display="block">

p(n) = \sum_{k = 1}^\infty (-1)^{k+1} \big(p(n-k(3k-1)/2) + p(n-k(3k+1)/2)\big) .

</math>

Another recurrence relation for <math>p(n)</math> can be given in terms of the [[divisor function|sum of divisors function]] {{math|''σ''}}:{{r|wilf}}

Line 246 ⟶ 243:

<ref name=aa>{{citation

| last1 = Al
| first1 = Busra

| last2 = Alkan
| first2 = Mustafa

| contribution = A note on relations among partitions

| pages = 35–39

| title = Proc. Mediterranean Int. Conf. Pure & Applied Math. and Related Areas (MICOPAM 2018)

| url = https://elibrary.matf.bg.ac.rs/handle/123456789/4699

| year = 2018}}</ref>

| access-date = 2018-12-17

| archive-date = 2024-04-27

| archive-url = https://web.archive.org/web/20240427205845/http://elibrary.matf.bg.ac.rs/handle/123456789/4699

| url-status = dead

| year = 2017}}</ref>

<ref name=ab>{{citation

| last1 = Ahlgren
| first1 = Scott

| last2 = Boylan
| first2 = Matthew

| doi = 10.1007/s00222-003-0295-6

| issue = 3

Line 265 ⟶ 271:

| url = https://www.math.sc.edu/~boylan/reprints/nomoreramafinal.pdf

| volume = 153

| year = 2003
| bibcode = 2003InMat.153..487A

| s2cid = 123104639

| access-date = 2018-12-17

| archive-date = 2008-07-19

| archive-url = https://web.archive.org/web/20080719184728/http://www.math.sc.edu/~boylan/reprints/nomoreramafinal.pdf

| url-status = dead

}}</ref>

Line 279 ⟶ 290:

<ref name=ao>{{citation

| last1 = Ahlgren
| first1 = Scott

| last2 = Ono
| first2 = Ken
| author2-link = Ken Ono

| bibcode = 2001PNAS...9812882A

| doi = 10.1073/pnas.191488598

Line 290 ⟶ 304:

| url = https://www.mathcs.emory.edu/~ono/publications-cv/pdfs/061.pdf

| volume = 98

| year = 2001
| pmid = 11606715

| pmc = 60793

| doi-access = free

| access-date = 2018-12-17

| archive-date = 2019-03-04

| archive-url = https://web.archive.org/web/20190304030350/http://www.mathcs.emory.edu/~ono/publications-cv/pdfs/061.pdf

| url-status = dead

}}</ref>

Line 310 ⟶ 329:

<ref name=bo>{{citation

| last1 = Berndt
| first1 = Bruce C.
| author1-link = Bruce C. Berndt

| last2 = Ono
| first2 = Ken
| author2-link = Ken Ono

| contribution = Ramanujan's unpublished manuscript on the partition and tau functions with proofs and commentary

| contribution-url = https://www.mathcs.emory.edu/~ono/publications-cv/pdfs/044.pdf

Line 319 ⟶ 342:

| title = The Andrews Festschrift (Maratea, 1998)

| volume = 42

| year = 1999}}</ref>

| access-date = 2018-12-17

| archive-date = 2019-03-04

<ref name=caldwell>{{citation

| archive-url = https://web.archive.org/web/20190304030309/http://www.mathcs.emory.edu/~ono/publications-cv/pdfs/044.pdf

| last = Caldwell | first = Chris K.

| url-status = dead

| title = The Top Twenty

}}</ref>

| url = https://primes.utm.edu/top20/page.php?id=54

| year = 2017}}</ref>

<ref name=e>{{citation

| last = Euler
| first = Leonhard
| author-link = Leonhard Euler

| journal = Novi Commentarii Academiae Scientiarum Petropolitanae

| language = la

Line 335 ⟶ 359:

| url = https://eulerarchive.maa.org/pages/E191.html

| volume = 3

| year = 1753}}</ref>

| access-date = 2018-12-17

| archive-date = 2023-08-05

| archive-url = https://web.archive.org/web/20230805000145/http://eulerarchive.maa.org//pages/E191.html

| url-status = dead

}}</ref>

<ref name=erdos42>{{citation