M?bius(莫比烏斯函數(shù))的推廣形式

2022-10-04 19:58 作者:加餐勺 0人讀過 | 我要投稿

以下內(nèi)容以及演繹思路參考自李文威的《代數(shù)學(xué)方法》卷1第5章

初識自然數(shù)上關(guān)于"|(整除)"關(guān)系的莫比烏斯反演時總覺得不夠自然，看完此章后終意平。

（note：閱讀需要有一點點的抽象代數(shù)基礎(chǔ)（大概？

首先給出偏序集的定義：

偏序集? $(P%2C%5Cleq%20)$ ?,P是一個集合， $%5Cleq$ 是一個二元關(guān)系，滿足：

反身性：

$%5Cforall%20x%20%5Cin%20P%2C%20x%20%5Cleq%20x$

傳遞性：

$x%20%5Cleq%20y%2Cy%5Cleq%20z%20%5Cimplies%20x%5Cleq%20z$

反稱性：

$x%5Cleq%20y%20%2C%20y%5Cleq%20x%20%5Cimplies%20x%3Dy$

若? $(P%2C%5Cleq%20)$ 是一個偏序集，且? $%5Cforall%20(x%2Cy)%5Cin%20P%5E2%20%2Cx%20%5Cleq%20y$ ，有：

$%5Bx%2Cy%5D%3D%5C%7Bz%20%5Cin%20P%7Cx%5Cleq%20z%5Cleq%20y%20%5C%7D$ 為有限集

那么稱該偏序集為一個局部有限偏序集。

我們在一個局部有限偏序集上 $(P%2C%5Cleq%20)$ ?構(gòu)造環(huán)結(jié)構(gòu)如下：

映射

$f%3AP%5E2%20%5Crightarrow%20Q%2Cf(x%2Cy)%5Cin%20Q%EF%BC%8Cx%20%5Cleq%20y$ ? ，其中Q為我們熟知的有理數(shù)域

所有的 $f$ 組成一個集合 $I(P%2C%5Cleq)$ ，在其上定義加法運算"+"與乘法運算" $%5Ccirc%20$ "

$(f%2Bg)(x%2Cy)%3Df(x%2Cy)%2Bg(x%2Cy)$

$(f%5Ccirc%20g)(x%2Cy)%3D%5Csum_%7Bz%20%5Cin%20%5Bx%2Cy%5D%7Df(x%2Cz)*g(z%2Cy)$

顯然 $I(P%2C%5Cleq)$ 中關(guān)于加法是封閉的結(jié)合的，交換的，零元為

$0(x%2Cy)%3D0%20%5Cin%20Q%2C%20%5Cforall%20(x%2Cy)%5Cin%20P%5E2$

$f$ ?的加法逆元為 $f'(x%2Cy)%3D-f(x%2Cy)%2C%5Cforall%20(x%2Cy)%5Cin%20P%5E2$

所以 $(I(P%2C%5Cleq)%2C%2B)$ 為交換群；

關(guān)于 $%5Ccirc$ ，封閉是顯然的，下證結(jié)合律：

$%5Cforall%20h%2Cf%2Cg%20%5Cin%20I(P%2C%5Cleq)%EF%BC%8Cx%2Cy%5Cin%20P%2Cx%5Cleq%20y%EF%BC%9A$

$(hf)g(x%2Cy)%3D%5Csum_%7Bz%20%5Cin%20%5Bx%2Cy%5D%7D(hf)(x%2Cz)*g(z%2Cy)%0A%3D%5Csum_%7Bz%20%5Cin%20%5Bx%2Cy%5D%7D(%5Csum_%7Bt%5Cin%20%5Bx%2Cz%5D%7Dh(x%2Ct)f(t%2Cz))*g(z%2Cy)$

$%3D%5Csum_%7Bx%5Cleq%20t%5Cleq%20z%20%5Cleq%20y%7Dh(x%2Ct)f(t%2Cz)g(z%2Cy)%3D%5Csum_%7Bt%5Cin%20%5Bx%2Cy%5D%7Dh(x%2Ct)(%5Csum_%7Bz%5Cin%20%5Bt%2Cy%5D%7Df(t%2Cz)g(z%2Cy))$

$%3D%5Csum_%7Bt%5Cin%20%5Bx%2Cy%5D%7Dh(x%2Ct)(fg)(t%2Cy)%3Dh(fg)(x%2Cy)%0A$

（note：局部有限性使得上述等式的成立

我們再定義

$%5Cdelta%20(x%2Cy)%3D0%2Cif%20%5C%3B%20x%20%5Cneq%20y%3B%5Cdelta%20(x%2Cy)%3D1%2Cif%20%5C%3B%20x%20%3D%20y$

容易驗證此 $%5Cdelta%20(x%2Cy)%E4%B8%BAI(P%2C%5Cleq)$ 中的乘法單位元。

綜上 $R%3D(I(P%2C%5Cleq)%2C%2B%2C%5Ccirc)$ 為幺環(huán)。

$%5Cforall%20f%20%5Cin%20R$

首先給出3個等價的性質(zhì)：

$f$ 有左逆元 $%253D%255Csum_%257Bt%255Cin%2520%255Bx%252Cy%255D%257Dh(x%252Ct)(fg)(t%252Cy)%250A$
$%5Cforall%20x%20%5Cin%20P%2Cf(x%2Cx)%20%5Cneq%200$
$f$ 有右逆元

proof:

定義:

$g(x%2Cx)%3D%5Cfrac%7B1%7D%7Bf(x%2Cx)%7D$

$g(x%2Cy)f(y%2Cy)%3D-%5Csum_%7Bx%5Cleq%20z%3Cy%7Dg(x%2Cz)f(z%2Cy)$

當(dāng)（2.）成立時對任意 $f$ 唯一的確定了 $g$

顯然 $g%5Ccirc%20f%20%3D%5Cdelta$ ?，由逆元的唯一性(1.) $%5Ccong%20$ (2.)

右逆元形式可類似構(gòu)造，并且易知左逆元就是右逆元。

現(xiàn)在在 $R$ 上考慮元素 $%5Cvarsigma%20$ ：

$%5Czeta%20(x%2Cy)%3D1%2C%5Cforall%20x%20%5Cleq%20y%2C(x%2Cy)%20%5Cin%20P%5E2$

顯然 $%5Czeta%20%5Cin%20R$

終于，我們可以定義莫比烏斯(M?bius)函數(shù)了：

$def%20%5C%3B%20%5Cmu%20%3D%5Cmu%20_p%20%5Cin%20R%3A%0A%5Cmu%20%3D%5Czeta%5E%7B-1%7D%20%0A$

當(dāng)然的根據(jù)定義有：

$%5Csum_%7Bz%5Cin%20%5Bx%2Cy%5D%7D%5Cmu(x%2Cz)%3D%5Csum_%7Bz%5Cin%20%5Bx%2Cy%5D%7D%5Cmu(z%2Cy)%3D%5Cdelta(x%2Cy)$

現(xiàn)在我們來回顧莫比烏斯反演：

設(shè) $(A%2C%2B)$ 為任意交換群， $(P%2C%5Cleq)$ 為偏序集滿足：

$%5Cforall%20x%20%5Cin%20P%2C%5C%7By%5Cin%20P%7Cy%5Cleq%20x%5C%7D$ 為有限集，

顯見 $(P%2C%5Cleq)$ 為局部有限偏序集。

給出函數(shù) $f%2Cg%3AP%5Crightarrow%20A$ ，則

$f(x)%3D%5Csum_%7By%20%5Cleq%20x%7Dg(y)%5Ciff%20g(x)%3D%5Csum_%7By%5Cleq%20x%7Df(y)%5Cmu(y%2Cx).$

(note:這里 $%5Cmu%20f$ 可以視作 $Q$ 在 $A$ 上的群作用，或者將 $A$ 看作 $Q$ 上的向量空間）

證明方法與經(jīng)典情形類似，僅證左推右：

$%5Csum_%7By%5Cleq%20x%7Df(y)%5Cmu(y%2Cx)%3D%5Csum_%7Bz%5Cleq%20y%5Cleq%20x%7Dg(z)%5Cmu(y%2Cx)%3D%5Csum_%7Bz%5Cleq%20x%7D(%5Csum_%7By%5Cin%20%5Bz%2Cx%5D%7D%5Cmu(y%2Cx))g(z)$

$%3D%5Csum_%7Bz%5Cleq%20x%7D%5Cdelta(z%2Cx)g(z)%3Dg(x)$

根據(jù)交換群 $A$ 上的運算可以寫成乘積形式或者是和式，它們的本質(zhì)沒有區(qū)別。

此即為推廣形式的莫比烏斯反演，現(xiàn)在我們希望用它來得到 $Z_%7B%5Cgeq%201%7D%3D%5C%7Bn%5Cin%20Z%7Cn%5Cgeq%201%5C%7D$ 上的經(jīng)典情形的莫比烏斯反演。

首先引入直積形式：

考慮一族局部有限偏序集 $%5C%7B(P_i%2C%5Cleq_i)%5C%7D_%7Bi%3D1%7D%5En$

令 $P%3D%5Cprod_%7Bi%3D1%7D%5En%20P_i%2Cx%3D(x_1%2C...%2Cx_n)%5Cin%20P%2C%5Cforall%20i%20%2Cx_i%5Cin%20P_i$

$x%5Cleq%20y%5Ciff%20%20%5Cforall%20i%2Cx_i%5Cleq_i%20y_i$

顯見 $(P%2C%5Cleq)$ 為局部有限偏序集

簡記 $x%3D(x_i)_i$

在 $P$ 上定義 $%5Cmu(x%2Cy)%3D%5Cprod_%7Bi%3D1%7D%5En%5Cmu_%7BP_i%7D(x_i%2Cy_i)$

易見

$%5Csum_%7Bz%5Cin%20%5Bx%2Cy%5D%7D%3D%5Csum_%7Bz_1%20%5Cin%20%5Bx_1%2Cy_1%5D%7D...%5Csum_%7Bz_n%20%5Cin%20%5Bx_n%2Cy_n%5D%7D$

這個 $%5Cmu(x%2Cy)$ 確實為前述定義的莫比烏斯函數(shù)。

現(xiàn)在分別在 $(Z_%7B%5Cgeq0%7D%2C%5Cleq)$ 與 $(Z_%7B%5Cgeq1%7D%2C%7C)$ 上考慮：

大于0的所有整數(shù)關(guān)于數(shù)的小于等于關(guān)系當(dāng)然構(gòu)成局部有限偏序集，而大于等于1的整數(shù)關(guān)于數(shù)的整除關(guān)系也構(gòu)成局部偏序集。

在 $(Z_%7B%5Cgeq0%7D%2C%5Cleq)$ 上考慮 $%5Cmu(n%2Cm)%3D1%2Cif%5C%3Bn%3Dm%20%5C%5C%0A%5Cmu(n%2Cm)%3D-1%2Cif%5C%3Bn-m%3D-1%20%5C%5C%0A%5Cmu(n%2Cm)%3D0%2C%E5%85%B6%E4%BB%96$

那么易證 $%5Cmu%E4%B8%BA(Z_%7B%5Cgeq0%7D%2C%5Cleq)$ 導(dǎo)出的莫比烏斯函數(shù)。

現(xiàn)在來構(gòu)造一個 $%5Cprod_%7Bp%7D(Z_%7B%5Cge0%7D%2C%5Cle)%5Crightarrow%20(Z_%7B%5Cge1%7D%2C%7C)$ 的雙射

任意一個大于0的整數(shù)n有唯一的有限的素因子分解

$n%3D%5Cprod_p%20p%5E%7Bn_p%7D$ ，那么 $(n_p)_p%5Crightarrow%20%5Cprod_p%20p%5E%7Bn_p%7D$ 為雙射

（note：若要嚴(yán)謹?shù)谋硎鲞@個雙射以避免有限與可列的混淆，其實要構(gòu)造一個幾乎處處收斂于該積偏序的偏序，但引入測度等概念過于麻煩，即使不引入也不影響對該雙射的理解）

該映射將 $%5Cprod_%7Bp%7D(Z_%7B%5Cge0%7D%2C%5Cle)$ 上的莫比烏斯函數(shù)映射至熟知的情形：

$%5Cmu((n_p)_p%2C(m_p)_p)%3D%5Cprod_p%20%5Cmu_%7B(Z_%7B%5Cge0%7D%2C%5Cle)%7D(n_p%2Cm_p)$

考慮 $n%3D%5Cprod_p%20p%5E%7Bn_p%7D$ 與 $m%3D%5Cprod_p%20p%5E%7Bm_p%7D$ 在同一個素因子 $p$ 上的冪， $m_p%3Dn_p$ 時該處的莫比烏斯函數(shù)返回1，冪次相差1且 $m_p%3En_p$ 時該處的莫比烏斯函數(shù)返回-1，其他情形返回0，有一個0則整個 $%5Cprod_p%20%5Cmu_%7B(Z_%7B%5Cge0%7D%2C%5Cle)%7D(n_p%2Cm_p)%3D0$ ，這相當(dāng)于是說，n不整除m時，以及 $%5Cfrac%7Bm%7D%7Bn%7D$ 有平方素因子時 $%5Cmu((n_p)_p%2C(m_p)_p)%3D0$ .

這其實就是我們熟知的莫比烏斯函數(shù)，我們直接給出它在 $(Z_%7B%5Cge1%7D%2C%7C)$ 上的形式：

記 $%5Cmu(1%2Cn)%3D%5Cmu(n)%2C%E9%82%A3%E4%B9%88%5Cmu(d%2Cn)%3D%5Cmu(n%2Fd)$

$%5Cmu(n)%3D(-1)%5E%7Bn%E7%9A%84%E7%B4%A0%E5%9B%A0%E5%AD%90%E4%B8%AA%E6%95%B0%7D%2Cif%5C%3Bn%E6%97%A0%E4%B8%8D%E7%AD%89%E4%BA%8E1%E7%9A%84%E5%B9%B3%E6%96%B9%E5%9B%A0%E5%AD%90%5C%5C%0A%5Cmu(n)%3D0%2C%E5%85%B6%E4%BB%96$