狄利克雷生成函数

记 P 表示素数集合。

狄利克雷生成函数¶

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

F~(x)=∑i≥1fiix

如果序列 f 满足积性（积性函数2）：∀i⊥j,fij=fifj，那么其 DGF 可以由质数幂处的取值表示：

F~(x)=∏p∈P(1+fppx+fp2p2x+fp3p3x+⋯)

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

F~(x)G~(x)=∑i∑jfigj(ij)x=∑i1ix∑d|ifdgid

常见积性函数的 DGF¶

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

黎曼函数¶

序列 [1,1,1,…] 的 DGF 是 ∑i≥11ix=ζ(x)。ζ 是黎曼函数。

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

ζ(x)=∏p∈P(1+1px+1p2x+…)=∏p∈P11−p−x

莫比乌斯函数¶

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

M~(x)=∏p∈P(1−1px)=∏p∈P(1−p−x)

容易发现 ζ(x)M~(x)=1，也就是说 M~(x)=1ζ(x)。

欧拉函数¶

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

Φ~(x)=∏p∈P(1+p−1px+p(p−1)p2x+p2(p−1)p3x+…)=∏p∈P1−p−x1−p1−x

因此有 Φ~(x)=ζ(x−1)ζ(x)。

幂函数¶

对于函数 Ik(n)=nk，它的 DGF 定义为

Ik~(x)=∏p∈P(1+pkpx+p2kp2x+…)=∏p∈P11−pk−x=ζ(x−k)

根据这些定义，容易推导出 φ∗1=I，∗ 表示狄利克雷卷积。因为 Φ~(x)ζ(x)=ζ(x−1)。

其他函数¶

对于约数幂函数 σk(n)=∑d|ndk，它的 DGF 可以表示为狄利克雷卷积的形式：S~(x)=ζ(x−k)ζ(x)。

对于 u(n)=|μ(n)|（无平方因子数），它的 DGF 为 U~(x)=∏p∈P(1+p−x)=ζ(x)ζ(2x)。

Dirichlet 卷积¶

定义¶

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

h(x)=∑d∣xf(d)g(xd)=∑ab=xf(a)g(b)

上式可以简记为：

h=f∗g

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

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

F~(x)G~(x)=∑i∑jfigj(ij)x=∑i1ix∑d|ifdgid

性质¶

交换律： 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)≠0。

证明： 充分性是显然的。

证明必要性，我们先假设存在 x，使得 f(x)≠g(y)。那么我们找到最小的 y∈N，满足 f(y)≠g(y)，并设 r=f∗h−g∗h=(f−g)∗h。

r(y)=∑d∣y(f(d)−g(d))h(yd)=(f(y)−g(y))h(1)≠0

则 f∗h 和 g∗h 在 y 处的取值不一样，即有 f∗h≠g∗h。矛盾，所以必要性成立。

证毕

注

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

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

注

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

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

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

注

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

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

g(x)=ε(x)−∑d∣x,d≠1f(d)g(xd)f(1)

重要结论¶

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

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

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

h(a)=∑d1∣af(d1)g(ad1),h(b)=∑d2∣bf(d2)g(bd2),

h(a)h(b)=∑d1∣af(d1)g(ad1)∑d2∣bf(d2)g(bd2)=∑d∣abf(d)g(abd)=h(ab)

所以结论成立。

证毕

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

证明：我们设 f∗g=ε，并且不妨设 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)=−∑d∣nm,d≠1f(d)g(nmd)=−∑a∣n,b∣m,ab≠1f(ab)g(nmab) 又因为 nmab<nm，所以有： g(nm)=−∑a∣n,b∣m,ab≠1f(ab)g(nmab)=−∑a∣n,b∣m,ab≠1f(a)f(b)g(na)g(mb)=f(1)f(1)g(n)g(m)−∑a∣n,b∣mf(a)f(b)g(na)g(mb)=g(n)g(m)−∑a∣nf(a)g(na)∑b∣mf(b)g(mb)=g(n)g(m)−ε(n)−ε(m)=g(n)g(m)

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

证毕

注

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

例子¶

ε=μ∗1⟺ε(n)=∑d∣nμ(d)d=1∗1⟺d(n)=∑d∣n1σ=id∗1⟺σ(n)=∑d∣ndφ=μ∗id⟺φ(n)=∑d∣nd⋅μ(nd)

狄利克雷生成函数

狄利克雷生成函数