莫比乌斯反演与狄利克雷卷积

终于算是搞明白这个东西了

一个记号:

艾弗森括号: $
[P]=\begin{cases}\
1 &, P\ is\ true \\
0 &, P\ is\ false
\end{cases}
$
其中$P$为一个命题, 同时艾弗森括号与其他值相乘时不受其定义域影响, 例如$\frac{[x\neq 0]}{x}$当$x=0$时其值为零.

数论函数:

讲莫比乌斯反演首先得讲莫比乌斯函数, 讲莫比乌斯函数首先得说下啥是数论函数.

数论函数即是定义在正整数区间上的函数. 常见的数论函数有欧拉$\varphi$函数, 因数个数, 因数和, 以及接下来讨论的莫比乌斯$\mu$函数.

一类比较重要的数论函数叫做积性函数: 对于两个互质的正整数$p,q$, 若有$f(pq)=f(p)f(q)$, 则称数论函数$f$为积性函数. 上面提到的数论函数都是积性函数.

特殊地, 若去掉互质的约束, 即对于任意正整数$p,q$均有$f(pq)=f(p)f(q)$, 则称$f$为完全积性函数. 比如$f(x) = x^k$.

积性函数都可以使用欧拉筛进行线性的预处理.

莫比乌斯函数:

莫比乌斯$\mu$函数的定义如下:

$$\mu(x) = \begin{cases} 1 &, x=1 \\ (-1)^k &,x=\prod_{i=1}^k p_i \\ 0 &, others \end{cases}$$

其中$p_1 \neq p_2 \neq \cdots$, 且$p_i$均为质数.

一个重要性质如下:

$$\sum_{d|n} \mu(d) = [n=1]$$

(事实上这个性质比反演好用)

证明:

当$n=1$时, 等式显然成立.

当$n \neq 1$时, 令$n = \prod_{i=1}^k p_i^{c_i}$(质因数分解), 则有:

$$\begin{aligned} & \sum_{d|n}\mu(d) \\ = & \ \mu(1) + \mu(p_1)+\mu(p_2)+\cdots \\ & + \mu(p_1p_2) + \mu(p_1p_3) + \cdots \\ & + \cdots + \mu(p_1p_2 \cdots p_k) \\ = & \ \sum_{i=0}^k (-1)^i {k \choose i} \\ = & \ (1-1)^k = 0 \end{aligned}$$

从中可以看出$\mu$函数在容斥当中的作用.

莫比乌斯反演:

对于函数$f(n)$, 若有$F(n) = \sum_{d|n} f(x)$, 则有$f(n) = \sum_{d|n}\mu(d)F(n/d)$.

另一种更常用的形式如下:

对于函数$f(n)$, 若有$F(n) = \sum_{n|d} f(x)$, 则有$f(n) = \sum_{n|d}\mu(d/n)F(d)$.

证明:

对于第一种形式:

$$\require{extpfeil} \begin{aligned} \sum_{d|n}\mu(d)F(\frac{n}{d}) = & \sum_{d|n}\mu(d)\sum_{q|(n/d)}f(q) \\ \xlongequal{q|n, dq|n} & \sum_{q|n}f(q)\sum_{d|(n/q)}\mu(d) \\ = & \sum_{q|n}f(q)[\frac{n}{q}=1] \\ = & f(n) \end{aligned}$$

对于第二种形式:

$$\begin{aligned} \sum_{n|d}\mu(\frac{d}{n})F(d) = & \sum_{i=1} \mu(i)F(in) \\ = & \sum_{i=1}\mu(i)\sum_{j=1}f(ijn) \\ \xlongequal{T=ij} & \sum_{T=1}f(Tn)\sum_{i|T}\mu(i) \\ = & \sum_{T=1}f(Tn)[T=1] \\ = & f(n) \end{aligned}$$

狄利克雷卷积:

对于两个数论函数$f(x),g(x)$, 定义运算:

$$(f*g)(x) = \sum_{d|x}f(d)g(\frac{x}{d})$$

该运算称为狄利克雷卷积.

显然狄利克雷卷积满足交换律, 结合律和分配律. (其实是懒得写证明了)

狄利克雷卷积有条重要的性质: 两个积性函数卷积后依然是积性函数, 所以通过狄利克雷卷积得到的函数也可以使用欧拉筛线性预处理.

狄利克雷卷积有单位元$\epsilon(x) = [x=1]$.

有了狄利克雷卷积, 之前提到的$\mu$函数的性质就可以表示为:

$$\mu * I = \epsilon$$

其中$I(x)=1$. 也即$\mu$是$I$的逆元.

此时莫比乌斯反演的第一种形式也变得十分显然:

$$\begin{aligned} & F = f*I \\ \therefore \ & F*\mu = f*I*\mu \\ & = f * \epsilon = f \end{aligned}$$

同时欧拉$\varphi$函数有一个与狄利克雷卷积有关的性质:

$$\sum_{d|n} \varphi(d) = n$$

证明:

$$\begin{aligned} \sum_{d|n} \varphi(d) = & \sum_{d|n}\varphi(\frac{n}{d}) \\ = & \sum_{d|n}\sum_{i=1}^{n/d}[(i,\frac{n}{d}=1)] \\ = & \sum_{d|n}\sum_{i=1}^{n/d}[(id,n)=d] \\ \xlongequal{引入无关项} & \sum_{d|n}\sum_{i=1}^{n}[(i,n)=d] \\ \xlongequal{枚举gcd} & n \end{aligned}$$

事实上有个更通用的做法: 考察积性函数在质数幂次上的值:

$$\begin{aligned} \sum_{d|p^k} \varphi(d) = & 1 + \sum_{i=1}^{k} p^i-p^{i-1} \\ = & p^k \\ \mathrm{assume}\ n = & \prod_{p} p^k \\ \Rightarrow\sum_{d|n} \varphi(d) = & \prod_{p} \sum_{d|p^k} \varphi(d) \\ = & \prod_{p} p^k = n \end{aligned}$$

同时:

$$\begin{aligned} & \varphi * I = id \\ \Longrightarrow & \varphi = id * \mu \\ \iff & \varphi(x) = \sum_{d|x} \mu(d) \frac{x}{d} \\ \Longrightarrow & \frac{\varphi(x)}{x} = \sum_{d|x} \frac{\mu(d)}{d} \end{aligned}$$

这个式子简洁地将$\varphi$函数与$\mu$函数结合在了一起. (虽然好像暂时不知道有啥用)