从卷积到反演

狄利克雷卷积

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

多项式相乘就是一种卷积。次数为 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)=\sum_{i+j=n}A(i)B(j)
$$
之后，我们将用 $(F*G)(n)$表示离散函数 F 和 G 的狄利克雷卷积,$[F*G](n)$表示离散函数 F 和 G 的多项式卷积。

多项式卷积及其反演

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

这个应该是显然的，因为多项式卷积本身是一个对称的过程。

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

这也是显然的，多项式的相乘不分先后。

存在单位元 ($e$)

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

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

存在逆元 ($f^{-1}$)

对于离散函数 $f$，我们把它看成是一个多项式，或者说生成函数，那么它的逆元就记作：$\frac{1}{f}$，或者 $f^{-1}$。

---

以上的性质已经说明，离散函数 $(f, g, h)$与多项式卷积构成了一个乘法群。以上的性质已经可以帮助我们非常容易地理解什么是反演了。

一般反演

这里的反演的一般定义是：对于数列 $f,g$，如果他们可以写成如下的形式：
$$
\begin{align}
g_n &= \sum_{i=0}^{n}a_{n-i}f_i \\
f_n &= \sum_{i=0}^{n}b_{n-i}g_i
\end{align}
$$
那么称这两个序列是互反的。现在，我们可以把这两个序列理解为离散函数，那么：
$$
\begin{aligned}
g & =a*f \\
f & =b*g
\end{aligned}
$$

而反演的意义在于，当 $f$不是很好求，而 $g$非常好求的时候，我们可以用反演求出 $f$。那么首先，我们需要知道 $a,b$之间存在怎样的关系。

根据之前提到的，离散函数的四大性质，我们可以作出如下推断：
$$
\begin{aligned}
f & = b*g\\
f & = b*a*f\\
b*a & = e
\end{aligned}
$$

也就是说，$b,a$代表的离散函数在多项式卷积下互逆。哈，一般反演说到这里就结束了。

二项式反演与矩阵

二项式反演是一般反演的加强版：
$$
\begin{align}
g_n &= \sum_{i=0}^{n}a_{ni}f_i \\
f_n &= \sum_{i=0}^{n}b_{ni}g_i
\end{align}
$$
这里的 $a$对于不同的 $n$是完全不同的数列了，$b$也同样。那么这时，我们需要将 $a,b$看成一些二维的东西，比如矩阵。矩阵的乘法实际上可以看成是高维的卷积。
$$
\begin{align}
\begin{bmatrix}
g_0\\
g_1\\
g_2\\
\end{bmatrix} &=
\begin{bmatrix}
a_{00} & 0 & 0\\
a_{10} & a_{11} & 0\\
a_{20} & a_{21} & a_{22}\\
\end{bmatrix} \times
\begin{bmatrix}
f_0\\
f_1\\
f_2\\
\end{bmatrix}\\
\begin{bmatrix}
f_0\\
f_1\\
f_2\\
\end{bmatrix} &=
\begin{bmatrix}
b_{00} & 0 & 0\\
b_{10} & b_{11} & 0\\
b_{20} & b_{21} & b_{22}\\
\end{bmatrix} \times
\begin{bmatrix}
g_0\\
g_1\\
g_2\\
\end{bmatrix}\\
\end{align}
$$
现在，像上次一样，我们要知道当 $f,g$互反时，$a,b$应满足怎样的关系。下面用列向量表示 $f,g$, 用方阵表示 $a,b$：
$$
\begin{align}
\vec{F} &= A\times \vec{G}\\
\vec{G} &= B\times \vec{F}\\
\Rightarrow \vec{F} = A\times \vec{G} &= A\times B\times\vec{F} \\
A\times B &= E
\end{align}
$$
而 $A\times B = E$展开后的表示就是：
$$
\sum_{j=m}^{n}b_{ni}a_{im} = \begin{cases}
0 & (n \neq m)\\
1 & (n = m)
\end{cases}
$$

而满足这样的典型的 $a,b$就包括：

$$
\begin{align}
g_n & = \sum_{i=0}^{n}C_n^if_i \\
f_n & = \sum_{i=0}^{n}(-1)^{n-i}C_n^ig_i
\end{align}
$$

以及：
$$
\begin{align}
g_n & = \sum_{i=0}^{n}(-1)^iC_n^if_i \\
f_n & = \sum_{i=0}^{n}(-1)^iC_n^ig_i
\end{align}
$$

上面两个式子的证明并不复杂：
式 1：
$$
\begin{align}
A\times B & = \sum_{i=m}^{n}b_{ni}a_{im}\\
& = \sum_{i=m}^{n}(-1)^{i-m}C_n^iC_i^m\\
& = \sum_{i=m}^{n}(-1)^{i-m}C_n^mC_{n-m}^{n-i}\\
& = (-1)^{i-m}C_n^m\sum_{i=m}^{n}C_{n-m}^{n-i}\\
& = (-1)^{n-i-m}C_n^m\sum_{i=0}^{n-m}C_{n-m}^{i}\\
& = (-1)^{n-m}C_n^m\sum_{i=0}^{n-m}(-1)^iC_{n-m}^{i}\\
& = (-1)^{n-m}C_n^m(1-1)^{n-m}
\end{align}
$$
因此，$A\times B = E$。式 2 的证明同理。

狄利克雷卷积及其反演

交换律 ($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$)

同多项式卷积的单位元，我们可以写出狄利克雷卷积的单位元：
$$
e(n) = \begin{cases}
1 & (n=1) \\
0 & (n\neq 1)
\end{cases}
$$

存在逆元 ($f^{-1}$)

对于一个函数 $f!=0$，我们总能找到一个函数 $g$，使得 $f*g=e$，则 $g$一定是 $f$的逆元。并且这个 $g$一定是唯一的。

---

以上的这些结论，已经可以说明这些离散函数 $(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}
$$