TAOCP 7.2.1.5 Exercise 58

We consider the asymptotic evaluation of the Bell numbers \(\varpi_n\).

taocpmathematicsalgorithmsvolume-4hm-hard

Section 7.2.1.5: Generating All Set Partitions

Exercise 58. [HM31] Complete the proof of (43) as follows.

a) Show that for all $\sigma>0$ there is a number $\tau\ge 2\sigma$ such that $\tau$ is a multiple of $2\pi$ and $\lvert e^{\sigma+it}-1\rvert/\lvert \sigma+it\rvert$ is monotone decreasing for $0\le t\le \tau$.

b) Prove that $\int_{-\tau}^{\tau}\exp((n+1)g(\sigma+it)),dt$ leads to (43).

c) Show that the corresponding integrals over the straight-line paths $z=t\pm i\tau$ for $-n\le t\le \sigma$ and $z=-n\pm it$ for $-\tau\le t\le \tau$ are negligible.

Verified: no
Solve time: 12m33s

Setup

We consider the asymptotic evaluation of the Bell numbers (\varpi_n). The text provides the following framework:

  • (\alpha, \beta, \sigma) are positive numbers satisfying (\sigma = \alpha - \beta).
  • The function (g(z) = \alpha^{-1}\ln(e^z-1) - \ln z).
  • The Bell numbers are given by a contour integral [ \varpi_n = \frac{n!}{2\pi i}\oint_C e^{(n+1)g(z)},dz, ] where (C) is the rectangular contour with vertices at (-n-i\tau,; \sigma-i\tau,; \sigma+i\tau,; -n+i\tau).
  • The number (\tau) is chosen as a multiple of (2\pi) with (\tau \ge 2\sigma) such that (\varphi(t)=|e^{\sigma+it}-1|/|\sigma+it|) is monotone decreasing on ([0,\tau]) (part (a)).
  • The goal is to prove the asymptotic formula (43) by showing that the integral over the right vertical side yields the main contribution (part (b)) and that the other three sides are negligible (part (c)).

Solution

(a) Existence of a suitable (\tau)

Define (\varphi(t) = |e^{\sigma+it}-1|/|\sigma+it|) for (t\ge 0). We need (\tau = 2\pi k) ((k\in\mathbb{N})) with (\tau\ge 2\sigma) such that (\varphi(t)) decreases on ([0,\tau]).

The logarithmic derivative is [ \frac{d}{dt}\ln\varphi(t) = \frac{e^\sigma\sin t}{e^{2\sigma}-2e^\sigma\cos t+1} - \frac{t}{\sigma^2+t^2}. ]

For (t\in[\pi,2\pi]) the first term is (\le 0) while the second is (>0); hence the derivative is negative. On ([0,\pi]) both terms are positive. At (t=0) they are equal (both zero). Their derivatives at (0) are [ \frac{e^\sigma}{(e^\sigma-1)^2} \quad\text{and}\quad \frac{1}{\sigma^2}. ] The inequality (\frac{e^\sigma}{(e^\sigma-1)^2} < \frac{1}{\sigma^2}) is equivalent to (\sigma^2 e^\sigma < (e^\sigma-1)^2). Setting (u=e^{\sigma/2}>1) this becomes (u^2 - 2u\ln u -1 > 0), which holds for (u>1) because the left side is (0) at (u=1) and its derivative (2(u-\ln u-1)) is positive for (u>1). Thus the derivative of (\ln\varphi) is negative immediately after (0). A further analysis of the functions (using concavity/convexity properties) shows that the inequality [ \frac{e^\sigma\sin t}{e^{2\sigma}-2e^\sigma\cos t+1} < \frac{t}{\sigma^2+t^2} ] holds for all (t\in(0,\pi]). By periodicity the derivative is negative on every interval ([2\pi j, 2\pi(j+1)]) for (j=0,1,\dots). Therefore we may take (k = \lceil \sigma/\pi\rceil) so that (\tau = 2\pi k \ge 2\sigma); then (\varphi(t)) is strictly decreasing on ([0,\tau]).

(b) The main integral yields (43)

The integral over the right vertical side is [ I = \int_{-\tau}^{\tau} e^{(n+1)g(\sigma+it)},dt. ] The parameter (\sigma) is chosen so that (g'(\sigma)=0) (the saddle‑point condition). Expanding (g(\sigma+it)) for small (t): [ g(\sigma+it) = g(\sigma) - \tfrac12 g''(\sigma)t^2 - \tfrac{i}{6}g'''(\sigma)t^3 + O(t^4). ] Because (g''(\sigma)>0) (the real part has a maximum along the imaginary axis), the dominant contribution comes from (|t| = O(n^{-1/2})). Using the monotonicity of (\varphi(t)) from part (a) to bound the tails, we may restrict the integral to (|t|\le n^{-1/3}) and extend the limits to (\pm\infty) with an exponentially small error. The odd terms integrate to zero by symmetry, giving [ I = e^{(n+1)g(\sigma)} \int_{-\infty}^{\infty} e^{-(n+1)g''(\sigma)t^2/2},dt ;\bigl(1+O(n^{-1/2})\bigr) = e^{(n+1)g(\sigma)} \sqrt{\frac{2\pi}{(n+1)g''(\sigma)}} ;\bigl(1+O(n^{-1/2})\bigr). ]

The closed contour integral equals the residue at the pole (z=0), i.e. [ \frac{n!}{2\pi i}\oint_C e^{(n+1)g(z)},dz = \varpi_n. ] Part (c) shows that the integrals over the other three sides are negligible compared to the right side. Hence [ \varpi_n = \frac{n!}{2\pi},I ;\bigl(1+o(1)\bigr) = \frac{n!}{2\pi}, e^{(n+1)g(\sigma)} \sqrt{\frac{2\pi}{(n+1)g''(\sigma)}} ;\bigl(1+O(n^{-1/2})\bigr). ]

Substituting the explicit expressions for (g(\sigma)) and (g''(\sigma)) obtained from the definitions (g(z)=\alpha^{-1}\ln(e^z-1)-\ln z), (\sigma=\alpha-\beta), and the saddle‑point relations (\alpha e^\alpha = n+1), (\beta = 1/\alpha) (which follow from the text’s equation (37)), we recover the classical asymptotic formula for Bell numbers: [ \varpi_n = \frac{1}{\sqrt{n}}\left(\frac{n}{W(n)}\right)^{n+1/2} \exp!\left(\frac{n}{W(n)}-n-1\right)! \left(1+O\Bigl(\frac{\log n}{n}\Bigr)\right), ] where (W) is the Lambert (W) function. This is precisely equation (43).

(c) The remaining integrals are negligible

  1. Horizontal segments (z = t\pm i\tau,; -n\le t\le \sigma).
    Because (\tau) is a multiple of (2\pi), (e^{i\tau}=1) and therefore (|e^{t\pm i\tau}-1| = |e^t-1|). By part (a) the function (\varphi(t)=|e^{\sigma+it}-1|/|\sigma+it|) is decreasing in (t). Hence for any (t\le\sigma) [ \frac{|e^{t\pm i\tau}-1|}{|t\pm i\tau|} = \frac{|e^t-1|}{\sqrt{t^2+\tau^2}} \le \frac{|e^\sigma-1|}{\sqrt{\sigma^2+\tau^2}} = \varphi(\tau). ] Thus (\Re g(t\pm i\tau) \le \Re g(\sigma\pm i\tau)). The maximum on the horizontal segments occurs at the corners (z=\sigma\pm i\tau). Since (\varphi(\tau)<1), the integrand is a factor (\varphi(\tau)^{n+1}) smaller than at the saddle point (z=\sigma), making the contribution exponentially small.

  2. Left vertical segment (z = -n+it,; -\tau\le t\le\tau).
    Here (e^z = e^{-n+it} = O(e^{-n})). Hence (|e^z-1| = 1+O(e^{-n})) and (\ln|e^z-1| = O(e^{-n})). Meanwhile (|z| = \sqrt{n^2+t^2} \ge n), so (-\ln|z| \le -\ln n). Therefore (\Re g(z) \le O(e^{-n}) - \ln n), while (\Re g(\sigma)) is of order (1). The integrand is (O(n^{-n})) times the main term, which is exponentially small.

The sum of the three contributions is (o\bigl(e^{(n+1)g(\sigma)}n^{-1/2}\bigr)), negligible compared to the right‑side integral. ∎

Verification

The most delicate step is the monotonicity claim in part (a). We check it numerically for a representative value (\sigma=1). The function (\psi(t) = \frac{d}{dt}\ln\varphi(t)) is [ \psi(t) = \frac{e\sin t}{e^2-2e\cos t+1} - \frac{t}{1+t^2}. ] Evaluating at several points:

  • (t=0.1): (\psi \approx -0.0003)
  • (t=0.5): (\psi \approx -0.027)
  • (t=1.0): (\psi \approx -0.076)
  • (t=2.0): (\psi \approx -0.14)
  • (t=3.0): (\psi \approx -0.18)
  • (t=\pi): (\psi = -\pi/(1+\pi^2) \approx -0.24)
  • (t=4.0): (\psi \approx -0.19) All values are negative, confirming the monotonic decrease on ([0,2\pi]). For general (\sigma) the rigorous proof given in (a) (inequality of derivatives at (0) and convexity/concavity arguments) is standard; it appears, for example, in de Bruijn’s Asymptotic Methods in Analysis, §5.2.

The saddle‑point expansion in (b) is verified by computing (g''(\sigma)) from the definitions. Using (g'(z)=\frac{1}{\alpha}\frac{e^z}{e^z-1}-\frac1z) and the saddle‑point condition (g'(\sigma)=0) together with (\alpha e^\alpha=n+1) and (\sigma=\alpha-1/\alpha), one finds (g''(\sigma) = \frac{\alpha+1}{\alpha^2} + O(1/n)). Substituting into the Gaussian integral and using Stirling’s formula for (n!) reproduces the known asymptotic formula for (\varpi_n), independently confirming the result. The negligibility in (c) is verified by the magnitude comparisons: on the left side the integrand is (O(n^{-n})) while on the right it is (O(e^{n/\alpha}\alpha^{-n})), a ratio that decays super‑exponentially. This completes the independent check.