莫比乌斯反演
前言
- 不要把莫比乌斯反演和莫比乌斯变换当成一回事
莫比乌斯变换的范围要广的多，别一眼看上去：哇，傻逼分式线性函数嘛，so easy！然后后面你就不懂了
详细看维基百科：Möbius transformation
还有这一篇深度好文 Moebius.pdf
言归正传，回到topic。今天主要从数学角度去研究。
定义
如果对数论函数$f(n)$和$g(n)$，有以下关系式:
${\displaystyle g(n)=\sum _{d\,\mid \,n}f(d)\quad {\text{对于每个整数}}n\geq 1} $
那么有
${\displaystyle f(n)=\sum _{d\,\mid \,n}\mu (d)g\left({\frac {n}{d}}\right)\quad {\text{对于每个整数}}n\geq 1}$
其中$\mu$是莫比乌斯函数。实际上，原函数$f(n)$通过使用反演公式给定唯一的$g(n)$。$f$和$g$被称为对方的$莫比乌斯变换$
如果f和g是从正整数到某个阿贝尔群的函数（被看作ℤ - 模块），则该公式也是正确的。
用Dirichlet卷积描述，第一个公式可以写成${\displaystyle g = f * {\mathit {1}}}$
其中星号表示Dirichlet卷积，$\mathit{1}$是常数函数$\mathit{1}(n)=1$。然后将第二个公式写成$f = \mu * g$
因为卷乘是(可交换的)和关联的，并且$\mathit{1} * \mu=\varepsilon$，而$\varepsilon$是Dirichlet卷积中的单位函数
所以我们有：
仅仅是数论函数？我们来看看它的一般形式：
一般形式
设 ${\displaystyle F(x)}$及 ${\displaystyle G(x)}$ 为定义在$ {\displaystyle [1,\infty )}$上的复值函数并且有${\displaystyle G(x)=\sum _{1\leqslant n\leqslant x}F\left({\frac {x}{n}}\right)} $
那么有${\displaystyle F(x)=\sum _{1\leqslant n\leqslant x}\mu (n)G\left({\frac {x}{n}}\right)} $
级数关系
令${\displaystyle a_{n}=\sum _{d\mid n}b_{d}} $
那么${\displaystyle b_{n}=\sum _{d\mid n}\mu \left({\frac {n}{d}}\right)a_{d}} $
就是它的莫比乌斯变换。
- 与Lambert 级数的意义相关：
${\displaystyle \sum _{n=1}^{\infty }a_{n}x^{n}=\sum _{n=1}^{\infty }b_{n}{\frac {x^{n}}{1-x^{n}}}} $
- 还有Dirichlet级数：
${\displaystyle \sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}=\zeta (s)\sum _{n=1}^{\infty }{\frac {b_{n}}{n^{s}}}} $，其中$\zeta(s)$是黎曼$\zeta$函数
- 与分圆多项式的对数相关
$\Phi_n(x)=\prod_\limits{d|n}(1-x^{\frac{n}{d}})^{\mu(d)}$
推广
在组合学中更有用的相关反演公式如下：
假设$F(x)$和$G(x)$都是定义在区间$[1,\infty)$上的复值函数，使得
${\displaystyle G(x)=\sum _{1\leq n\leq x}F\left({\frac {x}{n}}\right)\quad {\mbox{ 对于所有}}x\geq 1} $
于是就有
${\displaystyle F(x)=\sum _{1\leq n\leq x}\mu (n)G\left({\frac {x}{n}}\right)\quad {\mbox{ 对于所有}}x\geq 1.} $
这里，总和扩展到小于或等于x的所有正整数n。
反过来，我们得到了更为特殊的基本形式：
如果$\alpha(n)$是一个算术函数，并且具有Dirichlet逆$\alpha^{-1}(n)$
定义${\displaystyle G(x)=\sum _{1\leq n\leq x}\alpha (n)F\left({\frac {x}{n}}\right)\quad {\mbox{ 对于所有 }}x\geq 1} $
那么有${\displaystyle F(x)=\sum _{1\leq n\leq x}\alpha ^{-1}(n)G\left({\frac {x}{n}}\right)\quad {\mbox{对于所有 }}x\geq 1.} $
前面的公式若出现在常数函数$\alpha(n)=1$的特殊情况下，它的Dirichlet逆就是$\mu(n)$
如果我们在正整数上定义了复值函数$f(n)$和$g(n)$，则会出现第一个扩展的特定应用：
${\displaystyle g(n)=\sum _{1\leq m\leq n}f\left(\left\lfloor {\frac {n}{m}}\right\rfloor \right)\quad {\mbox{ 对于所有 }}n\geq 1.} $
定义$F(x)=f(\lfloor x\rfloor)$和$G(x)=g(\lfloor x\rfloor)$
我们得到${\displaystyle f(n)=\sum _{1\leq m\leq n}\mu (m)g\left(\left\lfloor {\frac {n}{m}}\right\rfloor \right)\quad {\mbox{ 对于所有 }}n\geq 1.} $
另外一个反转公式则是
${\displaystyle g(x)=\sum _{m=1}^{\infty }{\frac {f(mx)}{m^{s}}}\quad {\mbox{ for all }}x\geq 1\quad \Longleftrightarrow \quad f(x)=\sum _{m=1}^{\infty }\mu (m){\frac {g(mx)}{m^{s}}}\quad {\mbox{ 对于所有 }}x\geq 1.} $
和前面类似，推广到$\alpha(n)$是一个算术函数，并且具有Dirichlet逆$\alpha^{-1}(n)$的情况：
${\displaystyle g(x)=\sum _{m=1}^{\infty }\alpha (m){\frac {f(mx)}{m^{s}}}\quad {\mbox{ for all }}x\geq 1\quad \Longleftrightarrow \quad f(x)=\sum _{m=1}^{\infty }\alpha ^{-1}(m){\frac {g(mx)}{m^{s}}}\quad {\mbox{ 对于所有 }}x\geq 1.} $
在偏序集上的反演
对于一个偏序集$P$(每个主序理想有限)，用${\displaystyle \mu (s,s)=1{\text{ for }}s\in P,\qquad \mu (s,u)=-\sum _{s\leq t<u}\mu (s,t),\quad {\text{ for }}s<u{\text{ in }}P.} $递归地定义莫比乌斯函数$\mu$
对于$ {\displaystyle f,g:P\to K}$($K$为域) ，有${\displaystyle g(t)=\sum _{s\leq t}f(s)\qquad {\text{ for all }}t\in P} $当且仅当${\displaystyle f(t)=\sum _{s\leq t}g(s)\mu (s,t)\qquad {\text{ for all }}t\in P.} $
加法换成乘法？
- 由于莫比乌斯反演适用于任何阿贝尔群，因此群作用是加法还是乘法没有区别。这产生了以下反演公式的符号变形：
- ${\displaystyle {\mbox{若}}F(n)=\prod _{d|n}f(d),{\mbox{ 则 }}f(n)=\prod _{d|n}F\left({\frac {n}{d}}\right)^{\mu (d)}.} $
简要证明
拿第一次推广为例：
${\displaystyle {\begin{aligned}\sum _{1\leq n\leq x}\mu (n)g\left({\frac {x}{n}}\right)&=\sum _{1\leq n\leq x}\mu (n)\sum _{1\leq m\leq {\frac {x}{n}}}f\left({\frac {x}{mn}}\right)\\&=\sum _{1\leq n\leq x}\mu (n)\sum _{1\leq m\leq {\frac {x}{n}}}\sum _{1\leq r\leq x}[r=mn]f\left({\frac {x}{r}}\right)\\&=\sum _{1\leq r\leq x}f\left({\frac {x}{r}}\right)\sum _{1\leq n\leq x}\mu (n)\sum _{1\leq m\leq {\frac {x}{n}}}\left[m={\frac {r}{n}}\right]\qquad {\text{重新排列和式的顺序}}\\&=\sum _{1\leq r\leq x}f\left({\frac {x}{r}}\right)\sum _{n|r}\mu (n)\\&=\sum _{1\leq r\leq x}f\left({\frac {x}{r}}\right)i(r)\\&=f(x)\qquad {\text{当}}i(r)=0{\text{ ,除了 }}r=1{\text{ 的情况 }}\end{aligned}}} $
$\alpha(n)$替换$\mathit{1}$的更一般情况下的证明基本相同，第二次推广也是如此。
参考资料
[1] Wikipedia, Möbius inversion formula
[2] wolfram mathworld, Möbius Inversion Formula
[3] Mobius Inversion Formula, Zeta Functions, Lecture 14 Notes Here
[4] Twisted One 151’s Weblog, Möbius Inversion Formula