从卷积谈莫比乌斯反演

狄利克雷卷积

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

多项式相乘就是一种卷积。次数为 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}
$$

啊，多美