莫比乌斯反演

Introduction

最精彩的证明是自动证明。今天在知乎上看到的一位大佬对莫比乌斯反演的证明让我体会到了数论的神奇。坚定了我投靠数学的决心。

Mobius Inversion Formula

若存在
$$ g(n)=\sum_{d|n} f(d) \hspace{1em} (n \geq 1) $$

则有
$$ f(n)=\sum_{d|n} \mu(d) g(n/d) \hspace{1em} (n \geq 1) $$

反之亦然。

Basic Concept

1. Convolution / 卷积

对两个数论函数\( f \), \( g \), 卷积运算\( f\ast g \)定义为
$$ (f\ast g)(n)=\sum_{ij=n}f(i)g(j) $$

卷积运算满足：

1. 交换律：\( f\ast g=g\ast f \)
2. 结合律：\( (f\ast g)\ast h=f\ast (g\ast h) \)
3. 存在单位元\( \iota \). \( \iota\ast f=f \). 不难知道\( \iota \)定义应为：
   $$ \iota(n)= \begin{cases} 1& n = 1 \\ 0& n \neq 1 \end{cases} $$

2. 乘法单位元

普通乘法意义上的单位元，将所有自然数映射到1的函数，记为\( u \)。

3. 莫比乌斯函数

\( u \)在卷积意义下的逆元，称为莫比乌斯函数\( \mu \)。即
$$ u\ast \mu=\iota $$

展开写作：
$$ \sum_{d|n} \mu(d) = \iota(n) $$

\( \mu \) 定义为：
$$ \mu(n)= \begin{cases} 1& \text{n is a square-free positive integer,} \\ & \text{with an even number of prime factors} \\ -1& \text{n is a square-free positive integer,} \\ & \text{with an odd number of prime factors} \\ 0& \text{n has a square prime factor} \end{cases} $$

在知乎上大神引用的定义是：
$$ \mu(n)= \begin{cases} 1& \text{n = 1} \\ (-1)^{k}& \text{n is a positive integer,} \\ & \text{with k distint prime factors} \\ 0& \text{other circumstances} \end{cases} $$

这两种定义是等价的。前者是英文 Wikipedia 上给出的定义。后者可能比较好理解一些。

Prove

莫比乌斯反演写作卷积形式：
$$ f=g\ast u \iff g=f\ast \mu $$

证明：
$$ \begin{align} f=g\ast u \Rightarrow& f\ast \mu=(g\ast u)\ast \mu \\ \Rightarrow& f\ast\mu=g\ast(u\ast\mu) \\ \Rightarrow& f\ast\mu=g\ast\iota \\ \Rightarrow& f\ast\mu=g \end{align} $$

反之
$$ \begin{align} g=f\ast\mu \Rightarrow& g\ast u=(f\ast\mu)\ast u \\ \Rightarrow& g\ast u=f\ast(\mu\ast u) \\ \Rightarrow& g\ast u=f\ast\iota \\ \Rightarrow& g\ast u=f \end{align} $$

Reference

参考资料：
[1] 知乎 - 如何证明莫比乌斯反演 - Syu Gau 的回答
[2] Wikipedia Mobius Inversion Formula
ACM 相关题目（使我接触到莫比乌斯反演的博客）：
[1] forever97 - 莫比乌斯反演