メビウスの反転公式

テンプレート:簡易区別 数学において、古典的なメビウスの反転公式 (Möbius inversion formula) は、アウグスト・フェルディナント・メビウス (August Ferdinand Möbius) によって19世紀に数論に導入された。

整除関係によって順序付けられた自然数という古典的な場合に、別のテンプレート:仮リンクが取って代わると、他のメビウス反転公式が得られる。説明は隣接代数を参照。

古典的な反転公式

古典的なバージョンは次のようなものである。テンプレート:Mvar と テンプレート:Mvar が、すべての正の整数 テンプレート:Mvar に対して

$g(n)=\sum _{d\mid n}f(d)$

を満たす数論的関数であれば、すべての正の整数 テンプレート:Mvar に対して

$f(n)=\sum _{d\mid n}\mu (d)g(n/d)$

が成り立つ。ここで テンプレート:Math はメビウス関数であり、和は テンプレート:Mvar のすべての正の約数 テンプレート:Mvar を渡る。要するに、もとの テンプレート:Math は テンプレート:Math が与えられると反転公式を用いて決定することができる。2つの数列は互いのメビウス変換 (Möbius transform) と呼ばれる。

公式は テンプレート:Mvar と テンプレート:Mvar が正の整数から（Z-加群と見た）アーベル群への関数であるときにも正しい。

ディリクレの畳み込みを用いて、最初の式を

$g=f*1$

と書くことができる。ここに テンプレート:Math はディリクレの畳み込みを表し、テンプレート:Math は定数関数 $1(n)=1$ である。すると二番目の式は

$f=\mu *g$

と書ける。多くの具体例は乗法的関数の記事で与えられている。

定理は テンプレート:Math が（可換かつ）結合的であり、テンプレート:Math であることから従う、ただし テンプレート:Math はディリクレの畳み込みに対する単位元であり、テンプレート:Math および テンプレート:Math に対して テンプレート:Math という値を取る。したがって $\mu *g=\mu *(1*f)=(\mu *1)*f=\epsilon *f=f$ となる。

級数関係

$a_n=\sum _{d\mid n}{b}_d$

とすると、変換は

$b_n=\sum _{d\mid n}\mu \left(\frac{n}{d}\right)a_d$

である。変換は級数によって関連付けられる。テンプレート:仮リンク

$\sum _{n=1}^{\mathrm{\infty }}{a}_n{x}^n=\sum _{n=1}^{\mathrm{\infty }}{b}_n\frac{x^n}{1-x^n}$

やディリクレ級数

$\sum _{n=1}^{\mathrm{\infty }}\frac{a_n}{n^s}=\zeta (s)\sum _{n=1}^{\mathrm{\infty }}\frac{b_n}{n^s}$

である。ここで $\zeta (s)$ はリーマンのゼータ関数である。

繰り返しの変換

数論的関数が与えられると、最初の総和を繰り返し適用することによって他の数論的関数の両側無限列を生成することができる。

例えば、オイラーのトーシェント関数 $\phi$ に対して変換を繰り返し適用していくと

1. $\phi ,$ トーシェント関数
2. $\phi *1=\mathrm{Id},$ 恒等写像
3. $\mathrm{Id}*1={\sigma }_1=\sigma ,$ 約数関数

メビウスの関数自身から始めると、

1. $\mu ,$ メビウス関数
2. $\mu *1=\epsilon ,$ ただし $\epsilon (n)=\{\begin{array}{cc}1,& \text{if }n=1\\ 0,& \text{if }n>1\end{array}$　は テンプレート:仮リンク
3. $\epsilon *1=1,$ 定値写像
4. $1*1={\sigma }_0=\mathrm{d}=\tau ,$ ただし $\mathrm{d}=\tau$ は テンプレート:Mvar の約数の個数（約数関数参照）

これらのリストのいずれも、両方向に無限に伸びる。メビウスの反転公式によって逆向きに行くことができる。

例として、$\phi$ で始まる列は：

$f_n=\{\begin{array}{cc}\underset{-n\text{ factors}}{\underbrace{\mu *\dots *\mu }}*\phi & \text{if }n<0\\ \phi & \text{if }n=0\\ \phi *\underset{n\text{ factors}}{\underbrace{1*\dots *1}}& \text{if }n>0\end{array}$

生成される列は、対応するディリクレ級数を考えることによってより容易に理解できるかもしれない。各変換はリーマンのゼータ関数を掛けることに対応する。

一般化

テンプレート:See also 組合せ数学においてより有用な反転公式は次のようなものである。F (x) と G (x) は区間 [1, ∞) 上で定義された複素数値関数であって、

$G(x)=\sum _{1\le n\le x}F(x/n)\text{ for all }x\ge 1$

であれば、

$F(x)=\sum _{1\le n\le x}\mu (n)G(x/n)\text{ for all }x\ge 1$

である。ここで和は x 以下のすべての正の整数 n を走る。

これはさらに一般化される。$\alpha (n)$ がテンプレート:仮リンク ${\alpha }^{-1}(n)$ を持つ数論的関数であるとき、

$G(x)=\sum _{1\le n\le x}\alpha (n)F(x/n)\text{ for all }x\ge 1$

と定義すると、

$F(x)=\sum _{1\le n\le x}{\alpha }^{-1}(n)G(x/n)\text{ for all }x\ge 1$

が成り立つ。前の公式は定数関数 $\alpha (n)=1$ という特別な場合である。このとき逆元は ${\alpha }^{-1}(n)=\mu (n)$ である。

これらの拡張のうち 1 つ目を適用できる例として、正の整数上定義された（複素数値）関数 f (n) と g (n) であって

$g(n)=\sum _{1\le m\le n}f\left(\lfloor \frac{n}{m}\rfloor \right)\text{ for all }n\ge 1$

なるものがあるとき、$F(x)=f(\lfloor x\rfloor )$ および $G(x)=g(\lfloor x\rfloor )$ とすると、

$f(n)=\sum _{1\le m\le n}\mu (m)g\left(\lfloor \frac{n}{m}\rfloor \right)\text{ for all }n\ge 1$

となる。

この公式を使う簡単な例は、テンプレート:仮リンク テンプレート:Math の個数を数えることである。ここで a と b は互いに素で b ≤ n である。f (n) をこの個数とすれば、g (n) は b ≤ n なる分数 テンプレート:Math の総数である。ここで a と b は互いに素である必要はない。（なぜならば、テンプレート:Math かつ テンプレート:Math なるすべての分数 テンプレート:Math は テンプレート:Math なる分数 (a / d ) / (b / d ) に簡約でき、逆もまた然りであるからだ。）テンプレート:Math であることを確かめるのは容易だが、テンプレート:Math は計算が難しい。

別の反転公式は、

$\begin{array}{ccccc}& & g(x)& =\sum _{m=1}^{\mathrm{\infty }}\frac{f(mx)}{m^s}& \text{for all }x\ge 1\\ & ⟺& f(x)& =\sum _{m=1}^{\mathrm{\infty }}\mu (m)\frac{g(mx)}{m^s}& \text{for all }x\ge 1\end{array}$

（ただし、級数は絶対収束すると仮定する。）上と同様、これは $\alpha (n)$ がディリクレ逆元 ${\alpha }^{-1}(n)$ を持つ数論的関数である場合に一般化される。

$\begin{array}{ccccc}& & g(x)& =\sum _{m=1}^{\mathrm{\infty }}\alpha (m)\frac{f(mx)}{m^s}& \text{for all }x\ge 1\\ & ⟺& f(x)& =\sum _{m=1}^{\mathrm{\infty }}{\alpha }^{-1}(m)\frac{g(mx)}{m^s}& \text{for all }x\ge 1\end{array}$

乗法的表記

メビウスの変換公式は任意のアーベル群に対して適用できるから、群の演算が加法的に書かれているか乗法的に書かれているかは関係ない。乗法的な場合反転公式は次のようになる。

$F(n)=\prod _{d\mid n}f(d)$

ならば

$f(n)=\prod _{d\mid n}F(n/d{)}^{\mu (d)}$

一般化の証明

最初の一般化は次のように証明できる。Iverson's convention を使う。これは [条件] がその条件の指示関数、つまり、条件が真であれば 1 で偽であれば 0 であるような関数を表すというものである。次の結果を使う。$\sum _{d|n}\mu (d)=\epsilon (n)$, つまり、テンプレート:Math。

すると以下のようになる。

$\begin{array}{cc}\sum _{1\le n\le x}\mu (n)g\left(\frac{x}{n}\right)& =\sum _{1\le n\le x}\mu (n)\sum _{1\le m\le x/n}f\left(\frac{x}{mn}\right)\\ & =\sum _{1\le n\le x}\mu (n)\sum _{1\le m\le x/n}\sum _{1\le r\le x}[r=mn]f\left(\frac{x}{r}\right)\\ & =\sum _{1\le r\le x}f\left(\frac{x}{r}\right)\sum _{1\le n\le x}\mu (n)\sum _{1\le m\le x/n}[m=r/n]\text{rearranging the summation order}\\ & =\sum _{1\le r\le x}f\left(\frac{x}{r}\right)\sum _{n|r}\mu (n)\\ & =\sum _{1\le r\le x}f\left(\frac{x}{r}\right)\epsilon (r)\\ & =f(x)\text{since }\epsilon (r)=0\text{ except when }r=1\end{array}$

二つ目の一般化では テンプレート:Math が テンプレート:Math に取って代わるが、証明は本質的に同一である。

Weisner, Hall, Rota の貢献

訳：一般化メビウス反転公式は、当初はワイズナー（1935）とフィリップ・ホール（1936）が独立に与えたものである。両者とも群論の問題から着想を得ている。 両者とも、この公式が組み合わせ数学と関連することに気づいていたわけでも、メビウス関数の理論を発展させたわけでもなかったようである。 メビウス関数の基礎的論文において、ロタは組み合わせ数学におけるこの理論の重要性を示し、深い考察を与えた。彼は包除原理、古典的な数論的メビウス反転、彩色問題、ネットワーク上の流れといった事柄間の関連性に言及している。 それ以降ロタの強い影響力により、メビウス反転の理論とそれに関連する事柄は、組み合わせ数学で活発に研究される領域となった。

関連項目

• 包除原理
• ファレイ数列
• 隣接代数 (順序理論)

参考文献

• テンプレート:Apostol IANT
• テンプレート:SpringerEOM
• K. Ireland, M. Rosen. A Classical Introduction to Modern Number Theory, (1990) Springer-Verlag.

外部リンク

• テンプレート:高校数学の美しい物語
• Möbius Inversion Formula at ProofWiki
• テンプレート:MathWorld