メビウスの反転公式

ウィキペディア

メビウスの反転公式

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/04/17 05:14 UTC 版)

メビウス変換 (Möbius transformation) とは異なります。

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

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

古典的な反転公式

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

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

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

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

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

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

ディリクレの畳み込み（英語版）を用いて、最初の式を

${\displaystyle g=f*1}$

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

${\displaystyle f=\mu *g}$

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

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

級数関係

${\displaystyle a_{n}=\sum _{d\mid n}b_{d}}$

とすると、変換は

${\displaystyle b_{n}=\sum _{d\mid n}\mu \left({\frac {n}{d}}\right)a_{d}}$

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

${\displaystyle \sum _{n=1}^{\infty }a_{n}x^{n}=\sum _{n=1}^{\infty }b_{n}{\frac {x^{n}}{1-x^{n}}}}$

やディリクレ級数

${\displaystyle \sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}=\zeta (s)\sum _{n=1}^{\infty }{\frac {b_{n}}{n^{s}}}}$

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

繰り返しの変換

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

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

1. ${\displaystyle \varphi ,}$ トーシェント関数
2. ${\displaystyle \varphi *1=\operatorname {Id} ,}$ 恒等写像
3. ${\displaystyle \operatorname {Id} *1=\sigma _{1}=\sigma ,}$ 約数関数

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

1. ${\displaystyle \mu ,}$ メビウス関数
2. ${\displaystyle \mu *1=\varepsilon ,}$ ただし ${\displaystyle \varepsilon (n)={\begin{cases}1,&{\mbox{if }}n=1\\0,&{\mbox{if }}n>1\end{cases}}}$　は unit function（英語版）
3. ${\displaystyle \varepsilon *1=1,}$ 定値写像
4. ${\displaystyle 1*1=\sigma _{0}=\operatorname {d} =\tau ,}$ ただし ${\displaystyle \operatorname {d} =\tau }$ は n の約数の個数（約数関数参照）

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

例として、${\displaystyle \varphi }$ で始まる列は：

${\displaystyle f_{n}={\begin{cases}\underbrace {\mu *\ldots *\mu } _{-n{\text{ factors}}}*\varphi &{\text{if }}n<0\\\varphi &{\text{if }}n=0\\\varphi *\underbrace {1*\ldots *1} _{n{\text{ factors}}}&{\text{if }}n>0\end{cases}}}$

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

一般化

「隣接代数」も参照

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

${\displaystyle G(x)=\sum _{1\leq n\leq x}F(x/n)\quad {\mbox{ for all }}x\geq 1}$

であれば、

${\displaystyle F(x)=\sum _{1\leq n\leq x}\mu (n)G(x/n)\quad {\mbox{ for all }}x\geq 1}$

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

これはさらに一般化される。${\displaystyle \alpha (n)}$ がディリクレ逆元（英語版） ${\displaystyle \alpha ^{-1}(n)}$ を持つ数論的関数であるとき、

${\displaystyle G(x)=\sum _{1\leq n\leq x}\alpha (n)F(x/n)\quad {\mbox{ for all }}x\geq 1}$

と定義すると、

${\displaystyle F(x)=\sum _{1\leq n\leq x}\alpha ^{-1}(n)G(x/n)\quad {\mbox{ for all }}x\geq 1}$

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

これらの拡張のうち 1 つ目を適用できる例として、正の整数上定義された（複素数値）関数 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{ for all }}n\geq 1}$

なるものがあるとき、${\displaystyle F(x)=f(\lfloor x\rfloor )}$ および ${\displaystyle 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{ for all }}n\geq 1}$

となる。

この公式を使う簡単な例は、既約分数 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) は計算が難しい。

別の反転公式は、

${\displaystyle {\begin{aligned}&&g(x)&=\sum _{m=1}^{\infty }{\frac {f(mx)}{m^{s}}}&{\mbox{for all }}x\geq 1\\&\Longleftrightarrow &f(x)&=\sum _{m=1}^{\infty }\mu (m){\frac {g(mx)}{m^{s}}}&{\mbox{for all }}x\geq 1\end{aligned}}}$

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

${\displaystyle {\begin{aligned}&&g(x)&=\sum _{m=1}^{\infty }\alpha (m){\frac {f(mx)}{m^{s}}}&{\mbox{for all }}x\geq 1\\&\Longleftrightarrow &f(x)&=\sum _{m=1}^{\infty }\alpha ^{-1}(m){\frac {g(mx)}{m^{s}}}&{\mbox{for all }}x\geq 1\end{aligned}}}$

乗法的表記

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

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

ならば

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

一般化の証明

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

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

${\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 x/n}f\left({\frac {x}{mn}}\right)\\&=\sum _{1\leq n\leq x}\mu (n)\sum _{1\leq m\leq 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 x/n}[m=r/n]\qquad {\text{rearranging the summation order}}\\&=\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)\varepsilon (r)\\&=f(x)\qquad {\text{since }}\varepsilon (r)=0{\text{ except when }}r=1\end{aligned}}}$

二つ目の一般化では α(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.^[1]

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

関連項目

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

参考文献

• Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR0434929, Zbl 0335.10001 
• Kung, Joseph P.S. (2001), "Möbius inversion", in Hazewinkel, Michiel (ed.), Encyclopaedia of Mathematics, Springer, ISBN 978-1-55608-010-4。
• K. Ireland, M. Rosen. A Classical Introduction to Modern Number Theory, (1990) Springer-Verlag.

脚注

1. ^ Bender, Edward A.; Goldman, J. R. (1975). “On the applications of Mö inversion in combinatorial analysis”. Amer. Math. Monthly 82: 789–803. http://www.maa.org/programs/maa-awards/writing-awards/on-the-applications-of-m-bius-inversion-in-combinatorial-analysis. 

外部リンク

• 『メビウスの反転公式の証明と応用』 - 高校数学の美しい物語
• Möbius Inversion Formula at ProofWiki
• Weisstein, Eric W. "Möbius Transform". MathWorld (英語).

ウィキペディア小見出し辞書

メビウスの反転公式

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/19 06:15 UTC 版)

「メビウス関数」の記事における「メビウスの反転公式」の解説

詳細は「メビウスの反転公式」を参照 関数 f(n), g(n) について、次の 2 つの命題は同値である。 g ( n ) = ∑ d ∣ n f ( d ) . f ( n ) = ∑ d ∣ n g ( d ) μ ( n d ) . これをメビウスの反転公式という。