狄利克雷生成函数

记 $\mathcal{P}$ 表示素数集合。

狄利克雷生成函数

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

$$\tilde{F}(x)=\sum _{i\ge 1}\frac{f_i}{i^x}$$

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

$$\tilde{F}(x)=\prod _{p\in \mathcal{P}}(1+\frac{f_p}{p^x}+\frac{f_{p^2}}{p^{2x}}+\frac{f_{p^3}}{p^{3x}}+\cdots )$$

对于两个序列 $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,\dots ]$ 的 DGF 是 $\sum _{i\ge 1}\frac{1}{i^x}=\zeta (x)$。$\zeta$ 是黎曼函数。

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

$$\zeta (x)=\prod _{p\in \mathcal{P}}(1+\frac{1}{p^x}+\frac{1}{p^{2x}}+\dots )=\prod _{p\in \mathcal{P}}\frac{1}{1-p^{-x}}$$

莫比乌斯函数

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

$$\tilde{M}(x)=\prod _{p\in \mathcal{P}}(1-\frac{1}{p^x})=\prod _{p\in \mathcal{P}}(1-p^{-x})$$

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

欧拉函数

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

$$\tilde{\mathrm{\Phi }}(x)=\prod _{p\in \mathcal{P}}(1+\frac{p-1}{p^x}+\frac{p(p-1)}{p^{2x}}+\frac{p^2(p-1)}{p^{3x}}+\dots )=\prod _{p\in \mathcal{P}}\frac{1-p^{-x}}{1-p^{1-x}}$$

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

幂函数

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

$$\widetilde{I_k}(x)=\prod _{p\in \mathcal{P}}(1+\frac{p^k}{p^x}+\frac{p^{2k}}{p^{2x}}+\dots )=\prod _{p\in \mathcal{P}}\frac{1}{1-p^{k-x}}=\zeta (x-k)$$

根据这些定义，容易推导出 $\phi \ast 1=I$，$\ast$ 表示狄利克雷卷积。因为 $\tilde{\mathrm{\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({\displaystyle \frac{x}{d}}\right)=\sum _{ab=x}f(a)g(b)$$

上式可以简记为：

$$h=f\ast 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\ast g=g\ast f$。

结合律：$(f\ast g)\ast h=f\ast (g\ast h)$。

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

等式的性质： $f=g$ 的充要条件是 $f\ast h=g\ast h$，其中数论函数 $h(x)$ 要满足 $h(1)\ne 0$。

证明： 充分性是显然的。

证明必要性，我们先假设存在 $x$，使得 $f(x)\ne g(y)$。那么我们找到最小的 $y\in \mathbb{N}$，满足 $f(y)\ne g(y)$，并设 $r=f\ast h-g\ast h=(f-g)\ast h$。

则有：

$$\begin{array}{rl}r(y)& =\sum _{d\mid y}(f(d)-g(d))h\left({\displaystyle \frac{y}{d}}\right)\\ & =(f(y)-g(y))h(1)\\ & \ne 0\end{array}$$

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

证毕

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

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

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

$$g(x)={\displaystyle \frac{\epsilon (x)-\sum _{d\mid x,d\ne 1}f(d)g\left({\displaystyle \frac{x}{d}}\right)}{f(1)}}$$

重要结论

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

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

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

$$h(a)=\sum _{d_1\mid a}f(d_1)g\left({\displaystyle \frac{a}{d_1}}\right),h(b)=\sum _{d_2\mid b}f(d_2)g\left({\displaystyle \frac{b}{d_2}}\right),$$

所以：

$$\begin{array}{rl}h(a)h(b)& =\sum _{d_1\mid a}f(d_1)g\left({\displaystyle \frac{a}{d_1}}\right)\sum _{d_2\mid b}f(d_2)g\left({\displaystyle \frac{b}{d_2}}\right)\\ & =\sum _{d\mid ab}f(d)g\left({\displaystyle \frac{ab}{d}}\right)\\ & =h(ab)\end{array}$$

所以结论成立。

证毕

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

证明：我们设 $f\ast g=\epsilon$，并且不妨设 $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({\displaystyle \frac{nm}{d}}\right)=-\sum _{a\mid n,b\mid m,ab\ne 1}f(ab)g\left({\displaystyle \frac{nm}{ab}}\right)$$

  又因为 ${\displaystyle \frac{nm}{ab}}<nm$，所以有：

  $$\begin{array}{rl}g(nm)& =-\sum _{a\mid n,b\mid m,ab\ne 1}f(ab)g\left({\displaystyle \frac{nm}{ab}}\right)\\ \\ & =-\sum _{a\mid n,b\mid m,ab\ne 1}f(a)f(b)g\left({\displaystyle \frac{n}{a}}\right)g\left({\displaystyle \frac{m}{b}}\right)\\ \\ & =f(1)f(1)g(n)g(m)-\sum _{a\mid n,b\mid m}f(a)f(b)g\left({\displaystyle \frac{n}{a}}\right)g\left({\displaystyle \frac{m}{b}}\right)\\ \\ & =g(n)g(m)-\sum _{a\mid n}f(a)g\left({\displaystyle \frac{n}{a}}\right)\sum _{b\mid m}f(b)g\left({\displaystyle \frac{m}{b}}\right)\\ \\ & =g(n)g(m)-\epsilon (n)\epsilon (m)\\ \\ & =g(n)g(m)\end{array}$$

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

证毕

例子

$$\begin{array}{rl}\epsilon =\mu \ast 1& ⟺\epsilon (n)=\sum _{d\mid n}\mu (d)\\ d=1\ast 1& ⟺d(n)=\sum _{d\mid n}1\\ \sigma =\mathrm{id}\ast 1& ⟺\sigma (n)=\sum _{d\mid n}d\\ \phi =\mu \ast \mathrm{id}& ⟺\phi (n)=\sum _{d\mid n}d\cdot \mu (\frac{n}{d})\end{array}$$

相关应用

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

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

以 洛谷 P3768 简单的数学题 为例，我们要对 $f_i=i^2\phi (i)$ 构造一个满足上述条件的积性序列 $g$。由于 $f$ 是积性的，考虑其 DGF

$$\tilde{F}(x)=\prod _{p\in \mathcal{P}}(1+\sum _{k\ge 1}\frac{p^{3k-1}(p-1)}{p^{kx}})=\prod _{p\in \mathcal{P}}\frac{1-p^{2-x}}{1-p^{3-x}}=\frac{\zeta (x-3)}{\zeta (x-2)}$$

因此 $\tilde{F}(x)\zeta (x-2)=\zeta (x-3)$。而 $\zeta (x-2)$ 对应的积性函数为 $I_2$，所以令 $g=I_2$ 即可。这样有 $f\ast g=I_3$，两者都是可以快速计算前缀和的。

本页面最近更新：2024/7/12 14:31:57，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：danielqfmai, sshwy, billchenchina, CCXXXI, Enter-tainer, Great-designer, lychees, Menci, Nanarikom, ouuan, shuzhouliu, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用