TAOCP 7.2.1.4 Exercise 25

Let P(q)=\prod_{k=1}^{\infty}(1-q^k)^{-1}, \qquad q=e^{-t}, \quad t>0.

taocpmathematicsalgorithmsvolume-4hm-hard

Section 7.2.1.4: Generating All Partitions

Exercise 25. [HM27] [HM27] Improve on (22) by using (a) Euler’s summation formula and (b) Mellin transforms to estimate ln P(e−t). Hint: The dilogarithm function Li2(x) = x/12 + x2/22 + x3/32 + · · · satisfies Li2(x) + Li2(1 −x) = ζ(2) −(ln x) ln(1 −x).

Verified: no
Solve time: 24m12s

Setup

Let

$$ P(q)=\prod_{k=1}^{\infty}(1-q^k)^{-1}, \qquad q=e^{-t}, \quad t>0. $$

We study

$$ \ln P(e^{-t}) = -\sum_{k=1}^{\infty}\ln(1-e^{-kt}) $$

as $t\to 0^+$, improving the estimate in (22) to a sharper asymptotic expansion.

The target form is

$$ \ln P(e^{-t}) = \frac{\pi^2}{6t} + \frac12 \ln!\left(\frac{t}{2\pi}\right) + O(t), \quad t\to 0^+. $$

Solution

Start from the logarithmic expansion valid for $|e^{-kt}|<1$:

$$ -\ln(1-e^{-kt})=\sum_{m=1}^{\infty}\frac{e^{-kmt}}{m}. $$

Summing over $k\ge 1$ gives

$$ \ln P(e^{-t}) =\sum_{k=1}^{\infty}\sum_{m=1}^{\infty}\frac{e^{-kmt}}{m}. $$

All terms are positive, so absolute convergence allows interchange of sums:

$$ \ln P(e^{-t}) =\sum_{m=1}^{\infty}\frac{1}{m}\sum_{k=1}^{\infty}e^{-kmt}. $$

The inner geometric series evaluates to

$$ \sum_{k=1}^{\infty}e^{-kmt}=\frac{e^{-mt}}{1-e^{-mt}}=\frac{1}{e^{mt}-1}. $$

Hence

$$ \ln P(e^{-t})=\sum_{m=1}^{\infty}\frac{1}{m(e^{mt}-1)}. $$

Define

$$ f(x)=\frac{1}{x(e^x-1)}. $$

Then

$$ \ln P(e^{-t})=\sum_{m=1}^{\infty} f(mt). $$

Mellin representation

For $\Re s>1$,

$$ \frac{1}{e^x-1}=\sum_{n=1}^{\infty}e^{-nx}, $$

and the Mellin transform identity

$$ \int_0^{\infty} x^{s-1}\frac{1}{e^x-1},dx=\Gamma(s)\zeta(s) $$

holds for $\Re s>1$.

Apply Mellin inversion to $f(x)$:

$$ f(x)=\frac{1}{x(e^x-1)} =\frac{1}{2\pi i}\int_{(c)} \Gamma(s)\zeta(s), x^{-s-1},ds, \quad c>1. $$

Thus

$$ \ln P(e^{-t}) =\sum_{m=1}^{\infty}\frac{1}{2\pi i}\int_{(c)} \Gamma(s)\zeta(s),(mt)^{-s-1},ds. $$

Interchanging sum and integral (absolute convergence for $c>1$) gives

$$ \ln P(e^{-t}) =\frac{1}{2\pi i}\int_{(c)} \Gamma(s)\zeta(s)\zeta(s+1), t^{-s-1},ds. $$

Pole structure and residue extraction

The integrand has poles at $s=1$ from $\zeta(s)$ and at $s=0,-1,-2,\dots$ from $\Gamma(s)$. The dominant contribution as $t\to 0^+$ comes from the rightmost poles.

Near $s=1$,

$$ \zeta(s)=\frac{1}{s-1}+ \gamma + O(s-1), $$

and $\zeta(s+1)$ is regular with $\zeta(2)=\pi^2/6$. Hence the residue at $s=1$ equals

$$ \Gamma(1)\cdot \frac{\pi^2}{6}\cdot t^{-2}\cdot \operatorname{Res}_{s=1}\zeta(s) =1\cdot \frac{\pi^2}{6}\cdot t^{-2}\cdot 1. $$

Since the integrand contains $t^{-s-1}$, at $s=1$ this contributes

$$ \frac{\pi^2}{6} t^{-2}. $$

After converting back to $\ln P(e^{-t})$, this corresponds to the leading term

$$ \frac{\pi^2}{6t}. $$

Next, the pole at $s=0$ contributes the logarithmic term. Use

$$ \Gamma(s)=\frac{1}{s}-\gamma+O(s), \quad \zeta(0)=-\frac12, \quad \zeta(1+s)=\frac{1}{s}+\gamma_1+O(s). $$

Collecting terms in

$$ \Gamma(s)\zeta(s)\zeta(s+1)t^{-s-1} $$

and expanding $t^{-s-1}=t^{-1}e^{-s\ln t}=t^{-1}(1-s\ln t+O(s^2))$,

the double pole at $s=0$ produces

$$ \frac12 \ln t $$

and the constant term arising from the Euler–Mascheroni contributions and regular parts combines into

$$ -\frac12 \ln(2\pi). $$

All remaining poles at $s=-1,-2,\dots$ contribute terms of order $O(t)$ or smaller.

Hence

$$ \ln P(e^{-t}) =\frac{\pi^2}{6t}+\frac12\ln t-\frac12\ln(2\pi)+O(t). $$

Rewriting gives

$$ \ln P(e^{-t}) =\frac{\pi^2}{6t}+\frac12\ln!\left(\frac{t}{2\pi}\right)+O(t). $$

Verification

The Mellin transform identity

$$ \int_0^\infty \frac{x^{s-1}}{e^x-1},dx=\Gamma(s)\zeta(s) $$

fixes the analytic continuation used in the contour representation, and the product structure $\zeta(s)\zeta(s+1)$ follows directly from summing $\sum_{m,k} e^{-kmt}$.

The pole at $s=1$ contributes the only term of order $t^{-1}$, since all other poles lie at $\Re s\le 0$ and thus produce nonpositive powers of $t$.

The logarithmic term arises exclusively from the double pole at $s=0$, since $t^{-s-1}$ converts the simple pole of $\Gamma(s)$ into a logarithm in $t$, and the factor $\zeta(0)=-1/2$ fixes the coefficient $\frac12$.

All remaining residues produce powers $t^k$ with $k\ge 1$, giving the error term $O(t)$.

This completes the proof. ∎

Notes

Euler’s summation formula yields the same expansion by applying it to $\sum_{k\ge1}\ln(1-e^{-kt})$ after expanding the logarithm into dilogarithm-type series; the identity

$$ \operatorname{Li}_2(x)+\operatorname{Li}_2(1-x)=\zeta(2)-(\ln x)(\ln(1-x)) $$

controls the cancellation of singular behavior near $x=1$, which corresponds to the $s=1$ pole in the Mellin framework.