物理

生成函数（4）：Dirichlet 生成函数（Dirichlet 卷积）

仔细观察之前给出的Mobius 反演公式。它也也可以看作某种形式的卷积，前面我们说卷积的特征是角标和与求和变量无关，而这里是乘积而已。因此我们可以从中定义一种新的卷积。

我们定义两个数论函数的Dirichlet卷积为$(f \ast g)(n)=\sum_{ab=n}f(a)g(b)$。记$1(n)=1$是常函数，那么我们可以把Mobius反演重新叙述为$f \ast 1=F$当且仅当$f=F \ast \mu$。Dirichlet 卷积作为一个二元运算，我们自然需要研究它的运算律以及运算性质。

（1）Dirichlet卷积满足交换律：$f \ast g=\sum_{ab=n} f(a)g(b)=\sum_{ba=n} g(b)f(a)=g\ast f$

（2）Dirichlet卷积满足结,合律：$(f \ast g) \ast h = \sum_{(ab)c=n} (f(a)g(b))h(c)=\sum_{a(bc)=n} f(a)(g(b)h(c))=f\ast (g\ast h)$

（3）Dirichlet卷积存在单位元：$I \ast f=f\ast I=f$，其中$I(n)=[\frac{1}{n}]$，它被称为单位函数。

看到这里有的同学可能会觉得非常熟悉，这不就是Abel群吗？我们回顾一下什么是群，群是一个集合G与G上的一个二元运算$\circ :G\times G \to G$构成的二元组$(G,\circ)$，满足：

（1）结合律：$(a \circ b)\circ c=a\circ (b\circ c)$

（2）存在单位元$e$：$a\circ e=e\circ a=a$

（3）存在逆元：任意元素$a$，存在$b$使得$a\circ b=b\circ a=e$

如果它还满足交换律，则称为一个Abel 群，简记为群$G$。例如整数关于加法构成群，实数域上的n阶可逆矩阵构成群（称为一般线性群$GL_n(\mathbb{R})$）,n个元素的所有置换也构成群（称为n阶对称群）。只满足第一条的称为半群，只满足前两条的称为幺半群。

但是Dirichlet 积还缺一个性质，即我们不知道这些数论函数是否存在逆元，我们称为Dirichlet逆函数，简称逆函数。以下定理解决了这个问题。

定理1：

若数论函数$f$满足$f(1)\neq 0$，则$f$唯一存在逆函数。

我们用第二数学归纳法给出逆函数$f^{-1}$的一个具体算法。当$n=1$时，必须有$f^{-1}(1)=\frac{1}{f(1)}$。假设所有的$k\le n-1(n\ge 2)$上的取值已经被唯一确定，由$\sum_{ab=n} f(a)f^{-1}(b)=0$（注意这里不是1）知，$f^{-1}(n)=\frac{-1}{f(1)}\sum_{ab=n,a,b\neq n} f(a)f^{-1}(b)$，由归纳假设，这个函数被唯一确定，命题得证。

推论：

若积性函数不恒等于0，则存在逆函数。

由此，我们会发现在1处取值非零的数论函数在Dirichlet卷积的意义下构成了一个Abel群$D$。但结合推论，我们知道，全体不恒等于0的积性函数都在这个群$D$中。很自然地，我们想知道，非零积性函数（以后均考虑非零情形）是否也构成一个Abel群呢？换而言之，Dirichlet卷积是否能保持积性？逆函数是否能保持积性？如下定理可以回答这几个问题。

（1）若$f$和$g$为积性函数，则$f\ast g$也为积性函数。

（2）若$f$和$f\ast g$为积性函数，则$g$为积性函数。

我们设$h=f\ast g$，当$(m,n)=1$时，我们有$h(mn)=\sum_{t\mid mn} f(t)g(\frac{mn}{t})$。我们令$t=t_1t_2$，满足$t_1\mid m$且$t_2\mid n$，显然，当$t_1$和$t_2$分别遍历m和n的所有因子时，t会遍历mn的所有因子，这一结论是熟知的。因此我们就有$h(mn)=\sum_{t_1\mid m,t_2\mid n} f(t_1)f(t_2)g(\frac{m}{t_1})g(\frac{n}{t_2})=\sum_{t_1\mid m} f({t_1})g(\frac{m}{t_1}) \sum_{t_2\mid n} f(t_2)g(\frac{n}{t_2})=h(m)h(n)$，所以$h$是积性函数。

反过来，如果$h$和$f$都是积性函数，若$g$不是积性函数，考虑满足$(m,n)=1$，且$g(mn)\neq g(m)g(n)$，使得mn最小（最小数原理），显然有$mn\neq 1$。用和刚才一样的方法分离mn的因子，我们考虑$h(mn)=\sum_{t_1\mid m,t_2\mid n，mn\gt t_1t_2} f(t_1)f(t_2)g(\frac{m}{t_1})g(\frac{n}{t_2})+g(mn)=\sum_{t_1\mid m} f(t_1)g(\frac{m}{t_1} ) \sum_{t_2\mid n} f(t_2)g(\frac{n}{t_2})-g(m)g(n)+g(mn)$。这样，我们发现原来的式子被拆分出了简单的结果，化简得$h(mn)=h(m)h(n)-g(m)g(n)+g(mn)$，与假设矛盾。

由此，我们知道积性函数恰好构成$D$的子群。更进一步的想法是，对于完全积性函数而言，我们是否有同样的结论？答案是否定的，积性函数已经是最好的结果了。我们声称，完全积性函数的逆函数不一定是完全积性函数。我们这里直接给出完全积性函数逆函数的公式：$f^{-1}(n)=\mu(n)f(n)$，我们只需要做一次Dirichlet卷积即可证明。我们注意到$\mu(n)$是积性函数但不是完全积性函数，因此$f^{-1}$不一定是完全积性函数。

现在我们回过头来再看Mobius反演。我们用$1$表示映射到1的常数函数，$Id(n)=n$为恒等映射，$I(n)=[\frac{1}{n}]$为单位函数，那么我们有$\mu \ast 1=I$，而Mobius反演就是说如果$f\ast 1=g$，那么$g=\mu \ast f$，这和我们的结论完全一致。利用Dirichlet 卷积，我们还能得到关于Mobius 变换的许多性质，比如积性函数的Mobius变换是积性函数，积性函数的Mobius 逆变换也是积性函数。我们现在来试着处理一个简单的问题。

设$\tau(n)$为n的正因子的个数，求证：$f$的Mobius 变换的Mobius 变换是$\sum_{d\mid n} f(d)\tau(\frac{n}{d})$。

这是潘承洞和潘承彪的《初等数论》上的一道习题。其实我们就是都要证明$(f\ast 1) \ast 1=f\ast \tau$，也就是要证明$1\ast 1=\tau$，也就是$\sum_{d\mid n} 1=\tau(n)$，这就证完了。

通过这些运算我们还能得到更多的等式，比如刚学数论时我们就学过$\varphi \ast 1=Id$，其中$\varphi(n)$是欧拉函数，那么我们可以得到$\varphi=\mu \ast Id$。我们设$\sigma(n)$为除数和函数，那么我们有$\sigma (n)=\sum_{d\mid n} d$，所以$\sigma =Id \ast 1=\varphi \ast 1 \ast 1=\varphi \ast \tau$。这些等式如果不通过Dirichlet 卷积来计算，而希望通过组合意义或者直接计算得到，还是有一定难度的。

再看一个很经典的题目。

求证：$\sum_{d\mid n} \tau^{3}(d)=(\sum_{d\mid n} \tau(d))^2$

我们注意到两边都是积性函数，因此只需考虑它们在素数幂上的行为即可。$\sum^{k}_{i=0} \tau^3(p^i) =\sum^{k}_{i=0} (i+1)^3$，另外一边同理，然后打开纯计算即可。如果不能发现两边都是积性函数，证明可能会复杂一些。