物理

生成函数（3）：Dirichlet 生成函数（欧拉乘积公式，Mobius 变换）

（温馨提示，本文难度比前两篇大一点）

本文我们学习第三种生成函数，Dirichlet生成函数。它与我们所学习的普通生成函数以及指数型生成函数有着很大的不同。前两种生成函数让我们把组合问题转化成一些分析学的问题，因此它们具有非常浓厚的分析的味道，而Dirichlet生成函数则与数论紧密相关。研究对象也有很大的差别，前两种生成函数主要研究一些数列的递推以及组合计数问题，而Dirichlet生成函数主要用以研究数论函数。本文主要分为两个部分，第一部分主要围绕欧拉乘积公式展开，第二部分主要围绕Dirichlet卷积展开。

一个数列$\{ a_n\}$的Dirichlet生成函数是$\sum^{\infty}_{n=1} \frac{a_n}{n^s}$，其中s可以任意选取（下文不加声明时，生成函数均指Dirichlet生成函数）。注意，Dirichlet 生成函数求和的下限是1而不是0。从这个形式上我们也能看出我们前面处理生成函数的方法失效了，我们需要新的手段。由于数列和数论函数是一致的概念，因此生成函数可以自然地放在数论函数上，后文我们用$D_f(s)$表示数论函数$f(n)$的Dirichlet生成函数。

首先我们回忆一个简单公式，我们考虑$\zeta (s)=\sum^{\infty}_{n=1} \frac{1}{n^s}$，则我们有$\zeta (s)=\prod_{p~is~prime} (1-\frac{1}{p^s})^{-1}$。它的证明思路是这样的，我们考虑一个素数p，那么我们展开$(1-\frac{1}{p^s})\zeta (s)$，得到的结果刚好是$\zeta (s)$中把分母是p的倍数的项消去了，不断地操作下去，最终只会剩下1没有消去，于是公式得证。还有一种更具启发性的证明方法我们把右式再展开，得到$\prod_{p~is~prime} \sum^{\infty}_{k=0} \frac{1}{p^{ks}}$，利用算术基本定理，我们知道把这个式子打开后，每一个$\frac{1}{n^s}$恰好只出现一次，于是公式得证（这里略去了无穷乘积绝对收敛的证明）。

这种证明方法显然还可以证明更一般的公式，因为我们仅仅用到了素因数分解的唯一性，我们有如下定理。

设$f(n)$是一个积性函数，则有$D_f(s)=\prod_{p~is~prime} (\sum^{\infty}_{k=0} \frac{f(p^k)}{p^{ks}})$。

这个定理的证明与上面完全一样，这里留给读者当作习题。特别地，当$f(n)$为完全积性函数时，这个式子可以进一步化简。

设$f(n)$是一个完全积性函数，则有$D_f(s)=\prod_{p~is~prime} (1-\frac{f(p)}{p^s})^{-1}$。

欧拉乘积公式体现了解析数论中的整体－局部原理，利用它，我们可以通过研究数论函数在素数上的行为，来了解数论函数的整体行为。我们看一个最经典的应用，取$f(n)=\chi (n)$为Dirichlet特征，那么它的生成函数即著名的Dirichlet L 函数$L(s,\chi)$。$\chi$显然是一个完全积性函数，通过欧拉乘积公式，我们可以知道，当$Re(s)>1$时，$L$没有零点。再结合一些复分析与解析数论的技巧，我们能证明当$Re(s)=1$时，$L$也没有零点，而这正是Dirichlet大定理证明中的核心难点，但这超出了本文的内容。

现在来看第二个内容，我们来研究Dirichlet 卷积。我们从Mobius反演开始。

如果两个数论函数满足$F(n)=\sum_{d \mid n}f(d)$，那么我们称$F(n)$为$f(n)$的Mobius变换，且称$f(n)$为$F(n)$的Mobius逆变换。我们有两个基本的问题：

（1）已知一个数论函数，它的Mobius变换怎么求？有怎样的性质？

（2）反过来，如果已知一个数论函数，它的Mobius 逆变换是否存在？如果存在，是否唯一？

（1）是比较容易的。利用Mobius 变换的定义，它的前半段只需要我们找出n的所有因子即可。我们有如下定理。

设$n=\prod^{s}_{i=1} p_i^{\alpha_i}$，那么有$F(n)=\sum^{\alpha_1}_{i_1=1} \cdot \cdot \cdot \sum^{\alpha_s}_{i_s=1} f(\prod^{s}_{j=1} p_j^{i_j})$。

它的证明是显然的，无非就是让$f(k)$中的k遍历n的所有因子而已。这个式子很丑陋也很恐怖，同时它也很有用，它给出了(1)后半段的回答。

若$f$为积性函数，则它的Mobius变换$F$也是积性函数。

注意到，利用定理2并结合积性函数的性质，我们有$F(n)=\sum^{\alpha_1}_{i_1=1} \cdot \cdot \cdot \sum^{\alpha_s}_{i_s=1} \prod^{s}_{j=1} f(p_j^{i_j})$，而右式是可以分解的，我们有$F(n)=\prod^{s}_{k=1} (\sum^{\alpha_k}_{i_k=1} f(p_k^{i_k}))=\prod^{s}_{k=1} F(p^{\alpha_k})$，这满足积性函数的定义，因此$F$为积性函数。

这个定理有个很好用的特例，如下。

设$f$为积性函数，$\mu$为Mobius函数，则$\sum_{d\mid n} \mu(d) f(d)=\prod_{p \mid n} (1-f(p))$，$\sum_{d\mid n} \mu^2(d) f(d)=\prod_{p \mid n} (1+f(p))$。

从这个推论中我们也能大概看出Mobius 函数的一些作用，把“大于1”的元素去掉，留下“不超过1”的元素。在推论中它只留下了$f(p)$和1这两个幂次不超过1的。更进一步，如果我们令$f(n)=1$，那么我们就可以得到$I(x)=\sum_{d \mid n} \mu(d)=[\frac{1}{n}]$。下面我们利用这个性质来回答（2）中的问题。

$F$为$f$的Mobius变换，当且仅当$f(n)=\sum_{ab=n} F(a)\mu(b)$。

有的书上给出的是$f(n)=\sum_{d\mid n} F(d) \mu(\frac{n}{d})$，两者是一样的，但是我们选择了一种更对称的写法，后面会看到这样的好处。

我们用刚刚发现的Mobius函数“保留1”的性质来证明。我们有$f(n)=\sum_{ab=n} f(a)I(b)=\sum_{ab=n} \mu(b) \sum_{b\mid k,k\mid n} f(\frac{n}{k})$，这里用到的是交换求和的手法，如果令$k=bl$，那么我们有$f(n)=\sum_{ab=n} \mu(b) \sum_{l\mid a} f(\frac{a}{l})=\sum_{ab=n} \mu(b)F(a)$。这一公式就是著名的Mobius反演公式，反过来就是正常的计算。这告诉我们任意数论函数的Mobius逆变换均存在且唯一。