狄利克雷生成函数

记 $P$ 表示素数集合。

狄利克雷生成函数

对于无穷序列 $f_{1}, f_{2}, \dots$ ，定义其狄利克雷生成函数（Dirichlet series generating function，DGF）¹为：

\tilde{F} (x) = \sum_{i \geq 1} \frac{f_{i}}{i^{x}}

如果序列 $f$ 满足积性（是积性函数）： $\forall i ⟂ j, f_{i j} = f_{i} f_{j}$ ，那么其 DGF 可以由质数幂处的取值表示：

\tilde{F} (x) = \prod_{p \in P} (1 + \frac{f_{p}}{p^{x}} + \frac{f_{p^{2}}}{p^{2 x}} + \frac{f_{p^{3}}}{p^{3 x}} + \dots)

对于两个序列 $f, g$ ，其 DGF 之积对应的是两者的狄利克雷卷积序列的 DGF：

\tilde{F} (x) \tilde{G} (x) = \sum_{i} \sum_{j} \frac{f_{i} g_{j}}{(i j)^{x}} = \sum_{i} \frac{1}{i^{x}} \sum_{d | i} f_{d} g_{\frac{i}{d}}

常见积性函数的 DGF

DGF 最适合用于研究与积性函数的狄利克雷卷积相关的问题。因此首先我们要了解常见积性函数的 DGF。

黎曼函数

序列 $[1, 1, 1, \dots]$ 的 DGF 是 $\sum_{i \geq 1} \frac{1}{i^{x}} = ζ (x)$ 。 $ζ$ 是黎曼函数。

由于其满足积性，因此我们可以得到 $[1, 1, 1, \dots]$ 的 DGF 的另一种形式：

ζ (x) = \prod_{p \in P} (1 + \frac{1}{p^{x}} + \frac{1}{p^{2 x}} + \dots) = \prod_{p \in P} \frac{1}{1 - p^{- x}}

莫比乌斯函数

对于莫比乌斯函数 $μ$ ，它的 DGF 定义为

\tilde{M} (x) = \prod_{p \in P} (1 - \frac{1}{p^{x}}) = \prod_{p \in P} (1 - p^{- x})

容易发现 $ζ (x) \tilde{M} (x) = 1$ ，也就是说 $\tilde{M} (x) = \frac{1}{ζ (x)}$ 。

欧拉函数

对于欧拉函数 $φ$ ，它的 DGF 定义为

\tilde{Φ} (x) = \prod_{p \in P} (1 + \frac{p - 1}{p^{x}} + \frac{p (p - 1)}{p^{2 x}} + \frac{p^{2} (p - 1)}{p^{3 x}} + \dots) = \prod_{p \in P} \frac{1 - p^{- x}}{1 - p^{1 - x}}

因此有 $\tilde{Φ} (x) = \frac{ζ (x - 1)}{ζ (x)}$ 。

幂函数

对于函数 $I_{k} (n) = n^{k}$ ，它的 DGF 定义为

\tilde{I_{k}} (x) = \prod_{p \in P} (1 + \frac{p^{k}}{p^{x}} + \frac{p^{2 k}}{p^{2 x}} + \dots) = \prod_{p \in P} \frac{1}{1 - p^{k - x}} = ζ (x - k)

根据这些定义，容易推导出 $φ * 1 = I$ ， $*$ 表示狄利克雷卷积。因为 $\tilde{Φ} (x) ζ (x) = ζ (x - 1)$ 。

其他函数

对于约数幂函数 $σ_{k} (n) = \sum_{d | n} d^{k}$ ，它的 DGF 可以表示为狄利克雷卷积的形式： $\tilde{S} (x) = ζ (x - k) ζ (x)$ 。

对于 $u (n) = | μ (n) |$ （无平方因子数），它的 DGF 为 $\tilde{U} (x) = \prod_{p \in P} (1 + p^{- x}) = \frac{ζ (x)}{ζ (2 x)}$ 。

Dirichlet 卷积

定义

对于两个数论函数 $f (x)$ 和 $g (x)$ ，则它们的狄利克雷卷积得到的结果 $h (x)$ 定义为：

h (x) = \sum_{d ∣ x} f (d) g (\frac{x}{d}) = \sum_{a b = 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}}{(i j)^{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) \neq 0$ 。

证明： 充分性是显然的。
证明必要性，我们先假设存在 $x$ ，使得 $f (x) \neq g (y)$ 。那么我们找到最小的 $y \in N$ ，满足 $f (y) \neq g (y)$ ，并设 $r = f * h - g * h = (f - g) * h$ 。
则有：
$\begin{aligned} r (y) & = \sum_{d ∣ y} (f (d) - g (d)) h (\frac{y}{d}) \\ = (f (y) - g (y)) h (1) \\ \neq 0 \end{aligned}$
则 $f * h$ 和 $g * h$ 在 $y$ 处的取值不一样，即有 $f * h \neq g * h$ 。矛盾，所以必要性成立。
证毕

注

以上性质在狄利克雷生成函数的观点下是显然的，这种特殊的卷积等价于相应生成函数的乘法。

单位元： 单位函数 $ε$ 是 Dirichlet 卷积运算中的单位元，即对于任何数论函数 $f$ ，都有 $f * ε = f$ 。

注

狄利克雷卷积运算中的单位元不是常函数，但是在狄利克雷生成函数中等价于常数 $1$ 。

狄利克雷卷积运算中的数论函数常函数 $1$ ，在狄利克雷生成函数中等价于黎曼函数 $ζ$ 。

逆元： 对于任何一个满足 $f (x) \neq 0$ 的数论函数，如果有另一个数论函数 $g (x)$ 满足 $f * g = ε$ ，则称 $g (x)$ 是 $f (x)$ 的逆元。由 等式的性质 可知，逆元是唯一的。

注

狄利克雷卷积运算中的逆元，在狄利克雷生成函数中相当于倒数运算。

容易构造出 $g (x)$ 的表达式为：

g (x) = \frac{ε (x) - \sum_{d ∣ x, d \neq 1} f (d) g (\frac{x}{d})}{f (1)}

重要结论

两个积性函数的 Dirichlet 卷积也是积性函数

证明： 设两个积性函数为 $f (x)$ 和 $g (x)$ ，再记 $h = f * g$ 。

设 $gcd (a, b) = 1$ ，则：

h (a) = \sum_{d_{1} ∣ a} f (d_{1}) g (\frac{a}{d_{1}}), h (b) = \sum_{d_{2} ∣ b} f (d_{2}) g (\frac{b}{d_{2}}),

所以：

\begin{aligned} h (a) h (b) & = \sum_{d_{1} ∣ a} f (d_{1}) g (\frac{a}{d_{1}}) \sum_{d_{2} ∣ b} f (d_{2}) g (\frac{b}{d_{2}}) \\ = \sum_{d ∣ a b} f (d) g (\frac{a b}{d}) \\ = h (a b) \end{aligned}

所以结论成立。

证毕

积性函数的逆元也是积性函数

证明：我们设 $f * g = ε$ ，并且不妨设 $f (1) = 1$ 。考虑归纳法：

若 $n m = 1$ ，则 $g (n m) = g (1) = 1$ ，结论显然成立；
若 $n m > 1 (gcd (n, m) = 1)$ ，假设现在对于所有的 $x y < n m (gcd (x, y) = 1)$ ，都有 $g (x y) = g (x) g (y)$ ，所以有：
$g (n m) = - \sum_{d ∣ n m, d \neq 1} f (d) g (\frac{n m}{d}) = - \sum_{a ∣ n, b ∣ m, a b \neq 1} f (a b) g (\frac{n m}{a b})$
又因为 $\frac{n m}{a b} < n m$ ，所以有：
$\begin{aligned} g (n m) & = - \sum_{a ∣ n, b ∣ m, a b \neq 1} f (a b) g (\frac{n m}{a b}) \\ = - \sum_{a ∣ n, b ∣ m, a b \neq 1} f (a) f (b) g (\frac{n}{a}) g (\frac{m}{b}) \\ = f (1) f (1) g (n) g (m) - \sum_{a ∣ n, b ∣ m} f (a) f (b) g (\frac{n}{a}) g (\frac{m}{b}) \\ = g (n) g (m) - \sum_{a ∣ n} f (a) g (\frac{n}{a}) \sum_{b ∣ m} f (b) g (\frac{m}{b}) \\ = g (n) g (m) - ε (n) ε (m) \\ = g (n) g (m) \end{aligned}$

综合以上两点，结论成立。

证毕

注

这也说明，数论函数的积性，在狄利克雷生成函数中的对应具有封闭性。

例子

\begin{aligned} ε = μ * 1 & ⟺ ε (n) = \sum_{d ∣ n} μ (d) \\ d = 1 * 1 & ⟺ d (n) = \sum_{d ∣ n} 1 \\ σ = id * 1 & ⟺ σ (n) = \sum_{d ∣ n} d \\ φ = μ * id & ⟺ φ (n) = \sum_{d ∣ n} d \cdot μ (\frac{n}{d}) \end{aligned}

狄利克雷生成函数