狄利克雷卷积

定义

定义在数论函数$\mathbb Z_+\rightarrow\mathbb C$间的一种二元运算，可这样定义: $$ \begin{align*} (fg)(n)=\sum_{xy=n}f(x)g(y) \end{align} $$ 也可写作 $$ \begin{align*} (fg)(n)=\sum_{d|n}f(d)g(\frac n d); \end{align} $$

补充

这里定义一些数论函数的符号

单位函数 $\varepsilon(n)=\cases{1,;\text{while};n=1\0,;\text{otherwise}}$

幂函数$Id_k(n)=n^k$,当$k = 1$时为恒等函数$Id(n)$，当$k=0$时为常数函数$\bold1(n)$

除数函数$\sigma_k(n)=\sum_{d|n}d^k$,当$k=1$ 时为因数和函数$\sigma(n)$,$k=0$时为因数个数函数$\sigma_0(n)$

数函数 $\sigma_0(n)$

欧拉函数$\varphi(n)$

如上的函数都是积性函数，即满足$f(1)=1$,且若$a,b$互质，则有$f(a)f(b)=f(ab)$,其中前两个还是完全积性函数，即不需满足$a,b$互质的条件也符合等式。

性质1

积性函数的狄利克雷卷积有一个重要的性质。

若$f,g$是积性函数，则$f*g$也是积性函数。

$$ \begin{align*} & 证明: \ & (f*g)(1)=f(1)g(1),设a,b互质，则有:\

& (fg)(a)=\sum_{d|a}f(d)g(\frac a d),(fg)\&(b)=\sum_{d|b}f(d)g(\frac b d)\ &(fg)(ab)= \sum_{d|ab}f(d)g(\frac d {ab})\ & 注意到\ & (fg)(a)\cdot(fg)(b)=\sum_{d_1|a}f(d_1)g(\frac a {d_1})\cdot \sum_{d_2|b}f(d_2)g(\frac b {d_1})\ & =\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互质,ab的因数都可以唯一地表示为a的某个因数与b的某个因数的乘积，即上式可\ & 表示为 \sum_{d|ab}f(d)g(\frac {ab} d)\ & 即 (fg)(a)\cdot(fg)(b)=(fg)(ab)\ \ &得证 \end{align*} $$

数论函数之间的关系

1.除数函数和幂函数

由定义，可以得到$(f*\bold{1})(n)=\sum_{d|n}f(d)\bold{1}(\frac n d)=\sum_{d|n}f(d)$

所以，$(Id_k*\bold{1})(n)=\sum_{d|n}Id_k(d)=\sum_{d|n} d^k= \sigma_k(n)$

即$$Id_k* \bold 1 = \sigma_k$$

2.欧拉函数和恒等函数

由上文的结论$(f*\bold{1})(n)=\sum_{d|n}f(d)\bold{1}(\frac n d)=\sum_{d|n}f(d)$，可得到

$(\varphi*\bold 1)(n)=\sum_{d|n}\varphi(d)$，当$d = p^m$时（$p$为质数），有：

$$\sum_{d|n}\varphi(d)=\varphi(1)+\sum_{i=1}^m\varphi(p^i)=1+\sum^m_{i=1}(p^i-p^{i-1})=p^m=d$$

所以$$(\varphi*\bold 1)(p^m)=p^m$$。

现在令$n\in N_+$，它可以分成$\prod p^m$,根据前文关于积性函数的定义，必然有$$(\varphi*\bold 1)(\prod p^m)=\prod (\varphi * \bold 1)(p^m)=\prod p^m$$，从而$$(\varphi* \bold 1)(n)=n$$。即：

$$ \varphi * \bold 1=Id$$

其他性质

$$ (fg)(n)=(gf)(n)$$

$$ \begin{align*} &证明:\ &(fg)(n)=\sum_{xy=n}f(x)g(y)\ &交换x,y得\sum_{xy=n}f(y)g(x)=(gf)(n)\\ &得证 \end{align*} $$

这时狄利克雷卷积的交换律.

$$((fg)h)(n)=(f(gh))(n)$$ 证明:

$$ \begin{align*} ((fg)h))(n)&=\sum_{xy=n}(fg)(x)\cdot h(y)\ &=\sum_{xy=n}(\sum_{uv=x}f(u)g(v))h(y)\ &=\sum_{xy=n}\sum_{uv=x}f(u)g(v)h(y)\ &=\sum_{uxy=n}f(u)g(v)h(y)\ \end{align} $$

同理，交换u,x,y，可得 $$ \begin{align*} &=\sum_{xy=n}\sum_{uv=y}f(x)g(u)h(v)\ &=\sum_{xy=n}f(x)\cdot(gh)(y)\ &=(f(g*h))n \end{align} $$

得证.

这是狄利克雷卷积的分配律