メビウス反転公式と直積の積公式

メビウス反転公式 $g (y) = \sum_{x \leq y} f (x) ⟺ f (y) = \sum_{x \leq y} μ (x, y) g (x)$ を使って、累積和から元の関数の値を求められる。直積半順序集合で $μ_{P \times Q} ((x, x^{'}), (y, y^{'})) = μ_{P} (x, y) μ_{Q} (x^{'}, y^{'})$ となることを使い、区間を小さな因子の積に分けてメビウス関数の値を求められる

前提

半順序集合のメビウス関数（大学院数学代数的組合せ論）

説明

有限半順序集合 $P$ 上の関数 $f$ について、その「下からの累積和」 $g (y) = \sum_{x \leq y} f (x)$ がわかっているとき、メビウス反転公式 $f (y) = \sum_{x \leq y} μ (x, y) g (x)$ で元の $f$ を取り出せます。そのためにはメビウス関数の値が必要ですが、半順序集合が直積 $P \times Q$ になっているときは $μ_{P \times Q} ((x, x^{'}), (y, y^{'})) = μ_{P} (x, y) μ_{Q} (x^{'}, y^{'})$ と因子ごとの積で求められます。約数の集合（整除関係による順序）は鎖の直積になるので、整数論の「約数についての和」の反転が典型的な使い道です。

なぜそうしてよいのか

前提の漸化式 $μ (x, x) = 1$ , $μ (x, y) = - \sum_{x \leq z < y} μ (x, z)$ は、まとめて $\sum_{x \leq z \leq y} μ (x, z) = δ (x, y)$ （ $x = y$ なら $1$ 、 $x < y$ なら $0$ ）と書けます。 $P$ の元に順序と矛盾しない番号を付け、行列 $Z = (ζ (x, y))$ （ $x \leq y$ なら $1$ 、そうでなければ $0$ ）と $M = (μ (x, y))$ （ $x \neq \leq y$ のとき $μ (x, y) = 0$ とおく）を作ると、この式は $M Z = I$ という行列の等式です。正方行列では $M Z = I$ なら $Z M = I$ も成り立ちます。 $f, g$ を行ベクトルとみると $g (y) = \sum_{x \leq y} f (x)$ は $g = f Z$ のことなので、右から $M$ を掛けて $g M = f Z M = f$ 、すなわち $f (y) = \sum_{x \leq y} g (x) μ (x, y)$ が得られます。逆に $f = g M$ なら $f Z = g M Z = g$ なので、2 つの式は同値です。

直積 $P \times Q$ の順序は $(x, x^{'}) \leq (y, y^{'}) ⟺ x \leq y$ かつ $x^{'} \leq y^{'}$ です。 $ν ((x, x^{'}), (y, y^{'})) = μ_{P} (x, y) μ_{Q} (x^{'}, y^{'})$ とおくと、区間 $[(x, x^{'}), (y, y^{'})]$ は $[x, y] \times [x^{'}, y^{'}]$ なので
$(x, x^{'}) \leq (z, z^{'}) \leq (y, y^{'}) \sum ν ((x, x^{'}), (z, z^{'})) = (x \leq z \leq y \sum μ_{P} (x, z)) (x^{'} \leq z^{'} \leq y^{'} \sum μ_{Q} (x^{'}, z^{'})) = δ (x, y) δ (x^{'}, y^{'})$
となり、 $ν$ は $P \times Q$ のメビウス関数と同じ漸化式を満たします。漸化式で値は下から一意に決まるので $ν = μ_{P \times Q}$ です。

特に長さ $a$ の鎖 $0 < 1 < \dots < a$ では漸化式から $μ (i, i) = 1$ , $μ (i, i + 1) = - 1$ , $j \geq i + 2$ なら $μ (i, j) = 0$ です。 $n = p_{1}^{a_{1}} \dots p_{k}^{a_{k}}$ の約数全体は、 $d = p_{1}^{b_{1}} \dots p_{k}^{b_{k}}$ を指数の組 $(b_{1}, \dots, b_{k})$ に対応させると鎖の直積になるので、 $d ∣ e$ のとき $μ (d, e)$ は $e / d$ が相異なる $r$ 個の素数の積なら $(- 1)^{r}$ 、ある素数の 2 乗で割り切れれば $0$ （ $e = d$ なら $1$ ）となります。

手順

与えられた条件を $g (y) = \sum_{x \leq y} f (x)$ の形に書き、どの半順序集合 $P$ 上の累積和かを確認する
$P$ （または必要な区間 $[x, y]$ ）を、鎖などメビウス関数がわかる小さな半順序集合の直積に分解する
積公式 $μ_{P \times Q} ((x, x^{'}), (y, y^{'})) = μ_{P} (x, y) μ_{Q} (x^{'}, y^{'})$ で、必要な $μ (x, y)$ をすべて求める（鎖なら $μ$ は $1, - 1, 0$ のどれか）
反転公式 $f (y) = \sum_{x \leq y} μ (x, y) g (x)$ に代入し、 $μ (x, y) \neq = 0$ の項だけを足し合わせる

例題

$12$ の正の約数全体の集合 $D_{12} = {1, 2, 3, 4, 6, 12}$ を整除関係（ $d \leq e ⟺ d ∣ e$ ）で半順序集合とみる。 $D_{12}$ 上の関数 $f$ が、すべての $n \in D_{12}$ について $d ∣ n \sum f (d) = n^{2}$ を満たすとき、 $f (12)$ を求めよ。

例題の解答

【手順 1】 $g (n) = n^{2}$ とおくと、条件は $D_{12}$ 上で $g (n) = \sum_{d \leq n} f (d)$ という累積和の形である。

【手順 2】 $12 = 2^{2} \cdot 3$ なので、 $d = 2^{b} 3^{c}$ を $(b, c)$ に対応させると、 $D_{12}$ は鎖 ${0 < 1 < 2}$ と鎖 ${0 < 1}$ の直積と同じ順序をもつ。

【手順 3】積公式より、 $d ∣ 12$ に対し $μ (d, 12) = μ_{鎖} (b, 2) μ_{鎖} (c, 1)$ 。鎖では差が $0$ なら $1$ 、差が $1$ なら $- 1$ 、差が $2$ 以上なら $0$ なので
- $d = 12 (b, c) = (2, 1)$ : $1 \cdot 1 = 1$
- $d = 6 (1, 1)$ : $(- 1) \cdot 1 = - 1$
- $d = 4 (2, 0)$ : $1 \cdot (- 1) = - 1$
- $d = 2 (1, 0)$ : $(- 1) \cdot (- 1) = 1$
- $d = 3 (0, 1)$ , $d = 1 (0, 0)$ : 2 の指数の差が $2$ なので $0$

【手順 4】反転公式より
$f (12) = d ∣ 12 \sum μ (d, 12) g (d) = g (12) - g (6) - g (4) + g (2) = 144 - 36 - 16 + 4 = 96.$

答え: $96$

よくある誤り

反転公式で $μ (x, y)$ の代わりに $μ (0^, x)$ など別の引数を使ってしまう誤り。正しくは $f (y) = \sum_{x \leq y} μ (x, y) g (x)$ で、各項の係数は区間 $[x, y]$ のメビウス関数（例: 上の例で $g (6)$ の係数は $μ (6, 12) = - 1$ であり、 $μ (1, 6) = 1$ ではない）
積公式を和と取り違えて $μ_{P} (x, y) + μ_{Q} (x^{'}, y^{'})$ としてしまう誤り。正しくは積 $μ_{P} (x, y) μ_{Q} (x^{'}, y^{'})$ （例: $D_{12}$ で $μ (2, 12) = (- 1) \cdot (- 1) = 1$ であり、 $- 2$ ではない）
鎖で差が 2 以上でも $μ$ が $\pm 1$ になると考えてしまう誤り。漸化式から鎖では $μ (i, i + 2) = - (μ (i, i) + μ (i, i + 1)) = - (1 - 1) = 0$ で、差が 2 以上なら $0$ （例: $D_{12}$ で $μ (1, 12) = μ_{鎖} (0, 2) \cdot μ_{鎖} (0, 1) = 0$ ）
直積に分解するとき、区間の端点を取り違えて因子を作る誤り。 $μ (d, e)$ は区間 $[d, e]$ だけで決まり、約数の順序ではその区間は $[1, e / d]$ と同じ形になるので、 $e$ ではなく $e / d$ の素因数分解で分ける（例: $μ (2, 12)$ は $12/2 = 6 = 2 \cdot 3$ から $(- 1)^{2} = 1$ ）

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
$C_{4} = {0, 1, 2, 3}$ 、 $C_{3} = {0, 1, 2}$ を通常の大小関係による全順序集合（鎖）とし、直積 $P = C_{4} \times C_{3}$ に
$(a, b) \leq (a^{'}, b^{'}) ⟺ a \leq a^{'} かつ b \leq b^{'}$
で半順序を入れる。関数 $f : P \to Z$ が、すべての $(c, d) \in P$ に対して
$(a, b) \leq (c, d) \sum f (a, b) = (c + d + 1)^{3}$
を満たすとき、 $f (3, 2)$ の値を求めよ。

この技能を使う問題

この技能の次に学べること

ブール束・約数束・分割束のメビウス関数（大学院数学代数的組合せ論）
ボンド束と彩色多項式（大学院数学代数的組合せ論）