狄利克雷卷积

定义

狄利克雷卷积是一类特殊的生成函数，设有两个函数 \(f\)， \(g\) 则他们的卷积 \(h\) 满足

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

例如，\(h(4)=f(1)g(4)+f(2)g(2)+f(4)g(1)\)

容易发现，狄利克雷卷积满足交换律，结合律与分配律。

狄利克雷卷积并不要求 \(f\)， \(g\) 是积性函数，但如果它们都是积性函数，则它们的卷积也为积性函数。

常用卷积

1. \(\mu\cdot1=\varepsilon\)
2. \(\varphi\cdot1=\text{id}\)
3. \(\mu\cdot \text{id}=\varphi\)

有关这些卷积的证明已经在各自函数的页面给出。

最后，对任意函数 \(f\) 都有 \(f\cdot \varepsilon=f\)

证明：

\[(f\cdot\varepsilon)(n)=\sum_{d|n}f(d)[\frac{n}{d}=1]\]

当且仅当 \(n=d\) 时式子有值 \(f(n)\)