メビウスの反転公式と3つの応用 - 日々の暮らしと時々の数学

過去の記事
br-h2gk.hatenablog.com
に、この定理のクラシカルな証明はメビウスの反転公式をつかう、
と書いてあった。

実を言うとメビウスの反転公式を用いた経験がないため、
これを見て調べるまで、内容と証明を知らなかった。

しかし、調べてみると非常に美しい定理だということが分かった。
またこれを認めれば上記の命題の証明はもっとシンプルに
解決することが明らかなので、それを目標に、反転公式から紹介する。

まず反転公式を紹介しよう。

◆定理（メビウスの反転公式）◆
関数 $f(n),g(n)$ は数論的関数（自然数上の複素数値関数）であるとする。
もし、 $\displaystyle g(n)=\sum_{d|n}f(d)$ が成立するならば、
$\displaystyle f(n)=\sum_{d|n}\mu \left( \frac{n}{d}\right) g(d)$
が成立する。
ただし、 $\mu (n)$ はメビウス関数である。

要は、分かりにくい数論的関数 $f(n)$ があった時、
約数で和をとると分かりやすい関数 $g(n)$ になったとする。

すると、 $g(n)$ とメビウス関数を用いて逆に $f(n)$ が表示できる、
と主張している。
知ってみると凄い！逆転サヨナラホームラン的な定理だ。

定義から確認していこう。

定義と反転公式の証明

上に貼った記事にもあるが、再掲しておく。

◆定義◆
メビウス関数 $\mu :\mathbb{Z}_{>0}\to \{ 0,\pm 1\}$ を
$\displaystyle \mu (n)=\left\{ \begin{array} {}0 &(n \mbox{ has a squared prime factor}) \\ (-1)^k & (\mbox{otherwise})\end{array}\right.$
で、ここで $k$ は異なる素因数の数を表す。

まずこの定義から次が導かれる。

◆命題◆
$\displaystyle \sum_{d|n}\mu (d)=\left\{ \begin{array} {}1 &(n=1) \\ 0 & (n>1)\end{array}\right.$
これを ${\Delta}_n$ とおくことにする。

＜証明＞
$n=1$ の場合は明らかなので、 $n>1$ の場合を示す。
$n$ の素因数分解が $n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$ だったとする。
メビウス関数は平方因子があれば0になるので、
$e_1=e_2=\cdots =e_r=1$ のときに証明できれば十分である。

このとき、約数は $p_1,p_2,\dots ,p_n$ から $0\leq l\leq n$ 個取り出し、
その積を作ることで得られる。
その時のメビウス関数の値は定義から $(-1)^l$ である。
また、 $l$ を固定した時、このような素因数の取り出し方は ${}_n{\rm C}_l$ 通り
あるので、
$\displaystyle \sum_{d|n}\mu (d)=\sum_{l=0}^{n}(-1)^l{}_n{\rm C}_l=0$
が得られる。
＜証明終了＞

最後の二項係数の和は高校数学でよく出てきた。
確かにたまに顔を出すから大切だとは思っていたが、反転公式に必要だとは。

さて、これを用いて反転公式の証明をしよう。
＜反転公式の証明＞
$\displaystyle \sum_{d|n}\mu \left( \frac{n}{d}\right) g(d)=\sum_{d|n}\mu \left( \frac{n}{d}\right) \sum_{l|d}f(l)$
$\displaystyle =\sum_{l|d|n}\mu \left( \frac{n}{d}\right) f(l)$ （和は $l$ と $d$ の組を走る）
$\displaystyle =\sum_{l|n}f(l)\left( \sum_{(n/d)|(n/l)}\mu \left( \frac{n}{d}\right) \right)$
$\displaystyle =f(n)$ （∵　上の命題から $n=l$ 以外は後半の和が消える）
となる。
＜証明終了＞

まず、 $f(n)=\mu (n)$ 自身ととるということが考えられる。
これは、
$\displaystyle \mu (n)=\sum_{d|n}\mu \left(\frac{n}{d}\right){\Delta}_d=\mu (n)$
となって自分自身に戻ってくる。

以下、利用法を3つ挙げてみる。

利用例その１：有限体上の既約多項式の数

過去の記事で紹介した定理

◆定理◆
有限体 $\mathbb{F}_q$ 上の $n$ 次のモニックな既約多項式の数は、
$\displaystyle \frac{1}{n}\sum_{d|n}\mu \left( \frac{n}{d}\right) q^d$
で与えられる。ただし、 $\mu (n)$ はメビウス関数である。

をメビウスの反転公式を用いて証明しよう。

必要な有限体に関する基礎知識は過去の記事を参照のこと。
引き続き $\mathbb{F}_{q^n}$ のことを $\mathbb{F}\langle q^n\rangle$ と書くことにする。
（見やすさのため）

＜証明＞
代数閉包 $\overline{\mathbb{F}}_q$ を固定した下で考える。
$n=1$ のときは明らかなので、 $n>1$ としよう。
${\cal P}_n$ を $\mathbb{F}_q$ 上の $n$ 次のモニック既約多項式全体とする。
${\cal R}_n\subset \mathbb{F}\langle q^n\rangle$ を ${\cal P}_n$ の元の根全体とする。

このとき、 $n|{\cal P}_n|=|{\cal R}_n|$ である。
後ろの数を数える。

いま、 $d|n$ に対し、 $\mathbb{F}\langle q^d\rangle$ の元は $\mathbb{F}\langle q^n\rangle$ に属する。
また、 $\mathbb{F}\langle q^n\rangle$ の元はその $\mathbb{F}_q$ 上の最小多項式の次数によって、
ある唯一の $d|n$ があり、 ${\cal R}_d$ に属する。

このことを踏まえると、
$\displaystyle q^n=\sum_{d|n}|{\cal R}_d|$
が成立している。

したがって、これにメビウスの反転公式を用いれば、
$\displaystyle |{\cal R}_n|=\sum_{d|n}\mu \left( \frac{n}{d}\right) q^d$
が成立するから、主張は示された。
＜証明終了＞

とても鮮やかな方法である。
過去記事の方法よりこちらの方が明快でエレガントだと思う。
アイルランド・ローゼンは確認してないが、
反転公式による方法、とはこれに違いないだろう。
しかしなぜ、ウィキペディアの既約多項式には
あのマイナーな方法のリンクが貼ってあるんだろうか。

利用例その２：オイラー関数 $\phi (n)$

まず、オイラー関数とは次である。

◆定義◆
オイラー関数 $\phi :\mathbb{N}\rightarrow \mathbb{N}$ を
$1,2,\dots ,n$ のうち $n$ と互いに素な元の数 $\phi (n)$ として定める。
これは $\displaystyle \phi (n)=\left| \left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}\right|$ であり、位数 $n$ の巡回群の生成元の数となる。

基本的な性質として次を挙げる。

◆命題◆
$p$ を素数とする。

$\phi (p^e)=p^{e-1}(p-1)$

$\displaystyle n=\sum_{d|n}\phi (d)$

1.は定義から簡単にわかる。
2.は次のようにすればよい。
位数 $n$ の巡回群 $G$ を考える。 $d|n$ なる位数 $d$ の部分群はただ1つだから、
$G$ における位数 $d$ の元の個数は $\phi (d)$ である。
よって、 $G$ の元をその位数により分割することで、
が得られる。もっと直接的に定義に沿って証明することもできる。
（それは高校数学の美しい物語などを参照）
いまはこれが本題ではないから省略する。

さて、オイラー関数の求め方を挙げる。

◆定理◆
$n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$ を素因数分解とする。
このとき、
$\phi (n)=\phi (p_1^{e_1})\phi (p_2^{e_2})\cdots \phi (p_r^{e_r})$
である。
（ここで前命題から $\phi (p_i^{e_i})=p_i^{e_i-1}(p_i-1)$ であった）

これについては、 $\mathbb{Z}/n\mathbb{Z}$ を中国剰余定理により素べきの直積に
分解し、その前後で単数群を考えることで証明できた。
この方法しか知らなかったが、メビウスの反転公式により
証明する方法も実は有名なようだ。

＜証明＞
前命題により、メビウスの反転公式を $f(n)=\phi (n),g(n)=n$ として用いると
$\displaystyle \phi (n)=\sum_{d|n}\mu \left(\frac{n}{d}\right) d=\sum_{d|n}\mu \left(d\right) \frac{n}{d} =n\sum_{d|p_1p_2\cdots p_r}\mu \left(d\right) \frac{1}{d}$
が成立する。

ここで、
$\displaystyle \sum_{d|p_1p_2\cdots p_r}\mu \left(d\right) \frac{1}{d}=\left( 1-\frac{1}{p_1}\right)\left( 1-\frac{1}{p_2}\right)\cdots \left( 1-\frac{1}{p_r}\right)$
（右辺の展開を注意深く観察すると分かる）
が成立するので、

$\displaystyle \phi (n)=n\left( 1-\frac{1}{p_1}\right)\left( 1-\frac{1}{p_2}\right)\cdots \left( 1-\frac{1}{p_r}\right)$
$\displaystyle =p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}\left( 1-\frac{1}{p_1}\right)\left( 1-\frac{1}{p_2}\right)\cdots \left( 1-\frac{1}{p_r}\right)=\phi (p_1^{e_1})\phi (p_2^{e_2})\cdots \phi (p_r^{e_r})$
となる。
＜証明終了＞

これもかなりエレガントな方法だと思う。
なぜオイラー関数を学んだときにこの方法に
行きつかなかったのか悔やまれる。

利用例その３：円分多項式

自然数 $n$ を固定する。

◆定義◆
$\zeta =\exp{2\pi \sqrt{-1}/n}\in\mathbb{C}$ とする。
このとき $\displaystyle {\Phi}_n(x)=\prod_{(n,i)=1}(x-{\zeta}^i)\in\mathbb{Q}[ x]$ を $n$ 次の円分多項式と呼ぶ。

この ${\Phi}_n(x)$ とは原始 $n$ 乗根のみを根とする多項式である。
${\Phi}_n(x)\in\mathbb{Q}[ x]$ となっていることは省略する。

円分多項式について次が従う。

◆命題◆
$\displaystyle {\Phi}_n(x)=\prod_{d|n}(x^{\frac{n}{d}}-1)^{\mu (d)}$ が成り立つ。
特に、 ${\Phi}_n(x)\in \mathbb{Z}[ x]$ であって、次数は $\phi (n)$ である。

＜証明＞
$x^n-1$ の根は積についての位数 $d|n$ により原始 $d$ 乗根全体の集まりと
思えるから、
$\displaystyle x^n-1=\prod_{d|n}{\Phi}_d(x)$
が成立する。

これの $\log$ をとったときのメビウスの反転公式を用いることで、
$\displaystyle \log{(x^n-1)}=\sum_{d|n}\log{\left({\Phi}_d(x)\right) }$
から
$\displaystyle \log({\Phi}_n(x))=\sum_{d|n}\mu (d)\log{(x^{\frac{n}{d}}-1)}$
が成立する。