メビウスの反転公式

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

整除関係によって順序付けられた自然数という古典的な場合に、別の局所有限半順序集合が取って代わると、他のメビウス反転公式が得られる。説明は隣接代数を参照。

古典的な反転公式

古典的なバージョンは次のようなものである。g と f が、すべての正の整数 n に対して

[math]g(n)=\sum_{d\,\mid \,n}f(d)[/math]

を満たす数論的関数であれば、すべての正の整数 n に対して

[math]f(n)=\sum_{d\,\mid\, n}\mu(d)g(n/d)[/math]

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

公式は f と g が正の整数から（Z-加群と見た）アーベル群への関数であるときにも正しい。

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

[math]g=f*1[/math]

と書くことができる。ここに * はディリクレの畳み込みを表し、1 は定数関数 [math]1(n)=1[/math] である。すると二番目の式は

[math]f=\mu * g[/math]

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

定理は * が（可換かつ）結合的であり、1 * μ = ε であることから従う、ただし ε はディリクレの畳み込みに対する単位元であり、ε(1) = 1 および n > 1 に対して ε(n) = 0 という値を取る。したがって [math]\mu * g = \mu * (1 * f) = (\mu * 1) * f = \varepsilon * f = f[/math] となる。

級数関係

[math]a_n=\sum_{d\mid n} b_d[/math]

とすると、変換は

[math]b_n=\sum_{d\mid n} \mu\left(\frac{n}{d}\right)a_d[/math]

である。変換は級数によって関連付けられる。ランベルト級数

[math]\sum_{n=1}^\infty a_n x^n = \sum_{n=1}^\infty b_n \frac{x^n}{1-x^n}[/math]

やディリクレ級数

[math]\sum_{n=1}^\infty \frac {a_n} {n^s} = \zeta(s) \sum_{n=1}^\infty \frac{b_n}{n^s}[/math]

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

繰り返しの変換

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

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

1. [math]\varphi,[/math] トーシェント関数
2. [math]\varphi*1=\operatorname{Id},[/math] 恒等写像
3. [math]\operatorname{Id} *1 =\sigma_1 =\sigma,[/math] 約数関数

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

1. [math]\mu,[/math] メビウス関数
2. [math]\mu*1 = \varepsilon,[/math] ただし [math]\varepsilon(n) = \begin{cases} 1, & \mbox{if }n=1 \\ 0, & \mbox{if }n\gt 1 \end{cases} [/math]　は unit function
3. [math]\varepsilon*1 = 1,[/math] 定値写像
4. [math]1*1=\sigma_0=\operatorname{d}=\tau,[/math] ただし [math]\operatorname{d}=\tau[/math] は n の約数の個数（約数関数参照）

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

例として、[math]\varphi[/math] で始まる列は：

[math] f_n = \begin{cases} \underbrace{\mu * \ldots * \mu}_{-n \text{ factors}} * \varphi & \text{if } n \lt 0 \\ \varphi & \text{if } n = 0 \\ \varphi * \underbrace{1* \ldots * 1}_{n \text{ factors}} & \text{if } n \gt 0 \end{cases} [/math]

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

一般化

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

[math]G(x) = \sum_{1 \le n \le x}F(x/n)\quad\mbox{ for all }x\ge 1[/math]

であれば、

[math]F(x) = \sum_{1 \le n \le x}\mu(n)G(x/n)\quad\mbox{ for all }x\ge 1[/math]

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

これはさらに一般化される。[math]\alpha(n)[/math] がディリクレ逆元 [math]\alpha^{-1}(n)[/math] を持つ数論的関数であるとき、

[math]G(x) = \sum_{1 \le n \le x}\alpha (n) F(x/n)\quad\mbox{ for all }x\ge 1[/math]

と定義すると、

[math]F(x) = \sum_{1 \le n \le x}\alpha^{-1}(n)G(x/n)\quad\mbox{ for all }x\ge 1[/math]

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

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

[math]g(n) = \sum_{1 \le m \le n}f\left(\left\lfloor \frac{n}{m}\right\rfloor\right)\quad\mbox{ for all } n\ge 1[/math]

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

[math]f(n) = \sum_{1 \le m \le n}\mu(m)g\left(\left\lfloor \frac{n}{m}\right\rfloor\right)\quad\mbox{ for all } n\ge 1[/math]

となる。

この公式を使う簡単な例は、既約分数 0 < a / b < 1 の個数を数えることである。ここで a と b は互いに素で b ≤ n である。f (n) をこの個数とすれば、g (n) は b ≤ n なる分数 0 < a / b < 1 の総数である。ここで a と b は互いに素である必要はない。（なぜならば、gcd (a, b) = d かつ b ≤ n なるすべての分数 a / b は b / d ≤ n / d なる分数 (a / d ) / (b / d ) に簡約でき、逆もまた然りであるからだ。）g (n) = n (n − 1) / 2 であることを確かめるのは容易だが、f (n) は計算が難しい。

別の反転公式は、

[math]\begin{align} &&g(x) &= \sum_{m=1}^\infty \frac{f(mx)}{m^s}&\mbox{for all } x\ge 1\\ &\Longleftrightarrow&f(x) &= \sum_{m=1}^\infty \mu(m)\frac{g(mx)}{m^s}&\mbox{for all } x\ge 1 \end{align}[/math]

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

[math]\begin{align} &&g(x) &= \sum_{m=1}^\infty \alpha(m)\frac{f(mx)}{m^s}&\mbox{for all } x\ge 1\\ &\Longleftrightarrow&f(x) &= \sum_{m=1}^\infty \alpha^{-1}(m)\frac{g(mx)}{m^s}&\mbox{for all } x\ge 1 \end{align}[/math]

乗法的表記

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

[math]F(n) = \prod_{d\mid n} f(d)[/math]

ならば

[math]f(n) = \prod_{d\mid n} F(n/d)^{\mu(d)} \,[/math]

一般化の証明

最初の一般化は次のように証明できる。Iverson's convention を使う。これは [条件] がその条件の指示関数、つまり、条件が真であれば 1 で偽であれば 0 であるような関数を表すというものである。次の結果を使う。[math]\sum_{d|n}\mu(d)=\varepsilon(n)[/math], つまり、1*μ = ε。

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

[math]\begin{align} \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] \qquad\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) \varepsilon(r) \\ &= f(x) \qquad\text{since }\varepsilon(r)=0\text{ except when }r=1 \end{align}[/math]

二つ目の一般化では α(n) が 1 に取って代わるが、証明は本質的に同一である。

Weisner, Hall, Rota の貢献

The statement of the general Möbius inversion formula was first given independently by Weisner (1935) and Philip Hall (1936); both authors were motivated by group theory problems. Neither author seems to have been aware of the combinatorial implications of his work and neither developed the theory of Möbius functions. In a fundamental paper on Möbius functions, Rota showed the importance of this theory in combinatorial mathematics and gave a deep treatment of it. He noted the relation between such topics as inclusion-exclusion, classical number theoretic Möbius inversion, coloring problems and flows in networks. Since then, under the strong influence of Rota, the theory of Möbius inversion and related topics has become an active area of combinatorics.

関連項目

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

参考文献

• テンプレート:Apostol IANT
• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• K. Ireland, M. Rosen. A Classical Introduction to Modern Number Theory, (1990) Springer-Verlag.

外部リンク

• Möbius Inversion Formula at ProofWiki
• Weisstein, Eric W. “Möbius Transform”. MathWorld（英語）.