What's New
About the Project
NIST
27 Functions of Number TheoryAdditive Number Theory

§27.14 Unrestricted Partitions

Contents

§27.14(i) Partition Functions

A fundamental problem studies the number of ways n can be written as a sum of positive integers n, that is, the number of solutions of

27.14.1 n=a1+a2+,
a1a21.

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 p(n), and the summands are called parts; see §26.9(i). For example, p(5)=7 because there are exactly seven partitions of 5: 5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1.

The number of partitions of n into at most k parts is denoted by pk(n); again see §26.9(i).

§27.14(ii) Generating Functions and Recursions

Euler introduced the reciprocal of the infinite product

27.14.2 f(x)=m=1(1-xm),
|x|<1,

as a generating function for the function p(n) defined in §27.14(i):

27.14.3 1f(x)=n=0p(n)xn,

with p(0)=1. Euler’s pentagonal number theorem states that

27.14.4 f(x)=1-x-x2+x5+x7-x12-x15+=1+k=1(-1)k(xω(k)+xω(-k)),

where the exponents 1, 2, 5, 7, 12, 15, are the pentagonal numbers, defined by

27.14.5 ω(±k)=(3k2k)/2,
k=1,2,3,.

Multiplying the power series for f(x) with that for 1/f(x) and equating coefficients, we obtain the recursion formula

27.14.6 p(n)=k=1(-1)k+1(p(n-ω(k))+p(n-ω(-k)))=p(n-1)+p(n-2)-p(n-5)-p(n-7)+,

where p(k) is defined to be 0 if k<0. Logarithmic differentiation of the generating function 1/f(x) leads to another recursion:

27.14.7 np(n)=k=1nσ1(n)p(n-k),

where σ1(n) is defined by (27.2.10) with α=1.

§27.14(iii) Asymptotic Formulas

These recursions can be used to calculate p(n), which grows very rapidly. For example, p(10)=42,p(100) = 1905 69292, and p(200)=397 29990 29388. For large n

27.14.8 p(n)eKn/(4n3),

where K=π2/3 (Hardy and Ramanujan (1918)). Rademacher (1938) derives a convergent series that also provides an asymptotic expansion for p(n):

27.14.9 p(n)=1π2k=1kAk(n)[ddtsinh(Kt/k)t]t=n-(1/24),

where

27.14.10 Ak(n)=h=1(h,k)=1kexp(πis(h,k)-2πinhk),

and s(h,k) is a Dedekind sum given by

27.14.11 s(h,k)=r=1k-1rk(hrk-hrk-12).

§27.14(iv) Relation to Modular Functions

Dedekind sums occur in the transformation theory of the Dedekind modular function η(τ), defined by

27.14.12 η(τ)=eπiτ/12n=1(1-e2πinτ),
τ>0.

This is related to the function f(x) in (27.14.2) by

27.14.13 η(τ)=eπiτ/12f(e2πiτ).

η(τ) satisfies the following functional equation: if a,b,c,d are integers with ad-bc=1 and c>0, then

27.14.14 η(aτ+bcτ+d)=ε(-i(cτ+d))12η(τ),

where ε=exp(πi(((a+d)/(12c))-s(d,c))) and s(d,c) is given by (27.14.11).

For further properties of the function η(τ) see §§23.1523.19.

§27.14(v) Divisibility Properties

Ramanujan (1921) gives identities that imply divisibility properties of the partition function. For example, the Ramanujan identity

27.14.15 5(f(x5))5(f(x))6=n=0p(5n+4)xn

implies p(5n+4)0(mod5). Ramanujan also found that p(7n+5)0(mod7) and p(11n+6)0(mod11) for all n. 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 q>3 there are integers a and b such that p(an+b)0(modq) for all n. For example, p(1575 25693n+1 11247)0(mod13).

§27.14(vi) Ramanujan’s Tau Function

The discriminant function Δ(τ) is defined by

27.14.16 Δ(τ)=(2π)12(η(τ))24,
τ>0,

and satisfies the functional equation

27.14.17 Δ(aτ+bcτ+d)=(cτ+d)12Δ(τ),

if a,b,c,d are integers with ad-bc=1 and c>0.

The 24th power of η(τ) in (27.14.12) with e2πiτ=x is an infinite product that generates a power series in x with integer coefficients called Ramanujan’s tau function τ(n):

27.14.18 xn=1(1-xn)24=n=1τ(n)xn,
|x|<1.

The tau function is multiplicative and satisfies the more general relation:

27.14.19 τ(m)τ(n)=d|(m,n)d11τ(mnd2),
m,n=1,2,.

Lehmer (1947) conjectures that τ(n) is never 0 and verifies this for all n<21 49286 39999 by studying various congruences satisfied by τ(n), for example:

27.14.20 τ(n)σ11(n)(mod691).

For further information on partitions and generating functions see Andrews (1976); also §§17.217.14, and §§26.926.10.