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

QwQ 文章目前没有题目，只有理论知识

狄利克雷卷积

狄利克雷卷积 （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\) 都为积性函数，那么 \(f*g\) 也为积性函数

设 \(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}{d1}) * \sum{d_2|b}f(d_2)g(\frac{b}{d2})\
=&\sum{d_1d_2|ab}f(d_1d_2)g(\frac{ab}{d_1d2})\
=&\sum{d|ab}f(d)g(\frac{ab}{d})\\ =&\big(f*g\big)(ab) \end{aligned} \]

因为满足 \(a\)、\(b\) 互质，我们能将 \(\sum_{d1|a}\sum{d2|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 = (f*h)+(g*h)\)

\[\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 \]

特别的，有：

• \(k=1\) 时，为恒等函数 \(Id(n)\)，即 \(Id(n)=n\)；

• \(k=0\) 时，为常数函数 \(\pmb1(n)\)，即 \(\pmb1(n)=1\)；

这里的常数函数 \(\pmb 1(n)\) 的函数名是加粗了 的数字 \(1\)，不要和 \(1\) 弄混了.
在某些场合，有人会用大写字母 \(I\) 来代替 \(\pmb 1\)，以防混淆，这里还是使用 \(\pmb 1\).

除数函数 \(\sigma_k(n)\)

\[\sigmak(n)=\sum{d|n} d^k \quad (d\in \mathbb{N}) \]

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

特别的，有：

• \(k=1\) 时，为因数函数 \(\sigma(n)\)，即 \(\sigma(n)=\sum_{d|n} d\)；
• \(k=0\) 时，为个数函数 \(d(n)\)，即 \(d(n)=\sum_{d|n} 1\)；

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

• \(\sigma(n) = \prod{i=1}^m(\sum{j=0}^{c_i} p_i^j)\)
• \(d(n) = \prod_{i=1}^m (c_i+1)\)

欧拉函数 \(\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}^*, pi \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})\)：

• 若 \(n=1\)，那么 \(\mu(n)=1\)；

• 若 \(\exists\ i\in[1,m]\)，使得 \(c_i \ge 2\)，那么 \(\mu(n)=0\)，否则 \(\mu(n)=(-1)^m\)；

一些性质

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}^{ci},n’=\prod{i=1}^k pi\) 那么 \(\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}^{ci},n’=\prod{i=1}^k pi\) 那么 \(\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\)