メビウス反転式

数学において、古典的なメビウスの反転公式は、それぞれが約数上の和によって定義される算術関数のペアの関係です。これは、1832年にアウグスト・フェルディナント・メビウスによって数論に導入されました。^[1]

この公式の大規模な一般化は、任意の局所有限な半順序集合上の和に適用され、メビウスの古典的な公式は割り切れる順に順序付けられた自然数の集合に適用されます。接続代数を参照してください。

古典的なバージョンでは、gとfが次の式を満たす 算術関数である場合、

${\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について}$

ここで、μ はメビウス関数であり、和はnのすべての正の約数 dに及びます(上記の式では で示されています)。実際には、元のf ( n ) は、 g ( n )が与えられれば、反転式を使用して決定できます。2 つのシーケンスは、互いの メビウス変換であると言われています。${\displaystyle d\mid n}$

fとg が正の整数から何らかのアーベル群への関数（Z加群として見られる） である場合にも、この式は正しいです。

ディリクレ畳み込みの言語では、最初の式は次のように書ける。

${\displaystyle g={\mathit {1}}*f}$

ここで、∗ はディリクレ畳み込みを表し、1 は定数関数 1 ( n ) = 1である。2番目の式は次のように書かれる。

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

乗法関数に関する記事には、多くの具体的な例が示されています。

この定理は、 ∗が（可換かつ）結合的であり、1 ∗ μ = ε であるため成り立つ。ここでε はディリクレ畳み込みの恒等関数であり、n > 1のすべてにおいてε (1) = 1、ε ( n ) = 0 の値をとる。したがって、

${\displaystyle \mu *g=\mu *({\mathit {1}}*f)=(\mu *{\mathit {1}})*f=\varepsilon *f=f}$。

を に置き換えると、メビウス反転公式の積バージョンが得られます。 ${\displaystyle f,g}$${\displaystyle \ln f,\ln g}$

${\displaystyle g(n)=\prod _{d|n}f(d)\iff f(n)=\prod _{d|n}g\left({\frac {n}{d}}\right)^{\mu (d)},\forall n\geq 1.}$

させて

${\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}}}}$

ここでζ ( s )はリーマンゼータ関数である。

算術関数が与えられた場合、最初の合計を繰り返し適用することで、他の算術関数の双無限シーケンスを生成できます。

たとえば、オイラーのトーティエント関数 φから始めて、変換プロセスを繰り返し適用すると、次のようになります。

1. φトーティエント関数
2. φ ∗ 1 = I、ここでI ( n ) = n は恒等関数である
3. I ∗ 1 = σ ₁ = σ、除数関数

開始関数がメビウス関数自体である場合、関数のリストは次のようになります。

1. μ、メビウス関数
2. μ ∗ 1 = εここで単位関数$${\displaystyle \varepsilon (n)={\begin{cases}1,&{\text{if }}n=1\\0,&{\text{if }}n>1\end{cases}}}$$
3. ε ∗ 1 = 1、定数関数
4. 1 ∗ 1 = σ ₀ = d = τ、ここでd = τ はnの約数の個数です（約数関数を参照）。

これらの関数のリストは両方とも両方向に無限に拡張されます。メビウスの反転公式により、これらのリストを逆方向に走査することができます。

例として、φで始まるシーケンスは次のようになります。

${\displaystyle f_{n}={\begin{cases}\underbrace {\mu *\ldots *\mu } _{-n{\text{ factors}}}*\varphi &{\text{if }}n<0\\[8px]\varphi &{\text{if }}n=0\\[8px]\varphi *\underbrace {{\mathit {1}}*\ldots *{\mathit {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\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に及びます。

これは、より一般的な形式の特別なケースです。α ( n ) がディリクレ逆関数α ⁻¹ ( 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 に対して。}$

前の式は定数関数α ( n ) = 1の特殊なケースで生じ、そのディリクレ逆関数はα ⁻¹ ( n ) = μ ( 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 (⌊ x ⌋)およびG ( x ) = g (⌊ x ⌋)と定義すると、次の式が導かれます。

${\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 に対して。}$

この公式の簡単な使用例は、約分数の数を数えることです 。0 < ⁠1つの/b⁠ < 1、ただしaとb は互いに素で、 b ≤ n。この数をf ( n )とすると、 g ( n ) は0 < ⁠の分数の総数です1つの/b⁠ < 1 かつb ≤ nであり、 aとb は必ずしも互いに素であるとは限りません。（これは、すべての分数が1つの/b⁠ gcd( a , b ) = dかつb ≤ nの場合、分数に簡約できます⁠a / d/b / d⁠と⁠b/d⁠ ≤ ⁠ん/d⁠ 、逆もまた同様です。) ここで、 g ( n ) = ⁠を決定するのは簡単ですｎ（ｎ −１）/2⁠ですが、 f ( n )の計算はより困難です。

別の反転式は次のようになります (関係する級数が絶対収束すると仮定します)。

${\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{ for all }}x\geq 1.}$

上と同様に、これはα ( n )がディリクレ逆関数α ⁻¹ ( 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{ for all }}x\geq 1.}$

例えば、リーマンゼータ関数と素数ゼータ関数を関連付けるよく知られた証明があり、これは、 のときの前の式のメビウス反転の級数ベースの形式を使用する。すなわち、の オイラー積表現によって、${\displaystyle s=1}$${\displaystyle \zeta (s)}$${\displaystyle \Re (s)>1}$

${\displaystyle \log \zeta (s)=-\sum _{p\mathrm {\ prime} }\log \left(1-{\frac {1}{p^{s}}}\right)=\sum _{k\geq 1}{\frac {P(ks)}{k}}\iff P(s)=\sum _{k\geq 1}{\frac {\mu (k)}{k}}\log \zeta (ks),\Re (s)>1.}$

メビウス反転の別の形式に対するこれらの恒等式は、に見られる。^[2] 次の接続代数の節で部分的に引用されているメビウス反転公式のより一般的な理論は、ロタによって構築されている。^[3]

メビウス反転は任意のアーベル群に適用されるため、群演算が加算として記述されるか乗算として記述されるかは関係ありません。これにより、反転式の表記法の次の変形が生じます。

${\displaystyle {\mbox{if }}F(n)=\prod _{d|n}f(d),{\mbox{ then }}f(n)=\prod _{d|n}F\left({\frac {n}{d}}\right)^{\mu (d)}.}$

最初の一般化は次のように証明できる。[条件]は条件の指示関数であり、条件が真の場合は1、偽の場合は0であるという アイバーソンの慣例を使用する。

${\displaystyle \sum _{d|n}\mu (d)=\varepsilon (n),}$

つまり、であり、 は単位関数です。 ${\displaystyle 1*\mu =\varepsilon }$${\displaystyle \varepsilon }$

以下のものがあります:

${\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{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を置き換えるより一般的なケースでの証明は、2番目の一般化と同様に本質的に同一です。

半順序関係を持つ集合P に対して、Pのメビウス関数を次のように再帰的に 定義する。${\displaystyle \leq }$${\displaystyle \mu }$

${\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.}$

（ここでは和が有限であると仮定する。）すると、Kが可換環であるとき、 ${\displaystyle f,g:P\to 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.}$

(スタンレーの『列挙的組合せ論』第 1 巻、第 3.7 節を参照) 古典的な算術メビウス関数は、割り切れる順に並べられた正の整数のposet Pの特殊なケースです。つまり、正の整数s、t に対して、半順序をsがtの約数であることを意味するように定義します。 ${\displaystyle s\preccurlyeq t}$

一般的なメビウス反転公式（半順序集合用）の記述は、ワイスナー（1935）とフィリップ・ホール（1936）によって独立して初めて与えられた。著者らはどちらも群論の問題に動機づけられていた。どちらの著者も自分の研究の組み合わせ論的意味に気づいていなかったようで、メビウス関数の理論を展開しなかった。メビウス関数に関する基礎論文で、ロータは組み合わせ数学におけるこの理論の重要性を示し、それを深く扱った。彼は包含排他性、古典的な数論的メビウス反転、着色問題、ネットワークの流れなどのトピック間の関係を指摘した。それ以来、ロータの強い影響を受けて、メビウス反転の理論と関連するトピックは、組み合わせ論の活発な分野となった。^[4]

• フェアリー数列
• 包含・排除の原則

• アポストル、トム・M. (1976)、解析的数論入門、数学の学部テキスト、ニューヨーク-ハイデルベルグ：シュプリンガー・フェアラーク、ISBN 978-0-387-90163-3、MR  0434929、Zbl  0335.10001
• ベンダー、エドワード A.; ゴールドマン、J. R. (1975)、「組み合わせ解析におけるメビウス反転の応用について」、アメリカ数学月刊誌、82 (8): 789–803、doi :10.2307/2319793、JSTOR  2319793
• アイルランド、K.; ローゼン、M. (2010)、現代数論への古典的入門、数学の大学院テキスト（第84巻）（第2版）、シュプリンガー・フェアラーク、ISBN 978-1-4419-3094-1
• クン、ジョセフ PS (2001) [1994]、「メビウス反転」、数学百科事典、EMS プレス
• メビウス、AF (1832)、「Uber eine besondere Art von Umkehrung der Reihen.」、Journal für die reine und angewandte Mathematik、9 : 105–123
• スタンレー、リチャード P. (1997)、列挙的組合せ論、第 1 巻、ケンブリッジ大学出版局、ISBN 0-521-55309-1
• スタンレー、リチャード P. (1999)、列挙的組合せ論、第 2 巻、ケンブリッジ大学出版局、ISBN 0-521-56069-1

• ワイスタイン、エリック・W.「メビウス変換」。マスワールド。