メビウス関数
メビウス関数(メビウスかんすう)は、数論や組合せ論における重要な関数である。メビウスの輪で有名なドイツの数学者アウグスト・フェルディナント・メビウス (August Ferdinand Möbius) が1831年に紹介したことから、この名が付けられた。
定義
0 を含めない自然数において、メビウス関数 μ(n) は全ての自然数 n に対して定義され、n を素因数分解した結果によって -1、0、1 のいずれかの値をとる。
メビウス関数は次のように定義される(ただし 1 は 0 個の素因数を持つと考える):
- μ(n) = 0 (n が平方因子を持つ(平方数で割り切れる)とき)
- μ(n) = (-1)k (n が相異なる k 個の素因数に分解されるとき)
- n が相異なる偶数個の素数の積ならば μ(n) = 1
- n が相異なる奇数個の素数の積ならば μ(n) = -1
計算例
例えば、6 = 2 × 3 であり、素数の 2 乗で割り切れず、素因数の数は 2 で偶数であるから、μ(6) = 1 である。また、12 = 22 × 3 であり、2 の 2 乗で割り切れるため、μ(12) = 0 である。
n = 1, ..., 10 での μ(n) の値を示す(テンプレート:OEIS) テンプレート:Indent
性質
メビウス関数は乗法的な関数である。すなわち、互いに素な m, n に対して、 テンプレート:Indent となる。また、m, n が互いに素でなければ、 テンプレート:Indent である。
基本公式
また次のような基本的な公式が成り立つ。 テンプレート:Indent これは n = 1 のときは自明である。n が 1 より大きい場合について、平方因子をもつ因数 d については μ(d) = 0 であるから、n が無平方数である場合を見ておけばよい。n は k 個の素数の積であるとする。n の約数は、その素因数をいくつか掛け合わせたものになるが、偶数個(0 を含む)の素因数からなる約数 d に対しては μ(d) = 1 であり、奇数個の素因数からなる約数 d に対しては μ(d) = −1 となるから、因子の組合せの数を考慮すれば テンプレート:Indent が確かめられる。最後から二つ目の等号は二項定理による。
より一般に、 f を乗法的な数論的関数とすると、
が成り立つ。
メビウスの反転公式
関数 f(n), g(n) について、次の 2 つの命題は同値である。
- <math>g(n) = \sum_{d\mid n}f(d).</math>
- <math>f(n) = \sum_{d\mid n}g(d)\,\mu\!\left(\frac{n}{d}\right).</math>
これをメビウスの反転公式という。
例と応用
n の約数の総和を表す関数 σ(n) はその定義より テンプレート:Indent となるが、これに反転公式を適用すると テンプレート:Indent となる。
次の例は非常に重要な関数 Λ(n) を定義している(この関数はフォン・マンゴルトの関数 en:Von Mangoldt function と呼ばれる)。 テンプレート:Indent この式は、素因数の一意分解定理と同値であるが、反転すると テンプレート:Indent となる。和の中を具体的に計算すると テンプレート:Indent が得られる。
先の基本公式 (*) に適用すれば、ゼータ関数による母関数表示を得る。 テンプレート:Indent
エラトステネスの篩
既に知っている素数で割れる自然数を数表から篩い落とすことで新たな素数を順次決定していく操作はエラトステネスの篩として知られている。ゆえに、知っている素数で割れない自然数全体の集合を指定する方法が与えられることと、このエラトステネスの篩にかけることとは等価である。
集合を指定する方法の一つは、その指示函数を与えることである。いま、p1 から pk が素数として決定されたものとし、そのような素数全部の積を P とする。また、自然数 n と P との最大公約数を (n, P) と表せば、n が決定済みの素数で割れることと、(n, P) > 1 となることとは同値である。このとき、十分大きな自然数 N を考え、N 以下の自然数 n のうち、決定済みの素数 p1, ..., pk で割れない自然数全体の集合を E とおくと、基本公式によって E の指示函数 χE は
- <math>\chi_E(n) = \sum_{d\mid(n,P)}\mu(d)</math>
で与えられることがわかるから、これをエラトステネスの篩のメビウス函数を用いた表現と考えることができる(手続きとしては、χE(n) を計算することは知っている素数で順番に割っていくことに他ならないから、単に表現の仕方を変えただけである)。特に、χE(n) = 1 を満たす最小の n を pk+1 とすればこれは新しい素数であり、再び同様の手続きにしたがって次々に素数を決定することができる。
μ(n)
μ(n) = 0 となる必要十分条件は、n が素数の2乗で割り切れることである。このような n の数列は次のようになる。(テンプレート:OEIS):
4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28, 32, 36, 40, 44, 45, 48, 49, 50, 52, 54, 56, 60, 63, ...
n が素数であれば、μ(n) = −1 となる。しかし、逆は成り立たない。最初に μ(n) = −1 となる合成数 n は30 = 2·3·5 である。3つの異なる素数の積からなる数(楔数という)からできる数列は次のようになる。(テンプレート:OEIS2C) :
30, 42, 66, 70, 78, 102, 105, 110, 114, 130, 138, 154, 165, 170, 174, 182, 186, 190, 195, 222, ...
同様に5つの異なる素数の積からなる数列は、(テンプレート:OEIS2C) :
2310, 2730, 3570, 3990, 4290, 4830, 5610, 6006, 6090, 6270, 6510, 6630, 7410, 7590, 7770, 7854, 8610, 8778, 8970, 9030, 9282, 9570, 9690, 9870, 10010,10230,10374,10626,11130,11310,11730,12090,12210,12390,12558,12810, 13090,13110, ...
上の数列と似ているが、5種類の素数の積で表される(素数の 2乗で割り切れてもよい)数列である。 この中にはμ(n) = 0となるnも含まれる。例えば、4620 = 2²·3·5·7·11であり、μ(4620) = 0である。(テンプレート:OEIS2C) :
2310, 2730, 3570, 3990, 4290, 4620, 4830, 5460, 5610, 6006, 6090, 6270, 6510, 6630, 6930, 7140, 7410, 7590, 7770, 7854, 7980, 8190, 8580, 8610, 8778, 8970, 9030, 9240, 9282, 9570, 9660, 9690, 9870,10010,10230,10374, 10626,10710,10920,11130, ...