logo
搜索
我的图书馆

发文章

发文工具

其他工具

留言交流
搜索
分享

莫比乌斯函数

 svdk 2024-10-30
莫比乌斯函数μ(n)是由德国数学家奥古斯特·费迪南德·莫比乌斯于1832年引入的乘法函数。它在初等和解析数论中无处不在，最常作为其同名莫比乌斯反演公式的一部分出现。继20世纪60年代吉安-卡洛·罗塔的工作之后，莫比乌斯函数的推广被引入组合学，并以类似的方式表示为 μ(x)。1874年，梅滕斯(Mertens)首先使用μ(n)作为莫比乌斯函数的记号。而德国物理学家和数学家高斯(Gauss)认为莫比乌斯函数比莫比乌斯早30多年就已出现。莫比乌斯函数在数论中有着广泛应用。莫比乌斯函数
\mu(n)
是在正整数集上的函数，
\mu\left(n\right)=\begin{cases}1,\text{若}n=1\newline 0,\text{若}n能被一个素数的平方整除\newline \left(-1\right)^{r}\text{，若}n是r个（r\geq1）不同素数的乘积\end{cases}
莫比乌斯函数
\mu\left(n\right)
是积性函数。[5][6][7][1]
莫比乌斯函数
\mu\left(n\right)
与欧拉(Euler)
\varphi
函数关系密切，可表现为
\varphi(n)=n\sum_{d;n}\frac{\mu(d)}{d}=n\sum_{d\mid n^{*}}\frac{\mu\left(d\right)}{d}
。莫比乌斯函数的求和函数：
M\left(x\right)=\sum_{n\leq x}\mu\left(n\right)
称为梅滕斯（Mertens）函数。[8][9][10]
莫比乌斯函数具有很多好的性质，在数论领域占据着重要的地位。它的应用很广泛，不仅在数论的研究中，而且因为在现代组合数学中有很强的组合背景，已经成为计数组合数学的一个有力工具，在现代数学中发挥其作用。[11]

定义

莫比乌斯函数
\mu\left(n\right)
是数论函数，其定义是：
\mu\left(n\right)=\begin{cases}1,\text{若}n=1\newline 0,\text{若}n能被一个素数的平方整除\newline \left(-1\right)^{r}\text{，若}n是r个（r\geq1）不同素数的乘积\end{cases}
该定义可看出莫比乌斯函数直接反映了每个自然数的素数分解式中素数的构成情况。如果
n
有平方因子，则
\mu[n]=0
；若
n
没有平方因子，并且分解后有奇数个素因子，则
\mu[n]=-1
；如果
n
没有平方因子，并且分解后有偶数个素因子.，则
\mu[n]=1
。[1][12]
麦比乌斯函数
\mu\left(n\right)
也可以表示为狄利克雷卷积逆。[13]
定义刘维尔函数
\lambda(n):\lambda(1)=1;n>1,\lambda(n)=(-1)^{a_1+a_2+\cdots+a_k}
，其中
n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}
，莫比乌斯函数可以表示为刘维尔函数。[14]
μ(n)的首50个值如下表[15]：

提出与命名

1832年，德国数学家和天文学家奥古斯特·费迪南德·莫比乌斯（August Ferdinand Möbius）在其发表的文章《über eine besondere Art von Umkehrung der Reihen》中首次提出了莫比乌斯函数。该函数以他的名字命名。1874年，梅滕斯(Mertens)首先使用μ(n)作为莫比乌斯函数的记号。而德国物理学家和数学家高斯(Gauss)认为莫比乌斯函数比莫比乌斯早30多年就已出现。[5][4][6][7]

性质

性质一

莫比乌斯函数
\mu\left(n\right)
是积性函数。[12]
（1）且
\left.\sum_{d\mid n}\mu(d)=\left\{\begin{array}{cc}1&n=1\text{,} \newline0&n>1.\end{array}\right.\right.
[16]
证明：若
n=1
，则
\sum_{d\mid n}\mu\left(d\right)=\mu\left(1\right)=1
若
n\gt1
，设
n=p_{1}^{a_{1}},\cdots\cdot p_{m}^{a}m
，因为
d
如果能被某素数的平方整除，则
\mu\left(d\right)=0
故得
\begin{aligned} \sum_{d\mid n}\mu\left(d\right)& =\sum_{d,p,-p,n}\mu\left(d\right) \&=\mu\left(1\right)+\sum_{i=1}^{n}\mu\left(p_{i}\right)+\sum_{i<i}\mu\left(p_{i}p_{i}\right)+\cdots \&+\mu(p,\cdots p_{m}) \&=1+C_{n}^{1}\cdot(-1)+C_{n}^{2}+\cdots+C_{n}^{*}(-1)^{m} \&=\sum_{i=0}^{m}C_{n}^{\prime}\cdot(-1)^{i}=(1-1)^{m}=0_{*} \end{aligned}
[17]
（2）
\sum_{d\mid n}\mid\mu(d)\mid=2^{m}
，其中
n=p_{1}^{a}\cdot\cdots\cdot p_{m}^{a}m
证明：利用上述推导过程，则有
\begin{aligned} \sum_{d\mid1}\mu\left(d\right)& =\sum_{d\mid P_{1}-P_{m}}\mid\mu\left(d\right)\mid \&=1+C_{n}^{1}+C_{n}^{2}+\cdots+C_{n}^{m} \&=\sum_{i=0}^{m}C_{m}^{\prime}=(1+1)^{n}=2^{m} \end{aligned}
[17]

性质二

设
f
是算数函数，
F
是
f
的和函数，
F(n)=\sum_{d|n}f(d)
则
f(n)=\sum_{d|n}\mu(d)F(n/d)
，其中
n
是正整数。这就是莫比乌斯反演公式。[12]

性质三

莫比乌斯函数是可乘函数。
证明：设
a_{1}
，
a_{2}
是任意两个互质的正整数，若其中一个为1，若其中一个数能被质数平方整除，则结论显然成立。
假定
a_{1}=p_{1}p_{2}p_{3}\cdots p_{r},a_{2}=q_{1}q_{2}q_{3}\cdots q_{s}
，其中
p_1,p_2,p_3,\cdots\cdots p_r;q_1,q_2,q_3,\cdots\cdots q_s
是互不相同素数。
由于
(a_1,a_2)=1
，故
p_{i}\neq q_{j}
因此由定义
\mu(a_1a_2)=(-1)^{r+s}=(-1)^{r}(-1)^{s}=\mu(a_1)\mu(a_2)
故莫比乌斯函数是可乘函数。[18]

性质四

如果
n\gt2
是奇素数，
x,y,z
是正整数，使
x^{n}+y^{n}=z^{n}
，那么
\mu(x+y)=0
（
\mu
表示莫比乌斯函数）[19]
莫比乌斯函数
\mu\left(n\right)
使那些含平方因子的数都对应于零。[20]

定理

定理一

设
x
是给定正实数，在不超过
x
的正整数中与正整数
n
互素的整数个数为
\varphi(n,x)
则
\varphi(n,x)=\sum_{d\mid n}\mu(d)\biggl[\frac{x}{d}\biggr]
[21]

定理二

设
\Pi(x)
表示不超过正实数
x
的所有素数的个数，又设
p_{1}，p_{2}\cdots ，p_{r}
为不超过
\sqrt{x}
的所有素数，
则
\Pi(x)-\Pi(\sqrt{x})+1=\varphi(p_{1}p_{2}\cdots p_{r},x)
[21]

与其他函数的关系

与欧拉函数

与莫比乌斯函数关系很密切的另一类数论函数是欧拉(Euler)
\varphi
函数，它也是对正整数
n
定义的。[9]这二者的联系表现在以下的命题中：
对正整数
n
，
\varphi(n)=n\sum_{d;n}\frac{\mu(d)}{d}=n\sum_{d\mid n^{*}}\frac{\mu\left(d\right)}{d}
证明：设
n
的素因数分解式为
n={p_{1}}^{t_{1}}{p_{2}}^{t_{2}}\cdots{p_{k}}^{t_{k}}
，则
n^{*}=p_{1}p_{2}\cdots p_{k}
，
\begin{aligned}n\sum_{d,n}\frac{\mu\left(d\right)}{d}&=n\sum_{d,n}\frac{\mu\left(d\right)}{d}\&=n\sum_{s=0}^{k}\sum_{1\leq i_{1}<\cdots<i_{s}\leq k}\frac{\mu\left(p_{i_{1}}\cdots p_{i_{s}}\right)}{p_{i_{1}}\cdots p_{i_{s}}} \&=n\sum_{s=0}^{k}\sum_{1\leq i_{1}<\cdots<i_{s}\leq k}\frac{(-1)^{s}}{p_{i_{1}\cdots p_{is}}} \&=n\prod_{i-1}^{k}\left(1-\frac{1}{p_{i}}\right)=\varphi\left(n\right) \end{aligned}
以下是
1\leq n\leq20
的
\mu\left(n\right)
与
\varphi(n)
数值表：[10]

与梅滕斯函数

在数论中，与莫比乌斯函数密切相关的另一个算术函数是梅滕斯（Mertens）函数，其定义为
M(n)=\sum_{k=1}^{n}\mu(k)
从公式
\mu(n)=\sum_{\overset{1\leq k\leq n}{\operatorname*{\gcd}(k,n)=1}}e^{2\pi i\frac{k}{n}}
由此可知，梅滕斯函数由下式给出：
M(n)=-1+\sum_{a\in\mathcal{F}_n}e^{2\pi ia}
[22]

相关概念

莫比乌斯变换

设
f(n)
，
g(n)
为两个数论函数
若
\mathrm{g(n)=\sum_{d\mid n}f(d)=\sum_{d\mid n}f\left(\frac{n}{d}\right)}
则
g(n)
称为
f(n)
的莫比乌斯变换，
f(n)
称为
g(n)
的莫比乌斯逆变换（反演）。[23]

积性函数

定义：设有一个不恒等于0的数论函数
f(n)
，若对任意两个互素的正整数
a,b
，都有
f(ab)=f(a)f(b)
，则称
f(n)
为积性函数。
若对所有正整数
a,b
，都有
f(ab)=f(a)f(b)
，则称
f(n)
为完全积性函数
由此定义可知，莫比乌斯函数
\mu\left(n\right)
是积性函数，但不是完全积性函数，而勒让德符号与雅可比符号都是完全积性函数。此外，表示不超过
x
的素数个数的函数
\pi\left( x \right)
不是积性函数。[24]

推广

偏序集上的莫比乌斯函数

设
(X_{1},\preceq_{1})
和
(X_{2},\preceq_{2})
为两个局部有限的偏序集。令
X=X_{1}\times X_{2},x,y\in X,x=(x_{1},y_{1}),y=(x_{2},y_{2})
定义
x\preceq y
当且仅当
x_{1}\preceq_{1}x_{2}
，
y_{1}\preceq_{2}y_{2}
，那么
(X,\preceq)
是局部有限的偏序集。若令
\mu_{1}
和
\mu_{2}
分别为偏序集
(X_{1},\preceq_{1})
和
(X_{2},\preceq_{2})
上的莫比乌斯函数，则偏序集
(X,\preceq)
上的莫比乌斯函数满足任意的
x，y\in X
，有
\mu(x,y)=\mu_{_1}(x_{_1},x_{_2})\cdot\mu_{_2}(y_{_1}y_{_2})
[25]

广义莫比乌斯函数

波波维奇函数定义的广义莫比乌斯函数
\mu_{k}=\mu*...*\mu
，是莫比乌斯函数与自身的k 次狄利克雷卷积。也是一个可乘函数。
其中
\mu_k\left(p^a\right)=(-1)^a\dbinom{k}{a}
如果
a\gt k
，则二项式系数被视为零。通过将二项式看作
k
的多项式，可以将该定义扩展到复数
k
。[26][27]

应用

莫比乌斯函数具有很多好的性质，在数论领域占据着重要的地位。它的应用很广泛，不仅在数论的研究中，而且因为在现代组合数学中有很强的组合背景，已经成为计数组合数学的一个有力工具，在现代数学中发挥其作用。[23]

计数组合数学

（1）分圆多项式的莫比乌斯函数表达：
\boldsymbol{\Phi}_{n}(x)=\prod_{d|n}(x^{d}-1)^{\mu(\frac{n}{d!})}
（2）指数函数的莫比乌斯函数表达：
引理
F(x)=\prod_{n\geqslant1}(1-x^n)^{-\frac{\mu(n)}{n}}
作为形式幂级数是收敛的
证明：因为
(1-x^{n})-\frac{\mu(n)}{n}=\sum_{i\geq0}\left(\vcenter{\hbox{$\frac{\mu(n)}{\frac{n}{i}}$}}\right)(-1)^{i}x^{in}=1+H(x)
，其中
\mathrm{deg}H(x)=n
，
故无穷乘积
F(x)=\prod_{n\ge1}(\begin{array}{c}1-x^n)\end{array}^{-\frac{\mu(n)}{n}}
收敛
引理
\log(\begin{array}{c}1+x)\end{array}=\sum_{n\geqslant1}(\begin{array}{c}-1)\end{array}^{n-1}\frac{x^n}{n}
，其中
\log x
是自然对数
定理
e^x=\prod_{n\gg1}(\begin{array}{c}1-x^n)\end{array}^{-\frac{\mu(n)}{n}}
，其中
\mu\left(n\right)
是莫比乌斯函数
证明：设
F(x)=\prod_{n\ge1}(1-x^{n})^{-\frac{\mu(n)}{n}}
，两边取自然对数得：
\begin{aligned}\log F(x)&=\log\prod_{n\approx1}(1-x^n)^{-\frac{\mu(n)}{n}}=\sum_{n\leq1}\log(1+x^n)^{-\frac{\mu(n)}{n}}=-\sum_{n\geq1}\frac{\mu(n)}{n}\log(1-x^n)=\\&-\sum_{n\leq1}\frac{\mu(n)}{n}\sum_{i\leq1}(-\frac{x^{in}}{i})\end{aligned}
上面幂级数中
x^{m}
项的系数为
\frac1m\sum_{d\mid m}\mu(\text{ }d)
。其中求和遍历整除
m
的所有正整数
d
由推论（1）可知
\mathrm{log}F(x)=x
故
F(x)=e^{x}
[28]

序列密码学

序列密码的安全性主要依赖于生成的密钥流（或滚动密钥）的质量，因此，设计出高效且难以预测的密钥流序列是实现其安全性的关键。密钥流序列通常由专门的密钥流生成器产生，这些生成器包括前馈序列产生器、非线性组合序列产生器、非线性反馈移位寄存器以及钟控序列生成器等。在非线性反馈移位寄存器的设计中，莫比乌斯函数有着重要的应用，它有助于增强序列的复杂性和随机性，从而提高密码系统的安全性。[29]
莫比乌斯函数与序列密码学

算数级数

这里
R(r,q,N,P)=-\sum\limits_{d>1}\mu(d)\Big(\Big\{\frac{N-x(r,d)}{d}\Big\}+\frac{x(r,d)}{d}\Big)
x(r,d)
为一次同余式
qx+r\equiv0(\mathrm{~mod~}d)
的一个解，
0\leqslant x(r,d)<d,\mu(n)
为莫比乌斯函数。[30]

参考资料

展开

相关合集

该页面最新编辑时间为 2024年9月5日

    本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。
    转藏 分享 献花（0）

    来自： svdk > 《自然与科学》

    举报/认领

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多