狄利克雷卷积及常见函数与莫比乌斯反演

· · 个人记录

题目以后再补吧

狄利克雷卷积

狄利克雷卷积（Dirichlet Convolution）在解析数论中是一个非常重要的工具.

使用狄利克雷卷积可以很方便地推出一些重要函数和公式，它在信息学竞赛和解析数论中至关重要.

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

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

它常见的定义式为：

\big(f*g\big)(n)=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{d|n}f(\frac{n}{d})g(d)\quad (d\in\mathbb{N})\\ \big(f*g\big)(n)=\sum_{xy=n}f(x)g(y)\quad (x,y\in\mathbb{N})

狄利克雷卷积的一些定理

  1. *若 f、g 都为积性函数，那么 $fg$ 也为积性函数**

设 a、b 满足 gcd(a,b)=1，那么：

\begin{aligned} & \big(f*g\big)(a)\ *\ \big(f*g\big)(b) \\ =&\sum_{d_1|a}f(d_1)g(\frac{a}{d_1}) * \sum_{d_2|b}f(d_2)g(\frac{b}{d_2})\\ =&\sum_{d_1d_2|ab}f(d_1d_2)g(\frac{ab}{d_1d_2})\\ =&\sum_{d|ab}f(d)g(\frac{ab}{d})\\ =&\big(f*g\big)(ab) \end{aligned}

因为满足 a、b 互质，我们能将 \sum_{d_1|a}\sum_{d_2|b} 合并成 \sum_{d_1d_2|ab}，所以 f*g 也就是积性函数了.

  1. 狄利克雷卷积具有交换律，即 f*g = g*f
\begin{aligned} &\big(f*g\big)(n)\\ =&\sum_{xy=n}f(x)g(y)\\ =&\sum_{yx=n}f(y)g(x)\\ =&\big(g*f\big)(n) \end{aligned}

显而易见

  1. 狄利克雷卷积具有结合律，即 (f*g)*h = f*(g*h)
\begin{aligned} &\Big(\big(f*g\big)*h\Big)(n)\\ =&\sum_{wz=n}\big(f*g\big)(w)\ h(z)\\ =&\sum_{wz=n}\Big(\sum_{xy=w}f(x)g(y)\Big)h(z)\\ =&\sum_{xyz=n}f(x)g(y)h(z) \end{aligned} \begin{aligned} &\Big(f*\big(g*h\big)\Big)(n)\\ =&\sum_{xw=n}f(x)\big(g*h\big)(w)\\ =&\sum_{xw=n}f(x)\Big(\sum_{yz=w}g(y)h(z)\Big)\\ =&\sum_{xyz=n}f(x)g(y)h(z) \end{aligned}

如上，可知两式相等，结合律成立.

  1. *狄利克雷卷积具有分配律，即 $(f+g)h = (fh)+(gh)$**
\begin{aligned} &\Big(\big(f+g\big)*h\Big)(n)\\ =&\sum_{xy=n}\big(f(x)+g(x)\big)\ h(y)\\ =&\sum_{xy=n}f(x)h(y)+g(x)h(y)\\ =&\sum_{xy=n}f(x)h(y)+\sum_{xy=n}g(x)h(y)\\ =&\big(f*h\big)(n)+\big(g*h\big)(n) \end{aligned}
总结一下：
  1. 若 f、g 都为积性函数，那么 f*g 也为积性函数
  2. 狄利克雷卷积具有交换律，即 f*g = g*f
  3. 狄利克雷卷积具有结合律，即 (f*g)*h = f*(g*h)
  4. 狄利克雷卷积具有分配律，即 (f+g)*h = (f*h)+(g*h)

关于“狄利克雷卷积”名称：

首先，狄利克雷（Gustav Lejeune Dirichlet）是 19 世纪德国的数学家，他是解析数论的创立者，是解析数论很多重要理论的提出者.

“狄利克雷卷积”亦可称为“狄利克雷乘积”，如果定义普通函数加法为数论函数间的“加”运算，那么这里的狄利克雷卷积就是数论函数的“乘”运算，并且，狄利克雷卷积满足交换律、结合律和分配律，其运算法则和普通算数乘法完全类似.

函数部分（均为积性函数

单位函数（单位元）\epsilon(n)

\epsilon(n)=\begin{cases}1, && n=1 \\ 0, && \texttt{otherwise.}\end{cases}

显然，有：

\big(f*\epsilon\big)(n)=\sum_{d|n}f(d)\epsilon(\frac{n}{d})=f(n)

因此，单位函数 \epsilon(n) 称为狄利克雷卷积的单位元，它在狄利克雷卷积中的作用和 1 在普通乘法中的作用是类似的.

任何函数（包括 \epsilon）和 \epsilon 进行狄利克雷卷积，都得到该函数本身.

这里再引入一个东西：

狄利克雷逆

我们可以把这里的“逆”和“逆元”作类比.

例如，在普通运算中，一个数的“逆元”就是这个数的倒数；

在同余运算中，一个数的“逆元”在同个模的意义下，能使得它与这个数相乘的结果与 1 同余.

分别而言，如果我们规定 n 的逆元是 n^{-1}（这个符号是作为整体引入的，大多数情况下不能简单地理解为 \frac{1}{n}），那么就有这样两个式子：

n\times n^{-1} = 1 n\times n^{-1} \equiv 1 \quad \mod r

数字 1 代表两种运算中的单位元，所以说，逆元在类似乘法的运算中起着“倒数”的地位.

在狄利克雷卷积中，单位元为 \epsilon，我们定义狄利克雷逆如下：

f*f^{-1}=\epsilon

函数 f^{-1} 就称为函数 f 的狄利克雷逆.

幂函数 Id_k(n)

Id_k(n)=n^k

特别的，有：

除数函数 \sigma_k(n)

\sigma_k(n)=\sum_{d|n} d^k \quad (d\in \mathbb{N})

直观上理解，\sigma_k(n) 表示 n 的所有因子的 k 次幂之和.

特别的，有：

或者说，假设 n 分解为 \prod_{i=1}^m p_i^{c_i} \quad (c_i\in \mathbb{N}^*, p_i\in \mathbb{P})，那么：

欧拉函数 \varphi(n)

在数论中，对正整数 n，欧拉函数 \varphi(n) 是小于或等于 n 的正整数中与 n 互质的数的数目。此函数以其首名研究者欧拉命名，它又称为 \varphi 函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。

当 n 是质数的时候，显然有 \varphi(n) = n - 1.

一些性质

  1. 欧拉函数是积性函数

如果有 \gcd(a, b) = 1，那么 \varphi(a \times b) = \varphi(a) \times \varphi(b)；

特别地，当 n 是奇数时 \varphi(2n) = \varphi(n)；

  1. n = \sum_{d \mid n}{\varphi(d)}

可以这样考虑：如果 \gcd(k, n) = d，那么 \gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1, ( k < n )。

如果我们设 f(x) 表示 \gcd(k, n) = x 的数的个数，那么 n = \sum_{i = 1}^n{f(i)}。

根据上面的证明，我们发现，f(x) = \varphi(\dfrac{n}{x})，从而 n = \sum_{d|n}\varphi(\dfrac{n}{d})，所以上式化为 n = \sum_{d|n}\varphi(d)。

  1. 若 n = p^k，其中 p 是质数，那么 \varphi(n) = p^k - p^{k - 1}。

显然对于从 1 到 p^k 的所有数中，除了 p^{k-1} 个 p 的倍数以外其它数都与 p^k 互素，故 \varphi(p^k)=p^k-p^{k-1}=p^{k-1}\times(p-1)。

那么根据 1、3 性质可得：

  1. 若 n 的分解为 \prod_{i=1}^m p_i^{c_i} \quad (c_i \in \mathbb{N}^*, p_i \in \mathbb{P})，则 \varphi(n) = n\times \prod_{i=1}^m \frac{p_i-1}{p_i}

证明略.

欧拉定理

若 (a,m)=1 ，则 a^{\varphi(m)}\equiv1\ (\text{mod}\ m)

扩展欧拉定理

a^b\equiv \begin{cases} a^{b\bmod \varphi(p)}&(a,p)=1\\ a^b&(a,p)\ne 1,b<\varphi(p)\\ a^{b\bmod \varphi(p)+\varphi(p)}&(a,p)\ne 1,b\geq\varphi(p) \end{cases} \mod m

莫比乌斯函数 \mu(n) 与 莫比乌斯反演（Möbius Inversion）

\mu(n):=\begin{cases}1&& n=1\\ 0 && n\ 含有平方因子 \\ (-1)^k && k为\ n\ 的本质不同质因子个数\end{cases}

或者说，若 n 的分解为 \prod_{i=1}^m p_i^{c_i} \quad (c_i \in \mathbb{N}^*, p_i \in \mathbb{P})：

一些性质

  1. 莫比乌斯函数为积性函数；

  2. \sum_{d\mid n}\mu(d)=\begin{cases}1&n=1\\0&n\neq 1\\\end{cases}

设 n=\prod_{i=1}^k{p_i}^{c_i},n'=\prod_{i=1}^k p_i 那么 \sum_{d|n}\mu(d)=\sum_{d|n'}\mu(d)=\sum_{i=0}^k \dbinom{k}{i}\cdot(-1)^i=(1+(-1))^k，根据二项式定理，易知该式子的值在 k=0 即 n=1 时值为 1 否则为 0，这也同时证明了 \sum_{d|n}\mu(d)=[n=1]=\varepsilon(n) 以及 \mu*1=\varepsilon.

所以，莫比乌斯函数也可定义为函数 \pmb 1 的逆，即 \mu=\pmb 1^{-1}，那么就可以使用狄利克雷卷积来推导出莫比乌斯反演的结论了：

g=f*\pmb 1 \Leftrightarrow f=g*\mu

将其展开，即：

g(n)=\sum_{d|n}f(d)\Leftrightarrow f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})

莫比乌斯反演扩展

对于数论函数 f,g 和完全积性函数 t 且 t(1)=1:

f(n)=\sum_{i=1}^nt(i) g\bigg( \bigg\lfloor\frac{n}{i}\bigg\rfloor \bigg )\iff g(n)=\sum_{i=1}^n\mu(i)t(i) f\bigg( \bigg\lfloor\frac{n}{i}\bigg\rfloor \bigg )

常用狄利克雷卷积

\epsilon = \mu*\pmb1

上文：

设 n=\prod_{i=1}^k{p_i}^{c_i},n'=\prod_{i=1}^k p_i 那么 \sum_{d|n}\mu(d)=\sum_{d|n'}\mu(d)=\sum_{i=0}^k \dbinom{k}{i}\cdot(-1)^i=(1+(-1))^k，根据二项式定理，易知该式子的值在 k=0 即 n=1 时值为 1 否则为 0，这也同时证明了 \sum_{d|n}\mu(d)=[n=1]=\varepsilon(n) 以及 \mu*1=\varepsilon.

d=\pmb1*\pmb1、\sigma = Id*\pmb1

均易证，略

Id=\varphi*\pmb1、\varphi =\mu*Id

上文：

Id(n) = n = \sum_{d \mid n}{\varphi(d)}

可以这样考虑：如果 \gcd(k, n) = d，那么 \gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1, ( k < n )。

如果我们设 f(x) 表示 \gcd(k, n) = x 的数的个数，那么 n = \sum_{i = 1}^n{f(i)}。

根据上面的证明，我们发现，f(x) = \varphi(\dfrac{n}{x})，从而 n = \sum_{d|n}\varphi(\dfrac{n}{d})。注意到约数 d 和 \dfrac{n}{d} 具有对称性，所以上式化为 n = \sum_{d|n}\varphi(d)。

而因为 \mu 是 \pmb 1 的逆，所以 \varphi*\pmb 1*\mu=Id*\mu=\varphi