从卷积谈莫比乌斯反演

狄利克雷卷积

对于卷积,我们应该并不陌生。最简单的卷积从我们常见的竖式乘法开始,再到生成函数(多项式)的相乘,无处不在。

多项式相乘就是一种卷积。次数为a和b的项的系数相乘得到系数为$(a+b)$项的系数。
$$
C[n]=\sum_{i=0}^{n}A[i]B[n-i]
$$
同样,我们今天所说的狄利克雷卷积也是一种类似的卷积。
$$
C[n]=\sum_{ij=n}A[i]B[j]
$$
如果把A和B都理解成一种函数,A[i]是函数在x=i时的取值,那么我们就可以把式子这么写:
$$
(F*G)(n)=\sum_{ij=n}A(i)B(j)
$$
之后,我们将用$(F*G)(n)$表示离散函数F和G的狄利克雷卷积。

卷积的性质

交换律($f*g=g*f$)

和多项式乘法一样,狄利克雷卷积也满足交换律。证明嘛。。。显然的。

结合律 ($(f*g)*h=f*(g*h)$)

对于$(f*g)*h$在n处的取值,我们进行如下证明:
$$
\begin{aligned}
((f*g)*h)(n) & =\sum_{ij=n}(f*g)(i)h(j) \\
& =\sum_{ij=n}(\sum_{kl=i}f(k)g(l))h(j) \\
& =\sum_{ijk=n}f(i)g(j)h(k)
\end{aligned}
$$
同理,对于$f*(g*h)$在n处的取值,我们也把它变成上面的形式:
$$
\begin{aligned}
(f*(g*h))(n) & =\sum_{ij=n}f(i)(g*h)(j) \\
& =\sum_{ijk=n}f(i)g(j)h(k)
\end{aligned}
$$
所以结合律在这个卷积中存在。

存在单位元e

单位元的意思,就好比小学数学中的1,矩阵中的单位矩阵。它乘以任何东西,那个东西都不会变。

于是乎,我们要求一个离散函数$e$,使得:
$$
e*f=f
$$
显然,我们需要的单位元是:
$$
e(n)=\begin{cases}
1 & n=1\\
0 & n\neq 1
\end{cases}
$$
因为,这样的$e$才能保证$e*f$的每一项就是$f$的每一项。


以上的这些结论,已经可以说明这些离散函数(f,g,h)在卷积意义下构成了一个交换群。但是这并不重要。重要的是我们为什么可以用卷积的方式更简单地分析莫比乌斯反演。

莫比乌斯函数

来由

我们通常见到的莫比乌斯反演总是这样的:
$$
f(n)=\sum_{d|n}g(d) \Rightarrow g(d)=\sum_{d|n}f(d)\mu(\frac{n}{d})
$$
我们把它先用卷积的形式写一下:
$$
f=u*g \Rightarrow g=f*\mu
$$
其中$u$是一个恒为1的函数。

哈哈,这样,我们只需要说明$u$和$\mu$互为反函数就行啦。

因为,如果u和g互为反函数(即$u*g=e$),我们可以证明:
$$
\begin{aligned}
f & = g*u \\
f*\mu & = g*u*\mu \\
f*\mu & = g*e \\
f*\mu & = g
\end{aligned}
$$

$\mu$的定义

我们直接定义$u*\mu=e$,即$\sum_{d|n}\mu(d)=\cases{1 & n=1\\0 & n>1}$

然后我们随手构造一个$\mu(d)$的取值表,使他满足这个东西就好啦。

$\mu$的构造

前人已经发现了$\mu$的构造方法。

$\mu(1)=1$

$\mu(n)=(-1)^k$,如果n可以写成k个不同质数的积

$\mu(n)=0$,其他n

按照这种定义,显然n=1时$\sum_{d|n}\mu(d)=1$

对于其他n,我们可以尝试证明一下。

首先,我们把n唯一分解一下,变成若干个素数的积,然后选择n的因数d,把他们的$\mu(d)$加起来。注意下面的证明中只把非0的$\mu(d)$加了起来。
$$
\begin{aligned}
\sum_{d|n}\mu(d) & =\mu(1)+\mu(p_1)+\mu(p_2)+\dots+\mu(p_1p_2)+\dots+\mu(p_1p_2\dots p_k) \\
& =\sum_{i=0}^k C_k^i(-1)^i \\
& = 0
\end{aligned}
$$

莫比乌斯反演

现在我们对这篇文章精彩回放一下:

1.我们用卷积表示形如$f(n)=\sum_{d|n}g(d)$的运算。

2.我们利用卷积的性质发现,我们需要一个函数$\mu$,才能完成炫酷的反演。

3.我们找到了$\mu$的一些性质,并尝试利用这些性质构造出$\mu$

4.我们发现前人已经构造出了$\mu$,所以我们只需要验证一下。

于是这篇文章的精华就是:
$$
\begin{aligned}
f & = g*u \\
f*\mu & = g*u*\mu \\
f*\mu & = g*e \\
f*\mu & = g
\end{aligned}
$$

啊,多美

分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *