2015/11/05

メビウスの反転公式の証明と応用

分野: 整数問題  レベル: マニアック

前半は準備(メビウス関数の定義,簡単な性質)です。後半はメビウスの反転公式という美しい定理とその応用例を解説します。

メビウス関数

まずメビウス関数 $\mu(n)$ を定義します。正の整数を与えると$-1,0,1$ のいずれかを返す関数です:

  • $\mu(1)=1$
  • $n$ がある素数 $p$ で $2$ 回割り切れるとき $\mu(n)=0$
  • $n$ が相異なる $k$ 個の素数の積であるとき $\mu(n)=(-1)^k$

例えば $\mu(9)=0$,$\mu(12)=0$,$\mu(6)=1$,$\mu(30)=-1$ などです。

メビウス関数の性質

$2$ 以上の任意の整数 $n$ について,
$\displaystyle\sum_{d\mid n}\mu(d)=0$

$\displaystyle\sum_{d\mid n}$ とは,$n$ の全ての約数 $d$ について和を取るという意味です。 証明は定義に従って計算するだけです。

証明

$n$ の素因数分解を $p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ とする。
左辺の和について,$d$ が同じ素因数を $2$ つ以上含む項は消えるので,
素因数を含まないもの:$\mu(1)$(値は $1$)
素因数をちょうど $1$ つ含むもの:$\mu(p_1),\cdots \mu(p_k)$ の $k$ 個(値は全て$-1$)
素因数をちょうど $2$ つ含むもの:$\mu(p_1p_2),\cdots,\mu(p_{k-1}p_k)$ の${}_k\mathrm{C}_2$ 個(値は全て $1$)
$\cdots$
よって,左辺は
$1-{}_k\mathrm{C}_1+{}_k\mathrm{C}_2-\cdots +(-1)^k{}_k\mathrm{C}_k\\
=(1-1)^k\\
=0$

ちなみに $n=1$ のとき,定理の式の左辺の値は $1$ になります。

メビウスの反転公式

$f(n),g(n)$ を正の整数から実数(複素数でもよい)への関数とします。

メビウスの反転公式:
$g(n)=\displaystyle\sum_{d\mid n}f(d)$ ならば,
$f(n)=\displaystyle\sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)g(d)$

「 $g=f$ の和」という形の式を「 $f=g$ の和」という形の式に「反転」できるという公式です。

証明

$g(n)=\displaystyle\sum_{d\mid n}f(d)$ のとき,
$\displaystyle\sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)g(d)\\
=\displaystyle\sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)\sum_{d’\mid d}f(d’)\\
=\displaystyle\sum_{d,d’}\mu\left(\dfrac{n}{d}\right)f(d’)$
ただし,最後の式の和は「 $d’$が $d$ の約数かつ $d$ が $n$ の約数,を満たす全ての $d$ と $d’$のペア」について取る。

$d’$を固定して考えると,$d$ の動く範囲は $d’$の倍数かつ $n$ の約数。つまり $\dfrac{n}{d}$ の動く範囲は $\dfrac{n}{d’}$ の約数。つまり $f(d’)$ が登場する部分からは

$f(d’)\displaystyle\sum_{t}\mu(t)$
という項が出てくる。ただし,$t$ は $\dfrac{n}{d’}$ の約数を動く。そして,$d’\neq n$ のとき,さきほど述べたメビウスの関数の性質によりこの和は $0$ である!

よって,$d’=n$ のときの項:$f(n)$ が残る。

メビウスの反転公式の応用例

$1$ から $n$ までの整数の中で $n$ と互いに素なものの数 $\phi(n)$ は,$n$ の素因数分解を $p_1^{e_1}\cdots p_k^{e_k}$ とすると,
$n\left(1-\dfrac{1}{p_1}\right)\cdots \left(1-\dfrac{1}{p_k}\right)$

証明の概略

$f(n)=\phi(n)$,$g(n)=n$ とおくと,オイラーのファイ関数のイメージと性質の最後の性質により,$g(n)=\displaystyle\sum_{d\mid n}f(d)$ が成立する。よって,メビウスの反転公式より,
$\phi(n)=\displaystyle\sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)d=\displaystyle\sum_{d\mid n}\mu(d)\dfrac{n}{d}$
メビウス関数の定義に従って最右辺を計算すると $n(1-\frac{1}{p_1})\cdots (1-\frac{1}{p_k})$ となる。

メビウスの反転公式はより一般の半順序集合に拡張できます。そこから包除原理を導出したりできます(奥が深い)。
分野: 整数問題  レベル: マニアック