狄利克雷卷积

狄利克雷卷积

狄利克雷卷积

定义

定义在数论函数$\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})\
& 注意到\
& (f
g)(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)\
& 即 (f
g)(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)=(g
f)(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
}
$$

得证.

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

作者

Steve Li

发布于

2021-09-21

更新于

2022-01-22

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×