|
|
| 1行目: |
1行目: |
| − | {{簡易区別|[[メビウス変換]] (Möbius transformation) }} | + | {{テンプレート:20180815sk}} |
| − | [[数学]]において、古典的な'''メビウスの反転公式''' (Möbius inversion formula) は[[アウグスト・フェルディナント・メビウス]] (August Ferdinand Möbius) によって19世紀に[[数論]]に導入された。
| |
| − | | |
| − | [[約数|整除関係]]によって[[順序集合|順序]]付けられた自然数という古典的な場合に、別の{{仮リンク|局所有限半順序集合|label=局所有限半順序集合|en|Locally finite poset}}が取って代わると、他のメビウス反転公式が得られる。説明は[[隣接代数 (順序理論)|隣接代数]]を参照。
| |
| − | | |
| − | ==古典的な反転公式==
| |
| − | 古典的なバージョンは次のようなものである。{{mvar|g}} と {{mvar|f}} が、すべての正の整数 {{mvar|n}} に対して
| |
| − | | |
| − | : <math>g(n)=\sum_{d\,\mid \,n}f(d)</math>
| |
| − | | |
| − | を満たす[[数論的関数]]であれば、すべての正の整数 {{mvar|n}} に対して
| |
| − | | |
| − | :<math>f(n)=\sum_{d\,\mid\, n}\mu(d)g(n/d)</math>
| |
| − | | |
| − | が成り立つ。ここで {{math|μ}} は[[メビウス関数]]であり、和は {{mvar|n}} のすべての正の[[約数]] {{mvar|d}} を渡る。要するに、もとの {{math|''f'' (''n'')}} は {{math|''g'' (''n'')}} が与えられると反転公式を用いて決定することができる。2つの数列は互いの'''メビウス変換''' (Möbius transform) と呼ばれる。
| |
| − | | |
| − | 公式は {{mvar|f}} と {{mvar|g}} が正の整数から（'''Z'''-[[環上の加群|加群]]と見た）[[アーベル群]]への関数であるときにも正しい。
| |
| − | | |
| − | {{仮リンク|ディリクレの畳み込み|en|Dirichlet convolution}}を用いて、最初の式を
| |
| − | | |
| − | :<math>g=f*1</math>
| |
| − | | |
| − | と書くことができる。ここに {{math|*}} はディリクレの畳み込みを表し、{{math|1}} は[[定数関数]] <math>1(n)=1</math> である。すると二番目の式は
| |
| − | | |
| − | :<math>f=\mu * g</math>
| |
| − | | |
| − | と書ける。多くの具体例は[[乗法的関数]]の記事で与えられている。
| |
| − | | |
| − | 定理は {{math|*}} が（可換かつ）結合的であり、{{math|1 * μ {{=}} ε}} であることから従う、ただし {{math|ε}} はディリクレの畳み込みに対する単位元であり、{{math|ε(1) {{=}} 1}} および {{math|''n'' > 1}} に対して {{math|ε(''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>
| |
| − | | |
| − | である。変換は級数によって関連付けられる。{{仮リンク|ランベルト級数|en|Lambert series}}
| |
| − | | |
| − | :<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> に対して変換を繰り返し適用していくと
| |
| − | | |
| − | #<math>\varphi,</math> トーシェント関数
| |
| − | #<math>\varphi*1=\operatorname{Id},</math> [[恒等写像]]
| |
| − | #<math>\operatorname{Id} *1 =\sigma_1 =\sigma,</math> [[約数関数]]
| |
| − | | |
| − | メビウスの関数自身から始めると、
| |
| − | #<math>\mu,</math> メビウス関数
| |
| − | #<math>\mu*1 = \varepsilon,</math> ただし <math>\varepsilon(n) = \begin{cases} 1, & \mbox{if }n=1 \\ 0, & \mbox{if }n>1 \end{cases} </math> は {{仮リンク|unit function|en|unit function}}
| |
| − | #<math>\varepsilon*1 = 1,</math> [[定値写像]]
| |
| − | #<math>1*1=\sigma_0=\operatorname{d}=\tau,</math> ただし <math>\operatorname{d}=\tau</math> は {{mvar|n}} の約数の個数（[[約数関数]]参照）
| |
| − | | |
| − | これらのリストのいずれも、両方向に無限に伸びる。メビウスの反転公式によって逆向きに行くことができる。
| |
| − | | |
| − | 例として、<math>\varphi</math> で始まる列は：
| |
| − | | |
| − | <math>
| |
| − | 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}
| |
| − | </math>
| |
| − | | |
| − | 生成される列は、対応する[[ディリクレ級数]]を考えることによってより容易に理解できるかもしれない。各変換は[[リーマンのゼータ関数]]を掛けることに対応する。
| |
| − | | |
| − | ==一般化==
| |
| − | {{See also|[[隣接代数 (順序理論)|隣接代数]]}}
| |
| − | [[組合せ数学]]においてより有用な反転公式は次のようなものである。''F'' (''x'') と ''G'' (''x'') は[[区間 (数学)|区間]] <nowiki>[1, ∞)</nowiki> 上で定義された[[複素数]]値[[関数 (数学)|関数]]であって、
| |
| − | | |
| − | :<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> が{{仮リンク|ディリクレ逆元|en|Dirichlet inverse}} <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>
| |
| − | | |
| − | となる。
| |
| − | | |
| − | この公式を使う簡単な例は、{{仮リンク|既約分数|en|reduced fraction}} {{math|0 < ''a'' / ''b'' < 1}} の個数を数えることである。ここで ''a'' と ''b'' は互いに素で ''b'' ≤ ''n'' である。''f'' (''n'') をこの個数とすれば、''g'' (''n'') は ''b'' ≤ ''n'' なる分数 {{math|0 < ''a'' / ''b'' < 1}} の総数である。ここで ''a'' と ''b'' は互いに素である必要はない。（なぜならば、{{math|gcd (''a'', ''b'') {{=}} ''d''}} かつ {{math|''b'' ≤ ''n''}} なるすべての分数 {{math|''a'' / ''b''}} は {{math|''b'' / ''d'' ≤ ''n'' / ''d''}} なる分数 (''a'' / ''d'' ) / (''b'' / ''d'' ) に簡約でき、逆もまた然りであるからだ。）{{math|''g'' (''n'') {{=}} ''n'' (''n'' − 1) / 2}} であることを確かめるのは容易だが、{{math|''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>, つまり、{{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>
| |
| − | | |
| − | 二つ目の一般化では {{math|α(''n'')}} が {{math|1}} に取って代わるが、証明は本質的に同一である。
| |
| − | | |
| − | == Weisner, Hall, Rota の貢献==
| |
| − | {{Quotation|
| |
| − | The statement of the general Möbius inversion formula was first given independently by [[Louis Weisner|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, [[Gian-Carlo Rota|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.<ref>{{cite journal|author=Bender, Edward A.|author2=Goldman, J. R.|title=On the applications of Mö inversion in combinatorial analysis|journal=Amer. Math. Monthly|volume=82|year=1975|pages=789–803|url=http://www.maa.org/programs/maa-awards/writing-awards/on-the-applications-of-m-bius-inversion-in-combinatorial-analysis}}</ref>
| |
| − | }}
| |
| − | | |
| − | ==関連項目==
| |
| − | * [[包除原理]]
| |
| − | * [[ファレイ数列]]
| |
| − | * [[隣接代数 (順序理論)]]
| |
| − | ==参考文献==
| |
| − | * {{Apostol IANT}}
| |
| − | * {{SpringerEOM|id=M/m130180 |title=Möbius inversion |first=Joseph P.S. |last=Kung}}
| |
| − | *K. Ireland, M. Rosen. ''A Classical Introduction to Modern Number Theory'', (1990) Springer-Verlag.
| |
| − | | |
| − | {{reflist}}
| |
| − | | |
| − | ==外部リンク==
| |
| − | *[http://proofwiki.org/wiki/M%C3%B6bius_Inversion_Formula Möbius Inversion Formula] at [http://www.proofwiki.org ProofWiki]
| |
| − | *{{MathWorld|MoebiusTransform|Möbius Transform}}
| |
| − | | |
| − | {{DEFAULTSORT:めひうすのはんてんこうしき}}
| |
| − | [[Category:整数論的関数]]
| |
| − | <!--[[Category:Enumerative combinatorics]]-->
| |
| − | [[Category:順序構造]]
| |
| − | [[Category:数論]]
| |
| − | [[Category:数学に関する記事]]
| |
| − | | |
| − | [[ru:Функция Мёбиуса#Обращение Мёбиуса]]
| |