小零食：Hardy-Ramanujan 渐进公式

· · 算法·理论

在写更多更复杂的东西之前，先看看我们已经得到的一些特殊模形式的应用。

在分拆数与 q-analog 小记一文中，对于分拆数 p_n，我们得到了 p_n=\mathcal O(\exp(\pi\sqrt{2n/3}))。

本文将把该结论改进为 Hardy-Ramanujan 渐进公式：

p_n\sim\dfrac{1}{4\sqrt3n}\exp\left(\pi\sqrt{\dfrac{2n}3}\right)

首先考虑分拆数的生成函数：

F(q)=\sum_{n=0}^{+\infty}p_nq^n=\prod_{k=1}^{+\infty}\dfrac1{1-q^k}

其中 q\in\mathbb C 且 |q|<1。由 Cauchy 积分的推论得：

p_n=\dfrac1{2\pi\text{i}}\oint_C\dfrac{F(q)}{q^{n+1}}\text{d}q

其中 C 是单位圆内部绕 0 一圈的闭曲线。

我们有 Dedekind η 函数 \eta(\tau)=q^{1/24}\displaystyle\prod_{k=1}^{+\infty}(1-q^k)，显然 F(q)=\dfrac{q^{1/24}}{\eta(\tau)}。

研究 q\to1 时的行为，已经知道 \eta(-1/\tau)=\sqrt{-\text{i}\tau}\eta(\tau)，做换元 z=-2\pi\text{i}\tau，有：

\eta(\tau)=\dfrac{\eta(-1/\tau)}{\sqrt{-\text{i}\tau}}\implies\eta(\tau)=\sqrt{\dfrac{2\pi}z}\eta\left(\dfrac{2\pi\text{i}}{z}\right)

代回 F(q) 中：

F(\text{e}^{-z})=\dfrac{\text{e}^{-z/24}\sqrt{z/2\pi}}{\eta(2\pi\text{i}/z)}

现在让 z\to0，设 \hat q=\text{e}^{2\pi\text{i}(2\pi\text{i}/z)}=\text{e}^{-4\pi^2/z}，它以指数速度趋近于 0。有：

\eta\left(\dfrac{2\pi\text{i}}{z}\right)=\text{e}^{-\pi^2/6z}\prod_{k=1}^{+\infty}(1-\hat q^k)\approx\text{e}^{-\pi^2/6z}

则有：

F(\text{e}^{-z})\approx\sqrt{\dfrac{z}{2\pi}}\exp\left(\dfrac{\pi^2}{6z}-\dfrac{z}{24}\right)

忽略掉 -z/24，得到渐近展开式 F(\text{e}^{-z})\approx\sqrt{\dfrac{z}{2\pi}}\exp\left(\dfrac{\pi^2}{6z}\right)。

回到 Cauchy 积分，代入 q=\text{e}^{-z}，有 \text{d}q=-\text{e}^{-z}\text{d}z，积分路径从小圆 C 变成自上而下的竖线 z=c+\text{i}y，其中 c>0 很小，y\in[-\pi,\pi]。翻转积分方向恰好消掉负号：

\begin{aligned}p_n&=\dfrac1{2\pi\text{i}}\int_{c-\text{i}\pi}^{c+\text{i}\pi}\dfrac{F(\text{e}^{-z})}{\text{e}^{-(n+1)z}}\text{e}^{-z}\text{d}z\\&\approx\dfrac1{2\pi\text{i}}\int_{c-\text{i}\pi}^{c+\text{i}\pi}\sqrt{\dfrac{z}{2\pi}}\exp\left(\dfrac{\pi^2}{6z}+nz\right)\text{d}z\end{aligned}

使用鞍点法，指数 g(z) 在 z_0=\dfrac{\pi}{\sqrt{6n}} 时取到最小值 g(z_0)=\pi\sqrt{\dfrac{2n}3}。

在 z_0 处展开 g(z)\approx g(z_0)+\dfrac12g''(z_0)(z-z_0)^2，其中 g''(z)=\dfrac{\pi^2}{3z^3}。

设 z=z_0+\text{i}y，此时 \text{d}z=\text{i}\,\text{d}y，(z-z_0)^2=-y^2，指数 g(z)\approx g(z_0)-\dfrac{y^2}2g''(z_0)，这是正态分布的形式。

把积分范围扩展到 (-\infty,+\infty)。对于积分里的 \sqrt{z}=\sqrt{z_0+\text{i}y}，将其在 y=0 处展开成 \sqrt{z_0}+c_1y+c_2y^2+\cdots，乘入积分后，c_1y\text{e}^{-y^2} 项是奇函数，抵消；而 c_2y^2\text{e}^{-y^2} 项的结果比常数项的小 \mathcal O(\sqrt n) 量级，具体过程略。

因此有：

\begin{aligned} p_n&\approx\dfrac1{2\pi\text{i}}\int_{-\infty}^{+\infty}\sqrt{\dfrac{z_0}{2\pi}}\exp\left(g(z_0)-\dfrac{y^2}2g''(z_0)\right)\text{i}\ \text{d}y\\ &\approx\dfrac1{2\pi}\sqrt{\dfrac{z_0}{2\pi}}\text{e}^{g(z_0)}\int_{-\infty}^{+\infty}\text{e}^{-\frac12g''(z_0)y^2}\text{d}y \end{aligned}

根据高斯积分 \displaystyle\int_{-\infty}^{+\infty}\text{e}^{-x^2}\text{d}x=\sqrt\pi，积分结果为 \sqrt{\dfrac{2\pi}{g''(z_0)}}。

代入 z_0=\dfrac{\pi}{\sqrt{6n}} 和 g''(z_0)=\dfrac{2n\sqrt{6n}}{\pi}，即得系数部分为 \dfrac{1}{4\sqrt3n}。因此有：

p_n\sim\dfrac{1}{4\sqrt3n}\exp\left(\pi\sqrt{\dfrac{2n}3}\right)

算是填了一个坑吧。

在此基础上，Rademacher 得到了分拆数的收敛级数，完整的公式极为冗长在此略去。

为了得到更好的渐进公式，还需要更深入的椭圆模函数知识，第四节将会对这部分内容做一个大致的引入。