# Partition function (number theory)

The values ${\displaystyle p(1),\dots ,p(8)}$ of the partition function (1, 2, 3, 5, 7, 11, 15, and 22) can be determined by counting the Young diagrams for the partitions of the numbers from 1 to 8.

In number theory, the partition function p(n) represents the number of possible partitions of a non-negative integer n. For instance, p(4) = 5 because the integer 4 has the five partitions 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, and 4.

No closed-form expression for the partition function is known, but it has both asymptotic expansions that accurately approximate it and recurrence relations 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.

Srinivasa Ramanujan first discovered that the partition function has nontrivial patterns in modular arithmetic, now known as Ramanujan's congruences. For instance, whenever the decimal representation of n ends in the digit 4 or 9, the number of partitions of n will be divisible by 5.

## Definition and examples

For a positive integer n, p(n) is the number of distinct ways of representing n as a 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 are not considered to be distinct.

By convention p(0) = 1, as there is one way (the empty sum) of representing zero as a sum of positive integers. Furthermore p(n) = 0 when n is negative.

The first few values of the partition function, starting with p(0) = 1, are:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, ... (sequence A000041 in the OEIS).

Some exact values of p(n) for larger values of n include:[1]

{\displaystyle {\begin{aligned}p(100)&=190,\!569,\!292\\p(1000)&=24,\!061,\!467,\!864,\!032,\!622,\!473,\!692,\!149,\!727,\!991\approx 2.40615\times 10^{31}\\p(10000)&=36,\!167,\!251,\!325,\!\dots ,\!906,\!916,\!435,\!144\approx 3.61673\times 10^{106}\end{aligned}}}

As of June 2022, the largest known prime number among the values of p(n) is p(1289844341), with 40,000 decimal digits.[2][3] Until March 2022, this was also the largest prime that has been proved using elliptic curve primality proving.[4]

## Generating function

Using Euler's method to find p(40): A ruler with plus and minus signs (grey box) is slid downwards, the relevant terms added or subtracted. The positions of the signs are given by differences of alternating natural (blue) and odd (orange) numbers. In the SVG file, hover over the image to move the ruler.

The generating function for p(n) is given by[5]

{\displaystyle {\begin{aligned}\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{aligned}}}
The equality between the products on the first and second lines of this formula is obtained by expanding each factor ${\displaystyle 1/(1-x^{k})}$ into the geometric series ${\displaystyle (1+x^{k}+x^{2k}+x^{3k}+\cdots ).}$ 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 monomials of the form ${\displaystyle x^{a_{1}}x^{2a_{2}}x^{3a_{3}}\cdots }$ for some sequence of coefficients ${\displaystyle a_{i}}$, only finitely many of which can be non-zero. The exponent of the term is ${\textstyle n=\sum ia_{i}}$, and this sum can be interpreted as a representation of ${\displaystyle n}$ as a partition into ${\displaystyle a_{i}}$ copies of each number ${\displaystyle i}$. Therefore, the number of terms of the product that have exponent ${\displaystyle n}$ is exactly ${\displaystyle p(n)}$, the same as the coefficient of ${\displaystyle x^{n}}$ 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 ${\displaystyle x}$ in these lines are the pentagonal numbers ${\displaystyle P_{k}=k(3k-1)/2}$ for ${\displaystyle k\in \{0,1,-1,2,-2,\dots \}}$ (generalized somewhat from the usual pentagonal numbers, which come from the same formula for the positive values of ${\displaystyle k}$). The pattern of positive and negative signs in the third line comes from the term ${\displaystyle (-1)^{k}}$ in the fourth line: even choices of ${\displaystyle k}$ produce positive terms, and odd choices produce negative terms.

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

## Recurrence relations

The same sequence of pentagonal numbers appears in a recurrence relation for the partition function:[7]

{\displaystyle {\begin{aligned}p(n)&=\sum _{k\in \mathbb {Z} \setminus \{0\}}(-1)^{k+1}p(n-k(3k-1)/2)\\&=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-p(n-22)-\cdots \end{aligned}}}
As base cases, ${\displaystyle p(0)}$ is taken to equal ${\displaystyle 1}$, and ${\displaystyle p(k)}$ is taken to be zero for negative ${\displaystyle k}$. Although the sum on the right side appears infinite, it has only finitely many nonzero terms, coming from the nonzero values of ${\displaystyle k}$ in the range
${\displaystyle -{\frac {{\sqrt {24n+1}}-1}{6}}\leq k\leq {\frac {{\sqrt {24n+1}}+1}{6}}.}$

Another recurrence relation for ${\displaystyle p(n)}$ can be given in terms of the sum of divisors function σ:[8]

${\displaystyle p(n)={\frac {1}{n}}\sum _{k=0}^{n-1}\sigma (n-k)p(k).}$
If ${\displaystyle q(n)}$ denotes the number of partitions of ${\displaystyle n}$ with no repeated parts then it follows by splitting each partition into its even parts and odd parts, and dividing the even parts by two, that[9]
${\displaystyle p(n)=\sum _{k=0}^{\left\lfloor n/2\right\rfloor }q(n-2k)p(k).}$

## Congruences

Srinivasa Ramanujan is credited with discovering that the partition function has nontrivial patterns in modular arithmetic. For instance the number of partitions is divisible by five whenever the decimal representation of ${\displaystyle n}$ ends in the digit 4 or 9, as expressed by the congruence[10]

${\displaystyle p(5k+4)\equiv 0{\pmod {5}}}$
For instance, the number of partitions for the integer 4 is 5. For the integer 9, the number of partitions is 30; for 14 there are 135 partitions. This congruence is implied by the more general identity
${\displaystyle \sum _{k=0}^{\infty }p(5k+4)x^{k}=5~{\frac {(x^{5})_{\infty }^{5}}{(x)_{\infty }^{6}}},}$
also by Ramanujan,[11][12] where the notation ${\displaystyle (x)_{\infty }}$ denotes the product defined by
${\displaystyle (x)_{\infty }=\prod _{m=1}^{\infty }(1-x^{m}).}$
A short proof of this result can be obtained from the partition function generating function.

Ramanujan also discovered congruences modulo 7 and 11:[10]

{\displaystyle {\begin{aligned}p(7k+5)&\equiv 0{\pmod {7}},\\p(11k+6)&\equiv 0{\pmod {11}}.\end{aligned}}}
The first one comes from Ramanujan's identity[12]
${\displaystyle \sum _{k=0}^{\infty }p(7k+5)x^{k}=7~{\frac {(x^{7})_{\infty }^{3}}{(x)_{\infty }^{4}}}+49x~{\frac {(x^{7})_{\infty }^{7}}{(x)_{\infty }^{8}}}.}$

Since 5, 7, and 11 are consecutive primes, one might think that there would be an analogous congruence for the next prime 13, ${\displaystyle p(13k+a)\equiv 0{\pmod {13}}}$ for some a. However, there is no congruence of the form ${\displaystyle p(bk+a)\equiv 0{\pmod {b}}}$ for any prime b other than 5, 7, or 11.[13] Instead, to obtain a congruence, the argument of ${\displaystyle p}$ should take the form ${\displaystyle cbk+a}$ for some ${\displaystyle c>1}$. In the 1960s, A. O. L. Atkin of the University of Illinois at Chicago discovered additional congruences of this form for small prime moduli. For example:

${\displaystyle p(11^{3}\cdot 13\cdot k+237)\equiv 0{\pmod {13}}.}$

Ken Ono (2000) proved that there are such congruences for every prime modulus greater than 3. Later, Ahlgren & Ono (2001) showed there are partition congruences modulo every integer coprime to 6.[14][15]

## Approximation formulas

Approximation formulas exist that are faster to calculate than the exact formula given above.

An asymptotic expression for p(n) is given by

${\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)}$ as ${\displaystyle n\to \infty }$.

This asymptotic formula was first obtained by G. H. Hardy and Ramanujan in 1918 and independently by J. V. Uspensky in 1920. Considering ${\displaystyle p(1000)}$, the asymptotic formula gives about ${\displaystyle 2.4402\times 10^{31}}$, reasonably close to the exact answer given above (1.415% larger than the true value).

Hardy and Ramanujan obtained an asymptotic expansion with this approximation as the first term:[16]

${\displaystyle p(n)\sim {\frac {1}{2\pi {\sqrt {2}}}}\sum _{k=1}^{v}A_{k}(n){\sqrt {k}}\cdot {\frac {d}{dn}}\left({{\frac {1}{\sqrt {n-{\frac {1}{24}}}}}\exp \left[{{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}}\,\,\,\right]}\right),}$
where
${\displaystyle A_{k}(n)=\sum _{0\leq m
Here, the notation ${\displaystyle (m,k)=1}$ means that the sum is taken only over the values of ${\displaystyle m}$ that are relatively prime to ${\displaystyle k}$. The function ${\displaystyle s(m,k)}$ is a Dedekind sum.

The error after ${\displaystyle v}$ terms is of the order of the next term, and ${\displaystyle v}$ may be taken to be of the order of ${\displaystyle {\sqrt {n}}}$. As an example, Hardy and Ramanujan showed that ${\displaystyle p(200)}$ is the nearest integer to the sum of the first ${\displaystyle v=5}$ terms of the series.[16]

In 1937, Hans Rademacher was able to improve on Hardy and Ramanujan's results by providing a convergent series expression for ${\displaystyle p(n)}$. It is[17][18]

${\displaystyle p(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty }A_{k}(n){\sqrt {k}}\cdot {\frac {d}{dn}}\left({{\frac {1}{\sqrt {n-{\frac {1}{24}}}}}\sinh \left[{{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}}\,\,\,\right]}\right).}$

The proof of Rademacher's formula involves Ford circles, Farey sequences, modular symmetry and the Dedekind eta function.

It may be shown that the ${\displaystyle k}$th term of Rademacher's series is of the order

${\displaystyle \exp \left({\frac {\pi }{k}}{\sqrt {\frac {2n}{3}}}\right),}$
so that the first term gives the Hardy–Ramanujan asymptotic approximation. Paul Erdős (1942) published an elementary proof of the asymptotic formula for ${\displaystyle p(n)}$.[19][20]

Techniques for implementing the Hardy–Ramanujan–Rademacher formula efficiently on a computer are discussed by Johansson (2012), who shows that ${\displaystyle p(n)}$ can be computed in time ${\displaystyle O(n^{1/2+\varepsilon })}$ for any ${\displaystyle \varepsilon >0}$. This is near-optimal in that it matches the number of digits of the result.[21] The largest value of the partition function computed exactly is ${\displaystyle p(10^{20})}$, which has slightly more than 11 billion digits.[22]

## Strict partition function

### Definition and properties

If no summand occurs repeatedly[23] in the affected partition sums, then the so called strict partitions are present. The function Q(n) gives the number of these strict partitions in relation to the given sum n. Therefore the strict partition sequence Q(n) satisfies the criterion Q(n) ≤ P(n) for all ${\displaystyle n\in \mathbb {N} _{0}}$. The same result[24] results if only odd summands[25] may appear in the partition sum, but these may also occur more than once.

### Exemplary values of strict partition numbers

Representations of the partitions:

Exemplary values of Q(n) and associated number partitions
n Q(n) Number partitions without repeated addends Number partitions with only odd addends
0 1 () empty partition () empty partition
1 1 (1) (1)
2 1 (2) (1+1)
3 2 (1+2), (3) (1+1+1), (3)
4 2 (1+3), (4) (1+1+1+1), (1+3)
5 3 (2+3), (1+4), (5) (1+1+1+1+1), (1+1+3), (5)
6 4 (1+2+3), (2+4), (1+5), (6) (1+1+1+1+1+1), (1+1+1+3), (3+3), (1+5)
7 5 (1+2+4), (3+4), (2+5), (1+6), (7) (1+1+1+1+1+1+1), (1+1+1+1+3), (1+3+3), (1+1+5), (7)
8 6 (1+3+4), (1+2+5), (3+5), (2+6), (1+7), (8) (1+1+1+1+1+1+1+1), (1+1+1+1+1+3), (1+1+3+3), (1+1+1+5), (3+5), (1+7)
9 8 (2+3+4), (1+3+5), (4+5), (1+2+6), (3+6), (2+7), (1+8), (9) ......
10 10 (1+2+3+4), (2+3+5), (1+4+5), (1+3+6), (4+6), (1+2+7), (3+7), (2+8), (1+9), (10) ......

### MacLaurin Series

The corresponding generating function based on the MacLaurin series with the numbers Q(n) as coefficients in front of xn is as follows:

${\displaystyle \sum _{k=0}^{\infty }Q(k)x^{k}=(x;x^{2})_{\infty }^{-1}=\vartheta _{00}(x)^{1/6}\vartheta _{01}(x)^{-1/3}{\biggl \{}{\frac {1}{16\,x}}{\bigl [}\vartheta _{00}(x)^{4}-\vartheta _{01}(x)^{4}{\bigr ]}{\biggr \}}^{1/24}}$

The following first addends are obtained:

${\displaystyle (x;x^{2})_{\infty }^{-1}=1+1x+1x^{2}+2x^{3}+2x^{4}+3x^{5}+4x^{6}+5x^{7}+6x^{8}+8x^{9}+10x^{10}...}$

In comparison, the generating function of the regular partition numbers P(n) has this identity with respect to the theta function:

${\displaystyle \sum _{k=0}^{\infty }P(k)x^{k}=(x;x)_{\infty }^{-1}=\vartheta _{00}(x)^{-1/6}\vartheta _{01}(x)^{-2/3}{\biggl \{}{\frac {1}{16\,x}}{\bigl [}\vartheta _{00}(x)^{4}-\vartheta _{01}(x)^{4}{\bigr ]}{\biggr \}}^{-1/24}}$

Important calculation formulas for the theta function:

${\displaystyle (x;x)_{\infty }(x;x^{2})_{\infty }=\vartheta _{01}(x)}$
${\displaystyle 16\,x\,(x;x)_{\infty }^{8}=(x;x^{2})_{\infty }^{16}\,\vartheta _{00}(x)^{4}{\bigl [}\vartheta _{00}(x)^{4}-\vartheta _{01}(x)^{4}{\bigr ]}}$

These are the definitions of the two mentioned theta functions:

${\displaystyle \vartheta _{00}(x)=1+2\sum _{n=1}^{\infty }x^{n^{2}}}$
${\displaystyle \vartheta _{01}(x)=1+2\sum _{n=1}^{\infty }(-1)^{n}x^{n^{2}}}$

The products in the brackets are the so called Pochhammer products and they are defined as follows:

${\displaystyle (a;b)_{\infty }=\prod _{k=0}^{\infty }(1-ab^{k})}$

These are two examples:

${\displaystyle (x;x)_{\infty }=\prod _{n=1}^{\infty }(1-x^{n})}$
${\displaystyle (x;x^{2})_{\infty }=\prod _{n=1}^{\infty }(1-x^{2n-1})}$

### Identities about strict partition numbers

Following identity is valid for the Pochhammer products:

${\displaystyle (x;x)_{\infty }^{-1}=(x^{2};x^{2})_{\infty }^{-1}(x;x^{2})_{\infty }^{-1}}$

From this identity follows that formula:

${\displaystyle {\biggl [}\sum _{n=0}^{\infty }P(n)x^{n}{\biggr ]}={\biggl [}\sum _{n=0}^{\infty }P(n)x^{2n}{\biggr ]}{\biggl [}\sum _{n=0}^{\infty }Q(n)x^{n}{\biggr ]}}$

Therefore those two formulas are valid for the synthesis of the number sequence P(n):

${\displaystyle P(2n)=\sum _{k=0}^{n}P(n-k)Q(2k)}$
${\displaystyle P(2n+1)=\sum _{k=0}^{n}P(n-k)Q(2k+1)}$

In the following, two examples are accurately executed:

${\displaystyle P(8)=\sum _{k=0}^{4}P(4-k)Q(2k)=}$
${\displaystyle =P(4)Q(0)+P(3)Q(2)+P(2)Q(4)+P(1)Q(6)+P(0)Q(8)=}$
${\displaystyle =5\times 1+3\times 1+2\times 2+1\times 4+1\times 6=22}$
${\displaystyle P(9)=\sum _{k=0}^{4}P(4-k)Q(2k+1)=}$
${\displaystyle =P(4)Q(1)+P(3)Q(3)+P(2)Q(5)+P(1)Q(7)+P(0)Q(9)=}$
${\displaystyle =5\times 1+3\times 2+2\times 3+1\times 5+1\times 8=30}$

## References

1. ^ Sloane, N. J. A. (ed.), "Sequence A070177", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
2. ^ Caldwell, Chris K. (2017), The Top Twenty
3. ^ "PrimePage Primes: p(1289844341)", primes.utm.edu, retrieved 30 June 2022
4. ^ "The Top Twenty: Elliptic Curve Primality Proof", primes.utm.edu, retrieved 30 June 2022
5. ^ Abramowitz, Milton; Stegun, Irene (1964), Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, United States Department of Commerce, National Bureau of Standards, p. 825, ISBN 0-486-61272-4
6. ^ Euler, Leonhard (1753), "De partitione numerorum", Novi Commentarii Academiae Scientiarum Petropolitanae (in Latin), 3: 125–169
7. ^ Ewell, John A. (2004), "Recurrences for the partition function and its relatives", The Rocky Mountain Journal of Mathematics, 34 (2): 619–627, doi:10.1216/rmjm/1181069871, JSTOR 44238988, MR 2072798
8. ^ Wilf, Herbert S. (1982), "What is an answer?", American Mathematical Monthly, 89 (5): 289–292, doi:10.2307/2321713, JSTOR 2321713, MR 0653502
9. ^ Al, Busra; Alkan, Mustafa (2018), "A note on relations among partitions", Proc. Mediterranean Int. Conf. Pure & Applied Math. and Related Areas (MICOPAM 2018), pp. 35–39
10. ^ a b Hardy, G. H.; Wright, E. M. (2008) [1938], An Introduction to the Theory of Numbers (6th ed.), Oxford University Press, p. 380, ISBN 978-0-19-921986-5, MR 2445243, Zbl 1159.11001
11. ^ Berndt, Bruce C.; Ono, Ken (1999), "Ramanujan's unpublished manuscript on the partition and tau functions with proofs and commentary" (PDF), The Andrews Festschrift (Maratea, 1998), Séminaire Lotharingien de Combinatoire, vol. 42, Art. B42c, 63, MR 1701582
12. ^ a b Ono, Ken (2004), The web of modularity: arithmetic of the coefficients of modular forms and ${\displaystyle q}$-series, CBMS Regional Conference Series in Mathematics, vol. 102, Providence, Rhode Island: American Mathematical Society, p. 87, ISBN 0-8218-3368-5, Zbl 1119.11026
13. ^ Ahlgren, Scott; Boylan, Matthew (2003), "Arithmetic properties of the partition function" (PDF), Inventiones Mathematicae, 153 (3): 487–502, Bibcode:2003InMat.153..487A, doi:10.1007/s00222-003-0295-6, MR 2000466, S2CID 123104639
14. ^ Ono, Ken (2000), "Distribution of the partition function modulo ${\displaystyle m}$", Annals of Mathematics, 151 (1): 293–307, arXiv:math/0008140, Bibcode:2000math......8140O, doi:10.2307/121118, JSTOR 121118, MR 1745012, S2CID 119750203, Zbl 0984.11050
15. ^ Ahlgren, Scott; Ono, Ken (2001), "Congruence properties for the partition function" (PDF), Proceedings of the National Academy of Sciences, 98 (23): 12882–12884, Bibcode:2001PNAS...9812882A, doi:10.1073/pnas.191488598, MR 1862931, PMC 60793, PMID 11606715
16. ^ a b Hardy, G. H.; Ramanujan, S. (1918), "Asymptotic formulae in combinatory analysis", Proceedings of the London Mathematical Society, Second Series, 17 (75–115). Reprinted in Collected papers of Srinivasa Ramanujan, Amer. Math. Soc. (2000), pp. 276–309.
17. ^ Andrews, George E. (1976), The Theory of Partitions, Cambridge University Press, p. 69, ISBN 0-521-63766-X, MR 0557013
18. ^ Rademacher, Hans (1937), "On the partition function ${\displaystyle p(n)}$", Proceedings of the London Mathematical Society, Second Series, 43 (4): 241–254, doi:10.1112/plms/s2-43.4.241, MR 1575213
19. ^ Erdős, P. (1942), "On an elementary proof of some asymptotic formulas in the theory of partitions" (PDF), Annals of Mathematics, Second Series, 43 (3): 437–450, doi:10.2307/1968802, JSTOR 1968802, MR 0006749, Zbl 0061.07905
20. ^ Nathanson, M. B. (2000), Elementary Methods in Number Theory, Graduate Texts in Mathematics, vol. 195, Springer-Verlag, p. 456, ISBN 0-387-98912-9, Zbl 0953.11002
21. ^ Johansson, Fredrik (2012), "Efficient implementation of the Hardy–Ramanujan–Rademacher formula", LMS Journal of Computation and Mathematics, 15: 341–59, arXiv:1205.5991, doi:10.1112/S1461157012001088, MR 2988821, S2CID 16580723
22. ^ Johansson, Fredrik (March 2, 2014), New partition function record: p(1020) computed
23. ^ "code golf - Strict partitions of a positive integer". Retrieved 2022-03-09.
24. ^ "A000009 - OEIS". Retrieved 2022-03-09.
25. ^ Eric W. Weisstein. "Partition Function Q". Retrieved 2022-03-09.