狄利克雷卷积

注：阅读本文需要一定的基础数论或抽象代数知识

先给出一堆名词定义和解释

数论函数(算术函数)：
函数$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$
说明加法可交换

$f\cdot g(n)=\sum_{d|n}{f(d)g(\frac{n}{d})} \cdots(1)$ $g\cdot f(n)=\sum_{d|n}{g(d)f(\frac{n}{d})} \cdots(2)$

对$(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) \\ =\sum_{ld=n}{(f\cdot g)(l)u(d)} \\ =\sum_{ld=n}{(\sum_{ij=l}{f(i)g(j)})u(d)} \\ =\sum_{ijd=n}{f(i)g(j)u(d)} \\$ $f\cdot(g\cdot u)(n) \\ =\sum_{il=n}{f(i)(g\cdot u)(l)} \\ =\sum_{il=n}{f(i)\sum_{jd=l}{g(j)u(d)}} \\ =\sum_{ijd=n}{f(i)g(j)u(d)} \\$

即$(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的因数

应用

关于莫比乌斯反演的应用由于涉及篇幅较长将重开一篇文章介绍

结

本文为莫比乌斯反演做基础知识的铺垫（持续更新中…）