MacWilliams恒等式で学ぶPlessモーメント入門

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

を考えます．ここで

です． 本稿では，符号語 $c \in \F_q^E$ に対して

と書きます． 線形符号 $C$ の重み多項式 (weight enumerator) を

で定めます． MacWilliams恒等式は，双対符号の重み多項式が，$C$ の重み多項式から次のように計算できるという公式です：

これがMacWilliams恒等式です．

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

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

• （有限）体とは何か

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

• Hamming重みとは何か

• 双対符号とは何か

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

本稿は，第1回〜第5回を前提にしません． 途中でKrawtchouk多項式やアソシエーションスキームの影が見える箇所はありますが， 本稿ではそれらの理論は使いません． 必要な道具は，重み分布，モーメント，二項係数，二重数え上げ，有限次元線形代数だけです．

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

1. Fourier・指標・Poisson系．

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

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

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

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

本稿では，このうち「モーメント・二重数え上げ系」に着目します． 今回の目標は，MacWilliams恒等式の証明を案内役として， Plessモーメント，特に重み分布のモーメントと二重数え上げに入門することです．

重み分布を

と書くと，重み多項式は

です． 別の立場では，Krawtchouk多項式やHammingスキームを使って， MacWilliams恒等式を重み分布そのものに対する変換として見ることができます． ここでいうHammingスキームとは，おおまかには二つの語をHamming距離ごとに分類して得られる組合せ構造のことです． しかし本稿では，その理論的な定義や一般論は使いません． ここでは，重み分布を直接変換する代わりに，まず

のようなモーメントを見ます．

確率論では，分布を理解するために平均，分散，高次モーメントを調べます． ここでも同じことをします． ただし，本稿で扱うモーメントは，確率分布として正規化した期待値ではありません． 符号語全体にわたる総和としてのモーメントを使います． 確率論的な平均や期待値として見たい場合は，これらの量を $\card{C}$ で割ればよいです． ただし，符号理論では，普通の冪 $w^{h}$ よりも，二項係数 $\binom{w}{r}$ を使ったモーメントの方が自然です． なぜなら $\binom{\wt(c)}{r}$ は，符号語 $c$ の非零座標の中から $r$ 個の座標を選ぶ方法の数だからです． したがって

は，符号語と座標集合の組を数える量になります． この量を二通りに数えることで，Plessのモーメント恒等式が現れます．

本稿の流れは次のようになります．

Plessの古典的な論文 [Ple63] では，MacWilliams恒等式から冪モーメント恒等式が導かれ， それらの応用も与えられています． 本稿では，MacWilliams恒等式を既知とせず，二項モーメントを直接二重数え上げで計算し， 十分多くのモーメントからMacWilliams恒等式を復元する，という方向で説明します． 双対符号の重み分布とMacWilliams方程式の古典的な扱いについては MacWilliams–Sloane [MS77, Chapter 5] を参照してください． また，MacWilliams方程式とPlessモーメントを含む同値な定式化については Huffman–Pless [HP03, Sections 7.1–7.2] が標準的です． Plessモーメントの教科書的な扱いについては， Pless [Ple98, Chapter 8] も参照してください．

まず，重み分布を数列として見ます． $C \leq \F_{q}^{E}$ を線形符号とし，

と書きます．この数列 $(A_{0}, A_{1}, \dots, A_{n})$ が $C$ の重み分布 (weight distribution) です．

重み分布を一変数多項式としてまとめるために

とおきます． この $P_{C}(t)$ は，重み多項式 $W_{C}(X,Y)$ を非斉次化したものです． 実際，

と読めます． ここでの $Y/X$ は形式的な読み替えであり，最終的には両辺を多項式として比較します．

$h = 0$ のときは，慣習として $0^{0} = 1$ と読み，

です． $h = 1$ のときは，符号語の重みの総和

です． $h=2$ は，重みの二乗和です．

しかし，符号理論では冪モーメントよりも，次の二項モーメントの方が扱いやすいです．

ここで $\binom{w}{r}=0$ ($w < r$) と約束します． 二項モーメントの意味は非常に具体的です． 符号語 $c \in C$ を固定すると，$\binom{\wt(c)}{r}$ は $\supp(c)$ の中から $r$ 個の座標を選ぶ方法の数です． したがって $r$ 次の二項モーメント $M_{r}(C)$ は，次のような組を数えています：

この「組を数える」という見方が，Plessモーメント恒等式の入口になります．

二項モーメントは，多項式 $P_{C}(t)$ を $t = 1$ のまわりで展開した係数として現れます．

証明

二項定理により

$$(1 + z)^{w} = \sum_{r = 0}^{w} \binom{w}{r} z^{r}$$

である．したがって

$$\begin{aligned} P_{C}(1 + z) &= \sum_{w = 0}^{n} A_{w}(C)(1 + z)^{w} \\ &= \sum_{w = 0}^{n} A_{w}(C) \sum_{r = 0}^{w} \binom{w}{r} z^{r} \\ &= \sum_{r = 0}^{n} \left( \sum_{w = 0}^{n} A_{w}(C) \binom{w}{r} \right)z^r \\ &= \sum_{r = 0}^{n} M_{r}(C) z^{r}. \end{aligned}$$

証明終わり□

この定理から，二項モーメントは分布を完全に決めることが分かります．

証明

$P(t) = \sum_{w=0}^{n} a_{w} t^{w}$ とおく． 仮定は

$$P(1 + z) = \sum_{r = 0}^{n} m_{r} z^{r}$$

が成り立つことである． ここで $z = t - 1$ と置き換えると

$$P(t) = \sum_{r = 0}^{n} m_{r}(t - 1)^{r}$$

を得る．右辺の $t^{w}$ の係数を取ると

$$a_{w} = \sum_{r=w}^{n} m_{r} \binom{r}{w}(-1)^{r-w}$$

を得る．

証明終わり□

この定理は，今回の証明で重要です． MacWilliams恒等式は，重み分布全体を結ぶ公式です． しかし，重み分布全体を直接扱わなくても， すべての二項モーメントを求めれば重み分布は復元できます． したがって，双対符号の重み分布を求めるには，双対符号の二項モーメントをすべて求めれば十分です．

ここから二項モーメントを数えます． $C$ を $\F_{q}$ 上の $[n,k]$ 線形符号，つまり $\dim_{\F_{q}} C = k$ とします． したがって $\card{C} = q^{k}$ です． 双対符号の重み $j$ の符号語数は，通常通り $A_{j}(C^{\perp})$ と書きます．

二項モーメント $\displaystyle M_{r}(C) = \sum_{w = 0}^{n} A_{w}(C) \binom{w}{r}$ は，組

の個数を数えるものでした．これを，まず $S$ を固定して数えます．

この記号を使うと

です． 固定した $S$ に対して，$N_{C}(S)$ は「$S$ の座標がすべて非零である符号語」の数です． ここで $S$ の外の座標には条件を課していないことに注意します． つまり $N_{C}(S)$ は，台がちょうど $S$ である符号語数ではなく， 少なくとも $S$ 上では非零である符号語数です． この「非零」という条件は線形条件ではないので， まず「どの座標が $0$ であるか」という線形条件に直して数えます．

$T \subseteq S$ に対して，$T$ の座標がすべて $0$ である符号語全体を考えます． これは線形部分空間です．$T$ の座標への制限写像

を考えると，その核は

です． $Z_{e} = \{ c \in C : c_{e} = 0\}$ とおくと， $N_{C}(S)$ は $S$ 内のどの $Z_{e}$ にも属さない符号語の数です． したがって包除原理により

次に，$\card{\Ker(\rho_{T})}$ を双対符号の情報で書きます． ここで，双対符号のうち台が $T$ に含まれるものを

と書きます． これは $C^{\perp}$ を $T$ に短縮した符号そのものではなく， $E$ 上の符号語のうち台が $T$ に含まれるものを集めた部分空間です．

証明

制限写像 $\rho_{T} \colon C \to \F_{q}^{T}$ の像を $\rho_{T}(C)$ と書く． 第一同型定理より

$$\card{\Ker(\rho_{T})} = \frac{\card{C}}{\card{\rho_{T}(C)}} = \frac{q^{k}}{\card{\rho_{T}(C)}}.$$

一方，$\F_{q}^{T}$ の標準内積に関して，$C^{\perp}(T)$ は $\rho_{T}(C)$ の直交補と同一視できます． 実際，$u \in \F_{q}^{T}$ を $E$ 上に零で延長したものを $\widetilde{u}$ とすると，

$$\begin{aligned} u \in \rho_{T}(C)^{\perp} &\Longleftrightarrow u \cdot c|_{T} = 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}$ は $T$ の外で $0$ なので，これは $\widetilde{u} \in C^{\perp}(T)$ と同値である． 一般に，有限次元空間 $\F_{q}^{T}$ の部分空間 $D$ について $\dim D + \dim D^{\perp} = \card{T}$ である． したがって $\card{D}\card{D^{\perp}} = q^{\card{T}}$ が成り立つ． これを $D = \rho_{T}(C)$ に適用すると

$$\card{\rho_{T}(C)}\card{C^{\perp}(T)} = q^{\card{T}}$$

が成り立つ．これを上の式に代入すると

$$\card{\Ker(\rho_{T})} = q^{k} \frac{\card{C^{\perp}(T)}}{q^{\card{T}}} = q^{k-\card{T}}\card{C^{\perp}(T)}$$

を得る．

証明終わり□

この補題が，二重数え上げの線形代数的な核心です． $C$ の座標制限写像の核の大きさが，双対符号 $C^{\perp}$ のうち台が $T$ に含まれる符号語数で表されます． なお，右辺には $q^{k-\card{T}}$ が現れるので，$\card{T} > k$ のとき一見分数のように見えます． しかしこれは $\card{\Ker(\rho_{T})}=\card{C}/\card{\rho_{T}(C)}$ を直交補の大きさで書き換えたもので，最終的には必ず整数です． 同値に，その場合は $\card{C^{\perp}(T)}$ が不足分の $q$ の冪を含んでいます．

前節の準備から，二項モーメントの公式を得ます． これがPlessモーメント恒等式の二項モーメント版です．

証明

証明に入る前に，三つの集合の役割を整理しておく． $S$ は，符号語 $c$ が非零であることを要求する $r$ 個の座標集合である． $T$ は，包除原理の中で「ここは $0$ である」と指定する座標集合である． $U$ は，双対符号語 $u \in C^{\perp}$ の台である． 条件 $U \subseteq T \subseteq S$ は，台が $U$ である双対符号語が $C^{\perp}(T)$ に数えられ，その $T$ が包除原理で使われる，という意味である．

左辺を $M_{r}(C)$ と書く． $$M_{r}(C) = \sum_{\substack{S \subseteq E \\\card{S} = r}} N_{C}(S) \tag{4.1}$$(4.1) と $$N_{C}(S) = \sum_{T \subseteq S}(-1)^{\card{T}}\card{\Ker(\rho_{T})}. \tag{4.2}$$(4.2) より

$$\begin{aligned} M_{r}(C) &= \sum_{\substack{S \subseteq E\\\card{S} = r}} \sum_{T \subseteq S}(-1)^{\card{T}}\card{\Ker(\rho_{T})}. \end{aligned}$$

ここに 補題 4.2任意の $T \subseteq E$ に対して $$\card{\Ker(\rho_{T})} = q^{k - \card{T}} \card{C^{\perp}(T)}$$ が成り立つ．補題 4.2 を代入すると

$$M_{r}(C) = \sum_{\substack{S \subseteq E\\\card{S} = r}} \sum_{T \subseteq S} (-1)^{\card{T}}q^{k-\card{T}}\card{C^{\perp}(T)}.$$

ここで，$C^{\perp}$ の符号語を台ごとに分ける． $U \subseteq E$ に対して

$$A_{C^{\perp}}(U) \coloneqq \card{\{ u \in C^{\perp}:\supp(u) = U \}}$$

とおく． これは重みだけを固定した個数 $A_j(C^{\perp})$ ではなく，台 $U$ そのものを固定した個数を表す補助記号である． このとき

$$\card{C^{\perp}(T)} = \sum_{U \subseteq T}A_{C^{\perp}}(U)$$

である．したがって

$$\begin{aligned} M_{r}(C) &= \sum_{U \subseteq E}A_{C^{\perp}}(U) \sum_{\substack{S \subseteq E,\ \card{S} = r}} \sum_{\substack{T: U \subseteq T \subseteq S}} (-1)^{\card{T}}q^{k-\card{T}} \end{aligned}$$

となる．

固定した $U$ について，$\card{U} = j$ とする． ここからは，$U \subseteq T \subseteq S$ を満たす $S,T$ の寄与を数える． $j > r$ なら，$U \subseteq S$ かつ $\card{S} = r$ を満たす $S$ は存在しないので寄与は $0$ となる． 以下 $j \leq r$ とする． $S$ が $U\subseteq S$, $\card{S}=r$ を満たすとき， $T$ は $U \subseteq T \subseteq S$ を動く． $T = U \cup L$，$L \subseteq S \setminus U$ と書くと，内側の和は

$$\begin{aligned} \sum_{L \subseteq S \setminus U} (-1)^{j + \card{L}} q^{k - j - \card{L}} &= (-1)^{j} q^{k - j} \sum_{L \subseteq S \setminus U}(-q^{-1})^{\card{L}} \\ &= (-1)^{j} q^{k-j} \left( 1 - \frac{1}{q} \right)^{r-j} \\ &= (-1)^{j} q^{k - r}(q - 1)^{r - j}. \end{aligned}$$

また，$U$ を含む $r$ 元部分集合 $S$ の個数は $\binom{n-j}{r-j}$ である． したがって，台が $U$ である双対符号語の全寄与は

$$A_{C^{\perp}}(U) (-1)^{j} q^{k-r}(q-1)^{r-j}\binom{n-j}{r-j}$$

となる．

最後に，$\card{U} = j$ である $U$ 全体について足し合わせると

$$\sum_{\substack{U \subseteq E \\ \card{U} = j}}A_{C^{\perp}}(U) = A_{j}(C^{\perp})$$

となる．よって

$$M_{r}(C) = q^{k-r} \sum_{j = 0}^{r} (-1)^{j}(q - 1)^{r - j} \binom{n - j}{r - j}A_{j}(C^{\perp})$$

を得る．

証明終わり□

この公式は，かなり意味のある形をしています． 左辺は $C$ の $r$ 次二項モーメントです． 右辺には，双対符号 $C^{\perp}$ の重み $0, 1, \dots, r$ までの個数だけが現れています． つまり，$C$ の低次モーメントは，双対符号の低重み部分に支配されます．

例えば $r = 0$ の場合，公式は

となります．これは単に $\card{C} = q^{k}$ です． $r = 1$ の場合は

です．もし $C^{\perp}$ に重み $1$ の符号語がなければ，

となります． 重み $1$ の双対符号語がないことは，各座標への写像 $c \mapsto c_{e}$ が零写像ではないことを意味します． 非零な線形写像 $C \to \F_{q}$ は全射なので，各座標では $0$ が $q^{k - 1}$ 回，非零値が合計 $(q - 1)q^{k - 1}$ 回現れます． これを全座標で合計すると，上の $q^{k - 1}(q - 1)n$ が得られます． これは，平均的には各座標が $q - 1$ 対 $1$ の比で非零になる，という感覚と一致します．

$r = 2$ の場合は

です． ここでは，双対符号の重み $1$ と重み $2$ の符号語が，二次モーメントの補正項として現れます．

Plessの恒等式は，しばしば二項モーメントではなく，冪モーメント $\sum_{w = 0}^{n} A_{w}(C) w^{h}$ の形で書かれます． 二項モーメントから冪モーメントへ移るには，Stirling数を使います．

ここで

なので，

です．

証明

$$x^{h} = \sum_{r=0}^{h} r! \Stirling{h}{r} \binom{x}{r} \tag{6.1}$$(6.1) に $x = w$ を代入し，重み分布で重み付き和を取る． すると

$$\begin{aligned} \sum_{w = 0}^{n} A_{w}(C) w^{h} &= \sum_{w=0}^{n} A_{w}(C) \sum_{r=0}^{h} r!\Stirling{h}{r}\binom{w}{r} \\ &= \sum_{r=0}^{\min(h,n)} r! \Stirling{h}{r} \sum_{w=0}^{n} A_{w}(C)\binom{w}{r}. \end{aligned}$$

ここに 定理 5.1（Plessの二項モーメント恒等式）$C \leq \F_{q}^{E}$ を $[n, k]$ 線形符号とする． このとき，$0 \leq r \leq n$ に対して $$\sum_{w=0}^{n} A_{w}(C)\binom{w}{r} = q^{k - r} \sum_{j = 0}^{r} (-1)^{j}(q - 1)^{r-j} \binom{n - j}{r - j} A_{j}(C^{\perp}) \tag{5.1}$$ が成り立つ．定理 5.1 を代入すればよい．

証明終わり□

この形が，Pless [Ple63] に由来する古典的な冪モーメント恒等式です． 見た目は少し複雑ですが，構造は単純です． まず，冪 $w^{h}$ を二項係数 $\binom{w}{r}$ の線形結合に展開します． 次に，二項モーメントを二重数え上げで計算します．

特に重要なのは，右辺に双対符号の低重み分布だけが現れることです． $h \leq n$ の範囲では，$C^{\perp}$ の重み $0, 1, \dots, h$ の符号語数だけを知ればよい． 一般には，必要なのは重み $0, 1, \dots, \min(h,n)$ までである． この性質は，具体的な符号の重み分布を決めるときに非常に有用です．

ここまでで，Plessの二項モーメント恒等式を示しました． 次に，この恒等式からMacWilliams恒等式を復元します． ポイントは，二項モーメントを母関数にまとめることです．

$C$ が $[n,k]$ 符号なら，$C^{\perp}$ は $[n,n-k]$ 符号です． $C^{\perp}$ に対して 定理 5.1（Plessの二項モーメント恒等式）$C \leq \F_{q}^{E}$ を $[n, k]$ 線形符号とする． このとき，$0 \leq r \leq n$ に対して $$\sum_{w=0}^{n} A_{w}(C)\binom{w}{r} = q^{k - r} \sum_{j = 0}^{r} (-1)^{j}(q - 1)^{r-j} \binom{n - j}{r - j} A_{j}(C^{\perp}) \tag{5.1}$$ が成り立つ．定理 5.1 を適用します． $(C^{\perp})^{\perp} = C$ なので，$A_{w} = A_{w}(C)$ と書けば，$C^{\perp}$ の二項モーメントは

です．

一方，定理 3.1$P_{C}(t) = \sum_{w = 0}^{n} A_{w}(C) t^{w}$ とする． このとき $$P_{C}(1 + z) = \sum_{r = 0}^{n} M_{r}(C) z^{r}$$ が成り立つ．定理 3.1 より

です． $$M_{r}(C^{\perp}) = q^{n - k - r} \sum_{w = 0}^{r} (-1)^{w}(q - 1)^{r - w} \binom{n - w}{r - w} A_{w} \tag{7.1}$$(7.1) を代入すると

ここで $r = w + s$ とおくと，内側の和は

したがって

ここで $t \coloneqq 1 + z$ と置きます． すると

なので，$$P_{C^{\perp}}(1 + z) = \frac{1}{\card{C}} \sum_{w = 0}^{n} A_{w}(-z)^{w} \bigl( q + (q - 1)z \bigr)^{n - w}. \tag{7.2}$$(7.2) は

となります．

最後に，この一変数の等式を斉次化します． $P_{C^{\perp}}(t) = W_{C^{\perp}}(1, t)$ なので，形式的に $t = Y/X$ と置いて両辺に $X^{n}$ を掛けると，

これは多項式恒等式としての計算です． したがってMacWilliams恒等式が得られました．

この証明では，Krawtchouk多項式を名前としては使いませんでした． しかし，二項モーメントを母関数にまとめる過程で， 実質的には同じ変換係数が姿を変えて現れています． 違いは，今回の見方では重み分布をいきなり変換するのではなく， まずすべてのモーメントを計算し，そこから分布を復元しているという点です．

小さな例で，モーメントから双対符号の重み分布を復元してみます． $\F_{2}^{3}$ 上の反復符号

を考えます． この符号は $[3,1]$ 符号であり，重み分布は

です． 双対符号 $C^{\perp}$ は偶数重みの語全体

なので，答えは

になるはずです． ここでは，これをPlessモーメントから復元します．

$C^{\perp}$ は $[3,2]$ 符号です． Plessの二項モーメント恒等式を $C^{\perp}$ に適用すると， $(C^{\perp})^{\perp} = C$ なので

です． ここでは $q = 2$ なので $(q - 1)^{r - w} = 1$ です．

順に計算します． $r = 0$ では

$r = 1$ では

$r = 2$ では

$r = 3$ では

したがって

ここで $z = t - 1$ と置くと

よって

であり，重み分布は

と復元されます．

この例では，双対符号の元を直接列挙して答えを確認しました． しかし，Plessモーメントの見方では，まず $M_{0}(C^{\perp})$, $M_{1}(C^{\perp})$, $M_{2}(C^{\perp})$, $M_{3}(C^{\perp})$ を求め，そこから $P_{C^{\perp}}(t)$ を復元し，最後に重み分布を読み取っています． 分布を直接当てにいくのではなく，モーメントを経由して分布を決める，という流れです．

証明の中でPlessモーメントが担っていた役割を整理しておきます．

第一に，重み分布をモーメントで見る視点を導入しました． 重み分布 $(A_{0}, A_{1}, \dots, A_{n})$ を直接扱う代わりに，

を見ました． これは，正規化すれば平均値や高次平均値に対応する総和型の量，および二項モーメントによって分布を調べるという考え方です．

第二に，二項モーメントは自然な数え上げになっていました． $\displaystyle \sum_{w=0}^{n} A_{w}(C) \binom{w}{r}$ は，符号語 $c \in C$ と，その非零座標に含まれる $r$ 元部分集合 $S$ の組を数えています． このため，二項モーメントは二重数え上げに向いています．

第三に，二重数え上げの途中で双対符号の低重み分布が現れました． $S$ の座標がすべて非零である符号語を数えるために包除原理を使い， 座標制限写像の核を双対符号の台が小さい部分で表しました． その結果，$r$ 次二項モーメントには $C^{\perp}$ の重み $0, 1, \dots, r$ の符号語数だけが現れました．

第四に，すべての二項モーメントを集めると重み分布全体が復元できました． 母関数

を使うと，モーメント列は重み分布多項式を $t = 1$ のまわりで展開した係数です． したがって，十分多くのモーメントを知れば，分布そのものが分かります．

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

MacWilliams恒等式は，重み分布を直接変換する公式であると同時に， 双対符号の低重み分布が元の符号のモーメントを支配するというPlessモーメント恒等式の母関数版でもある．

この回では，MacWilliams恒等式の証明を目標にしながら， Plessモーメントの基本的な道具を導入しました． 整理すると次のようになります．

重み分布

符号 $C$ に対して

$$A_{w}(C) = \card{\{ c \in C : \wt(c) = w \}}$$

で定まる数列です． 重み多項式は，この数列を二変数多項式としてまとめたものです．

冪モーメント

$$\sum_{w = 0}^{n} A_{w}(C) w^{h}$$

の形の量です． 重み分布を重みの $h$ 乗で測ったものです．

二項モーメント

$$M_{r}(C) = \sum_{w = 0}^{n} A_{w}(C) \binom{w}{r}$$

で定まる量です． これは，符号語とその非零座標内の $r$ 元部分集合の組を数えています．

モーメント母関数

非斉次重み多項式 $P_{C}(t) = W_{C}(1, t)$ に対して

$$P_{C}(1 + z) = \sum_{r = 0}^{n} M_{r}(C) z^{r}$$

が成り立ちます． 二項モーメントは，$P_{C}(t)$ の $t = 1$ のまわりの展開係数です．

二重数え上げ

$M_{r}(C)$ を，符号語から数える方法と，座標集合を固定して数える方法の二通りで見ました． 後者では包除原理と座標制限写像が現れます．

Plessの二項モーメント恒等式

$C$ が $[n,k]$ 符号のとき

$$\sum_{w=0}^{n} A_{w}(C)\binom{w}{r} = q^{k-r} \sum_{j=0}^{r} (-1)^{j} (q - 1)^{r - j} \binom{n - j}{r - j} A_{j}(C^{\perp})$$

です． $r$ 次二項モーメントは，双対符号の重み $0$ から $r$ までの分布だけで決まります．

Plessのpower moment identities

冪 $w^{h}$ を二項係数 $\binom{w}{r}$ の線形結合に展開することで， 二項モーメント恒等式から冪モーメントの公式が得られます． その変換係数として第二種Stirling数が現れます．

Plessモーメントの見方では，MacWilliams恒等式は単に「重み多項式を変数変換する公式」ではありません． それは，符号の重み分布の各モーメントが，双対符号の低重み符号語によって制御されるという， 数え上げ的な構造をまとめたものでもあります．

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

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

に属します． 表面的には，重み分布のモーメントを計算する証明です． しかし，深いところでは，分布そのものを直接変換するのではなく， その分布が定める数え上げ量を二通りに数え， 十分な個数のモーメントから分布を復元しています．

今回の証明の要点は，次の一文です．

重み分布をモーメント列として見直し，そのモーメントを二重数え上げで双対符号の低重み分布に結びつける．

Fourier・指標系では，双対符号は指標の直交関係から現れます． アソシエーションスキームの言葉を使う証明では， Hamming距離ごとに分類された関係を行列として扱い， それらの行列の同時固有分解から重み分布の変換を読み取る，という見方をします． 本稿ではその行列代数を使わず，同じ変換をモーメントの数え上げから取り出しました． 今回のモーメント系では，双対符号は座標制限写像の核を数える過程で現れます． 同じMacWilliams恒等式でも，見ている量が違うため，かなり違った姿になります．

次回は，MacWilliams恒等式をマトロイドとTutte多項式の側から見ます．

今回の証明では，重み分布のモーメントを二重数え上げによって調べました． 次回は，線形符号の生成行列の列が定める組合せ構造，すなわちマトロイドを考えます． 符号の重み多項式は，対応するマトロイドのTutte多項式の特殊化として表されます． そして，双対符号は双対マトロイドに対応し，Tutte多項式の双対性からMacWilliams恒等式が出てきます．

つまり次回の主役は，

です． 同じMacWilliams恒等式が，今度はマトロイド不変量の双対性として現れます．

参考文献

1. [Ple63] Vera Pless. Power moment identities on weight distributions in error correcting codes. Information and Control, vol. 6, no. 2, pp. 147–152, 1963. doi:10.1016/S0019-9958(63)90189-X 引用箇所Plessの古典的な論文 [Ple63] では，MacWilliams恒等式から冪モーメント恒等式が導かれ， それらの応用も与えられています． 本稿では，MacWilliams恒等式を既知とせず，二項モーメントを直接二重数え上げで計算し， 十分多くのモーメントからMacWilliams恒等式を復元する，という方向で説明します． 双対符号の重み分布とMacWilliams方程式の古典的な扱いについては MacWilliams–Sloane [MS77, Chapter 5] を参照してください． また，MacWilliams方程式とPlessモーメントを含む同値な定式化については Huffman–Pless [HP03, Sections 7.1–7.2] が標準的です． Plessモーメントの教科書的な扱いについては， Pless [Ple98, Chapter 8] も参照してください．↩1 引用箇所この形が，Pless [Ple63] に由来する古典的な冪モーメント恒等式です． 見た目は少し複雑ですが，構造は単純です． まず，冪 $w^{h}$ を二項係数 $\binom{w}{r}$ の線形結合に展開します． 次に，二項モーメントを二重数え上げで計算します．↩2
2. [MS77] F. J. MacWilliams and N. J. A. Sloane. The theory of error-correcting codes. I. North-Holland Publishing Co., Amsterdam-New York-Oxford, vol. Vol. 16, pp. i–xv and 1–369, 1977 引用箇所Plessの古典的な論文 [Ple63] では，MacWilliams恒等式から冪モーメント恒等式が導かれ， それらの応用も与えられています． 本稿では，MacWilliams恒等式を既知とせず，二項モーメントを直接二重数え上げで計算し， 十分多くのモーメントからMacWilliams恒等式を復元する，という方向で説明します． 双対符号の重み分布とMacWilliams方程式の古典的な扱いについては MacWilliams–Sloane [MS77, Chapter 5] を参照してください． また，MacWilliams方程式とPlessモーメントを含む同値な定式化については Huffman–Pless [HP03, Sections 7.1–7.2] が標準的です． Plessモーメントの教科書的な扱いについては， Pless [Ple98, Chapter 8] も参照してください．↩
3. [HP03] W. Cary Huffman and Vera Pless. Fundamentals of Error-Correcting Codes. Cambridge University Press, 2003. doi:10.1017/CBO9780511807077 引用箇所Plessの古典的な論文 [Ple63] では，MacWilliams恒等式から冪モーメント恒等式が導かれ， それらの応用も与えられています． 本稿では，MacWilliams恒等式を既知とせず，二項モーメントを直接二重数え上げで計算し， 十分多くのモーメントからMacWilliams恒等式を復元する，という方向で説明します． 双対符号の重み分布とMacWilliams方程式の古典的な扱いについては MacWilliams–Sloane [MS77, Chapter 5] を参照してください． また，MacWilliams方程式とPlessモーメントを含む同値な定式化については Huffman–Pless [HP03, Sections 7.1–7.2] が標準的です． Plessモーメントの教科書的な扱いについては， Pless [Ple98, Chapter 8] も参照してください．↩
4. [Ple98] Vera Pless. Introduction to the theory of error-correcting codes. John Wiley & Sons, Inc., New York, pp. xiv+207, 1998. doi:10.1002/9781118032749 引用箇所Plessの古典的な論文 [Ple63] では，MacWilliams恒等式から冪モーメント恒等式が導かれ， それらの応用も与えられています． 本稿では，MacWilliams恒等式を既知とせず，二項モーメントを直接二重数え上げで計算し， 十分多くのモーメントからMacWilliams恒等式を復元する，という方向で説明します． 双対符号の重み分布とMacWilliams方程式の古典的な扱いについては MacWilliams–Sloane [MS77, Chapter 5] を参照してください． また，MacWilliams方程式とPlessモーメントを含む同値な定式化については Huffman–Pless [HP03, Sections 7.1–7.2] が標準的です． Plessモーメントの教科書的な扱いについては， Pless [Ple98, Chapter 8] も参照してください．↩