注:阅读本文需要一定的基础数论或抽象代数知识
先给出一堆名词定义和解释
- 数论函数(算术函数):
函数$f$被称为数论函数,如果它的定义域为正整数,值域为复数,比较常见的有欧拉函数$\varphi$和莫比乌斯函数$\mu$ - 环:
如果集合$R$与二元运算$+,\cdot$,且$R$中的任意两个元素在+运算下是一个阿贝尔群(可交换群),在$\cdot$下是一个幺半群 那么$(R,+,\cdot)$是一个环 特别的 如果元素对于$\cdot$运算可交换 那么这是一个交换环 - 幺半群:
$(M,\cdot)$是幺半群 如果$(M,\cdot)$符合以下公理:
满足元素结合律 即$\forall a,b,c \in (M,\cdot)$有$(a\cdot b)\cdot c=a\cdot(b\cdot c)$
存在单位元 即$\exists e\in (M,\cdot)$ $s.t.$ $a\cdot e=e\cdot a=a$
满足运算封闭性 即$\forall a,b \in (M,\cdot)$有$a\cdot b \in (M,\cdot)$
狄利克雷卷积的引出
为了使数论函数之间的运算具有类似与整环的性质(方便研究)
对于数论函数$f,g$的加法 显然$f+g=g+f$
而对于乘法,我们不能简单的将两个数论函数相乘 而引入狄利克雷卷积 记作$\cdot$
$f\cdot g(n)=\sum_{d|n}{f(d)g(\frac{n}{d})}$
我们来证明一下$(数论函数,+,\cdot)$是一个可交换环
记$C=$数论函数集
$\forall f,g,u \in C$
首先$f+g=g+f$
说明加法可交换
对$(2)$做换元$k=\frac{n}{d}$则
$g\cdot f(n)=\sum_{\frac{n}{k}|n}{g(\frac{n}{d})f(n)}$
由于$\frac{n}{k}$也是$n$的因子 那么换一种写法就是
$g\cdot f(n)=\sum_{k|n}{g(\frac{n}{d})f(n)}$
显然有$f\cdot g(n)=g\cdot f(n)$
说明乘法可交换
指出单位元$e(n)=[n=1]$
由于乘法可交换 所以这里只需证明 $f\cdot e=f$
$f\cdot e(n)=\sum_{d|n}{f(d)e(\frac{n}{d})}$
注意到这里的$e(\frac{n}{d})$只有当$d=n$的时候才为1 其余都为0
那么$f\cdot e(n)=f(n)e(1)=f(n)$
所以单位元存在
即$(f\cdot g)\cdot u(n)=f\cdot(g\cdot u)(n)$
故结合律成立
由于复数域内乘法满足封闭性 那么 $f\cdot g \in C$也成立
因此
$(C,\cdot)$是一个幺半群
$(C,+,\cdot)$是个环 而且还是个交换环
数论函数与狄利克雷卷积
我们不加证明的给出一些恒等式(因为重点不在这里(雾))
- $1\cdot\mu=e$ 其中$1(n)=1$
- 由1.可以得到 $g=f\cdot 1$ iff $f=g\cdot \mu$即大名鼎鼎的莫比乌斯反演公式
- $\lambda\cdot |\mu| =e$ 其中$\lambda$是刘维尔函数
- $d=1\cdot 1$ 其中d(n)为n的因数个数
……….还有很多以后再补
莫比乌斯反演
$f=g\cdot \mu$ 当且仅当 $g=f\cdot 1$
$f,g$都是一般的数论函数
莫比乌斯函数
定义
$\mu$是莫比乌斯函数 他是这么定义的
$\mu(1)=1$
设$n=p_1^{k_1}\cdot p_2^{k_2}\cdots p_m^{k_m}$
如果$\prod_{i=1}^m{k_i}=1$则$\mu(n)=(-1)^m$
否则$\mu(n)=0$
通俗一点说就是 有平方因子的数的莫比乌斯函数值为0
性质
- 莫比乌斯函数是积性函数
$\mu(a\cdot b)=\mu(a)\cdot \mu(b),gcd(a,b)=1$注意这里的乘法是数量乘法不是卷积 - $\sum_{d|n}{\mu(d)=[n=1]}$
这个就是上面提过的$1\cdot\mu=e$
公式
如果数论函数$f,g$满足$f(n)=\sum_{d|n}{g(d)}$
那么有 $g(n)=\sum_{d|n}{\mu(d)f(\frac{n}{d})}=\sum_{d|n}{\mu(\frac{n}{d})f(d)}$
或者可以这么写
$f(i)=\sum_{d=1}^{\lfloor\frac{n}{i}\rfloor}{g(d\cdot i)}\Rightarrow g(i)=\sum_{d=1}^{\lfloor\frac{n}{i}\rfloor}{f(d\cdot i)\mu(d)}$枚举了n的因数
应用
关于莫比乌斯反演的应用 由于涉及篇幅较长 将重开一篇文章介绍
结
本文为莫比乌斯反演做基础知识的铺垫(持续更新中…)