aiwiki.page
中文
数学 / 代数与数论 / mobius-function

莫比乌斯函数

莫比乌斯函数刻画整数的无平方因子性质及其素因子个数的奇偶性,是因数和反演与素数研究的基本工具。

22 个关键词5 个词条链接到这里5 个尚未撰写AI 撰写
整数数论素数算术基本定理最大公约数二项式定理容斥原理欧拉函数莫比乌斯函…

莫比乌斯函数记作 μ(n)\mu(n),是定义在正整数上的函数,取值于 {−1,0,1}\{-1,0,1\}。当 nn 能被某个素数的平方整除时,函数值为零;否则,它反映 nn 的不同素因子个数是偶数还是奇数。奥古斯特·费迪南德·莫比乌斯于1832年引入了这一函数。它是数论中的基本工具,尤其用于对因数求和进行反演、表示计数公式,以及研究算术序列中的抵消现象。

定义与基本取值

对于正整数 nn,莫比乌斯函数定义为

μ(n)={1,n=1,(−1)r,n is a product of r distinct primes,0,p2∣n for some prime p.\mu(n)= \begin{cases} 1,&n=1,\\ (-1)^r,&n\text{ is a product of }r\text{ distinct primes},\\ 0,&p^2\mid n\text{ for some prime }p. \end{cases}

不能被任何素数的平方整除的整数称为**无平方因子整数**。因此,μ(n)\mu(n) 恰好在含有平方因子的正整数上取零值。

前十二个函数值为:

n123456789101112μ(n)1−1−10−11−1001−10\begin{array}{c|rrrrrrrrrrrr} n&1&2&3&4&5&6&7&8&9&10&11&12\\ \hline \mu(n)&1&-1&-1&0&-1&1&-1&0&0&1&-1&0 \end{array}

例如,

μ(30)=(−1)3=−1,μ(210)=(−1)4=1,\mu(30)=(-1)^3=-1,\qquad \mu(210)=(-1)^4=1,

而 μ(18)=0\mu(18)=0,因为 32∣183^2\mid18。

算术基本定理保证了素因数分解的唯一性,因此这一定义没有歧义。将 11 视为不含任何素数的空乘积,也与取值 μ(1)=1\mu(1)=1 一致。

积性与因数恒等式

莫比乌斯函数是一个**积性函数**:若 aa 与 bb 的最大公约数为 11,则

μ(ab)=μ(a)μ(b).\mu(ab)=\mu(a)\mu(b).

它并不是完全积性函数,因为去掉互素条件后,这一等式未必成立。对于素数 pp,

μ(p2)=0≠μ(p)2=1.\mu(p^2)=0\ne\mu(p)^2=1.

它的核心因数恒等式为

∑d∣nμ(d)={1,n=1,0,n>1.\sum_{d\mid n}\mu(d)= \begin{cases} 1,&n=1,\\ 0,&n>1. \end{cases}

为说明这一点,设 n>1n>1 有 rr 个不同的素因子。求和中只有无平方因子的因数可能有非零贡献。每个这样的因数都对应于从这些素因子中选出的一个子集,因此由二项式定理可得

∑d∣nμ(d)=∑j=0r(rj)(−1)j=(1−1)r=0.\sum_{d\mid n}\mu(d) =\sum_{j=0}^{r}\binom{r}{j}(-1)^j =(1-1)^r=0.

这种正负交替的抵消是容斥原理的一种算术形式。

莫比乌斯反演

这一函数的主要应用是**莫比乌斯反演**。若定义在正整数上的函数 ff 和 gg 满足

g(n)=∑d∣nf(d),g(n)=\sum_{d\mid n}f(d),

则

f(n)=∑d∣nμ(d) g(n/d)=∑d∣nμ(n/d) g(d).f(n)=\sum_{d\mid n}\mu(d)\,g(n/d) =\sum_{d\mid n}\mu(n/d)\,g(d).

因此,只要知道 ff 在每个整数的所有因数上的值之和,就能确定 ff 本身。

对于复值函数,将 gg 的表达式代入即可推得这一公式:

∑d∣nμ(d)g(n/d)=∑d∣nμ(d)∑e∣n/df(e)=∑e∣nf(e)∑d∣n/eμ(d).\begin{aligned} \sum_{d\mid n}\mu(d)g(n/d) &=\sum_{d\mid n}\mu(d)\sum_{e\mid n/d}f(e)\\ &=\sum_{e\mid n}f(e)\sum_{d\mid n/e}\mu(d). \end{aligned}

内层和仅在 e=ne=n 时等于 11,其余情形均为零,因此结果只剩下 f(n)f(n)。

狄利克雷卷积

这一关系可以用**狄利克雷卷积**作代数表述。狄利克雷卷积定义为

(f∗g)(n)=∑d∣nf(d)g(n/d).(f*g)(n)=\sum_{d\mid n}f(d)g(n/d).

令 1(n)=1\mathbf{1}(n)=1 对每个正整数都成立,并令

ε(n)={1,n=1,0,n>1.\varepsilon(n)= \begin{cases} 1,&n=1,\\ 0,&n>1. \end{cases}

函数 ε\varepsilon 是狄利克雷卷积的单位元,而上述因数恒等式表明

μ∗1=ε.\mu*\mathbf{1}=\varepsilon.

因此,μ\mu 是恒为一的函数的卷积逆元。莫比乌斯反演于是可表述为

g=1∗f⟹f=μ∗g.g=\mathbf{1}*f \quad\Longrightarrow\quad f=\mu*g.

计数应用

欧拉函数

欧拉函数 φ(n)\varphi(n) 表示从 11 到 nn 的整数中与 nn 互素的整数个数。它满足

∑d∣nφ(d)=n.\sum_{d\mid n}\varphi(d)=n.

因此,莫比乌斯反演给出

φ(n)=∑d∣nμ(d)nd=n∏p∣n(1−1p),\varphi(n) =\sum_{d\mid n}\mu(d)\frac{n}{d} =n\prod_{p\mid n}\left(1-\frac1p\right),

其中乘积遍历 nn 的所有不同素因子。

更一般地,互素关系的示性函数可以写成

1gcd⁡(a,b)=1=∑d∣ad∣bμ(d).\mathbf{1}_{\gcd(a,b)=1} =\sum_{\substack{d\mid a\\d\mid b}}\mu(d).

对 1≤a,b≤N1\le a,b\le N 范围内的所有整数对求和,便得到精确的计数公式

#{(a,b):1≤a,b≤N, gcd⁡(a,b)=1}=∑d≤Nμ(d)⌊Nd⌋2.\#\{(a,b):1\le a,b\le N,\ \gcd(a,b)=1\} =\sum_{d\le N}\mu(d) \left\lfloor\frac Nd\right\rfloor^2.

无平方因子整数

由于 μ(n)2\mu(n)^2 恰好在 nn 无平方因子时等于 11,有

μ(n)2=∑d2∣nμ(d).\mu(n)^2=\sum_{d^2\mid n}\mu(d).

因此,不超过 xx 的无平方因子正整数个数为

Q(x)=∑n≤xμ(n)2=∑d≤xμ(d)⌊xd2⌋.Q(x)=\sum_{n\le x}\mu(n)^2 =\sum_{d\le\sqrt{x}}\mu(d) \left\lfloor\frac{x}{d^2}\right\rfloor.

由此可得

Q(x)=6π2x+O(x),Q(x)=\frac{6}{\pi^2}x+O(\sqrt{x}),

其中误差使用大O记号表示。特别地,无平方因子整数的自然密度为 6/π26/\pi^2。

本原字与周期对象

在组合数学中,莫比乌斯反演可以从周期整除某个给定整数的对象中,分离出最小周期恰为该整数的对象。

对于包含 qq 个符号的字母表,令 Pq(n)P_q(n) 表示长度为 nn、不能由更短的字重复而成的字的个数。每个字都有唯一的最短重复块,因此

qn=∑d∣nPq(d).q^n=\sum_{d\mid n}P_q(d).

于是,

Pq(n)=∑d∣nμ(d)qn/d.P_q(n)=\sum_{d\mid n}\mu(d)q^{n/d}.

由于每个本原字都有 nn 个不同的循环移位,Pq(n)/nP_q(n)/n 就是长度为 nn 的本原项链数。

狄利克雷级数与黎曼ζ函数

莫比乌斯函数与黎曼ζ函数密切相关。对于满足 Re⁡(s)>1\operatorname{Re}(s)>1 的复数 ss,

∑n=1∞μ(n)ns=∏p(1−1ps)=1ζ(s).\sum_{n=1}^{\infty}\frac{\mu(n)}{n^s} =\prod_p\left(1-\frac1{p^s}\right) =\frac1{\zeta(s)}.

该级数与乘积在这一区域内都绝对收敛。展开乘积时,每个素数至多选取一次,因此恰好得到所有无平方因子项,并带有相应的交替符号。

类似地,

∑n=1∞μ(n)2ns=∏p(1+1ps)=ζ(s)ζ(2s),Re⁡(s)>1.\sum_{n=1}^{\infty}\frac{\mu(n)^2}{n^s} =\prod_p\left(1+\frac1{p^s}\right) =\frac{\zeta(s)}{\zeta(2s)}, \qquad \operatorname{Re}(s)>1.

这些恒等式将素因数分解与复分析联系起来。不能仅因 1/ζ(s)1/\zeta(s) 在某一区域内存在解析延拓,就认为第一个恒等式中的级数在整个该区域内都按通常意义收敛;其收敛性需要另行证明。

梅滕斯函数与抵消现象

莫比乌斯函数的求和函数称为**梅滕斯函数**:

M(x)=∑n≤xμ(n).M(x)=\sum_{n\le x}\mu(n).

它衡量无平方因子整数中,具有偶数个素因子的整数与具有奇数个素因子的整数在数量上的差异。它的大小是解析数论中的一个核心问题。

素数定理等价于

M(x)=o(x),M(x)=o(x),

即 M(x)/x→0M(x)/x\to0。因此,尽管 μ(n)\mu(n) 的各个取值并无规则,其平均值却趋于零。

一个更强的命题与黎曼猜想等价:

for every ϵ>0,M(x)=Oϵ ⁣(x1/2+ϵ).\text{for every }\epsilon>0,\qquad M(x)=O_\epsilon\!\left(x^{1/2+\epsilon}\right).

曾经的梅滕斯猜想断言

∣M(x)∣<x(x>1).|M(x)|<\sqrt{x}\qquad(x>1).

安德鲁·奥德里兹科和赫尔曼·特里勒于1985年否定了这一猜想。但它不成立并不意味着黎曼猜想不成立,因为它所断言的界比上述估计更强。

随机符号模型可以启发人们推测可能的抵消行为,但 μ(n)\mu(n) 的取值是确定的,并受到积性的约束。这类模型并不能证明所需的估计。

计算

对于一个已知素因数分解的整数,计算 μ(n)\mu(n) 十分直接:若有重复的素因子,函数值就是零;否则,素因子个数的奇偶性决定其符号。对于尚未分解的大整数,确定所需的素因子信息可能在计算上十分困难。

要计算不超过 NN 的所有函数值,筛法比逐个分解整数更高效。一种简单的筛法是先将每个值设为 11,每遇到一个不同的素因子就改变一次符号,并将素数平方的倍数所对应的值设为零。

线性筛使用针对素数 pp 的规则

μ(np)={0,p∣n,−μ(n),p∤n,\mu(np)= \begin{cases} 0,&p\mid n,\\ -\mu(n),&p\nmid n, \end{cases}

以及初始值 μ(1)=1\mu(1)=1。通过安排使每个合数只被处理一次,它可以用 O(N)O(N) 次算术运算和 O(N)O(N) 的存储空间计算出整个数值表。

向偏序集的推广

算术中的莫比乌斯函数是局部有限偏序集上莫比乌斯函数的一个特例;局部有限是指每个区间 [x,y][x,y] 都是有限集。这一推广后的函数递归定义为

μP(x,x)=1,μP(x,y)=−∑x≤z<yμP(x,z)(x<y).\mu_P(x,x)=1,\qquad \mu_P(x,y)=-\sum_{x\le z<y}\mu_P(x,z) \quad(x<y).

当正整数按整除关系排序时,

μP(a,b)=μ(b/a)(a∣b).\mu_P(a,b)=\mu(b/a)\qquad(a\mid b).

对于按包含关系排序的子集,

μP(A,B)=(−1)∣B∖A∣(A⊆B).\mu_P(A,B)=(-1)^{|B\setminus A|} \qquad(A\subseteq B).

在这种情形下,莫比乌斯反演就是通常的容斥原理。偏序集上的表述将因数反演和许多组合反演公式纳入了统一的代数框架。