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

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}{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 = (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)\)

\[\sigma_k(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}^*, 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})\)

  • \(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}^{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*1\)

上文:

\(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\)

热门相关:高人竟在我身边   顶楼的大象   学霸的黑科技系统   仙城之王   我在末世有套房