分析组合学/陶伯定理

引言

“陶伯”指的是一类具有广泛应用的定理。陶伯定理的完整范围在这里无法涵盖。

我们这里只证明由哈代、利特尔伍德和卡拉马塔提出的一个特殊的陶伯定理，它在分析组合学中很有用。

定理

哈代提出的定理。

如果$f(y)\sim y^{-\sigma }L(y^{-1})$ 当$y\to 0$，其中$\sigma >0$ 且$L(y)$ 是一个缓慢变化函数，则$a_{n}\sim {\frac {n^{\sigma -1}}{\Gamma (\sigma )}}L(n)$ 当$n\to \infty$。

请记住，如果$f(x)=\sum a_{n}x^{n}={\frac {1}{(1-x)^{\sigma }}}L({\frac {1}{1-x}})$，我们可以通过替换$x=e^{-y}$将其转换为广义狄利克雷级数（不会改变我们感兴趣的系数的值），使得

$f(y)=\sum a_{n}(e^{-y})^{n}={\frac {1}{(1-e^{-y})^{\sigma }}}L({\frac {1}{1-e^{-y}}})\sim y^{-\sigma }L(y^{-1})$

当$y\to 0$。

这给了我们

$[x^{n}]{\frac {1}{(1-x)^{\sigma }}}L({\frac {1}{1-x}})\sim {\frac {n^{\sigma -1}}{\Gamma (\sigma )}}L(n)$

该公式在 Flajolet 和 Sedgewick 2009 年的著作中给出，参见第 435 页。

证明

哈代给出的证明。

如果$f(x)={\frac {1}{(1-x)^{\sigma }}}L({\frac {1}{1-x}})=\sum _{0}^{\infty }a_{n}x^{n}$，那么该方法实际上找到了$s_{n}=\sum _{i=0}^{n}a_{i}$的渐近估计，之后我们可以通过$s_{n}-s_{n-1}$或在$(1-x)f(x)$中找到$s_{n}$来找到$a_{n}$。

令$a(t)$为一个阶梯函数阶梯函数，其中$a(n)-a(n-1)=a_{n}$，$a(n)=\sum _{i=0}^{n}a_{i}$ 且 $a(0)=0$。

$a(y^{-1})=\int _{0}^{y^{-1}}da(t)$

使用分部积分法

$\int _{0}^{y^{-1}}da(t)=a(y^{-1})-a(0)-\int _{0}^{y^{-1}}a(t)d1=a(y^{-1})$

因为 $a(0)=\int _{0}^{y^{-1}}a(t)d1=0$。

如果 $g(x)=x^{-1}\quad (e^{-1}\leq x\leq 1),\quad g(x)=0\quad (0\leq x<e^{-1})$ 那么

$\int _{0}^{y^{-1}}da(t)=\int _{0}^{\infty }e^{-yt}g(e^{-yt})da(t)$

因为当 $0\leq t\leq y^{-1}$ 时，$e^{-yt}g(e^{-yt})$ 的取值范围是从 $e^{-1}g(e^{-1})$ 到 $e^{0}g(e^{0})$，所以 $e^{-yt}g(e^{-yt})={\frac {e^{yt}}{e^{yt}}}=1$，而当 $t>y^{-1}$ 时，$e^{-yt}g(e^{-yt})=0$。

引理 1

$\int _{0}^{\infty }e^{-yt}g(e^{-yt})da(t)\sim {\frac {1}{\Gamma (\sigma )}}y^{-\sigma }L(y^{-1})\int _{0}^{\infty }e^{-t}t^{\sigma -1}g(e^{-t})dt$

当 $y\to 0$。

为了证明这一点，我们需要另外两个引理。

引理 2

$\int _{0}^{\infty }e^{-yt}Q(e^{-yt})da(t)\sim {\frac {1}{\Gamma (\sigma )}}y^{-\sigma }L(y^{-1})\int _{0}^{\infty }e^{-t}t^{\sigma -1}Q(e^{-t})dt$

其中 $Q$ 是任意多项式，并且当 $y\to 0$。

$\int _{0}^{\infty }e^{-yt}Q(e^{-yt})da(t)=\int _{0}^{\infty }e^{-yt}(\cdots +e^{-ytn}+\cdots )da(t)=\int _{0}^{\infty }\cdots +\int _{0}^{\infty }e^{-yt}e^{-ytn}da(t)+\int _{0}^{\infty }\cdots$

$\int _{0}^{\infty }e^{-yt}e^{-ytn}da(t)=\int _{0}^{\infty }e^{-(n+1)yt}da(t)\sim (n+1)^{-\sigma }y^{-\sigma }L({\frac {1}{(n+1)y}})$

当 $y\to 0$，根据定理中的假设。

$(n+1)^{-\sigma }y^{-\sigma }L({\frac {1}{(n+1)y}})\sim (n+1)^{-\sigma }y^{-\sigma }L({\frac {1}{y}})$

根据慢变函数的定义。

$(n+1)^{-\sigma }y^{-\sigma }L({\frac {1}{y}})=y^{-\sigma }L({\frac {1}{y}}){\frac {1}{\Gamma (\sigma )}}\int _{0}^{\infty }e^{-t}e^{-tn}t^{\sigma -1}dt$

$\cdots +y^{-\sigma }L({\frac {1}{y}}){\frac {1}{\Gamma (\sigma )}}\int _{0}^{\infty }e^{-t}e^{-tm}t^{\sigma -1}dt+y^{-\sigma }L({\frac {1}{y}}){\frac {1}{\Gamma (\sigma )}}\int _{0}^{\infty }e^{-t}e^{-tn}t^{\sigma -1}dt+\cdots =y^{-\sigma }L({\frac {1}{y}}){\frac {1}{\Gamma (\sigma )}}\int _{0}^{\infty }e^{-t}Q(e^{-t})t^{\sigma -1}dt$

引理 3

如果$g(x)$ 是实值且在开区间$(0,1)$ 上黎曼可积，且$\sigma >0$，则存在多项式$p(x)$ 和 $P(x)$ 使得 $p(x)<g(x)<P(x)$ 并且

$\int _{0}^{1}(P(x)-p(x))(log{\frac {1}{x}})^{\sigma -1}dx=\int _{0}^{\infty }e^{-t}t^{\sigma -1}(P(e^{-t})-p(e^{-t}))dt<\epsilon \Gamma (\sigma )$

构造连续函数$h$ 和 $H$ 使得

$h\leq g\leq H,\quad \int _{0}^{1}(H-g)dx<\epsilon ,\quad \int _{0}^{1}(g-h)dx<\epsilon$

那么

$\int _{0}^{1}(H-g)(log{\frac {1}{x}})^{\sigma -1}dx<\epsilon \int _{0}^{1}(log{\frac {1}{x}})^{\sigma -1}dx=\epsilon \Gamma (\sigma )$

以及

$\int _{0}^{1}(g-h)(log{\frac {1}{x}})^{\sigma -1}dx<\epsilon \int _{0}^{1}(log{\frac {1}{x}})^{\sigma -1}dx=\epsilon \Gamma (\sigma )$

根据魏尔斯特拉斯逼近定理，存在多项式$q$ 和 $Q$ 使得 $|Q-h|<\epsilon$ 以及 $|h-q|<\epsilon$。如果 $p(x)=q(x)-\epsilon$ 以及 $P(x)=Q(x)+\epsilon$，那么 $p(x)<g(x)<P(x)$，如引理所要求的那样，并且

$\int _{0}^{1}(P(x)-g(x))(log{\frac {1}{x}})^{\sigma -1}dx\leq \int _{0}^{1}(P(x)-Q(x))(log{\frac {1}{x}})^{\sigma -1}dx+\int _{0}^{1}|Q(x)-h(x)|(log{\frac {1}{x}})^{\sigma -1}dx+\int _{0}^{1}(h(x)-g(x))(log{\frac {1}{x}})^{\sigma -1}dx<3\epsilon \Gamma (\sigma )$

由于 $g(x)$ 是黎曼可积的，我们可以找到有限阶梯函数 $g_{1}$ 和 $g_{2}$，使得 $g_{1}(x)\leq g(x)\leq g_{2}(x)$ 并且

$\int _{0}^{1}(g_{2}(x)-g_{1}(x))(log{\frac {1}{x}})^{\sigma -1}dx<3\epsilon \Gamma (\sigma )$

然后，我们已经在上面证明了存在多项式 $p(x)$ 和 $P(x)$，使得 $p(x)<g_{1}(x)\leq g(x)\leq g_{2}(x)<P(x)$ 并且

$\int _{0}^{1}(P(x)-g_{2}(x))(log{\frac {1}{x}})^{\sigma -1}dx<\epsilon \Gamma (\sigma ),\quad \int _{0}^{1}(g_{1}(x)-p(x))(log{\frac {1}{x}})^{\sigma -1}dx<\epsilon \Gamma (\sigma )$

结合这些，我们可以完成引理 3 的证明。

$\int _{0}^{1}(P(x)-p(x))(log{\frac {1}{x}})^{\sigma -1}dx<5\epsilon \Gamma (\sigma )$

回到引理 1的证明。

$\limsup _{y\to \infty }\int _{0}^{\infty }e^{-yt}g(e^{-yt})da(t)\leq \lim _{y\to \infty }\int _{0}^{\infty }e^{-yt}P(e^{-yt})da(t)={\frac {1}{\Gamma (\sigma )}}y^{-\sigma }L(y^{-1})\int _{0}^{\infty }e^{-t}t^{\sigma -1}P(e^{-t})dt$

根据引理 2。

引理 3 意味着

$\int _{0}^{\infty }e^{-t}t^{\sigma -1}(P(e^{-t})-g(e^{-t}))dt<\epsilon \Gamma (\sigma )$

因此

${\frac {1}{\Gamma (\sigma )}}y^{-\sigma }L(y^{-1})\int _{0}^{\infty }e^{-t}t^{\sigma -1}P(e^{-t})dt-{\frac {1}{\Gamma (\sigma )}}y^{-\sigma }L(y^{-1})\int _{0}^{\infty }e^{-t}t^{\sigma -1}g(e^{-t})dt<\epsilon$

以及

${\frac {1}{\Gamma (\sigma )}}y^{-\sigma }L(y^{-1})\int _{0}^{\infty }e^{-t}t^{\sigma -1}P(e^{-t})dt<{\frac {1}{\Gamma (\sigma )}}y^{-\sigma }L(y^{-1})\int _{0}^{\infty }e^{-t}t^{\sigma -1}g(e^{-t})dt+\epsilon$

最后

$\limsup _{y\to \infty }\int _{0}^{\infty }e^{-yt}g(e^{-yt})da(t)<{\frac {1}{\Gamma (\sigma )}}y^{-\sigma }L(y^{-1})\int _{0}^{\infty }e^{-t}t^{\sigma -1}g(e^{-t})dt+\epsilon$

通过类似的论证，可以证明

$\liminf _{y\to \infty }\int _{0}^{\infty }e^{-yt}g(e^{-yt})da(t)>{\frac {1}{\Gamma (\sigma )}}y^{-\sigma }L(y^{-1})\int _{0}^{\infty }e^{-t}t^{\sigma -1}g(e^{-t})dt-\epsilon$

结合这两个结果，我们得出引理1的证明

$\int _{0}^{\infty }e^{-yt}g(e^{-yt})da(t)\sim {\frac {1}{\Gamma (\sigma )}}y^{-\sigma }L(y^{-1})\int _{0}^{\infty }e^{-t}t^{\sigma -1}g(e^{-t})dt$

综合以上结果

$a(y^{-1})=\int _{0}^{y^{-1}}da(t)=\int _{0}^{\infty }e^{-yt}g(e^{-yt})da(t)\sim {\frac {1}{\Gamma (\sigma )}}y^{-\sigma }L(y^{-1})\int _{0}^{\infty }e^{-t}t^{\sigma -1}g(e^{-t})dt={\frac {1}{\Gamma (\sigma )}}y^{-\sigma }L(y^{-1})\int _{0}^{1}t^{\sigma -1}dt={\frac {1}{\Gamma (\sigma +1)}}y^{-\sigma }L(y^{-1})$

或者

$a(y)={\frac {y^{\sigma }}{\Gamma (\sigma +1)}}L(y)$.

当 $y\to \infty$。那么，如果 $f(x)={\frac {1}{(1-x)^{\sigma }}}L({\frac {1}{1-x}})$

$a_{n}=[x^{n}]{\frac {1}{(1-x)^{\sigma }}}L({\frac {1}{1-x}})=[s_{n}]{\frac {(1-x)}{(1-x)^{\sigma }}}L({\frac {1}{1-x}})=[s_{n}]{\frac {1}{(1-x)^{\sigma -1}}}L({\frac {1}{1-x}})={\frac {n^{\sigma -1}}{\Gamma (\sigma )}}L(n)$

参考文献

• Hardy, G.H. (1949). 发散级数 (第1版). 牛津大学出版社.
• Flajolet, Philippe; Sedgewick, Robert (2009). 分析组合学 (PDF). 剑桥大学出版社.
• De Bruijn, N.G. (1981). 分析中的渐近方法. 多佛出版物.