メビウス関数
このページでは、整数上のMöbius関数について解説する。Möbius関数は包含と除去の原理やMöbiusの反転公式を通じて、
整数の集合の数え上げや他の整数論的関数の考察などに幅広く応用される関数である。
Möbius関数
正の整数 $N$ が
$$N=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}, e_i>0$$
と素因数分解されるとき
$$N=\left\{\begin{array}{cl} (-1)^r& (\forall i[e_i\leq 1])\\
0 & (\exists i[e_i\geq 2])\end{array}\right.$$
によりMöbius関数を定義する。
定義よりMöbius関数は乗法的関数である。Möbius関数は有限半順序集合上のMöbius関数に一般化される。
$N>0$ に対して
$$\sum_{d\mid N}\mu(d)=\left\{\begin{array}{cl} 1 & (N=1)\\
0 & (N>1)\end{array}\right.$$
が成り立つ。
$N=1$ ならば
$$\sum_{d\mid N}\mu(d)=\mu(1)=1$$
となる。
$N>1$ のとき
$$N=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$$
と素因数分解すると $\mu$ は乗法的関数なので
定理4.4
より
$$\sum_{d\mid N}\mu(d)=\prod_{i=1}^r \sum_{f_i=0}^{e_i}\mu(p_i^{f_i})=\prod_{i=1}^r (\mu(1)+\mu(p_i))=0$$
となる。
$S$ を有限集合、$P$ を素数の有限集合、$D$ を $P$ に属する相異なる素数の積であらわされる整数全体とする。
素数 $p\in P$ について $S$ の部分集合 $S_p$ が定まっているとし、
$d\in D$ に対して $S_d=\bigcap_{p\mid d}S_p$ とおく。さらに $T=S\backslash \bigcup_p S_p$ を、$S$ の要素でどの $S_p$ にも属さないもの全体の集合とすると、
$$\#T=\sum_{d\in D} \mu(d) \# S_d$$
となる。
$x\mid S_d\Longleftrightarrow \forall (p\mid d)x\in S_p$
であるから、各 $x\in S$ について $N(x)=\prod_{x\in S_p} p$ を $S_p$ が $x$ を含んでいる素数 $p$ すべての積とすると、$N(x)\in D$ で
$$x\in S_d\Longleftrightarrow d\mid N(x)$$
となる。
それで、$f(x)=\sum_{x\in S_d}\mu(d)$ とおくと
$$f(x)=\sum_{d\mid N(x)}\mu(d)$$
より
$$f(x)=1\Longleftrightarrow N(x)=1\Longleftrightarrow x\in T$$
となる。よって
$$\#T=\sum_{x\in S}f(x)=\sum_{d\in D} \mu(d)\sum_{x\in S_d} 1=\sum_{d\in D} \mu(d)\# S_d$$
となる。
この定理は有限半順序集合上の包含と除去の原理に一般化される。
参考文献
本ページについてはHardy and Wright, Chapter 16 を参照。
参考文献
