莫比乌斯函数

Posted on

版权声明:本文作者 22 班周裕杭，未经作者允许严禁转载。

相信大家对莫比乌斯函数及其相关内容都很陌生吧！不过 TST2022 好像有一道莫反题（相信大家的目标都是在 TST 做到 24/24 吧！），故作此文章，向大家科普一下这个在 OI 里很常用，MO 里却比较 useless 的东西。由于是科普向的文章，不会涉及一些比较困难的内容，而是会讲得比较繁琐。

一些记号说明：

  • τ(n)\tau(n) 表示 nn 的约数个数。
  • ω(n)\omega(n) 表示 nn 的不同素因子个数。
  • [P][P] 表示当 PP 为真时该式取 11，否则取 00.

积性函数

我们首先从积性函数这个概念讲起。

称函数 f:Z+→Cf : \mathbb Z ^ + \to \mathbb C 是积性函数当且仅当 ∀x,y∈Z+&(x,y)=1\forall x, y \in \mathbb{Z} ^ {+} \And (x, y) = 1，有 f(xy)=f(x)f(y)f(xy) = f(x) f(y). 不过，在接下来的讨论中，我们将不考虑函数 f(n)=0f(n) = 0，也就是说必定有 f(1)=0f(1) = 0. 一些很常见的积性函数有：

  • 1(n)=11(n) = 1.

  • id⁡(n)=n\operatorname{id}(n)=n.

  • τ(n)\tau(n).

  • φ(n)\varphi(n).

关于这些函数的积性的证明，相信大家早已熟悉，这里不多赘述。

现在我们已经定义了名为”积性函数“的集合，接下来我们将定义作用在这个集合上的二元运算——狄利克雷卷积。

两个积性函数 f,gf, g 的狄利克雷卷积 h=f×gh = f \times g，满足 h(n)=∑d∣nf(d)g(nd)h(n) = \sum _ {d \mid n} f(d) g\left( \frac {n} {d} \right). 容易验证，积性函数关于这一运算有封闭性，交换律和结合律。同时，我们也可以很容易地找出一个”单位元“：ε(n)=[n=1]\varepsilon(n) = [n = 1]. 了解过群论的同学自然会好奇：（积性函数，狄利克雷卷积）是否构成一个群呢？

想要证明这个命题，我们只需证明对于每个积性函数 ff，都恰存在一个积性函数 gg，满足 f×g=g×f=εf \times g = g \times f = \varepsilon. 这并不困难：假设我们已经知道了 g(1),g(2),⋯ ,g(n−1)g(1), g(2), \cdots, g(n - 1) 的取值，根据狄利克雷卷积的定义，我们有：

∑d∣nf(d)g(nd)=[n=1]g(n)=[n=1]−∑d∣n,d>1f(d)g(nd)\begin{aligned} & \sum _ {d\mid n} f(d) g \left( \frac {n} {d} \right) = [n = 1]\\ & g(n) = [n = 1] -\sum _ {d \mid n, d > 1} f(d) g \left( \frac {n} {d} \right) \end{aligned}

这意味着我们可以进一步确定 g(n)g(n) 的值，从而我们可以唯一确定 gg 在每一处的取值。这样看来，积性函数确实关于狄利克雷卷积构成了一个交换群。

莫比乌斯函数

上述的论证其实就是在证明每个积性函数 ff 都存在一个逆元 gg. 那积性函数 1(n)=11(n) = 1 的逆元是什么呢？我们先记它为 μ\mu，下面让我们来看看如何算出 μ\mu 具体的样子。

在进行下一步前，首先要介绍一个关于积性函数的非常简单的性质：设 ff 是一积性函数，nn 的标准分解为 n=∏i=1kpiαin = \prod _ {i = 1} ^ k p_i ^ {\alpha _ i}，则 f(n)=∏i=1kf(piαi)f(n) = \prod _ {i = 1} ^ k f \left( p_i ^ {\alpha _ i} \right). 这是非常容易证明的，大家可以从定义出发自行思考一下。

上述性质告诉我们，如果我们确定了一个积性函数 ff 在所有形如 pkp ^ k 处的取值，那我们实际上也就确定了它每一处的取值。我们从这个思路出发计算 μ\mu：

  • 对于任意素数 pp，μ(p)=0−μ(1)1(p)=−1\mu(p) = 0 - \mu(1) 1(p) = -1.
  • μ(p2)=0−μ(p)1(p)−μ(1)1(p2)=0\mu(p ^ 2) = 0 - \mu(p) 1(p) - \mu(1)1(p ^ 2) = 0.
  • 进一步推导不难发现，对于任意正整数 k≥2k \ge 2，都有 μ(pk)=0\mu(p ^ k) = 0.

于是我们得到了 μ\mu 的一种定义：

  • 对于正整数 nn：
    • 若存在素数 pp 满足 p2∣np ^ 2 \mid n，则 μ(n)=0\mu(n) = 0.
    • 否则 μ(n)=(−1)ω(n)\mu(n) = (-1) ^ {\omega(n)}.

同时，由于 μ\mu 和 11 互为逆元，因此形如 ∑d∣nμ(d)=[n=1]\sum _ {d \mid n} \mu(d) = [n = 1] 的式子天然成立。当然，很多人认识 μ\mu 函数的过程与本文的叙述顺序相反，即先记住 μ\mu 的定义式，再尝试证明 ∑d∣nμ(d)=[n=1]\sum _ {d \mid n} \mu(d) = [n = 1]. 这当然可以用狄利克雷卷积那一套理论非常暴力地证明（也就是上文的逆过程），不过，接下来我们将展示 μ\mu 函数与容斥原理间千丝万缕的联系，并从这个角度来证明上式。

容斥原理

说起容斥原理与积性函数之间的联系，很多人第一时间想起的可能会是 φ\varphi 的那个经典计算式。让我们回顾一下 φ(n)\varphi(n) 试图解决什么问题：{1,2,⋯ ,n}\{1, 2, \cdots, n \} 中有多少个与 nn 互质的数，对吧？那如果我们扩展这一形式，将问题改为求 {1,2,⋯ ,m}\{1, 2, \cdots, m \} 中与 nn 互质的数的个数呢？

这里，我先给出一个非常组合计数的做法：

  • 记 SP⁡(n)\operatorname{SP}(n) 为 nn 的所有素因子构成的集合，那么 xx 与 nn 互质就可以简单地被刻画为 SP⁡(x)∩SP⁡(n)=∅\operatorname{SP}(x) \cap \operatorname{SP}(n) = \varnothing.
  • 记 fSf _ S 为 {1,2,⋯ ,m}\{1, 2, \cdots, m \} 里满足 SP⁡(x)∩SP⁡(n)=S\operatorname{SP}(x) \cap \operatorname{SP}(n) = S 的 xx 的个数，显然我们所求即 f∅f_{\varnothing}.（这里序列的下标是一个集合）
  • 再记 gSg _ S 为 {1,2,⋯ ,m}\{1, 2, \cdots, m \} 里满足 S⊆(SP⁡(x)∩SP⁡(n))S \subseteq (\operatorname{SP}(x) \cap \operatorname{SP}(n)) 的 xx 的个数，显然当 S⊆SP⁡(n)S \subseteq \operatorname{SP}(n) 时，gS=⌊m∏p∈Sp⌋g _ S = \left\lfloor \frac {m} {\prod _ {p \in S} p} \right\rfloor.
  • 根据容斥原理，f∅=∑S⊆SP⁡(n)(−1)∣S∣gS=∑S⊆SP⁡(n)(−1)∣S∣⌊m∏p∈Sp⌋f _ {\varnothing} = \sum _ {S \subseteq \operatorname{SP}(n)} (-1) ^ {|S|} g_S = \sum _ {S \subseteq \operatorname{SP}(n)} (-1) ^ {|S|} \left\lfloor \frac {m} {\prod _ {p \in S} p} \right\rfloor.

写到这里，相比注意力惊人的你一定发现了，上面的式子实质上就是 ∑d∣nμ(d)⌊md⌋\sum _ {d \mid n} \mu(d) \left\lfloor \frac {m} {d} \right\rfloor，这无疑告诉我们，μ\mu 函数就是一个在素因子集合上的容斥系数。于是欲证的式子就很简单了：∑d∣nμ(d)=∑S⊆SP⁡(n)(−1)∣S∣=[SP⁡(n)=∅]=[n=1]\sum _ {d \mid n} \mu(d) = \sum _ {S \subseteq \operatorname{SP}(n)} (-1) ^ {|S|} = [\operatorname{SP}(n) = \varnothing] = [n = 1].

给大家留一个简单的思考题：如何直接使用 ∑d∣nμ(d)=[n=1]\sum _ {d \mid n} \mu(d) = [n = 1] 来解决上面提出的问题？

提示：将式子写成 ∑i=1m[(i,n)=1]\sum _ {i = 1} ^ m [(i, n) = 1] 的形式并拆开。

莫比乌斯反演

终于来到最为重量级的部分了！虽然好像几乎没有题目需要用它

莫比乌斯反演 形式一：g(n)=∑d∣nf(d)  ⟺  f(n)=∑d∣nμ(nd)g(d)g(n) = \sum _ {d \mid n} f(d) \iff f(n) = \sum _ {d \mid n} \mu \left( \frac {n} {d} \right) g(d)

相信大家可能对上面这个式子的含义有些许的不解。更严谨的说话是，如果 ∀n∈Z+\forall n \in \mathbb Z ^ +，都有 g(n)=∑d∣nf(d)g(n) = \sum _ {d \mid n} f(d)，那么反过来也有 ∀n∈Z+,f(n)=∑d∣nμ(nd)g(d)\forall n \in \mathbb Z ^ +, f(n) = \sum _ {d \mid n} \mu \left( \frac {n} {d} \right) g(d)；反之亦然。了解线性代数的同学可以进一步看出一个反演的本质其实就是构造一对互逆的矩阵，不过这里先略去不谈。

回到这个式子的证明，一种非常简明的方法是使用狄利克雷卷积。用卷积的形式重写上式，命题就变为 g=f×1  ⟺  f=g×μg = f \times 1 \iff f = g \times \mu，而这是显然的：g=f×1  ⟺  g×μ=f×1×μ=f×(1×μ)=fg = f \times 1 \iff g \times \mu = f \times 1 \times \mu = f \times (1 \times \mu) = f. 注意这里 ff 和 gg 无需是积性函数，因为狄利克雷卷积在一般序列上也满足交换律和结合律。

莫比乌斯反演 形式二：g(n)=∑n∣df(d)  ⟺  f(n)=∑n∣dμ(dn)g(d)g(n) = \sum _ {n \mid d} f(d) \iff f(n) = \sum _ {n \mid d} \mu \left( \frac {d} {n} \right) g(d)

对这一形式，我们直接给出证明：

f(n)=∑n∣dμ(dn)g(d)=∑n∣dμ(dn)∑d∣d′f(d′)=∑n∣d′f(d′)∑n∣d,d∣d′μ(dn)=∑n∣d′f(d′)∑d∣d′nμ(d)=∑n∣d′f(d′)[d′n=1]=f(n)\begin{aligned} & f(n) \\ & = \sum _ {n \mid d} \mu \left( \frac {d} {n} \right) g(d) \\ & = \sum _ {n \mid d} \mu \left( \frac {d} {n} \right) \sum _ { d \mid d' } f(d') \\ & = \sum _ {n \mid d'} f(d') \sum _ {n \mid d, d \mid d'} \mu \left( \frac {d} {n} \right) \\ & = \sum _ {n \mid d'} f(d') \sum _ {d \mid \frac {d'} {n}} \mu(d) \\ & = \sum _ {n \mid d'} f(d') \left[ \frac {d'} {n} = 1 \right] \\ & = f(n) \end{aligned}

在倒数第三个等号处，我们实际上是用 dd 替代了上式中的 dn\frac {d} {n}.

习题

  1. 求证以下等式恒成立（默认数域为 Z+\mathbb Z ^ +，使用尽量简明的方法）：

    (1). ∑d∣nφ(d)=n\sum _ {d \mid n} \varphi(d) = n.

    (2). ∑d∣nμ(d)nd=φ(n)\sum_{d \mid n} \mu(d) \frac {n} {d} = \varphi(n).

    (3). ∑d∣nφ(d)τ(nd)=σ(n)\sum _ {d \mid n} \varphi(d) \tau \left( \frac {n} {d} \right) = \sigma(n).

    (4). ∑d∣naω(d)=τ(na)\sum _ {d \mid n} a ^ {\omega(d)} = \tau(n ^ a).

    (5). 1n∑d∣nσ(d)=∑d∣nτ(d)d\frac {1} {n} \sum _ {d \mid n} \sigma(d) = \sum _ {d \mid n} \frac {\tau(d)} {d}.

    (6). n∑d∣nσ(d)d=∑d∣ndτ(d)n \sum _ {d \mid n} \frac {\sigma(d)} {d} = \sum _ {d \mid n} d \tau(d).

  2. 求所有的积性函数 ff，使得 F(n)=∑i=1nf(i)F(n) = \sum _ {i = 1} ^ n f(i) 也是积性函数。

  3. 称数 xx 是好的，当且仅当 μ(x)≠0\mu(x) \neq 0。记 f(n)f(n) 为 1∼n1 \sim n 中好数的个数，求证：存在常数 cc，使得对于所有充分大的 nn，都有 f(n)>c⋅nf(n) > c \cdot n. 有能力者可进一步给出一个紧的 cc.

  4. 求证：对于给定的正整数 aa，若 N→N\mathbb N \to \mathbb N 的函数 ff 满足 ∀x∈N,f(x)=∑i=1a2ω(i+x)\forall x \in \mathbb N, f(x) = \sum _ {i = 1} ^ a 2 ^ {\omega(i + x)} ，则其最小值为 f(0)f(0).

  5. 求 {1,2,⋯ ,2021}\{1, 2, \cdots, 2021 \} 有多少个子集 SS 满足 2021∣∑x∈Sx2021 \mid \sum _ {x \in S} x.（提示：试使用 [k∣n]=1k∑i=0k−1ωkij[k \mid n] = \frac {1} {k} \sum _ {i = 0} ^ {k - 1} \omega _ {k} ^ {ij}）

  6. 求证：∑i=1nφ(i)2i−1<2\sum _ {i = 1} ^ n \frac {\varphi(i)} {2 ^ i - 1} < 2.

  7. 试证明：对于任意有限集 A⊂Z+A \subset \mathbb Z ^ +，都有 ∑S⊆A(−2)∣S∣−1gcd⁡(S)>0\sum _ {S \subseteq A} (-2) ^ {|S| - 1} \gcd(S) > 0，其中 gcd⁡(S)\gcd(S) 表示 SS 中所有元素的最大公约数。

  8. 设 nn 是正整数，DD 是 nn 所有正因子构成的集合，ff 是 D→ZD \to \mathbb Z 的映射。证明下面两个论断等价：

(A) 对任意 m∈Dm \in D，n∣∑d∣mf(d)(n/dm/d)n \mid \sum _ {d \mid m} f(d) \binom {n / d} {m / d}

(B) 对任意 k∈Dk \in D，k∣∑d∣kf(d)k \mid \sum _ {d \mid k} f(d)