メビウス関数

曖昧さ回避 この項目では、数論的メビウス関数について説明しています。組合せ論的メビウス関数については「隣接代数 (順序理論)」をご覧ください。

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

定義

0 を含めない自然数において、メビウス関数 μ(n) は全ての自然数 n に対して定義され、n を素因数分解した結果によって -1、0、1 のいずれかの値をとる。

メビウス関数は次のように定義される（ただし 1 は 0 個の素因数を持つと考える）：

  • μ(n) = 0 （n が平方因子を持つ（1以外の平方数で割り切れる）とき）
  • μ(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) の値を示す[1]

μ(1) = 1, μ(2) = -1, μ(3) = -1, μ(4) = 0, μ(5) = -1, μ(6) =1, μ(7) = -1, μ(8) = 0, μ(9) = 0, μ(10) = 1
50 以下の n に対する μ(n) の値
50 以下の n に対する μ(n) の値

性質

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

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

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

μ(mn) = 0

である。

基本公式

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

∑ d ∣ n μ ( d ) = { 1 ( n = 1 ) 0 ( n ≠ 1 ) {\displaystyle \sum _{d\mid n}\mu (d)={\begin{cases}1&(n=1)\\0&(n\neq 1)\end{cases}}}
(1)

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

∑ d ∣ n μ ( d ) = k C 0 − k C 1 + k C 2 − k C 3 + ⋯ + ( − 1 ) k k C k = ∑ i = 0 k ( − 1 ) i k C i = ( 1 − 1 ) k = 0 {\displaystyle {\begin{aligned}\sum _{d\mid n}\mu (d)&={}_{k}\mathrm {C} _{0}-{}_{k}\mathrm {C} _{1}+{}_{k}\mathrm {C} _{2}-{}_{k}\mathrm {C} _{3}+\dotsb +(-1)^{k}{}_{k}\mathrm {C} _{k}\\[-10pt]&=\sum _{i=0}^{k}(-1)^{i}{}_{k}\mathrm {C} _{i}=(1-1)^{k}=0\end{aligned}}}

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

また、μ(n) は 1 の原始 n 乗根の和である。すなわち

μ ( n ) = ∑ gcd ( k , n ) = 1 1 ≤ k ≤ n exp ⁡ ( 2 π k i / n ) {\displaystyle \mu (n)=\!\sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\!\exp(2\pi ki/n)}

が成り立つ。n > 1 のとき 1 の n 乗根の和は 0 であるから、これは上の公式 (1) の別証明を与える。

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

∑ d | n μ ( d ) f ( d ) = ∏ p | n ( 1 − f ( p ) ) {\displaystyle \sum _{d|n}\mu (d)f(d)=\prod _{p|n}(1-f(p))}
(2)

が成り立つ。

メビウスの反転公式

詳細は「メビウスの反転公式」を参照

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

  1. g ( n ) = ∑ d ∣ n f ( d ) . {\displaystyle g(n)=\sum _{d\mid n}f(d).}
  2. f ( n ) = ∑ d ∣ n g ( d ) μ ( n d ) . {\displaystyle f(n)=\sum _{d\mid n}g(d)\,\mu \!\left({\frac {n}{d}}\right).}

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

例と応用

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

σ ( n ) = ∑ d ∣ n d {\displaystyle \sigma (n)=\sum _{d\mid n}d}

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

n = ∑ d | n μ ( n d ) σ ( d ) {\displaystyle n=\sum _{d|n}\mu \left({\frac {n}{d}}\right)\sigma (d)}

となる。

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

log ⁡ n = ∑ d ∣ n Λ ( d ) {\displaystyle \log n=\sum _{d\mid n}\Lambda (d)}

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

Λ ( n ) = ∑ d | n μ ( d ) log ⁡ n d {\displaystyle \Lambda (n)=\sum _{d|n}\mu (d)\log {\frac {n}{d}}}

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

Λ ( n ) = { log ⁡ p ( n = p k , k > 0 ) 0 ( otherwise ) {\displaystyle \Lambda (n)={\begin{cases}\log p&(n=p^{k},k>0)\\0&({\text{otherwise}})\end{cases}}}

が得られる。

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

∑ n = 1 ∞ μ ( n ) n s = 1 ζ ( s ) {\displaystyle \sum _{n=1}^{\infty }{\frac {\mu (n)}{n^{s}}}={\frac {1}{\zeta (s)}}}

エラトステネスの篩

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

集合を指定する方法の一つは、その指示函数を与えることである。いま、p1 から pk が素数として決定されたものとし、そのような素数全部の積を P とする。また、自然数 n と P との最大公約数を (n, P) と表せば、n が決定済みの素数で割れることと、(n, P) > 1 となることとは同値である。このとき、十分大きな自然数 N を考え、N 以下の自然数 n のうち、決定済みの素数 p1, ..., pk で割れない自然数全体の集合を E とおくと、基本公式によって E の指示函数 χE は

χ E ( n ) = ∑ d ∣ ( n , P ) μ ( d ) {\displaystyle \chi _{E}(n)=\sum _{d\mid (n,P)}\mu (d)}

で与えられることがわかるから、これをエラトステネスの篩のメビウス函数を用いた表現と考えることができる（手続きとしては、χE(n) を計算することは知っている素数で順番に割っていくことに他ならないから、単に表現の仕方を変えただけである）。特に、χE(n) = 1 を満たす最小の n を pk+1 とすればこれは新しい素数であり、再び同様の手続きにしたがって次々に素数を決定することができる。

μ(n)

μ(n) = 0 となる必要十分条件は、n が素数の2乗で割り切れることである。このような n の数列は次のようになる。[2] : 

 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つの異なる素数の積からなる数（楔数という）からできる数列は次のようになる。[3] : 

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

同様に5つの異なる素数の積からなる数列は、[4] : 

 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 = 22・3・5・7・11 であり、μ(4620) = 0である。[5] : 

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

関連項目

脚注

[脚注の使い方]
  1. ^ オンライン整数列大辞典の数列 A008683
  2. ^ オンライン整数列大辞典の数列 A013929
  3. ^ A007304
  4. ^ A046387
  5. ^ A051270

参考文献

  • Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (5th ed.), Oxford: Oxford University Press, ISBN 978-0-19-853171-5 
  • 高木貞治『初等整数論講義』（第2版）共立出版。 

外部リンク

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