Excel VBA 数学教室ではアフィリエイトプログラムを利用して商品を紹介しています。

メビウス関数(Mobius function)

メビウス関数の定義

任意の自然数 $n$ の約数すべてにわたって和をとったときに $0$ になるような関数 $f(n)$ があれば、数論にとって非常に有用な関数となります。1831 年、メビウスの輪で有名なドイツの数学者メビウス(August Ferdinand Möbius)がそのような条件を満たす関数 $\mu(n)$ を発表しました。

【定義D3】メビウス関数 $\mu(n)$ を以下のように定義する。
(1) $n=1$ のときは $\mu(n)=1$
(2) $n$ が $r$ 個の異なる素数の積であるときは $\mu(n)=(-1)^r$
(3) $n$ が平方因子(素数の 2 乗)をもつときは $\mu(n)=0$

具体的に計算してみましょう。

 $n=1$ のときは定義によって $\mu(1)=1$
 $n=2$ は 1 個の素数の積なので $\mu(2)=(-1)^1=-1$
 $n=3$ のときも同様に $\mu(3)=-1$
 $n=4$ のときは平方因子 $2^2$ をもつので $\mu(4)=0$

以下同様に計算していくと、
\[\mu(5)=-1,\quad\mu(6)=\mu(2\cdot 3)=(-1)^2=1,\quad\mu(7)=-1,\quad\cdots\]
のような値をとることがわかります。定義より明らかに素数 $p$ について
\[\mu(p)=-1,\quad \mu(p^k)=0\quad(k=2,\:3,\:\cdots)\]
が成り立ちます。

メビウス関数が乗法的であることを証明しておきます。

【定理D9】メビウス関数は $(a,\:b)=1$ のとき
\[\mu(ab)=\mu(a)\,\mu(b)\]を満たす乗法的関数です。

[証明] $a,\;b$ を素因数分解して
\[\begin{align*}a=&\,p_1^{\,a_1}\,p_2^{\,a_2}\,\cdots\,p_i^{\,a_i}\\[6pt]
b=&\,q_1^{\,b_1}\,q_2^{\,b_2}\,\cdots\,p_j^{\,b_j}\end{align*}\]
のように表せたとします。$(a,\:b)=1$ なので、
\[p_1,\;p_2,\;\cdots,\;p_i,\;q_1,\;q_2,\;\cdots,\;q_j\]
の中に共通する素因数はないので、$a$ と $b$ の積をつくると
\[ab=p_1^{\,a_1}\,p_2^{\,a_2}\,\cdots\,p_i^{\,a_i}\,q_1^{\,b_1}\,q_2^{\,b_2}\,\cdots\,q_i^{\,b_i}\]
となります。$a_1,\;a_2,\;\cdots,\;b_1,\;b_2$ のなかに 2 以上の値があるときは
\[\mu(a)\,\mu(b)=0=\mu(ab)\]
となります。$a_1=a_2=\cdots b_1=b_2=\cdots =1$ のときは
\[\mu(a)=(-1)^i,\quad\mu(b)=(-1)^j,\quad\mu(ab)=(-1)^{i+j}\]
となるので、
\[\mu(ab)=\mu(a)\mu(b)\]
が成り立ちます。(証明終)

たとえば $n=20$ のとき、
\[\mu(35)=\mu(5)\,\mu(7)=(-1)\cdot (-1)=1\]
のように計算できます。

メビウス関数の約数にわたる和

たとえば $n=12$ のとき、そのすべての約数について和をとると
\[\begin{align*}\sum_{d|12}\mu(d)=&\,\mu(1)+\mu(2)+\mu(3)+\mu(4)+\mu(6)+\mu(12)\\[6pt]=&\,1+(-1)+(-1)+0+(-1)^2+0=0\end{align*}\]
となります。これは一般にも成り立つ定理です。

【定理D10】
\[\sum_{d|n}\mu(d)=\begin{cases}1 & (n=1)\\[6pt]0 & (n\gt 1)\end{cases}\]

[証明] $n=1$ のときは定義より明らかです。$n\neq 1$ のとき
\[n=p_1^{\,a_1}\,p_2^{\,a_2}\,\cdots\,p_k^{\,a_k}\]
のように素因数分解されたとすると、その約数は
\[d=p_1^{\,x_1}\,p_2^{\,x_2}\,\cdots\,p_k^{\,a_k}\quad (1\leq x_i\leq a_k)\]
で表されます。$x_i\geq 2$ であれば $\mu(d)=0$ なので、このようなケースを除いて、$x_i=0$ または $x_i=1$ についてのみ和をとると
\[\begin{align*}\sum_{d|n}\mu(d)&=\mu(1)+\mu(p_1)+\mu(p_2)+\cdots +\mu(p_k)+\cdots\\[6pt]&+\mu(p_1\,p_2)+\mu(p_1\,p_3)+\cdots\\[6pt]&+\mu(p_1\,p_2\,p_3)+\mu(p_1\,p_3\,p_4)+\cdots\\[6pt]&+\cdots\cdots\cdots\\[6pt]&+\mu(p_1\,p_2\,\cdots\,p_k)\end{align*}\]
ここでたとえば $\mu(p_1\,p_2)+\mu(p_1\,p_3)+\cdots$ は $k$ 個から異なる $2$ 個を取り出したときの組み合わせの和となっているので、
\[\begin{align*}\sum_{d|n}\mu(d)=&\,1+{}_k\mathrm{C}_1\,(-1)+{}_k\mathrm{C}_2\,(-1)^2+\cdots+{}_k\mathrm{C}_k\\[6pt]=&\,\{1+(-1)\}^k=0\end{align*}\]
となります。(証明終)

証明の最後のところでは 二項定理
\[(a+b)^n=\sum_{k=0}^n{}_n\mathrm{C}_k\:a^{n-k}\:b^{\:k}\]
を用いました。
 

$\mu(d)$と$\mu(n/d)$の約数にわたる和

たとえば $\mu(10/d)$ の約数にわたる和を計算してみると
\[\begin{align*}\sum_{d|10}\mu\left(\frac{10}{d}\right)=&\mu\left(\frac{10}{1}\right)+\mu\left(\frac{10}{2}\right)+\mu\left(\frac{10}{5}\right)+\mu\left(\frac{10}{10}\right)\\[6pt]
&=\mu(10)+\mu(5)+\mu(2)+\mu(1)=\sum_{d|10}\mu(d)\end{align*}\]
のようになって $\mu(d)$ の和に等しくなります。一般的にも
\[\sum_{d|n}\mu\left(\frac{n}{d}\right)=\sum_{d|n}\mu(d)\]
という関係が成り立ちます。

メビウスの反転公式

次は メビウスの反転公式(Möbius inversion formula)を証明しますが、その前に準備として補題を1つ示しておきます。

【補題D1】\[d\,|\,n\;\wedge\;e\,|\,d\quad\Longleftrightarrow\quad e\,|\,n\;\wedge\;\frac{n}{d}\mid\frac{n}{e}\]

[証明] $d\,|\,n\;\wedge\; e\,|\,d$ ならば
\[n=kd,\quad d=le\]
とおけるので、
\[n=kle\quad\therefore e\,|\,d\]
が成り立ちます。さらに
\[\frac{n}{d}=k,\quad \frac{n}{d}=kl\]
なので、$\displaystyle\frac{n}{d}\mid\frac{n}{e}$ が成り立ちます。逆に $\displaystyle e\,|\,n\;\wedge\;\frac{n}{d}\mid\frac{n}{e}$ が成り立つとき、
\[\frac{n}{e}=m\frac{n}{d}\]
とおけるので、$d=me$ すなわち $e\,|\,d$ となります。(証明終)

ある整数論的関数 $g(n)$ を別の関数 $f(n)$ の約数にわたる和によって
\[g(n)=\sum_{d|n}f(d)\]
のように定義されるとき、逆に $f(n)$ が $g(n)$ によってどのように表されるかを述べているのが次の定理です。

【定理D11:メビウスの反転公式】
\[\begin{align*}g(n)=&\,\sum_{d|n}f(d)\qquad\qquad\quad (1)\\[6pt]
f(n)=&\,\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d)\qquad (2)\end{align*}\]

[証明] (1) を (2) の右辺に代入すると
\[\sum_{d|n}\mu\left(\frac{n}{d}\right)\left[\sum_{e|d}f(e)\right]=\,\sum_{d|n}\left[\sum_{e|d}\mu\left(\frac{n}{d}\right)f(e)\right]\]
ここで先ほどの補題 D1
\[d\,|\,n\;\wedge\;e\,|\,d\quad\Longleftrightarrow\quad e\,|\,n\;\wedge\;\frac{n}{d}\mid\frac{n}{e}\]
を用いて和の変数を置き換えると
\[\sum_{d|n}\left[\sum_{e|d}\mu\left(\frac{n}{d}\right)f(e)\right]=\sum_{e|n}\left[\sum_{(n/d)|(n/e)}\mu\left(\frac{n}{d}\right)\right]f(e)\]
ここで [ ] の中は $n/e=1$ のときのみ $1$ となり、その他の場合は $0$ となります。よって $n=e$ より
\[\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d)=f(n)\]
となることが示されました。(証明終)

メビウス関数とオイラー関数

メビウスの反転公式
\[\begin{align*}g(n)=&\,\sum_{d|n}f(d)\qquad\qquad\quad (1)\\[6pt]f(n)=&\,\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d)\qquad (2)\end{align*}\]
において $f(n)=\varphi(n)$ とおくと、
\[g(n)=\sum_{d|n}\varphi(d)=n\]
となるので、
\[\varphi(n)=\sum_{d|n}\mu\left(\frac{n}{d}\right)d\]
$n=de$ とおくと

\[\varphi(n)=\sum_{e|n}\mu(e)\frac{n}{e}=n\sum_{d|n}\frac{\mu(d)}{d}\]

となって、メビウス関数と オイラー関数 を結びつけることができます。$n=12$ の場合で試してみます。
\[\begin{align*}\varphi(12)=&\,12\sum_{d|12}\frac{\mu(d)}{d}\\[6pt]
=&\,12\left(\frac{\mu(1)}{1}+\frac{\mu(2)}{2}+\frac{\mu(3)}{3}+\frac{\mu(4)}{4}+\frac{\mu(6)}{6}+\frac{\mu(12)}{12}\right)\\[6pt]=&\,12\left(\frac{1}{1}+\frac{(-1)}{2}+\frac{(-1)}{3}+\frac{0}{4}+\frac{1}{6}+\frac{0}{12}\right)=4\end{align*}\]

エクセルや数学に関するコメントをお寄せください