メビウスの反転公式 | メビウス関数の証明を通じて添え字の学習！
" メビウスの反転公式 “は、メビウスの輪で知られるメビウスが導入したメビウス関数についての公式です。大学の初等整数論や可換環論や体論の入門的な講義で出てきたりします。
メビウス関数についての基本的な性質を証明することで、論理的な思考の良い練習になるかと思います。
また、添え字と対応する項についての和の取り方の良いトレーニングにもなります。
大学の数学科などで、レポート課題等でメビウス関数がらみの問題が出題されたりすることもあったりして、単位の取得にも役立つかもしれません。
このブログ記事で用いる記号ですが、自然数全体から成る集合を N と表しています。
メビウスの反転公式 :メビウス関数の定義
【定義】
μ : N → {－1, 0, 1} で次を満たすものをメビウス関数という。
(1) 自然数 1 に対して、μ(1) = 1
(2) 2 以上の自然数 n について、
n = p1k1p2k2 … psks を素因数分解とするとき、
k1 = k2 = … = ks = 1 ならば、
μ(n) = (-1)s である。
ki > 1 となる i (1 ≦ i ≦ s) があれば、
μ(n) = 0 である。
(1) については、関数 μ が自然数 1 に対して、1 を対応させるということです。
(2) で、n の素因数分解に現れている素数 p1, p2, … , ps を n の素因数（素因子）といいます。自然数 s は、n の素因数分解に使われた素因数の種類が s 個ということです。
すべての素因数の指数が 1 である場合と、少なくとも 1 つは指数が 2 以上となっている素因数がある場合に分かれます。
2 以上の自然数 n の素因数分解において、「すべての素因数の指数が 1 である」ということの否定が「少なくとも 1 つは指数が 2 以上となっている素因数がある」ということです。
※ 最大公約元という記事で、素因数分解の証明を述べています。
数学の論理から、どちらか一方の場合のみが起こります。
「すべての素因数の指数が 1 である」場合には、メビウス関数 μ は n に対して (－1)s を対応させます。
s が奇数だと μ(n) = －1 で、
s が偶数だと μ(n) = 1 です。
素因数分解に使われている素因数の種類が奇数個か偶数個かで値が分かれます。
一方、「少なくとも 1 つは指数が 2 以上となっている素因数がある」場合だと、μ は n に対して 0 を対応させます。
それでは、このメビウス関数 μ の定義から導かれる性質について、それらを証明します。
基本性質 1
【命題 1】
自然数 m と n の最大公約数が 1 とする。
このとき、μ(mn) = μ(m)μ(n) である。
＜証明＞
m か n のうち、どちらかが「少なくとも 1 つは指数が 2 以上となっている素因数がある」とします。そうすると、mn の素因数分解にも、その指数が 2 以上となっている素因数が現れます。
そのため、μ(mn) = 0 = μ(m)μ(n) となり、成立しています。
よって、以下では、m と n のどちらも「すべての素因数の指数が 1 」だとして議論を進めます。
m と n の素因数分解を
m = p1・・・ps ,
n = q1・・・qt とします。
すると、
μ(m)μ(n) = (－1)s × (－1)t
= (－1)s+t
仮定より、m と n の最大公約数が 1 なので、
mn = p1・・・psq1・・・qt
が mn の素因数分解です。
よって、mn の素因数分解に使われている素因数の種類は (s + t) 個で、すべての指数が 1 となっているので、μ の定義から、μ(mn) = (－1)s+t
以上より、μ(mn) = (－1)s+t = μ(m)μ(n) となり成立しています。【証明完了】
メビウス関数の定義、そして基本性質の証明で、素因数分解の一意性が効いています。この【命題 1】から、メビウス関数は乗法的であるといわれます。
メビウスの反転公式 :添え字と和の取り方
大学の数学では、シグマ計算を使うことが多いです。
シグマ記号の計算は、それぞれの添え字について、項を対応させ、項たち全部で和をとるということです。
添え字が動く範囲も大切になります。
次の【命題 2】では、自然数 n が 1 つ与えられたときに、添え字 d が n の正の約数全体を動きます。
n の 1 つの正の約数 d に対して、μ(d) という項が 1 つ対応します。そのため、n の正の約数の分だけ、項が出現することになります。
また、自然数 x と y について、x が y の約数であるときに、x | y と表すことにします。
基本性質 2
＜証明＞
n = 1 のとき、n の正の約数は 1 しかないので、μ(1) = 1 となり成立します。
以下では、n ≧ 2 のときを議論します。
n = p1k1・・・psks を n の素因数分解とします。
d が n の正の約数全体を動くとき、次の 3 パターンになります。
＜パターン 1＞
n の正の約数のうち、その約数 d を素因数分解したときに、指数が 2 以上となっている素因数が 1 つでもあれば、μ(d) = 0 となります。
＜パターン 2＞
d = 1 のとき、μ(d) = 1 です。
＜パターン 3＞
パターン 1 でもパターン 2 でもないとき、n の正の約数 d は p1 から ps までの異なる s 個の素因数から t 個を選び、それらをすべて掛けたものになります。
すなわち、それらは、
pi1・・・pit という形です。
ただし、t は 1 ≦ t ≦ s の自然数です。
μ(pi1・・・pit) = (－1)t で、異なる s 個から t 個を選ぶ組合せは sCt 通りです。
そのため、1 以上 s 以下の自然数 t について、
(－1)t を sCt 個足し合わせることになります。
これらの n の正の約数 d について、μ(d) すべての加法を計算します。
μ(d) = 0 のときは、0 を加えても値が変わらないことから、書かないことにすると、
Σd|n μ(d)
= μ(1) + ΣtsCt(－1)t
= 1 + ΣtsCt(－1)t
= sC0(－1)0 + ΣtsCt(－1)t
t が 1 から s まで動くことから、
二項定理より、
Σd|n μ(d) = (1 － 1)s = 0【証明完了】
証明の最後に、
あえて 1 を sC0 に書き換え二項定理を使いました。
添数集合
シグマ計算をするとき、添え字を動かしました。この添え字が動く範囲を表す集合を添数集合といいます。
大学の数学では、添数集合のそれぞれの元（要素）に対して 1 つの項を対応させ、それらの項をすべて足し合わせるという考え方をします。
そこで、このブログの主定理であるメビウスの反転公式を証明するときに使う添数集合について、予め述べておきます。
記号ですが、二つの自然数 x と y について、x を y で割ったときの商を x/y と表すことにします。
自然数 n を 1 つ固定し、その n を第 1 成分に書き、第 2 成分と第 3 成分に条件を満たす自然数を配置した組から成る添数集合を考えます。
自然数全体から成る集合を N と表しています。
{(n,d,e) | d,e∈N, d|n , e|d}= S’,
{(n,es,e) | e,s∈N, e|n, s|(n/e)}= S"
この二つの集合 S’ と S" は同じ集合になります。二つの集合が等しいことを認めて、メビウスの反転公式を証明します。
その証明の後で、S’ と S" が等しいことを示します。
まずは、具体的な例で、どのような元が現れているのかを確認してみます。
n = 8 として、第 1 成分に固定し、S’ の元をすべて書き出してみます。
第 2 成分の d として、8 の正の約数である 1, 2, 4, 8 が現れます。そして、各 d の値についての正の約数を第 3 成分の e の値とします。
(8, 1, 1),
(8, 2, 1), (8, 2, 2),
(8, 4, 1), (8, 4, 2), (8, 4, 4),
(8, 8, 1), (8, 8, 2), (8, 8, 4), (8, 8, 8)
次に S2 の元を書き出します。
第 3 成分の 8 の正の約数 e の値 1 つについて、n/e の正の約数 s を決めてから第 2 成分の値を決定するという手順です。
(8, 1×1, 1), (8, 1×2, 1), (8, 1×4, 1),
(8, 1×8, 1), (8, 2×1, 2), (8, 2×2, 2),
(8, 2×4, 2), (8, 4×1, 4), (8, 4×2, 4),
(8, 8×1, 8)
第 2 成分の掛け算の値を計算すると、順番が入れ替わっているだけで、S’ の元がすべて現れています。
S’ = S" となります。
そのため、「S’ の元である組 1 個に対して 1 つの項が現れ、すべての項を足し合わせるということ」と「S" の元である組 1 個に対して 1 つの項が現れ、すべての項を足し合わせるということ」が総和として同じ値になります。
加法なので、足す順番を入れ替えても総和が同じ値というのが、メビウスの反転公式を証明するときの決め手になります。
記号の注意ですが、s | n/e、つまり自然数 s が 自然数 n/e の正の約数なので、n/e は s で割り切れます。n/e を s で割ったときの商を n/es と表します。
メビウスの反転公式 :いよいよ証明
＜証明＞
自然数 n が与えられたとします。
n のそれぞれの正の約数 d について、g(d) を仮定の f を使った式に書き換えるところから式の変形をスタートします。
Σd|n μ(u/d)g(d)
= Σd|n μ(n/d)(Σe|d f(e))
= Σ(n,d,e)∈S’ μ(n/d)f(e)
= Σ(n,es,e)∈S" μ(n/es)f(e)
= Σe|n f(e)(Σs|(n/e) μ(n/es))
ここで【命題 2】より、自然数 n/e が 2 以上のとき、n/e の正の約数すべてで和をとるとシグマの値が 0 になります。
0 を足しても値は変わらないので、その部分を除きます。
すると、残るのは n/e が 1 のときのみになります。
n/e = 1 となるのは、e = n のときです。
そして、e = n のとき n/e = 1 の正の約数 s は s = 1 のみです。
これらのことを踏まえて、最後の式を書き換えます。
Σd|n μ(n/d)g(d)
= Σe|n f(e)(Σs|(n/e) μ(n/es))
= f(n)(Σs|(n/n) μ(n/n×1/s))
= f(n) × μ(1)
= f(n) × 1 = f(n)【証明完了】
ちなみに、メビウスの反転公式ですが、結論の f(n) の式で、n | d のとき、(n/d) も n の正の約数なので、μ(d)g(n/d) と書き換えることができます。
d が n の正の約数をすべて走るときに、n/d も n のすべての正の約数を走ります。
この f と g の例として、f をオイラーのファイ関数 φ、g として恒等写像 g(n) = n が挙げられます。
※ ファイ関数については、一つ前の記事で解説をしています。
このメビウスの反転公式を使って、φ(n) の値をメビウス関数の定義を考慮しながら求めることもできます。
※ φ(n) については、リンク先の記事で解説をしています。
それでは、証明の鍵となった二つの添数集合が等しいことの証明をします。
S’ ⊂ S" かつ S" ⊂ S’ を示すと、S’ と S" が等しい集合ということになります。
添数集合が等しいことの証明
{(n,d,e) | d,e∈N, d|n , e|d}= S’,
{(n,es,e) | e,s∈N, e|n, s|(n/e)}= S"
＜証明＞
(n, d, e) ∈ S’ を任意にとります。
d | n, e | d より、
n = du (u は自然数),
d = ek (k は自然数) と表すことができます。
よって、n = (ek)u = e(ku) より、
e | n です。
さらに、n ÷ e = n/e = ku より、
k は自然数 n/e の正の約数だから、
k | (n/e) です。
したがって、(n, ek, e) ∈ S" であり、
(n, d, e) = (n, ek, e) だから、
(n, d, e) ∈ S" です。
部分集合の定義から、S’ ⊂ S" が示せました。
次に、(n, es, e) ∈ S" を任意にとります。
e | n より n/e = t (t は自然数) と表せます。
また、s | (n/e) より n/e = sk (k は自然数) と表せます。
よって、n = e(sk) = (es)k となり、
es | n です。
また、e | es より、(n, es, s) ∈ S1 です。
ゆえに、部分集合の定義から S" ⊂ S’ です。
S’ ⊂ S" かつ S" ⊂ S’ なので、S’ = S" であることが示せました。【証明完了】
部分集合の定義は、大学の数学を学習するときに、よく使います。部分集合の定義について、慣れておくと良いかと思います。
この添数集合を使って、メビウスの反転公式の乗法版も証明できます。先ほどの加法版のときは、e を固定してから f(e) について分配法則でくくり出しました。
乗法版では、e を固定してから f(e) が使われているところを指数法則でまとめます。
加法版のときと同じ要領になります。
上で示した【命題 2】の内容が活躍します。
反転公式の書き換え
【反転公式の乗法版】
C(x) を有理関数体とし、
f, g : N → C(X)－{0} をメビウス関数とする。
また、定数 n は自然数とする。
このとき、
g(n) = Πd|n f(d) ならば、
f(n) = Πd|n g(d)μ(n/d) である。
＜証明＞
仮定より、g(n) を書き換え
Πd|n g(d)μ(n/d)
= Πd|n (Πe|d f(e))μ(n/d)
= Π(n,d,e)∈S1 f(e)μ(n/d)
= Π(n,es,e)∈S1 f(e)μ(n/es)
= Πe|s f(e)(Σs|(n/e) μ(n/es))
※ e を固定して s を動かしたとき、f(e) どうしの積に指数法則を適用。
【命題２】で述べた内容から、加法版のときと同様に、自然数 n/e が 2 以上のとき、n/e のすべての正の約数で和をとると、シグマの値が 0 となります。
f(e)0 = 1 より、正味の値は n = e のときです。
そして、n = e のとき s = 1 ということに注意します。
よって、
Πd|n g(d)μ(n/d)
= Πe|s f(e)(Σs|(n/e) μ(n/es))
= f(n)(Σs|(n/n) μ(n/ns))
= f(n)μ(1) = f(n)1
= f(n) 【証明完了】
この乗法版の反転公式を使うと、有名な円分多項式を書き換えることができます。
各自然数 n について、
Φ(n) = xn－1, ψ(n) = fn(x) とおくと
Φ(n) = Πd|n fd(x) = Πd|n ψ(d) です。
メビウスの反転公式より、
ψ(n) = Πd|n Φ(d)μ(n/d)
すなわち、
fn(x) = Πd|n (xn－1)μ(n/d) です。
それでは、これで今回のブログ記事を終了します。
読んで頂き、ありがとうございました。