整数論的関数の反転公式 メビウスの反転公式


整数論的関数の反転公式、 代数系入門 (松坂和夫) 第1章 §8 問題3 の解答です。

代数系入門 (松坂和夫) では 整数論的関数の反転公式 とありますが、 Möbius の反転公式 という名前のほうがよく使われています。

命題

( F ) を整数論的関数、 ( mu ) を Möbius(メビウス)関数として

[ G(n) = sum_{d|n} F(d) ]

とすると

[ F(n) = sum_{d|n} mu(d) G left( frac{n}{d} right) ]

証明

begin{eqnarray*} & & sum_{d|n} mu(d) G left( frac{n}{d} right) & = & sum_{d|n} mu(d) left{ sum_{l|frac{n}{d}} F(l) right} & = & sum_{d|n, l|frac{n}{d}} mu(d) F(l) end{eqnarray*}

( d|n wedge l | frac{n}{d} ) は ( l|n wedge d|frac{n}{l} ) と同値です。 ( ( d|n wedge l | frac{n}{d} ) という条件から、 ( a | n ) なる ( a ) を用いて ( la = frac{n}{d} ) と書くことができ、 これは ( da = frac{n}{l} ) と式変形できます。 よって ( d | frac{n}{l} ) であることがわかります。 また ( d|n ) より ( frac{n}{d} in mathbb{Z} ) で、 ( l | frac{n}{d} ) なので ( l|n ) です。 逆も同様です。 )

これより次のように式変形できます。

begin{eqnarray*} & & sum_{d|n, l|frac{n}{d}} mu(d) F(l)  & = & sum_{l|n, d|frac{n}{l}} mu(d) F(l) & = & sum_{l|n} F(l) left{ sum_{d|frac{n}{l}} mu(d) right} end{eqnarray*}

( sum_{d|frac{n}{l}} mu(d) ) は ( n > 1 ) のとき ( sum_{d|n} mu(d) = 0 ) (代数系入門 (松坂和夫) の 定理11) であることから ( l lt n ) においては 0 になります。 そのため、 ( l = n ) の場合のみを考えれば十分です。 これより

begin{eqnarray*} & & sum_{l|n} F(l) left{ sum_{d|frac{n}{l}} mu(d) right} & = & F(n) end{eqnarray*}

となります。

(逆も成り立ちます。)