MacWilliams恒等式で学ぶKrawtchouk多項式入門

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

を考えます． ここで

です． この双対符号の重み多項式は，$C$ の重み多項式から次のように計算できます：

これがMacWilliams恒等式です．

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

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

• （有限）体とは何か

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

• Hamming重みとは何か

• 双対符号とは何か

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

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

1. Fourier・指標・Poisson系．

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

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

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

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

本稿では，このうち「直交多項式・アソシエーションスキーム系」に着目します． ただし，本稿ではアソシエーションスキーム全体の理論にはまだ入りません． 指標和を最小限の道具として使いながら，MacWilliams恒等式を重み分布上のKrawtchouk変換として読み直します． これは，直交多項式・アソシエーションスキーム的な見方への入口です． 本稿の目標は，MacWilliams恒等式の証明を案内役として， Krawtchouk多項式に入門することです．

MacWilliams恒等式は，通常，多項式の恒等式として

という形で書かれます． 本稿では，この式を係数レベルで見ます． 符号 $C$ の重み分布を

と書くと，重み多項式は

です．MacWilliams恒等式は，重み分布ベクトル

から，双対符号の重み分布ベクトル

を計算する変換でもあります． この変換係数として現れるのがKrawtchouk多項式です．

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

• 重み分布を見る．

• Krawtchouk多項式を母関数で定義する．

• 明示公式と小さな例で慣れる．

• 指標和としての意味を見る．

• 直交性とKrawtchouk変換を確認する．

• 係数レベルのMacWilliams恒等式を導く．

• 通常の多項式形へ戻る．

Krawtchouk多項式は，離散的な直交多項式の代表例です． 古典的な直交多項式の世界では，Hermite多項式，Laguerre多項式，Jacobi多項式などがよく知られています． これらは連続的な区間上の積分に関する直交性を持ちます． 一方，Krawtchouk多項式は $\{ 0, 1, \dots, n \}$ という有限集合上の和に関して直交します． この「有限集合上の直交多項式」であることが，Hamming重みと非常によく噛み合います．

Krawtchouk多項式の原論文は Krawtchouk [Kra29] です． 直交多項式としての体系的な位置づけについては Koekoek–Lesky–Swarttouw [KLS10, Chapter 9] が標準的な参考文献です． 符号理論におけるKrawtchouk多項式とMacWilliams恒等式については MacWilliams–Sloane [MS77, Chapter 5] が古典的な標準文献です．

まず，重み多項式を係数ベクトルとして見直します． $E$ を有限集合，$n = \card{E}$ とします． 符号語 $c \in \mathbb{F}_{q}^{E}$ のHamming重みを

と書きます．

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

と書けます． 重み多項式は，重み分布を一つの二変数多項式として包み込んだものです．

MacWilliams恒等式を係数レベルで書くために，双対符号の重み分布を

と書きます． 目標は，$B_j$ を $A_w(C)$ たちで表すことです． その形は

となります． ここで $\Kraw_j(w)$ がKrawtchouk多項式の値です．

つまり，本稿の証明では，MacWilliams恒等式を

重み分布ベクトルに対する線形変換

として見ます． この線形変換を記述する行列の成分がKrawtchouk多項式です．

ここからKrawtchouk多項式を定義します． 本稿では，符号理論で自然に現れる $q$ 元Hamming空間に合わせた規格化を使います． 文献によって，添字の置き方や正規化にはいくつかの流儀がありますが， 本稿では次の定義を採用します．

ここで，下付き添字 $j$ は「何番目のKrawtchouk多項式か」を表し， 括弧内の $w$ はその多項式に代入するHamming重みを表します． したがって $\Kraw_j(w)$ は，$j$ 番目の多項式 $\Kraw_j(x)$ に $x=w$ を代入した値です． 符号理論では，主に $w=0,1,\dots,n$ に対する値を使います．

この定義では，最初に $x$ を一般変数として右辺を読むのではなく， 重み $w=0,1,\dots,n$ に対する値を先に定めています． 次の明示公式を見ると，$\Kraw_j(x)$ は $x$ に関する本当に次数 $j$ 以下の多項式であり， 整数 $w$ を代入すると $$\sum_{j=0}^{n}\Kraw_{j}(w)z^{j} = \bigl( 1 + (q - 1)z \bigr)^{n - w}(1 - z)^{w} \tag{3.1}$$3.1 を満たすことが分かります． 符号理論では，主に $x=w$ を重みとする整数値に代入して使います．

$$\sum_{j=0}^{n}\Kraw_{j}(w)z^{j} = \bigl( 1 + (q - 1)z \bigr)^{n - w}(1 - z)^{w} \tag{3.1}$$3.1 を展開すると，次の明示公式が得られます．

証明

まず $0\leq w\leq n$ を固定し，母関数の右辺を二項定理で展開する．

$$\begin{aligned} &\bigl(1+(q-1)z\bigr)^{n-w}(1-z)^w \\ ={}& \left( \sum_{a\geq 0}\binom{n-w}{a}(q-1)^a z^a \right) \left( \sum_{b\geq 0}\binom{w}{b}(-1)^b z^b \right) . \end{aligned}$$

$z^j$ の係数を取ると，$a+b=j$ であるから，$b=\ell$ とおいて

$$\sum_{\ell=0}^{j} (-1)^{\ell}(q-1)^{j-\ell} \binom{w}{\ell}\binom{n-w}{j-\ell}$$

を得る． これは母関数の左辺における $z^j$ の係数 $\Kraw_j(w)$ に等しい． 右辺を $w$ の代わりに変数 $x$ で書いたものが $$\Kraw_j(x) = \sum_{\ell=0}^{j} (-1)^{\ell}(q-1)^{j-\ell} \binom{x}{\ell}\binom{n-x}{j-\ell} \tag{3.2}$$(3.2) の多項式である．

証明終わり□

ここで $\binom{x}{\ell}$ は

で定まる $x$ の多項式として読みます． 同様に $\binom{n-x}{j-\ell}$ も $x$ の多項式です． 整数 $x=w$ を代入すると通常の二項係数の値と一致するので， この意味で $$\Kraw_j(x) = \sum_{\ell=0}^{j} (-1)^{\ell}(q-1)^{j-\ell} \binom{x}{\ell}\binom{n-x}{j-\ell} \tag{3.2}$$(3.2) は $\Kraw_j(x)$ を $x$ の多項式として与えています．

この公式には，すでに符号理論的な意味が見えています． 重み $w$ の語を一つ固定します． 長さ $n$ の座標のうち，$w$ 個は非零座標，$n-w$ 個は零座標です． 重み $j$ の別の語を考えるとき，その非零座標のうち $\ell$ 個が固定した語の非零座標と重なり， 残りの $j-\ell$ 個が零座標側にある，という選び方が現れます． その数え上げの中に符号付きの和が入ることで，Krawtchouk多項式が出てきます． ここで注意したいのは，これは単なる個数の和ではない，という点です． 後で導入する非自明加法指標 $\psi$ を使って指標和として説明しますが， 固定した語の非零座標と重なる場所では， 非零値を $q-1$ 通りとしてそのまま数えるのではなく，

という振動和が現れます． そのため，重なった座標の寄与は $(q-1)^{\ell}$ ではなく $(-1)^{\ell}$ になります． この値を $w$ の関数として見たものが $\Kraw_j(w)$ であり， 明示公式によって多項式 $\Kraw_j(x)$ として表されます． この符号付きの数え上げが，後の指標和としての解釈につながります．

定義に慣れるために，いくつかの低次の多項式を計算してみます． 重み $w$ に対する母関数

の定数項は $1$ なので，

です．

次に $z$ の係数を見ると，重み $w$ に対して

です． これを $x$ の多項式として書くと，

となります． つまり，$\Kraw_1(x)$ は $x$ に関する一次式です．

特に二元の場合，つまり $q=2$ では

です． これは，二元Hamming空間で非常によく現れる量です． 重み $w$ の語は，零座標を $n-w$ 個，非零座標を $w$ 個持ちます． 二元の場合，非零座標は符号付きで $-1$ を寄与し，零座標は $+1$ を寄与するので，差

が現れます．

この表は，後で二元反復符号の例で使います． ここでは，$j$ を固定すると $x$ の関数になっていることに注意してください． 例えば $\Kraw_2(x)$ は，$x=0,1,2,3$ に対して $3,-1,-1,3$ という値を取ります．

Krawtchouk多項式は，単に母関数で定義された多項式ではありません． Hamming空間の中では，次のような自然な和として現れます．

ここでは，有限体 $\mathbb{F}_{q}$ の非自明な加法指標

を一つ固定します． つまり，$\psi(a+b)=\psi(a)\psi(b)$ が成り立ち，かつ $\psi$ は恒等的に $1$ ではないとします． 有限体にはそのような加法指標が存在します． 実際，$q=p^m$ とし，非零な $\mathbb{F}_{p}$ 線形写像 $L\colon \mathbb{F}_{q}\to\mathbb{F}_{p}$ を取れば，

は非自明な加法指標です． ここでは，$L(a)\in\mathbb{F}_{p}$ を $0,1,\dots,p-1$ の代表で読んでいます． 本稿の主役は指標論ではありませんが，Krawtchouk多項式がHamming空間から出てくる様子を見るために， この一つの道具だけを使います． 指標論の一般論は仮定せず，以下で必要な性質だけを証明します． 具体的には，ここで証明する一座標の指標和と，後で使う双対符号の指示関数を取り出す公式だけを使います． そのため，指標論を体系的に知っていなくても，この節の証明は追えるようにしてあります．

必要になる指標和の性質は次の一つです．

証明

$b=0$ なら，すべての $a$ に対して $\psi(ab)=\psi(0)=1$ なので，和は $q$ である． $b\neq 0$ とする．このとき $a\mapsto ab$ は $\mathbb{F}_{q}$ の全単射なので，

$$\sum_{a\in\mathbb{F}_{q}}\psi(ab) = \sum_{t\in\mathbb{F}_{q}}\psi(t)$$

である．右辺を $S$ とおく． $\psi$ は非自明なので，ある $d\in\mathbb{F}_{q}$ に対して $\psi(d)\neq 1$ である． $t$ が $\mathbb{F}_{q}$ 全体を動くとき，$t+d$ も $\mathbb{F}_{q}$ 全体を動くから，

$$S = \sum_{t\in\mathbb{F}_{q}}\psi(t+d) = \sum_{t\in\mathbb{F}_{q}}\psi(t)\psi(d) = \psi(d)S.$$

$\psi(d)\neq 1$ なので $S=0$ である．

証明終わり□

証明

左辺を $j$ についてまとめた母関数を計算する．

$$\begin{aligned} \sum_{j=0}^{n} \left( \sum_{\substack{u\in\mathbb{F}_{q}^{E}\\ \wt(u)=j}} \psi(u\cdot c) \right)z^j &= \sum_{u\in\mathbb{F}_{q}^{E}} \psi(u\cdot c)z^{\wt(u)} \\ &= \sum_{u\in\mathbb{F}_{q}^{E}} \prod_{r\in E}\psi(u_r c_r)z^{\mathbf{1}_{u_r\neq 0}} \\ &= \prod_{r\in E} \left( \sum_{a\in\mathbb{F}_{q}} \psi(a c_r)z^{\mathbf{1}_{a\neq 0}} \right). \end{aligned}$$

ここで $\mathbf{1}_{u_r\neq 0}$ は，$u_r\neq 0$ のとき $1$，そうでないとき $0$ である．

座標 $r$ について，$c_r=0$ なら

$$\sum_{a\in\mathbb{F}_{q}} \psi(a c_r)z^{\mathbf{1}_{a\neq 0}} = 1+(q-1)z$$

である． 一方，$c_r\neq 0$ なら，$a\mapsto ac_r$ は $\mathbb{F}_{q}$ の全単射であり， 補題 5.1$b\in\mathbb{F}_{q}$ に対して $$\sum_{a\in\mathbb{F}_{q}}\psi(ab) = \begin{cases} q, & b=0,\\ 0, & b\neq 0 \end{cases}$$ が成り立つ．補題 5.1 より

$$\sum_{a\in\mathbb{F}_{q}}\psi(ac_r)=0$$

である．したがって

$$\sum_{a\in\mathbb{F}_{q}^{\times}}\psi(ac_r)=-1$$

である．したがって

$$\sum_{a\in\mathbb{F}_{q}} \psi(a c_r)z^{\mathbf{1}_{a\neq 0}} = 1-z$$

となる．

$c$ は重み $w$ を持つので，$c_r\neq 0$ となる座標は $w$ 個，$c_r=0$ となる座標は $n-w$ 個である． よって上の母関数は

$$\bigl(1+(q-1)z\bigr)^{n-w}(1-z)^w$$

である．これはKrawtchouk多項式の母関数

$$\sum_{j=0}^{n}\Kraw_j(w)z^j$$

に等しい．$z^j$ の係数を比較して，主張を得る．

証明終わり□

この定理は，Krawtchouk多項式の符号理論的な意味をよく表しています． $\Kraw_j(w)$ は，重み $w$ の語 $c$ を固定したとき， 重み $j$ の語 $u$ について指標値 $\psi(u\cdot c)$ を足し合わせたものです． 言い換えると，Krawtchouk多項式は，

Hamming空間の重み $j$ の層を，重み $w$ の語に対して見たときの振動和

です．

ここでは指標和を使って説明しましたが，式 $$\Kraw_j(x) = \sum_{\ell=0}^{j} (-1)^{\ell}(q-1)^{j-\ell} \binom{x}{\ell}\binom{n-x}{j-\ell} \tag{3.2}$$(3.2) だけを見れば， これは座標の重なり方を数えた二項係数の和でもあります． 直交多項式としてのKrawtchouk多項式は，この二つの見方を橋渡ししています．

Krawtchouk多項式が「直交多項式」と呼ばれる理由を見ます． 直交性とは，大まかには，異なる次数の多項式どうしの内積が $0$ になることです． Krawtchouk多項式の場合，内積は有限集合

上の和で定義されます．

$0\leq w\leq n$ に対して

とおきます． これは，$\mathbb{F}_{q}^{E}$ の中で重み $w$ の語の個数です． 実際，非零となる $w$ 個の座標を選ぶ方法が $\binom{n}{w}$ 通りあり， それぞれの非零座標には $q-1$ 通りの値があります．

この内積は，Hamming空間の各重み層の大きさを重みとして持っています． Krawtchouk多項式は，この内積に関して直交します． Krawtchouk多項式の値は実数なので，直交性の公式では複素共役を書いても書かなくても同じ式になります．

証明

二変数の母関数を計算する．

$$\begin{aligned} &H(z,t) \\ \coloneqq{}& \sum_{w=0}^{n}\binom{n}{w}(q-1)^w \left(\sum_{r=0}^{n}\Kraw_r(w)z^r\right) \left(\sum_{s=0}^{n}\Kraw_s(w)t^s\right) \\ &= \sum_{w=0}^{n}\binom{n}{w}(q-1)^w \bigl(1+(q-1)z\bigr)^{n-w}(1-z)^w \bigl(1+(q-1)t\bigr)^{n-w}(1-t)^w \\ &= \sum_{w=0}^{n}\binom{n}{w} \left((1+(q-1)z)(1+(q-1)t)\right)^{n-w} \left((q-1)(1-z)(1-t)\right)^w \\ &= \left( (1+(q-1)z)(1+(q-1)t) +(q-1)(1-z)(1-t) \right)^n . \end{aligned}$$

括弧の中を整理すると，

$$\begin{aligned} &(1+(q-1)z)(1+(q-1)t) +(q-1)(1-z)(1-t) \\ &\qquad= q\bigl(1+(q-1)zt\bigr) \end{aligned}$$

である．したがって

$$H(z,t) = q^n\bigl(1+(q-1)zt\bigr)^n = q^n\sum_{r=0}^{n}\binom{n}{r}(q-1)^r z^r t^r.$$

一方，$H(z,t)$ の定義から，$z^r t^s$ の係数は左辺

$$\sum_{w=0}^{n}\binom{n}{w}(q-1)^w\Kraw_r(w)\Kraw_s(w)$$

である．係数を比較して $$\sum_{w=0}^{n} \binom{n}{w}(q-1)^w \Kraw_r(w)\Kraw_s(w) = q^n \binom{n}{r}(q-1)^r \delta_{r,s} \tag{6.1}$$(6.1) を得る．

証明終わり□

この定理により，$\Kraw_0,\Kraw_1,\dots,\Kraw_n$ は， 有限集合 $\{0,1,\dots,n\}$ 上の関数空間の直交基底になっています． ここが重要です． Krawtchouk多項式は，単なる便利な係数ではなく， Hamming空間の重み層に自然に付随する直交基底です．

Krawtchouk多項式を使うと，長さ $n+1$ のベクトルに対する変換を定義できます． これがKrawtchouk変換です．

行列で書けば，Krawtchouk変換は

という $(n+1)\times(n+1)$ 行列を掛ける操作です． この行列をKrawtchouk行列と呼ぶことがあります．

直前に示した直交性は，重み

を付けた内積に関する直交性であり，和は

という形でした． 一方，ここで示す自己逆性は，Krawtchouk行列そのものを二回掛ける性質であり，和は

という形になります． 両者は密接に関係していますが，和を取る添字と重みの付き方が違うので，ここでは区別しておきます． 直交性は関数 $\Kraw_r,\Kraw_s$ の重み付き内積に関する式であり， 自己逆性はKrawtchouk行列 $K=(\Kraw_j(w))$ の積に関する式です．

Krawtchouk変換は，正規化を除いて自分自身が逆変換になります．

証明

示すべきことは，任意の $0\leq r,w\leq n$ に対して

$$\sum_{j=0}^{n}\Kraw_r(j)\Kraw_j(w) = q^n\delta_{r,w} \tag{7.1}$$

が成り立つことである． 固定した $w$ に対して，左辺を $r$ について母関数にまとめる．

$$\begin{aligned} \sum_{r=0}^{n} \left( \sum_{j=0}^{n}\Kraw_r(j)\Kraw_j(w) \right)t^r &= \sum_{j=0}^{n}\Kraw_j(w) \left( \sum_{r=0}^{n}\Kraw_r(j)t^r \right) \\ &= \sum_{j=0}^{n}\Kraw_j(w) \bigl(1+(q-1)t\bigr)^{n-j}(1-t)^j \\ &= \bigl(1+(q-1)t\bigr)^n \sum_{j=0}^{n}\Kraw_j(w) \left(\frac{1-t}{1+(q-1)t}\right)^j . \end{aligned}$$

Krawtchouk多項式の母関数を

$$s=\frac{1-t}{1+(q-1)t}$$

に代入すると，

$$\begin{aligned} \sum_{j=0}^{n}\Kraw_j(w)s^j &= \bigl(1+(q-1)s\bigr)^{n-w}(1-s)^w. \end{aligned}$$

ここで

$$1+(q-1)s = \frac{q}{1+(q-1)t}, \qquad 1-s = \frac{qt}{1+(q-1)t}$$

である．したがって

$$\begin{aligned} &\bigl(1+(q-1)t\bigr)^n \sum_{j=0}^{n}\Kraw_j(w)s^j \\ ={}& \bigl(1+(q-1)t\bigr)^n \left(\frac{q}{1+(q-1)t}\right)^{n-w} \left(\frac{qt}{1+(q-1)t}\right)^w \\ ={}& q^n t^w. \end{aligned}$$

よって，$t^r$ の係数は $r=w$ のとき $q^n$，それ以外のとき $0$ である． これが $$\sum_{j=0}^{n}\Kraw_r(j)\Kraw_j(w) = q^n\delta_{r,w} \tag{7.1}$$(7.1) であり，主張が従う．

証明終わり□

この自己逆性は，MacWilliams恒等式の対称性と対応しています． 実際，$C$ の双対をさらに取ると $(C^{\perp})^{\perp}=C$ です． また，有限体上の線形符号では

です． これは $\dim C+\dim C^{\perp}=n$ から従います． したがって，重み分布に対する変換が二回で $q^n$ 倍になることは， 双対を二回取ると元に戻ることと整合しています．

ここからKrawtchouk多項式を用いてMacWilliams恒等式を証明します． まず係数レベルの公式を示します．

この節でも，有限体 $\mathbb{F}_{q}$ の非自明な加法指標 $\psi$ を一つ固定します． 指標論そのものを詳しく展開するわけではありませんが，次の直交補抽出公式だけを使います．

証明

$u\in C^{\perp}$ なら，任意の $c\in C$ に対して $u\cdot c=0$ なので， 各項は $\psi(0)=1$ であり，和は $\card{C}$ である．

$u\notin C^{\perp}$ とする．このとき，ある $c_0\in C$ が存在して $d=u\cdot c_0\neq 0$ である． $d\neq 0$ なので，$a\mapsto ad$ は $\mathbb{F}_{q}$ の全単射である． $\psi$ は非自明なので，ある $a\in\mathbb{F}_{q}$ に対して $\psi(ad)\neq 1$ となる．

$$S=\sum_{c\in C}\psi(u\cdot c)$$

とおく．$C$ は線形符号なので $ac_0\in C$ であり， $c$ が $C$ 全体を動くとき $c+ac_0$ も $C$ 全体を一度ずつ動く． したがって

$$\begin{aligned} S &= \sum_{c\in C}\psi(u\cdot(c+ac_0)) \\ &= \sum_{c\in C}\psi(u\cdot c)\psi(a(u\cdot c_0)) \\ &= \psi(ad)S. \end{aligned}$$

いま $\psi(ad)\neq 1$ なので，$S=0$ である．

証明終わり□

この補題により，$C^{\perp}$ 上の和を $C$ 上の和に変換できます． ここにKrawtchouk多項式の和 $$\sum_{\substack{u\in\mathbb{F}_{q}^{E}\\ \wt(u)=j}} \psi(u\cdot c) = \Kraw_j(w) \tag{5.1}$$(5.1) を代入します．

証明

双対符号の重み $j$ の語の個数を，指示関数を使って書くと

$$B_j = \sum_{\substack{u\in\mathbb{F}_{q}^{E}\\\wt(u)=j}} \mathbf{1}_{C^{\perp}}(u)$$

である． 補題 8.1任意の $u\in\mathbb{F}_{q}^{E}$ に対して $$\frac{1}{\card{C}} \sum_{c\in C}\psi(u\cdot c) = \begin{cases} 1, & u\in C^{\perp},\\ 0, & u\notin C^{\perp} \end{cases} \tag{8.1}$$ が成り立つ．補題 8.1 を代入すると，

$$\begin{aligned} B_j &= \frac{1}{\card{C}} \sum_{\substack{u\in\mathbb{F}_{q}^{E}\\\wt(u)=j}} \sum_{c\in C}\psi(u\cdot c) \\ &= \frac{1}{\card{C}} \sum_{c\in C} \sum_{\substack{u\in\mathbb{F}_{q}^{E}\\\wt(u)=j}} \psi(u\cdot c). \end{aligned}$$

定理 5.2$c\in\mathbb{F}_{q}^{E}$ を重み $w$ の語とする． このとき任意の $0\leq j\leq n$ に対して $$\sum_{\substack{u\in\mathbb{F}_{q}^{E}\\ \wt(u)=j}} \psi(u\cdot c) = \Kraw_j(w) \tag{5.1}$$ が成り立つ．定理 5.2 より，内側の和は

$$\Kraw_j(\wt(c))$$

に等しい．したがって

$$B_j = \frac{1}{\card{C}} \sum_{c\in C}\Kraw_j(\wt(c)).$$

重み $w$ の符号語は $A_w$ 個あるので，これは

$$B_j = \frac{1}{\card{C}} \sum_{w=0}^{n}A_w\Kraw_j(w)$$

となる．

証明終わり□

この定理が，Krawtchouk多項式によるMacWilliams恒等式の係数版です． 言い換えると，双対符号の重み分布は，元の符号の重み分布のKrawtchouk変換を $\card{C}$ で割ったものです：

係数レベルの公式から，通常の多項式形のMacWilliams恒等式を導きます．

証明

$A_w=A_w(C)$，$B_j=A_j(C^{\perp})$ とおく． 係数レベルの公式 $$B_j = \frac{1}{\card{C}} \sum_{w=0}^{n}A_w\Kraw_j(w) \tag{8.2}$$(8.2) より

$$\begin{aligned} W_{C^{\perp}}(X,Y) &= \sum_{j=0}^{n}B_jX^{n-j}Y^j \\ &= \frac{1}{\card{C}} \sum_{j=0}^{n} \sum_{w=0}^{n}A_w\Kraw_j(w)X^{n-j}Y^j \\ &= \frac{1}{\card{C}} \sum_{w=0}^{n}A_w \sum_{j=0}^{n}\Kraw_j(w)X^{n-j}Y^j. \end{aligned}$$

ここでKrawtchouk多項式の母関数を使う． ここでの $Y/X$ は形式的な計算であり，最終的には両辺が $X,Y$ の多項式として一致することを意味している．

$$\begin{aligned} \sum_{j=0}^{n}\Kraw_j(w)X^{n-j}Y^j &= X^n\sum_{j=0}^{n}\Kraw_j(w)\left(\frac{Y}{X}\right)^j \\ &= X^n \left(1+(q-1)\frac{Y}{X}\right)^{n-w} \left(1-\frac{Y}{X}\right)^w \\ &= \bigl(X+(q-1)Y\bigr)^{n-w}(X-Y)^w. \end{aligned}$$

したがって

$$\begin{aligned} W_{C^{\perp}}(X,Y) &= \frac{1}{\card{C}} \sum_{w=0}^{n}A_w \bigl(X+(q-1)Y\bigr)^{n-w}(X-Y)^w \\ &= \frac{1}{\card{C}} W_C\bigl(X+(q-1)Y,X-Y\bigr). \end{aligned}$$

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

証明終わり□

この証明では，MacWilliams恒等式の変数変換

は，Krawtchouk多項式の母関数から現れました． つまり，MacWilliams恒等式は

Krawtchouk変換を，重み多項式という母関数でまとめ直したもの

と見ることができます．

係数レベルの公式を，小さな例で確認します． $\mathbb{F}_{2}^{3}$ 上の反復符号

を考えます． この符号の重み分布は

です．

この符号の双対符号は

であり，偶数重みの語全体です．したがって

で，重み分布は

です． これがKrawtchouk変換から出てくることを確認します．

例 4.1（二元で n=3 の場合）$q=2$, $n=3$ とする．母関数は $$\sum_{j=0}^{3}\Kraw_j(w)z^j = (1+z)^{3-w}(1-z)^w$$ である． $x=0,1,2,3$ に対する値を表にすると， $$\begin{array}{c|rrrr} & x=0 & x=1 & x=2 & x=3 \\ \hline \Kraw_0(x) & 1 & 1 & 1 & 1 \\ \Kraw_1(x) & 3 & 1 & -1 & -3 \\ \Kraw_2(x) & 3 & -1 & -1 & 3 \\ \Kraw_3(x) & 1 & -1 & 1 & -1 \end{array}$$ となる．例 4.1 より，$q=2$, $n=3$ のKrawtchouk表は

です． 係数レベルのMacWilliams恒等式は

でした．いま $\card{C}=2$，かつ $A_0=A_3=1$，$A_1=A_2=0$ なので

です． 表から

したがって

となり，確かに $C^{\perp}$ の重み分布と一致します．

多項式で見ると，

であり，MacWilliams恒等式の右辺は

これは

と一致します．

この例では，Krawtchouk表の第 $j$ 行を重み分布 $(1,0,0,1)$ に掛けることで， 双対符号の $j$ 番目の重み分布係数が得られています．

証明の中でKrawtchouk多項式が果たしていた役割を整理しておきます．

第一に，Krawtchouk多項式は，重み分布の変換係数でした． $C$ の重み分布を $A_w=A_w(C)$，$C^{\perp}$ の重み分布を $B_j=A_j(C^{\perp})$ と書くと，

でした． これは，MacWilliams恒等式を係数レベルで見た式です．

第二に，Krawtchouk多項式は，Hamming空間の重み層に関する振動和でした． 重み $w$ の語 $c$ を固定すると，

が成り立ちました． つまり，$\Kraw_j(w)$ は，重み $j$ の層を重み $w$ の語から見たときの和です．

第三に，Krawtchouk多項式は直交基底を作っていました． 重み

を付けた有限集合 $\{0,\dots,n\}$ 上で， $\Kraw_0,\dots,\Kraw_n$ は互いに直交します． これは，Krawtchouk多項式が単なる計算上の係数ではなく， Hamming空間の距離構造に付随する直交多項式であることを示しています．

第四に，母関数がMacWilliams変数変換を作っていました．

に形式的に $z=Y/X$ を代入します． ここでの $Y/X$ は形式的な置き換えであり，最終的には $X,Y$ の多項式としての等式を得ています．

が得られました． これが，多項式形のMacWilliams恒等式の変数変換です．

したがって，本稿の証明では，Krawtchouk多項式が

1. 双対符号の重み分布を計算する変換係数，

2. Hamming空間の重み層に関する振動和，

3. 有限集合上の直交多項式，

4. MacWilliams変数変換を生む母関数，

という四つの役割を果たしていました．

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

重み分布

符号 $C$ に対して

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

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

Krawtchouk多項式

まず重み $w=0,1,\dots,n$ に対する値を，母関数

$$\sum_{j=0}^{n}\Kraw_j(w)z^j = \bigl(1+(q-1)z\bigr)^{n-w}(1-z)^w$$

で定めます． 明示公式により，これらの値は $x$ に関する多項式 $\Kraw_j(x)$ から得られます． 符号理論では，主に $x$ に重み $0,1,\dots,n$ を代入して使います．

明示公式

Krawtchouk多項式は

$$\Kraw_j(x) = \sum_{\ell=0}^{j} (-1)^{\ell}(q-1)^{j-\ell} \binom{x}{\ell}\binom{n-x}{j-\ell}$$

と書けます． これは，重なり方を数える二項係数に，指標値から来る符号付きの寄与を加えた和として解釈できます．

直交性

$\Kraw_0,\dots,\Kraw_n$ は，重み

$$\binom{n}{w}(q-1)^w$$

を持つ有限集合 $\{0,\dots,n\}$ 上で直交します． この重みは，Hamming空間における重み $w$ の語の個数です．

Krawtchouk変換

ベクトル $a=(a_0,\dots,a_n)$ に対して

$$(\mathcal{K}a)_j=\sum_{w=0}^{n}a_w\Kraw_j(w)$$

で定まる変換です． この変換は二回施すと $q^n$ 倍になります．

係数レベルのMacWilliams恒等式

$A_w=A_w(C)$，$B_j=A_j(C^{\perp})$ とすると

$$B_j = \frac{1}{\card{C}} \sum_{w=0}^{n}A_w\Kraw_j(w)$$

となります． これは，双対符号の重み分布が元の符号の重み分布のKrawtchouk変換で得られることを意味します．

直交多項式というと，最初は解析的な対象に見えるかもしれません． しかしKrawtchouk多項式は，有限集合上の和だけで直交性を持つ，非常に離散的な直交多項式です． そのため，Hamming空間や符号理論と相性がよいのです．

冒頭で述べたように，本稿の証明は

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

への入口として読むことができます． 表面的には，Krawtchouk多項式を使った係数計算です． また，係数レベルのMacWilliams恒等式を証明するために，指標和も最小限の道具として使いました． しかし，深いところでは，Hamming空間の距離構造に付随する直交多項式が， 重み分布の変換を支配しています．

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

MacWilliams恒等式は，重み分布に対するKrawtchouk変換である．

Fourier的な見方では，$\mathbb{F}_{q}^{E}$ の全体に対する変換を扱います． 本稿の見方では，その情報を「重みだけ」に押しつぶしています． 全ての語を区別するのではなく，重み $0,1,\dots,n$ ごとの係数だけを見る． この圧縮された世界で，Fourier的な変換の影として現れるのがKrawtchouk多項式です．

この見方は，発展的にはアソシエーションスキームへ自然につながります． Hamming空間では，二つの語の距離が $0,1,\dots,n$ のどれであるかによって関係を分けることができます． その関係から作られる可換代数がHammingアソシエーションスキームのBose–Mesner代数です． その固有値として現れるのが，まさにKrawtchouk多項式です． Delsarteのアソシエーションスキーム的な符号理論については Delsarte [Del73] が古典的な出発点であり， Delsarte–Levenshtein [DL98] はアソシエーションスキームと符号理論の関係を概観しています． Krawtchouk多項式がHamming空間の符号・デザインの限界に現れることについては Levenshtein [Lev95] も代表的な文献です．

ここまでで，本稿の目的であるKrawtchouk多項式を用いたMacWilliams恒等式の見方は一通り完結しました． ここから先は発展的な見方として，本稿で現れたKrawtchouk多項式をアソシエーションスキームの言葉で見直す方向を紹介します．

本稿の証明では，Krawtchouk多項式を母関数で定義し，重み分布の変換係数として使いました． しかし，なぜこの多項式がHamming空間に自然に付随するのでしょうか． その答えは，Hamming空間の距離関係から作られる行列にあります．

長さ $n$ の語全体を頂点集合とし，二つの語の距離が $j$ であるかどうかを表す行列を $M_{j}$ と書きます． ここでの $M_j$ は，距離関係を表す隣接行列です． これらの行列は互いに可換な代数を作ります． この代数を同時対角化すると，その固有値としてKrawtchouk多項式が現れます．

つまり，発展的な見方での主役は

という流れです． MacWilliams恒等式は，この固有値理論の中で，重み分布の双対変換として現れます．

同じKrawtchouk多項式であっても，本稿のように「母関数で定義される直交多項式」として見るか， 発展的に「Hamming schemeの固有値」として見るかで，見え方は大きく変わります． この違いが，アソシエーションスキームへの自然な入口になります．

参考文献

1. [Kra29] M. Krawtchouk. Sur une généralisation des polynômes d'Hermite. Comptes rendus hebdomadaires des séances de l'Académie des sciences, vol. 189, pp. 620–622, 1929 引用箇所Krawtchouk多項式の原論文は Krawtchouk [Kra29] です． 直交多項式としての体系的な位置づけについては Koekoek–Lesky–Swarttouw [KLS10, Chapter 9] が標準的な参考文献です． 符号理論におけるKrawtchouk多項式とMacWilliams恒等式については MacWilliams–Sloane [MS77, Chapter 5] が古典的な標準文献です．↩
2. [KLS10] Roelof Koekoek, Peter A. Lesky, and René F. Swarttouw. Hypergeometric orthogonal polynomials and their q-analogues. Springer-Verlag, Berlin, pp. xx+578, 2010. doi:10.1007/978-3-642-05014-5 引用箇所Krawtchouk多項式の原論文は Krawtchouk [Kra29] です． 直交多項式としての体系的な位置づけについては Koekoek–Lesky–Swarttouw [KLS10, Chapter 9] が標準的な参考文献です． 符号理論におけるKrawtchouk多項式とMacWilliams恒等式については MacWilliams–Sloane [MS77, Chapter 5] が古典的な標準文献です．↩
3. [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 引用箇所Krawtchouk多項式の原論文は Krawtchouk [Kra29] です． 直交多項式としての体系的な位置づけについては Koekoek–Lesky–Swarttouw [KLS10, Chapter 9] が標準的な参考文献です． 符号理論におけるKrawtchouk多項式とMacWilliams恒等式については MacWilliams–Sloane [MS77, Chapter 5] が古典的な標準文献です．↩
4. [Del73] P. Delsarte. An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl., no. 10, pp. vi+97, 1973 引用箇所この見方は，発展的にはアソシエーションスキームへ自然につながります． Hamming空間では，二つの語の距離が $0,1,\dots,n$ のどれであるかによって関係を分けることができます． その関係から作られる可換代数がHammingアソシエーションスキームのBose–Mesner代数です． その固有値として現れるのが，まさにKrawtchouk多項式です． Delsarteのアソシエーションスキーム的な符号理論については Delsarte [Del73] が古典的な出発点であり， Delsarte–Levenshtein [DL98] はアソシエーションスキームと符号理論の関係を概観しています． Krawtchouk多項式がHamming空間の符号・デザインの限界に現れることについては Levenshtein [Lev95] も代表的な文献です．↩
5. [DL98] Philippe Delsarte and Vladimir I. Levenshtein. Association schemes and coding theory. IEEE Trans. Inform. Theory, vol. 44, no. 6, pp. 2477–2504, 1998. doi:10.1109/18.720545 引用箇所この見方は，発展的にはアソシエーションスキームへ自然につながります． Hamming空間では，二つの語の距離が $0,1,\dots,n$ のどれであるかによって関係を分けることができます． その関係から作られる可換代数がHammingアソシエーションスキームのBose–Mesner代数です． その固有値として現れるのが，まさにKrawtchouk多項式です． Delsarteのアソシエーションスキーム的な符号理論については Delsarte [Del73] が古典的な出発点であり， Delsarte–Levenshtein [DL98] はアソシエーションスキームと符号理論の関係を概観しています． Krawtchouk多項式がHamming空間の符号・デザインの限界に現れることについては Levenshtein [Lev95] も代表的な文献です．↩
6. [Lev95] Vladimir I. Levenshtein. Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces. IEEE Trans. Inform. Theory, vol. 41, no. 5, pp. 1303–1321, 1995. doi:10.1109/18.412678 引用箇所この見方は，発展的にはアソシエーションスキームへ自然につながります． Hamming空間では，二つの語の距離が $0,1,\dots,n$ のどれであるかによって関係を分けることができます． その関係から作られる可換代数がHammingアソシエーションスキームのBose–Mesner代数です． その固有値として現れるのが，まさにKrawtchouk多項式です． Delsarteのアソシエーションスキーム的な符号理論については Delsarte [Del73] が古典的な出発点であり， Delsarte–Levenshtein [DL98] はアソシエーションスキームと符号理論の関係を概観しています． Krawtchouk多項式がHamming空間の符号・デザインの限界に現れることについては Levenshtein [Lev95] も代表的な文献です．↩