本記事の内容
本記事は「メビウスの反転公式」の証明を与える記事です。
本記事を読むに当たり、メビウス関数について知っている必要があるため、以下の記事も合わせてご覧ください。
メビウス関数の軽い復習
一言で述べれば
です。
メビウス関数とは？
メビウス関数
関数\(\mu\mu:\mathbb{N}\longrightarrow\mathbb{N}\)を、\(n\in\mathbb{N}\)に対して $$ \mu(n)= \begin{cases} 1&(n=1)\\ (-1)^k&(k=p_1p_2\cdots p_k)\\ 0&({\rm otherwise}) \end{cases} $$ で定める。 ただし、\(p_1<p_2<\cdots<p_k\)は素数とする。 この関数\(\mu\)をメビウス関数(M\(\ddot{{\rm o}}\)bius関数)という。要するに、\(n\in\mathbb{N}\)に対して
- \(n=1\)ならば\(\mu(n)=1\)
- \(n\)が相異なる\(k\)個の素数の積で表せるならば\(\mu(n)=(-1)^k\)
- \(n\)が平方数を因数に持つならば\(\mu(n)=0\)
で定まる関数がメビウス関数です。
具体例
- \(\mu(1)=1\)
これはそのままです。 - \(\mu(2)=-1\)
なぜかというと、\(2\)は素数ですので、1つの素数で表現できているわけですから\(\mu(2)=(-1)^1=-1\)です。 - \(\mu(3)=-1\)
\(\mu(2)\)の場合と同じです。 - \(\mu(4)=0\)
\(4=2^2\)と素因数分解できますので、\(4\)は相異なる素数の積で表現できていません。
したがって、\(\mu(4)=0\)です。 - \(\mu(5)=0\)
\(\mu(2)\)および\(\mu(3)\)と同じです。 - \(\mu(6)=1\)
\(6=2\times 3\)と素因数分解できるため、相異なる2つの素数の積で書けるから\(\mu(6)=(-1)^2=1\)です。 - \(\mu(2023)=0\)
\(2023=7\times17^2\)と素因数分解できるため、相異なる素数の積で表現できていません。
したがって、\(\mu(2023)=0\)です。 - \(\mu(5282023)=-1\)
\(5282023\)は素数のため、\(\mu(2)\)、\(\mu(3)\)及び\(\mu(5)\)と同じです。
ここでもうお気づき可と思いますが、\(n\)が素数である場合は、常に\(\mu(n)=-1\)です。
本記事で言いたいこと
本記事で述べたいのは
定理0.(メビウスの反転公式)
\(f(n)\)を乗法的関数(※後述)とする。\(\displaystyle F(n)=\sum_{d\mid n}f(d)\)で定めれば、 $$ f(n)=\sum_{d\mid n}\mu(d)F\left( \frac{n}{d}\right)=\sum_{d\mid n}\mu\left( \frac{n}{d}\right)F(d) $$ である。の証明です。
乗法的関数、完全乗法的関数
“雰囲気”の話をすると、乗法的関数、完全乗法的関数というのは線形写像と似たものです。
乗法的関数、完全乗法的関数とは何か？
では、実際何者なのか？という話をします。
乗法的関数、完全乗法的関数
関数\(f\)が正の整数全体の集合上で定められた関数であるとする。- 乗法的関数 \(f(1)=1\)であり、かつ\(m,n\in\mathbb{N}\)に対して\(\gcd(m,n)=1\)ならば\(f(nm)=f(n)f(m)\)を満たすとき\(f\)を乗法的関数という。
- 完全乗法的関数 \(f\)が乗法的関数であり、任意の\(m,n\in\mathbb{N}\)に対して\(f(nm)=f(n)f(m)\)となるとき、\(f\)を完全乗法的関数という。
乗法的関数と完全乗法的関数の違いは「定義域の要素が互いに素であるという仮定があるか否か」です。
乗法的関数の例1. オイラーの\(\varphi\)関数
オイラーの\(\varphi\)関数は乗法的関数です。
実際次が成り立つのでした。
定理1.(オイラーの\(\varphi\)関数の乗法性)
\(\varphi:\mathbb{N}\longrightarrow\mathbb{N}\)をオイラーの\(\varphi\)関数とする。\(a,b\in\mathbb{N}\)に対して $$ \gcd(a,b)=1\ \Longrightarrow\ \varphi(ab)=\varphi(a)\cdot\varphi(b) $$定理1.の証明は【代数学の基礎シリーズ】初等整数論編 その17を御覧ください。
これはまさに、オイラーの\(\varphi\)関数が乗法的関数であることを示しています。
乗法的関数の例2. メビウス関数
実は、メビウス関数も乗法的関数です。
すなわち、以下が成り立ちます。
定理2.(メビウス関数の乗法性)
メビウス関数\(\mu:\mathbb{N}\longrightarrow \left\{ -1,0,1\right\}\)は乗法的関数である。すなわち \(\mu(1)=1\)であり、かつ\(m,n\in\mathbb{N}\)に対して\(\gcd(m,n)=1\)ならば\(\mu(nm)=\mu(n)\mu(m)\)を満たす。定理2.(メビウス関数の乗法性)の証明
まず、\(\mu(1)=1\)です。
次に、\(m,n\in\mathbb{N}\)ならば\(\mu(nm)=\mu(n)\mu(m)\)を示します。
\(n=1\)または\(m=1\)の場合、\(\mu(nm)=\mu(n)\mu(m)\)を満たします。
そこで、\(m,n\in\mathbb{N}\)が\(m,n\neq1\)を満たすとします(つまり\(m,n\)は\(2\)以上の自然数)。
また、\(\gcd(m,n)=1\)であるとします。
①\(n\)または\(m\)が平方因子を持つ場合
もし、\(n\)または\(m\)が平方因子を持つ、すなわち平方数で割り切れるのであれば、\(nm\)もまた平方因子を持ちます。
実際、仮に\(n\)が平方因子\(a^2\ (a\in\mathbb{N})\)を持つとすると、\(n=k_na^2\)と書ける為、
$$
nm=k_na^2m
$$
となり、\(nm\)もまた\(a^2\)で割り切れるからです(\(m\)が平方因子を持つ場合も同様)。
故に、この場合は\(\mu(n)=0\)ですから、\(\mu(m)\)がどんな値であれ\(\mu(n)\mu(m)=0\)です。
さらにこのとき、\(nm\)も平方因子を持つため\(\mu(nm)=0\)となり、
$$
\mu(nm)=\mu(n)\mu(m)=0
$$
が成り立ちます(\(m\)が平方因子を持つ場合も、\(m\)も\(n\)も平方因子を持つ場合も同様)。
②\(n\)も\(m\)も平方因子を持たない場合
この場合、\(m,n\)を素因数分解すると、\(\gcd(m,n)=1\)から相異なる素数\(p_1,\cdots,p_t,q_1,\cdots,q_s\)を用いて
\begin{eqnarray}
&&n=p_1\cdots p_t\\
&&m=q_1\cdots q_s
\end{eqnarray}
と書くことができます。
このとき、
$$
nm=p_1\cdots p_tq_1\cdots q_s
$$
ですから、\(nm\)の素因数の個数は\(t+s\)個です。
故に
$$
\mu(n)=(-1)^t,\quad \mu(m)=(-1)^s,\quad \mu(nm)=(-1)^{t+s}
$$
です。
したがって、
$$
\mu(nm)=\mu(n)\mu(m)
$$
となり、証明完了です。
定理2.(メビウス関数の乗法性)の証明
完全乗法的関数の例
\(a>0\)を正の実数とします。
\(n\in\mathbb{N}\)に対して、
$$
f(n)=n^a
$$
と定めると、\(f\)は完全乗法的関数です。
実際、\(m,n\in\mathbb{N}\)に対して
\begin{eqnarray}
f(mn)&=&(mn)^a=m^a\cdot n^a=f(m)\cdot f(n)
\end{eqnarray}
だからです。
特に、任意の\(n\in\mathbb{N}\)に対して\(f(n)=1\)なる関数は完全乗法的な関数です。
メビウスの反転公式とその証明
では、本題です。
定理0.(メビウスの反転公式)※再掲※
\(f(n)\)を乗法的関数(※後述)とする。\(\displaystyle F(n)=\sum_{d\mid n}f(d)\)で定めれば、 $$ f(n)=\sum_{d\mid n}\mu(d)F\left( \frac{n}{d}\right)=\sum_{d\mid n}\mu\left( \frac{n}{d}\right)F(d) $$ である。定理0.(メビウスの反転公式)の証明
まず、
$$
\sum_{d\mid n}\mu(d)F\left( \frac{n}{d}\right)=\sum_{d\mid n}\mu\left( \frac{n}{d}\right)F(d)
$$
という等式について考えます。
\(\displaystyle k=\frac{n}{d}\)とすれば、\(\displaystyle d=\frac{n}{k}\)です。
そして、\(n\in\mathbb{N}\)は今固定ですので、\(k\)は\(d\)に対して一意的に定まります。
さらに、\(n=kd\)ですから、\(k\in\mathbb{N}\)もまた\(n\)の約数、すなわち\(k\mid n\)を満たします。
したがって、
$$
\sum_{d\mid n}\mu(d)F\left( \frac{n}{d}\right)=\sum_{k\mid n}\mu\left( \frac{n}{k}\right)F(k)
$$
となります。
文字\(k\)は今回の条件さえ満たせば何でも良い(どんな文字でも良い)ので、\(k\)を新たに\(d\)という文字に書き直して
$$
\sum_{d\mid n}\mu(d)F\left( \frac{n}{d}\right)=\sum_{d\mid n}\mu\left( \frac{n}{d}\right)F(d)
$$
が成り立ちます。
余談(和の条件の取替について)
数学では、上記のように和の条件を書き換えるという操作をよく行います。結局何をしているのかということを数学的に説明すると、
数学において、特に和においてはこのような操作がよく行われますので、ぜひマスターしておくと良いと思います。
ちなみに、筆者は包含排除の原理を学んだときに鍛えられました。
したがって、
$$
f(n)=\sum_{d\mid n}\mu\left( \frac{n}{d}\right)F(d)
$$
を証明します。
\(\displaystyle F(n)=\sum_{d\mid n}f(d)\)により、文字\(d\)を\(e\)に書き直すことで
$$
\sum_{d\mid n}\mu\left( \frac{n}{d}\right)F(d)=\sum_{d\mid n}\mu\left( \frac{n}{d}\right)\sum_{e\mid d}f(e)\tag{1}
$$
が成り立ちます。
さて、(1)の右辺は有限和ですから、
$$
\sum_{d\mid n}\mu\left( \frac{n}{d}\right)\sum_{e\mid d}f(e)=\sum_{d\mid n}\sum_{e\mid d}\mu\left( \frac{n}{d}\right)f(e)
$$
と書くことができます。
2つの\(\displaystyle\sum\)記号をあわせて
$$
\sum_{d\mid n}\mu\left( \frac{n}{d}\right)\sum_{e\mid d}f(e)=\sum_{\substack{d\mid n\\ e\mid d}}\mu\left( \frac{n}{d}\right)f(e)\tag{2}
$$
と書くこともできます。
すなわち、(2)は
ということになります。
では、条件
を言い換えてみましょう。
\(d\mid n\)と\(e\mid d\)の組を考えることは、\(d=ed_1\)と書くことで\(e\mid n\)と\(\displaystyle \left.d_1\middle| \frac{n}{e}\right.\)を考えることと同じことです。
より厳密には
$$
d\mid n,\ e\mid d\quad \Longleftrightarrow \quad e\mid n,\ \left.d_1\middle|\frac{n}{e}\right.\ (d=ed_1)
$$
が成り立つということです。
故に、
\begin{eqnarray}
\sum_{\substack{d\mid n\ e\mid d}}\mu\left( \frac{n}{d}\right)f(e)&=&\sum_{\substack{e\mid n\\ \left. d_1\middle| \frac{n}{e}\right.}}\mu\left( \frac{n}{ed_1}\right)f(e)
\end{eqnarray}
です。
また、どの和も有限和ですから、和の順序を交換してもOKですので、
\begin{eqnarray}
\sum_{\substack{e\mid n\\ \left. d_1\middle| \frac{n}{e}\right.}}\mu\left( \frac{n}{ed_1}\right)f(e)&=&\sum_{e\mid n}f(e)\sum_{\left. d_1\middle|\frac{n}{e}\right.}\mu\left(\frac{n}{ed_1} \right)\\
&=&\sum_{e\mid n}f(e)\sum_{\left. d_1\middle|\frac{n}{e}\right.}\mu(d_1)\ (※)
\end{eqnarray}
となります。
(※)についてですが、序盤の話とほぼ同じです。
\(\displaystyle\left. d_1\middle| \frac{n}{e}\right.\)により、
$$
(\exists k\in\mathbb{N})\ {\rm s.t.}\ \frac{n}{e}=kd_1
$$
ですから、\(n=ked_1\)です。
故に、
$$
\mu\left( \frac{n}{ed_1}\right)=\mu\left( \frac{ked_1}{ed_1}\right)=\mu(k)
$$
です。
しかも、このとき\(k\)は一意的に定まります。
以上のことから、\(\displaystyle\left. d_1\middle| \frac{n}{e}\right.\)を満たす\(d_1\)での\(\displaystyle\mu\left( \frac{n}{ed_1}\right)\)の和は\(\displaystyle\left. k\middle| \frac{n}{e}\right.\)を満たす\(k\)での\(\displaystyle\mu\left(k\right)\)の和と同じものです。
そこで、\(k\)を新たに\(d_1\)と書き直している、ということです。
ここで、次の性質を使います。
定理3.
\(n\in\mathbb{N}\)に対して、\(n>1\)ならば、 $$ \sum_{\substack{d\in\mathbb{N}\\ d\mid n}}\mu(d)=0 $$ である。定理3.の証明は【代数学の基礎シリーズ】初等整数論編 その19を御覧ください。
この性質を使えば、\(\displaystyle\frac{n}{e}>1\)の場合は
$$
\sum_{\left. d_1\middle|\frac{n}{e}\right.}\mu(d_1)=0
$$
となりますから、\(\displaystyle\frac{n}{e}=1\)の場合、すなわち\(n=e\)の場合だけ考えればOKです。
したがって、
$$
\sum_{e\mid n}f(e)\sum_{\left. d_1\middle|\frac{n}{e}\right.}\mu(d_1)=f(n)
$$
が得られます。
定理0.(メビウスの反転公式)の証明終わり
実際に計算して確かめてみる
具体的に計算して確かめてみましょう。
完全乗法的関数の例として挙げた関数を使います。
\(a>0\)を正の実数とします。
\(n\in\mathbb{N}\)に対して、
$$
f(n)=n^a
$$
と定めると、\(f\)は完全乗法的関数です。
この\(f\)に対してメビウスの反転公式が成り立つことを具体的な値で確かめてみます。
今回は\(n=2\)の場合、すなわち
$$
f(2)=\sum_{d\mid 2}\mu\left( \frac{2}{d}\right)F(d)
$$
を確かめてみます。
\begin{eqnarray}
\sum_{d\mid 2}\mu\left( \frac{2}{d}\right)F(d)&=&\mu\left(\frac{2}{1} \right)F(1)+\mu\left( \frac{2}{2}\right)F(2)\\
&=&\mu(2)F(1)+\mu(1)F(2)\\
&=&-1\cdot\sum_{e\mid 1}e^a+1\cdot\sum_{e\mid 2}e^a\\
&=&-1\cdot1^a+1^a+2^a\\
&=&2^a=f(2)
\end{eqnarray}
となって成り立ちます。
皆様のコメントをください！
本ブログを読んでいただいている方は、おおよそ「数学が好きだ」とか「数学に興味がある」という方が多いのではないでしょうか。
「いや、そこまで好きじゃないけど数学の講義があってさ…」という方もいらっしゃるでしょうが、少なくとも数学と親和性がある分野を専攻なさっているという意味では「数学にも興味がある」と言えると思います。
さて、筆者は「なんで数学好きなの？どこが好きなの？」と質問されたことがあります。
長らくそういう質問をされていなかったので実は即答できませんでした。
大学、大学院で数学をやっていると、数学好きが集まっているわけですので、わざわざどこが好きかなんて質問は飛び交わないのです(少なくとも筆者の周りではそうでした)。
そこで、皆様に質問です。
「数学のどういうところが好きですか？」
ぜひコメントで教えてください！
結
今回は、乗法的関数、完全乗法的関数、メビウス関数の乗法性、メビウスの反転公式について解説しました。
メビウス関数は自然数の集合を定義域として、自然数の素因数分解の結果によって\(-1,0,1\)を対応させる関数です。
筆者が初めてメビウスの反転公式を見たときは「なんか複雑そうだな…」と思ったのですが、証明を見ると実にシンプルで感嘆したものです。
次回以降は、「オイラーの\(\varphi\)関数とメビウス関数の関係」について解説します。
乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければお答えします！
初等整数論について、以下の書籍をオススメします！
コメントをする