狄利克雷生成函数


表示素数集合。

狄利克雷生成函数

对于无穷序列 ,定义其狄利克雷生成函数(Dirichlet series generating function,DGF)1为:

如果序列 满足积性(是

积性函数):,那么其 DGF 可以由质数幂处的取值表示:

对于两个序列 ,其 DGF 之积对应的是两者的 狄利克雷卷积 序列的 DGF:

常见积性函数的 DGF

DGF 最适合用于研究与积性函数的狄利克雷卷积相关的问题。因此首先我们要了解常见积性函数的 DGF。

黎曼函数

序列 的 DGF 是 是黎曼函数。

由于其满足积性,因此我们可以得到 的 DGF 的另一种形式:

莫比乌斯函数

对于莫比乌斯函数 ,它的 DGF 定义为

容易发现 ,也就是说

欧拉函数

对于欧拉函数 ,它的 DGF 定义为

因此有

幂函数

对于函数 ,它的 DGF 定义为

根据这些定义,容易推导出 表示狄利克雷卷积。因为

其他函数

对于约数幂函数 ,它的 DGF 可以表示为狄利克雷卷积的形式:

对于 (无平方因子数),它的 DGF 为

Dirichlet 卷积

定义

对于两个数论函数 ,则它们的狄利克雷卷积得到的结果 定义为:

上式可以简记为:

狄利克雷卷积是数论函数的重要运算,数论函数的许多性质都是通过这个运算挖掘出来的。

狄利克雷卷积与狄利克雷生成函数(DGF)密切相关。对于两个序列 ,其狄利克雷生成函数之积,对应的是两者的狄利克雷卷积序列的狄利克雷生成函数:

性质

交换律:

结合律:

分配律:

等式的性质: 的充要条件是 ,其中数论函数 要满足

证明: 充分性是显然的。

证明必要性,我们先假设存在 ,使得 。那么我们找到最小的 ,满足 ,并设

则有:

处的取值不一样,即有 。矛盾,所以必要性成立。

证毕

以上性质在狄利克雷生成函数的观点下是显然的,这种特殊的卷积等价于相应生成函数的乘法。

单位元: 单位函数 是 Dirichlet 卷积运算中的单位元,即对于任何数论函数 ,都有

狄利克雷卷积运算中的单位元不是常函数,但是在狄利克雷生成函数中等价于常数

狄利克雷卷积运算中的数论函数常函数 ,在狄利克雷生成函数中等价于黎曼函数

逆元: 对于任何一个满足 的数论函数,如果有另一个数论函数 满足 ,则称 的逆元。由 等式的性质 可知,逆元是唯一的。

狄利克雷卷积运算中的逆元,在狄利克雷生成函数中相当于倒数运算。

容易构造出 的表达式为:

重要结论

两个积性函数的 Dirichlet 卷积也是积性函数

证明: 设两个积性函数为 ,再记

,则:

所以:

所以结论成立。

证毕

积性函数的逆元也是积性函数

证明:我们设 ,并且不妨设 。考虑归纳法:

  • ,则 ,结论显然成立;

  • ,假设现在对于所有的 ,都有 ,所以有:

    又因为 ,所以有:

综合以上两点,结论成立。

证毕

这也说明,数论函数的积性,在狄利克雷生成函数中的对应具有封闭性。

例子


相关应用

DGF 的应用主要体现在构造积性序列的狄利克雷卷积序列。研究方向通常是质数处的取值。

例如在杜教筛的过程中,要计算积性序列(积性函数在正整数处的取值构成的序列) 的前缀和,我们需要找到一个积性序列 使得 都可以快速求前缀和。那么我们可以利用 DGF 推导这一过程。

洛谷 P3768 简单的数学题 为例,我们要对 构造一个满足上述条件的积性序列 。由于 是积性的,考虑其 DGF

因此 。而 对应的积性函数为 ,所以令 即可。这样有 ,两者都是可以快速计算前缀和的。

Footnotes

  1. https://en.wikipedia.org/wiki/Generating_function#Dirichlet_series_generating_functions_(DGFs)

贡献者:@Yufan@CCXXXI@Great-designer

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组