Möbius 反演公式

请先阅读数论函数。

在数论中，Möbius 反演公式（莫比乌斯反演公式）是数论函数的一种关于数论函数的卷积的变换，一个函数经过 Möbius 变换后会得到一个新的数论函数，由新的数论函数再回到原来的函数即为 Möbius 逆变换。

Möbius 反演公式

设有数论函数$f(n)$，如下定义的函数

$$F(n) = \sum_{d:d|n} f(d) = f * \{ 1 \}.$$

称为$f(n)$的 Möbius 变换（由后一个等号可知该变换是卷积的特例），而$f(n)$称为$F(n)$的 Möbius 逆变换，它由下式确定

$$f(n) = \sum_{d:d|n} F\left( \dfrac{n}{d} \right) \mu(d) = F * \mu.$$

上式常称作Möbius 反演公式。$f(n)$是积性的当且仅当$F(n)$是积性的。

计算

设$F(n)$是$f(n)$的 Möbius 变换，且有标准分解式$n = p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_r^{\alpha_r}$，那么$F(1) = f(1),$且

$$F(n) = \sum_{\beta_1 = 0}^{\alpha_1}\sum_{\beta_2 = 0}^{\alpha_2}\cdots\sum_{\beta_r = 0}^{\alpha_r} f(p_1^{\beta_1} p_2^{\beta_2} p_3^{\beta_3} \cdots p_r^{\beta_r}).$$

特别地，当$f(n)$是积性函数时，

$$F(n) = \prod_{j=1}^r (1 + f(p_j) + f(p_j^2) + \cdots + f(p_j^{\alpha_r})).$$

由此可以推出

$$\begin{align} \sum_{d:d|n} \mu (d) f(d) & = \prod_{p:p|n} (1-f(p)), \\ \sum_{d:d|n} \mu^2(d) f(d) & = \prod_{p:p|n} (1+f(p)). \\ \end{align}$$

其中，$p$是素数。

一个函数$f(n)$的 Möbius 变换的 Möbius 变换是$f * \{ 1 \} * \{ 1 \} = f * \tau.$进一步，函数$f(n)$作$k$次 Möbius 变换就是$f * \tau_k, \tau_1 = \{ 1 \}, \tau_2 = \tau.$记号$\tau_k(n)$详见除数函数#推广。

例子

变换

1. Möbius 函数$\mu (n)$的 Möbius 变换：卷积的幺元$e(n) = \mu * \{ 1 \}.$
2. 恒为1的函数的 Möbius 变换：除数函数$\tau(n) = \{ 1 \} * \{ 1 \}.$
3. 恒等函数的 Möbius 变换：除数和函数$\sigma(n) = \{ n \} * \{ 1 \}.$
4. Liouville 函数的 Möbius 变换：完全平方数的特征函数$\lambda(n) * \{ 1 \} = \begin{cases} 1, & n = k^2, k \in \N^+, \\ 0, & \text{otherwise}.\end{cases}$
5. Euler 函数$\varphi(n)$的 Möbius 变换：恒等函数$\{ n \} = \varphi * \{ 1 \}.$
6. 作为上例的推广，$\varphi_k (n)$的 Möbius 变换：幂函数$\{ n^k \} = \varphi_k * \{ 1 \}.$记号详见Euler 函数#推广。
7. 作为(2)的推广，$\tau_k(n)$的 Möbius 变换：$\tau_{k+1} (n) = \tau_k * \{ 1 \}, k \geqslant 1.$记号详见除数函数#推广。
8. $|\mu(n)|$的 Möbius 变换：$2^{\omega(n)} = |\mu| * \{ 1 \}.$
9. $\mu^2(n) \varphi(n)$的 Möbius 变换：$\dfrac{n}{\varphi(n)} = (\mu^2 \cdot \varphi) * \{ 1 \}.$
10. $\dfrac{\mu(n)}{n}$的 Möbius 变换：$\dfrac{\varphi(n)}{n}.$
11. $\Omega (n)$的 Möbius 变换：$\dfrac{1}{2} \Omega \cdot \tau = \Omega * \{ 1 \}.$
12. Mangoldt 函数$\Lambda(n)$的 Möbius 变换：对数函数$\ln (n) = \Lambda * \{ 1 \}.$

逆变换

上述变换的例子反过来就是逆变换，如：（第2条）除数函数的 Möbius 逆变换是恒为1的函数。此外还有

1. Euler 函数$\varphi(n)$的 Möbius 逆变换：$\varphi * \mu = n \prod_{p:p||n}\left( 1-\dfrac{2}{p} \right) \prod_{p:p|n} \left( 1-\dfrac{1}{p} \right)^2.$
2. Mangoldt 函数$\Lambda(n)$的 Möbius 逆变换：$\Lambda * \mu = - \mu(n) \ln (n).$