默比乌斯反演公式(Mobius inversion formula)一种序列反演公式。经典的莫比乌斯反演公式在十八世纪由费迪南德·莫比乌斯(FerdinandMöbius)引入到数学理论中。在数学上,当不同的局部有限部分有序集合取代了通过可分性排序的自然数的经典情况时,便可获得其他莫比乌斯反演公式。
简介
默比乌斯反演公式(Mobius inversion formula)一种
序列反演公式。它是德国数学家默比乌斯(Mobius , A. F.)提出的,最早出现在初等数论的研究中。设f(n)和g(n)是定义在自然数集N上的两个函数,反演公式:
称为(经典的)默比乌斯反演公式。这里,记号“拼”表示左右两式可以互推。函数爪n)是默比乌斯在1832年研究素数分布时首次引入的,后称它为(经典的)
默比乌斯函数。
公式声明
经典版本说明,如果g和f是算数函数,则:
则有:
其中μ是Möbius函数,并且和在n的所有正除数d之间延伸。 实际上,原始的f(n)可以通过使用反演公式给出g(n)来确定。 这两个序列是彼此的
莫比乌斯变换。
如果f和g是从正整数到某些阿贝尔组(被视为ℤ模块)的函数,那么公式也是正确的。
用Dirichlet卷积的语言,第一个公式可以写成:g=f1,
其中*表示Dirichlet卷积,1是常数函数1(n)= 1。然后将第二个公式写为:f=g。
关于乘法函数的文章中给出了许多具体的例子。
定理遵循因为*是(交换和)关联,并且1 *μ=ε,其中ε是Dirichlet卷积的同一性函数,对于所有n> 1,取值ε(1)= 1,ε(n)= 0 因此:
系列关系
我们使:
因此得到:
这个式子是它的转变。 这些变换是通过系列方式进行的,兰伯特系列:
和Dirichlet系列:
其中ζ(s)是Riemann zeta函数。
重复转换
给定算术函数,可以通过重复应用第一个求和来生成其他算术函数的双无限序列。
例如,如果从欧拉的常数函数开始,并重复应用变换过程,则得到:
1.φ的常数函数
2.φ* 1 = I,其中I(n)= n是识别函数
3.I * 1 =σ1=σ,除数函数
如果起始功能是Möbius功能本身,功能列表是:
1.μ,Möbius函数
2.μ* 1 =ε其中,
是单位功能。
3.ε* 1 = 1,常数函数
4.1 * 1 =σ0= d =τ,其中d =τ是n的除数,(见除数函数)。
这两个功能列表在两个方向都无限延伸。 Möbius反演公式使得这些列表能够向后
遍历。
作为一个例子,从φ开始的序列是:
通过考虑相应的Dirichlet系列可以更容易地理解生成的序列:变换的每个重复应用对应于Riemann zeta函数的乘法。
推广
在组合中更有用的相关反演公式如下:假设F(x)和G(x)是在区间[1,∞)上定义的复值函数,使得:
那么:
这里的总和扩展到小于或等于x的所有正整数n。
这反过来又是一个更一般形式的特殊情况。 如果α(n)是具有Dirichlet反的算术函数,则如果定义:
那么:
前一个公式出现在
常数函数α(n)= 1的特殊情况下,其Dirichlet逆为=μ'(n)。
如果我们在正整数上定义(复值)函数f(n)和g(n),则会出现这些扩展中的第一个的特定应用,
通过定义F(x)= f(⌊x⌋)和G(x)= g(⌊x⌋),我们推导出:
使用此公式的一个简单示例是计算减少比例0 <<1,其中a和b是互质的,b≤n。 如果我们令f(n)为这个数字,则g(n)是分数0<<1的总数,其中b≤n,其中a和b不一定是互质的。(这是因为每个分数满足gcd(a,b)= d和b≤n,并且可以减少到分数,其中,反之亦然)。这里可以直接确定g(n)=,但是f(n)更难计算。
另一个反演公式是(我们假设所涉及的系列是绝对收敛的):
如上所述,这概括为α(n)是具有Dirichlet反α-1(n)的算术函数:
乘法符号
由于Möbius反演适用于任何阿贝尔组,所以组操作是作为加法还是作为乘法来表示没有区别。 这产生了以下反演公式的符号变体:
概括证明
第一个概括可以证明如下。 我们使用Iverson的约定,[condition]是条件的指标函数,如果条件为真,则为1,如果为false则为1。我们使用的结果,
即1 *μ= i。我们可以进行一下证明:
在α(n)代替1的更一般情况下的证明基本上是相同的,如第二次
泛化。