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


整数論的関数の反転公式、 代数系入門 (松坂和夫) 第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*}

となります。

(逆も成り立ちます。)