动机
因数和把一个整数及其所有因数的信息混合在一起。例如,统计分母整除 的分数,得到的总数涉及每个 对应的 。莫比乌斯(Möbius)反演则能够还原恰好在整数 处的贡献。在反演之前,我们需要一种无需逐个列出所有因数就能计算因数和的方法。
定义
定义 4.1.1
(算术函数与积性)
算术函数是定义在正整数上的函数,这里取复数值。若 ,且当 时 ,则称其为积性函数。若该乘积恒等式在没有互素限制时也成立,则称其为完全积性函数。定义
令 ;当某个素数的平方整除 时,令 ;否则,当 是 个互不相同的素数之积时,令 。并约定欧拉(Euler)函数 。
除非另有说明,“积性”一词始终保留其互素条件。积性函数由它在素数幂上的取值所决定,因为唯一分解定理把 分解为两两互素的素数幂因子。
定理/命题
定理 4.1.2
(素数幂乘积公式)
设 ,其中素数互不相同,指数均为正,则
这三个函数都是积性函数。
定理 4.1.3
(莫比乌斯反演)
对于算术函数 ,等式 对所有正整数 成立,当且仅当
对所有正整数 成立。特别地,,且 。
证明思路
证明
(指数组与容斥原理)
的每个因数唯一对应一组指数 。数一数这样的指数组,即证得 的公式;对 求和并展开乘积,即证得 的公式。为计算 ,在 中统计不被任何 整除的整数。容斥原理先减去 ,再加上 ,如此继续。其展开式为 。互素的两个输入具有互不相交的素因子集合,由此证得积性。
证明
(抵消恒等式与有限和的重排)
关键的抵消恒等式是
只有无平方因数的因数才有贡献。若 有 个互不相同的素因子,这些贡献之和为 。当 时,唯一的因数是 。
现在把因数和代入 ,并重排有限和:
反过来,把所设的 的公式代入 ,并使用同样的内层抵消,便得到 。无需任何收敛性论证:每个和都是有限和。
最后,按 对整数 分类。对于 的某个固定因数 ,写 ,则 且 ,因而有 种选择。求和即证得 ;再由反演得到最后的公式。
证明透视
抵消在哪里用上,以及符号为何不计重数
反演证明中真正不属于记账的只有一步:当 时的抵消 。其余只是交换有限和的次序。代入 后,得到的是对所有满足 的正整数对 求和;改为按 而不是按 分组, 便遍历 的因数。把抵消恒等式用于 (而不是 ),除 外的每一项都被消去。逆方向以另一种分组使用同一恒等式。
证明对 与 没有任何假设:没有用到积性、正性或增长条件,因为每个和都是有限和。真正用到的是符号的确切选择。若把 换成符号 ,其中 计算带重数的素因子个数,则在 处符号的因数和为 ,而不是 。取 及 时 ,于是 恒为 ;类比的反演公式在 处给出 ,而不是 。正是令含平方因子的因数取零,子集和 才会出现。
例题详解
例题 4.1.4
(同一整数处的三个函数)
对于 ,有 ,,以及 。这些公式计数的是不同的对象:因数的个数、因数之和,以及单位的个数。
例题 4.1.5
(对观测到的因数总和进行反演)
设 ,且 。在 处,只有 的莫比乌斯值非零,所以 。更一般地,对无平方因数的因数展开,反演给出 。
例题 4.1.6
(为什么积性比完全积性更弱)
但 ,所以 。同样,。这些并不是积性的反例,因为这些因子并不互素。相比之下,。
因数是相互独立的指数选择
因数公式之所以有用,是因为唯一分解把一个整体性的问题转化为相互独立的局部选择。对整数的每个素因子,因数可以取从零到该整数中此素数指数之间的任意指数。这些指数一旦选定,恰好得到一个因数。反过来,每个因数恰好给出这样一组指数。因此这些公式是一个双射的推论,而不是在数值表中观察到的巧合。
这一观点解释了为什么因数个数公式是把个数相乘,而因数和公式是把和相乘。在前一种情形中,每个指数选择贡献的权重为一。在后一种情形中,一个选择贡献相应的素数幂,而这些局部权重之积就是因数本身。展开一个和式的乘积,会把每一组指数恰好枚举一次,并赋予正确的权重。只要给因数赋予一个积性权重,同样的方法都适用。
完全平方数提供了一个有用的检验。它的素数指数全是偶数,所以其因数个数乘积中的每个因子都是奇数。反过来,若因数个数为奇数,则每个指数必为偶数。因此,一个正整数恰好在它是平方数时才有奇数个正因数。还有一个配对证明:把每个因数与用该整数除以它得到的互补因数配成一对;只有平方根才可能与自身配对。两种不同的观点得到同一结论,并揭示了结构的不同侧面。
积性只是对互素输入的限制
要正确使用积性,首先要把属于不同素数的素数幂分开。一般不能把一个素数幂拆成该素数的若干重复拷贝再把函数值相乘,因为这些因子并不互素。因此,素数幂处的取值表才是正确的局部数据。仅有素数处取值的表对完全积性函数已经足够,但对一般的积性函数则不够。
例如,把整数映为其因数个数的函数在每个素数处的值都是二。仅凭这些值并不能告诉我们它在素数平方处的值;由定义和指数枚举,该值是三,而不是四。在实际计算中,先写出互素的分解,可以防止错误的规则混入算术之中。这一区别在证明中同样重要:在 gcd 条件下证得的乘积恒等式,如果不核对新输入处的该条件,就不能再次使用。
莫比乌斯函数是一种抵消工具
莫比乌斯函数忽略含有重复素数的因数,因为它的目的在于组织不同素因子的子集。无平方因数的因数对应于从这些素数中选出一个子集。它的符号记录该子集的大小是偶数还是奇数。对子集求和,得到与容斥原理相同的交错抵消。把定义当作一列数列出时,它可能显得不规则;但在固定某个整数的因数结构上观察时,它是系统的。
这也证明了莫比乌斯函数是积性的。若两个输入互素,它们的素数集合不相交。乘积中出现重复素数的平方,恰好当它出现在其中一个输入里时;此时积性等式的两边都为零。若两者都没有这样的平方因子,则所选的不同素数的个数相加,于是它们的符号相乘。在一处的取值提供了空集的情形。于是,这个抵消函数与前面的因数函数一样,适合同一个由局部到整体的框架。
卷积把反演计算打包
对于算术函数,把它们在某个整数处的因数卷积定义为:对第一个函数在某因数处的值乘以第二个函数在互补因数处的值求和。这样的分解只有有限多个。交换一个因数与其互补因数,说明这一运算是交换的。对正因子的三元组分组,说明它是结合的:无论按哪种顺序做卷积,都是对所有乘积等于该输入的三元组上的同样权重求和。
这一运算的单位元并不是常值函数一。它是在输入一处取一、在其他处取零的函数。与它做卷积时,只有互补因子为一的那一项被保留。常值函数一则把一个函数变为它的因数和。莫比乌斯抵消恒等式说明,莫比乌斯函数是该常值函数的卷积逆。于是结合律用一句话就解释了反演:施加逆元便撤销了因数求和这一运算。
概念视角结构
反演即撤销一次有限聚合
因数求和是按整除关系,而不是按整数通常的顺序,把较小的贡献聚合起来。莫比乌斯反演则是该关系上的逆聚合。有限和的证明仍然不可或缺:它核实了哪些因数对被组合在一起,以及为什么所有不需要的贡献都会抵消。
这种记号对计算并非必需,但有助于在新问题中识别同样的模式。它也带来一个提醒:卷积乘法不同于逐点乘法。把两个函数在同一输入处的值相乘,不同于对所有因子对求和。用卷积写成的公式在翻译回普通的和式时,必须保持其含义。
不借助符号反演的重构步骤
因数总和与其确切贡献之间的关系是三角形的。在输入一处,总和等于第一个贡献。在任何更大的输入处,从总和中减去所有真因数处已知的贡献,即得到该输入本身处剩余的贡献。由于每个真正因数都更小,这递归地确定了该函数。这个论证即使不显式使用莫比乌斯函数,也证明了唯一性。
莫比乌斯反演给出了这一递归减法的封闭表达式。因此它并不对未知函数引入额外的假设:任意复值的贡献都是允许的,也不需要正性。总和可以是正的,而个别贡献是负的。这样的符号并不是反演的错误;它们取决于所给的实际数据。当这些贡献是在计数对象时,另外的组合解释可能迫使它们非负,但这一性质来自该解释,而不是单单来自这个代数定理。
只要每个元素只有有限多个前驱,同样的三角形减法就能在任意偏序上反演求和。
通往推广的路径
在其他偏序上反演求和
只要每个元素只有有限多个前驱,同样的三角形减法就能在任意偏序上反演求和。
上面的重构只用到每个输入只有有限多个因数。在一个偏序中,若每个集合 都有限,定义 ,并对 定义 。那么对所有 有 ,当且仅当对所有 有 。对整除关系,;对有限集合的子集,,这正是容斥原理。
按确切分母统计互素分子
涉及欧拉函数的恒等式可以理解为把分数约成最简形式。从分子取遍一到固定分母的那些分数出发。约分之后,其确切分母是原分母的一个因数。对每个可能的确切分母,约分后的分子恰好是其范围内与它互素的整数。按此确切分母分类,便得到因数和。这一解释包含等于一的端点分数;欧拉函数在一处的约定,正是使该情形被正确计入的原因。
用 gcd 分类的证明与约分分数的解释,用不同的语言描述了同一个划分。认识到这一联系,有助于判断何时适宜使用反演:先找出一个按唯一的、取值为因数的参数对对象分组的总和,再还原该参数某个确切取值处的贡献。
另一个有用的核对是:若总量为整数,反演得到的各项贡献也为整数,因为公式仅使用整数系数和有限个项。这不要求正性或任何增长估计。先检查输入为一的情形,再从每个较大输入的有限因数集合独立恢复其值。因此,即使不存在收敛的无限生成级数,这个初等反演定理仍然适用。关于渐近大小的问题,则需要本节有限代数以外的进一步论证。
常见错误
常见错误
(因数和同时包括 与 )
因数和遍历所有正因数,包括 与 。漏掉 会破坏反演以及 处的规范化。例如,只对 的因数 求 之和,得到 ,而不是 。
常见错误
(莫比乌斯符号不计重复的素因子)
莫比乌斯值取决于重复的素因子:,而 。若计算带重数的素因子总个数并据此赋予符号,在 处会得到 ,定义的是另一个不同的函数,而它的因数和并不抵消。
常见错误
(内层和遍历 的因数)
重排反演和式时,要跟踪确切的条件 。内层和遍历的是 的因数,而不是独立于 的 的因数。正是这一限制把 孤立了出来。
总结
唯一分解把因数的枚举转化为相互独立的指数选择。莫比乌斯抵消消除了真因数的贡献,从而给出确切贡献与其因数总和之间的可逆关系。
练习
快速检查
(计算 、、 和 。)
先做分解;不要枚举 个候选数。
解答 · 答案
。因此 ,,。由于 ,。
快速检查
(设对每个 , 在 的所有正因数 上的和等于 。求 ,并论证其唯一性。)
可以使用反演,或使用 的定义。
解答 · 答案
常值函数 的因数和为 ,所以它是一个解。莫比乌斯反演使 被唯一确定,因此没有其他解。等价地,把两个所设的解相减并对 归纳:所有真因数处的贡献先行消失,迫使剩余的贡献也消失。
快速检查
(设对每个 都有 。求 ,并用反演公式在 处验证答案。)
比较 的定义与因数和的定义。
解答 · 答案
按定义 ,所以 是一个解,而莫比乌斯反演说明它是唯一的解。在 处,莫比乌斯值非零的因数是 ,公式给出 ,与预期一致。