迪利克雷卷积

约 341 个字 预计阅读时间 1 分钟

狄利克雷卷积

定义在数论函数间一种二元运算，可这样定义：
$(f*g)(n)=\sum\limits_{xy=n} f(x)*g(y)$
也常常等价地写作：
$(f*g)(n)=\sum\limits_{d\mid n} f(d)*g(n/d)$

常用数论函数

单位函数$ε(n)=\begin{cases}1&n=1\\0&otherwise\end{cases}$
符号是希腊字母$epsilon$

幂函数$Id_k(n)=n^k$.
k=1时为恒等函数$Id(n)$
k=0时为常数函数$1(n)$

除数函数$σ_k(n)=\sum\limits_{d\mid n} d^k$
k=1时为因数和函数$σ(n)$
k=0时为因数个数函数$σ_0(n)$
符号是希腊字母$sigma$

欧拉函数$φ(n)$
符号是希腊字母$phi$

这些函数都是积性函数，前二者还是完全积性函数

常用数论函数联系

常用，牢记

除数函数与幂函数
$Id_k*1=σ_k$
欧拉函数与恒等函数
$φ*1=Id$
注意：$1$此时是常数函数

狄利克雷卷积性质

若$f$,$g$是积性函数，则$f*g$也是积性函数
交换律，结合律

对函数加法的分配律，即
$(f*(g+h))(n)=(f*g)(n)+(f*h)(n)$
单位元是单位函数$ε$
狄利克雷逆存在必要条件是$f(1)\ne 0$
英文是Dirichlet inverse，但是已有乘法逆元Multiplicative inverse modulo，所以翻译成这样

积性函数必然存在狄利克雷逆，且狄利克雷逆仍是积性函数。