炫酷广义莫比乌斯反演魔术

· · 算法·理论

作者是蒟蒻，如果有错误请批评指正，您有改进的建议也请提出/kel

0. 引入

这是数论 mobius 反演：

\begin{align*} f(n) &= \sum_{d|n} g(d) \\ g(n) &= \sum_{d|n} \mu \left(\frac{n}{d}\right) f(d) \end{align*}

这是快速 mobius 变换：

\begin{align*} f(S) &= \sum_{T \subseteq S} g(T) \\ g(S) &= \sum_{T \subseteq S} (-1)^{|S| - |T|} f(T) \end{align*}

有没有发现这俩东西很像？

设 n = \prod_{i = 1}^{k} p_{i} ^ {a_i} \ (a_i \ge 1)。当 \forall a_i = 1 时，数论 mobius 反演就是 mobius 变换，指数上 b_i = 0/1 可以对应为集合上的属于关系，这与 mobius 变换等价。

我们可以从更高的视角分析这个问题，下面将介绍炫酷广义 mobius 反演魔术！

1. 广义 mobius 变换

定义 1.1 偏序集

称 (X, \le) 为偏序集，其中 \le 表示偏序关系：

X^{\le} = \{ (x, y) \in X \times X \mid x \le y \}

定义 1.2 广义狄利克雷卷积

(f * g)(x, y) = \sum_{x \le z \le y} f(x, z)g(z, y) \epsilon(x, y) = [x = y] \bold{1}(x, y) = 1

注意：广义 Dirichlet 卷积不满足交换律！

定义 1.2 广义 mobius 函数

定义 mobius 函数为 \mu，使得

\mu * \bold{1} = \bold{1} * \mu = \epsilon \\

定理 1.3 mobius 函数的存在性与唯一性

可以证明，莫比乌斯函数存在且唯一。

证明

根据定义，对任意 (x, y) \in X^{\le}：

(\mu * \bold{1})(x, y) = \sum_{x \le z \le y} \mu(x, z) = \epsilon(x, y) = [x = y] \tag{1.3.1} \mu(x, y) = -\sum_{x \le z < y} \mu(x, z) \tag{1.3.2}

可见 \mu 对于所有偏序集一定存在，且唯一。

式 (1.3.1) 和式 (1.3.2) 常用于推导 \mu 的表达式，注意 (1.3.2) 的条件 x \le z < y 是左闭右开区间。

定理 1.4 广义 mobius 反演

设 X 有最小元为 u，则对任意映射 f, g : X \rightarrow R，如果对任意 y \in X 都有

f(y) = \sum_{u \le x \le y} g(x)

那么对任意 y \in X 都有

g(y) = \sum_{u \le x \le y} f(x) \mu(x, y)

证明：

对于任意 G(x, y) 满足

\begin{align*} G(x, y) &= (G * \mu * \bold{1})(x, y) = \sum_{x \le z \le w \le y} G(x, z) \mu(z, w) \bold{1}(w, y) \\ &= \sum_{x \le z \le w \le y} G(x, z) \mu(w, y) \\ \end{align*}

令 G(u, y) = g(y)，带入 g(y)，得到

\begin{align*} g(y) &= \sum_{u \le z \le w \le y} g(z) \mu(w, y) \\ &= \sum_{w \le y} \mu(w, y) \sum_{u \le z \le w} g(z) \\ &= \sum_{w \le y} f(w) \mu(w, y) \end{align*}

2. 例子

前缀和

取偏序集 (N_+, \le)，考察函数

f(n) = \sum_{1 \le i \le n} g(i)

显然 f 是 g 的前缀和

由 (1.3.1) 可得 \sum_{i \le k \le j} \mu(i, j) = \epsilon(i, j) = [i = j]。

归纳得：\mu(i, j) = 0 当 j - i \ge 2。

所以 g(n) = f(n) - f(n - 1)，哎这不是差分吗。

数论 mobius 反演

取偏序集 (N_+, |)，其中 | 是整除，考察函数

f(n) = \sum_{d | n} g(d)

由 (1.3.1)，函数 \mu 由方程 \sum_{x | z | y} \mu(x, z) = \epsilon(x, y) = [x = y] 给出。

观察：若 x|y，则有 \mu(x, y) = \mu \left(1, \frac{y}{x} \right)。

证明：

设局部偏序集：

\begin{align*} L &= \{ (x, z) \times X \mid z \in X, x | z | y, x \le z < y \} \\ R &= \{ (1, z) \times X \mid z \in X, z | \frac{y}{x}, 1 \le z < \frac{y}{x} \} \end{align*}

根据 (1.3.2) 有

\begin{align*} \mu(x, y) &= -\sum_{(x, z) \in L} \mu(x, z) \\ \mu(1, \frac{y}{x}) &= -\sum_{(1, z) \in R} \mu(1, z) \end{align*}

左侧 L 的元素 (x, z) 通过映射 (x, z) \mapsto (1, \frac{z}{x})，与右侧 R 的元素一一对应。

我们对 (x, y) 归纳证明，假设对于 (x', y') < (x, y) 命题成立，且 L, R 内的元素都满足小于 (x, y)，根据归纳假设与上面推出的映射对应可得

\sum_{(x, z) \in L} \mu(x, z) = \sum_{(1, z) \in R} \mu(1, z)

而初始情况 (1, 1) 成立，所以 \mu(x, y) = \mu(1, \frac{y}{x})。

因此 \mu(x, y) = \mu(1, \frac{y}{x})，我们只需要找到 \mu(1, n) 的通项公式即可，接下来的 \mu(n) 表示 \mu(1, n)。

由方程得到 \sum_{d | n}\mu(1, d) = \epsilon(1, n) = [n = 1]（莫反的核心式子，其实是源于广义莫比乌斯函数的定义）。

对于素数幂 p^k：

归纳得：\mu(p^k) = 0 当 k \ge 2。

接下来证明函数积性：

假设对所有小于 nm 的正整数积性成立。考虑 nm，其中 \gcd(n, m) = 1。

\begin{align*} \mu(nm) &= -\sum_{\substack{d|nm \\ d <nm}} \mu(d) = -\sum_{\substack{d1|n \\ d2|m \\ d1d2 < nm}} \mu(d1) \mu(d2) \\ &= -\left( \sum_{\substack{d1|n \\ d1 < n}} \mu(d1) \sum_{\substack{d2|m \\ d2 < m}} \mu(d2) \right) + \mu(n) \left( \sum_{\substack{d2|m \\ d2 < m}} \mu(d2) \right) + \mu(m) \left( \sum_{\substack{d1|n \\ d1 < n}} \mu(d1) \right) \\ &= -\mu(n)\mu(m) + 2\mu(n)\mu(m) = \mu(n)\mu(m) \end{align*}

综上，设 n = \prod_{i = 1}^{k} {p_i}^{a_i} \ (a_i > 1)，我们得到了 \mu(n) 的表达式（也就是一般语境下的“莫比乌斯函数”）：

\mu(n) = \begin{cases} 1 & n = 1 \\ 0 & \exist a_i \ge 2 \\ (−1)^k & \text{otherwise} \end{cases}

于是可得

g(n) = \sum_{d | n} f(d) \mu(d, n) = \sum_{d | n} f(d) \mu\left(\frac{n}{d}\right)

快速莫比乌斯变换（FMT）

对于有限集 U，取偏序集 (U, \subseteq)，考察函数

f(S) = \sum_{T \subseteq S} g(T)

由 (1.3.2) 有 \displaystyle \mu(I, J) = -\sum_{I \subseteq K \subset J} \mu(I, K)。

观察：若 |I| = |I'|, |J| = |J'| 且 I \subseteq J, I' \subseteq J'，则 \mu(I, J) = \mu(I', J')。

证明思路：

与上题类似，设

\begin{align*} L &= \{ (I, K) \mid I \subseteq K \subset J \} \\ R &= \{ (I', K) \mid I' \subseteq K \subset J' \} \end{align*}

由于 I,I' 和 J, J' 集合大小相同，任意一种双射 F : J \rightarrow J' 都可以使 L, R 通过 F 一一对应。（感性理解一下，将集合视作二进制数，标号一下就能对应上了）

然后归纳证明即可。

而 L,R 又可以通过映射 K \mapsto K \backslash I 同构于 [\varnothing, J \backslash I]，所以其实 \mu(I, J) = \mu(\varnothing, J \backslash I)，而 \mu(\varnothing, J \backslash I) 又只与 |J \backslash I| 有关，所以下文使用 \mu(|J| - |I|) 表示 \mu(I, J)。

重新整理

\mu(I, J) = \mu(|J| - |I|) = -\sum_{I \subseteq K \subset J} \mu(I, K) = -\sum_{k = |I|}^{|J| - 1} \sum_{\substack{|K| = k \\ I \subseteq K \subset J}} \mu(|K| - |I|)

而 I \subseteq K \subset J 等价于 (I \backslash I) \subseteq (K \backslash I) \subset (J \backslash I)，K 的个数是 \displaystyle\binom{|J \backslash I|}{|K \backslash I|} = \binom{|J| - |I|}{|K| - |I|}，可以得到

\mu(|J| - |I|) = -\sum_{k = |I|}^{|J| - 1} \sum_{\substack{|K| = k \\ I \subseteq K \subset J}} \mu(|K| - |I|) = -\sum_{k = |I|}^{|J| - 1} \binom{|J| - |I|}{k - |I|} \mu(|K| - |I|)

带入 I = \varnothing 方便我们推导

\mu(|J|) = -\sum_{k = 0}^{|J| - 1} \binom{|J|}{k} \mu(k)

可归纳证明 \mu(n) = (-1)^n：

\mu(n) = -\sum_{k = 0}^{n - 1} \binom{n}{k} \mu(k) = -\sum_{k = 0}^{n - 1} \binom{n}{k} (-1)^k = -(0 - (-1)^n) = (-1)^n

所以

g(S) = \sum_{T \subseteq S} f(T)\mu(T, S) = \sum_{T \subseteq S} (-1)^{|S| - |T|}f(T)

这是子集反演的推导，超集反演可以通过上面的式子变换一下符号得到。我们称集合 S 的补集为 U - S，超集反演的定义是

f(S) = \sum_{S \subseteq T} g(T) = \sum_{T \subseteq (U - S)} g(T)

我们定义 F(U - S) = f(S)，套用子集反演的结论，得到

\begin{align*} g(S) &= \sum_{T \subseteq S} (-1)^{|S| - |T|} F(T) = \sum_{(U - T) \subseteq S} (-1)^{|S| - |U - T|} f(U - T) \\ &= \sum_{S \subseteq T} (-1)^{|S| - |T|} f(T) \end{align*}

上式的 (-1)^{|S| - |T|} 大部分博客写做 (-1)^{|T| - |S|} 的，本质相同。

3. 总结

广义 mobius 反演可以做所有 DAG 前缀和反演状物的东西，提供了一种更一般的视角看这类反演问题，可以加深数学理解。同时定理 (1.1.3) 告知我们逆矩阵一定存在，但是如果 DAG 没有性质，求反演复杂度等价于求逆矩阵。

广义 mobius 反演也是一份强大的数学工具，出现在许多证明中。例如，它被大量用于迪尔沃斯定理的原始证明中，即有限偏序集合中，包含元素最多反链的元素数等于包含链数最少的链分解的链数。