Möbius関数とMöbius反転公式
Abstract
Möbius関数は数論的関数の一つであり, 恒等的に1の定数関数のDirichlet逆元である. このことを利用すると, Möbius反転公式が示せる. さらに, Dirichlet畳み込みは広いクラスの関数集合への作用に拡張でき, この作用に関してもMöbius反転公式と同様の式が成立する.
Explanation
以下では, 数論的関数の集合を$ \mathcal{N} = \{ f \colon \Z_{>0} \to \mathbb{C} \}と書く. $ \mathcal{N}に加法$ +とDirichlet畳み込み$ *を定義し, $ \mathcal{N}は環をなしていると考える (詳細は数論的関数とDirichlet環を参照). Möbius関数
定義
まず, Möbius関数の定義を与える.
Definition (Möbius関数)
$ n \in \Z_{>0}に対し, 次で定義される関数$ \mu \in \mathcal{N}をMöbius関数 (Möbius function) という:
$ \mu(1) := 1と定める. $ n > 1については, $ n = \prod_{i = 1}^{k} p_i^{e_i}と素因数分解されるとすると,
$ \mu(n) = \begin{cases} (-1)^k & (\forall i, ~ e_i = 1) \\ 0 & (\mathrm{otherwise}) \end{cases}
と定める.
定義によれば, $ p^2 \mid nとなる素数$ pが存在する (このことを$ nが平方因子をもつ, という) とき, またそのときに限り, $ \mu(n) = 0となる.
性質
Möbius関数の性質としては, 次がある.
Theorem 1 (Möbius関数の性質)Theorem 1は, $ \muのDirichlet逆元が$ \mu^{-1} = k_1であること (同様に, $ k_1のDirichlet逆元が$ k_1^{-1} = \muであること) を意味する.
正整数$ n \in \Z_{>0}に対して, 次式が成立する.
$ (k_1 * \mu) (n) = \varepsilon (n).
ここで, $ k_1(n)は値が恒等的に1の定数関数であり, $ \varepsilonはDirichlet畳み込み$ *に関する単位元である.
和の形で明示的に表すと, 次式がすべての$ n \in \Z_{>0}に対して成立する:
$ \sum_{d \mid n} \mu (d) = \begin{cases} 1 & (n = 1) \\ 0 & (\mathrm{otherwise}) \end{cases}
Proof
$ n = 1のときは明らかに成り立つ.
$ n > 1とし, $ n = \prod_{i = 1}^{k} p_i^{e_i}と素因数分解されるとする. 和$ \sum_{d \mid n} \mu (d)において, $ \mu (d)が非ゼロであるのは,
$ d = \prod_{i = 1}^{k} p_i^{f_i}, \quad f_i \in \{0, 1\}
と表されるときに限るので,
$ \sum_{d \mid n} \mu (d) = \mu(1) + \mu(p_1) + \dots + \mu(p_k) + \mu(p_1 p_2) + \dots + \mu(p_{k-1} p_k) + \dots + \mu(p_1 \cdot \dots \cdot p_k)
$ = 1 + \binom{k}{1} (-1) + \binom{k}{2} (-1)^2 + \dots + \binom{k}{k} (-1)^k
$ = (1 - 1)^k = 0 = \varepsilon(n).
となり, 示された.$ \blacksquare
Möbius反転公式
まず, 一般形の反転公式を示す.
Theorem 2 (一般形の反転公式)
Dirichlet逆元を持つ数論的関数$ \alpha \in \mathcal{N}^{\times}と, 数論的関数$ f, g \in \mathcal{N}に対して, 次式が成立する:
$ f = g * \alpha \Longleftrightarrow g = f * \alpha^{-1}.
和の形で明示的に表すと, 次式がすべての$ n \in \Z_{>0}に対して成立する:
$ f(n) = \sum_{d \mid n} g(d) \alpha \left( \frac{n}{d} \right) \Longleftrightarrow g(n) = \sum_{d \mid n} f(d) \alpha^{-1} \left( \frac{n}{d} \right).
Proof
$ f = g * \alpha \Longleftrightarrow f * \alpha^{-1} = g * (\alpha * \alpha^{-1}) \Longleftrightarrow f * \alpha^{-1} = g * \varepsilon \Longleftrightarrow f * \alpha^{-1} = g. $ \blacksquare
Theorem 1より, $ k_1のDirichlet逆元が$ k_1^{-1} = \muで与えられることがわかっているので, 次のMöbius反転公式 (Möbius inversion formula) が成立する.
Corollary 3 (Möbius反転公式)
数論的関数$ f, g \in \mathcal{N}に対して, 次式が成立する:
$ f = g * k_1 \Longleftrightarrow g = f * \mu.
和の形で明示的に表すと, 次式がすべての$ n \in \Z_{>0}に対して成立する:
$ f(n) = \sum_{d \mid n} g(d) \Longleftrightarrow g(n) = \sum_{d \mid n} f(d) \mu \left( \frac{n}{d} \right).
畳み込みの一般化と反転公式
実軸上で定義される複素数値関数$ Fで, $ x \in (0, 1)に対しては$ F(x) = 0となるものの集合を$ \mathcal{F} := \{ F \colon (0, \infty) \to \mathbb{C} \mid F(x) = 0, ~ x \in (0, 1) \}と書くことにする. 数論的関数$ f \in \mathcal{N}に対して,
$ \tilde{f}(x) := \begin{cases} f(x) & (x \in \Z_{>0}) \\ 0 & (\mathrm{otherwise}) \end{cases}
と定めると$ \tilde{f} \in \mathcal{F}となる. 写像$ \tilde{\cdot} \colon \mathcal{N} \to \mathcal{F}は単射であることは容易にわかるので, 写像$ \tilde{\cdot}により数論的関数の集合$ \mathcal{N}を$ \mathcal{F}に埋め込める. よって, この埋め込みにより$ \mathcal{N} \subseteq \mathcal{F}であると考える.
さて, Dirichlet畳み込みは$ \mathcal{N}での二項演算$ * \colon \mathcal{N} \times \mathcal{N} \to \mathcal{N}であった. これを集合$ \mathcal{F}への$ \mathcal{N}の作用$ \bullet \colon \mathcal{N} \times \mathcal{F} \to \mathcal{F}へと拡張して, 反転公式の一般化をする.
$ f, g \in \mathcal{N}とする. $ f, gのDirichlet畳み込みは
$ (f * g)(n) = \sum_{d \mid n} f(d) g \left( \frac{n}{d} \right)
で定義されていた. この$ g \in \mathcal{N}を$ g \in \mathcal{F}と思うと, Dirichlet畳み込み$ *を拡張した$ \bulletは
$ (f \bullet g)(x) = \begin{cases} (f * g)(x) & (x \in \Z_{>0}) \\ 0 & (\mathrm{otherwise}) \end{cases}
を満たしていてほしい. そこで, (天下り的だが) 以下のように定義する.
Definition (畳み込み作用)
数論的関数の集合$ \mathcal{N}の集合$ \mathcal{F}への (左) 作用$ \bullet \colon \mathcal{N} \times \mathcal{F} \to \mathcal{F}を以下で定義する:
$ f \in \mathcal{N}と$ G \in \mathcal{F}に対し,$ (f \bullet G)(x) := \sum_{n \in \Z_{>0}, ~ n \le x} f(n) G\left( \frac{x}{n} \right).
Remark
$ G \in \mathcal{F}であることから$ (f \bullet G)(x) = 0, ~ x \in (0, 1)が成り立っており, 確かに$ f \bullet G \in \mathcal{F}となっている.
定義した$ \bulletが確かに作用になっていることを確認しておこう.
Lemma 4
数論的関数の集合$ \mathcal{N}の集合$ \mathcal{F}への作用$ \bullet \colon \mathcal{N} \times \mathcal{F} \to \mathcal{F}は, 可換モノイド$ (\mathcal{N}, *)のモノイド作用である, i.e., 次が成立する: $ f, g \in \mathcal{N}, $ F \in \mathcal{F}とし, $ \varepsilonをDirichlet畳み込み$ *の単位元とすると.
(1) $ f \bullet (g \bullet F) = (f * g) \bullet F.
(2) $ \varepsilon \bullet F = F.
Proof
$ x > 0を任意に取る.
(1) 定義より,
$ (f \bullet (g \bullet F))(x) = \sum_{n \in \Z_{>0}, ~ n \le x} f(n) (g \bullet F)\left( \frac{x}{n} \right)
$ = \sum_{n \in \Z_{>0}, ~ n \le x} f(n) \sum_{m \in \Z_{>0}, ~ m \le x/n} g(m) F\left( \frac{x}{mn} \right)
$ = \sum_{n, m \in \Z_{>0}, ~ n \le x, ~ mn \le x} f(n) g(m) F\left( \frac{x}{mn} \right)
$ = \sum_{n, m \in \Z_{>0}, ~ mn \le x} f(n) g(m) F\left( \frac{x}{mn} \right). $ n, m \in \Z_{>0}なので, $ mn \le xから$ n \le \frac{x}{m} \le xが従う.よって, $ n \le xかつ$ mn \le x$ \Longleftrightarrow$ mn \le xである.
さて, $ k = mnとおくと,
$ f \bullet (g \bullet F)(x)
$ = \sum_{k \in \Z_{>0}, ~ k \le x} \left( \sum_{mn = k} f(n) g(m) \right) F\left( \frac{x}{k} \right)
$ = \sum_{k \in \Z_{>0}, ~ k \le x} (f * g)(k) F\left( \frac{x}{k} \right)
$ = ((f * g) \bullet F)(x).
(2) $ (\varepsilon \bullet F)(x) = \sum_{n \in \Z_{>0}, ~ n \le x} \varepsilon(n) F\left( \frac{x}{n} \right)
$ = \begin{cases} \varepsilon (1) F\left( \frac{x}{1} \right) & (x \ge 1) \\ 0 & (\mathrm{otherwise}) \end{cases}
$ = F(x). $ \blacksquare
また, このように定義した$ \bulletは, きちんとDirichlet畳み込み$ *の拡張になっている.
Proposition 5
数論的関数$ f, g \in \mathcal{N}に対しては, 次が成立する:
$ (f \bullet g)(x) = \begin{cases} (f * g)(x) & (x \in \Z_{>0}) \\ 0 & (\mathrm{otherwise}) \end{cases}
Proof
($ x \in \Z_{>0}のとき)
$ n \le xとなる$ n \in \Z_{>0}のうち, $ \frac{x}{n} \not \in \Z_{>0}となるものに関しては, $ g\left( \frac{x}{n} \right) = 0となるので和に含まれない. よって, $ n \mid xとなるものだけ考えればよく,
$ (f \bullet g)(x) = \sum_{n \mid x} f(n) g\left( \frac{x}{n} \right) = (f * g)(x)
が成立する.
($ x \not \in \Z_{>0}のとき)
$ n \in \Z_{>0}なので$ \frac{x}{n} \not \in \Z_{>0}であるから, $ g\left( \frac{x}{n} \right) = 0. よって, $ (f \bullet G)(x) = 0.$ \blacksquare
作用の性質を利用して, 次の一般化された反転公式を示す. これはTheorem 2の拡張になっている.
Theorem 6 (一般化された反転公式)
Dirichlet逆元を持つ数論的関数$ \alpha \in \mathcal{N}^{\times}と, $ F, G \in \mathcal{F}に対して, 次式が成立する:
$ F = \alpha \bullet G \Longleftrightarrow G = \alpha^{-1} \bullet F.
和の形で明示的に表すと, 次式がすべての$ x \in (0, \infty)に対して成立する:
$ F(x) = \sum_{n \in \Z_{>0}, ~ n \le x} \alpha(n) G \left( \frac{x}{n} \right) \Longleftrightarrow G(x) = \sum_{n \in \Z_{>0}, ~ n \le x} \alpha^{-1}(n) F \left( \frac{x}{n} \right).
Proof
Lemma 4より,
$ F = \alpha \bullet G \Longleftrightarrow \alpha^{-1} \bullet F = \alpha^{-1} \bullet (\alpha \bullet G) \Longleftrightarrow \alpha^{-1} \bullet F = (\alpha^{-1} * \alpha) \bullet G
$ \Longleftrightarrow \alpha^{-1} \bullet F = \varepsilon \bullet G \Longleftrightarrow \alpha^{-1} \bullet F = G
となり, 成立する.$ \blacksquare
とくに, $ \alpha \in \mathcal{N}^{\times}が完全乗法的であれば, $ \alpha^{-1}(n) = \mu(n) \alpha(n)となるので, 次の一般化Möbius反転公式が成立する.
Corollary 7 (一般化Möbius反転公式)
数論的関数$ \mathcal{N}に積$ \cdot \colon \mathcal{N} \times \mathcal{N} \to \mathcal{N}を
$ (f \cdot g)(n) := f(n) g(n)
で定義する. 完全乗法的関数$ \alpha \in \mathcal{N}^{\times}と, $ F, G \in \mathcal{F}に対して, 次式が成立する:
$ F = \alpha \bullet G \Longleftrightarrow G = (\mu \cdot \alpha) \bullet F.
和の形で明示的に表すと, 次式がすべての$ x \in (0, \infty)に対して成立する:
$ F(x) = \sum_{n \in \Z_{>0}, ~ n \le x} \alpha(n) G \left( \frac{x}{n} \right) \Longleftrightarrow G(x) = \sum_{n \in \Z_{>0}, ~ n \le x} \mu(n) \alpha(n) F \left( \frac{x}{n} \right).
References
T. M. Apostol, "Introduction to analytic number theory", Springer-Verlag, 1976.
中村 憲, 『数論アルゴリズム』, 朝倉書店, 2009.