メビウスの反転公式

※ MathJax を使用しています。数式を表示するためには、JavaScript をオンにする必要があります。

$\mathbb{Z}^{+}$ を正の整数全体からなる集合とする. $\mathbb{Z}^{+}$ 上定義された実数値または複素数値関数のことを整数論的関数という.

[補題] $a$ を正の整数とする. このとき, \begin{align*} & \{ (d, d')\in(\mathbb{Z}^{+})^{2} \mid \mbox{$d$ は $a$ の約数かつ $d'$ は $d$ の約数}\} \\ & = \{ (a/d'', d')\in(\mathbb{Z}^{+})^{2} \mid \mbox{$d'$ は $a$ の約数かつ $d''$ は $a/d'$ の約数}\} \end{align*} が成り立つ.

[証明] $(d, d')$ を左辺の集合の元とし, $d''=a/d$ とおくと, $d=a/d''$ であり, \begin{align*} \mbox{$d\mid a$ かつ $d'\mid d$} & \Longrightarrow \mbox{$d'\mid a$ かつ $a/d\mid a/d'$} \\ & \Longrightarrow \mbox{$d'\mid a$ かつ $d''\mid a/d'$} \end{align*} であるから, $(d, d')$ は右辺の集合の元である.

逆に, $(a/d'', d')$ を右辺の集合の元とし, $d=a/d''$ とおくと, $d''=a/d$ であり, \begin{align*} \mbox{$d'\mid a$ かつ $d''\mid a/d$} & \Longrightarrow \mbox{$d\mid a$ かつ $a/d\mid a/d'$} \\ & \Longrightarrow \mbox{$d\mid a$ かつ $d'\mid d$} \end{align*} であるから, $(a/d'', d')$ は左辺の集合の元である. (証明終)

[定理 (Möbius の反転公式)] $F(n)$ を整数論的関数とし, $$ G(n) = \sum_{d\mid n}F(d) $$ とおく. このとき, $$ F(n) = \sum_{d\mid n}\mu\left(\frac{n}{d}\right)G(d) $$ が成り立つ. ただし, $\mu(n)$ は Möbius の関数である.

[証明] $a$ を正の整数とする. このとき, \begin{align*} \sum_{d\mid a}\mu\left(\frac{a}{d}\right)G(d) &= \sum_{d\mid a}\mu\left(\frac{a}{d}\right)\sum_{d'\mid d}F(d') \\ &= \sum_{d\mid a}\sum_{d'\mid d}\mu\left(\frac{a}{d}\right)F(d'). \end{align*} また, 補題より \begin{align*} & \{ (d, d')\in(\mathbb{Z}^{+})^{2} \mid \mbox{$d$ は $a$ の約数かつ $d'$ は $d$ の約数}\} \\ & = \{ (a/d'', d')\in(\mathbb{Z}^{+})^{2} \mid \mbox{$d'$ は $a$ の約数かつ $d''$ は $a/d'$ の約数}\} \end{align*} が成り立つから, \begin{align*} \sum_{d\mid a}\sum_{d'\mid d}\mu\left(\frac{a}{d}\right)F(d') &= \sum_{d'\mid a}\sum_{d''\mid a/d'}\mu(d'')F(d') \\ &= \sum_{d'\mid a}F(d')\sum_{d''\mid a/d'}\mu(d''). \end{align*} さらに, $a$ のすべての約数 $d'$ に対して $$ \sum_{d''\mid a/d'}\mu(d'') = \begin{cases} 1, & \mbox{$a/d'=1$ のとき}, \\ 0, & \mbox{$a/d'>1$ のとき} \end{cases} $$ であるから, $$ \sum_{d'\mid a}F(d')\sum_{d''\mid a/d'}\mu(d'') = \sum_{d'=a}F(d')\cdot 1 = F(a). $$ ゆえに, $$ \sum_{d\mid a}\mu\left(\frac{a}{d}\right)G(d) = F(a). $$ $a$ は任意であるから, $n$ を変数とする関数についての等式 $$ \sum_{d\mid n}\mu\left(\frac{n}{d}\right)G(d) = F(n) $$ が成り立つ. (証明終)

関連記事

メビウス関数の値の和

【theme : 数学
【genre : 学問・文化・芸術

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示