Dirichlet卷积与Mobius变换

2021-12-27 10:06 作者:子瞻Louis 0人读过 | 我要投稿

在数学中，经常会遇到实数序列或是复数序列，如 $n%EF%BC%81$ ， $%5Ccos%20n$ 等

而在数论中，它们有另一个特殊的名字，即数论函数

我们先给出以下几个定义：

以正整数集为定义域的实值函数或复值函数称为数论函数，又叫算术函数
具有一下性质的数论函数f(n)称为积性函数：

若gcd(a,b)=1（即a，b的最大公约数是1）,则f(ab)=f(a)f(b)
若对于任意两个正整数都有上式成立，则f(n)称为完全积性函数

由定义不难得出：若f(n)为积性函数，则

$f(a)%3Df(a%5Ccdot%201)%3Df(a)f(1)%5CRightarrow%20f(1)%3D1$

设

$%5Cmu%20(n)%20%3D%20%5Cleft%5C%7B%20%5Cbegin%7Barray%7D%7Brcl%7D%0A1%2C%20%26%20%20n%3D1%20%5C%5C%20(-1)%5E%7Br%7D%2C%20%26%20n%E6%98%AFr%E4%B8%AA%E4%B8%8D%E5%90%8C%E7%B4%A0%E6%95%B0%E4%B9%8B%E7%A7%AF%20%5C%5C%0A0%2C%20%26%20%E5%85%B6%E4%BB%96%E6%83%85%E5%86%B5%0A%5Cend%7Barray%7D%5Cright.$

即当且仅当n的素因子分解中有素数的大于二次乘方时 $%5Cmu%20(n)%3D0$

不难发现 $%5Cmu(n)$ 是积性函数但非完全积性函数，易得

$%5Cmu%20(1)%3D1%2C%5Cmu(2)%3D-1%2C%5Cmu%20(3)%3D-1%2C%5Cmu(4)%20%3D0%2C%5Cmu%20(5)%20%3D-1%2C$

$%20%5Cmu%20(6)%20%3D1%2C%5Cmu(7)%3D-1%2C%5Cmu(8)%3D0%2C%5Cmu(9)%3D0%2C%5Cmu(10)%3D1%2C%E2%80%A6$

Mobius函数是数论中经常会出现的函数，它有许多有用的性质

Dirichlet卷积

我们来看下面这一和式

$f(n)%3D%5Csum_%7Bd%5Cvert%20n%7Dg(d)h%5Cleft(%5Cfrac%7Bn%7D%7Bd%7D%5Cright)$

式中 $%5Csum_%7Bd%5Cvert%20n%7D$ 遍历所有整除n的d（n的所有约数），g(n),h(n)都是非零积性函数

假设 $%5Cgcd(a%2Cb)%3D1$ ，则

$f(ab)%3D%5Csum_%7Bd%5Cvert%20ab%7Dg(d)h%5Cleft(%5Cfrac%7Bab%7D%7Bd%7D%5Cright)$

令 $%5Cgcd(a%2Cd)%3Du%2C%5Cgcd(b%2Cd)%3Dv$ ，则 $uv%3Dd$ ，于是

$%5Cbegin%7Baligned%7Df(ab)%26%3D%5Csum_%7Bu%5Cvert%20a%7D%5Csum_%7Bv%5Cvert%20b%7Dg(uv)h%5Cleft(%5Cfrac%7Bab%7D%7Buv%7D%5Cright)%5C%5C%26%3D%5Csum_%7Bu%5Cvert%20a%7Dg(u)h%5Cleft(%5Cfrac%7Ba%7D%7Bu%7D%5Cright)%5Csum_%7Bv%5Cvert%20b%7Dg(v)h%5Cleft(%5Cfrac%7Bb%7D%7Bv%7D%5Cright)%5C%5C%26%3Df(a)f(b)%5Cend%7Baligned%7D$

即得知了 $f(n)$ 也是一积性函数

要注意两个完全积性函数的Dirichlet卷积不一定是完全积性函数

称 $f(n)$ 为 $g(n)$ 与 $h(n)$ 的Dirichlet卷积，记为 $f(n)%3Dg*h(n)$ ，同数学分析中的卷积，它具有交换律与结合律：

首先，交换律显然成立，下面证明结合律

若 $f(n)%2Cg(n)%2Ch(n)$ 为积性函数，为了证明结合律，可以悄悄地对Dirichlet卷积重新定义

$f*g(n)%3D%5Csum_%7Bn%3Dab%7Df(a)g(b)$

其中 $%5Csum_%7Bn%3Dab%7D$ 表实将n分解为两个正整数的积后求和

容易验证它与原先的定义是等价的，于是

$%5Cbegin%7Baligned%7D(f*g)(n)*h(n)%26%3D%5Csum_%7Bn%3Dab%7D(f*g)(a)h(b)%5C%5C%26%3D%5Csum_%7Bn%3Dab%7D%5Cleft(%5Csum_%7Ba%3Dcd%7Df(c)g(d)%5Cright)h(b)%5C%5C%26%3D%5Csum_%7Bn%3Dbcd%7Df(c)g(d)h(b)%5Cend%7Baligned%7D$

同理可得

$f(n)*(g*h)(n)%3D%5Csum_%7Bn%3Dabc%7Df(a)g(b)h(c)$

$%5CRightarrow%20(f*g)(n)*h(n)%3Df(n)*(g*h)(n)$

取 $g(n)%3D%5Cmu(n)f(n)%2Ch(n)%3D1$ ，其中，f(n)是一非零积性函数，因此，

$g*h(n)%3D%5Csum_%7Bd%5Cvert%20n%7D%5Cmu%20(d)f(n)$

也是一积性函数

有n的素因子分解 $n%3Dp_%7B1%7D%5E%7Ba_%7B1%7D%7Dp_%7B2%7D%5E%7Ba_%7B2%7D%7D%E2%80%A6p_%7Bt%7D%5E%7Ba_%7Bt%7D%7D$ ，我们只需讨论n的约数中无平方素因子的情况

因 $f(n)$ 积性，

$%5Cbegin%7Baligned%7Dg*h(n)%26%3D1-(f(p_%7B1%7D)%2B%E2%80%A6%2Bf(p_%7Bt%7D))%2B%5Cleft(f(p_%7B1%7Dp_%7B2%7D)%2Bf(p_%7B1%7Dp_%7B3%7D)%2B%E2%80%A6%2Bf(p_%7Bt-1%7Dp_%7Bt%7D)%5Cright)-%E2%80%A6%5C%5C%26%2B(-1)%5Etf(p_1%E2%80%A6p_t)%5C%5C%26%3D%5Cprod_%7Bp%5Cvert%20n%7D(1-f(p))%5Cend%7Baligned%7D$

其中 $%5Cprod_%7Bp%5Cvert%20n%7D%20$ 遍历n的全部素因子 ■

若在上式中取 $f(n)%3D1$ ，则可得到

$%5Csum_%7Bd%5Cvert%20n%7D%5Cmu(d)%3D%5Cleft%5B%5Cfrac%7B1%7D%7Bn%7D%5Cright%5D%3D%20%5Cleft%5C%7B%20%5Cbegin%7Barray%7D%7Brcl%7D%0A1%2C%20%26%20%20n%3D1%20%5C%5C%200%2C%20%26%20n%E2%89%A01%20%5Cend%7Barray%7D%5Cright.$

再来看一个例子，令 $1(n)%5Cequiv%201$ ，

$%5Ctilde%20%7B1%7D(n)%3D%5Csum_%7Bd%5Cvert%20n%7D1%3Dd(n)$

d(n)为除数函数即n的所有约数的个数

若令 $E_%7Ba%7D(n)%3Dn%5E%7Ba%7D$

我们还可以得到

$%5Ctilde%7BE_%7Ba%7D%7D(n)%3D%5Csum_%7Bd%5Cvert%20n%7Dn%5E%7Ba%7D%3D%5Csigma_%7Ba%7D(n)%20$

取a=0即为上式

我们已经讨论过下式

$%5Ctilde%20%5Cmu%20(n)%3D%5Cleft%5B%5Cfrac%7B1%7D%7Bn%7D%5Cright%5D%3D%5Cleft%5C%7B%20%5Cbegin%7Barray%7D%7Brcl%7D%0A1%20%26%20n%3D1%20%5C%5C%200%20%26%20n%E2%89%A01%20%5C%5C%0A%5Cend%7Barray%7D%5Cright.$

称他为单位示性函数，记为 $%5Cvarepsilon%20(n)%3D%5Ctilde%20%5Cmu%20(n)$

对任意数论函数，皆有

$f*%5Cvarepsilon(n)%3D%5Cvarepsilon*f(n)%3Df(n)$

Mobius反演

若 $f(n)$ 为一数论函数，定义

$g(n)%3D%5Csum_%7Bd%5Cvert%20n%7Df(d)$

那么有

$f(n)%3D%5Csum_%7Bd%5Cvert%20n%7D%5Cmu(d)g%5Cleft(%5Cfrac%7Bn%7D%7Bd%7D%5Cright)$

该关系可以由Dirichlet卷积表示出， $f(n)%3Dg*%5Cmu(n)$ ，我们不妨来推导一下

证明：只需证明 $g(n)%3Df*1(n)%5CRightarrow%20f(n)%3Dg*%5Cmu%20(n)$

我们在 $g(n)%3Df*1(n)$ 的两边同时卷积一个Mobius函数

$%5Cbegin%7Baligned%7Dg*%5Cmu(n)%26%3D((f*1)*%5Cmu%20)(n)%5C%5C%26%3D(f*(%5Cmu*1))(n)%5C%5C%26%3Df*%5Cvarepsilon(n)%5C%5C%26%3Df(n)%5Cend%7Baligned%7D$

■

下面来看一个有趣的性质：

若 $%5Calpha(n)$ 是完全积性函数，则

$%5Calpha%5E%7B-1%7D(n)%3D%5Cmu(n)%5Calpha(n)$

证明：因为它是完全积性的， $%5Calpha(1)%3D1$

$%5Cbegin%7Baligned%7D(%5Cmu%20%5Calpha)*%5Calpha(n)%26%3D%5Csum_%7Bd%5Cvert%20n%7D%5Cmu(d)%5Calpha(d)%5Calpha%5Cleft(%5Cfrac%7Bn%7D%7Bd%7D%5Cright)%5C%5C%26%3D%5Csum_%7Bd%5Cvert%20n%7D%5Cmu(d)%5Calpha%5Cleft(d%5Ccdot%20%5Cfrac%7Bn%7D%7Bd%7D%5Cright)%5C%5C%26%3D%5Calpha(n)%5Csum_%7Bd%5Cvert%20n%7D%5Cmu(n)%5C%5C%26%3D%5Cvarepsilon(n)%5Calpha(n)%3D%5Cvarepsilon(n)%5Cend%7Baligned%7D$

最后在两边卷积一个 $%5Calpha%5E%7B-1%7D(n)$ ，得

$(%5Cmu%20%5Calpha)*(%5Calpha*%5Calpha%5E%7B-1%7D)(n)%3D%5Cmu(n)%5Calpha(n)%3D%5Calpha%5E%7B-1%7D(n)$

■

接下来我们就要来构造一个群了

我们已知Dirichlet卷积与所有数论函数构成一个半群

又易知 $%5Cvarepsilon%20(n)$ 为群中的单位元，因此上述半群其实是一个幺半群

因此，若我们能得出

$%5Cforall%20f(1)%E2%89%A00%2C%5Cexists%20g(n)%2C%5Ctext%7Bsuch%20that%7D%20f*g(n)%3D%5Cvarepsilon(n)$

则现在就能说所有满足 $f(1)%E2%89%A00$ 的数论函数的集合 $D$ 关于Dirichlet卷积构成一个群，我称它为Dirichlet群

证明：之所以要求 $f(1)%E2%89%A00$ 是因为n=1时

$f*g(1)%3Df(1)g(1)%3D%5Cvarepsilon(1)%3D1%5CRightarrow%20g(1)%3D%5Cfrac%7B1%7D%7Bf(1)%7D$

下面我们讨论n＞1的情况，有 $%5Cvarepsilon(n)%3D0$ ，又

$%5Cbegin%7Baligned%7D%5Cvarepsilon(n)%26%3Df*g(n)%5C%5C%26%3D%5Csum_%7Bd%5Cvert%20n%7Df(d)g%5Cleft(%5Cfrac%7Bn%7D%7Bd%7D%5Cright)%5C%5C%26%3D%5Csum_%7Bd%5Cvert%20n%20%5C%5C%20d%E2%89%A01%7Df(d)g%5Cleft(%5Cfrac%7Bn%7D%7Bd%7D%5Cright)%2Bf(1)g(n)%5Cend%7Baligned%7D$

所以

$g(n)%3D-%5Cfrac%7B1%7D%7Bf(1)%7D%5Csum_%7Bd%5Cvert%20n%20%5C%5C%20d%E2%89%A01%7Df(d)g%5Cleft(%5Cfrac%7Bn%7D%7Bd%7D%5Cright)$

称 $g(n)$ 为 $f(n)$ 的Dirichlet逆，记为 $f%5E%7B-1%7D(n)$ ■

从中也可得知当 $f(1)%3D0$ 时 $f(n)$ 不可逆

事实上有的地方为了区别于反函数一般不会这样记，但我为了方便（偷懒）就这样记了

广义Mobius反演

上诉的Dirichlet卷积和Mobius反演仅限于数论函数，我们不妨将其扩展一下

首先我们来看下面这个映射：
$A$ 是所以在 $%5B1%2C%2B%5Cinfty)$ 有定义的实值函数（或复值函数）构成的集合， $D$ 是Dirichlet群

定义：

$%5Cbegin%7Baligned%7D%5Ccirc%20%3AD%5Ctimes%20A%26%5Crightarrow%20A%20%5C%5C%20%5Ccirc%20%3A(%5Calpha%2CF(x))%26%5Crightarrow%20%5Csum_%7B1%5Cleq%20n%5Cleq%20x%7D%5Calpha(n)F%5Cleft(%5Cfrac%7Bx%7D%7Bn%7D%5Cright)%5Cend%7Baligned%7D$

$%5Calpha%20%5Ccirc%20F(x)%3A%3D%5Ccirc(%5Calpha%2CF(x))$ ，若无特殊说明 $%5Csum_%7Bn%5Cleq%20x%7D$ 表示 $%5Csum_%7B1%5Cleq%20n%5Cleq%20x%7D$

由定义不难得到，

$%5Cvarepsilon%5Ccirc%20F(x)%3DF(x)$

同时，结合律对该映射成立：

证明：设 $%5Calpha%2C%5Cbeta%5Cin%20D%2CF%5Cin%20A$ ，

$%5Cbegin%7Baligned%7D%5Calpha%5Ccirc(%5Cbeta%5Ccirc%20F)(x)%26%3D%5Csum_%7Bn%5Cleq%20x%7D%5Calpha(n)%5Csum_%7Bm%5Cleq%5Cfrac%7Bx%7D%7Bn%7D%7D%5Cbeta(m)F%5Cleft(%5Cfrac%7Bx%7D%7Bmn%7D%5Cright)%5C%5C%26%3D%5Csum_%7Bmn%5Cleq%20x%7D%5Calpha(n)%5Cbeta(m)F%5Cleft(%5Cfrac%7Bx%7D%7Bmn%7D%5Cright)%5Cend%7Baligned%7D$

做代换mn=k，则

$%5Calpha%5Ccirc(%5Cbeta%5Ccirc%20F)(x)%3D%5Csum_%7Bk%5Cleq%20x%7D%5Cleft(%5Csum_%7Bk%3Dmn%7D%5Calpha(n)%5Cbeta(m)%5Cright)F%5Cleft(%5Cfrac%7Bx%7D%7Bk%7D%5Cright)%3D(%5Calpha*%5Cbeta)%5Ccirc%20F(x)$

$%5CRightarrow%5Ccirc(%5Calpha%2C%5Ccirc(%5Cbeta%2CF))%3D%5Ccirc(%5Calpha*%5Cbeta%2CF)$

■

则该映射是 $D$ 在 $A$ 上的群作用

广义Mobius反演

若 $G(x)%3D%5Calpha%5Ccirc%20F(x)$ ，则

$F(x)%3D%5Calpha%5E%7B-1%7D%5Ccirc%20G(x)$

证明：由结合性质可得

$%5Calpha%5E%7B-1%7D%5Ccirc(%5Calpha%5Ccirc%20F)(x)%3D(%5Calpha*%5Calpha%5E%7B-1%7D)%5Ccirc%20F(x)%3DF(x)$

$%5CRightarrow%20F(x)%3D%5Calpha%5E%7B-1%7D%5Ccirc%20G(x)$

■

即得到了广义反演公式：

$G(x)%3D%5Csum_%7Bn%5Cleq%20x%7D%5Calpha(n)F%5Cleft(%5Cfrac%7Bx%7D%7Bn%7D%5Cright)%5CRightarrow%20F(x)%3D%5Csum_%7Bn%5Cleq%20x%7D%5Calpha%5E%7B-1%7D(n)G%5Cleft(%5Cfrac%7Bx%7D%7Bn%7D%5Cright)$

特别的，若 $%5Calpha(n)$ 是完全积性的，则

$G(x)%3D%5Csum_%7Bn%5Cleq%20x%7D%5Calpha(n)F%5Cleft(%5Cfrac%7Bx%7D%7Bn%7D%5Cright)%5CRightarrow%20F(x)%3D%5Csum_%7Bn%5Cleq%20x%7D%5Cmu(n)%5Calpha(n)G%5Cleft(%5Cfrac%20xn%5Cright)$

◀只需证明在此情况下 $%5Calpha%5E%7B-1%7D(n)%3D%5Cmu(n)%5Calpha(n)$ ，而前面我们已经证明过它了■

标签：

Dirichlet卷积与Mobius变换

Dirichlet卷积

Mobius反演

广义Mobius反演