つい先日、「Möbius の反転公式」が実は単に集合の包除関係を素直に表しただけの式でしかない、ということを理解した。「なんだ、わざわざ Möbius 関数なんてものを定義して和の形に書いたりするのはややオーバーで、内実はそこまでしなくても素朴に理解できるような単純な話だったのか…！」と恥じ入りながら検索してみると、どうもそういう観点から説明しているものが見当たらない。いや、やはり検索の上位でヒットした所をいくつか見ただけなので、下位の方はそうでもない、というだけの話かもしれないけれど、とにかく目についた範囲内ではどれも「逆変換の式に代入してみると Möbius 関数の性質によって Kronecker delta が現れ期待通りの式が出てきてくれる」という流れだった。
その示し方が悪いとは言わない。紙数を使わずに簡潔に示す上ではそれが最善だろう。また、和を使って畳み込みの形に書いておくことで、畳み込みを演算とする群構造が現れて、そこで基本関数の間にこんな関係が成り立つ、といった話に発展させられるということはもちろん説明する価値がある面白い話だ。ただ、そういったことは、まず「やってるのは要するにこういう単純な話だ」ということをちゃんと理解した上で、「その上にこういう綺麗な構造を載せることができる」という理解の仕方をすべきではないだろうか。その両者がセットでないと、せっかくの「抽象化のご利益」がそこにある、ということもはっきりと意識できなくなってしまうだろう。また、上述のような、逆変換の式を天下り式に与えた証明だと、「いったいどうやってこの式は出てきたのか？また、Möbius 関数の謎めいた定義はどうやって出てきたのか？」という点がさっぱり見えてこない。
そこで、（例によって主目的は自己満足だが、）反転公式が単に集合の包除関係を表した式に過ぎない、ということの説明をここで公開しておこうと思う。ご覧になった方の参考になれば幸い。
まず、記法の定義と確認から。自然数（ここでは、\(0\) は除く）を定義域とする関数 \(F(n)\), \(G(n)\) があって、
\begin{equation}
\label{eq:44-1}
G(n) = \sum_{d \mid n} F(d) \qquad (n \geqq 1)
\end{equation}
がなりたっているとする。ここで、条件「\(d \mid n\)」には \(d\), \(n\) ２つの文字が含まれているが、\(n\) は外部によって既に値が決まってるので、和をとる時に動かすことができるのは \(d\) の方だけ。つまりこの \(\sum_{d \mid n}\) は「\(n\) の（正の）約数 \(d\) 全体にわたる和」と解釈すべきもの。例えば \(2\)の約数は \(1\), \(2\) だから
\[ G(2) = F(1)+F(2) \]
で、\(6\) の約数は \(1\), \(2\), \(3\), \(6\) だから
\[ G(6) = F(1)+F(2)+F(3)+F(6) \]
という具合。
\eqref{eq:44-1}は、\(G(n)\) の定義式であってもいいし、単に「すべての \(n\) についてなりたつ」だけの式でもいいんだけど、いずれにしろ「\(G\) を \(F\) で表す」という形の式になっている。これを逆に解いて「\(F\) を \(G\) で表す」ことが実はできるよ、というのが Möbius の反転公式で、こんな式になっている。
\begin{align}
F(n) &= \sum_{d \mid n} \mu \Bigl( \frac{n}{d} \Bigr) G(d) \notag\\
\label{eq:44-2}
&= \sum_{d \mid n} \mu(d) G\Bigl( \frac{n}{d} \Bigr)
\end{align}
ここで、\(\mu(n)\) は Möbius 関数と呼ばれる関数で、次のように定義される。\(n\) の素因数にダブリが１つでもあれば \(\mu(n)=0\)。ダブリがないときは、異なる素因数の個数の偶奇に応じて \(\mu(n) = \pm 1\)。例えば \(12\) を素因数分解すると \(2^{2}\cdot 3\) で、素因数 \(2\) がダブっているので \(\mu(12)=0\)。\(30=2\cdot 3\cdot 5\) は素因数にダブリがなく、素因数は \(2\), \(3\), \(5\) の３種（奇数）なので \(\mu(30)=-1\)。\(1\) は素因数が \(0\) 個と見て、\(\mu(1)=1\)。
\eqref{eq:44-2}の具体例をいくつか書いてみると
\begin{align*}
F(2) &= \mu(1) G\Bigl( \frac{2}{1} \Bigr) + \mu(2) G\Bigl( \frac{2}{2} \Bigr) \\
&= G(2) – G(1) \\
F(4) &= \mu(1) G\Bigl( \frac{4}{1} \Bigr) + \mu(2) G\Bigl( \frac{4}{2} \Bigr) + \mu(4) G\Bigl( \frac{4}{4} \Bigr) \\
&= G(4) – G(2) + G(1) \\
F(12) &= \mu(1) G\Bigl( \frac{12}{1} \Bigr) + \mu(2) \Bigl( \frac{12}{2} \Bigr) + \mu(3) G\Bigl( \frac{12}{3} \Bigr) + \mu(4) G\Bigl( \frac{12}{4} \Bigr) + \mu(6) G\Bigl( \frac{12}{6} \Bigr) + \mu(12) G\Bigl( \frac{12}{12} \Bigr) \\
&= G(12) – G(6) – G(4) + G(2)
\end{align*}
といった具合。
確認が済んだところで、「なぜ、\eqref{eq:44-2}がなりたつのか」の説明に入って行こう。まずは \(n=2^{2} \cdot 3^{3}\) に対する \(G(n)\) を、\eqref{eq:44-1}に従って書き下してみる。\(n\) が素因数分解されていることにより、約数を漏れなく、重複なく列挙することが系統的に可能になっている。
\begin{align*}
G(2^{2} \cdot 3^{3}) &= F(2^{2}\cdot 3^{3}) + F(2^{1} \cdot 3^{3}) +F(2^{0}\cdot 3^{3}) &&\leftarrow\quad \text{\(3\) が\(3\)個} \\
&+ F(2^{2}\cdot 3^{2}) + F(2^{1} \cdot 3^{2}) + F(2^{0}\cdot 3^{2}) &&\leftarrow\quad \text{\(3\) が\(2\)個} \\
&+ F(2^{2}\cdot 3^{1}) + F(2^{1} \cdot 3^{1}) + F(2^{0}\cdot 3^{1}) &&\leftarrow\quad \text{\(3\) が\(1\)個} \\
&+ F(2^{2}\cdot 3^{0}) + F(2^{1} \cdot 3^{0}) + F(2^{0}\cdot 3^{0}) &&\leftarrow\quad \text{\(3\) が\(0\)個}
\end{align*}
これを見ると、右辺のあちこちに \(G(n)\) で表せる部分があることに気づかないだろうか。
これより、次の等式がなりたつ。
\begin{equation}
\label{eq:44-3}
G(2^{2} \cdot 3^{3}) = F(2^{2} \cdot 3^{3}) + \color{green}{\underbrace{G(2^{1} \cdot 3^{3})}_{\text{緑の部分}} }+ \color{blue}{\underbrace{G(2^{2} \cdot 3^{2})}_{\text{青の部分}} } – \color{red}{\underbrace{G(2^{1} \cdot 3^{2})}_{\text{ダブった赤の部分を引く}}}
\end{equation}
よって、移項すれば \(F\) を \(G\) で表すことができて、
\begin{equation}
\label{eq:44-4}
F(2^{2} \cdot 3^{3}) = G(2^{2} \cdot 3^{3}) – G(2^{1} \cdot 3^{3}) – G(2^{2} \cdot 3^{2}) + G(2^{1} \cdot 3^{2})
\end{equation}
となる。
さて、\eqref{eq:44-3}を振り返ってみよう。この右辺の \(G\) で表される項の部分は、集合の要素数の基本関係式
\[ \#(A \cup B) = \color{green}{\#(A)} + \color{blue}{\#(B)} – \color{red}{\#(A \cap B)} \]
と本質的に同じメカニズムで出てきていることが見てとれるだろう。
\eqref{eq:44-3}で \(A\), \(B\) に当たる集合は何かというと、全体集合を「\(n=2^{2}\cdot 3^{3}\) の約数全体」としたとき、\(A\) は「素因数 \(2\) の個数が \(1\) 個以下の元の集合」で、\(B\) は「素因数 \(3\) の個数が \(2\) 個以下の元の集合」である。言い換えると
\begin{align*}
\color{green}{A} &= \color{green}{\text{素因数 \(2\) の個数が \(n\) より \(1\) 個以上少ない元の集合}} \\
\color{blue}{B} &= \color{blue}{\text{素因数 \(3\) の個数が \(n\) より \(1\) 個以上少ない元の集合}}
\end{align*}
である。この書き方に従えば
\[ \color{red}{A \cap B} = \color{red}{\text{素因数 \(2\), \(3\) の個数が共に \(n\) より \(1\) 個以上少ない元の集合}} \]
であって、それぞれの集合上にわたる \(F\) の値の和が
\begin{align*}
\color{green}{\sum_{d \in A} F(d)} &= \color{green}{G(2^{1} \cdot 3^{3}) = G\biggl( \frac{n}{2} \biggr)} \\
\color{blue}{\sum_{d \in B} F(d)} &= \color{blue}{G(2^{2} \cdot 3^{2}) = G\biggl( \frac{n}{3} \biggr)} \\
\color{red}{\sum_{d \in A \cap B} F(d)} &= \color{red}{G(2^{1} \cdot 3^{2}) = G\biggl( \frac{n}{2\cdot 3} \biggr)}
\end{align*}
のように \(G\) を使って書けている。すなわち、\eqref{eq:44-4}は
\[ F(n) = G(n) – G\biggl( \frac{n}{2} \biggr) – G\biggl( \frac{n}{3} \biggr) + G\biggl( \frac{n}{2\cdot 3} \biggr) \quad (n=2^{2} \cdot 3^{3}) \]
という式である。
今の場合、\(n\) の素因数が \(2\), \(3\) の \(2\) 種類だったが、\(3\) 種類の場合もまったく同様である。\(n\) の素因数が \(2\), \(3\), \(5\) だったとして、全体集合を \(n\) の約数全体とし、
\begin{align*}
A &= \text{素因数 \(2\) の個数が \(n\) より \(1\) 個以上少ない元の集合} \\
B &= \text{素因数 \(3\) の個数が \(n\) より \(1\) 個以上少ない元の集合} \\
C &= \text{素因数 \(5\) の個数が \(n\) より \(1\) 個以上少ない元の集合}
\end{align*}
とすれば、「\(n\) の約数のうち、\(n\) 自身を除く全体」が「\(n\) に比べて素因数のいずれかが \(1\) 個以上少ないもの全体」すなわち \(A \cup B \cup C\) になっている。よって、合併の要素数が
\[ \#(A \cup B \cup C) = \#(A) + \#(B) + \#(C) – \#(A \cap B) – \#(B \cap C)
– \#(C \cap A) + \#(A \cap B \cap C) \]
となっていたこととまったく同様にして、\eqref{eq:44-3}に相当する式は
\[ G(n) = F(n) + G\biggl( \frac{n}{2} \biggr) + G\biggl( \frac{n}{3} \biggr) + G\biggl( \frac{n}{5} \biggr) – G\biggl( \frac{n}{2\cdot 3} \biggr) – G\biggl( \frac{n}{3\cdot 5} \biggr) – G\biggl( \frac{n}{5\cdot 2} \biggr) + G\biggl( \frac{n}{2\cdot 3\cdot 5} \biggr) \]
となる。\(n\) の異なる素因数が \(p\), \(q\), \(r\) の３種の場合も同様で、\eqref{eq:44-4}に当たる式は
\[ F(n) = G(n) – G\biggl( \frac{n}{p} \biggr) – G\biggl( \frac{n}{q} \biggr) – G\biggl( \frac{n}{r} \biggr) + G\biggl( \frac{n}{pq} \biggr) + G\biggl( \frac{n}{qr} \biggr) + G\biggl( \frac{n}{rp} \biggr) – G\biggl( \frac{n}{pqr} \biggr) \]
となる。
異なる素因数の個数がさらに増えてもまったく同じで、一般に
\begin{equation}
\begin{split}
\#(A \cup B \cup C \cup \dots \cup D) = & \#(A) + \dots + \#(D) – (\#(A \cap B) + \dots + \#(C \cap D)) \\
& + (\#(A \cap B \cap C) + \dots + \#(B \cap C \cap D)) \\
& – \dots \pm \#(A \cap \dots \cap D)
\end{split}
\label{eq:44-5}
\end{equation}
がなりたつのとまったく同様に、
\begin{equation}
\begin{split}
G(n) &= F(n) + G\biggl( \frac{n}{p} \biggr) + \dots + G\biggl( \frac{n}{s}
\biggr) \\
&- \left(G\biggl( \frac{n}{pq} \biggr) + \dots + G\biggl( \frac{n}{rs}
\biggr)\right) \\
&+ \left(G\biggl( \frac{n}{pqr} \biggr) + \dots + G\biggl( \frac{n}{qrs}
\biggr) \right) \\
&- \dots \pm G\biggl( \frac{n}{pqr \dots s} \biggr)
\end{split}
\label{eq:44-6}
\end{equation}
で、
\begin{equation}
\begin{split}
F(n) &= G(n) – \left( G\biggl( \frac{n}{p} \biggr) + \dots + G\biggl(
\frac{n}{s} \biggr) \right) \\
&+ \left(G\biggl( \frac{n}{pq} \biggr) + \dots + G\biggl( \frac{n}{rs}
\biggr) \right) \\
&- \left(G\biggl( \frac{n}{pqr} \biggr) + \dots + G\biggl( \frac{n}{qrs}
\biggr) \right) \\
&+ \dots \pm G\biggl( \frac{n}{pqr \dots s} \biggr)
\end{split}
\label{eq:44-7}
\end{equation}
となっている（ここで、\(p, q, r, \dots, s\) は \(n\) の異なる素因数）。これが Möbius 反転公式の素朴な姿である。（なお、きちんと言えば\eqref{eq:44-5}と\eqref{eq:44-6}はまったく同じ式というわけではない。前者は集合の合併や交わり「の要素数」に関する等式であり、後者はそれら「の上にわたる和」に関する等式であるから、厳密に言えば\eqref{eq:44-6}は\eqref{eq:44-5}とは独立に証明を要する。しかし、\eqref{eq:44-5}は要するに「合併でダブっている分を交わりで補正するにはどう足し引きすればいいか」を表したものなので、その符号規則がそのまま\eqref{eq:44-6}でも使える、ということはストレートに理解できる。ちゃんと証明したければ、\eqref{eq:44-5}の証明をモデルにして「要素数」を「集合上にわたる和」に修正すればまったく同様に示せるのでここでは割愛する）
\eqref{eq:44-7}の右辺には規則性があるので、\(\sum\) の形で書き直せる。
\[ F(n) = \sum_{d} \left\{ \pm G\biggl( \frac{n}{d} \biggr) \right\} \]
ここで、\(d\) は \(n\) の（正の）約数のうち、どの素因数も \(1\) 個以下しか現れない（素因数に重複がない）範囲を動き、\(\pm\) の符号は \(d\) の素因数の個数の偶奇に応じて定まる。こう書いてみると、Möbius 関数の定義があのようになる事情も極めて自然に理解できる。
コメントを残す