狄利克雷生成函数

记 表示素数集合。

对于无穷序列 ，定义其狄利克雷生成函数（Dirichlet series generating function，DGF）1为：

如果序列 满足积性（是 积性函数）：，那么其 DGF 可以由质数幂处的取值表示：

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

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

序列 的 DGF 是 。 是黎曼函数。

由于其满足积性，因此我们可以得到 的 DGF 的另一种形式：

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

容易发现 ，也就是说 。

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

因此有 。

对于函数 ，它的 DGF 定义为

根据这些定义，容易推导出 ， 表示狄利克雷卷积。因为 。

对于约数幂函数 ，它的 DGF 可以表示为狄利克雷卷积的形式：。

对于 （无平方因子数），它的 DGF 为 。

对于两个数论函数 和 ，则它们的狄利克雷卷积得到的结果 定义为：

上式可以简记为：

狄利克雷卷积是数论函数的重要运算，数论函数的许多性质都是通过这个运算挖掘出来的。

狄利克雷卷积与狄利克雷生成函数（DGF）密切相关。对于两个序列 ，其狄利克雷生成函数之积，对应的是两者的狄利克雷卷积序列的狄利克雷生成函数：

交换律： 。

结合律：。

分配律：。

等式的性质： 的充要条件是 ，其中数论函数 要满足 。

证明： 充分性是显然的。

证明必要性，我们先假设存在 ，使得 。那么我们找到最小的 ，满足 ，并设 。

则有：

则 和 在 处的取值不一样，即有 。矛盾，所以必要性成立。

证毕

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

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

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

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

逆元： 对于任何一个满足 的数论函数，如果有另一个数论函数 满足 ，则称 是 的逆元。由 等式的性质 可知，逆元是唯一的。

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

容易构造出 的表达式为：

证明： 设两个积性函数为 和 ，再记 。

设 ，则：

所以：

所以结论成立。

证毕

证明：我们设 ，并且不妨设 。考虑归纳法：

若 ，则 ，结论显然成立；

若 ，假设现在对于所有的 ，都有 ，所以有：

又因为 ，所以有：

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

证毕

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

DGF 的应用主要体现在构造积性序列的狄利克雷卷积序列。研究方向通常是质数处的取值。

例如在杜教筛的过程中，要计算积性序列（积性函数在正整数处的取值构成的序列） 的前缀和，我们需要找到一个积性序列 使得 和 都可以快速求前缀和。那么我们可以利用 DGF 推导这一过程。

以 洛谷 P3768 简单的数学题 为例，我们要对 构造一个满足上述条件的积性序列 。由于 是积性的，考虑其 DGF

因此 。而 对应的积性函数为 ，所以令 即可。这样有 ，两者都是可以快速计算前缀和的。

https://en.wikipedia.org/wiki/Generating_function#Dirichlet_series_generating_functions_(DGFs) ↩