動機
因數和把一個整數及其所有因數的資訊混合在一起。例如,統計分母整除 的分數,所得的總數涉及每個 所對應的 。莫比烏斯(Möbius)反演則可以還原恰好在整數 處的貢獻。在反演之前,我們需要一個無須逐一列出所有因數便能計算因數和的方法。
定義
定義 4.1.1
(算術函數與積性)
算術函數是定義在正整數上的函數,這裏取複數值。若 ,且當 時 ,則稱它為積性函數。若這個乘積恆等式在沒有互質限制時也成立,則稱它為完全積性函數。定義
令 ;當某個質數的平方整除 時,令 ;否則,當 是 個互不相同的質數之積時,令 。並約定歐拉(Euler)函數 。
除非另有說明,「積性」一詞始終保留其互質條件。積性函數由它在質數冪上的取值所決定,因為唯一分解定理把 分解為兩兩互質的質數冪因子。
定理/命題
定理 4.1.2
(質數冪乘積公式)
設 ,其中質數互不相同,指數均為正,則
這三個函數都是積性函數。
定理 4.1.3
(莫比烏斯反演)
對於算術函數 ,等式 對所有正整數 成立,當且僅當
對所有正整數 成立。特別地,,且 。
證明思路
證明
(指數組與容斥原理)
的每個因數唯一對應一組指數 。數一數這樣的指數組,便證得 的公式;對 求和並展開乘積,便證得 的公式。要計算 ,在 之中統計不被任何 整除的整數。容斥原理先減去 ,再加上 ,如此類推。其展開式為 。互質的兩個輸入具有互不相交的質因數集合,積性便由此得證。
證明
(抵消恆等式與有限和的重排)
關鍵的抵消恆等式是
只有無平方因數的因數才有貢獻。若 有 個互不相同的質因數,這些貢獻之和為 。當 時,唯一的因數是 。
現在把因數和代入 ,並重排有限和:
反過來,把所設的 的公式代入 ,並使用同樣的內層抵消,便得到 。無須任何收斂性論證:每個和都是有限和。
最後,按 把整數 分類。對於 的某個固定因數 ,寫 ,則 且 ,因此有 種選擇。求和即證得 ;再由反演得出最後的公式。
證明透視
抵消在哪裏用上,以及符號為何不計重數
反演證明中真正不屬於記賬的只有一步:當 時的抵消 。其餘只是交換有限和的次序。代入 後,得到的是對所有滿足 的正整數對 求和;改為按 而非按 分組, 便遍歷 的因數。把抵消恆等式用於 (而不是 ),除 外的每一項都被消去。逆方向以另一種分組使用同一恆等式。
證明對 與 沒有任何假設:沒有用到積性、正性或增長條件,因為每個和都是有限和。真正用到的是符號的確切選擇。若把 換成符號 ,其中 計算帶重數的質因數個數,則在 處符號的因數和為 ,而不是 。取 及 時 ,於是 恆為 ;類比的反演公式在 處給出 ,而非 。正是令非無平方因數的因數取零,子集和 才會出現。
例題詳解
例題 4.1.4
(同一整數處的三個函數)
對於 ,有 ,,以及 。這些公式所計數的是不同的對象:因數的個數、因數之和,以及單位的個數。
例題 4.1.5
(對觀測到的因數總和進行反演)
設 ,且 。在 處,只有 的莫比烏斯值非零,所以 。更一般地,對無平方因數的因數展開,反演給出 。
例題 4.1.6
(為甚麼積性比完全積性更弱)
但 ,所以 。同樣,。這些並不是積性的反例,因為這些因子並不互質。相比之下,。
因數是相互獨立的指數選擇
因數公式之所以有用,是因為唯一分解把一個整體性的問題轉化為相互獨立的局部選擇。對整數的每個質因數,因數可以取從零至該整數中此質數的指數之間的任何指數。這些指數一經選定,恰好得到一個因數。反過來,每個因數恰好給出這樣一組指數。因此這些公式是一個雙射的推論,而不是在數值表中觀察到的巧合。
這個觀點解釋了為甚麼因數個數公式是把個數相乘,而因數和公式是把和相乘。在前一種情況中,每個指數選擇貢獻的權重為一。在後一種情況中,一個選擇貢獻相應的質數冪,而這些局部權重之積就是因數本身。展開一個和式的乘積,會把每一組指數恰好枚舉一次,並賦予正確的權重。只要給因數賦予一個積性權重,同樣的方法都適用。
完全平方數提供了一個有用的檢驗。它的質數指數全是偶數,所以其因數個數乘積中的每個因子都是奇數。反過來,若因數個數為奇數,則每個指數必為偶數。因此,一個正整數恰好在它是平方數時才有奇數個正因數。還有一個配對的證明:把每個因數與用該整數除以它而得的互補因數配成一對;只有平方根才可能與自身配對。兩種不同的觀點得出同一結論,並揭示了結構的不同側面。
積性只是對互質輸入的限制
要正確使用積性,首先要把屬於不同質數的質數冪分開。一般而言,不能把一個質數冪拆成該質數的若干重複副本再把函數值相乘,因為這些因子並不互質。因此,質數冪處的取值表才是正確的局部數據。只有質數處取值的表,對完全積性函數已經足夠,但對一般的積性函數則不夠。
例如,把整數映為其因數個數的函數在每個質數處的值都是二。單憑這些值並不能告訴我們它在質數平方處的值;由定義和指數枚舉,該值是三,而不是四。在實際計算中,先寫出互質的分解,可以防止錯誤的規則混入運算之中。這個區別在證明中同樣重要:在 gcd 條件下證得的乘積恆等式,如果不核對新輸入處的該條件,就不能再次使用。
莫比烏斯函數是一種抵消工具
莫比烏斯函數忽略含有重複質數的因數,因為它的目的在於整理不同質因數的子集。無平方因數的因數對應於從這些質數中選出一個子集。它的符號記錄該子集的大小是偶數還是奇數。對子集求和,得到與容斥原理相同的交錯抵消。把定義當作一列數列出時,它可能顯得不規則;但在固定某個整數的因數結構上觀察時,它是有系統的。
這也證明了莫比烏斯函數是積性的。若兩個輸入互質,它們的質數集合不相交。乘積中出現重複質數的平方,恰好當它出現在其中一個輸入裏時;此時積性等式的兩邊都為零。若兩者都沒有這樣的平方因子,則所選的不同質數的個數相加,於是它們的符號相乘。在一處的取值提供了空集的情況。於是,這個抵消函數與前面的因數函數一樣,適合同一個由局部到整體的框架。
卷積把反演計算打包
對於算術函數,把它們在某個整數處的因數卷積定義為:對第一個函數在某因數處的值乘以第二個函數在互補因數處的值求和。這樣的分解只有有限多個。交換一個因數與其互補因數,說明這個運算是可交換的。對正因子的三元組分組,說明它是可結合的:無論按哪種次序做卷積,都是對所有乘積等於該輸入的三元組上的同樣權重求和。
這個運算的單位元並不是常數函數一。它是在輸入一處取一、在其他處取零的函數。與它做卷積時,只有互補因子為一的那一項被保留。常數函數一則把一個函數變為它的因數和。莫比烏斯抵消恆等式說明,莫比烏斯函數是該常數函數的卷積逆元。於是結合律一句話便解釋了反演:施加逆元便撤銷了因數求和這個運算。
概念視角結構
反演即撤銷一次有限聚合
因數求和是按整除關係,而不是按整數通常的次序,把較小的貢獻聚合起來。莫比烏斯反演則是該關係上的逆聚合。有限和的證明仍然不可或缺:它核實了哪些因數對被組合在一起,以及為甚麼所有不需要的貢獻都會抵消。
這種記法對計算並非必需,但有助於在新問題中辨認同樣的模式。它也帶來一個提醒:卷積乘法不同於逐點乘法。把兩個函數在同一輸入處的值相乘,不同於對所有因子對求和。用卷積寫成的公式在翻譯回普通的和式時,必須保持其含義。
不借助符號反演的重構步驟
因數總和與其確切貢獻之間的關係是三角形的。在輸入一處,總和等於第一個貢獻。在任何更大的輸入處,從總和中減去所有真因數處已知的貢獻,便得到該輸入本身處餘下的貢獻。由於每個真正因數都更小,這遞歸地確定了該函數。這個論證即使不明確使用莫比烏斯函數,也證明了唯一性。
莫比烏斯反演給出了這個遞歸減法的封閉表達式。因此它並不對未知函數引入額外的假設:任意複值的貢獻都是容許的,也不需要正性。總和可以是正的,而個別貢獻是負的。這樣的符號並不是反演的錯誤;它們取決於所給的實際數據。當這些貢獻是在計數對象時,另外的組合解釋可能迫使它們非負,但這個性質來自該解釋,而不是單單來自這個代數定理。
只要每個元素只有有限多個前驅,同樣的三角形減法就能在任何偏序上反演求和。
通往推廣的路徑
在其他偏序上反演求和
只要每個元素只有有限多個前驅,同樣的三角形減法就能在任何偏序上反演求和。
上述重構只用到每個輸入只有有限多個因數。在一個偏序中,若每個集合 都有限,定義 ,並對 定義 。則對所有 有 ,當且僅當對所有 有 。對整除關係,;對有限集合的子集,,這正是容斥原理。
按確切分母統計互質分子
涉及歐拉函數的恆等式可以理解為把分數約成最簡形式。從分子取遍一至固定分母的那些分數出發。約分之後,其確切分母是原分母的一個因數。對每個可能的確切分母,約分後的分子恰好是其範圍內與它互質的整數。按此確切分母分類,便得到因數和。這個解釋包含等於一的端點分數;歐拉函數在一處的約定,正是使該情況被正確計入的原因。
用 gcd 分類的證明與約分分數的解釋,以不同的語言描述了同一個劃分。認識到這個聯繫,有助於判斷何時適宜使用反演:先找出一個按唯一的、取值為因數的參數對對象分組的總和,再還原該參數某個確切取值處的貢獻。
另一個有用的核對是:若總量取整數值,反演所得的各項貢獻亦為整數,因為公式只使用整數係數和有限項。這不需要正性或任何增長估計。先檢查輸入為一的情形,再從每個較大輸入的有限因數集合獨立恢復其值。因此,即使沒有收斂的無限生成級數,這個初等反演定理仍可使用。漸近大小的問題則需要本節有限代數以外的進一步論證。
常見錯誤
常見錯誤
(因數和同時包括 與 )
因數和遍歷所有正因數,包括 與 。漏掉 會破壞反演以及 處的規範化。例如,只對 的因數 求 之和,得到 ,而不是 。
常見錯誤
(莫比烏斯符號不計重複的質因數)
莫比烏斯值取決於重複的質因數:,而 。若計算帶重數的質因數總個數並據此賦予符號,在 處會得到 ,定義的是另一個不同的函數,而它的因數和並不抵消。
常見錯誤
(內層和遍歷 的因數)
重排反演和式時,要追蹤確切的條件 。內層和遍歷的是 的因數,而不是獨立於 的 的因數。正是這個限制把 孤立了出來。
總結
唯一分解把因數的枚舉轉化為相互獨立的指數選擇。莫比烏斯抵消消除了真因數的貢獻,從而給出確切貢獻與其因數總和之間的可逆關係。
練習
快速檢查
(計算 、、 和 。)
先做分解;不要枚舉 個候選數。
解答 · 答案
。因此 ,,。由於 ,。
快速檢查
(設對每個 , 在 的所有正因數 上的和等於 。求 ,並論證其唯一性。)
可以使用反演,或使用 的定義。
解答 · 答案
常數函數 的因數和為 ,所以它是一個解。莫比烏斯反演使 被唯一確定,因此沒有其他解。等價地,把兩個所設的解相減並對 歸納:所有真因數處的貢獻先行消失,迫使餘下的貢獻也消失。
快速檢查
(設對每個 都有 。求 ,並用反演公式在 處驗證答案。)
比較 的定義與因數和的定義。
解答 · 答案
按定義 ,所以 是一個解,而莫比烏斯反演說明它是唯一的解。在 處,莫比烏斯值非零的因數是 ,公式給出 ,與預期一致。