Möbius 反演
| 莫比乌斯反演公式 | |
|---|---|
| 术语名称 | 莫比乌斯反演公式 |
| 英语名称 | Möbius inversion formula |
| 莫比乌斯变换 | |
|---|---|
| 术语名称 | 莫比乌斯变换 |
| 英语名称 | Möbius transform |
| 莫比乌斯逆变换 | |
|---|---|
| 术语名称 | 莫比乌斯逆变换 |
| 英语名称 | inverse Möbius transform |
莫比乌斯反演公式(Möbius inversion formula)指两个数论函数之间的关系，其中之一相当于另一个对全部正因数使用并求和。 可以用于难以求解的函数分解成对因数或倍数的另一个函数求和。
定义
对两个数论函数 [math]\displaystyle{ f }[/math] 和 [math]\displaystyle{ F }[/math] ，若
[math]\displaystyle{ F(n) = \sum_{d \mid n} f(d) }[/math]
其中 [math]\displaystyle{ \sum_{d \mid n} }[/math] 代表对全部正因数求和，此时有
[math]\displaystyle{ f(n) = \sum_{d \mid n} \mu(d) F\left(\frac{n}{d}\right) }[/math]
其中 [math]\displaystyle{ \mu(n) }[/math] 是 Möbius 函数。 并称函数 [math]\displaystyle{ F(n) }[/math] 是函数 [math]\displaystyle{ f(n) }[/math] 的Möbius 变换(Möbius transform)，函数 [math]\displaystyle{ f(n) }[/math] 是函数 [math]\displaystyle{ F(n) }[/math] 的Möbius 逆变换(inverse Möbius transform)，这一对公式被称为 Möbius 反演公式(Möbius inversion formula)。
Dirichlet 卷积形式
可以通过 Dirichlet 卷积描述这一过程，即：
[math]\displaystyle{ F = 1 * f \Leftrightarrow f = \mu * F }[/math]
倍数版本
对两个数论函数 [math]\displaystyle{ f }[/math] 和 [math]\displaystyle{ F }[/math] ，若
[math]\displaystyle{ F(n) = \sum_{n \mid m} f(n) }[/math]
其中 [math]\displaystyle{ \sum_{n \mid m} }[/math] 代表对全部正倍数求和，此时有
[math]\displaystyle{ f(n) = \sum_{n \mid m} \mu(m) F\left(\frac{m}{n}\right) }[/math]
其中 [math]\displaystyle{ \mu(n) }[/math] 是 Möbius 函数。
性质
[math]\displaystyle{ F(1)=f(1) }[/math] ，且若 [math]\displaystyle{ n = p_1^{k_1} p_2^{k_2} \dots p_m^{k_m} }[/math] 是标准质因数分解，则 [math]\displaystyle{ F(n) = \sum_{h_1 = 1}^{k_1} \sum_{h_2 = 1}^{k_2} \dots \sum_{h_m = 1}^{k_m} f(p_1^{h_1} p_2^{h_2} \dots p_m^{h_m}) }[/math] 。
乘性函数进行 Möbius 反演后得到的也是乘性函数，反过来也成立。因此 [math]\displaystyle{ F(n) = \prod_{j=1}^m (1 + f(p_j) + \dots + f(p_j^{k_j})) = \prod_{p^h\|n} (1 + f(p) + \dots + f(p^h)) }[/math] ，其中 [math]\displaystyle{ \prod_{p^h\|n} }[/math] 表示对所有恰整除 [math]\displaystyle{ n }[/math] 的 [math]\displaystyle{ p,h }[/math] 求和。
进一步地，如果是一个完全乘性函数，指数可以拿出来，有 [math]\displaystyle{ F(n) = \prod_{j=1}^m (1 + f(p_j) + \dots + (f(p_j))^{k_j}) = \prod_{p^h\|n} (1 + f(p) + \dots + (f(p))^h) }[/math] ，变成一系列等比级数的乘积。
特别地，对于乘性函数 [math]\displaystyle{ f(n) }[/math] 和 [math]\displaystyle{ F(n) }[/math] ，有 [math]\displaystyle{ \sum_{d\mid n} \mu(d)f(d) = \prod_{p\mid n}(1 - f(p)), \sum_{d\mid n} (\mu(d))^2f(d) = \prod_{p\mid n}(1 - f(p) }[/math] 以及 [math]\displaystyle{ f(p^k) = F(p^k) - F(p^{k-1}) }[/math] ，并且可以利用乘性计算任意合数对应的函数值。
Möbius 反演中的加法实际上只要求是交换群上的运算，若把式中的累和与乘法改为累积与乘方，依旧成立，即 [math]\displaystyle{ F(n) = \prod_{d\mid n} f(d) \Rightarrow f(n) = \prod_{d\mid n} F\left(\frac{n}{d}\right)^{\mu(d)} }[/math]。