狄利克雷卷积简介
卷积这名字听起来挺学究的,今天学了之后发现其实挺朴实hhh。
卷积:
“(n)”表示到n的一个范围。
设\(f,g\)是两个数论函数(也就是说,以自然数集为定义域的复数值函数),则卷积运算\(f\ast g\)定义为
\]
另一种写法就是:
\]
这里给一段数论函数的定义:
数论函数亦称算术函数,一类重要的函数,指定义在正整数集上的实值或复值函数,更一般地,也可把数论函数看做是某一整数集上定义的函数。
一些数论函数
首先最简单的就是常数函数,直接映射到一个正整数,比如\(f(x)=1,f(x)=2\)这样的。
再有就是一些整数域数列的通项公式函数,例如\(f(x)=x\)这样的。
还有就是\(\phi(x)\)欧拉函数,表示因数个数。
另外就是元函数e,写成表达式就是\(e(x)=[x=1]\).
还有特殊的常数函数,把所有的数字映射成1的\(u(x)=1\)
莫比乌斯函数:通常,莫比乌斯函数\(\mu\)定义为
\(\mu(1)=1;\)
\(\mu(n)=(-1)^k\)如果n能写成k个不同素数之积;
\(\mu(n)=0\),其他情况。
一些简单性质
交换律
根据$$(f\ast g)(n) = \sum_{ij=n}{f(i)g(j)}$$
这个定义,结论是显然的了。
结合律
只要证明\((f*g)*h=f*(g*h)\)就可以了。
于是左边就是
\]
右边是
\]
得证。
加法的结合律
看不懂网上的证明,简单贴一下。
存在单位元\(\iota\) 使得\(\iota\ast f=f\)
我们需要
\]
故不难猜到\(\iota\) 应该定义为\(\iota(n)=\) \begin{cases} 1&n=1\ 0&n\neq1 \end{cases}
事实上,直接验证可得
\]
以上说明数论函数在卷积意义下构成一个交换群。
卷积差不多就这些。。。
莫比乌斯反演证明
\(\mu\)函数的性质
为什么要发明这个函数呢,肯定是有道理的。
我们一般把\(\mu\)看做是\(u(x)=1\)在卷积意义下的逆元。就是说它满足:
\]
1就是函数f(n)=1。展开来写就是
\]
当 \(n=1\)时,显然成立。
当 \(n>1\)时,根据唯一分解定理我们可以把n拆成\(n=p^{k_1}_1*p^{k_2}_2*\cdots*p^{k_n}_n\)
当 \(\exists k_x=1\)时,\(\mu\)值肯定为0,所以我们把\(k_x\)都看作1。
而d枚举的就是n的因子,其实就是在n的质因子集合里取走任意个。所以这个式子可以写成这个样子:
\]
那么$$\sum_{d\mid n}\mu(d)=1$$就得证了。
反演形式1证明
法1
莫比乌斯反演形式1就是,如果\(f(n)=\sum_{d\mid n}g(d)\),则\(g(n)=\sum_{d\mid n}\mu\left(\frac{n}{d}\right)f(d)\)
写成卷积的形式就是,如果\(f=g*e\),则\(g=f*\mu\)。
这样写就比原来哪样要好记而且简介多了。
有了之前的铺垫,接下来就很容易了。
把原方程两边乘一个\(\mu\)
\]
\]
由于之前有证明\(\mu*e=1\)所以就有\(f*\mu=g\)于是得证。
感觉这种方法非常巧妙啊。。
法2
听知乎上大佬讲的,莫比乌斯反演其实就是偏序集上的容斥,简单理解了一下大概是这样的。
我们知道容斥定理的公式是
\]
用叉姐的话将就是:n 个坏事都不发生的概率,可以通过 2 n 个同时发生的概率计算,定义一个由数映射到它质因子集合的映射,映射关系显然是整除,V看做是S的质因子但不是V的质因子的乘积,那么莫比乌斯反演定理就和容斥的式子长得一模一样了。\(\mu\)就是\((-1)^{\mid S\mid-\mid V\mid}\)
反演形式2证明
以后再填坑。。感觉效率好低QAQ
\(\phi\)和μ的关系
有一个经典公式就是:
\]
这个公式怎么证明呢?
我们可以把它简记为
\]
然后两边乘一个\(\mu\)
\]
\]
再化回来
\]
μ只有在d质因数分解之后各个质因子个数为1的时候才有贡献,为奇数个因子的时候-,偶数为+,这不就是一个容斥求因子个数么。。于是左边等于右边,得证
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:狄利克雷卷积&莫比乌斯反演证明 - Python技术站