Featured image of post 狄利克雷卷积

狄利克雷卷积

狄利克雷卷积

定义

定义在数论函数$\mathbb Z_+\rightarrow\mathbb C$间的一种二元运算,可这样定义: $$ \begin{align*} (f*g)(n)=\sum_{xy=n}f(x)g(y) \end{align*} $$ 也可写作 $$ \begin{align*} (f*g)(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互质,则有:\

& (f*g)(a)=\sum_{d|a}f(d)g(\frac a d),(f*g)\&(b)=\sum_{d|b}f(d)g(\frac b d)\
&(f*g)(ab)= \sum_{d|ab}f(d)g(\frac d {ab})\
& 注意到\
& (f*g)(a)\cdot(f*g)(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)\
& 即 (f*g)(a)\cdot(f*g)(b)=(f*g)(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*} &证明:\
&(f*g)(n)=\sum_{xy=n}f(x)g(y)\
&交换x,y得\sum_{xy=n}f(y)g(x)=(g*f)(n)\\
&得证 \end{align*} $$

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

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

$$ \begin{align*} ((f*g)*h))(n)&=\sum_{xy=n}(f*g)(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(g*h)(y)\
&=(f*(g*h))*n \end{align*} $$

得证.

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

Licensed under CC BY-NC-SA 4.0
所念皆星河
Built with Hugo
主题 StackJimmy 设计

提供全站CDN服务