§1 はじめに 符号理論における基本定理の一つに，MacWilliams恒等式があります． E E E n = ∣ E ∣ n = \card{E} n = ∣ E ∣ F q \F_{q} F q C ≤ F q E C\leq \F_{q}^{E} C ≤ F q E
C ⊥ = { u ∈ F q E : u ⋅ c = 0 for all c ∈ C } C^{\perp}
=
\{ u \in \F_{q}^{E} : u \cdot c = 0 \text{ for all } c \in C \} C ⊥ = { u ∈ F q E : u ⋅ c = 0 for all c ∈ C } を考えます．ここで
u ⋅ c = ∑ e ∈ E u e c e u \cdot c = \sum_{e \in E} u_{e} c_{e} u ⋅ c = e ∈ E ∑ u e c e です．
まず，線形符号 C C C 重み多項式 (weight enumerator ) を
W C ( X , Y ) = ∑ c ∈ C X n − wt ( c ) Y wt ( c ) W_{C}(X,Y)
=
\sum_{c \in C} X^{n - \wt(c)} Y^{\wt(c)} W C ( X , Y ) = c ∈ C ∑ X n − wt ( c ) Y wt ( c ) で定めます． また，重み分布 (weight distribution ) を
A i ( C ) = ∣ { c ∈ C : wt ( c ) = i } ∣ ( 0 ≤ i ≤ n ) A_{i}(C)
=
\card{\{ c \in C : \wt(c) = i\}}
\qquad
(0 \leq i\leq n) A i ( C ) = ∣ { c ∈ C : wt ( c ) = i } ∣ ( 0 ≤ i ≤ n ) と書きます． このとき
W C ( X , Y ) = ∑ i = 0 n A i ( C ) X n − i Y i W_{C}(X, Y)
=
\sum_{i = 0}^{n} A_{i}(C) X^{n - i} Y^{i} W C ( X , Y ) = i = 0 ∑ n A i ( C ) X n − i Y i です．
MacWilliams恒等式は，双対符号の重み多項式が，C C C
W C ⊥ ( X , Y ) = 1 ∣ C ∣ W C ( X + ( q − 1 ) Y , X − Y ) . W_{C^{\perp}}(X, Y)
=
\frac{1}{\card{C}}
W_{C}\bigl( X + (q - 1)Y, X - Y \bigr). W C ⊥ ( X , Y ) = ∣ C ∣ 1 W C ( X + ( q − 1 ) Y , X − Y ) . これがMacWilliams恒等式です．
この連載では，MacWilliams恒等式の証明を手掛かりに， 周辺分野・周辺概念への入門を試みます． そのため，本連載では以下のような読者を対象としています：
符号理論の初歩，具体的には
程度は既知であることを前提としています (MacWilliams恒等式の証明は知らなくても問題ありません)．
本稿は，第1回〜第4回を前提にしません． 途中で Krawtchouk 多項式，テンソル積，加法指標が現れますが， 本稿で必要な範囲はその都度説明します． 第4回を読んでいれば見通しはよくなりますが，未読でも読める構成にします．
この連載では，MacWilliams恒等式の証明手法を大きく次の五つの系統に分けて眺めます．
本稿では，このうち「直交多項式・アソシエーションスキーム系 」に着目します． Krawtchouk多項式を使って書けば，MacWilliams恒等式は
重み分布に対するKrawtchouk変換
として現れます． ここでいう Krawtchouk 変換とは，
( a i ) i = 0 n ⟼ ( ∑ i = 0 n a i K j ( i ) ) j = 0 n (a_{i})_{i=0}^{n}
\longmapsto
\left(
\sum_{i = 0}^{n} a_{i} \Kraw_{j}(i)
\right)_{j=0}^{n} ( a i ) i = 0 n ⟼ ( i = 0 ∑ n a i K j ( i ) ) j = 0 n の形の変換です． ここで添字の読み方を先に述べておきます． K i ( w ) \Kraw_{i}(w) K i ( w ) i i i w w w j j j i i i K j ( i ) \Kraw_{j}(i) K j ( i ) アソシエーションスキーム の言葉で説明します． 言い換えると，本稿の目標は，係数 K j ( i ) \Kraw_j(i) K j ( i ) アソシエーションスキーム ，特にHammingスキームとBose–Mesner代数に入門することです．
アソシエーションスキームは，有限集合上の二項関係をいくつかの種類に分け， その関係たちが十分に規則的に振る舞う状況を抽象化したものです． Hamming空間では，二つの語 x , y ∈ F q E x, y \in \F_{q}^{E} x , y ∈ F q E
dist ( x , y ) = 0 , 1 , … , n \dist(x, y) = 0, 1, \dots, n dist ( x , y ) = 0 , 1 , … , n のどれであるかによって分類します． ここで dist ( x , y ) = wt ( x − y ) \dist(x, y) = \wt(x - y) dist ( x , y ) = wt ( x − y )
今回の流れは次のようになります．
関係分割 → 隣接行列 → アソシエーションスキーム → Bose–Mesner代数 → 原始冪等元 → 内部分布・双対分布 → MacWilliams恒等式
アソシエーションスキーム的な符号理論の古典的な出発点は Delsarte [Del73] です． 距離分布，MacWilliams変換，線形計画法まで含めて， アソシエーションスキームと符号理論の関係を概観する文献としては Delsarte–Levenshtein [DL98] があります． アソシエーションスキームの体系的な文献としては Bannai–Ito [BI84] が標準的です． また，距離正則グラフとの関係も含めた詳しい解説として Brouwer–Cohen–Neumaier [BCN89] があります． 符号理論におけるMacWilliams恒等式とKrawtchouk多項式については MacWilliams–Sloane [MS77, Chapter 5] も古典的な標準文献です． 符号理論で使うアソシエーションスキームの基本事項については， Camion [Cam98] も有用です．
§2 有限集合上の関係を行列で見る アソシエーションスキームに入る前に，有限集合上の関係を行列で表す方法を見ます．
Ω \Omega Ω Ω \Omega Ω Ω × Ω \Omega\times \Omega Ω × Ω R ⊆ Ω × Ω R \subseteq \Omega \times \Omega R ⊆ Ω × Ω ( x , y ) ∈ R (x,y)\in R ( x , y ) ∈ R x x x y y y R R R
定義2.1．
有限集合 Ω \Omega Ω R ⊆ Ω × Ω R\subseteq \Omega\times \Omega R ⊆ Ω × Ω Ω \Omega Ω A R \mathsf{A}_R A R
( A R ) x , y = { 1 , ( x , y ) ∈ R , 0 , ( x , y ) ∉ R (\mathsf{A}_R)_{x,y}
=
\begin{cases}
1, & (x,y)\in R,\\
0, & (x,y)\notin R
\end{cases} ( A R ) x , y = { 1 , 0 , ( x , y ) ∈ R , ( x , y ) ∈ / R で定める． これを R R R 隣接行列 (adjacency matrix ) という．
この定義は，グラフの隣接行列の一般化です． 普通の単純グラフでは，二つの頂点が辺で結ばれているかどうかを 0 0 0 1 1 1 R R R
C Ω \C^{\Omega} C Ω Ω \Omega Ω Ω \Omega Ω x x x e x e_x e x A R \mathsf{A}_R A R C Ω \C^{\Omega} C Ω f : Ω → C f\colon \Omega\to\C f : Ω → C
( A R f ) ( x ) = ∑ y ∈ Ω ( x , y ) ∈ R f ( y ) (\mathsf{A}_R f)(x)
=
\sum_{\substack{y\in \Omega\\(x,y)\in R}} f(y) ( A R f ) ( x ) = y ∈ Ω ( x , y ) ∈ R ∑ f ( y ) です． つまり，A R \mathsf{A}_R A R x x x R R R y y y
例2.2（完全グラフの一座標関係）．
Ω = F q \Omega=\F_q Ω = F q
R 0 = { ( a , a ) : a ∈ F q } , R 1 = { ( a , b ) : a , b ∈ F q , a ≠ b } \begin{aligned}
R_{0} &= \{ (a, a) : a \in \F_{q} \},\\
R_{1} &= \{ (a, b) : a, b \in \F_{q},\, a \neq b\}
\end{aligned} R 0 R 1 = {( a , a ) : a ∈ F q } , = {( a , b ) : a , b ∈ F q , a = b } を考える． R 0 R_{0} R 0 I I I R 1 R_{1} R 1 J − I J - I J − I J J J 1 1 1 K q K_{q} K q
以下，I I I J J J 1 1 1 F q \F_{q} F q q × q q\times q q × q Ω = F q E \Omega=\F_{q}^{E} Ω = F q E I I I J J J Ω \Omega Ω q n × q n q^{n}\times q^{n} q n × q n
複数の関係を同時に扱うとき，重要なのはそれらが Ω × Ω \Omega\times \Omega Ω × Ω
定義2.3．
有限集合 Ω \Omega Ω R 0 , R 1 , … , R d ⊆ Ω × Ω R_{0}, R_{1}, \dots, R_{d} \subseteq \Omega \times \Omega R 0 , R 1 , … , R d ⊆ Ω × Ω Ω × Ω \Omega\times \Omega Ω × Ω 関係分割 であるとは，
Ω × Ω = R 0 ⊔ R 1 ⊔ ⋯ ⊔ R d \Omega\times \Omega=R_0\sqcup R_1\sqcup\cdots\sqcup R_d Ω × Ω = R 0 ⊔ R 1 ⊔ ⋯ ⊔ R d となることをいう．
関係分割は，任意の二点 x , y ∈ Ω x, y \in \Omega x , y ∈ Ω ( x , x ) (x, x) ( x , x ) R 0 R_{0} R 0
§3 アソシエーションスキーム 本稿では，最も基本的で符号理論に十分な対称アソシエーションスキーム を扱います． 一般には非対称なものもありますが，Hammingスキームは対称なので，まずはこの場合に限るのが見通しやすいです．
定義3.1．
有限集合 Ω \Omega Ω R 0 , R 1 , … , R d ⊆ Ω × Ω R_{0}, R_{1}, \dots, R_{d} \subseteq \Omega \times \Omega R 0 , R 1 , … , R d ⊆ Ω × Ω Ω × Ω \Omega\times \Omega Ω × Ω
Ω × Ω = R 0 ⊔ R 1 ⊔ ⋯ ⊔ R d \Omega \times \Omega = R_{0} \sqcup R_{1} \sqcup \dots \sqcup R_{d} Ω × Ω = R 0 ⊔ R 1 ⊔ ⋯ ⊔ R d が対称アソシエーションスキーム (symmetric association scheme ) であるとは， 次の条件を満たすことをいう：
R 0 = { ( x , x ) : x ∈ Ω } R_{0} = \{ (x, x) : x \in \Omega \} R 0 = {( x , x ) : x ∈ Ω }
各 i i i ( x , y ) ∈ R i (x, y) \in R_{i} ( x , y ) ∈ R i ( y , x ) ∈ R i (y, x) \in R_{i} ( y , x ) ∈ R i
任意の 0 ≤ i , j , k ≤ d 0 \leq i, j ,k \leq d 0 ≤ i , j , k ≤ d ( x , y ) ∈ R k (x, y) \in R_{k} ( x , y ) ∈ R k x , y ∈ Ω x, y \in \Omega x , y ∈ Ω
∣ { z ∈ Ω : ( x , z ) ∈ R i , ( z , y ) ∈ R j } ∣ \card{\{ z \in \Omega : (x, z) \in R_{i},\ (z, y) \in R_{j} \}} ∣ { z ∈ Ω : ( x , z ) ∈ R i , ( z , y ) ∈ R j } ∣ が x x x y y y i i i j j j k k k
各 R k R_{k} R k (A3) 任意の 0 ≤ i , j , k ≤ d 0 \leq i, j ,k \leq d 0 ≤ i , j , k ≤ d ( x , y ) ∈ R k (x, y) \in R_{k} ( x , y ) ∈ R k x , y ∈ Ω x, y \in \Omega x , y ∈ Ω
∣ { z ∈ Ω : ( x , z ) ∈ R i , ( z , y ) ∈ R j } ∣ \card{\{ z \in \Omega : (x, z) \in R_{i},\ (z, y) \in R_{j} \}} ∣ { z ∈ Ω : ( x , z ) ∈ R i , ( z , y ) ∈ R j } ∣ が x x x y y y i i i j j j k k k ( x , y ) ∈ R k (x, y)\in R_{k} ( x , y ) ∈ R k
条件 ((A3) 任意の 0 ≤ i , j , k ≤ d 0 \leq i, j ,k \leq d 0 ≤ i , j , k ≤ d ( x , y ) ∈ R k (x, y) \in R_{k} ( x , y ) ∈ R k x , y ∈ Ω x, y \in \Omega x , y ∈ Ω
∣ { z ∈ Ω : ( x , z ) ∈ R i , ( z , y ) ∈ R j } ∣ \card{\{ z \in \Omega : (x, z) \in R_{i},\ (z, y) \in R_{j} \}} ∣ { z ∈ Ω : ( x , z ) ∈ R i , ( z , y ) ∈ R j } ∣ が x x x y y y i i i j j j k k k p i j k p_{ij}^{k} p ij k 交叉数 (intersection number ) と呼びます．
この定義の意味を言葉で言うと，次のようになります． 二点 x x x y y y R k R_{k} R k x x x R i R_{i} R i y y y R j R_{j} R j z z z x x x y y y i i i j j j k k k
隣接行列で書くと，この条件はとても自然に見えます． R i R_{i} R i A i ≔ A R i \mathsf{A}_{i} \coloneqq \mathsf{A}_{R_{i}} A i : = A R i A i A j \mathsf{A}_{i}\mathsf{A}_{j} A i A j ( x , y ) (x, y) ( x , y )
( A i A j ) x , y = ∑ z ∈ Ω ( A i ) x , z ( A j ) z , y (\mathsf{A}_i\mathsf{A}_j)_{x,y}
=
\sum_{z\in \Omega}(\mathsf{A}_i)_{x,z}(\mathsf{A}_j)_{z,y} ( A i A j ) x , y = z ∈ Ω ∑ ( A i ) x , z ( A j ) z , y です．これは，( x , z ) ∈ R i (x, z) \in R_{i} ( x , z ) ∈ R i ( z , y ) ∈ R j (z, y) \in R_{j} ( z , y ) ∈ R j z z z
定理3.2．
対称アソシエーションスキームの隣接行列は
A i A j = ∑ k = 0 d p i j k A k \mathsf{A}_{i} \mathsf{A}_{j}
=
\sum_{k=0}^{d}p_{ij}^{k}\mathsf{A}_{k} A i A j = k = 0 ∑ d p ij k A k を満たす．
証明 両辺の ( x , y ) (x,y) ( x , y ) ( x , y ) ∈ R k (x,y)\in R_{k} ( x , y ) ∈ R k ( x , y ) (x,y) ( x , y ) ( x , z ) ∈ R i (x,z)\in R_{i} ( x , z ) ∈ R i ( z , y ) ∈ R j (z,y)\in R_{j} ( z , y ) ∈ R j z z z p i j k p_{ij}^{k} p ij k ( x , y ) (x,y) ( x , y ) ( x , y ) (x,y) ( x , y ) R k R_{k} R k
∑ ℓ = 0 d p i j ℓ ( A ℓ ) x , y = p i j k \sum_{\ell=0}^{d}p_{ij}^{\ell}(\mathsf{A}_{\ell})_{x,y}
=
p_{ij}^{k} ℓ = 0 ∑ d p ij ℓ ( A ℓ ) x , y = p ij k である．よって両辺の成分は一致する．
証明終わり □
つまり，交叉数条件は「関係 R i R_i R i R j R_j R j R 0 , … , R d R_0,\dots,R_d R 0 , … , R d
また，関係が Ω × Ω \Omega \times \Omega Ω × Ω
A 0 + A 1 + ⋯ + A d = J \mathsf{A}_{0} + \mathsf{A}_{1} + \dots + \mathsf{A}_{d} = J A 0 + A 1 + ⋯ + A d = J です．ここで J J J 1 1 1 R 0 R_0 R 0 A 0 = I \mathsf{A}_{0} = I A 0 = I
§4 Bose–Mesner代数 アソシエーションスキームの隣接行列たちは，行列の積で閉じています． そこで，これらの行列が張るベクトル空間を考えます．
定義4.1．
対称アソシエーションスキーム ( Ω , { R i } i = 0 d ) (\Omega, \{R_{i} \}_{i = 0}^{d}) ( Ω , { R i } i = 0 d ) A 0 , … , A d \mathsf{A}_{0}, \dots, \mathsf{A}_{d} A 0 , … , A d
A = Span C { A 0 , A 1 , … , A d } ⊆ Mat Ω ( C ) \mathcal{A}
=
\Span_{\C}\{\mathsf{A}_0,\mathsf{A}_1,\dots,\mathsf{A}_d\}
\subseteq
\Mat_{\Omega}(\C) A = Span C { A 0 , A 1 , … , A d } ⊆ Mat Ω ( C ) を，このスキームのBose–Mesner代数 (Bose–Mesner algebra ) という．
定理 3.2 対称アソシエーションスキームの隣接行列は
A i A j = ∑ k = 0 d p i j k A k \mathsf{A}_{i} \mathsf{A}_{j}
=
\sum_{k=0}^{d}p_{ij}^{k}\mathsf{A}_{k} A i A j = k = 0 ∑ d p ij k A k を満たす． A \mathcal{A} A A 0 = I \mathsf{A}_0=I A 0 = I R 0 , … , R d R_0,\dots,R_d R 0 , … , R d Ω × Ω \Omega\times \Omega Ω × Ω A 0 , … , A d \mathsf{A}_0,\dots,\mathsf{A}_d A 0 , … , A d 1 1 1
c 0 A 0 + ⋯ + c d A d = 0 c_{0} \mathsf{A}_{0} + \dots + c_{d}\mathsf{A}_{d} = 0 c 0 A 0 + ⋯ + c d A d = 0 なら，( x , y ) ∈ R k (x, y) \in R_{k} ( x , y ) ∈ R k c k = 0 c_{k} = 0 c k = 0 A 0 , … , A d \mathsf{A}_{0}, \dots, \mathsf{A}_{d} A 0 , … , A d dim C A = d + 1 \dim_{\C} \mathcal{A} = d + 1 dim C A = d + 1 A i \mathsf{A}_i A i 定理 3.2 対称アソシエーションスキームの隣接行列は
A i A j = ∑ k = 0 d p i j k A k \mathsf{A}_{i} \mathsf{A}_{j}
=
\sum_{k=0}^{d}p_{ij}^{k}\mathsf{A}_{k} A i A j = k = 0 ∑ d p ij k A k を満たす．
A i A j = ∑ k = 0 d p i j k A k \mathsf{A}_i\mathsf{A}_j
=
\sum_{k=0}^{d}p_{ij}^{k}\mathsf{A}_k A i A j = k = 0 ∑ d p ij k A k と書け，右辺が対称行列の線形結合だからです． 実際，
A i A j = ( A i A j ) T = A j T A i T = A j A i \mathsf{A}_i\mathsf{A}_j
=
(\mathsf{A}_i\mathsf{A}_j)^T
=
\mathsf{A}_j^T\mathsf{A}_i^T
=
\mathsf{A}_j\mathsf{A}_i A i A j = ( A i A j ) T = A j T A i T = A j A i となります． したがって，A \mathcal{A} A A 0 , … , A d \mathsf{A}_{0}, \dots, \mathsf{A}_{d} A 0 , … , A d
定理4.2．
対称アソシエーションスキームのBose–Mesner代数 A \mathcal{A} A E 0 , E 1 , … , E d ∈ A \mathsf{E}_{0}, \mathsf{E}_{1}, \dots, \mathsf{E}_{d} \in \mathcal{A} E 0 , E 1 , … , E d ∈ A
E r E s = 0 \mathsf{E}_{r} \mathsf{E}_{s} = 0 E r E s = 0 r ≠ s r \neq s r = s
E r 2 = E r \mathsf{E}_{r}^{2} = \mathsf{E}_{r} E r 2 = E r
E 0 + E 1 + ⋯ + E d = I \mathsf{E}_{0} + \mathsf{E}_{1} + \dots + \mathsf{E}_{d} = I E 0 + E 1 + ⋯ + E d = I
E 0 , E 1 , … , E d \mathsf{E}_{0}, \mathsf{E}_{1}, \dots, \mathsf{E}_{d} E 0 , E 1 , … , E d A \mathcal{A} A
各 A i \mathsf{A}_{i} A i E r \mathsf{E}_{r} E r
各 E r \mathsf{E}_{r} E r A \mathcal{A} A
これらの E r \mathsf{E}_{r} E r 原始冪等元 (primitive idempotents ) という．
証明 上で見たように，A 0 , … , A d \mathsf{A}_{0}, \dots, \mathsf{A}_{d} A 0 , … , A d C Ω \C^{\Omega} C Ω
共通固有値の組をすべて集めた集合を Λ \Lambda Λ λ ∈ Λ \lambda \in \Lambda λ ∈ Λ
λ = ( λ 0 , λ 1 , … , λ d ) ∈ C d + 1 \lambda = (\lambda_{0}, \lambda_{1}, \dots, \lambda_{d}) \in \C^{d+1} λ = ( λ 0 , λ 1 , … , λ d ) ∈ C d + 1 という形の組であり，対応する共通固有空間
W λ = { v ∈ C Ω : A i v = λ i v for all 0 ≤ i ≤ d } W_{\lambda}
=
\{ v \in \C^{\Omega}:
\mathsf{A}_{i} v = \lambda_{i} v
\text{ for all } 0 \leq i \leq d\} W λ = { v ∈ C Ω : A i v = λ i v for all 0 ≤ i ≤ d } が 0 0 0
C Ω = ⨁ λ ∈ Λ W λ \C^{\Omega}
=
\bigoplus_{\lambda\in\Lambda} W_{\lambda} C Ω = λ ∈ Λ ⨁ W λ という直交直和分解が得られる．
各 λ ∈ Λ \lambda \in \Lambda λ ∈ Λ W λ W_{\lambda} W λ F λ \mathsf{F}_{\lambda} F λ
射影の基本性質 直交直和分解から，
F λ F μ = 0 ( λ ≠ μ ) , F λ 2 = F λ , ∑ λ ∈ Λ F λ = I \mathsf{F}_{\lambda}\mathsf{F}_{\mu} = 0
\quad(\lambda \neq \mu),
\qquad
\mathsf{F}_{\lambda}^{2} = \mathsf{F}_{\lambda},
\qquad
\sum_{\lambda \in \Lambda} \mathsf{F}_{\lambda} = I F λ F μ = 0 ( λ = μ ) , F λ 2 = F λ , λ ∈ Λ ∑ F λ = I が成り立つ． また，各 A i \mathsf{A}_{i} A i W λ W_{\lambda} W λ λ i \lambda_{i} λ i
A i = ∑ λ ∈ Λ λ i F λ \mathsf{A}_{i}
=
\sum_{\lambda \in \Lambda} \lambda_{i} \mathsf{F}_{\lambda} A i = λ ∈ Λ ∑ λ i F λ と書ける．
次に，各 F λ \mathsf{F}_{\lambda} F λ A \mathcal{A} A
F λ ∈ A \mathsf{F}_{\lambda} \in \mathcal{A} F λ ∈ A λ ∈ Λ \lambda \in \Lambda λ ∈ Λ μ ∈ Λ \mu \in \Lambda μ ∈ Λ μ ≠ λ \mu \neq \lambda μ = λ i = i ( μ ) i = i(\mu) i = i ( μ ) λ i ( μ ) ≠ μ i ( μ ) \lambda_{i(\mu)} \neq \mu_{i(\mu)} λ i ( μ ) = μ i ( μ )
p λ ( X 0 , … , X d ) = ∏ μ ∈ Λ μ ≠ λ X i ( μ ) − μ i ( μ ) λ i ( μ ) − μ i ( μ ) p_\lambda(X_{0}, \dots, X_{d})
=
\prod_{\substack{\mu \in \Lambda \\ \mu \neq \lambda}}
\frac{X_{i(\mu)}-\mu_{i(\mu)}}{\lambda_{i(\mu)}-\mu_{i(\mu)}} p λ ( X 0 , … , X d ) = μ ∈ Λ μ = λ ∏ λ i ( μ ) − μ i ( μ ) X i ( μ ) − μ i ( μ ) を考える．
この多項式を，可換な行列 A 0 , … , A d \mathsf{A}_{0}, \dots, \mathsf{A}_{d} A 0 , … , A d W λ W_{\lambda} W λ A i \mathsf{A}_{i} A i λ i \lambda_{i} λ i p λ ( A 0 , … , A d ) p_\lambda(\mathsf{A}_{0}, \dots, \mathsf{A}_{d}) p λ ( A 0 , … , A d ) W λ W_{\lambda} W λ 1 1 1 ν ≠ λ \nu \neq \lambda ν = λ W ν W_{\nu} W ν μ = ν \mu = \nu μ = ν 0 0 0 p λ ( A 0 , … , A d ) p_\lambda(\mathsf{A}_{0}, \dots, \mathsf{A}_{d}) p λ ( A 0 , … , A d ) W ν W_{\nu} W ν 0 0 0
よって
p λ ( A 0 , … , A d ) = F λ p_\lambda(\mathsf{A}_{0}, \dots, \mathsf{A}_{d})
=
\mathsf{F}_{\lambda} p λ ( A 0 , … , A d ) = F λ が成り立つ． 左辺は A 0 , … , A d \mathsf{A}_{0}, \dots, \mathsf{A}_{d} A 0 , … , A d A \mathcal{A} A F λ ∈ A \mathsf{F}_{\lambda} \in \mathcal{A} F λ ∈ A
続いて，Λ \Lambda Λ
共通固有値の組の個数は d + 1 d+1 d + 1 Λ \Lambda Λ m m m F λ \mathsf{F}_{\lambda} F λ A \mathcal{A} A
∑ λ ∈ Λ c λ F λ = 0 \sum_{\lambda \in \Lambda} c_{\lambda}\mathsf{F}_{\lambda} = 0 λ ∈ Λ ∑ c λ F λ = 0 として，両辺を W μ W_{\mu} W μ c μ = 0 c_{\mu} = 0 c μ = 0
m ≤ dim C A m \leq \dim_{\C} \mathcal{A} m ≤ dim C A である．
逆向きの不等式を示す． 任意の M ∈ A \mathsf{M} \in \mathcal{A} M ∈ A
M = c 0 A 0 + ⋯ + c d A d \mathsf{M}
=
c_{0}\mathsf{A}_{0} + \dots + c_{d}\mathsf{A}_{d} M = c 0 A 0 + ⋯ + c d A d の形で表せる． このとき，W λ W_{\lambda} W λ M \mathsf{M} M c 0 λ 0 + ⋯ + c d λ d c_{0}\lambda_{0} + \dots + c_{d}\lambda_{d} c 0 λ 0 + ⋯ + c d λ d M \mathsf{M} M W λ W_{\lambda} W λ
そこで，写像 Φ : A → C Λ \Phi \colon \mathcal{A} \to \C^{\Lambda} Φ : A → C Λ
Φ ( M ) ≔ ( M が W λ 上で持つ固有値 ) λ ∈ Λ \Phi(\mathsf{M})
\coloneqq
\bigl(
\text{$\mathsf{M}$ が $W_\lambda$ 上で持つ固有値}
\bigr)_{\lambda\in\Lambda} Φ ( M ) : = ( M が W λ 上で持つ固有値 ) λ ∈ Λ で定める． もし Φ ( M ) = 0 \Phi(\mathsf{M}) = 0 Φ ( M ) = 0 M \mathsf{M} M W λ W_{\lambda} W λ 0 0 0
C Ω = ⨁ λ ∈ Λ W λ \C^{\Omega}
=
\bigoplus_{\lambda \in \Lambda} W_{\lambda} C Ω = λ ∈ Λ ⨁ W λ より，これは M \mathsf{M} M Φ \Phi Φ
dim C A ≤ m \dim_{\C} \mathcal{A} \leq m dim C A ≤ m である．
以上より
m = dim C A m = \dim_{\C} \mathcal{A} m = dim C A である． すでに A 0 , … , A d \mathsf{A}_{0}, \dots, \mathsf{A}_{d} A 0 , … , A d
dim C A = d + 1 \dim_{\C} \mathcal{A} = d + 1 dim C A = d + 1 が成り立つ．以上により m = d + 1 m = d + 1 m = d + 1
したがって，Λ \Lambda Λ λ ( 0 ) , λ ( 1 ) , … , λ ( d ) \lambda^{(0)}, \lambda^{(1)}, \dots, \lambda^{(d)} λ ( 0 ) , λ ( 1 ) , … , λ ( d )
E r ≔ F λ ( r ) ( 0 ≤ r ≤ d ) \mathsf{E}_{r}
\coloneqq
\mathsf{F}_{\lambda^{(r)}}
\qquad
(0 \leq r \leq d) E r : = F λ ( r ) ( 0 ≤ r ≤ d ) と定める．
定理の列挙事項の確認 E r \mathsf{E}_{r} E r E r 2 = E r \mathsf{E}_{r}^{2} = \mathsf{E}_{r} E r 2 = E r
E r E s = 0 ( r ≠ s ) \mathsf{E}_{r} \mathsf{E}_{s} = 0
\qquad
(r \neq s) E r E s = 0 ( r = s ) である． 共通固有空間の直和が全空間なので，
E 0 + E 1 + ⋯ + E d = I \mathsf{E}_{0} + \mathsf{E}_{1} + \dots + \mathsf{E}_{d} = I E 0 + E 1 + ⋯ + E d = I も成り立つ．
さらに，E 0 , … , E d \mathsf{E}_{0}, \dots, \mathsf{E}_{d} E 0 , … , E d A \mathcal{A} A d + 1 d + 1 d + 1 dim C A = d + 1 \dim_{\C} \mathcal{A} = d + 1 dim C A = d + 1 A \mathcal{A} A
また，各 A i \mathsf{A}_{i} A i W λ ( r ) = E r ( C Ω ) W_{\lambda^{(r)}} = \mathsf{E}_{r}(\C^{\Omega}) W λ ( r ) = E r ( C Ω ) λ i ( r ) \lambda_{i}^{(r)} λ i ( r ) A i \mathsf{A}_{i} A i E r \mathsf{E}_{r} E r
最後に，これらの冪等元が A \mathcal{A} A
原始性 ある r r r E r = G + H \mathsf{E}_{r} = \mathsf{G} + \mathsf{H} E r = G + H A \mathcal{A} A G , H \mathsf{G},\mathsf{H} G , H
G 2 = G , H 2 = H , G H = 0 \mathsf{G}^{2} = \mathsf{G},
\qquad
\mathsf{H}^{2} = \mathsf{H},
\qquad
\mathsf{G}\mathsf{H} = 0 G 2 = G , H 2 = H , GH = 0 とする．
G \mathsf{G} G H \mathsf{H} H A \mathcal{A} A W λ ( s ) W_{\lambda^{(s)}} W λ ( s ) G \mathsf{G} G W λ ( s ) W_{\lambda^{(s)}} W λ ( s ) g s g_{s} g s H \mathsf{H} H W λ ( s ) W_{\lambda^{(s)}} W λ ( s ) h s h_{s} h s G \mathsf{G} G H \mathsf{H} H
g s 2 = g s , h s 2 = h s g_{s}^{2} = g_{s},
\qquad
h_{s}^{2} = h_{s} g s 2 = g s , h s 2 = h s である．したがって g s , h s ∈ { 0 , 1 } g_{s}, h_{s} \in \{ 0, 1 \} g s , h s ∈ { 0 , 1 }
一方，E r = G + H \mathsf{E}_{r} = \mathsf{G} + \mathsf{H} E r = G + H s ≠ r s \neq r s = r E r \mathsf{E}_{r} E r W λ ( s ) W_{\lambda^{(s)}} W λ ( s ) 0 0 0 g s + h s = 0 g_{s} + h_{s} = 0 g s + h s = 0 g s , h s ∈ { 0 , 1 } g_{s}, h_{s} \in \{ 0, 1 \} g s , h s ∈ { 0 , 1 }
g s = h s = 0 g_{s} = h_{s} = 0 g s = h s = 0 となる．
s = r s = r s = r E r \mathsf{E}_{r} E r W λ ( r ) W_{\lambda^{(r)}} W λ ( r ) 1 1 1 g r + h r = 1 g_{r} + h_{r} = 1 g r + h r = 1
( g r , h r ) = ( 1 , 0 ) または ( g r , h r ) = ( 0 , 1 ) (g_{r}, h_{r}) = (1, 0)
\quad\text{または}\quad
(g_{r}, h_{r}) = (0, 1) ( g r , h r ) = ( 1 , 0 ) または ( g r , h r ) = ( 0 , 1 ) である．
以上より，G \mathsf{G} G H \mathsf{H} H W λ ( r ) W_{\lambda^{(r)}} W λ ( r ) 1 1 1 0 0 0 E r \mathsf{E}_{r} E r 0 0 0
したがって
{ G , H } = { E r , 0 } \{ \mathsf{G}, \mathsf{H} \}
=
\{ \mathsf{E}_{r}, 0 \} { G , H } = { E r , 0 } である．つまり，E r \mathsf{E}_{r} E r A \mathcal{A} A
以上で定理が証明された．
証明終わり □
まず，この番号づけが自然であることを確認しておきます． 対称アソシエーションスキームでは，各隣接行列 A i \mathsf{A}_{i} A i x ∈ Ω x\in\Omega x ∈ Ω ( x , x ) ∈ R 0 (x,x)\in R_{0} ( x , x ) ∈ R 0 p i i 0 p_{ii}^{0} p ii 0
p i i 0 = ∣ { z ∈ Ω : ( x , z ) ∈ R i , ( z , x ) ∈ R i } ∣ p_{ii}^{0}
=
\card{\{z\in\Omega:(x,z)\in R_{i},\ (z,x)\in R_{i}\}} p ii 0 = ∣ { z ∈ Ω : ( x , z ) ∈ R i , ( z , x ) ∈ R i } ∣ です． 対称性より ( z , x ) ∈ R i (z,x)\in R_{i} ( z , x ) ∈ R i ( x , z ) ∈ R i (x,z)\in R_{i} ( x , z ) ∈ R i
p i i 0 = ∣ { z ∈ Ω : ( x , z ) ∈ R i } ∣ p_{ii}^{0}
=
\card{\{z\in\Omega:(x,z)\in R_{i}\}} p ii 0 = ∣ { z ∈ Ω : ( x , z ) ∈ R i } ∣ となります． 右辺は A i \mathsf{A}_{i} A i x x x x x x A i \mathsf{A}_{i} A i A i \mathsf{A}_{i} A i
以後，定数関数全体からなる一次元空間への射影を E 0 \mathsf{E}_{0} E 0
E 0 = 1 ∣ Ω ∣ J \mathsf{E}_{0} = \frac{1}{\card{\Omega}}J E 0 = ∣ Ω ∣ 1 J です． 実際，J J J 1 1 1 ∣ Ω ∣ − 1 J \card{\Omega}^{-1}J ∣ Ω ∣ − 1 J
J = A 0 + A 1 + ⋯ + A d J= \mathsf{A}_{0} + \mathsf{A}_{1} + \dots + \mathsf{A}_{d} J = A 0 + A 1 + ⋯ + A d であるため，この射影も A \mathcal A A
冪等元とは，二乗して自分自身に戻る元のことです． 一般の冪等行列は，ある直和分解に沿った射影を表しています． 今回の原始冪等元は実対称，つまり自己随伴でもあるので，標準内積に関する直交射影になっています． したがって，原始冪等元は，Bose–Mesner代数が見ている自然な固有空間への直交射影です． ここで「原始」とは，Bose–Mesner代数の中でこれ以上非自明な直交冪等元の和に分解できない，という意味です． 行列としてランク 1 1 1
隣接行列と原始冪等元は，どちらもBose–Mesner代数の基底になります． したがって，互いに線形結合で表せます． 具体的な係数は Hammingスキームの節で書き下します．
つまり，アソシエーションスキームでは，次の二つの基底を行き来します．
関係を表す基底：A 0 , … , A d \mathsf{A}_{0}, \dots, \mathsf{A}_{d} A 0 , … , A d E 0 , … , E d \mathsf{E}_{0}, \dots, \mathsf{E}_{d} E 0 , … , E d
MacWilliams恒等式のアソシエーションスキーム的証明では， この「関係側」と「固有空間側」の行き来が本質になります． 符号の重み分布は関係側で定義され，双対分布は固有空間側への射影で定義されます． 本節で扱ったBose–Mesner代数や原始冪等元の線形代数的な扱いについては， Godsil [God93] も参照しやすいです．
§5 Hammingスキーム ここから，符号理論に現れる最も重要なアソシエーションスキームであるHammingスキームを見ます．
座標集合 E E E n = ∣ E ∣ n = \card{E} n = ∣ E ∣ E j \mathsf{E}_j E j Ω ≔ F q E \Omega \coloneqq \F_{q}^{E} Ω : = F q E n n n q q q x , y ∈ Ω x, y \in \Omega x , y ∈ Ω
dist ( x , y ) ≔ wt ( x − y ) \dist(x, y) \coloneqq \wt(x - y) dist ( x , y ) : = wt ( x − y ) で定めます．
定義5.1．
0 ≤ i ≤ n 0\leq i\leq n 0 ≤ i ≤ n
R i ≔ { ( x , y ) ∈ Ω × Ω : dist ( x , y ) = i } R_{i}
\coloneqq
\{ (x, y) \in \Omega \times \Omega : \dist(x, y) = i \} R i : = {( x , y ) ∈ Ω × Ω : dist ( x , y ) = i } と定める． この関係分割から得られるアソシエーションスキームを Hammingスキーム (Hamming scheme ) と呼び，H ( n , q ) H(n, q) H ( n , q )
R i R_{i} R i A i \mathsf{A}_{i} A i A i \mathsf{A}_{i} A i i i i
定理5.2．
H ( n , q ) H(n,q) H ( n , q )
証明 R 0 R_{0} R 0 R i R_{i} R i x x x y y y 0 , 1 , … , n 0, 1, \dots, n 0 , 1 , … , n R 0 , … , R n R_{0}, \dots, R_{n} R 0 , … , R n Ω × Ω \Omega \times \Omega Ω × Ω R i R_{i} R i 0 ∈ F q E 0 \in \F_{q}^{E} 0 ∈ F q E i i i y y y dist ( 0 , y ) = i \dist(0, y) = i dist ( 0 , y ) = i
交叉数の条件を確認する． dist ( x , y ) = k \dist(x, y) = k dist ( x , y ) = k z ∈ Ω z\in \Omega z ∈ Ω
dist ( x , z ) = i , dist ( z , y ) = j \dist(x, z) = i,
\qquad
\dist(z, y) = j dist ( x , z ) = i , dist ( z , y ) = j を満たす個数を数えたい． dist ( x , y ) = k \dist(x, y) = k dist ( x , y ) = k x e = y e x_{e} = y_{e} x e = y e n − k n - k n − k x e ≠ y e x_{e} \neq y_{e} x e = y e k k k
各座標での寄与は，次の表にまとめられる． ここで Δ x \Delta_x Δ x Δ y \Delta_y Δ y dist ( x , z ) \dist(x, z) dist ( x , z ) dist ( z , y ) \dist(z, y) dist ( z , y )
したがって，s s s dist ( x , z ) \dist(x, z) dist ( x , z ) t t t dist ( z , y ) \dist(z, y) dist ( z , y ) x e = y e x_{e} = y_{e} x e = y e
1 + ( q − 1 ) s t 1 + (q - 1)st 1 + ( q − 1 ) s t であり，後三行から，x e ≠ y e x_e\neq y_e x e = y e
s + t + ( q − 2 ) s t s + t + (q - 2)st s + t + ( q − 2 ) s t である． 各座標での選択は独立なので，全体の個数はこれらの一座標母関数の積で与えられる． ここで s s s dist ( x , z ) \dist(x,z) dist ( x , z ) t t t dist ( z , y ) \dist(z,y) dist ( z , y ) dist ( x , z ) = i \dist(x,z)=i dist ( x , z ) = i dist ( z , y ) = j \dist(z,y)=j dist ( z , y ) = j z z z
[ s i t j ] ( 1 + ( q − 1 ) s t ) n − k ( s + t + ( q − 2 ) s t ) k \lbrack s^{i} t^{j} \rbrack
\bigl( 1 + (q - 1)st \bigr)^{n - k}
\bigl( s + t + (q - 2)st \bigr)^{k} [ s i t j ] ( 1 + ( q − 1 ) s t ) n − k ( s + t + ( q − 2 ) s t ) k と書ける． ここで [ s i t j ] \lbrack s^{i} t^{j} \rbrack [ s i t j ] s i t j s^{i} t^{j} s i t j q = 2 q = 2 q = 2 q − 2 = 0 q - 2 = 0 q − 2 = 0 x x x y y y n n n q q q i i i j j j k k k
証明終わり □
この証明では交叉数の明示公式は使いませんでした． 重要なのは，二点 x x x y y y k k k
A i \mathsf{A}_{i} A i i i i
v i = ( n i ) ( q − 1 ) i v_{i} = \binom{n}{i}(q-1)^{i} v i = ( i n ) ( q − 1 ) i です．この v i v_{i} v i R i R_{i} R i 分岐指数 (valency ) と呼びます． 距離 i i i ( n i ) \binom{n}{i} ( i n ) q − 1 q - 1 q − 1
§6 Hammingスキームの固有空間 HammingスキームのBose–Mesner代数を理解するには， 隣接行列 A 0 , … , A n \mathsf{A}_{0}, \dots, \mathsf{A}_{n} A 0 , … , A n
まず一座標から始めます． 一座標の関数空間を U = C F q U = \C^{\F_q} U = C F q U U U U 0 = C 1 U_{0} = \C\one U 0 = C 1 0 0 0
U 1 = { f ∈ U : ∑ a ∈ F q f ( a ) = 0 } U_{1} = \left\{ f \in U : \sum_{a \in \F_{q}} f(a) = 0 \right\} U 1 = ⎩ ⎨ ⎧ f ∈ U : a ∈ F q ∑ f ( a ) = 0 ⎭ ⎬ ⎫ とおきます． 標準内積に関して U = U 0 ⊕ U 1 U = U_{0} \oplus U_{1} U = U 0 ⊕ U 1
一座標で「異なる値へ移る」隣接行列を N = J − I N = J - I N = J − I K q K_{q} K q N N N U 0 U_{0} U 0 q − 1 q - 1 q − 1 U 1 U_{1} U 1 − 1 -1 − 1 q − 1 q - 1 q − 1 q − 1 q - 1 q − 1 f ∈ U 1 f \in U_{1} f ∈ U 1
( N f ) ( a ) = ∑ b ≠ a f ( b ) = ∑ b ∈ F q f ( b ) − f ( a ) = − f ( a ) (Nf)(a) = \sum_{b \neq a} f(b) = \sum_{b \in \F_{q}}f(b) - f(a) = -f(a) ( N f ) ( a ) = b = a ∑ f ( b ) = b ∈ F q ∑ f ( b ) − f ( a ) = − f ( a ) です．
本稿で使うテンソル積は，各座標の一変数関数を掛け合わせて多座標の関数を作る操作， および一座標の作用素を各座標に独立に作用させる操作だと思えば十分です． テンソル積の一般論は，この記事の理解には不要です．
多座標空間は
C Ω = C F q E ≅ ⨂ e ∈ E U \C^{\Omega}
=
\C^{\F_{q}^{E}}
\cong
\bigotimes_{e \in E} U C Ω = C F q E ≅ e ∈ E ⨂ U です． 各 e ∈ E e \in E e ∈ E f e ∈ U f_{e} \in U f e ∈ U ⨂ e ∈ E f e \bigotimes_{e \in E} f_{e} ⨂ e ∈ E f e
x = ( x e ) e ∈ E ⟼ ∏ e ∈ E f e ( x e ) x = (x_{e})_{e \in E}
\longmapsto
\prod_{e \in E} f_{e}(x_{e}) x = ( x e ) e ∈ E ⟼ e ∈ E ∏ f e ( x e ) という関数を表します． また，一座標作用素 T e : U → U T_{e} \colon U \to U T e : U → U ⨂ e ∈ E T e \bigotimes_{e \in E} T_{e} ⨂ e ∈ E T e T e T_{e} T e E = { 1 , 2 } E = \{ 1, 2 \} E = { 1 , 2 } f 1 ⊗ f 2 f_{1} \otimes f_{2} f 1 ⊗ f 2
( a , b ) ⟼ f 1 ( a ) f 2 ( b ) (a, b) \longmapsto f_{1}(a)f_{2}(b) ( a , b ) ⟼ f 1 ( a ) f 2 ( b ) という二変数関数を表します．また T 1 ⊗ T 2 T_{1} \otimes T_{2} T 1 ⊗ T 2
( T 1 ⊗ T 2 ) ( f 1 ⊗ f 2 ) = ( T 1 f 1 ) ⊗ ( T 2 f 2 ) (T_{1} \otimes T_{2})(f_{1} \otimes f_{2})
=
(T_{1} f_{1}) \otimes (T_{2} f_{2}) ( T 1 ⊗ T 2 ) ( f 1 ⊗ f 2 ) = ( T 1 f 1 ) ⊗ ( T 2 f 2 ) と作用するので，第一座標に T 1 T_{1} T 1 T 2 T_{2} T 2 E E E U = U 0 ⊕ U 1 U = U_{0} \oplus U_{1} U = U 0 ⊕ U 1
C Ω = ⨁ S ⊆ E ( ⨂ e ∈ S U 1 ⊗ ⨂ e ∉ S U 0 ) \C^{\Omega}
=
\bigoplus_{S\subseteq E}
\left(
\bigotimes_{e\in S}U_1
\otimes
\bigotimes_{e\notin S}U_0
\right) C Ω = S ⊆ E ⨁ e ∈ S ⨂ U 1 ⊗ e ∈ / S ⨂ U 0 という直交分解が得られます． ここで，S S S
定義6.1．
0 ≤ w ≤ n 0 \leq w \leq n 0 ≤ w ≤ n
V w = ⨁ S ⊆ E ∣ S ∣ = w ( ⨂ e ∈ S U 1 ⊗ ⨂ e ∉ S U 0 ) V_w
=
\bigoplus_{\substack{S\subseteq E\\ \card{S} = w}}
\left(
\bigotimes_{e\in S}U_1
\otimes
\bigotimes_{e\notin S}U_0
\right) V w = S ⊆ E ∣ S ∣ = w ⨁ e ∈ S ⨂ U 1 ⊗ e ∈ / S ⨂ U 0 と定める．
すると
C Ω = V 0 ⊕ V 1 ⊕ ⋯ ⊕ V n \C^{\Omega} = V_{0} \oplus V_{1} \oplus \dots \oplus V_{n} C Ω = V 0 ⊕ V 1 ⊕ ⋯ ⊕ V n です． 各 ∣ S ∣ = w \card{S}=w ∣ S ∣ = w ( dim U 1 ) w = ( q − 1 ) w (\dim U_{1})^{w} = (q - 1)^{w} ( dim U 1 ) w = ( q − 1 ) w S S S ( n w ) \binom{n}{w} ( w n )
dim V w = ( n w ) ( q − 1 ) w \dim V_{w} = \binom{n}{w}(q - 1)^{w} dim V w = ( w n ) ( q − 1 ) w です． 直感的には，V w V_{w} V w w w w
次に，距離行列 A j \mathsf{A}_j A j I I I N N N U = C F q U = \C^{\F_{q}} U = C F q A j \mathsf{A}_{j} A j C Ω = C F q E \C^{\Omega} = \C^{\F_{q}^{E}} C Ω = C F q E I I I N = J − I N = J - I N = J − I
∑ j = 0 n A j z j = ⨂ e ∈ E ( I + z N ) (6.1) \sum_{j=0}^{n}\mathsf{A}_{j} z^{j}
= \bigotimes_{e \in E}(I + zN)
\tag{6.1} j = 0 ∑ n A j z j = e ∈ E ⨂ ( I + z N ) ( 6.1 ) が成り立ちます． 右辺を展開すると，z j z^{j} z j j j j
定義6.2．
0 ≤ w ≤ n 0 \leq w \leq n 0 ≤ w ≤ n K 0 ( w ) , … , K n ( w ) \Kraw_{0}(w), \dots, \Kraw_{n}(w) K 0 ( w ) , … , K n ( w )
∑ j = 0 n K j ( w ) z j = ( 1 + ( q − 1 ) z ) n − w ( 1 − z ) w (6.2) \sum_{j=0}^{n}\Kraw_{j}(w)z^{j}
=
\bigl( 1 + (q - 1)z \bigr)^{n - w}(1 - z)^{w}
\tag{6.2} j = 0 ∑ n K j ( w ) z j = ( 1 + ( q − 1 ) z ) n − w ( 1 − z ) w ( 6.2 ) によって定める． これを，q q q
母関数を展開すると，
K j ( w ) = ∑ ℓ = 0 j ( − 1 ) ℓ ( q − 1 ) j − ℓ ( w ℓ ) ( n − w j − ℓ ) \Kraw_j(w)
=
\sum_{\ell=0}^{j}
(-1)^\ell
(q-1)^{j-\ell}
\binom{w}{\ell}
\binom{n-w}{j-\ell} K j ( w ) = ℓ = 0 ∑ j ( − 1 ) ℓ ( q − 1 ) j − ℓ ( ℓ w ) ( j − ℓ n − w ) となる． ここで二項係数は範囲外では 0 0 0
この定義は，Krawtchouk多項式を「母関数で定義した多項式」として導入しているようにも見えますが， ここでの意味は少し違います． 式 ∑ j = 0 n K j ( w ) z j = ( 1 + ( q − 1 ) z ) n − w ( 1 − z ) w (6.2) \sum_{j=0}^{n}\Kraw_{j}(w)z^{j}
=
\bigl( 1 + (q - 1)z \bigr)^{n - w}(1 - z)^{w}
\tag{6.2} j = 0 ∑ n K j ( w ) z j = ( 1 + ( q − 1 ) z ) n − w ( 1 − z ) w ( 6.2 )
定理6.3．
0 ≤ j , w ≤ n 0 \leq j, w \leq n 0 ≤ j , w ≤ n A j \mathsf{A}_{j} A j V w V_{w} V w K j ( w ) \Kraw_{j}(w) K j ( w )
証明 V w V_w V w w w w U 1 U_{1} U 1 n − w n - w n − w U 0 U_{0} U 0 N N N U 0 U_{0} U 0 q − 1 q - 1 q − 1 U 1 U_{1} U 1 − 1 -1 − 1 ∑ j A j z j \sum_{j} \mathsf{A}_{j} z^{j} ∑ j A j z j V w V_{w} V w
( 1 + ( q − 1 ) z ) n − w ( 1 − z ) w \bigl( 1 + (q - 1)z \bigr)^{n - w}(1 - z)^{w} ( 1 + ( q − 1 ) z ) n − w ( 1 − z ) w 倍として作用する． z j z^{j} z j A j \mathsf{A}_{j} A j K j ( w ) \Kraw_{j}(w) K j ( w )
証明終わり □
この定理により，Krawtchouk多項式は次のように解釈できます．
Krawtchouk多項式は，Hammingスキームの距離 j j j w w w V w V_{w} V w
先に述べたように，添字の役割をここで整理しておきます． A i \mathsf{A}_{i} A i i i i V w V_{w} V w E w \mathsf{E}_{w} E w w w w K i ( w ) \Kraw_{i}(w) K i ( w ) i i i A i \mathsf{A}_{i} A i w w w V w V_w V w
E j = 1 q n ∑ i = 0 n K j ( i ) A i \mathsf{E}_{j}
=
\frac{1}{q^{n}} \sum_{i=0}^{n} \Kraw_{j}(i) \mathsf{A}_{i} E j = q n 1 i = 0 ∑ n K j ( i ) A i と書くときは，j j j i i i
特に j = 1 j = 1 j = 1
K 1 ( w ) = ( q − 1 ) ( n − w ) − w = ( q − 1 ) n − q w \Kraw_{1}(w) = (q - 1)(n - w) - w = (q - 1)n - qw K 1 ( w ) = ( q − 1 ) ( n − w ) − w = ( q − 1 ) n − q w であり，w = 0 , 1 , … , n w = 0, 1, \dots, n w = 0 , 1 , … , n V 0 , V 1 , … , V n V_{0}, V_{1}, \dots, V_{n} V 0 , V 1 , … , V n A 1 \mathsf{A}_{1} A 1 A 1 \mathsf{A}_{1} A 1 V 0 , … , V n V_{0}, \dots, V_{n} V 0 , … , V n
E w = ∏ u = 0 u ≠ w n A 1 − K 1 ( u ) I K 1 ( w ) − K 1 ( u ) \mathsf{E}_{w}
=
\prod_{\substack{u = 0 \\ u \neq w}}^{n}
\frac{\mathsf{A}_{1} - \Kraw_{1}(u)I}{\Kraw_{1}(w)-\Kraw_{1}(u)} E w = u = 0 u = w ∏ n K 1 ( w ) − K 1 ( u ) A 1 − K 1 ( u ) I と書けます． これは V w V_{w} V w A 1 \mathsf{A}_{1} A 1 E w \mathsf{E}_{w} E w
この見方が，アソシエーションスキーム的な見方の核心です． 多項式が先にあるのではなく，距離関係から作った行列代数を同時対角化すると， その固有値としてKrawtchouk多項式が現れます．
§7 原始冪等元を具体的に書く V w V_{w} V w E w \mathsf{E}_{w} E w E 0 , E 1 , … , E n \mathsf{E}_{0}, \mathsf{E}_{1}, \dots, \mathsf{E}_{n} E 0 , E 1 , … , E n
E r E s = δ r , s E r , ∑ r = 0 n E r = I \mathsf{E}_{r}\mathsf{E}_{s} = \delta_{r, s} \mathsf{E}_{r},
\qquad
\sum_{r=0}^{n}\mathsf{E}_{r} = I E r E s = δ r , s E r , r = 0 ∑ n E r = I であり，各 A j \mathsf{A}_{j} A j E w \mathsf{E}_{w} E w K j ( w ) \Kraw_{j}(w) K j ( w ) V w V_w V w
dim E w ( C Ω ) = dim V w = ( n w ) ( q − 1 ) w \dim \mathsf{E}_w(\C^{\Omega})
= \dim V_{w}
= \binom{n}{w}(q-1)^{w} dim E w ( C Ω ) = dim V w = ( w n ) ( q − 1 ) w です． したがって，Hammingスキームの原始冪等元も一般にはランク 1 1 1
この射影を，隣接行列 A i \mathsf{A}_i A i U 0 U_{0} U 0 Π 0 \Pi_{0} Π 0 U 1 U_{1} U 1 Π 1 \Pi_{1} Π 1
Π 0 = 1 q J , Π 1 = I − 1 q J \Pi_{0} = \frac{1}{q}J,
\qquad
\Pi_{1} = I - \frac{1}{q}J Π 0 = q 1 J , Π 1 = I − q 1 J です． 成分で書くと，a , b ∈ F q a, b \in \F_{q} a , b ∈ F q
Π 0 ( a , b ) = 1 q Π 1 ( a , b ) = { q − 1 q , a = b , − 1 q , a ≠ b \Pi_{0}(a, b) = \frac{1}{q}
\qquad
\Pi_{1}(a,b) =
\begin{cases}
\dfrac{q-1}{q}, & a = b,\\[4pt]
-\dfrac{1}{q}, & a \neq b
\end{cases} Π 0 ( a , b ) = q 1 Π 1 ( a , b ) = ⎩ ⎨ ⎧ q q − 1 , − q 1 , a = b , a = b です．
S ⊆ E S\subseteq E S ⊆ E S S S Π 1 \Pi_1 Π 1 Π 0 \Pi_0 Π 0 ∣ S ∣ = w \card{S} = w ∣ S ∣ = w E w \mathsf{E}_{w} E w
定理7.1．
Hammingスキーム H ( n , q ) H(n,q) H ( n , q )
E j = 1 q n ∑ i = 0 n K j ( i ) A i (7.1) \mathsf{E}_j
=
\frac{1}{q^n}
\sum_{i=0}^{n}\Kraw_j(i)\mathsf{A}_i
\tag{7.1} E j = q n 1 i = 0 ∑ n K j ( i ) A i ( 7.1 ) と書ける．
証明 x , y ∈ Ω = F q E x,y\in \Omega=\F_q^E x , y ∈ Ω = F q E dist ( x , y ) = i \dist(x,y)=i dist ( x , y ) = i E j \mathsf{E}_j E j ( x , y ) (x,y) ( x , y ) E j \mathsf{E}_j E j ∣ S ∣ = j \card{S}=j ∣ S ∣ = j S ⊆ E S\subseteq E S ⊆ E S S S Π 1 \Pi_1 Π 1 Π 0 \Pi_0 Π 0
母関数としてまとめると，
∑ j = 0 n q n ( E j ) x , y z j = ∏ e ∈ E ( q Π 0 ( x e , y e ) + q Π 1 ( x e , y e ) z ) . \begin{aligned}
\sum_{j=0}^{n} q^n(\mathsf{E}_j)_{x,y}z^j
&=
\prod_{e\in E}
\left(q\Pi_0(x_e,y_e)+q\Pi_1(x_e,y_e)z\right).
\end{aligned} j = 0 ∑ n q n ( E j ) x , y z j = e ∈ E ∏ ( q Π 0 ( x e , y e ) + q Π 1 ( x e , y e ) z ) . もし x e = y e x_e=y_e x e = y e
q Π 0 ( x e , y e ) = 1 , q Π 1 ( x e , y e ) = q − 1 q\Pi_0(x_e,y_e)=1,
\qquad
q\Pi_1(x_e,y_e)=q-1 q Π 0 ( x e , y e ) = 1 , q Π 1 ( x e , y e ) = q − 1 である． もし x e ≠ y e x_e\neq y_e x e = y e
q Π 0 ( x e , y e ) = 1 , q Π 1 ( x e , y e ) = − 1 q\Pi_0(x_e,y_e)=1,
\qquad
q\Pi_1(x_e,y_e)=-1 q Π 0 ( x e , y e ) = 1 , q Π 1 ( x e , y e ) = − 1 である． x x x y y y i i i n − i n-i n − i
∑ j = 0 n q n ( E j ) x , y z j = ( 1 + ( q − 1 ) z ) n − i ( 1 − z ) i = ∑ j = 0 n K j ( i ) z j . \sum_{j=0}^{n} q^n(\mathsf{E}_j)_{x,y}z^j
=
\bigl(1+(q-1)z\bigr)^{n-i}(1-z)^i
=
\sum_{j=0}^{n}\Kraw_j(i)z^j. j = 0 ∑ n q n ( E j ) x , y z j = ( 1 + ( q − 1 ) z ) n − i ( 1 − z ) i = j = 0 ∑ n K j ( i ) z j . よって
( E j ) x , y = 1 q n K j ( i ) . (\mathsf{E}_j)_{x,y}
=
\frac{1}{q^n}\Kraw_j(i). ( E j ) x , y = q n 1 K j ( i ) . これは，距離が i i i q − n K j ( i ) q^{-n}\Kraw_j(i) q − n K j ( i )
1 q n ∑ i = 0 n K j ( i ) A i \frac{1}{q^n}\sum_{i=0}^{n}\Kraw_j(i)\mathsf{A}_i q n 1 i = 0 ∑ n K j ( i ) A i は，A i \mathsf{A}_i A i i i i 1 1 1 i i i q − n K j ( i ) q^{-n}\Kraw_j(i) q − n K j ( i )
E j = 1 q n ∑ i = 0 n K j ( i ) A i \mathsf{E}_j
=
\frac{1}{q^n}\sum_{i=0}^{n}\Kraw_j(i)\mathsf{A}_i E j = q n 1 i = 0 ∑ n K j ( i ) A i となる．成分がすべて一致するので，行列として等しい．
証明終わり □
この式は非常に重要です． 左辺は固有空間への射影です． 右辺は距離関係を表す隣接行列の線形結合です． つまり，Krawtchouk多項式は，
関係側の基底 A i \mathsf{A}_i A i E j \mathsf{E}_{j} E j
になっています．
ここで一般論との対応を整理しておきます． 一般のアソシエーションスキームでは
A i = ∑ r = 0 d P r ( i ) E r , E r = 1 ∣ Ω ∣ ∑ i = 0 d Q r ( i ) A i \mathsf{A}_i
=
\sum_{r=0}^{d}P_r(i)\mathsf{E}_r,
\qquad
\mathsf{E}_r
=
\frac{1}{\card{\Omega}}
\sum_{i=0}^{d}Q_r(i)\mathsf{A}_i A i = r = 0 ∑ d P r ( i ) E r , E r = ∣ Ω ∣ 1 i = 0 ∑ d Q r ( i ) A i と書くときの係数を，それぞれ第一固有行列 P P P Q Q Q
A i = ∑ w = 0 n K i ( w ) E w , E j = 1 q n ∑ i = 0 n K j ( i ) A i \mathsf{A}_i=\sum_{w=0}^{n}\Kraw_i(w)\mathsf{E}_w,
\qquad
\mathsf{E}_j=\frac{1}{q^n}\sum_{i=0}^{n}\Kraw_j(i)\mathsf{A}_i A i = w = 0 ∑ n K i ( w ) E w , E j = q n 1 i = 0 ∑ n K j ( i ) A i なので，P w ( i ) = K i ( w ) P_w(i)=\Kraw_i(w) P w ( i ) = K i ( w ) Q j ( i ) = K j ( i ) Q_j(i)=\Kraw_j(i) Q j ( i ) = K j ( i )
Hammingスキームでは，この二方向の基底変換に同じ型のKrawtchouk多項式が現れます． ただし，一般に K j ( i ) = K i ( j ) \Kraw_{j}(i) = \Kraw_{i}(j) K j ( i ) = K i ( j ) v i = ( n i ) ( q − 1 ) i v_{i} = \binom{n}{i}(q-1)^{i} v i = ( i n ) ( q − 1 ) i
v i K j ( i ) = v j K i ( j ) v_{i} \Kraw_{j}(i) = v_{j}\Kraw_{i}(j) v i K j ( i ) = v j K i ( j ) という重み付き対称性が成り立ちます．
§8 内部分布：符号を関係側から見る ここから符号に戻ります． アソシエーションスキームでは，有限集合 Ω \Omega Ω D ⊆ Ω D\subseteq \Omega D ⊆ Ω [Del73 ; Cam98 ] ．
ここで似た記号を一度整理しておきます． A i \mathsf{A}_i A i i i i A i ( C ) A_i(C) A i ( C ) C C C i i i a i ( D ) a_i(D) a i ( D ) D D D
定義8.1．
部分集合 D ⊆ Ω D\subseteq \Omega D ⊆ Ω D D D 特性ベクトル を
1 D = ∑ x ∈ D e x ∈ C Ω \one_D
=
\sum_{x\in D}e_x
\in \C^{\Omega} 1 D = x ∈ D ∑ e x ∈ C Ω で定める．
標準内積を
⟨ f , g ⟩ = ∑ x ∈ Ω f ( x ) g ( x ) ‾ \langle f,g\rangle
=
\sum_{x\in \Omega}f(x)\overline{g(x)} ⟨ f , g ⟩ = x ∈ Ω ∑ f ( x ) g ( x ) とします． 隣接行列 A i \mathsf{A}_i A i D D D i i i ⟨ A i 1 D , 1 D ⟩ \langle \mathsf{A}_{i} \one_{D}, \one_{D} \rangle ⟨ A i 1 D , 1 D ⟩
定義8.2．
D ⊆ Ω D\subseteq \Omega D ⊆ Ω D D D 内部分布 (inner distribution ) を
a i ( D ) = 1 ∣ D ∣ ⟨ A i 1 D , 1 D ⟩ ( 0 ≤ i ≤ n ) a_i(D)
=
\frac{1}{\card{D}}
\langle \mathsf{A}_i\one_D,\one_D\rangle
\qquad
(0\leq i\leq n) a i ( D ) = ∣ D ∣ 1 ⟨ A i 1 D , 1 D ⟩ ( 0 ≤ i ≤ n ) で定める．
この正規化では，a 0 ( D ) = 1 a_0(D)=1 a 0 ( D ) = 1 A 0 = I \mathsf{A}_0=I A 0 = I
a 0 ( D ) = 1 ∣ D ∣ ⟨ 1 D , 1 D ⟩ = 1 a_{0}(D) = \frac{1}{\card{D}} \langle \one_{D}, \one_{D} \rangle = 1 a 0 ( D ) = ∣ D ∣ 1 ⟨ 1 D , 1 D ⟩ = 1 です． また，
∑ i = 0 n a i ( D ) = 1 ∣ D ∣ ⟨ ∑ i = 0 n A i 1 D , 1 D ⟩ = 1 ∣ D ∣ ⟨ J 1 D , 1 D ⟩ = ∣ D ∣ \sum_{i=0}^{n}a_i(D)
=
\frac{1}{\card{D}}
\left\langle
\sum_{i=0}^{n}\mathsf{A}_i\one_D,\one_D
\right\rangle
=
\frac{1}{\card{D}}\langle J\one_D,\one_D\rangle
=
\card{D} i = 0 ∑ n a i ( D ) = ∣ D ∣ 1 ⟨ i = 0 ∑ n A i 1 D , 1 D ⟩ = ∣ D ∣ 1 ⟨ J 1 D , 1 D ⟩ = ∣ D ∣ なので，この正規化では確率分布ではありません． a i ( D ) a_i(D) a i ( D ) D D D R i R_i R i D D D i i i D D D
線形符号の場合，内部分布は通常の重み分布と一致します．
定理8.3．
C ≤ F q E C \leq \F_{q}^{E} C ≤ F q E A i ( C ) = ∣ { c ∈ C : wt ( c ) = i } ∣ A_{i}(C) = \card{\{ c \in C : \wt(c) = i \}} A i ( C ) = ∣ { c ∈ C : wt ( c ) = i } ∣ a i ( C ) = A i ( C ) a_{i}(C) = A_{i}(C) a i ( C ) = A i ( C )
証明 ⟨ A i 1 C , 1 C ⟩ \langle \mathsf{A}_i\one_C,\one_C\rangle ⟨ A i 1 C , 1 C ⟩
x , y ∈ C , dist ( x , y ) = i x,y\in C,
\qquad
\dist(x,y)=i x , y ∈ C , dist ( x , y ) = i を満たす順序付きペア ( x , y ) (x,y) ( x , y ) C C C y − x y-x y − x C C C dist ( x , y ) = wt ( y − x ) \dist(x,y)=\wt(y-x) dist ( x , y ) = wt ( y − x )
重み i i i d ∈ C d\in C d ∈ C y − x = d y-x=d y − x = d ( x , y ) ∈ C 2 (x,y)\in C^2 ( x , y ) ∈ C 2 x ∈ C x\in C x ∈ C y = x + d y=x+d y = x + d ∣ C ∣ \card{C} ∣ C ∣ i i i A i ( C ) A_i(C) A i ( C )
⟨ A i 1 C , 1 C ⟩ = ∣ C ∣ A i ( C ) . \langle \mathsf{A}_i\one_C,\one_C\rangle
=
\card{C}A_i(C). ⟨ A i 1 C , 1 C ⟩ = ∣ C ∣ A i ( C ) . したがって a i ( C ) = A i ( C ) a_{i}(C) = A_{i}(C) a i ( C ) = A i ( C )
証明終わり □
この定理は，アソシエーションスキームの言葉が符号理論の重み分布を含んでいることを示しています． 一般の部分集合 D ⊆ Ω D\subseteq \Omega D ⊆ Ω a i ( D ) a_{i}(D) a i ( D ) D D D
§9 双対分布：符号を固有空間側から見る 内部分布は，隣接行列 A i \mathsf{A}_i A i E j \mathsf{E}_j E j
定義9.1．
D ⊆ Ω D\subseteq \Omega D ⊆ Ω D D D 双対分布 (dual distribution ) を
a j ∗ ( D ) = ∣ Ω ∣ ∣ D ∣ 2 ⟨ E j 1 D , 1 D ⟩ ( 0 ≤ j ≤ n ) a_j^{\ast}(D)
=
\frac{\card{\Omega}}{\card{D}^2}
\langle \mathsf{E}_j\one_D,\one_D\rangle
\qquad
(0\leq j\leq n) a j ∗ ( D ) = ∣ D ∣ 2 ∣ Ω ∣ ⟨ E j 1 D , 1 D ⟩ ( 0 ≤ j ≤ n ) で定める．
ここで
⟨ E j 1 D , 1 D ⟩ = ⟨ E j 1 D , E j 1 D ⟩ \langle \mathsf{E}_j\one_D,\one_D\rangle
=
\langle \mathsf{E}_j\one_D,\mathsf{E}_j\one_D\rangle ⟨ E j 1 D , 1 D ⟩ = ⟨ E j 1 D , E j 1 D ⟩ は，特性ベクトル 1 D \one_D 1 D V j V_j V j ∣ Ω ∣ ∣ D ∣ 2 \displaystyle \frac{\card{\Omega}}{\card{D}^2} ∣ D ∣ 2 ∣ Ω ∣ D = C D=C D = C a j ∗ ( C ) = A j ( C ⊥ ) a_j^{\ast}(C)=A_j(C^\perp) a j ∗ ( C ) = A j ( C ⊥ )
この正規化では，a 0 ∗ ( D ) = 1 a_0^{\ast}(D)=1 a 0 ∗ ( D ) = 1 E 0 = ∣ Ω ∣ − 1 J \mathsf{E}_0=\card{\Omega}^{-1}J E 0 = ∣ Ω ∣ − 1 J
⟨ E 0 1 D , 1 D ⟩ = ∣ D ∣ 2 ∣ Ω ∣ \langle \mathsf{E}_0\one_D,\one_D\rangle
=
\frac{\card{D}^2}{\card{\Omega}} ⟨ E 0 1 D , 1 D ⟩ = ∣ Ω ∣ ∣ D ∣ 2 である． また，
∑ j = 0 n a j ∗ ( D ) = ∣ Ω ∣ ∣ D ∣ 2 ⟨ ∑ j = 0 n E j 1 D , 1 D ⟩ = ∣ Ω ∣ ∣ D ∣ \sum_{j=0}^{n}a_j^{\ast}(D)
=
\frac{\card{\Omega}}{\card{D}^2}
\left\langle
\sum_{j=0}^{n}\mathsf{E}_j\one_D,\one_D
\right\rangle
=
\frac{\card{\Omega}}{\card{D}} j = 0 ∑ n a j ∗ ( D ) = ∣ D ∣ 2 ∣ Ω ∣ ⟨ j = 0 ∑ n E j 1 D , 1 D ⟩ = ∣ D ∣ ∣ Ω ∣ となる． したがって，双対分布もこの正規化では確率分布ではありません． 線形符号 C C C ∣ C ⊥ ∣ = ∣ Ω ∣ / ∣ C ∣ \card{C^{\perp}}=\card{\Omega}/\card{C} C ⊥ = ∣ Ω ∣ / ∣ C ∣ D ⊆ Ω D\subseteq \Omega D ⊆ Ω D ⊥ D^{\perp} D ⊥ a j ∗ ( D ) a_j^{\ast}(D) a j ∗ ( D ) E j \mathsf{E}_j E j
注意として，一般の部分集合 D D D a j ∗ ( D ) a_j^{\ast}(D) a j ∗ ( D ) 1 D \one_D 1 D
この定義は少し抽象的に見えるかもしれません． しかし，意味は単純です． 特性ベクトル 1 D \one_D 1 D V 0 , V 1 , … , V n V_{0}, V_{1}, \dots, V_{n} V 0 , V 1 , … , V n E j \mathsf{E}_j E j V j V_j V j
⟨ E j 1 D , 1 D ⟩ = ⟨ E j 1 D , E j 1 D ⟩ ≥ 0 \langle \mathsf{E}_j\one_D,\one_D\rangle
=
\langle \mathsf{E}_j\one_D,\mathsf{E}_j\one_D\rangle
\geq 0 ⟨ E j 1 D , 1 D ⟩ = ⟨ E j 1 D , E j 1 D ⟩ ≥ 0 です． したがって双対分布は非負です．
一般の部分集合 D D D a j ∗ ( D ) a_j^{\ast}(D) a j ∗ ( D )
次の定理では，一度だけ加法指標を使います． 目的は，アソシエーションスキームで定義した双対分布が， 線形符号の場合には通常の双対符号 C ⊥ C^\perp C ⊥
定理9.2．
C ≤ F q E C \leq \F_{q}^{E} C ≤ F q E a j ∗ ( C ) = A j ( C ⊥ ) a_{j}^{\ast}(C) = A_{j}(C^{\perp}) a j ∗ ( C ) = A j ( C ⊥ )
証明 有限体の非自明な加法指標 ψ : F q → C × \psi \colon \F_{q} \to \C^{\times} ψ : F q → C × q = p m q=p^m q = p m
ψ ( a ) = exp ( 2 π − 1 p Tr F q / F p ( a ) ) \psi(a)
= \exp\left(\frac{2\pi \sqrt{-1}}{p}\Tr_{\F_q/\F_p}(a)\right) ψ ( a ) = exp ( p 2 π − 1 Tr F q / F p ( a ) ) と定めると非自明な加法指標が得られる． ただし，本稿ではこの構成の詳細には立ち入らない． 以下では，非自明な加法指標の基本的な直交関係
∑ a ∈ F q ψ ( t a ) = { q , t = 0 , 0 , t ≠ 0 \sum_{a\in\F_q}\psi(ta)
=
\begin{cases}
q, & t=0,\\
0, & t\neq 0
\end{cases} a ∈ F q ∑ ψ ( t a ) = { q , 0 , t = 0 , t = 0 を用いる． u ∈ F q E u\in\F_q^E u ∈ F q E
χ u ( x ) = ψ ( u ⋅ x ) ( x ∈ F q E ) \chi_u(x)=\psi(u\cdot x)
\qquad
(x\in\F_q^E) χ u ( x ) = ψ ( u ⋅ x ) ( x ∈ F q E ) とおく．これは
χ u ( x ) = ψ ( u ⋅ x ) = ∏ e ∈ E ψ ( u e x e ) \chi_u(x)
=
\psi(u\cdot x)
=
\prod_{e\in E}\psi(u_ex_e) χ u ( x ) = ψ ( u ⋅ x ) = e ∈ E ∏ ψ ( u e x e ) と座標ごとに分解できる． したがって，一座標で見ると u e = 0 u_e=0 u e = 0 u e ≠ 0 u_e\neq 0 u e = 0 0 0 0 χ u ∈ V j \chi_u\in V_j χ u ∈ V j wt ( u ) = j \wt(u)=j wt ( u ) = j 1 1 1
ψ ( v ⋅ x ) ‾ = ψ ( − v ⋅ x ) \overline{\psi(v\cdot x)}=\psi(-v\cdot x) ψ ( v ⋅ x ) = ψ ( − v ⋅ x ) であることも使う． この関数たちは正規化すれば C Ω \C^{\Omega} C Ω u , v ∈ F q E u,v\in\F_q^E u , v ∈ F q E
⟨ χ u , χ v ⟩ = ∑ x ∈ F q E ψ ( ( u − v ) ⋅ x ) = ∏ e ∈ E ∑ x e ∈ F q ψ ( ( u e − v e ) x e ) \begin{aligned}
\langle \chi_u,\chi_v\rangle
&=
\sum_{x\in\F_q^E}\psi((u-v)\cdot x)\\
&=
\prod_{e\in E}
\sum_{x_e\in\F_q}\psi((u_e-v_e)x_e)
\end{aligned} ⟨ χ u , χ v ⟩ = x ∈ F q E ∑ ψ (( u − v ) ⋅ x ) = e ∈ E ∏ x e ∈ F q ∑ ψ (( u e − v e ) x e ) である． したがって u = v u=v u = v q n q^n q n u ≠ v u\neq v u = v u e − v e ≠ 0 u_e-v_e\neq 0 u e − v e = 0 0 0 0
{ q − n / 2 χ u : u ∈ F q E } \{q^{-n/2}\chi_u:u\in\F_q^E\} { q − n /2 χ u : u ∈ F q E } は C Ω \C^{\Omega} C Ω
一座標で見ると，u e = 0 u_e=0 u e = 0 x e ↦ ψ ( u e x e ) x_e\mapsto\psi(u_ex_e) x e ↦ ψ ( u e x e ) u e ≠ 0 u_e\neq0 u e = 0 0 0 0 χ u \chi_u χ u V j V_j V j wt ( u ) = j \wt(u)=j wt ( u ) = j E j \mathsf{E}_j E j j j j
いま，1 C \one_C 1 C j j j
⟨ E j 1 C , 1 C ⟩ = ∑ u ∈ F q E wt ( u ) = j ∣ ⟨ 1 C , q − n / 2 χ u ⟩ ∣ 2 . \begin{aligned}
\langle \mathsf{E}_j\one_C,\one_C\rangle
&=
\sum_{\substack{u\in\F_q^E\\ \wt(u)=j}}
\left\lvert
\left\langle \one_C,q^{-n/2}\chi_u\right\rangle
\right\rvert^2.
\end{aligned} ⟨ E j 1 C , 1 C ⟩ = u ∈ F q E wt ( u ) = j ∑ ⟨ 1 C , q − n /2 χ u ⟩ 2 . ここで
⟨ 1 C , q − n / 2 χ u ⟩ = q − n / 2 ∑ c ∈ C ψ ( u ⋅ c ) ‾ . \left\langle \one_C,q^{-n/2}\chi_u\right\rangle
=
q^{-n/2}\sum_{c\in C}\overline{\psi(u\cdot c)}. ⟨ 1 C , q − n /2 χ u ⟩ = q − n /2 c ∈ C ∑ ψ ( u ⋅ c ) . 右辺は q − n / 2 S u ‾ q^{-n/2}\overline{S_u} q − n /2 S u
S u ≔ ∑ c ∈ C ψ ( u ⋅ c ) S_u\coloneqq\sum_{c\in C}\psi(u\cdot c) S u : = c ∈ C ∑ ψ ( u ⋅ c ) とおく． u ∈ C ⊥ u\in C^{\perp} u ∈ C ⊥ u ⋅ c = 0 u\cdot c=0 u ⋅ c = 0 c ∈ C c\in C c ∈ C
S u = ∣ C ∣ S_u=\card{C} S u = ∣ C ∣ である． 一方，u ∉ C ⊥ u\notin C^{\perp} u ∈ / C ⊥ c ↦ u ⋅ c c \mapsto u \cdot c c ↦ u ⋅ c C C C F q \F_q F q F q \F_q F q ∣ C ∣ / q \card{C}/q ∣ C ∣ / q
S u = ∣ C ∣ q ∑ a ∈ F q ψ ( a ) = 0 S_u
=
\frac{\card{C}}{q}\sum_{a\in\F_q}\psi(a)
=
0 S u = q ∣ C ∣ a ∈ F q ∑ ψ ( a ) = 0 である． したがって
⟨ E j 1 C , 1 C ⟩ = ∣ C ∣ 2 q n ∣ { u ∈ C ⊥ : wt ( u ) = j } ∣ = ∣ C ∣ 2 q n A j ( C ⊥ ) . \langle \mathsf{E}_j\one_C,\one_C\rangle
=
\frac{\card{C}^2}{q^n}
\card{\{u\in C^{\perp}:\wt(u)=j\}}
=
\frac{\card{C}^2}{q^n}A_j(C^{\perp}). ⟨ E j 1 C , 1 C ⟩ = q n ∣ C ∣ 2 { u ∈ C ⊥ : wt ( u ) = j } = q n ∣ C ∣ 2 A j ( C ⊥ ) . いま ∣ Ω ∣ = q n \card{\Omega}=q^n ∣ Ω ∣ = q n
a j ∗ ( C ) = q n ∣ C ∣ 2 ⟨ E j 1 C , 1 C ⟩ = A j ( C ⊥ ) a_j^{\ast}(C)
=
\frac{q^n}{\card{C}^2}
\langle \mathsf{E}_j\one_C,\one_C\rangle
=
A_j(C^{\perp}) a j ∗ ( C ) = ∣ C ∣ 2 q n ⟨ E j 1 C , 1 C ⟩ = A j ( C ⊥ ) を得る．
証明終わり □
この定理の中で指標が一瞬だけ現れました． しかし，その役割は「Hammingスキームの固有空間側が，線形符号の場合には通常の双対符号を見ている」ことを確認するためです． アソシエーションスキーム的な視点では，C ⊥ C^{\perp} C ⊥
§10 係数レベルのMacWilliams恒等式 ここまでの準備により，MacWilliams恒等式はほとんど証明されています． まず，一般の部分集合に対する変換公式を書きます．
証明 双対分布の定義より
a j ∗ ( D ) = ∣ Ω ∣ ∣ D ∣ 2 ⟨ E j 1 D , 1 D ⟩ a_j^\ast(D)
=
\frac{\card{\Omega}}{\card{D}^2}
\langle \mathsf{E}_j\one_D,\one_D\rangle a j ∗ ( D ) = ∣ D ∣ 2 ∣ Ω ∣ ⟨ E j 1 D , 1 D ⟩ である． ここに 定理 7.1 Hammingスキーム H ( n , q ) H(n,q) H ( n , q )
E j = 1 q n ∑ i = 0 n K j ( i ) A i (7.1) \mathsf{E}_j
=
\frac{1}{q^n}
\sum_{i=0}^{n}\Kraw_j(i)\mathsf{A}_i
\tag{7.1} E j = q n 1 i = 0 ∑ n K j ( i ) A i ( 7.1 ) と書ける． ∣ Ω ∣ = q n \card{\Omega}=q^n ∣ Ω ∣ = q n
a j ∗ ( D ) = q n ∣ D ∣ 2 ⟨ 1 q n ∑ i = 0 n K j ( i ) A i 1 D , 1 D ⟩ = 1 ∣ D ∣ 2 ∑ i = 0 n K j ( i ) ⟨ A i 1 D , 1 D ⟩ = 1 ∣ D ∣ ∑ i = 0 n K j ( i ) a i ( D ) . \begin{aligned}
a_j^\ast(D)
&=
\frac{q^n}{\card{D}^2}
\left\langle
\frac{1}{q^n}\sum_{i=0}^{n}\Kraw_j(i)\mathsf{A}_i\one_D,
\one_D
\right\rangle\\
&=
\frac{1}{\card{D}^2}
\sum_{i=0}^{n}\Kraw_j(i)\langle \mathsf{A}_i\one_D,\one_D\rangle\\
&=
\frac{1}{\card{D}}
\sum_{i=0}^{n}\Kraw_j(i)a_i(D).
\end{aligned} a j ∗ ( D ) = ∣ D ∣ 2 q n ⟨ q n 1 i = 0 ∑ n K j ( i ) A i 1 D , 1 D ⟩ = ∣ D ∣ 2 1 i = 0 ∑ n K j ( i ) ⟨ A i 1 D , 1 D ⟩ = ∣ D ∣ 1 i = 0 ∑ n K j ( i ) a i ( D ) . 証明終わり □
線形符号 C C C 定理 8.3 C ≤ F q E C \leq \F_{q}^{E} C ≤ F q E A i ( C ) = ∣ { c ∈ C : wt ( c ) = i } ∣ A_{i}(C) = \card{\{ c \in C : \wt(c) = i \}} A i ( C ) = ∣ { c ∈ C : wt ( c ) = i } ∣ a i ( C ) = A i ( C ) a_{i}(C) = A_{i}(C) a i ( C ) = A i ( C ) 定理 9.2 C ≤ F q E C \leq \F_{q}^{E} C ≤ F q E a j ∗ ( C ) = A j ( C ⊥ ) a_{j}^{\ast}(C) = A_{j}(C^{\perp}) a j ∗ ( C ) = A j ( C ⊥ )
a i ( C ) = A i ( C ) , a j ∗ ( C ) = A j ( C ⊥ ) a_i(C)=A_i(C),
\qquad
a_j^\ast(C)=A_j(C^\perp) a i ( C ) = A i ( C ) , a j ∗ ( C ) = A j ( C ⊥ ) なので，この一般公式がそのまま係数レベルのMacWilliams恒等式になります．
定理10.2（係数レベルのMacWilliams恒等式）．
C ≤ F q E C\leq\F_q^E C ≤ F q E A i = A i ( C ) A_i=A_i(C) A i = A i ( C ) B j = A j ( C ⊥ ) B_j=A_j(C^{\perp}) B j = A j ( C ⊥ )
B j = 1 ∣ C ∣ ∑ i = 0 n A i K j ( i ) (10.2) B_j
=
\frac{1}{\card{C}}
\sum_{i=0}^{n}A_i\Kraw_j(i)
\tag{10.2} B j = ∣ C ∣ 1 i = 0 ∑ n A i K j ( i ) ( 10.2 ) が成り立つ．
証明 この証明の構造を整理すると，次の三段階です．
重み分布は，関係側の量
⟨ A i 1 C , 1 C ⟩ \langle \mathsf{A}_i\one_C,\one_C\rangle ⟨ A i 1 C , 1 C ⟩ として表される．
双対符号の重み分布は，固有空間側の量
⟨ E j 1 C , 1 C ⟩ \langle \mathsf{E}_j\one_C,\one_C\rangle ⟨ E j 1 C , 1 C ⟩ として表される．
E j \mathsf{E}_j E j A i \mathsf{A}_i A i
つまり，MacWilliams恒等式は，
Bose–Mesner代数の二つの基底，隣接行列基底と原始冪等元基底の変換公式
として現れています．
§11 多項式形のMacWilliams恒等式 係数レベルの公式から，通常の多項式形のMacWilliams恒等式を導きます．
定理11.1（MacWilliams恒等式）．
C ≤ F q E C\leq\F_q^E C ≤ F q E
W C ⊥ ( X , Y ) = 1 ∣ C ∣ W C ( X + ( q − 1 ) Y , X − Y ) W_{C^{\perp}}(X,Y)
=
\frac{1}{\card{C}}
W_C\bigl(X+(q-1)Y,X-Y\bigr) W C ⊥ ( X , Y ) = ∣ C ∣ 1 W C ( X + ( q − 1 ) Y , X − Y ) が成り立つ．
証明 A i = A i ( C ) A_i=A_i(C) A i = A i ( C ) B j = A j ( C ⊥ ) B_j=A_j(C^{\perp}) B j = A j ( C ⊥ ) 定理 10.2（係数レベルのMacWilliams恒等式） C ≤ F q E C\leq\F_q^E C ≤ F q E A i = A i ( C ) A_i=A_i(C) A i = A i ( C ) B j = A j ( C ⊥ ) B_j=A_j(C^{\perp}) B j = A j ( C ⊥ ) B j = 1 ∣ C ∣ ∑ i = 0 n A i K j ( i ) (10.2) B_j
=
\frac{1}{\card{C}}
\sum_{i=0}^{n}A_i\Kraw_j(i)
\tag{10.2} B j = ∣ C ∣ 1 i = 0 ∑ n A i K j ( i ) ( 10.2 ) が成り立つ．
W C ⊥ ( X , Y ) = ∑ j = 0 n B j X n − j Y j = 1 ∣ C ∣ ∑ j = 0 n ∑ i = 0 n A i K j ( i ) X n − j Y j = 1 ∣ C ∣ ∑ i = 0 n A i ∑ j = 0 n K j ( i ) X n − j Y j . \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_{i=0}^{n}A_i\Kraw_j(i)X^{n-j}Y^j\\
&=
\frac{1}{\card{C}}
\sum_{i=0}^{n}A_i
\sum_{j=0}^{n}\Kraw_j(i)X^{n-j}Y^j.
\end{aligned} W C ⊥ ( X , Y ) = j = 0 ∑ n B j X n − j Y j = ∣ C ∣ 1 j = 0 ∑ n i = 0 ∑ n A i K j ( i ) X n − j Y j = ∣ C ∣ 1 i = 0 ∑ n A i j = 0 ∑ n K j ( i ) X n − j Y j . Krawtchouk多項式の母関数
∑ j = 0 n K j ( i ) z j = ( 1 + ( q − 1 ) z ) n − i ( 1 − z ) i \sum_{j=0}^{n}\Kraw_j(i)z^j
=
\bigl(1+(q-1)z\bigr)^{n-i}(1-z)^i j = 0 ∑ n K j ( i ) z j = ( 1 + ( q − 1 ) z ) n − i ( 1 − z ) i の両辺に X n X^n X n z j z^j z j X − j Y j X^{-j}Y^j X − j Y j
∑ j = 0 n K j ( i ) X n − j Y j = ( X + ( q − 1 ) Y ) n − i ( X − Y ) i \sum_{j=0}^{n}\Kraw_j(i)X^{n-j}Y^j
=
\bigl(X+(q-1)Y\bigr)^{n-i}(X-Y)^i j = 0 ∑ n K j ( i ) X n − j Y j = ( X + ( q − 1 ) Y ) n − i ( X − Y ) i を得る． これは多項式恒等式としての計算であり，X X X
W C ⊥ ( X , Y ) = 1 ∣ C ∣ ∑ i = 0 n A i ( X + ( q − 1 ) Y ) n − i ( X − Y ) i = 1 ∣ C ∣ W C ( X + ( q − 1 ) Y , X − Y ) . \begin{aligned}
W_{C^{\perp}}(X,Y)
&=
\frac{1}{\card{C}}
\sum_{i=0}^{n}A_i
\bigl(X+(q-1)Y\bigr)^{n-i}(X-Y)^i\\
&=
\frac{1}{\card{C}}
W_C\bigl(X+(q-1)Y,X-Y\bigr).
\end{aligned} W C ⊥ ( X , Y ) = ∣ C ∣ 1 i = 0 ∑ n A i ( X + ( q − 1 ) Y ) n − i ( X − Y ) i = ∣ C ∣ 1 W C ( X + ( q − 1 ) Y , X − Y ) . これでMacWilliams恒等式が証明された．
証明終わり □
この証明で，変数変換
X ↦ X + ( q − 1 ) Y , Y ↦ X − Y X\mapsto X+(q-1)Y,
\qquad
Y\mapsto X-Y X ↦ X + ( q − 1 ) Y , Y ↦ X − Y は，Hammingスキームの固有値母関数から出てきました． つまり，変数変換は単なる代数的な偶然ではなく， 距離関係を表す行列たちの固有値をまとめたものです．
§12 小さな例：H ( 2 , 2 ) H(2,2) H ( 2 , 2 ) 最後に，小さな例でアソシエーションスキーム的な見方を確認します． Ω = F 2 2 \Omega=\F_2^2 Ω = F 2 2 H ( 2 , 2 ) H(2,2) H ( 2 , 2 )
00 , 01 , 10 , 11 00,01,10,11 00 , 01 , 10 , 11 の四つです． 関係は距離によって
R 0 = { ( x , x ) : x ∈ Ω } , R 1 = { ( x , y ) : dist ( x , y ) = 1 } , R 2 = { ( x , y ) : dist ( x , y ) = 2 } \begin{aligned}
R_0&=\{(x,x):x\in \Omega\},\\
R_1&=\{(x,y):\dist(x,y)=1\},\\
R_2&=\{(x,y):\dist(x,y)=2\}
\end{aligned} R 0 R 1 R 2 = {( x , x ) : x ∈ Ω } , = {( x , y ) : dist ( x , y ) = 1 } , = {( x , y ) : dist ( x , y ) = 2 } に分かれます． 頂点を 00 , 01 , 10 , 11 00,01,10,11 00 , 01 , 10 , 11
A 0 = I , A 1 = ( 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 ) , A 2 = ( 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 ) \mathsf{A}_0=I,
\qquad
\mathsf{A}_1=
\begin{pmatrix}
0&1&1&0\\
1&0&0&1\\
1&0&0&1\\
0&1&1&0
\end{pmatrix},
\qquad
\mathsf{A}_2=
\begin{pmatrix}
0&0&0&1\\
0&0&1&0\\
0&1&0&0\\
1&0&0&0
\end{pmatrix} A 0 = I , A 1 = 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 , A 2 = 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 です．
q = 2 q=2 q = 2 n = 2 n=2 n = 2
w = 0 w = 1 w = 2 j = 0 1 1 1 j = 1 2 0 − 2 j = 2 1 − 1 1 \begin{array}{c|rrr}
& w=0 & w=1 & w=2 \\
\hline
j=0 & 1 & 1 & 1 \\
j=1 & 2 & 0 & -2 \\
j=2 & 1 & -1 & 1
\end{array} j = 0 j = 1 j = 2 w = 0 1 2 1 w = 1 1 0 − 1 w = 2 1 − 2 1 です． これは，A j \mathsf{A}_j A j V w V_w V w j j j w w w
二元反復符号
C = { 00 , 11 } ≤ F 2 2 C=\{00,11\}\leq\F_2^2 C = { 00 , 11 } ≤ F 2 2 を考えます． この符号は自己双対です． 重み分布は
( A 0 , A 1 , A 2 ) = ( 1 , 0 , 1 ) (A_0,A_1,A_2)=(1,0,1) ( A 0 , A 1 , A 2 ) = ( 1 , 0 , 1 ) です． 係数レベルのMacWilliams恒等式は
B j = 1 ∣ C ∣ ∑ i = 0 2 A i K j ( i ) B_j
=
\frac{1}{\card{C}}
\sum_{i=0}^{2}A_i\Kraw_j(i) B j = ∣ C ∣ 1 i = 0 ∑ 2 A i K j ( i ) でした． いま ∣ C ∣ = 2 \card{C}=2 ∣ C ∣ = 2 A 0 = A 2 = 1 A_0=A_2=1 A 0 = A 2 = 1 A 1 = 0 A_1=0 A 1 = 0
B j = 1 2 ( K j ( 0 ) + K j ( 2 ) ) B_j
=
\frac{1}{2}\bigl(\Kraw_j(0)+\Kraw_j(2)\bigr) B j = 2 1 ( K j ( 0 ) + K j ( 2 ) ) です． 上の数表に現れた値を用いると
B 0 = 1 2 ( 1 + 1 ) = 1 , B 1 = 1 2 ( 2 − 2 ) = 0 , B 2 = 1 2 ( 1 + 1 ) = 1. B_{0} = \frac{1}{2}(1 + 1) = 1, \qquad
B_{1} = \frac{1}{2}(2 - 2) = 0, \qquad
B_{2} = \frac{1}{2}(1 + 1) = 1. B 0 = 2 1 ( 1 + 1 ) = 1 , B 1 = 2 1 ( 2 − 2 ) = 0 , B 2 = 2 1 ( 1 + 1 ) = 1. したがって
( B 0 , B 1 , B 2 ) = ( 1 , 0 , 1 ) (B_{0}, B_{1}, B_{2}) = (1, 0, 1) ( B 0 , B 1 , B 2 ) = ( 1 , 0 , 1 ) となり，確かに C ⊥ = C C^{\perp} = C C ⊥ = C
a ( C ) = ( 1 , 0 , 1 ) , a ∗ ( C ) = ( 1 , 0 , 1 ) a(C)=(1,0,1),
\qquad
a^\ast(C)=(1,0,1) a ( C ) = ( 1 , 0 , 1 ) , a ∗ ( C ) = ( 1 , 0 , 1 ) となっているということです． 後者は，1 C \one_C 1 C V 0 , V 1 , V 2 V_0,V_1,V_2 V 0 , V 1 , V 2 00 , 01 , 10 , 11 00,01,10,11 00 , 01 , 10 , 11
1 C = ( 1 , 0 , 0 , 1 ) \one_{C} = (1,0,0,1) 1 C = ( 1 , 0 , 0 , 1 ) であり，
1 C = 1 2 ( 1 , 1 , 1 , 1 ) + 1 2 ( 1 , − 1 , − 1 , 1 ) \one_{C}
=
\frac{1}{2}(1,1,1,1)
+
\frac{1}{2}(1,-1,-1,1) 1 C = 2 1 ( 1 , 1 , 1 , 1 ) + 2 1 ( 1 , − 1 , − 1 , 1 ) と分解できます． 第一成分は定数ベクトルなので V 0 V_0 V 0
( 1 , − 1 , − 1 , 1 ) = ( 1 , − 1 ) ⊗ ( 1 , − 1 ) (1,-1,-1,1) = (1, -1) \otimes (1, -1) ( 1 , − 1 , − 1 , 1 ) = ( 1 , − 1 ) ⊗ ( 1 , − 1 ) と書けるので V 2 V_{2} V 2 V 1 V_{1} V 1 0 0 0 1 , 0 , 1 1,0,1 1 , 0 , 1 ( 1 , 0 , 1 ) (1,0,1) ( 1 , 0 , 1 )
アソシエーションスキーム的には，この計算は次のように見えます． まず，C C C A 0 , A 1 , A 2 \mathsf{A}_0,\mathsf{A}_1,\mathsf{A}_2 A 0 , A 1 , A 2 1 C \one_C 1 C V 0 V_{0} V 0 V 1 V_{1} V 1 V 2 V_{2} V 2
§13 この証明でアソシエーションスキームは何をしていたか 証明の中でアソシエーションスキームが担っていた役割を整理しておきます．
第一に，アソシエーションスキームは，Hamming空間の距離構造を行列代数に変えました． 距離 i i i A i \mathsf{A}_i A i
第二に，Bose–Mesner代数の二つの基底が現れました． 一つは距離関係を表す隣接行列基底 A 0 , … , A n \mathsf{A}_{0}, \dots, \mathsf{A}_{n} A 0 , … , A n E 0 , … , E n \mathsf{E}_{0}, \dots, \mathsf{E}_{n} E 0 , … , E n
第三に，Krawtchouk多項式は固有値として現れました． 隣接行列 A j \mathsf{A}_{j} A j V w V_{w} V w K j ( w ) \Kraw_j(w) K j ( w )
第四に，符号の重み分布は内部分布として現れました． 線形符号 C C C
a i ( C ) = 1 ∣ C ∣ ⟨ A i 1 C , 1 C ⟩ a_{i}(C)
= \frac{1}{\card{C}}\langle \mathsf{A}_{i} \one_{C}, \one_{C} \rangle a i ( C ) = ∣ C ∣ 1 ⟨ A i 1 C , 1 C ⟩ が通常の重み分布 A i ( C ) A_{i}(C) A i ( C )
第五に，双対符号の重み分布は双対分布として現れました． 原始冪等元を使って
a j ∗ ( C ) = q n ∣ C ∣ 2 ⟨ E j 1 C , 1 C ⟩ a_{j}^{\ast}(C)
= \frac{q^{n}}{\card{C}^{2}} \langle \mathsf{E}_{j} \one_{C}, \one_{C} \rangle a j ∗ ( C ) = ∣ C ∣ 2 q n ⟨ E j 1 C , 1 C ⟩ と定義すると，線形符号では a j ∗ ( C ) = A j ( C ⊥ ) a_{j}^{\ast}(C) = A_{j}(C^{\perp}) a j ∗ ( C ) = A j ( C ⊥ )
したがって，今回の証明の要点は次の一文にまとめられます．
MacWilliams恒等式は，HammingスキームのBose–Mesner代数における， 隣接行列基底と原始冪等元基底の基底変換である．
§14 この回で見た概念 この回では，MacWilliams恒等式の証明を目標にしながら， アソシエーションスキームの基本的な道具を導入しました． 整理すると次のようになります．
関係分割 有限集合 Ω \Omega Ω Ω × Ω \Omega\times \Omega Ω × Ω R 0 , R 1 , … , R d R_{0}, R_{1}, \dots, R_{d} R 0 , R 1 , … , R d 0 , 1 , … , n 0, 1, \dots, n 0 , 1 , … , n
隣接行列 関係 R i R_{i} R i 0 0 0 1 1 1
アソシエーションスキーム 関係分割が十分に規則的であり，交叉数 p i j k p_{ij}^{k} p ij k
Bose–Mesner代数 隣接行列 A 0 , … , A d \mathsf{A}_{0}, \dots, \mathsf{A}_{d} A 0 , … , A d
原始冪等元 Bose–Mesner代数の共通固有空間への射影です． Hammingスキームでは，V 0 , … , V n V_{0}, \dots, V_{n} V 0 , … , V n E 0 , … , E n \mathsf{E}_{0}, \dots, \mathsf{E}_{n} E 0 , … , E n
Hammingスキーム Ω = F q E \Omega = \F_{q}^{E} Ω = F q E
Krawtchouk多項式 Hammingスキームの隣接行列 A j \mathsf{A}_{j} A j V w V_{w} V w
∑ j = 0 n K j ( w ) z j = ( 1 + ( q − 1 ) z ) n − w ( 1 − z ) w \sum_{j=0}^{n} \Kraw_{j}(w) z^{j}
= \bigl( 1 + (q - 1)z \bigr)^{n - w}(1 - z)^{w} j = 0 ∑ n K j ( w ) z j = ( 1 + ( q − 1 ) z ) n − w ( 1 − z ) w です．
内部分布 部分集合 D ⊆ Ω D\subseteq \Omega D ⊆ Ω R i R_{i} R i
双対分布 特性ベクトルを原始冪等元で射影し，各固有空間成分の大きさを測る分布です． 線形符号では，通常の双対符号の重み分布と一致します．
アソシエーションスキームの見方では，符号は単なる線形部分空間ではなく， Hamming空間という距離構造を持つ有限集合の部分集合として扱われます． その部分集合の距離分布と，Bose–Mesner代数の固有空間分解が結びつくところに， MacWilliams恒等式が現れます．
§15 今回の系統の振り返り 冒頭で述べたように，今回の証明は
直交多項式・アソシエーションスキーム系
に属します． 表面的には，Hamming距離から作った隣接行列とBose–Mesner代数を使った証明です． 深いところでは，Hamming空間の距離構造が可換な行列代数を作り， その固有値理論が重み分布の変換を支配しています．
Krawtchouk多項式を前面に出して見ると，MacWilliams恒等式は
重み分布に対するKrawtchouk変換
です． アソシエーションスキームの見方では，さらに一段階深く，
Krawtchouk変換は，HammingスキームのBose–Mesner代数における基底変換である
と理解できます．
この見方の利点は，MacWilliams恒等式をより広い枠組みに置けることです． Hammingスキームだけでなく，Johnsonスキーム，Grassmannスキーム，dual polarスキームなど， 多くのアソシエーションスキームにおいて， 内部分布，双対分布，固有値，線形計画法境界といった概念が同じ形式で現れます． 符号理論に現れるDelsarteの線形計画法も，このアソシエーションスキーム的な見方から自然に導かれます． この広い枠組みについては， Delsarte [Del73] および Delsarte–Levenshtein [DL98] を参照してください．
今回の証明の要点は，次の一文です．
Hamming距離で色分けした完全グラフのBose–Mesner代数を対角化すると， その固有値としてKrawtchouk多項式が現れ， 関係側の分布と固有空間側の分布を結ぶ公式としてMacWilliams恒等式が得られる．
§16 次回へ 次回は，MacWilliams恒等式をモーメント恒等式の側から見ます．
今回の証明では，重み分布そのものを，Hammingスキームの隣接行列や原始冪等元を使って変換しました． 次回は，重み分布を直接変換するのではなく，まず
∑ i = 0 n A i ( C ) i r や ∑ i = 0 n A i ( C ) ( i r ) \sum_{i=0}^{n} A_{i}(C) i^{r}
\quad\text{や}\quad
\sum_{i=0}^{n} A_{i}(C) \binom{i}{r} i = 0 ∑ n A i ( C ) i r や i = 0 ∑ n A i ( C ) ( r i ) のようなモーメントに注目します．
重み分布のモーメントは，符号語と座標集合の組を二通りに数えることで計算できます． そこからPlessのpower moment identitiesが現れます． 十分多くのモーメント恒等式を集めると，重み分布全体のMacWilliams変換を復元できます．
つまり次回の主役は，
重み分布 → モーメント → 二重数え上げ → MacWilliams恒等式
です． 同じMacWilliams恒等式であっても， 今回のような固有値・行列代数の見方とはかなり違った，数え上げ的な姿が見えてきます．
参考文献 [Del73] P. Delsarte. An algebraic approach to the association schemes of coding theory . Philips Res. Rep. Suppl., no. 10, pp. vi+97, 1973 引用箇所 アソシエーションスキーム的な符号理論の古典的な出発点は Delsarte [Del73] です． 距離分布，MacWilliams変換，線形計画法まで含めて， アソシエーションスキームと符号理論の関係を概観する文献としては Delsarte–Levenshtein [DL98] があります． アソシエーションスキームの体系的な文献としては Bannai–Ito [BI84] が標準的です． また，距離正則グラフとの関係も含めた詳しい解説として Brouwer–Cohen–Neumaier [BCN89] があります． 符号理論におけるMacWilliams恒等式とKrawtchouk多項式については MacWilliams–Sloane [MS77, Chapter 5] も古典的な標準文献です． 符号理論で使うアソシエーションスキームの基本事項については， Camion [Cam98] も有用です． 引用箇所 ここから符号に戻ります． アソシエーションスキームでは，有限集合 Ω \Omega Ω D ⊆ Ω D\subseteq \Omega D ⊆ Ω [Del73 ; Cam98 ] ． 引用箇所 この見方の利点は，MacWilliams恒等式をより広い枠組みに置けることです． Hammingスキームだけでなく，Johnsonスキーム，Grassmannスキーム，dual polarスキームなど， 多くのアソシエーションスキームにおいて， 内部分布，双対分布，固有値，線形計画法境界といった概念が同じ形式で現れます． 符号理論に現れるDelsarteの線形計画法も，このアソシエーションスキーム的な見方から自然に導かれます． この広い枠組みについては， Delsarte [Del73] および Delsarte–Levenshtein [DL98] を参照してください． [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 引用箇所 アソシエーションスキーム的な符号理論の古典的な出発点は Delsarte [Del73] です． 距離分布，MacWilliams変換，線形計画法まで含めて， アソシエーションスキームと符号理論の関係を概観する文献としては Delsarte–Levenshtein [DL98] があります． アソシエーションスキームの体系的な文献としては Bannai–Ito [BI84] が標準的です． また，距離正則グラフとの関係も含めた詳しい解説として Brouwer–Cohen–Neumaier [BCN89] があります． 符号理論におけるMacWilliams恒等式とKrawtchouk多項式については MacWilliams–Sloane [MS77, Chapter 5] も古典的な標準文献です． 符号理論で使うアソシエーションスキームの基本事項については， Camion [Cam98] も有用です． 引用箇所 この見方の利点は，MacWilliams恒等式をより広い枠組みに置けることです． Hammingスキームだけでなく，Johnsonスキーム，Grassmannスキーム，dual polarスキームなど， 多くのアソシエーションスキームにおいて， 内部分布，双対分布，固有値，線形計画法境界といった概念が同じ形式で現れます． 符号理論に現れるDelsarteの線形計画法も，このアソシエーションスキーム的な見方から自然に導かれます． この広い枠組みについては， Delsarte [Del73] および Delsarte–Levenshtein [DL98] を参照してください． [BI84] Eiichi Bannai and Tatsuro Ito. Algebraic combinatorics. I . The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, pp. xxiv+425, 1984 引用箇所 アソシエーションスキーム的な符号理論の古典的な出発点は Delsarte [Del73] です． 距離分布，MacWilliams変換，線形計画法まで含めて， アソシエーションスキームと符号理論の関係を概観する文献としては Delsarte–Levenshtein [DL98] があります． アソシエーションスキームの体系的な文献としては Bannai–Ito [BI84] が標準的です． また，距離正則グラフとの関係も含めた詳しい解説として Brouwer–Cohen–Neumaier [BCN89] があります． 符号理論におけるMacWilliams恒等式とKrawtchouk多項式については MacWilliams–Sloane [MS77, Chapter 5] も古典的な標準文献です． 符号理論で使うアソシエーションスキームの基本事項については， Camion [Cam98] も有用です． [BCN89] A. E. Brouwer, A. M. Cohen, and A. Neumaier. Distance-regular graphs . Springer-Verlag, Berlin, vol. 18, pp. xviii+495, 1989. doi:10.1007/978-3-642-74341-2 引用箇所 アソシエーションスキーム的な符号理論の古典的な出発点は Delsarte [Del73] です． 距離分布，MacWilliams変換，線形計画法まで含めて， アソシエーションスキームと符号理論の関係を概観する文献としては Delsarte–Levenshtein [DL98] があります． アソシエーションスキームの体系的な文献としては Bannai–Ito [BI84] が標準的です． また，距離正則グラフとの関係も含めた詳しい解説として Brouwer–Cohen–Neumaier [BCN89] があります． 符号理論におけるMacWilliams恒等式とKrawtchouk多項式については MacWilliams–Sloane [MS77, Chapter 5] も古典的な標準文献です． 符号理論で使うアソシエーションスキームの基本事項については， Camion [Cam98] も有用です． [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 引用箇所 アソシエーションスキーム的な符号理論の古典的な出発点は Delsarte [Del73] です． 距離分布，MacWilliams変換，線形計画法まで含めて， アソシエーションスキームと符号理論の関係を概観する文献としては Delsarte–Levenshtein [DL98] があります． アソシエーションスキームの体系的な文献としては Bannai–Ito [BI84] が標準的です． また，距離正則グラフとの関係も含めた詳しい解説として Brouwer–Cohen–Neumaier [BCN89] があります． 符号理論におけるMacWilliams恒等式とKrawtchouk多項式については MacWilliams–Sloane [MS77, Chapter 5] も古典的な標準文献です． 符号理論で使うアソシエーションスキームの基本事項については， Camion [Cam98] も有用です． [Cam98] Paul Camion. Codes and association schemes: basic properties of association schemes relevant to coding . Handbook of coding theory, Vol. I, II, pp. 1441–1566, 1998 引用箇所 アソシエーションスキーム的な符号理論の古典的な出発点は Delsarte [Del73] です． 距離分布，MacWilliams変換，線形計画法まで含めて， アソシエーションスキームと符号理論の関係を概観する文献としては Delsarte–Levenshtein [DL98] があります． アソシエーションスキームの体系的な文献としては Bannai–Ito [BI84] が標準的です． また，距離正則グラフとの関係も含めた詳しい解説として Brouwer–Cohen–Neumaier [BCN89] があります． 符号理論におけるMacWilliams恒等式とKrawtchouk多項式については MacWilliams–Sloane [MS77, Chapter 5] も古典的な標準文献です． 符号理論で使うアソシエーションスキームの基本事項については， Camion [Cam98] も有用です． 引用箇所 ここから符号に戻ります． アソシエーションスキームでは，有限集合 Ω \Omega Ω D ⊆ Ω D\subseteq \Omega D ⊆ Ω [Del73 ; Cam98 ] ． [God93] C. D. Godsil. Algebraic combinatorics . Chapman & Hall, New York, pp. xvi+362, 1993 引用箇所 MacWilliams恒等式のアソシエーションスキーム的証明では， この「関係側」と「固有空間側」の行き来が本質になります． 符号の重み分布は関係側で定義され，双対分布は固有空間側への射影で定義されます． 本節で扱ったBose–Mesner代数や原始冪等元の線形代数的な扱いについては， Godsil [God93] も参照しやすいです．