メビウス関数

出典: フリー百科事典『ウィキペディア（Wikipedia）』

メビウス関数（メビウスかんすう）は、数論や組合せ論における重要な関数である。メビウスの輪で有名なドイツの数学者アウグスト・フェルディナント・メビウス (August Ferdinand Möbius) が1831年に紹介したことから、この名が付けられた。

[編集] 定義

メビウス関数 μ(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 = 2² × 3 であり、2 の 2 乗で割り切れるため、μ(12) = 0 である。

n = 1, ..., 10 での μ(n) の値を示す：

μ(1) = 1, μ(2) = -1, μ(3) = -1, μ(4) = 0, μ(5) = -1, μ(6) =1, μ(7) = -1, μ(8) = 0, μ(9) = 0, μ(10) = 1

[編集] 性質

メビウス関数は乗法的な関数である。すなわち、互いに素な m, n に対して、

μ(mn) = μ(m)μ(n)

となる。また、m, n が互いに素でなければ、

μ(mn) = 0

である。

[編集] 基本公式

また次のような基本的な公式が成り立つ。

(*) $\sum_{d|n} \mu (d) = \begin{cases} 1 & (n = 1)\\ 0 & (n \ne 1) \end{cases}$

これは n = 1 のときは自明である。n が 1 より大きい場合について、平方因子をもつ因数 d については μ(d) = 0 であるから、n が無平方数である場合を見ておけばよい。n は k 個の素数の積であるとする。n の約数は、その素因数をいくつか掛け合わせたものになるが、偶数個（0 を含む）の素因数からなる約数 d に対しては μ(d) = 1 であり、奇数個の素因数からなる約数 d に対しては μ(d) = -1 となるから、因子の組合せの数を考慮すれば

$\sum_{d|n} \mu (d) = {}_k{\rm C}_0 -{}_k{\rm C}_1 + {}_k{\rm C}_2 -{}_k{\rm C}_3 + \cdots + (-1)^k {}_k{\rm C}_k$

$= \sum_{i=0}^k (-1)^k {}_k{\rm C}_i = (1-1)^k =0$

が確かめられる。最後から二つ目の等号は二項定理による。

より一般に、 f を乗法的な数論的関数とすると、

(**)

∑	μ(d)f(d) =	∏	(1 − f(p))
d \| n		p \| n

が成り立つ。

[編集] メビウスの反転公式

関数 f(n), g(n) について、次の 2 つの命題は同値である。

$g(n) = \sum_{d\mid n}f(d).$
$f(n) = \sum_{d\mid n}g(d)\,\mu\!\left(\frac{n}{d}\right).$

これをメビウスの反転公式という。

[編集] 例と応用

n の約数の総和を表す関数 σ(n) はその定義より

$\sigma(n) = \sum_{d\mid n} d$

となるが、これに反転公式を適用すると

$n = \sum_{d|n} \mu\left(\frac {n}{d}\right) \sigma(d)$

となる。

次の例は非常に重要な関数 Λ(n) を定義している（この関数はフォン・マンゴルトの関数と呼ばれる）。

$\log n = \sum_{d \mid n} \Lambda (d)$

この式は、素因数の一意分解定理と同値であるが、反転すると

$\Lambda (n) = \sum_{d|n} \mu (d) \log \frac {n}{d}$

となる。和の中を具体的に計算すると

$\Lambda (n) = \begin{cases} \log p & (n = p^k, k>0) \\ 0 & (\mbox{otherwise}) \end{cases}$

が得られる。

先の基本公式 (*) に適用すれば、ゼータ関数による母関数表示を得る。

$\sum_{n=1}^\infty \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)}$

[編集] エラトステネスの篩

既に知っている素数で割れる自然数を数表から篩い落とすことで新たな素数を順次決定していく操作はエラトステネスの篩として知られている。ゆえに、知っている素数で割れない自然数全体の集合を指定する方法が与えられることと、このエラトステネスの篩にかけることとは等価である。

集合を指定する方法の一つは、その特性関数を与えることである。いま、z 以下の全ての素数が分かっているものとして、そのような素数全部の積を P とする。また、自然数 n と P との最大公約数を (n, P) と表す。このとき、z 以下の素数で割れない自然数全体の集合を E とおくと、E の特性関数 χ_E は

$\chi_E(n) = \sum_{d\mid(n,P)}\mu(d)$

とメビウス関数を使って表せる。実際、n がp 以下の素数で割れないことは (n, P) = 1 となることに同値であり、これは基本公式 (*) そのものである。

したがって、x 以下のEの元の個数は、

$\sum_{d\mid P}\mu(d)|A_d|=\sum_{d\mid P}\mu(d)\left[\frac{x}{d}\right]$ （ここで A_d は x 以下の d の倍数の集合を表す）

と表すことができる。

z より大きい全ての素数は E に属しているので、結局エラトステネスの篩は、x 以下の素数の個数を表す関数 π(x) に関する公式

$\pi(n) \leq \pi(z) + 1 + \sum_{d\mid P} \mu(d)\left[\frac{n}{d}\right]$

に他ならない。特に z = n ^1/2 のとき、等式が成り立つ。

|[n/d ]-n/d |< 1であるから、(**)を使って、

$\pi(n) \leq \pi(z) + 1 + \sum_{d\mid P}(\mu(d)\frac{n}{d} + 1) = \pi(z) + 1 + n\sum_{d\mid P} \frac{\mu(d)}{d} + \Omega(P) = \pi(z) + 1 + n\prod_{p\leq z}(1 - \frac{1}{p}) + 2^{\pi(z)}$

が成り立つ。この公式を使って

$\lim_{x\to \infin} \frac{\pi (x)}{x} = 0$

を証明することができる（ z=log n とおき、素数の逆数の和が発散することを用いる）。このエラトステネスの篩の定量化はルジャンドルによるもので、ふるい法の最初の定量的利用といえる。

しかし、この方法は 2^π(z) が z に比べて非常に大きく、小さな z に対してしか非自明な評価を与えることができないという欠点を持っている。

ヴィーゴ・ブルンはこの方法を改良し、より広い状況で非自明な評価を与えることに成功した。その後、アトル・セルバーク、ジョン・バークリー・ロッサーなどによって様々なふるい法が考案され、双子素数など、多くの数論上の問題の研究に広く応用されている。

一般に、集合 S に対して μ(S)=(-1)^|S| とおくと、

$\sum_{T\subset S} \mu (T) = \begin{cases} 1 & (S = \phi)\\ 0 & (S \ne \phi) \end{cases}$

が成り立つ。ここである集合 A とその部分集合 A₁, A₂, ..., A_n に対して、

$A_I=\cap_{i\in I}A_i, A_{\phi}=A$

とおき、 E を A の元でどの A_i にも属さないものの集合とすると、

E の特性関数 χ_E は

$\chi_E(a) = \sum_{I\subset \{ 1, 2, \cdots, n\}(a\in A_I)}\mu(I)$

と表せる。したがって、

$|E|=\sum_{I\subset \{ 1, 2, \cdots, n\}}\mu(I)|A_I|$

と表せる。これは包含と除去の原理である。

[編集] μ(n)

μ(n) = 0 となる必要十分条件は、n が素数の2乗で割り切れることである。このような n の数列は次のようになる。（外部リンク OEIS（数列辞典）: A013929）:

 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つの異なる素数の積からなる数列は次のようになる。(OEIS: A007304):

 30,  42,  66,  70,  78, 102, 105, 110, 114, 130, 138, 154, 
165, 170, 174, 182, 186, 190, 195, 222, ...

同様に5つの異なる素数の積からなる数列は、(OEIS : A046387):

 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である。 (OEIS : A051270):

 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, ...

[編集] 関連項目

[編集] 外部リンク

Möbius Function -- From MathWorld（メビウス関数）（英語）

"http://ja.wikipedia.org../../../%E3%83%A1/%E3%83%93/%E3%82%A6/%E3%83%A1%E3%83%93%E3%82%A6%E3%82%B9%E9%96%A2%E6%95%B0.html" より作成

カテゴリ: 数論 | 整数論的関数 | 組合せ論 | 数学に関する記事