§27.14 Unrestricted Partitions
Contents
- §27.14(i) Partition Functions
- §27.14(ii) Generating Functions and Recursions
- §27.14(iii) Asymptotic Formulas
- §27.14(iv) Relation to Modular Functions
- §27.14(v) Divisibility Properties
- §27.14(vi) Ramanujan’s Tau Function
§27.14(i) Partition Functions
A fundamental problem studies the number of ways can be written as a sum
of positive integers
, that is, the number of solutions of
![n=a_{1}+a_{2}+\cdots,](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E1.png)
![a_{1}\geq a_{2}\geq\cdots\geq 1](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/m46.png)
The number of summands is unrestricted, repetition is allowed, and the order of
the summands is not taken into account. The corresponding unrestricted
partition function is denoted by , and the summands are
called parts; see §26.9(i). For example,
because there are exactly seven partitions of 5:
.
The number of partitions of into at most
parts is denoted by
; again see §26.9(i).
§27.14(ii) Generating Functions and Recursions
Euler introduced the reciprocal of the infinite product
![\mathop{\mathit{f}\/}\nolimits\!\left(x\right)=\prod _{{m=1}}^{\infty}(1-x^{m}),](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E2.png)
![|x|<1](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/m67.png)
as a generating function for the function defined in
§27.14(i):
![\frac{1}{\mathop{\mathit{f}\/}\nolimits\!\left(x\right)}=\sum _{{n=0}}^{\infty}\mathop{p\/}\nolimits\!\left(n\right)x^{n},](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E3.png)
with . Euler’s pentagonal number theorem states
that
![\mathop{\mathit{f}\/}\nolimits\!\left(x\right)=1-x-x^{2}+x^{5}+x^{7}-x^{{12}}-x^{{15}}+\dots=1+\sum _{{k=1}}^{\infty}(-1)^{k}\left(x^{{\omega(k)}}+x^{{\omega(-k)}}\right),](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E4.png)
where the exponents 1, 2, 5, 7, 12, 15, are the
pentagonal numbers, defined by
![\omega(\pm k)=(3k^{2}\mp k)/2,](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E5.png)
![k=1,2,3,\dots](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/m56.png)
Multiplying the power series for with that for
and equating coefficients, we obtain the recursion formula
![\mathop{p\/}\nolimits\!\left(n\right)=\sum _{{k=1}}^{\infty}(-1)^{{k+1}}\left(\mathop{p\/}\nolimits\!\left(n-\omega(k)\right)+\mathop{p\/}\nolimits\!\left(n-\omega(-k)\right)\right)=\mathop{p\/}\nolimits\!\left(n-1\right)+\mathop{p\/}\nolimits\!\left(n-2\right)-\mathop{p\/}\nolimits\!\left(n-5\right)-\mathop{p\/}\nolimits\!\left(n-7\right)+\cdots,](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E6.png)
where is defined to be 0 if
. Logarithmic
differentiation of the generating function
leads to another
recursion:
![n\mathop{p\/}\nolimits\!\left(n\right)=\sum _{{k=1}}^{n}\mathop{\sigma _{{1}}\/}\nolimits\!\left(n\right)\mathop{p\/}\nolimits\!\left(n-k\right),](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E7.png)
where is defined by (27.2.10) with
.
§27.14(iii) Asymptotic Formulas
These recursions can be used to calculate , which grows
very rapidly. For example,
= 1905 69292, and
. For large
![\mathop{p\/}\nolimits\!\left(n\right)\sim e^{{K\sqrt{n}}}/(4n\sqrt{3}),](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E8.png)
where (Hardy and Ramanujan (1918)).
Rademacher (1938) derives a convergent series that also provides an
asymptotic expansion for
:
![\mathop{p\/}\nolimits\!\left(n\right)=\frac{1}{\pi\sqrt{2}}\sum _{{k=1}}^{\infty}\sqrt{k}A_{k}(n)\*\left[\frac{d}{dt}\frac{\mathop{\sinh\/}\nolimits\!\left(\ifrac{K\sqrt{t}}{k}\right)}{\sqrt{t}}\right]_{{t=n-(1/24)}},](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E9.png)
where
![A_{k}(n)=\sum _{{\substack{h=1\\
\left(h,k\right)=1}}}^{k}\mathop{\exp\/}\nolimits\!\left(\pi is(h,k)-2\pi in\frac{h}{k}\right),](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E10.png)
and is a Dedekind sum given by
![s(h,k)=\sum _{{r=1}}^{{k-1}}\frac{r}{k}\left(\frac{hr}{k}-\left\lfloor\frac{hr}{k}\right\rfloor-\frac{1}{2}\right).](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E11.png)
§27.14(iv) Relation to Modular Functions
§27.14(v) Divisibility Properties
Ramanujan (1921) gives identities that imply divisibility properties of the partition function. For example, the Ramanujan identity
![5\frac{(\mathop{\mathit{f}\/}\nolimits\!\left(x^{5}\right))^{5}}{(\mathop{\mathit{f}\/}\nolimits\!\left(x\right))^{6}}=\sum _{{n=0}}^{\infty}\mathop{p\/}\nolimits\!\left(5n+4\right)x^{n}](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E15.png)
implies . Ramanujan also found that
and
for all
. After decades of nearly
fruitless searching for further congruences of this type, it was believed that
no others existed, until it was shown in Ono (2000) that there are
infinitely many.
Ono proved that for every prime
there are integers
and
such that
for all
. For example,
.
§27.14(vi) Ramanujan’s Tau Function
The discriminant function is defined by
![\mathop{\Delta\/}\nolimits\!\left(\tau\right)=(2\pi)^{{12}}(\mathop{\eta\/}\nolimits\!\left(\tau\right))^{{24}},](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E16.png)
![\imagpart{\tau}>0](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/m16.png)
and satisfies the functional equation
![\mathop{\Delta\/}\nolimits\!\left(\frac{a\tau+b}{c\tau+d}\right)=(c\tau+d)^{{12}}\mathop{\Delta\/}\nolimits\!\left(\tau\right),](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E17.png)
if are integers with
and
.
The 24th power of in (27.14.12) with
is an infinite product that generates a power series in
with integer coefficients called Ramanujan’s tau function
:
![x\prod _{{n=1}}^{\infty}(1-x^{n})^{{24}}=\sum _{{n=1}}^{\infty}\mathop{\tau\/}\nolimits\!\left(n\right)x^{n},](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E18.png)
![|x|<1](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/m67.png)
The tau function is multiplicative and satisfies the more general relation:
![\mathop{\tau\/}\nolimits\!\left(m\right)\mathop{\tau\/}\nolimits\!\left(n\right)=\sum _{{d\divides\left(m,n\right)}}d^{{11}}\mathop{\tau\/}\nolimits\!\left(\frac{mn}{d^{2}}\right),](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E19.png)
![m,n=1,2,\dots](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/m58.png)
Lehmer (1947) conjectures that is never 0 and
verifies this for all
by studying various congruences
satisfied by
, for example:
![\mathop{\tau\/}\nolimits\!\left(n\right)\equiv\mathop{\sigma _{{11}}\/}\nolimits\!\left(n\right)\;\;(\mathop{{\rm mod}}691).](https://webarchive.library.unt.edu/web/20130219031932im_/http://dlmf.nist.gov/27/14/E20.png)