莫比乌斯反演学习笔记

数论函数

定义：定义域是正整数，值域是复数的函数。

狄利克雷卷积

1. 定义：

$$\begin{aligned} (f\ast g)(n)=&\sum_{d|n,d\in{\mathbb{N}}}{f(d)\cdot g\bigg(\dfrac{n}{d}\bigg)}\\ =&\sum_{d|n,d\in{\mathbb{N}}}{f\bigg(\dfrac{n}{d}\bigg)\cdot g(d)} \end{aligned}$$

常用的数论函数

1. 单位函数：

$$\varepsilon(n)= \begin{cases} 1& n=1\\ 0& \text{其它} \end{cases}$$

2. 幂函数：

$$Id_{k}(n)=n^k$$

• 当 $k=1$ 时，$Id_{k}(n)$ 可以表示为 $Id(n)$。
• 当 $k=0$ 时，$Id_{k}(n)$ 可以表示为 $I(n)$。

3. 除数函数：

$$\sigma_{k}(n)=\sum_{d|n}{d^k}$$

4. 欧拉函数

$$\varphi(n)=n\cdot\prod_{i=1}^{k}{\dfrac{p_i-1}{p_i}}$$

积性函数

1. 定义：积性函数是指对于所有互质的正整数 $a,b$，都有 $f(ab)=f(a)\cdot f(b)$ 的数论函数。
   另：完全积性函数指任意两个正整数 $a,b$，都有 $f(ab)=f(a)\cdot f(b)$ 的数论函数。

2. 性质：若 $f$ 是一个积性函数，那么 $f(1)=1$。

狄利克雷卷积的常用定理

1. 若 $f,g$ 都是积性函数，那么 $f\ast g$ 也是积性函数。
2. 交换律：$f\ast g=g\ast f$
3. 结合律：$(f\ast g)\ast h=f\ast(g\ast h)$
4. 分配律：$f\ast(g+h)=f\ast g+f\ast h$

常用的特殊狄利克雷卷积

1. $Id_k\ast I=\sigma_{k}$
2. $\varphi\ast I=Id$
3. $I\ast I=\sigma$

狄利克雷逆

1. 单位元：乘上单位元后不改变结果的数值。
2. 狄利克雷卷积中的单位元：$\varepsilon$。
3. 狄利克雷逆：

• 定义：若函数 $f\ast g=\varepsilon$，就称 $f$ 和 $g$ 互为狄利克雷逆。
• 函数 $f$ 的狄利克雷逆表示为 $f^{-1}$。
• 一个数论函数 $f$ 存在狄利克雷逆的充分必要条件是：$f(1)\neq 0$，且函数 $f$ 若存在狄利克雷逆，则 $f^{-1}$ 是唯一的。
• 积性函数一定存在狄利克雷逆。

莫比乌斯反演公式

1. 莫比乌斯函数

• 定义：莫比乌斯函数 $\mu$ 为常数函数 $I$ 的狄利克雷逆。

$$\mu(n)= \begin{cases} 1& n=1\\ (-1)^{k}& n=\prod\limits_{i=1}^{k}{p_i}\space\space\space p_i\in \mathbb{prime}\\ 0& \text{其它} \end{cases}$$

2. 莫比乌斯反演公式

• $g=f\ast I\Longleftrightarrow f=g\ast \mu$
• $g(n)=\sum\limits_{d|n}{f(d)}\Longleftrightarrow f(n)=\sum\limits_{d|n}{\mu(d)\cdot g\big(\frac{n}{d}\big)}$
• $g(n)=\sum\limits_{n|N}{f(N)}\Longleftrightarrow f(n)=\sum\limits_{n|N}{g(N)\cdot\mu\big(\frac{N}{n}\big)}$