狄利克雷卷积与莫比乌斯反演详解

狄利克雷卷积与莫比乌斯反演

狄利克雷卷积

前言

狄利克雷卷积(Dirichlet Convolution)，在数论中是一个非常重要的工具，可以很方便的用来推出莫比乌斯反演(Mobius Inversion)的公式以及问题 🤔

正文

定义

狄利克雷卷积是定义在数论函数间的二元运算。

数论函数，是指定义域为 $\mathbb{N}$ ，值域为 $\mathbb{C}$ ， 的一类函数，每个数论函数可以视为一个复数的序列。

定义式为：

$$\bigg(f \ast g\bigg) (n) = \sum_{d \mid n} f(d)g(\frac{n}{d}) (d \in \mathbb{N}) \\$$

也可以写为 ：

$$\bigg(f \ast g\bigg) (n) = \sum_{d \mid n} f(\frac{n}{d})g(d) (d \in \mathbb{N})$$

同时由于对称性，又可以写为 ：

$$\bigg(f \ast g\bigg) (n) = \sum_{xy=n} f(x)g(y) (x,y \in \mathbb{N})$$

“+” 定义为了数论函数直接的直接相加， " $\ast$ "，其实就是乘

常见的数论函数

单位函数

$$\varepsilon (n) = \left[ n=1 \right]$$

幂函数

$$Id_k(n) = n^k$$

约数函数

$$\sigma(n) = \sum_{d \mid n} d^k (d \in \mathbb{N})$$

欧拉函数

$\varphi(n)$ 表示$1 ~ n$中与 $n$ 互质的整数的个数有多少个

$$\varphi (n) = n \prod_{p|n}(1-\frac{1}{p}) (p \in \mathbb{P})$$

（容斥可证）

有趣的是上面所写的函数均为积性函数，其中单位函数和幂函数为完全积性函数。

相关定理

1. 若 $f$ ， $g$ 为积性函数，则 $f \ast g$ 也为积性函数
   证明：

$$设 gcd(a,b) =1 \\ \begin{aligned} \therefore \bigg(f \ast g\bigg)(a) \cdot (f \ast g) (b) &= \sum_{i \mid a} f(i) g(\frac{a}{i}) \cdot \sum_{j \mid b} f(j) g(\frac{b}{j}) \\ &= \sum_{i \mid a} \sum_{j \mid b} f(i) g(\frac{a}{i}) \cdot f(j) g(\frac{b}{j}) \\ &= \sum_{d \mid ab} f(d)g(\frac{ab}{d}) \\ &= (f \ast g) (ab) \\ \end{aligned}\\ 用到了积性函数的性质\\$$

2. $f \ast g = g \ast f \\$

证明 ：

$$\begin{aligned} \bigg(f \ast g\bigg)(n) &= \sum_{ij=n} f(i)g(j) \\ &= \sum_{ji=n} f(j)g(i) \\ &= (g \ast j) (n) \end{aligned}$$

对称性。

3. $(f \ast g ) \ast h = f \ast (g \ast h)$

利用对称性的式子去拆开即可得证。

4. $f \ast (g+h) = f \ast g + f \ast h$

证明：

$$\begin{aligned} \bigg(f \ast (g + h )\bigg) (n) &= \sum_{ij=n} f(i)\bigg( g + h \bigg)(j) \\ &= \sum_{ij=n} f(i)\bigg[ g(j) + h(j) \bigg] \\ &= \sum_{ij=n} f(i)g(j) + f(i)h(j) \\ &= \sum_{ij=n} f(i)g(j) + \sum_{ij=n} f(i)h(j) \\ &= \bigg(f \ast g + f \ast h\bigg) (n) \end{aligned}$$

特殊的卷积

$$Id_k \ast 1 = \sigma_k \\$$

证明：

$$\begin{aligned} \bigg( Id_k \ast 1\bigg) (n) &= \sum_{d \mid n} Id_k (d) 1 (\frac{n}{d}) \\ &= \sum_{d \mid n} Id_k (d) \\ &= \sum_{d \mid n} d^k \\ &= \sigma (n) \end{aligned}$$

同时可以得到一个应用广泛的式子 ：

$$\bigg( f \ast 1 \bigg) (n) = \sum_{d \mid n} f(d)$$

$$\varphi \ast 1 = Id$$

证明 ：

$$\because \bigg( \varphi \ast 1 \bigg)(n) = \sum_{d \mid n} \varphi (d) \\ 将 n 拆分为 \prod p^k \\ \begin{aligned} \therefore \bigg( \varphi \ast 1 \bigg)(n) &= \bigg( \varphi \ast 1 \bigg)(\prod p^k) \\ &= \prod \bigg( \varphi \ast 1 \bigg)( p_i^{k_i}) \\ &= \prod \sum_{j=1}^{k_i}\varphi(p_i^j) \\ &= \prod p_i^{k_i} \\ &= n \\ \end{aligned}\\ \therefore \varphi \ast 1 =Id$$

$$1 \ast 1 = d$$

证明 ：

$$\begin{aligned} \bigg( 1 \ast 1 \bigg)(n) &= \sum_{d \mid n} 1(d) 1(\frac{n}{d}) \\ &= \sum_{d \mid n} 1 \\ &= d(n) \end{aligned}$$

上述的运算加以结合可以得到更多结论 。

狄利克雷卷积逆

需要用到单位元，有 ：

$$\bigg(f \ast \varepsilon \bigg)(n) = \sum_{d \mid n} \varepsilon(d)f(\frac{n}{d}) =f (n)$$

定义 ：

$$f \ast f^{-1} = \epsilon$$

即为狄利克雷卷积逆

关于进一步的推导，占个坑🙃 🙃 🙃

积性函数一定有狄利克雷逆，且它也是积性函数

莫比乌斯反演

前置知识

狄利克雷卷积

介绍

莫比乌斯函数

定义莫比乌斯函数为：

$$\mu (x) = \left\{ \begin{aligned} &1 &x=1 \\ &(-1)^k &\prod_{i=1}^k q_i=1 \\ &0&\max\left\{ q_i \right\} > 1 \end{aligned} \right.$$

推导

$$g=f \ast 1 \iff f= g \ast \mu$$

也就是 ：

$$f(n) = \sum_{d \mid n} g(d) \iff g(n) = \sum_{d \mid n} \mu(d) f( \frac{n}{d})$$

莫比乌斯函数的性质：

$$\sum_{d \mid n} ^n \mu(d) = [n=1]$$

接下来证明莫比乌斯反演定理 ：

$$\begin{aligned} &f(n)=\sum_{d \mid n}g(d)=\sum_{d \mid n}g(\frac{n}{d})\\ &\sum_{d \mid n} \mu(d)f(\frac{n}{d})=\sum_{d\mid n}\mu(d) \sum_{d_1 \mid \frac{n}{d}}g(d_1) \\ &\sum_{d \mid n}\sum_{d_1 \mid \frac{n}{d}} \mu(d)g(d_1) \\ &= \sum_{d_1 \mid n} \sum_{d \mid \frac{n}{d_1}}\mu(d)g(d_1) \\ &= \sum_{d_1 \mid n} g(d_1) \sum_{d \mid \frac{n}{d_1}} \mu(d) \\ &=g(n) \\ \end{aligned}$$

上述仅为充分性证明，必要性证明逆推即可。

问题

坑。