前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >狄利克雷近似定理_莫比乌斯反演例题

狄利克雷近似定理_莫比乌斯反演例题

作者头像
全栈程序员站长
发布2022-11-17 18:11:32
2550
发布2022-11-17 18:11:32
举报

首先定义几个概念:

1,卷积:

f,g
f,g

是两个数论函数(也就是说,以自然数集为定义域的复数值函数),则卷积运算

f\ast g
f\ast g

定义为

(f\ast g)(n) = \sum_{ij=n}{f(i)g(j)}
(f\ast g)(n) = \sum_{ij=n}{f(i)g(j)}

可以证明,卷积运算满足: 1)交换律:

f\ast g=g\ast f
f\ast g=g\ast f

由定义显然。

2)结合律:

(f\ast g)\ast h=f\ast(g\ast h)
(f\ast g)\ast h=f\ast(g\ast h)

考察两边作用在

n
n

上,左边是

\begin{align} ((f\ast g)\ast h)(n) &= \sum_{lk=n}(f\ast g)(l)h(k) \\ &= \sum_{lk=n}\left(\sum_{ij=l}f(i)g(j)\right)h(k)\\ &= \sum_{ijk=n} f(i)g(j)h(k) \end{align}
\begin{align} ((f\ast g)\ast h)(n) &= \sum_{lk=n}(f\ast g)(l)h(k) \\ &= \sum_{lk=n}\left(\sum_{ij=l}f(i)g(j)\right)h(k)\\ &= \sum_{ijk=n} f(i)g(j)h(k) \end{align}

右边是

\begin{align} (f\ast (g\ast h))(n) &= \sum_{il=n}f(i)(g\ast h)(l) \\ &= \sum_{il=n}f(i)\left(\sum_{jk=l}g(j)h(k)\right)\\ &= \sum_{ijk=n} f(i)g(j)h(k) \end{align}
\begin{align} (f\ast (g\ast h))(n) &= \sum_{il=n}f(i)(g\ast h)(l) \\ &= \sum_{il=n}f(i)\left(\sum_{jk=l}g(j)h(k)\right)\\ &= \sum_{ijk=n} f(i)g(j)h(k) \end{align}

故两边相等。

3)存在单位元

\iota
\iota

使得

\iota \ast f=f
\iota \ast f=f

我们需要

(\iota\ast f)(n)=\sum_{ij=n}\iota(i)f(j)=f(n)
(\iota\ast f)(n)=\sum_{ij=n}\iota(i)f(j)=f(n)

故不难猜到

\iota
\iota

应该定义为

\iota(n)= \begin{cases} 1&n=1\\ 0&n\neq1 \end{cases}
\iota(n)= \begin{cases} 1&n=1\\ 0&n\neq1 \end{cases}

事实上,直接验证可得

(\iota\ast f)(n)=\sum_{ij=n}\delta_{i,1}f(j)=f(n)
(\iota\ast f)(n)=\sum_{ij=n}\delta_{i,1}f(j)=f(n)

以上说明数论函数在卷积意义下构成一个交换群。

2,乘法单位元

u
u

上面的

\iota
\iota

是数论函数在卷积意义下的单位元,而普通乘法

(fg)(n):=f(n)g(n)
(fg)(n):=f(n)g(n)

意义下的单位元显然是把所有自然数都映到1的函数,记作

u
u

3,莫比乌斯函数

\mu
\mu
u
u

在卷积意义下的逆元,称为莫比乌斯函数。也就是说

\mu
\mu

是满足

u\ast\mu=\iota
u\ast\mu=\iota

的唯一的数论函数。 把这个表达式写开就是

\sum_{d\mid n}\mu(d)=\iota(n)
\sum_{d\mid n}\mu(d)=\iota(n)

…………(*)

通常,莫比乌斯函数

\mu
\mu

定义为

\mu(1)=1
\mu(1)=1

\mu(n)=(-1)^k
\mu(n)=(-1)^k

,如果

n
n

能写成

k
k

个不同素数之积;

\mu(n)=0
\mu(n)=0

,其他情况。

按照这种定义不难证明(*)式。 对于

n=1
n=1

,(*)式成立; 对于

n\neq1
n\neq1

,用算术基本定理把

n
n

写成

n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}
n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}

于是

\begin{align} \sum_{d\mid n}\mu(d) =& \mu(1)+\mu(p_1)+\mu(p_2)+\cdots+\mu(p_k)+\mu(p_1p_2)+\cdots+\mu(p_1p_2\cdots p_k) \\ =& \binom{k}{0}+\binom{k}{1}(-1)+\binom{k}{2}(-1)^2+\cdots+\binom{k}{k}(-1)^k \\ =&(1-1)^k=0 \end{align}
\begin{align} \sum_{d\mid n}\mu(d) =& \mu(1)+\mu(p_1)+\mu(p_2)+\cdots+\mu(p_k)+\mu(p_1p_2)+\cdots+\mu(p_1p_2\cdots p_k) \\ =& \binom{k}{0}+\binom{k}{1}(-1)+\binom{k}{2}(-1)^2+\cdots+\binom{k}{k}(-1)^k \\ =&(1-1)^k=0 \end{align}

现在来看看莫比乌斯反演说的是什么呢?

f(n)=\sum_{d\mid n}g(d)
f(n)=\sum_{d\mid n}g(d)

当且仅当

g(n)=\sum_{d\mid n}\mu\left(\frac{n}{d}\right)f(d)
g(n)=\sum_{d\mid n}\mu\left(\frac{n}{d}\right)f(d)

换而言之,

f = g\ast u \Leftrightarrow g = f\ast\mu
f = g\ast u \Leftrightarrow g = f\ast\mu

证明:

\begin{align} f=g\ast u \Rightarrow& f\ast \mu=(g\ast u)\ast \mu \\ \Rightarrow& f\ast\mu=g\ast(u\ast\mu) \\ \Rightarrow& f\ast\mu=g\ast\iota \\ \Rightarrow& f\ast\mu=g \end{align}
\begin{align} f=g\ast u \Rightarrow& f\ast \mu=(g\ast u)\ast \mu \\ \Rightarrow& f\ast\mu=g\ast(u\ast\mu) \\ \Rightarrow& f\ast\mu=g\ast\iota \\ \Rightarrow& f\ast\mu=g \end{align}

反之

\begin{align} g=f\ast\mu \Rightarrow& g\ast u=(f\ast\mu)\ast u \\ \Rightarrow& g\ast u=f\ast(\mu\ast u) \\ \Rightarrow& g\ast u=f\ast\iota \\ \Rightarrow& g\ast u=f \end{align}
\begin{align} g=f\ast\mu \Rightarrow& g\ast u=(f\ast\mu)\ast u \\ \Rightarrow& g\ast u=f\ast(\mu\ast u) \\ \Rightarrow& g\ast u=f\ast\iota \\ \Rightarrow& g\ast u=f \end{align}

作者:Syu Gau 链接:https://www.zhihu.com/question/23764267/answer/26007647 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/219524.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022年10月28日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档