狄利克雷生成函數

記 \(\mathcal{P}\) 表示素數集合。

狄利克雷生成函數

對於無窮序列 \(f_1, f_2, \ldots\)，定義其狄利克雷生成函數（Dirichlet series generating function，DGF）¹為：

\[ \tilde{F}(x) = \sum_{i\ge 1}\frac{f_i}{i^x} \]

如果序列 \(f\) 滿足積性（是積性函數）：\(\forall i\perp j, \; f_{ij} = f_i f_j\)，那麼其 DGF 可以由質數冪處的取值表示：

\[ \tilde{F}(x) = \prod_{p\in \mathcal{P}} \left(1 + \frac{f_p}{p^x} + \frac{f_{p^2}}{p^{2x}} + \frac{f_{p^3}}{p^{3x}} + \cdots \right) \]

對於兩個序列 \(f, g\)，其 DGF 之積對應的是兩者的狄利克雷卷積序列的 DGF：

\[ \tilde{F}(x)\tilde{G}(x) = \sum_{i} \sum_{j}\frac{f_i g_j}{(ij)^x} = \sum_{i} \frac{1}{i^x}\sum_{d | i} f_d g_{\frac{i}{d}} \]

常見積性函數的 DGF

DGF 最適合用於研究與積性函數的狄利克雷卷積相關的問題。因此首先我們要了解常見積性函數的 DGF。

黎曼函數

序列 \([1, 1, 1, \ldots]\) 的 DGF 是 \(\sum_{i\ge 1}\frac{1}{i^x} = \zeta(x)\)。\(\zeta\) 是黎曼函數。

由於其滿足積性，因此我們可以得到 \([1, 1, 1, \ldots]\) 的 DGF 的另一種形式：

\[ \zeta(x) = \prod_{p\in\mathcal{P}} \left(1 + \frac{1}{p^x} + \frac{1}{p^{2x}} + \ldots \right) = \prod_{p\in \mathcal{P}} \frac{1}{1-p^{-x}} \]

莫比烏斯函數

對於莫比烏斯函數 \(\mu\)，它的 DGF 定義為

\[ \tilde{M} (x) = \prod_{p\in \mathcal{P}}\left(1 - \frac{1}{p^x}\right) = \prod_{p\in \mathcal{P}}(1-p^{-x}) \]

容易發現 \(\zeta(x) \tilde{M}(x) = 1\)，也就是説 \(\tilde{M}(x) = \frac{1}{\zeta(x)}\)。

歐拉函數

對於歐拉函數 \(\varphi\)，它的 DGF 定義為

\[ \tilde{\Phi}(x) = \prod_{p\in\mathcal{P}} \left(1 + \frac{p-1}{p^x} + \frac{p(p-1)}{p^{2x}} + \frac{p^2(p-1)}{p^{3x}} + \ldots \right) = \prod_{p\in \mathcal{P}}\frac{1-p^{-x}}{1-p^{1-x}} \]

因此有 \(\tilde{\Phi}(x) = \frac{\zeta(x-1)}{\zeta(x)}\)。

冪函數

對於函數 \(I_k (n) = n^k\)，它的 DGF 定義為

\[ \tilde{I_k} (x) = \prod_{p\in\mathcal{P}} \left(1 + \frac{p^k}{p^x} + \frac{p^{2k}}{p^{2x}} + \ldots \right) = \prod_{p\in \mathcal{P}} \frac{1}{1-p^{k-x}} = \zeta(x-k) \]

根據這些定義，容易推導出 \(\varphi \ast 1 = I\)，\(\ast\) 表示狄利克雷卷積。因為 \(\tilde{\Phi}(x)\zeta(x) = \zeta(x-1)\)。

其他函數

對於約數冪函數 \(\sigma_k(n) = \sum_{d|n}d^k\)，它的 DGF 可以表示為狄利克雷卷積的形式：\(\tilde S(x) = \zeta(x-k)\zeta(x)\)。

對於 \(u(n) = |\mu(n)|\)（無平方因子數），它的 DGF 為 \(\tilde{U}(x) = \prod_{p\in \mathcal{P}} (1+p^{-x}) = \frac{\zeta(x)}{\zeta(2x)}\)。

Dirichlet 卷積

定義

對於兩個數論函數 \(f(x)\) 和 \(g(x)\)，則它們的狄利克雷卷積得到的結果 \(h(x)\) 定義為：

\[ h(x)=\sum_{d\mid x}{f(d)g\left(\dfrac xd \right)}=\sum_{ab=x}{f(a)g(b)} \]

上式可以簡記為：

\[ h=f*g \]

狄利克雷卷積是數論函數的重要運算，數論函數的許多性質都是通過這個運算挖掘出來的。

狄利克雷卷積與狄利克雷生成函數（DGF）密切相關。對於兩個序列 \(f, g\)，其狄利克雷生成函數之積，對應的是兩者的狄利克雷卷積序列的狄利克雷生成函數：

\[ \tilde{F}(x)\tilde{G}(x) = \sum_{i} \sum_{j}\frac{f_i g_j}{(ij)^x} = \sum_{i} \frac{1}{i^x}\sum_{d | i} f_d g_{\frac{i}{d}} \]

性質

交換律： \(f*g=g*f\)。

結合律：\((f*g)*h=f*(g*h)\)。

分配律：\((f+g)*h=f*h+g*h\)。

等式的性質： \(f=g\) 的充要條件是 \(f*h=g*h\)，其中數論函數 \(h(x)\) 要滿足 \(h(1)\ne 0\)。

證明： 充分性是顯然的。

證明必要性，我們先假設存在 \(x\)，使得 \(f(x)\ne g(y)\)。那麼我們找到最小的 \(y\in \mathbb{N}\)，滿足 \(f(y)\ne g(y)\)，並設 \(r=f*h-g*h=(f-g)*h\)。

則有：

\[ \begin{aligned} r(y)&=\sum_{d\mid y}{(f(d)-g(d))h\left(\dfrac yd \right)}\\ &=(f(y)-g(y))h(1)\\ &\ne 0 \end{aligned} \]

則 \(f*h\) 和 \(g*h\) 在 \(y\) 處的取值不一樣，即有 \(f*h\ne g*h\)。矛盾，所以必要性成立。

證畢

注

以上性質在狄利克雷生成函數的觀點下是顯然的，這種特殊的卷積等價於相應生成函數的乘法。

單位元： 單位函數 \(\varepsilon\) 是 Dirichlet 卷積運算中的單位元，即對於任何數論函數 \(f\)，都有 \(f*\varepsilon=f\)。

注

狄利克雷卷積運算中的單位元不是常函數，但是在狄利克雷生成函數中等價於常數 \(1\)。

狄利克雷卷積運算中的數論函數常函數 \(1\)，在狄利克雷生成函數中等價於黎曼函數 \(\zeta\)。

逆元： 對於任何一個滿足 \(f(x)\ne 0\) 的數論函數，如果有另一個數論函數 \(g(x)\) 滿足 \(f*g=\varepsilon\)，則稱 \(g(x)\) 是 \(f(x)\) 的逆元。由 等式的性質 可知，逆元是唯一的。

注

狄利克雷卷積運算中的逆元，在狄利克雷生成函數中相當於倒數運算。

容易構造出 \(g(x)\) 的表達式為：

\[ g(x)=\dfrac {\varepsilon(x)-\sum_{d\mid x,d\ne 1}{f(d)g\left(\dfrac {x}{d} \right)}}{f(1)} \]

重要結論

兩個積性函數的 Dirichlet 卷積也是積性函數

證明： 設兩個積性函數為 \(f(x)\) 和 \(g(x)\)，再記 \(h=f*g\)。

設 \(\gcd(a,b)=1\)，則：

\[ h(a)=\sum_{d_1\mid a}{f(d_1)g\left(\dfrac a{d_1} \right)},h(b)=\sum_{d_2\mid b}{f(d_2)g\left(\dfrac b{d_2} \right)}, \]

所以：

\[ \begin{aligned} h(a)h(b)&=\sum_{d_1\mid a}{f(d_1)g\left(\dfrac a{d_1} \right)}\sum_{d_2\mid b}{f(d_2)g\left(\dfrac b{d_2} \right)}\\ &=\sum_{d\mid ab}{f(d)g\left(\dfrac {ab}d \right)}\\ &=h(ab) \end{aligned} \]

所以結論成立。

證畢

積性函數的逆元也是積性函數

證明：我們設 \(f*g=\varepsilon\)，並且不妨設 \(f(1)=1\)。考慮歸納法：

若 \(nm=1\)，則 \(g(nm)=g(1)=1\)，結論顯然成立；
若 \(nm>1(\gcd(n,m)=1)\)，假設現在對於所有的 \(xy<nm(\gcd(x,y)=1)\)，都有 \(g(xy)=g(x)g(y)\)，所以有：

\[ g(nm)=-\sum_{d\mid nm,d\ne 1}{f(d)g\left(\dfrac {nm}d \right)}=-\sum_{a\mid n,b\mid m,ab\ne 1}{f(ab)g\left(\dfrac {nm}{ab} \right)} \]

又因為 \(\dfrac{nm}{ab}<nm\)，所以有：

\[ \begin{aligned} g(nm)&=-\sum_{a\mid n,b\mid m,ab\ne 1}{f(ab)g\left(\dfrac {nm}{ab} \right)}\\\\ &=-\sum_{a\mid n,b\mid m,ab\ne 1}{f(a)f(b)g\left(\dfrac {n}{a} \right)g\left(\dfrac {m}{b} \right)}\\\\ &=f(1)f(1)g(n)g(m)-\sum_{a\mid n,b\mid m}{f(a)f(b)g\left(\dfrac {n}{a} \right)g\left(\dfrac {m}{b} \right)}\\\\ &=g(n)g(m)-\sum_{a\mid n}{f(a)g\left(\dfrac {n}{a} \right)}\sum_{b\mid m}{f(b)g\left(\dfrac {m}{b} \right)}\\\\ &=g(n)g(m)-\varepsilon(n)-\varepsilon(m)\\\\ &=g(n)g(m) \end{aligned} \]

綜合以上兩點，結論成立。

證畢

注

這也説明，數論函數的積性，在狄利克雷生成函數中的對應具有封閉性。

例子

\[ \begin{aligned} \varepsilon=\mu \ast 1&\iff\varepsilon(n)=\sum_{d\mid n}\mu(d)\\ d=1 \ast 1&\iff d(n)=\sum_{d\mid n}1\\ \sigma=\operatorname{id} \ast 1&\iff\sigma(n)=\sum_{d\mid n}d\\ \varphi=\mu \ast \operatorname{id}&\iff\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d}) \end{aligned} \]

狄利克雷生成函數