MacWilliams恒等式で学ぶMöbius反転入門

符号理論における基本定理の一つに，MacWilliams恒等式があります． $E$ を座標集合とする有限体 $\mathbb{F}_{q}$ 上の線形符号 $C \leq \mathbb{F}_{q}^{E}$ に対して，その双対符号

の重み多項式は，$C$ の重み多項式から次のように計算できます：

これがMacWilliams恒等式です．

MacWilliams恒等式には，いくつもの証明があり，この連載ではMacWilliams恒等式の証明を手掛かりに， 周辺分野・周辺概念への入門を試みるものです． そのため，本連載では以下のような読者を対象としています：

符号理論の初歩，具体的には

• （有限）体とは何か

• 有限体上の線形符号とは何か

• Hamming重みとは何か

• 双対符号とは何か

程度は既知であることを前提としています (MacWilliams恒等式の証明は知らなくても問題ありません)．

この連載では，MacWilliams恒等式の証明手法を大きく次の五つの系統に分けて眺めます．

1. Fourier・指標・Poisson系．

2. Möbius反転・束論・短縮穿孔系．

3. 直交多項式・アソシエーションスキーム系．

4. マトロイド・Tutte多項式系．

5. モーメント・二重数え上げ系．

今回の証明は，このうち「Möbius反転・束論・短縮穿孔系」に着目します． つまり，第1回の目標は，MacWilliams恒等式の証明を案内役として， 束論ならびにMöbius反転に入門することです． MacWilliams恒等式を証明する目的に限るなら，束はブール束を押さえておけば十分ですが， 分野への入門の意味で，部分空間束や分割束など，基本的な束も紹介しています． MacWilliams恒等式の証明のみ知りたい方は，ブール束に関する記述以外は読み飛ばして頂いて構いません．

Möbius反転というと，初等整数論に出てくる

のような公式を思い浮かべるかもしれません． あるいは，有限集合に対する包除原理を思い浮かべるかもしれません．

実は，これらはどちらも同じ理論の特殊な例です． このような半順序集合上のMöbius関数の体系的な扱いは， Rota [Rot64] によって組合せ論の中心的道具として整理されました． その共通の舞台は，局所有限半順序集合です． 半順序集合の上で「下にあるものを全部足す」という操作を考えると， その逆操作としてMöbius反転が現れます．

今回の流れは次のようになります．

MacWilliams恒等式の証明だけを考えるなら， 最終的に必要になる半順序集合は，座標集合 $E$ の部分集合全体 $2^{E}$ です． これはブール束と呼ばれる特別な束です．しかし，ブール束だけを最初から扱ってしまうと， Möbius反転という分野そのものの見通しが悪くなります． そこで，まず一般の半順序集合上のMöbius反転を導入し， その後でブール束を一つの重要な例として扱い，最後に符号理論へ応用します．

半順序集合上の接合代数とMöbius反転については， Stanley [Sta12, Chapter 3] が標準的な参考文献です．

Möbius反転の舞台になるのは，順序を持つ集合です． まずは最も基本的な定義から始めます． 半順序集合と束の基本事項については， Davey–Priestley [DP02] が読みやすい標準的な入門書です．

文脈から考える順序が明らかな場合は，単に $P$ を半順序集合と言います． また，利便性のため

• $x \geq y$ $\defarrow$ $y \leq x$,

• $x < y$ $\defarrow$ $x \leq y$ かつ $x \neq y$,

• $x > y$ $\defarrow$ $x \geq y$ かつ $x \neq y$,

• $x \nleq y$ $\defarrow$ $x \leq y$ でない ^{脚注¹$x \nleq y$ は必ずしも $x > y$ を意味しないことに注意してください． $x$ と $y$ が比較可能でない (cf. 後述の定義 2.2) 場合も $x \nleq y$ となります．1}

と定めます．

半順序という言葉の「半」は，すべての二つの元が比較できるとは限らない，という意味です． 整数全体 $\mathbb{Z}$ に通常の大小関係を入れると，任意の二つの整数は比較できます． 一方，部分集合の包含関係を考えると，二つの集合がどちらも他方を含まないことがあります． このような状況も順序として扱うために，半順序集合という言葉を使います．

半順序集合の中でも，特に重要なのが束です． 束では，二つの元に対して「両方より上にある最小の元」と「両方より下にある最大の元」を考えることができ， それぞれ結びと交わりといいます．

ブール束では，二つの部分集合 $S, T \subseteq E$ に対して

です．つまり，結びは和集合，交わりは共通部分です．また，最小元は $\emptyset$，最大元は $E$ です．

約数の半順序集合 $D(N)$ も束です．二つの約数 $d, e \mid N$ に対して，

です．つまり $D(N)$ では，結びは最小公倍数，交わりは最大公約数になります．

ただし，Möbius反転そのものに必要なのは，束であることではありません． 実際には，もう少し広い局所有限半順序集合の上でMöbius反転ができます． 束は，Möbius反転が特に自然に現れる重要なクラスだと考えるのがよいです．

Möbius反転では，半順序集合全体よりも，二つの元の間に挟まれた部分が重要になります．

例えば，$2^{E}$ で $S \subseteq T$ とすると，

です．これは，$T \setminus S$ の部分集合全体と同じ形をしています． 実際，$U$ は $U = S \cup A$ ($A \subseteq T \setminus S$) の形で一意に書けます．

有限な半順序集合はもちろん局所有限です． 有限でないが局所有限である例としては例えば，有理整数環 $\mathbb{Z}$ が挙げられます． 整数は無限に存在するので，$\mathbb{Z}$ 自体は無限集合ですが，2つの整数 $s, t \in \mathbb{Z}$ の間にある整数は

で，$\card{\lbrack s, t \rbrack} = t - s + 1 < \infty$ と有限になるため， $\mathbb{Z}$ は局所有限半順序集合です． 一方で，有理数体 $\mathbb{Q}$ や実数体 $\mathbb{R}$ は $\mathbb{Z}$ と同じ通常の大小関係で半順序集合になりますが， $s < t$ である限り，$\lbrack s, t \rbrack$ は無限集合となってしまうため，局所有限ではありません．

この回でMacWilliams恒等式に使う $2^{E}$ も有限なので，局所有限です． 局所有限性が必要なのは，後で $\displaystyle \sum_{z \in \lbrack x, y \rbrack}$ のような和を考えるためです． この和に現れる $z$ が有限個であれば，収束の問題を気にせずに足し算できます．

Möbius反転の考え方を一言で言うと，「累積和から元の値を取り戻す方法」です．

まず，有限な半順序集合 $P$ を考えます．各元 $x \in P$ に数 $f(x)$ が割り当てられているとします． このとき，$x$ 以下の元の値をすべて足し合わせて

と定めます．この $g$ は，$f$ の累積和です．

例えば，鎖 $0 < 1 < 2 < \dots < m$ では，

です．この場合，元の $f$ は差分によって

と取り戻せます． ただし $i = 0$ では $f(0) = g(0)$ とします．

部分集合の半順序集合 $2^{E}$ では，

です．これは，「$S$ に含まれるすべての部分集合 $T$ について足す」という操作です． この場合に $f$ を取り戻す公式が，包除原理 (Inclusion–Exclusion Principle) です．

このように，Möbius反転は，普通の差分や包除原理を一つにまとめる理論です． この累積和の操作は，半順序集合の文脈ではゼータ変換 (zeta transform) と呼ばれます．

Möbius反転をきれいに書くために，接合代数を導入します． 代数という名前がついていますが，最初は 「半順序集合の各区間に数を割り当てる関数の集まり」 だと思えば十分です．

係数環である可換環 $R$ は，慣れていなければ有理数体 $\mathbb{Q}$ や実数体 $\mathbb{R}$ など，足し算と掛け算ができる数の範囲にあると考えてください． 以下，係数環を明示しないときは有理数体を採用して， $I(P) \coloneqq I(P;\mathbb{Q})$ と書くことにします．

畳み込み積の和に現れる非零項は，$I(P; R)$ 内の関数の制約により $x \leq z \leq y$ を満たす $z \in P$ に限られるため， $P$ が局所有限なら有限和になります．この演算により，$I(P;R)$ は単位的結合 $R$-代数になります．

畳み込み積は，行列の積に似ています． $n \times \ell$ 行列 $A$ と $\ell \times m$ 行列 $B$ の積では，その $(i, j)$ 成分を見ると，

と途中の添字 $k$ について足し上げます． 接合代数では，途中の添字 $z$ が，$\lbrack x, y \rbrack$ の元，すなわち $x \leq z \leq y$ を満たす元に限られているだけです．

畳み込み積は単位元を持ち，次のデルタ関数です．

実際，以下の命題からデルタ関数が単位元であることがわかります．

証明

$x, y \in P$ を任意に取り固定する． まず $x \nleq y$ のとき，$x \leq z \leq y$ を満たす $z$ は存在しないので，

$$(\delta \ast \alpha)(x,y)=0=\alpha(x,y)$$

である．ここで右辺の等号は $\alpha \in I(P)$ から従う．

次に $x \leq y$ とする．このとき畳み込み積の非零項は区間 $\lbrack x, y \rbrack$ に限られるので，

$$(\delta \ast \alpha)(x,y) = \sum_{z \in \lbrack x, y \rbrack} \delta(x,z)\alpha(z,y)$$

である．ここで $\delta(x,z)$ が非零になるのは $z=x$ のときだけであるから，

$$(\delta \ast \alpha)(x,y)=\alpha(x,y)$$

を得る．よって $\delta \ast \alpha = \alpha$ である．

同様に，$x \nleq y$ のときは $(\alpha \ast \delta)(x,y)=0=\alpha(x,y)$ であり， $x \leq y$ のときは

$$(\alpha \ast \delta)(x,y) = \sum_{z \in \lbrack x, y \rbrack} \alpha(x,z)\delta(z,y) = \alpha(x,y)$$

となる．したがって $\alpha \ast \delta = \alpha$ である．

証明終わり□

接合代数の中で，特に重要な関数がゼータ関数です． ここでいうゼータ関数は，リーマン予想で有名なリーマン・ゼータ関数ではなく， 半順序集合に付随する最も単純な接合代数の元です．

ゼータ関数 $\zeta$ を使うと，先ほどの累積和

は

と書けます．なぜなら，$y \leq x$ の下で $\zeta(y, x) = 1$ だからです．

このゼータ関数の逆元がMöbius関数です．

定義だけ見ると少し抽象的ですが，意味は単純です． ゼータ関数が「下にあるものを全部足す」操作を表すなら， Möbius関数はその逆操作を表します． Möbius関数は，次の再帰式で計算できます．

証明

$x \nleq y$ のときは，$\mu \in I(P)$ であるから $\mu(x,y)=0$ である．

条件 $\mu \ast \zeta = \delta$ を展開する． $x \leq y$ を満たす任意の $x, y \in P$ に対して，

$$(\mu \ast \zeta)(x, y) = \sum_{z \in \lbrack x, y \rbrack} \mu(x, z) \zeta(z, y) = \sum_{z \in \lbrack x, y \rbrack} \mu(x, z)$$

が成り立つ．これが $\delta(x, y)$ に等しいため， $x = y$ のときは $\mu(x, x) = 1$ でなければならない． また $x < y$ のときは

$$\sum_{z \in \lbrack x, y \rbrack} \mu(x, z) = 0$$

である．最後の項 $z = y$ を分けると，

$$\left( \sum_{z \in \lbrack x, y \rbrack, \, z \neq y} \mu(x, z) \right) + \mu(x, y) = 0$$

となるため，

$$\mu(x, y) = -\sum_{z \in \lbrack x, y \rbrack, \, z \neq y} \mu(x, z)$$

を得る． 局所有限性により区間 $\lbrack x, y \rbrack$ は有限なので， この式は短い区間から順に $\mu(x, y)$ を決めていく再帰式である．したがって $\mu$ は一意に定まる．

同様に，条件 $\zeta \ast \mu = \delta$ を展開すれば

$$\mu(x, y) = -\sum_{z \in \lbrack x, y \rbrack, \, z \neq x} \mu(z, y) \qquad (x < y)$$

も得られる．上で構成した $\mu$ がこの式も満たすことは，区間の大きさに関する帰納法で確認できる． したがって $\mu$ は $\zeta$ の両側逆元である．

証明終わり□

ここまで準備した言葉を使うと，Möbius反転は非常に短く書けますが， その前に一点注意事項があります． 接合代数とMöbius関数そのものは，局所有限半順序集合上で定義できます． ただし， 以下の定理で扱う一変数のゼータ変換 $\displaystyle g(x) = \sum_{y \leq x} f(y)$ は，この和が有限である場合にだけそのまま定義されます． 半順序集合の局所有限性は区間 $\lbrack x, y \rbrack$ の有限性しか仮定していないので， 総和が走る $\{ y \in P : y \leq x \}$ は必ずしも有限になるとは限りません． 例えば，$\mathbb{Z}$ は局所有限ですが，

は任意の $x \in \mathbb{Z}$ に対して無限集合です．

本稿で符号理論的モチベーションに基づき最終的に使う $2^{E}$ ($E$ は有限集合) は有限集合なので，以下では記述を簡単にするため有限半順序集合に限定して述べることにします．

証明

仮定より，$\displaystyle g(y) = \sum_{\substack{z \in P \\ z \leq y}} f(z)$ である． したがって

$$\begin{aligned} \sum_{y \in P, \, y \leq x} \mu(y, x)g(y) &= \sum_{y \in P, \, y \leq x} \mu(y, x) \sum_{z \in P, \, z \leq y} f(z)\\ &= \sum_{z \in P, \, z \leq x} f(z) \sum_{y \in \lbrack z, x \rbrack} \mu(y, x). \end{aligned}$$

ここで

$$\sum_{y \in \lbrack z, x \rbrack} \mu(y, x) = (\zeta \ast \mu)(z, x) = \delta(z, x)$$

である．よって上の式は

$$\sum_{z \in P, \, z \leq x} f(z) \delta(z, x) = f(x)$$

となる．

証明終わり□

この定理は，普通の差分公式や包除原理を一つの形で含んでいます． 次に，いくつかの例で見てみます．

この例は，Möbius反転が符号理論だけの道具ではなく， 整数論にも自然に現れる普遍的な反転原理であることを示しています． MacWilliams恒等式で最終的に使うのは，定義 3.3有限集合 $E$ に対して，部分集合全体 $2^{E}$ を包含関係で順序づけた束を， $E$ 上のブール束 (Boolean lattice) という．定義 3.3 で導入したブール束です． そのMöbius関数は非常に単純です．

証明

$S = T$ のとき，右辺は $1$ であり，$\mu(S, S) = 1$ と一致する．

$S \subsetneq T$ と仮定し，Möbius関数の再帰式を確かめればよい． 示すべきことは

$$\sum_{U \in \lbrack S, T \rbrack}(-1)^{\card{U} - \card{S}} = 0$$

である．ここで，$U$ は

$$U = S \cup A, \qquad A \subseteq T \setminus S$$

の形で一意に書けるため，左辺は

$$\sum_{A \subseteq T \setminus S} (-1)^{\card{A}} = (1 - 1)^{\card{T\setminus S}} = 0$$

となる．最後の等号では，$S \subsetneq T$ より $\card{T \setminus S} > 0$ であることを用いた．

よって，$(-1)^{\card{T} - \card{S}}$ はMöbius関数の再帰式を満たす． Möbius関数は一意に定まるため，結論が従う．

証明終わり□

したがって，ブール束上のMöbius反転は次の形になります．

これは包除原理そのものです．ただし，ここで重要なのは，包除原理を孤立した公式として覚えるのではなく， 半順序集合上のMöbius反転の一例として見ていることです．

ここから，Möbius反転をMacWilliams恒等式に応用します．

簡単のため，座標集合を $E = \{ 1, 2, \dots, n \}$ とし，$C \leq \mathbb{F}_{q}^{E}$ を線形符号とします． 符号語 $c = (c_{1}, \dots, c_{n})$ の台を非零成分の位置座標集合

と定めます．するとHamming重みは台の要素数

となります．

重み多項式は

でした．これを台ごとに分解するために，次の数を定義します．

この記号を使うと，重み多項式は

と書けます．

しかし，$A_{C}(S)$ は線形代数的には少し扱いにくい数です． なぜなら「台がピッタリ $S$」という条件は，

• $i \in S$ なら $c_{i} \neq 0$,

• $i \notin S$ なら $c_{i} = 0$

という条件を含むからです．非零であることは線形条件ではありません．

一方で，「台が $S$ に含まれる」という条件は線形条件です． そこで，$S \subseteq E$ に対して次の部分符号を考えます．

この二つの数の関係は，まさにブール束上のゼータ変換です．

証明

$B_{C}(S)$ は，台が $S$ に含まれる符号語の数である． そのような符号語の台は，ある部分集合 $T \subseteq S$ として一意に定まる． 台がちょうど $T$ である符号語の数は $A_{C}(T)$ であるから， $T \subseteq S$ について足し合わせれば

$$B_{C}(S) = \sum_{T \subseteq S} A_{C}(T)$$

となる．

証明終わり□

したがって，Möbius反転により次を得ます．

ここで見えている構造は，符号理論固有のものではありません． 半順序集合 $2^{E}$ 上で，

と足し上げた関数を，Möbius反転で元に戻しているだけです．

前節のMöbius反転を重み多項式に代入すると， 便利な形が得られます．これは後の証明で何度も使う計算です．

証明

重み多項式を台がちょうど $S$ である符号語数で書くと，

$$W_{C}(X, Y) = \sum_{S \subseteq E} A_{C}(S) X^{n-\card{S}} Y^{\card{S}}$$

となる．ここに

$$A_{C}(S) = \sum_{T \subseteq S}(-1)^{\card{S}-\card{T}} B_{C}(T)$$

を代入すると，

$$\begin{aligned} W_{C}(X,Y) &= \sum_{S \subseteq E} \sum_{T \subseteq S} (-1)^{\card{S} - \card{T}} B_{C}(T) X^{n - \card{S}} Y^{\card{S}}\\ &= \sum_{T \subseteq E} B_{C}(T) \sum_{S \subseteq E, \, T \subseteq S} (-1)^{\card{S}-\card{T}} X^{n - \card{S}}Y^{\card{S}}. \end{aligned}$$

$S$ は $S = T \cup A$，$A \subseteq E \setminus T$ と一意に書けるので，内側の和は

$$\begin{aligned} \sum_{A \subseteq E \setminus T} (-1)^{\card{A}} X^{n - \card{T} - \card{A}} Y^{\card{T} + \card{A}} &= Y^{\card{T}} \sum_{A \subseteq E \setminus T} X^{n - \card{T} - \card{A}} (-Y)^{\card{A}}\\ &= Y^{\card{T}} (X - Y)^{n - \card{T}} \end{aligned}$$

となる．よって主張が従う．

証明終わり□

この式は，MacWilliams恒等式の証明におけるMöbius反転の働きをよく表しています． $X - Y$ という変数は，ブール束のMöbius関数 $(-1)^{\card{S} - \card{T}}$ から現れています． ちなみに，$qY$ は有限体上の直交補の大きさ $\card{U}\card{U^\perp}=q^{\card{S}}$ から現れています．

ここまでで，Möbius反転によって重み多項式を

を使って書けることが分かりました． 残る課題は，$C^{\perp}$ に対する $B_{C^{\perp}}(S)$ を， $C$ に対する $B_{C}(S)$ で表すことです．

このために，穿孔と短縮の記法を導入します．

ここで，上付きも下付きも「削除する座標集合」を表していることに注意してください． したがって，$S$ の座標を残す穿孔は $C^{E \setminus S}$ であり， $C(S)$ は $S$ への制限により $C_{E \setminus S}$ と自然に同一視できます． つまり，

となります．同様に，$C^{\perp}(S)$ は $(C^{\perp})_{E \setminus S}$ と自然に同一視できます．

証明

左の等号は $B_{C^{\perp}}(S)$ の定義そのものである． したがって，右の等式を示せばよい．

$S \subseteq E$ を固定する． $S$ の座標への制限写像

$$\rho_{S} \colon C \to \mathbb{F}_{q}^{S}, \qquad c \mapsto c|_{S}$$

を考える．このとき，穿孔符号の定義より

$$\Im(\rho_{S}) = C^{E \setminus S}$$

である．また，$\rho_S$ の核は $S$ の各座標がすべて $0$ である符号語全体であるから，

$$\Ker(\rho_{S}) = \{ c \in C : \supp(c) \subseteq E \setminus S \} = C(E \setminus S)$$

である．したがって第一同型定理より

$$\card{C^{E \setminus S}} = \card{\Im(\rho_S)} = \frac{\card{C}}{\card{\Ker(\rho_S)}} = \frac{\card{C}}{\card{C(E \setminus S)}} = \frac{\card{C}}{B_C(E \setminus S)} \tag{11.1}$$

を得る．

次に，$(C^{\perp})(S)$ と $C^{E\setminus S}$ の直交補との関係を調べる． $\mathbb{F}_{q}^{S}$ には通常の内積

$$u \cdot v = \sum_{i \in S} u_i v_i$$

を入れておく． また，$u \in \mathbb{F}_{q}^{S}$ に対して，$u$ を $E$ 上に $0$ で延長したベクトルを $\widetilde{u} \in \mathbb{F}_{q}^{E}$ と書く．すなわち

$$\widetilde{u}_i = \begin{cases} u_i, & i \in S,\\ 0, & i \in E \setminus S \end{cases}$$

と定める．このとき

$$\{ u \in \mathbb{F}_{q}^{S} : \widetilde{u} \in (C^{\perp})(S) \} = \left(C^{E \setminus S}\right)^{\perp} \tag{11.2}$$

が成り立つ．実際，$u \in \mathbb{F}_{q}^{S}$ に対して，

$$\begin{aligned} u \in \left(C^{E \setminus S}\right)^{\perp} &\Longleftrightarrow u \cdot v = 0 \quad \text{for all } v \in C^{E \setminus S} \\ &\Longleftrightarrow u \cdot (c|_S) = 0 \quad \text{for all } c \in C \\ &\Longleftrightarrow \widetilde{u} \cdot c = 0 \quad \text{for all } c \in C \\ &\Longleftrightarrow \widetilde{u} \in C^{\perp}. \end{aligned}$$

さらに $\widetilde{u}$ は $E \setminus S$ の座標がすべて $0$ であるから， $\widetilde{u} \in C^{\perp}$ であることは $\widetilde{u} \in (C^{\perp})(S)$ であることと同値である． よって $$\{ u \in \mathbb{F}_{q}^{S} : \widetilde{u} \in (C^{\perp})(S) \} = \left(C^{E \setminus S}\right)^{\perp} \tag{11.2}$$(11.2) が従う．

零延長写像

$$\mathbb{F}_{q}^{S} \to \mathbb{F}_{q}^{E}, \qquad u \mapsto \widetilde{u}$$

は，$\mathbb{F}_{q}^{S}$ と台が $S$ に含まれる $\mathbb{F}_{q}^{E}$ のベクトル全体との間の線形同型である． したがって $$\{ u \in \mathbb{F}_{q}^{S} : \widetilde{u} \in (C^{\perp})(S) \} = \left(C^{E \setminus S}\right)^{\perp} \tag{11.2}$$(11.2) より

$$\card{(C^{\perp})(S)} = \card{\left(C^{E \setminus S}\right)^{\perp}}$$

である．

有限次元ベクトル空間では，任意の部分空間 $U \leq \mathbb{F}_{q}^{S}$ に対して

$$\card{U}\,\card{U^{\perp}} = q^{\card{S}}$$

が成り立つ．これは $\dim U + \dim U^{\perp} = \card{S}$ および $\card{U}=q^{\dim U}$ から従う． これを $U = C^{E \setminus S}$ に適用すると，

$$\card{(C^{\perp})(S)} = \card{\left(C^{E \setminus S}\right)^{\perp}} = \frac{q^{\card{S}}}{\card{C^{E \setminus S}}}$$

となる．ここに $$\card{C^{E \setminus S}} = \card{\Im(\rho_S)} = \frac{\card{C}}{\card{\Ker(\rho_S)}} = \frac{\card{C}}{\card{C(E \setminus S)}} = \frac{\card{C}}{B_C(E \setminus S)} \tag{11.1}$$(11.1) を代入して

$$\card{(C^{\perp})(S)} = \frac{q^{\card{S}}}{\card{C}} B_C(E \setminus S)$$

を得る．よって主張が従う．

証明終わり□

この定理は，今回の証明における線形代数的な核心です． Möbius反転が「台が含まれる」と「台がちょうど」を行き来させ， 上の定理が $C$ と $C^{\perp}$ を結びつけます． 符号理論の言葉では，ここで使ったのは $C^{E \setminus S}$ と $C(S) \cong C_{E \setminus S}$ の関係です．したがって，次節での証明における計算は，穿孔と短縮の関係を線形代数的に使っていることになります．

いよいよMacWilliams恒等式を証明します． ここまでの準備を組み合わせるだけです． 穿孔・短縮や台に基づく組合せ論的な証明の流れは， Brualdi–Pless–Beissinger [BPB88] と Goldwasser [Gol97] に近いものです．

まず，定理 定理 10.1$C \leq \mathbb{F}_{q}^{E}$ を線形符号とする．このとき $$W_{C}(X,Y) = \sum_{T \subseteq E} B_{C}(T) Y^{\card{T}}(X - Y)^{n - \card{T}}$$ が成り立つ．定理 10.1 を $C^{\perp}$ に適用すると，

です．定理 定理 11.2任意の $S \subseteq E$ に対して $$B_{C^{\perp}}(S) = \card{(C^{\perp})(S)} = \frac{q^{\card{S}}}{\card{C}} B_{C}(E \setminus S)$$ が成り立つ．定理 11.2 より，

なので，

ここで $J = E \setminus S$ とおくと， $\card{S} = n - \card{J}$ なので，

次に，

を代入します．すると式 $$\begin{aligned} W_{C^{\perp}}(X, Y) &= \frac{1}{\card{C}} \sum_{J \subseteq E} (qY)^{n-\card{J}} B_{C}(J) (X - Y)^{\card{J}}. \tag{12.1} \end{aligned}$$(12.1) の右辺は

ここで，$J = U \cup A$，$A \subseteq E \setminus U$ と書くと，内側の和は

したがって

これでMacWilliams恒等式が証明されました．

証明の中でMöbius反転が担っていた役割を整理しておきます．

符号理論的には，次の二つの数がありました．

1. $A_{C}(S)$：台がピッタリ $S$ である符号語の数,

2. $B_{C}(S)$：台が $S$ に含まれる符号語の数.

この二つは

で結ばれていました．これはブール束上のゼータ変換です．したがって，逆向きには

となります．これがブール束上のMöbius反転です．

ここで大切なのは，$A_{C}(S)$ よりも $B_{C}(S)$ の方が線形代数と相性がよいことです． 「台がピッタリ $S$」は非零条件を含むため線形部分空間ではありません． 一方，「台が $S$ に含まれる」符号語全体は

という部分符号になります． したがって，今回の証明では，数えたい量 $A_{C}(S)$ をいったん 線形代数で扱いやすい量 $B_{C}(S)=\card{C(S)}$ に移し， 最後にMöbius反転で元に戻していました． この視点は，Möbius反転を使う多くの場面で共通しています．

この回では，MacWilliams恒等式の証明を目標にしながら， Möbius反転の基本的な道具を導入しました． 整理すると次のようになります．

半順序集合

反射律，反対称律，推移律を満たす順序を持つ集合です． すべての元が比較できるとは限りません．

束

任意の二つの元に対して，結びと交わりが存在する半順序集合です． 部分集合全体 $2^{E}$ では，結びは和集合，交わりは共通部分です．

区間

半順序集合 $P$ において $x \leq y$ を満たす $x$ と $y$ の間にある元全体

$$\lbrack x, y \rbrack = \{ z \in P : x \leq z \leq y\}$$

です．

局所有限性

すべての区間が有限であるという性質です． Möbius反転では，区間上の有限和を考えるためにこの条件が自然に現れます．

接合代数

$P \times P$ 上の関数で，$x \nleq y$ なら $0$ になるもの全体の代数です． 積は，中間の元をすべて経由する畳み込みで定義されます．

ゼータ関数

$x \leq y$ なら $1$，そうでなければ $0$ を返す接合代数の元です． ゼータ関数は，半順序集合上の累積和を表します．

Möbius関数

接合代数におけるゼータ関数の逆元です． 累積和を元に戻す係数を与えます．

Möbius反転

$$g(x)=\sum_{y \in P, \, y \leq x}f(y)$$

から

$$f(x) = \sum_{y \in P, \, y \leq x}\mu(y,x)g(y)$$

を得る反転公式です．

ブール束

部分集合全体 $2^{E}$ を包含関係で順序づけた束です． そのMöbius関数は

$$\mu(S, T) = (-1)^{\card{T} - \card{S}}$$

です．

MacWilliams恒等式の証明においては，ブール束上のMöbius反転が使われました． しかし，ブール束はMöbius反転の一例にすぎません． 鎖では差分，約数半順序集合では整数論のMöbius反転， ブール束では包除原理が現れます． このように，Möbius反転は「累積された情報から局所的な情報を取り戻す」ための一般原理です．

冒頭で述べたように，今回の証明は

Möbius反転・束論・短縮穿孔系

に属します．表面的には，符号語の台を使った証明です． しかし，深いところでは，ブール束上のゼータ変換とMöbius反転を使っています．

今回の証明の要点は，次の一文にまとめられます．

台が含まれるという累積情報から，台がちょうど等しいという情報を取り戻す．

この「累積情報から局所情報を取り戻す」という考え方が，Möbius反転の核心です．

より一般に，束に値を取る台写像から得られる重みに対しても， MacWilliams型恒等式を研究する枠組みがあります [Rav18]．

次回は，MacWilliams恒等式の最も標準的な証明に近い道具である， 有限アーベル群の指標を扱います．

今回の証明では，$C^{\perp}$ は座標の制限写像と直交補の次元計算から現れました． 次回の指標論的証明では，$C^{\perp}$ は指標の直交関係

から現れます．

同じMacWilliams恒等式であっても， Möbius反転の証明では「台の包含関係」が主役でした． 指標論の証明では，「群の双対性」と「直交関係」が主役になります． この違いを見ることで，MacWilliams恒等式がさまざまな数学の交差点にあることが， 少しずつ見えてくるはずです．

脚注

1. $x \nleq y$ は必ずしも $x > y$ を意味しないことに注意してください． $x$ と $y$ が比較可能でない (cf. 後述の定義 2.2$P$ を半順序集合とする．二元 $x, y \in P$ が比較可能 (comparable) であるとは，$x \leq y$ か $y \leq x$ のいずれかが成り立つことをいう． 半順序集合が鎖 (chain) または全順序 (totally ordered) または線形順序 (linearly ordered) であるとは，任意の二元が比較可能であることをいう．定義 2.2) 場合も $x \nleq y$ となります． ↩
2. 厳密には閉区間と呼んだ方が良いかもしれませんが，単に区間と呼ぶのが標準的なようです． ↩
3. 隣接代数，接合環とも呼ばれます． ↩
4. しばしば，$I(P;R)$ の元を $x \leq y$ を満たす組 $(x, y) \in P \times P$ 上の関数として定義することがあります． その場合，$\alpha(x, y)$ は $x \leq y$ のときだけ書く，という暗黙の了解を徹底する必要があります． というのも，後の議論で総和の式変形に $x \nleq y$ を満たす組などが現れてしまうためです． 本稿では，$x \nleq y$ のときの扱いを明示的に取り扱うために，値を $0$ と明記することで， $P \times P$ 上の関数とみなす流儀を採用することにします． ↩

参考文献

1. [Rot64] Gian-Carlo Rota. On the foundations of combinatorial theory. I. Theory of Möbius functions. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, vol. 2, pp. 340–368, 1964. doi:10.1007/BF00531932 引用箇所実は，これらはどちらも同じ理論の特殊な例です． このような半順序集合上のMöbius関数の体系的な扱いは， Rota [Rot64] によって組合せ論の中心的道具として整理されました． その共通の舞台は，局所有限半順序集合です． 半順序集合の上で「下にあるものを全部足す」という操作を考えると， その逆操作としてMöbius反転が現れます．↩
2. [Sta12] Richard P. Stanley. Enumerative combinatorics. Volume 1. Cambridge University Press, Cambridge, vol. 49, pp. xiv+626, 2012 引用箇所半順序集合上の接合代数とMöbius反転については， Stanley [Sta12, Chapter 3] が標準的な参考文献です．↩
3. [DP02] B. A. Davey and H. A. Priestley. Introduction to lattices and order. Cambridge University Press, New York, pp. xii+298, 2002. doi:10.1017/CBO9780511809088 引用箇所Möbius反転の舞台になるのは，順序を持つ集合です． まずは最も基本的な定義から始めます． 半順序集合と束の基本事項については， Davey–Priestley [DP02] が読みやすい標準的な入門書です．↩
4. [BPB88] Richard A. Brualdi, Vera S. Pless, and Janet S. Beissinger. On the MacWilliams identities for linear codes. Linear Algebra Appl., vol. 107, pp. 181–189, 1988. doi:10.1016/0024-3795(88)90244-3 引用箇所いよいよMacWilliams恒等式を証明します． ここまでの準備を組み合わせるだけです． 穿孔・短縮や台に基づく組合せ論的な証明の流れは， Brualdi–Pless–Beissinger [BPB88] と Goldwasser [Gol97] に近いものです．↩
5. [Gol97] John L. Goldwasser. Shortened and punctured codes and the MacWilliams identities. Linear Algebra Appl., vol. 253, pp. 1–13, 1997. doi:10.1016/0024-3795(95)00671-0 引用箇所いよいよMacWilliams恒等式を証明します． ここまでの準備を組み合わせるだけです． 穿孔・短縮や台に基づく組合せ論的な証明の流れは， Brualdi–Pless–Beissinger [BPB88] と Goldwasser [Gol97] に近いものです．↩
6. [Rav18] Alberto Ravagnani. Duality of codes supported on regular lattices, with an application to enumerative combinatorics. Des. Codes Cryptogr., vol. 86, no. 9, pp. 2035–2063, 2018. doi:10.1007/s10623-017-0436-3 引用箇所より一般に，束に値を取る台写像から得られる重みに対しても， MacWilliams型恒等式を研究する枠組みがあります [Rav18]．↩