狄利克雷卷积学习笔记

· · 个人记录

0.更新

upd 2023.5.18 更新了狄利克雷卷积新的一个性质，更新了常用结论的证明

1.正文

这玩意儿是这么说的：

定义一个运算： * 为狄利克雷卷积。

他是干啥的呢？把两个数论函数进行一个运算。

h(n)=(f * g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})

当 f,g 都是积性函数时，他们的狄利克雷卷积 h 也是一个积性函数。

下面简单证明一下：

此处，n 不为质数。

我们设 n=ab ，其中 1 <a,b<n \ ,gcd(a,b)=1。

则有：

(f * g)(a)= \sum_{d_1|a}f(d_1)g(\frac{a}{d_1}) (f * g)(b)= \sum_{d_2|a}f(d_2)g(\frac{b}{d_2}) (f * g)(ab)= \sum_{d|ab}f(d)g(\frac{ab}{d}) (f * g)(a) \times (f * g)(b)= \sum_{d_1|a}f(d_1)g(\frac{a}{d_1}) \times \sum_{d_2|b}f(d_2)g(\frac{b}{d_2}) =\sum_{d_1|a,d_2|b}f(d_1)g(\frac{a}{d_1})f(d_2)g(\frac{b}{d_2}) =\sum_{d_1|a,d_2|b}f(d_1d_2)g(\frac{ab}{d_1d_2})

因为 a,b 互质，所以 d_1,d_2 互质。

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

证毕。

接下来是关于运算律的知识

这个运算是满足交换律、结合律的，爆算即可

还有一个性质：当函数 A 为积性函数时，有：

(f\cdot A)*(g\cdot A)=h\cdot A

证明一下：

\sum_{d|n}(f(d)A(d))\times(g(\frac{n}{d})A(\frac{n}{d}))=A(n)\sum_{d|n}f(d)g(\frac{n}{d})=A(n)h(n)

证毕

还有一些常用的结论需要记忆：

id(n)=n \varepsilon(n)=[n==1] I(n)=1

则有以下结论：

\mu * I = \varepsilon \mu * id=\varphi \varphi * I=id

第一个的证明：

当 n=1 当，结论显然成立

当 n\not =1 时，考虑 n=\prod\limits_{i=1}^k p_i^{\alpha_i}

考虑哪些 n 的因数有贡献，只有所有质因子都小于 2 的才有

也就意味着有用的质因子次数必定都为 1 或 0

考虑计算答案，有奇数个质因子为 1，则 \mu =-1，否则为 1

\sum_{i=0}^{k} (-1)^kC_k^i=(1-1)^k=0

证毕

第二个的证明：

柿子为 \displaystyle\sum_{d|n}\mu(d)\frac{n}{d}

=\sum_{i=1}^n\sum_{d|(i,n)}\mu(d) =\sum_{i=1}^n[(i,n)=1]

这符合 \varphi 的定义，所以成立

第三个的证明：

这个我们暴力一点来证明，假设 n=\prod\limits_{i=1}^{k} p_i^{\alpha_i}

那么我们要求的 \displaystyle\sum_{d|n} \varphi(d) 就可以化为这样的一个东西：

\sum_{a_1=0}^{\alpha_1}\sum_{a_2=0}^{\alpha_2}\cdots\sum_{a_k=0}^{\alpha_k} \varphi(\prod\limits_{i=1}^n p_i^{a_i})

我们成功化简为繁，将这个柿子从一重和式变成了无数重

其实变得更简单了，我们可以利用 \varphi 是积性函数的特性来将其拆开，变为这样：

(\sum_{a_1=0}^{\alpha_1}\varphi(p_1^{a_1}))\cdots(\sum_{a_k=0}^{\alpha_k}\varphi(p_k^{a_k}))

对每一项单独求，你会发现对于第 i 项，结果为 p_i^{\alpha_i}

由此证毕

之后在一些特殊题目和杜教筛中会使用这些东西。