分析組合學/陶伯定理

引言

“陶伯”指的是一類具有廣泛應用的定理。陶伯定理的完整範圍在這裡無法涵蓋。

我們這裡只證明由哈代、利特爾伍德和卡拉馬塔提出的一個特殊的陶伯定理，它在分析組合學中很有用。

定理

哈代提出的定理。

如果$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). 分析中的漸近方法. 多佛出版物.