Dirichlet卷積與Mobius變換

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

在數(shù)學(xué)中，經(jīng)常會遇到實(shí)數(shù)序列或是復(fù)數(shù)序列，如 $n%EF%BC%81$ ， $%5Ccos%20n$ 等

而在數(shù)論中，它們有另一個特殊的名字，即數(shù)論函數(shù)

我們先給出以下幾個定義：

以正整數(shù)集為定義域的實(shí)值函數(shù)或復(fù)值函數(shù)稱為數(shù)論函數(shù)，又叫算術(shù)函數(shù)
具有一下性質(zhì)的數(shù)論函數(shù)f(n)稱為積性函數(shù)：

若gcd(a,b)=1（即a，b的最大公約數(shù)是1）,則f(ab)=f(a)f(b)
若對于任意兩個正整數(shù)都有上式成立，則f(n)稱為完全積性函數(shù)

由定義不難得出：若f(n)為積性函數(shù)，則

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

設(shè)

$%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.$

即當(dāng)且僅當(dāng)n的素因子分解中有素數(shù)的大于二次乘方時 $%5Cmu%20(n)%3D0$

不難發(fā)現(xiàn) $%5Cmu(n)$ 是積性函數(shù)但非完全積性函數(shù)，易得

$%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函數(shù)是數(shù)論中經(jīng)常會出現(xiàn)的函數(shù)，它有許多有用的性質(zhì)

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的所有約數(shù)），g(n),h(n)都是非零積性函數(shù)

假設(shè) $%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)$ 也是一積性函數(shù)?

要注意兩個完全積性函數(shù)的Dirichlet卷積不一定是完全積性函數(shù)

稱 $f(n)$ 為 $g(n)$ 與 $h(n)$ 的Dirichlet卷積，記為 $f(n)%3Dg*h(n)$ ，同數(shù)學(xué)分析中的卷積，它具有交換律與結(jié)合律：

首先，交換律顯然成立，下面證明結(jié)合律

若 $f(n)%2Cg(n)%2Ch(n)$ 為積性函數(shù)，為了證明結(jié)合律，可以悄悄地對Dirichlet卷積重新定義

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

其中 $%5Csum_%7Bn%3Dab%7D$ 表實(shí)將n分解為兩個正整數(shù)的積后求和

容易驗(yà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)是一非零積性函數(shù)，因此，

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

也是一積性函數(shù)

有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的約數(shù)中無平方素因子的情況

因 $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)為除數(shù)函數(shù)即n的所有約數(shù)的個數(shù)

若令 $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即為上式?

我們已經(jīng)討論過下式

$%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.$

?稱他為單位示性函數(shù)，記為 $%5Cvarepsilon%20(n)%3D%5Ctilde%20%5Cmu%20(n)$

對任意數(shù)論函數(shù)，皆有

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

Mobius反演

若 $f(n)$ 為一數(shù)論函數(shù)，定義?

$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)$

該關(guān)系可以由Dirichlet卷積表示出， $f(n)%3Dg*%5Cmu(n)$ ，我們不妨來推導(dǎo)一下

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

我們在 $g(n)%3Df*1(n)$ 的兩邊同時卷積一個Mobius函數(shù)

$%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$

■

下面來看一個有趣的性質(zhì)：

若 $%5Calpha(n)$ 是完全積性函數(shù)，則

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

證明：因?yàn)樗峭耆e性的， $%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)$

■

接下來我們就要來構(gòu)造一個群了

我們已知Dirichlet卷積與所有數(shù)論函數(shù)構(gòu)成一個半群

又易知 $%5Cvarepsilon%20(n)$ 為群中的單位元，因此上述半群其實(shí)是一個幺半群

因此，若我們能得出

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

則現(xiàn)在就能說所有滿足? $f(1)%E2%89%A00$ ?的數(shù)論函數(shù)的集合? $D$ ?關(guān)于Dirichlet卷積構(gòu)成一個群，我稱它為Dirichlet群

證明：之所以要求 $f(1)%E2%89%A00$ 是因?yà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)$ ■

從中也可得知當(dāng)? $f(1)%3D0$ ?時? $f(n)$ ?不可逆

事實(shí)上有的地方為了區(qū)別于反函數(shù)一般不會這樣記，但我為了方便（偷懶）就這樣記了

廣義Mobius反演

上訴的Dirichlet卷積和Mobius反演僅限于數(shù)論函數(shù)，我們不妨將其擴(kuò)展一下

首先我們來看下面這個映射：
$A$ 是所以在 $%5B1%2C%2B%5Cinfty)$ 有定義的實(shí)值函數(shù)（或復(fù)值函數(shù)）構(gòu)成的集合， $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)$

同時，結(jié)合律對該映射成立：

證明：設(shè) $%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)$

證明：由結(jié)合性質(zhì)可得

$%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)$ ?，而前面我們已經(jīng)證明過它了■

標(biāo)簽：

最美情侣中文字幕电影,在线麻豆精品传媒,在线网站高清黄,久久黄色视频

Dirichlet卷積與Mobius變換

Dirichlet卷積

Mobius反演

廣義Mobius反演