3. 狄利克雷卷积狄利克雷（Dirichlet）卷积是数论函数的基本运算 ， 其重要程度相当于代数中的四则运算 。
3.1 定义与性质为数列定义卷积 ， 自然想到加法卷积 \(c_k = \sum\limits_{i + j = k} a_ib_j\) ， 但加法卷积不能保留积性 。让我们发散想象力 ， 如果将加法换成乘法 ， 结果如何？这引出了 狄利克雷卷积：
\[h(n) = \sum\limits_{d\mid x} f(d) g\left(\dfrac n d\right)\]上式简记为 \(h = f * g\) 。按照定义式计算狄利克雷卷积 ， 复杂度为调和级数的 \(\mathcal{O}(n\ln n)\) 。
接下来证明一些狄利克雷卷积的性质 。
性质 1：狄利克雷卷积具有 交换律 ， 结合律 ， 分配律 。交换律：
\[\begin{aligned}(f * g)(n) & = \sum\limits_{d\mid n} f(d) g\left(\dfrac n d\right) \\& = \sum\limits_{d'\mid n} f\left(\dfrac n {d'}\right) g\left(d'\right) \\& = \sum\limits_{d'\mid n} g(d')f\left(\dfrac n {d'}\right) \\& = (g * f)(n)\end{aligned}\]其中 \(d' = \dfrac n d\) 。因此 \(f * g = g * f\) 。
结合律：
\[\begin{aligned}((f * g) * h)(n) & = \sum\limits_{d\mid n} \left(\sum\limits_{i\mid d} f(i) g\left(\dfrac d i\right)\right) h\left(\dfrac n d\right) \\& = \sum\limits_{i\mid n} f(i) \left(\sum\limits_{d = ki \land d\mid n} g\left(\dfrac d i\right) h\left(\dfrac n d\right)\right) \\& = \sum\limits_{i\mid n} f(i) \left(\sum\limits_{k \mid \frac n i} g\left(k\right) h\left(\dfrac {\frac n i} k\right)\right) \\& = (f * (g * h))(n)\end{aligned}\]其中 \(k = \dfrac d i\) 。因此 \((f * g) * h = f * (g * h)\) 。
分配律：
\[\begin{aligned}((f + g) * h)(n) & = \sum\limits_{d\mid n} (f(d) + g(d)) h\left(\dfrac n d\right) \\& = \sum\limits_{d\mid n} f(d)h\left(\dfrac n d\right) + \sum\limits_{d\mid n} g(d)h\left(\dfrac n d\right) \\& = (f * h + g * h)(n)\end{aligned}\]因此 \((f + g) * h = f * h + g * h\) 。证毕 。
性质 2：\(\epsilon * f = f\) 。证明：\((\epsilon * f)(n) = \sum\limits_{d \mid n}[d = 1]f\left(\dfrac n d\right) = f(n)\) 。证毕 。
因此单位函数 \(\epsilon\) 为狄利克雷卷积的 单位元 。
既然存在单位元 ， 就可以据此定义数论函数 \(f\) 的逆元 \(f ^ {-1}\) ， 满足 \(f * f ^ {-1} = \epsilon\) 。
性质 3：\(f\) 可逆当且仅当 \(f(1)\neq 0\) 。证明：设 \(g = f ^ {-1}\) 。当 \(f(1) = 0\) 时 ， \(f(1)g(1) = 0\) 且 \(f(1) g(1) = \epsilon(1) = 1\) ， 矛盾 。当 \(f(1) \neq 0\) 时 ， \(g(1) = \dfrac 1 {f(1)}\) ， 对 \(n > 1\) 的 \(g(x)\) 通
过 \(\sum\limits_{d\mid x} g(d)f\left(\dfrac n d\right) = 0\) 得到递推式 \(g(n) = -\dfrac{\sum\limits_{d \mid n, d \neq n} g(d)f\left(\dfrac n d\right)} {f(1)}\) 。这同时说明 逆元唯一 。证毕 。
性质 4：\(f = g\) 的充要条件是 \(f * h = g * h\) ， 其中 \(h(1) \neq 0\) 。证明：\(f * h = g * h\Rightarrow f * h * h ^ {-1} = g * h * h ^ {-1} \Rightarrow f = g\) ， 充分性得证 。必要性显然 。证毕 。
性质 5：积性函数的狄利克雷卷积是积性函数 。证明：考虑积性函数 \(f\) 和 \(g\) 的狄利克雷卷积 \(h\) 。若 \(a\perp b\) ， 则
\[\begin{aligned}h(n)h(m) & = \left(\sum\limits_{d_1\mid n} f(d_1) g\left(\dfrac n {d_1} \right)\right)\left(\sum\limits_{d_2\mid m} f(d_2) g\left(\dfrac m {d_2} \right)\right) \\ & = \sum\limits_{d\mid nm} f(d) g\left(\dfrac {nm}{d} \right) \\ & = h(nm)\end{aligned}\]其中 \(d = d_1d_2\) 。第二步依赖于 \(f\) 和 \(g\) 的积性：\(f(d_1) f(d_2) = f(d_1d_2) = f(d)\) 。证毕 。
性质 6：积性函数的逆元是积性函数 。经验总结扩展阅读
- 为什么有些人会孤立认真学习的人
- 苹果ipad分屏功能怎么使用（ipad 9可以分屏学习吗)
- 前端程序员学习 Golang gin 框架实战笔记之一开始玩 gin
- 1 Libgdx游戏学习——环境配置及demo运行
- Go设计模式学习准备——下载bilibili合集视频
- 学习ASP.NET Core Blazor编程系列五——列表页面
- 小学生的学习动机是什么
- 七 Netty 学习：NioEventLoop 对应线程的创建和启动源码说明
- ZCTF note3：一种新解法
- 关于环境学习生活类的名言急
