メビウス反転公式

数学において、古典的なメビウスの反転公式は、それぞれが約数に関する和によって互いに定義される算術関数のペア間の関係である。これは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（で示される）にわたって展開される。${\displaystyle d\mid n}$上記の式において）。実際には、反転公式を用いることで、 g ( n )が与えられた場合に元のf ( n )を決定することができる。この2つの数列は互いにメビウス変換であると言われる。

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

それから

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

ここで、和はx以下のすべての正の整数nに及ぶ。

これは、より一般的な形式の特殊なケースです。α ( n )がディリクレ逆関数α ^-1 ( n )を持つ算術関数である場合、次のように定義できます。

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

それから

${\displaystyle F(x)=\sum _{1\leq n\leq x}\alpha ^{-1}(n)G\left({\frac {x}{n}}\right)\quad {\mbox{ for all }}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{ for all }}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{ 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 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 ]}に記載されています。 次の接続代数に関するセクションで部分的に引用されているメビウス反転公式のより一般的な理論は、Rota によって^{[ 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に対して、半順序関係を備えた集合${\displaystyle \leq }$メビウス関数を定義する${\displaystyle \mu }$Pの再帰的に

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

（ここでは総和が有限であると仮定する。）すると、${\displaystyle f,g:P\to K}$ここで、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節を参照。）

古典的な算術メビウス関数は、正の整数の半順序集合Pを整除性で順序付けた特殊なケースです。つまり、正の整数s、t に対して、半順序を定義します。${\displaystyle s\preccurlyeq t}$sがtの約数であることを意味する。冪集合上では${\displaystyle {\mathcal {P}}(S)}$集合の${\displaystyle S}$注文者${\displaystyle \subseteq }$（集合の包含関係）では、メビウスの反転定理は包含排除原理を再現し、集合上で${\displaystyle \mathbb {N} }$自然数の標準（全）順序付けによる${\displaystyle \leq }$この定理は、微積分学の基本定理の離散版と一致します（スタンレーの『列挙的組合せ論』第1巻、第3.8節を参照）。科学の様々な分野で、相互作用の多くの尺度は、異なる半順序集合上のメビウス反転として定式化できます。例としては、ゲーム理論のシャプレー値、統計力学の最大エントロピー相互作用、遺伝学のエピスタシス、情報理論の相互作用情報、全相関、 部分情報分解などがあります。^{[ 4 ]}

半順序集合に対する一般的なメビウス反転公式の記述は、最初にワイズナー（1935年）とフィリップ・ホール（1936年）によって独立に提示されました。両著者とも群論の問題に触発されていました。両著者とも自身の研究の組み合わせ論的な意味合いに気付いておらず、メビウス関数の理論を発展させることもありませんでした。メビウス関数に関する基礎的な論文で、ロータはこの理論が組み合わせ論において重要であることを示し、深く考察しました。彼は、包含排除、古典的な数論的メビウス反転、彩色問題、ネットワークにおける流れといったトピック間の関係性に着目しました。それ以来、ロータの強い影響の下、メビウス反転の理論と関連するトピックは組み合わせ論の活発な分野となっています。^{[ 5 ]}

• ファレー症候群
• 包含排除原理

• アポストル、トム M. (1976)、解析的整数論入門、数学学部教科書、ニューヨーク-ハイデルベルク：シュプリンガー・フェルラーク、ISBN 978-0-387-90163-3MR 0434929、Zbl 0335.10001​  
• Bender, Edward A.; Goldman, J.  R. (1975)、「組合せ解析におけるメビウス反転の応用について」、Amer. Math. Monthly、82 (8): 789–803、doi : 10.2307/2319793、JSTOR 2319793 
• Ireland, K.; Rosen, M. (2010), 『現代数論への古典的入門』、大学院数学テキスト（第84巻）（第2 版）、Springer-Verlag、ISBN 978-1-4419-3094-1
• Kung, Joseph PS (2001) [1994]、「メビウス反転」、数学百科事典、EMS Press
• メビウス、AF (1832)、「Uber eine besondere Art von Umkehrung der Reihen」。、数学ジャーナル、9 : 105–123
• スタンレー、リチャード P. (1997)、『列挙的組合せ論』第 1 巻 、ケンブリッジ大学出版局、ISBN 0-521-55309-1
• スタンレー、リチャード P. (1999)、『列挙的組合せ論』第 2 巻 、ケンブリッジ大学出版局、ISBN 0-521-56069-1

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