§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 ∈ F q E c \in \F_{q}^{E} c ∈ F q E 台 (support ) とHamming重み (Hamming weight ) を
supp ( c ) = { e ∈ E : c e ≠ 0 } , wt ( c ) = ∣ supp ( c ) ∣ \supp(c) = \{ e \in E: c_{e} \neq 0 \},
\qquad
\wt(c) = \card{\supp(c)} supp ( c ) = { e ∈ E : c e = 0 } , wt ( c ) = ∣ supp ( c ) ∣ と書きます． 線形符号 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 ) で定めます． 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回から第7回を前提にしません． 後半では，加法指標の直交性に相当する計算と完全重み多項式を使いますが， 必要な定義と事実は本稿内で導入します． なお，本稿では「なぜこの五系統に分けるのか」という連載全体の動機には深入りせず， 群作用・巡回指数の言葉だけで今回の証明が読めるように構成します．
この連載では，MacWilliams恒等式の証明手法を大きく次の五つの系統に分けて眺めています． ただし，この分類は連載全体の見取り図であり，本稿の証明を読むために必須ではありません：
今回扱う証明は，表面的には
群作用・Burnsideの補題・Pólya計数・巡回指数
の言葉で書かれます． 五つの系統に圧縮すれば，これは「Fourier・指標・Poisson系 」寄りです． なぜなら，最後に双対符号 C ⊥ C^{\perp} C ⊥ F q \F_q F q ( F q , + ) (\F_q,+) ( F q , + ) 群作用と巡回指数 に入門することです．
群作用とは，群の元が集合の対称性として振る舞う状況を記述する言葉です． 有限集合に群が作用しているとき，その集合は軌道に分解されます． 軌道の個数を不動点の平均として数える公式が Burnside の補題です． さらに，群の元を置換として見て，その巡回分解を記録したものが巡回指数です． Pólya計数では，この巡回指数に変数を代入することで， 対称性を込めた彩色の数え上げができます．
符号理論では，符号語 c = ( c e ) e ∈ E c = (c_{e})_{e \in E} c = ( c e ) e ∈ E
a ⟼ a + c e a \longmapsto a + c_{e} a ⟼ a + c e として見ることができます． つまり，符号 C C C C C C c e ∈ F q c_{e} \in \F_{q} c e ∈ F q
本稿の流れは次のようになります．
群作用 → 軌道と不動点 → Burnsideの補題 → 巡回指数 → Pólya計数 → 符号から作る置換群 → 完全巡回指数 → MacWilliams恒等式
巡回指数と符号の重み多項式の関係については， Cameron [Cam02] が， 線形符号に付随する置換群の巡回指数が， 正規化を除いて重み多項式になることを述べています． 完全巡回指数と完全重み多項式の関係については， 三枝崎–大浦 [MO19] を参照してください． また，Pólya計数や巡回指数の古典的な扱いについては Pólya [Ply37] ，Harary–Palmer [HP73] などを参照してください． 置換群の基本事項については Cameron [Cam95] も標準的です．
§2 群作用 まず，群作用の定義から始めます． ここでは有限群だけを扱います． なお，符号理論では G G G G G G
定義2.1．
G G G Ω \Omega Ω G G G Ω \Omega Ω 作用する (act ) とは， 各 g ∈ G g \in G g ∈ G x ∈ Ω x \in \Omega x ∈ Ω g ⋅ x ∈ Ω g \cdot x \in \Omega g ⋅ x ∈ Ω
単位元 1 G ∈ G 1_{G} \in G 1 G ∈ G x ∈ Ω x \in \Omega x ∈ Ω
1 G ⋅ x = x 1_{G} \cdot {x} = x 1 G ⋅ x = x が成り立つ．
任意の g , h ∈ G g, h \in G g , h ∈ G x ∈ Ω x \in \Omega x ∈ Ω
g ⋅ ( h ⋅ x ) = ( g h ) ⋅ x g \cdot (h \cdot x) = (gh) \cdot x g ⋅ ( h ⋅ x ) = ( g h ) ⋅ x が成り立つ．
このとき，Ω \Omega Ω G G G G G G
群作用は，「群の元を集合の対称性として実現する」ことです． 実際，各 g ∈ G g \in G g ∈ G
Ω → Ω , x ↦ g ⋅ x \Omega \to \Omega,
\qquad
x \mapsto g \cdot x Ω → Ω , x ↦ g ⋅ x が定まります．この写像は全単射です． 逆写像は x ↦ g − 1 ⋅ x x \mapsto g^{-1} \cdot x x ↦ g − 1 ⋅ x G G G Ω \Omega Ω
例2.2（対称群の自然な作用）．
Ω = { 1 , 2 , … , n } \Omega = \{ 1, 2, \dots, n \} Ω = { 1 , 2 , … , n } Ω \Omega Ω Sym ( Ω ) \Sym(\Omega) Sym ( Ω ) Sym ( Ω ) \Sym(\Omega) Sym ( Ω ) Ω \Omega Ω σ ∈ Sym ( Ω ) \sigma \in \Sym(\Omega) σ ∈ Sym ( Ω ) i ∈ Ω i \in \Omega i ∈ Ω
σ ⋅ i ≔ σ ( i ) \sigma \cdot i \coloneqq \sigma(i) σ ⋅ i : = σ ( i ) と定めればよい．
例2.3（巡回群の正多角形への作用）．
正 m m m
Ω = { 0 , 1 , … , m − 1 } \Omega = \{ 0, 1, \dots, m - 1 \} Ω = { 0 , 1 , … , m − 1 } と番号づける． 巡回群 Z / m Z \mathbb{Z}/m\mathbb{Z} Z / m Z Ω \Omega Ω
a ‾ ⋅ i = i + a ( m o d m ) \overline{a} \cdot i = i + a \pmod{m} a ⋅ i = i + a ( mod m ) である．
符号理論に近い例も見ておきます．
例2.4（符号による平行移動作用）．
V = F q E V = \F_{q}^{E} V = F q E C ≤ V C \leq V C ≤ V C C C C C C V V V
c ⋅ v = v + c ( c ∈ C , v ∈ V ) . c \cdot v = v + c
\qquad(c \in C,\, v \in V). c ⋅ v = v + c ( c ∈ C , v ∈ V ) . この作用の軌道は C C C
v + C = { v + c : c ∈ C } v + C = \{ v + c: c \in C\} v + C = { v + c : c ∈ C } である．
この例では，群作用によって V V V
§3 軌道，不動点，安定化群 群作用で最初に見るべきものは，軌道と不動点です．
定義3.1．
G G G Ω \Omega Ω x ∈ Ω x \in \Omega x ∈ Ω
Orb G ( x ) ≔ { g ⋅ x : g ∈ G } \Orb_{G}(x)
\coloneqq
\{ g \cdot x: g \in G \} Orb G ( x ) : = { g ⋅ x : g ∈ G } を x x x 軌道 (orbit ) という． また，
Stab G ( x ) ≔ { g ∈ G : g ⋅ x = x } \Stab_{G}(x)
\coloneqq
\{ g \in G:g \cdot x = x \} Stab G ( x ) : = { g ∈ G : g ⋅ x = x } を x x x 安定化群 (stabilizer ) という． さらに，g ∈ G g \in G g ∈ G
Fix Ω ( g ) ≔ { x ∈ Ω : g ⋅ x = x } \Fix_{\Omega}(g)
\coloneqq
\{ x \in \Omega: g \cdot x = x \} Fix Ω ( g ) : = { x ∈ Ω : g ⋅ x = x } を g g g 不動点集合 (fixed point set ) という．
軌道は，点 x x x x x x g g g Stab G ( x ) \Stab_{G}(x) Stab G ( x ) G G G x x x x x x x x x x x x x x x
定理3.2（軌道・安定化群定理）．
有限群 G G G Ω \Omega Ω x ∈ Ω x \in \Omega x ∈ Ω
∣ Orb G ( x ) ∣ ∣ Stab G ( x ) ∣ = ∣ G ∣ \card{\Orb_G(x)}\card{\Stab_G(x)} = \card{G} ∣ Orb G ( x ) ∣ ∣ Stab G ( x ) ∣ = ∣ G ∣ が成り立つ．
証明 写像
G → Orb G ( x ) , g ↦ g ⋅ x G \to \Orb_{G}(x),
\qquad
g \mapsto g \cdot x G → Orb G ( x ) , g ↦ g ⋅ x を考える． g ⋅ x = h ⋅ x g \cdot x = h \cdot x g ⋅ x = h ⋅ x
h − 1 g ⋅ x = x h^{-1}g \cdot x = x h − 1 g ⋅ x = x と同値である． つまり h − 1 g ∈ Stab G ( x ) h^{-1}g \in \Stab_{G}(x) h − 1 g ∈ Stab G ( x ) Orb G ( x ) \Orb_{G}(x) Orb G ( x ) Stab G ( x ) \Stab_{G}(x) Stab G ( x )
∣ G ∣ = ∣ Orb G ( x ) ∣ ∣ Stab G ( x ) ∣ \card{G}
= \card{\Orb_{G}(x)}\card{\Stab_{G}(x)} ∣ G ∣ = ∣ Orb G ( x ) ∣ ∣ Stab G ( x ) ∣ となる．
証明終わり □
この定理は，後でBurnsideの補題を証明するときに使います． 直感的には，軌道が大きい点ほど，その点を固定する対称性は少ない，ということを表しています．
§4 Burnsideの補題 群作用によって集合 Ω \Omega Ω
定理4.1（Burnsideの補題）．
有限群 G G G Ω \Omega Ω
∣ Ω / G ∣ = 1 ∣ G ∣ ∑ g ∈ G ∣ Fix Ω ( g ) ∣ \card{\Omega/G}
=
\frac{1}{\card{G}}
\sum_{g \in G}\card{\Fix_{\Omega}(g)} ∣ Ω/ G ∣ = ∣ G ∣ 1 g ∈ G ∑ ∣ Fix Ω ( g ) ∣ で与えられる． ここで Ω / G \Omega/G Ω/ G
証明 集合
S = { ( g , x ) ∈ G × Ω : g ⋅ x = x } S =
\{ (g, x) \in G \times \Omega: g \cdot x = x \} S = {( g , x ) ∈ G × Ω : g ⋅ x = x } を二通りに数える．
まず g ∈ G g \in G g ∈ G g ⋅ x = x g \cdot x = x g ⋅ x = x x x x ∣ Fix Ω ( g ) ∣ \card{\Fix_{\Omega}(g)} ∣ Fix Ω ( g ) ∣
∣ S ∣ = ∑ g ∈ G ∣ Fix Ω ( g ) ∣ . \card{S} = \sum_{g \in G}\card{\Fix_{\Omega}(g)}. ∣ S ∣ = g ∈ G ∑ ∣ Fix Ω ( g ) ∣ . 次に x ∈ Ω x \in \Omega x ∈ Ω g ⋅ x = x g \cdot x = x g ⋅ x = x g g g ∣ Stab G ( x ) ∣ \card{\Stab_{G}(x)} ∣ Stab G ( x ) ∣
∣ S ∣ = ∑ x ∈ Ω ∣ Stab G ( x ) ∣ . \card{S}
= \sum_{x \in \Omega}\card{\Stab_{G}(x)}. ∣ S ∣ = x ∈ Ω ∑ ∣ Stab G ( x ) ∣ . ここで Ω \Omega Ω O \mathcal{O} O x ∈ O x\in \mathcal{O} x ∈ O
∣ Stab G ( x ) ∣ = ∣ G ∣ ∣ O ∣ \card{\Stab_{G}(x)} = \frac{\card{G}}{\card{\mathcal{O}}} ∣ Stab G ( x ) ∣ = ∣ O ∣ ∣ G ∣ である．したがって，この軌道からの寄与は
∑ x ∈ O ∣ Stab G ( x ) ∣ = ∣ O ∣ ⋅ ∣ G ∣ ∣ O ∣ = ∣ G ∣ \sum_{x \in \mathcal{O}}\card{\Stab_{G}(x)}
=
\card{\mathcal{O}} \cdot \frac{\card{G}}{\card{\mathcal{O}}}
=
\card{G} x ∈ O ∑ ∣ Stab G ( x ) ∣ = ∣ O ∣ ⋅ ∣ O ∣ ∣ G ∣ = ∣ G ∣ である． 軌道一つにつき ∣ G ∣ \card{G} ∣ G ∣
∣ S ∣ = ∣ Ω / G ∣ ∣ G ∣ \card{S} = \card{\Omega/G}\card{G} ∣ S ∣ = ∣ Ω/ G ∣ ∣ G ∣ となる．
二通りの式を比較して ∣ G ∣ \card{G} ∣ G ∣
証明終わり □
Burnsideの補題の要点は，
軌道数は不動点数の平均である．
という一文に尽きます． この「群作用に沿って平均する」という発想が，巡回指数やPólya計数につながります． MacWilliams恒等式の証明でも平均が現れます． ただし，Burnsideの補題そのものが双対符号 C ⊥ C^{\perp} C ⊥ g ∈ G g \in G g ∈ G C C C c ∈ C c \in C c ∈ C ψ ( u ⋅ c ) \psi(u \cdot c) ψ ( u ⋅ c ) u ∈ C ⊥ u \in C^{\perp} u ∈ C ⊥
§5 置換の巡回分解と巡回指数 ここから巡回指数に入ります． 有限集合 Ω \Omega Ω σ ∈ Sym ( Ω ) \sigma \in \Sym(\Omega) σ ∈ Sym ( Ω )
σ = ( 1 3 5 ) ( 2 4 ) \sigma = (1 \; 3 \; 5)(2 \; 4) σ = ( 1 3 5 ) ( 2 4 ) であれば，3 3 3 2 2 2 1 1 1
定義5.1．
Ω \Omega Ω σ ∈ Sym ( Ω ) \sigma \in \Sym(\Omega) σ ∈ Sym ( Ω ) ℓ ≥ 1 \ell \geq 1 ℓ ≥ 1 σ \sigma σ ℓ \ell ℓ
c ℓ ( σ ) c_{\ell}(\sigma) c ℓ ( σ ) と書く． 列 ( c 1 ( σ ) , c 2 ( σ ) , … ) (c_{1}(\sigma), c_{2}(\sigma),\dots) ( c 1 ( σ ) , c 2 ( σ ) , … ) σ \sigma σ 巡回型 (cycle type ) という．
もちろん Ω \Omega Ω ℓ \ell ℓ c ℓ ( σ ) = 0 c_{\ell}(\sigma) = 0 c ℓ ( σ ) = 0
∑ ℓ ≥ 1 ℓ c ℓ ( σ ) = ∣ Ω ∣ \sum_{\ell \geq 1} \ell c_{\ell}(\sigma) = \card{\Omega} ℓ ≥ 1 ∑ ℓ c ℓ ( σ ) = ∣ Ω ∣ です．
定義5.2（巡回指数）．
有限群 G G G Ω \Omega Ω g ∈ G g \in G g ∈ G Ω \Omega Ω c ℓ ( g ) c_{\ell}(g) c ℓ ( g ) G G G 巡回指数 (cycle index ) を
Z G , Ω ( s 1 , s 2 , … ) ≔ 1 ∣ G ∣ ∑ g ∈ G ∏ ℓ ≥ 1 s ℓ c ℓ ( g ) \Zcycle_{G,\Omega}(s_{1}, s_{2}, \dots)
\coloneqq
\frac{1}{\card{G}}
\sum_{g \in G} \prod_{\ell \geq 1} s_{\ell}^{c_{\ell}(g)} Z G , Ω ( s 1 , s 2 , … ) : = ∣ G ∣ 1 g ∈ G ∑ ℓ ≥ 1 ∏ s ℓ c ℓ ( g ) で定める．
本稿では，群の元にわたる平均として巡回指数を定義しています． 厳密には，巡回指数は抽象群 G G G G G G Ω \Omega Ω 1 / ∣ G ∣ 1/\card{G} 1/ ∣ G ∣
例5.3（三角形の回転群）．
Ω \Omega Ω G = Z / 3 Z G = \mathbb{Z}/3\mathbb{Z} G = Z /3 Z Ω \Omega Ω c 1 = 3 c_{1} = 3 c 1 = 3 3 3 3 c 3 = 1 c_3=1 c 3 = 1
Z G , Ω ( s 1 , s 2 , s 3 , … ) = 1 3 ( s 1 3 + 2 s 3 ) \Zcycle_{G,\Omega}(s_{1}, s_{2}, s_{3}, \dots)
=
\frac{1}{3}\left( s_{1}^{3} + 2s_{3} \right) Z G , Ω ( s 1 , s 2 , s 3 , … ) = 3 1 ( s 1 3 + 2 s 3 ) である．
例えば三角形の頂点を二色で塗るなら，巡回指数の変数に s 1 = 2 s_{1}=2 s 1 = 2 s 3 = 2 s_{3}=2 s 3 = 2 1 1 1 3 3 3
1 3 ( 2 3 + 2 ⋅ 2 ) = 4 \frac{1}{3}\left(2^{3}+2\cdot 2\right)=4 3 1 ( 2 3 + 2 ⋅ 2 ) = 4 となります． つまり，巡回指数に代入すると，回転で同じと見なす二色彩色が四通りあることが分かります．
巡回指数は，群作用の情報を完全に記録しているわけではありません． しかし，彩色の数え上げに必要な情報を非常に効率よく圧縮しています． 次節でこの点を見ます．
§6 Pólya計数 Pólya計数は，群作用の下で同じと見なす彩色を数える方法です． ここでは重み付きの形を述べます．
有限集合 Ω \Omega Ω A A A f : Ω → A f \colon \Omega \to A f : Ω → A G G G Ω \Omega Ω G G G A Ω A^{\Omega} A Ω
( g ⋅ f ) ( x ) = f ( g − 1 ⋅ x ) (g \cdot f)(x) = f(g^{-1} \cdot x) ( g ⋅ f ) ( x ) = f ( g − 1 ⋅ x ) で定めます．これは，場所を g − 1 g^{-1} g − 1 g − 1 g^{-1} g − 1 g ⋅ ( h ⋅ f ) = ( g h ) ⋅ f g\cdot(h\cdot f)=(gh)\cdot f g ⋅ ( h ⋅ f ) = ( g h ) ⋅ f
各色 a ∈ A a \in A a ∈ A w a w_{a} w a f f f 重み単項式 (weight monomial ) を
mon ( f ) = ∏ x ∈ Ω w f ( x ) \mon(f)
= \prod_{x \in \Omega} w_{f(x)} mon ( f ) = x ∈ Ω ∏ w f ( x ) で定めます．この重み単項式は，G G G g g g Ω \Omega Ω O \mathcal{O} O mon ( O ) \mon(\mathcal{O}) mon ( O )
定理6.1（Pólyaの数え上げ定理）．
有限群 G G G Ω \Omega Ω A A A a ∈ A a \in A a ∈ A w a w_{a} w a ℓ ≥ 1 \ell \geq 1 ℓ ≥ 1
P ℓ = ∑ a ∈ A w a ℓ P_{\ell} = \sum_{a \in A} w_{a}^{\ell} P ℓ = a ∈ A ∑ w a ℓ とおく． このとき，彩色の軌道重み単項式の和は
∑ O ∈ A Ω / G mon ( O ) = Z G , Ω ( P 1 , P 2 , P 3 , … ) \sum_{\mathcal{O} \in A^{\Omega}/G}\mon(\mathcal{O})
= \Zcycle_{G,\Omega}(P_{1}, P_{2}, P_{3}, \dots) O ∈ A Ω / G ∑ mon ( O ) = Z G , Ω ( P 1 , P 2 , P 3 , … ) で与えられる．
証明 Burnsideの補題を重み付きで使う． 重み単項式は軌道上で一定なので，軌道重み単項式の和は
1 ∣ G ∣ ∑ g ∈ G ∑ f ∈ A Ω g ⋅ f = f mon ( f ) \frac{1}{\card{G}}
\sum_{g \in G}
\sum_{\substack{f \in A^{\Omega} \\ g \cdot f = f}}
\mon(f) ∣ G ∣ 1 g ∈ G ∑ f ∈ A Ω g ⋅ f = f ∑ mon ( f ) に等しい． 実際，一つの軌道 O \mathcal{O} O f f f ∣ Stab G ( f ) ∣ \card{\Stab_{G}(f)} ∣ Stab G ( f ) ∣
1 ∣ G ∣ ∣ O ∣ ∣ Stab G ( f ) ∣ mon ( f ) = mon ( O ) \frac{1}{\card{G}}
\card{\mathcal{O}}\card{\Stab_G(f)}\mon(f)
=
\mon(\mathcal{O}) ∣ G ∣ 1 ∣ O ∣ ∣ Stab G ( f ) ∣ mon ( f ) = mon ( O ) である．
次に g ∈ G g \in G g ∈ G g g g f f f g ⋅ f = f g \cdot f = f g ⋅ f = f f f f g g g ℓ \ell ℓ a ∈ A a \in A a ∈ A w a ℓ w_{a}^{\ell} w a ℓ ℓ \ell ℓ
P ℓ = ∑ a ∈ A w a ℓ P_{\ell} = \sum_{a \in A} w_{a}^{\ell} P ℓ = a ∈ A ∑ w a ℓ である． g g g ℓ \ell ℓ c ℓ ( g ) c_{\ell}(g) c ℓ ( g ) g g g
∏ ℓ ≥ 1 P ℓ c ℓ ( g ) \prod_{\ell \geq 1} P_{\ell}^{c_{\ell}(g)} ℓ ≥ 1 ∏ P ℓ c ℓ ( g ) である． これを g ∈ G g \in G g ∈ G
1 ∣ G ∣ ∑ g ∈ G ∏ ℓ ≥ 1 P ℓ c ℓ ( g ) = Z G , Ω ( P 1 , P 2 , P 3 , … ) \frac{1}{\card{G}}
\sum_{g \in G}\prod_{\ell \geq 1} P_{\ell}^{c_{\ell}(g)}
=
\Zcycle_{G,\Omega}(P_{1}, P_{2}, P_{3}, \dots) ∣ G ∣ 1 g ∈ G ∑ ℓ ≥ 1 ∏ P ℓ c ℓ ( g ) = Z G , Ω ( P 1 , P 2 , P 3 , … ) となる．
証明終わり □
この定理が示しているのは，巡回指数が「固定される彩色の重み単項式の和」を一括して記録しているということです． 置換 g g g ℓ \ell ℓ w a ℓ w_{a}^{\ell} w a ℓ
ここまでの Burnside の補題と Pólya計数は，後で使う巡回指数が「群の元にわたる平均」として何を記録しているかを理解するための準備です． 以下のMacWilliams恒等式の証明では，Pólya計数定理そのものを直接適用するわけではありません． むしろ，巡回指数的な平均表示を符号から作った置換群に適用し，最後に加法指標の直交性で双対符号を取り出します．
§7 符号から置換群を作る ここから符号理論に戻ります． 線形符号 C ≤ F q E C \leq \F_{q}^{E} C ≤ F q E q = p m q = p^{m} q = p m p p p
先ほどの例では C C C V = F q E V=\F_q^E V = F q E V = F q E V=\F_q^E V = F q E C C C { e } × F q \{e\}\times\F_q { e } × F q V V V Ω C = E × F q \Omega_C=E\times\F_q Ω C = E × F q e e e F q \F_q F q { e } × F q \{e\}\times\F_q { e } × F q c e c_e c e
集合
Ω C ≔ E × F q \Omega_{C}
\coloneqq
E\times \F_{q} Ω C : = E × F q を考えます． これは，各座標 e ∈ E e \in E e ∈ E F q \F_q F q
E × F q → E , ( e , a ) ↦ e E\times\F_q \to E,
\qquad
(e,a)\mapsto e E × F q → E , ( e , a ) ↦ e のもとで，e e e { e } × F q \{e\}\times\F_q { e } × F q e e e c = ( c e ) e ∈ E ∈ C c = (c_{e})_{e \in E} \in C c = ( c e ) e ∈ E ∈ C Ω C \Omega_{C} Ω C σ c \sigma_{c} σ c
σ c ( e , a ) = ( e , a + c e ) ( e ∈ E , a ∈ F q ) \sigma_{c}(e, a) = (e, a + c_{e})
\qquad(e \in E,\, a \in \F_{q}) σ c ( e , a ) = ( e , a + c e ) ( e ∈ E , a ∈ F q ) で定めます． つまり，e e e { e } × F q \{e\}\times\F_q { e } × F q F q \F_{q} F q c e c_{e} c e
命題7.1．
写像
C → Sym ( Ω C ) , c ↦ σ c C \to \Sym(\Omega_{C}),
\qquad
c \mapsto \sigma_{c} C → Sym ( Ω C ) , c ↦ σ c は加法群としての C C C
G ( C ) ≔ { σ c : c ∈ C } G(C) \coloneqq \{ \sigma_{c} : c \in C \} G ( C ) : = { σ c : c ∈ C } は C C C
証明 c , d ∈ C c, d \in C c , d ∈ C ( e , a ) ∈ Ω C (e, a) \in \Omega_{C} ( e , a ) ∈ Ω C
σ c ( σ d ( e , a ) ) = σ c ( e , a + d e ) = ( e , a + d e + c e ) = σ c + d ( e , a ) \sigma_{c}(\sigma_{d}(e, a))
= \sigma_{c}(e, a + d_{e})
= (e, a + d_{e} + c_{e})
= \sigma_{c+d}(e,a) σ c ( σ d ( e , a )) = σ c ( e , a + d e ) = ( e , a + d e + c e ) = σ c + d ( e , a ) である．したがって σ c σ d = σ c + d \sigma_{c}\sigma_{d} = \sigma_{c+d} σ c σ d = σ c + d
また，σ c \sigma_{c} σ c e ∈ E e \in E e ∈ E a ∈ F q a \in \F_{q} a ∈ F q a + c e = a a + c_{e} = a a + c e = a c e = 0 c_{e} = 0 c e = 0 e e e c = 0 c = 0 c = 0
証明終わり □
以下では，この単射によって G ( C ) G(C) G ( C ) c ∈ C c \in C c ∈ C G ( C ) G(C) G ( C ) C C C
この置換群 G ( C ) G(C) G ( C ) c e = 0 c_{e} = 0 c e = 0 a ↦ a + c e a \mapsto a + c_{e} a ↦ a + c e F q \F_{q} F q q q q 1 1 1 c e ≠ 0 c_{e} \neq 0 c e = 0 a ↦ a + c e a \mapsto a + c_{e} a ↦ a + c e F q \F_{q} F q c e c_{e} c e p p p p p p F q \F_{q} F q q / p q/p q / p p p p q q q p p p F q \F_q F q F p \F_p F p m m m d d d
0 , d , 2 d , … , ( p − 1 ) d 0,\ d,\ 2d,\ \dots,\ (p-1)d 0 , d , 2 d , … , ( p − 1 ) d という長さ p p p F q \F_q F q q / p q/p q / p p p p q = 4 q=4 q = 4 p = 2 p=2 p = 2 a ↦ a + d a\mapsto a+d a ↦ a + d F 4 \F_4 F 4 4 4 4 4 4 4 2 2 2
定理7.2（符号の置換群の巡回指数）．
C ≤ F q E C \leq \F_{q}^{E} C ≤ F q E q = p m q = p^{m} q = p m G ( C ) G(C) G ( C )
Z G ( C ) , Ω C ( s 1 , s 2 , … ) = 1 ∣ C ∣ ∑ c ∈ C s 1 q ( n − wt ( c ) ) s p ( q / p ) wt ( c ) (7.1) \Zcycle_{G(C),\Omega_C}(s_{1}, s_{2}, \dots)
=
\frac{1}{\card{C}}
\sum_{c \in C}
s_{1}^{q(n - \wt(c))} s_{p}^{(q/p)\wt(c)}
\tag{7.1} Z G ( C ) , Ω C ( s 1 , s 2 , … ) = ∣ C ∣ 1 c ∈ C ∑ s 1 q ( n − wt ( c )) s p ( q / p ) wt ( c ) ( 7.1 ) である．
証明 c ∈ C c \in C c ∈ C c e = 0 c_{e} = 0 c e = 0 e e e { e } × F q \{ e \} \times \F_{q} { e } × F q q q q 1 1 1 n − wt ( c ) n - \wt(c) n − wt ( c ) 1 1 1 q ( n − wt ( c ) ) q(n - \wt(c)) q ( n − wt ( c ))
一方，c e ≠ 0 c_{e} \neq 0 c e = 0 e e e { e } × F q \{ e \} \times \F_{q} { e } × F q q / p q/p q / p p p p wt ( c ) \wt(c) wt ( c ) p p p ( q / p ) wt ( c ) (q/p)\wt(c) ( q / p ) wt ( c )
よって σ c \sigma_{c} σ c
s 1 q ( n − wt ( c ) ) s p ( q / p ) wt ( c ) s_{1}^{q(n - \wt(c))} s_{p}^{(q/p)\wt(c)} s 1 q ( n − wt ( c )) s p ( q / p ) wt ( c ) である．これを c ∈ C c \in C c ∈ C Z G ( C ) , Ω C ( s 1 , s 2 , … ) = 1 ∣ C ∣ ∑ c ∈ C s 1 q ( n − wt ( c ) ) s p ( q / p ) wt ( c ) (7.1) \Zcycle_{G(C),\Omega_C}(s_{1}, s_{2}, \dots)
=
\frac{1}{\card{C}}
\sum_{c \in C}
s_{1}^{q(n - \wt(c))} s_{p}^{(q/p)\wt(c)}
\tag{7.1} Z G ( C ) , Ω C ( s 1 , s 2 , … ) = ∣ C ∣ 1 c ∈ C ∑ s 1 q ( n − wt ( c )) s p ( q / p ) wt ( c ) ( 7.1 )
証明終わり □
このように，符号から得られる置換群の普通の巡回指数が Hamming重み多項式を記録するという見方は， Cameron [Cam02] に現れるものです． 本稿では，この見方を，後で完全重み多項式に対応するように 平行移動量付きに精密化します．
定理 7.2（符号の置換群の巡回指数） C ≤ F q E C \leq \F_{q}^{E} C ≤ F q E q = p m q = p^{m} q = p m G ( C ) G(C) G ( C ) Z G ( C ) , Ω C ( s 1 , s 2 , … ) = 1 ∣ C ∣ ∑ c ∈ C s 1 q ( n − wt ( c ) ) s p ( q / p ) wt ( c ) (7.1) \Zcycle_{G(C),\Omega_C}(s_{1}, s_{2}, \dots)
=
\frac{1}{\card{C}}
\sum_{c \in C}
s_{1}^{q(n - \wt(c))} s_{p}^{(q/p)\wt(c)}
\tag{7.1} Z G ( C ) , Ω C ( s 1 , s 2 , … ) = ∣ C ∣ 1 c ∈ C ∑ s 1 q ( n − wt ( c )) s p ( q / p ) wt ( c ) ( 7.1 ) である． G ( C ) G(C) G ( C ) C C C
U 0 = s 1 q , U 1 = s p q / p U_{0} = s_{1}^{q},
\qquad
U_{1} = s_{p}^{q/p} U 0 = s 1 q , U 1 = s p q / p とおきます． すると Z G ( C ) , Ω C ( s 1 , s 2 , … ) = 1 ∣ C ∣ ∑ c ∈ C s 1 q ( n − wt ( c ) ) s p ( q / p ) wt ( c ) (7.1) \Zcycle_{G(C),\Omega_C}(s_{1}, s_{2}, \dots)
=
\frac{1}{\card{C}}
\sum_{c \in C}
s_{1}^{q(n - \wt(c))} s_{p}^{(q/p)\wt(c)}
\tag{7.1} Z G ( C ) , Ω C ( s 1 , s 2 , … ) = ∣ C ∣ 1 c ∈ C ∑ s 1 q ( n − wt ( c )) s p ( q / p ) wt ( c ) ( 7.1 )
Z G ( C ) , Ω C ( s 1 , s 2 , … ) = 1 ∣ C ∣ W C ( U 0 , U 1 ) \Zcycle_{G(C),\Omega_C}(s_{1}, s_{2}, \dots)
=
\frac{1}{\card{C}} W_{C}(U_{0}, U_{1}) Z G ( C ) , Ω C ( s 1 , s 2 , … ) = ∣ C ∣ 1 W C ( U 0 , U 1 ) と書けます． つまり，普通の巡回指数では s 1 s_{1} s 1 s p s_{p} s p U 0 U_{0} U 0 U 1 U_{1} U 1
1 ∣ C ∣ W C ( U 0 , U 1 ) \frac{1}{\card{C}} W_{C}(U_{0}, U_{1}) ∣ C ∣ 1 W C ( U 0 , U 1 ) が得られます． ここでは s 1 s_{1} s 1 s p s_{p} s p U 0 , U 1 U_{0}, U_{1} U 0 , U 1
つまり，符号語のHamming重みは，対応する置換の巡回型として読むことができます． 零座標は q q q q / p q/p q / p p p p
§8 普通の巡回指数から完全巡回指数へ 前節で見た普通の巡回指数は，Hamming重み多項式を記録するには十分です． しかし，普通の巡回指数には一つ弱点があります． 普通の巡回指数は，置換を単なる置換として見て，サイクル長だけを記録します． そのため，各非零成分 c e ≠ 0 c_{e} \neq 0 c e = 0
例えば，q = 5 q = 5 q = 5 c e = 1 c_{e} = 1 c e = 1 c e = 2 c_{e} = 2 c e = 2 a ↦ a + c e a \mapsto a + c_{e} a ↦ a + c e 5 5 5 1 1 1 2 2 2
ここで残したいのは，Ω C = E × F q \Omega_C=E\times\F_q Ω C = E × F q { e } × F q \{e\}\times\F_q { e } × F q c e c_e c e σ c \sigma_c σ c
そこで，各 a ∈ F q a \in \F_{q} a ∈ F q x a x_{a} x a x a x_a x a Z G , Ω \Zcycle_{G,\Omega} Z G , Ω c ∈ C c \in C c ∈ C
∏ e ∈ E x c e \prod_{e \in E} x_{c_{e}} e ∈ E ∏ x c e を対応させます． これは，各座標ファイバー { e } × F q \{e\}\times\F_q { e } × F q a ↦ a + c e a \mapsto a + c_{e} a ↦ a + c e
定義8.1（完全重み多項式）．
線形符号 C ≤ F q E C \leq \F_{q}^{E} C ≤ F q E 完全重み多項式 (complete weight enumerator ) を
cwe C ( ( x a ) a ∈ F q ) = ∑ c ∈ C ∏ e ∈ E x c e \cwe_{C}((x_{a})_{a \in \F_{q}})
=
\sum_{c \in C} \prod_{e \in E} x_{c_{e}} cwe C (( x a ) a ∈ F q ) = c ∈ C ∑ e ∈ E ∏ x c e で定める．
完全重み多項式版MacWilliams恒等式そのものの標準的な扱いについては， MacWilliams–Sloane [MS77, Chapters 5 and 19] を参照してください． ただし，本稿で強調するのは，この恒等式を 符号から作る平行移動置換群の完全巡回指数として読む点です．
定義8.2（完全巡回指数）．
線形符号 C ≤ F q E C \leq \F_{q}^{E} C ≤ F q E
cZ C ( ( x a ) a ∈ F q ) = 1 ∣ C ∣ ∑ c ∈ C ∏ e ∈ E x c e \cZ_{C}((x_{a})_{a \in \F_{q}})
=
\frac{1}{\card{C}}
\sum_{c \in C} \prod_{e \in E} x_{c_{e}} cZ C (( x a ) a ∈ F q ) = ∣ C ∣ 1 c ∈ C ∑ e ∈ E ∏ x c e と定める． これを本稿では C C C 完全巡回指数 (complete cycle index ) と呼ぶ．
この定義では
cwe C ( ( x a ) a ∈ F q ) = ∣ C ∣ cZ C ( ( x a ) a ∈ F q ) \cwe_C((x_{a})_{a \in \F_{q}})
=
\card{C}\,\cZ_{C}((x_{a})_{a \in \F_{q}}) cwe C (( x a ) a ∈ F q ) = ∣ C ∣ cZ C (( x a ) a ∈ F q ) です． つまり，完全巡回指数は完全重み多項式を群の元にわたる平均として正規化したものです． 注意しておくと，本稿でいう完全巡回指数は，一般の置換群に対して標準的に定義される普通の巡回指数そのものではありません． 普通の巡回指数が置換のサイクル長だけを見るのに対して，本稿の cZ C \cZ_C cZ C { e } × F q \{e\}\times\F_q { e } × F q c e c_e c e cZ C \cZ_C cZ C c c c c e c_e c e s ( h , i ) s(h,i) s ( h , i ) cZ C \cZ_C cZ C ∣ C ∣ \card{C} ∣ C ∣ [MO19] が扱う完全巡回指数と完全重み多項式の関係に沿っています． 本稿では，そのうちMacWilliams恒等式の変数変換に必要な部分だけを取り出して説明します．
Hamming重み多項式は，完全重み多項式の特殊化です． 実際，
x 0 = X , x a = Y ( a ≠ 0 ) x_{0} = X,
\qquad
x_{a} = Y \quad(a \neq 0) x 0 = X , x a = Y ( a = 0 ) と置けば，任意の c ∈ C c \in C c ∈ C
∏ e ∈ E x c e = X n − wt ( c ) Y wt ( c ) \prod_{e \in E} x_{c_{e}}
= X^{n - \wt(c)} Y^{\wt(c)} e ∈ E ∏ x c e = X n − wt ( c ) Y wt ( c ) となるので，
cwe C ( ( x a ) ) ∣ x 0 = X , x a = Y ( a ≠ 0 ) = W C ( X , Y ) \cwe_{C}((x_{a}))\bigg|_{x_{0} = X,\, x_{a} = Y \, (a \neq 0)}
= W_{C}(X,Y) cwe C (( x a )) x 0 = X , x a = Y ( a = 0 ) = W C ( 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 は，完全重み多項式のレベルではもっと対称的な変換から出てくるということです． その変換は，有限体 F q \F_q F q ( F q , + ) (\F_q,+) ( F q , + )
§9 一座標の指標表変換 ここから先では，有限集合 F q \F_q F q ( F q , + ) (\F_q,+) ( F q , + )
MacWilliams恒等式を完全重み多項式のレベルで証明するために， 有限体 F q \F_{q} F q ψ : F q → C × \psi \colon \F_{q} \to \C^{\times} ψ : F q → C ×
ψ ( a + b ) = ψ ( a ) ψ ( b ) \psi(a + b) = \psi(a)\psi(b) ψ ( a + b ) = ψ ( a ) ψ ( b ) を満たし，かつ恒等的に 1 1 1 q = p q=p q = p ψ ( a ) = exp ( 2 π − 1 a / p ) \psi(a)=\exp(2\pi \sqrt{-1}a/p) ψ ( a ) = exp ( 2 π − 1 a / p ) q = p m q=p^m q = p m F q \F_q F q F p \F_p F p
ψ ( 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 ) ) と定めることで，そのような加法指標が得られます． ここで Tr F q / F p ( a ) \Tr_{\F_q/\F_p}(a) Tr F q / F p ( a ) F p \F_p F p 0 , 1 , … , p − 1 0,1,\dots,p-1 0 , 1 , … , p − 1
有限群上のFourier解析や指標表の標準的な背景については， Terras [Ter99] を参照してください． また，有限体のトレース写像と加法指標については Lidl–Niederreiter [LN83] が標準的です．
本稿で使う性質は次の一つだけです．
補題9.1．
b ∈ F q b \in \F_{q} b ∈ F q
∑ a ∈ F q ψ ( a b ) = { q , b = 0 , 0 , b ≠ 0 \sum_{a \in \F_{q}}\psi(ab)
=
\begin{cases}
q, & b = 0,\\
0, & b \neq 0
\end{cases} a ∈ F q ∑ ψ ( ab ) = { q , 0 , b = 0 , b = 0 が成り立つ．
証明 b = 0 b = 0 b = 0 a ∈ F q a \in \F_{q} a ∈ F q ψ ( a b ) = ψ ( 0 ) = 1 \psi(ab) = \psi(0) = 1 ψ ( ab ) = ψ ( 0 ) = 1 q q q
b ≠ 0 b \neq 0 b = 0 a ↦ a b a \mapsto ab a ↦ ab F q \F_{q} F q
∑ a ∈ F q ψ ( a b ) = ∑ t ∈ F q ψ ( t ) \sum_{a \in \F_{q}} \psi(ab)
= \sum_{t \in \F_{q}} \psi(t) a ∈ F q ∑ ψ ( ab ) = t ∈ F q ∑ ψ ( t ) である．右辺を S S S ψ \psi ψ d ∈ F q d \in \F_{q} d ∈ F q ψ ( d ) ≠ 1 \psi(d) \neq 1 ψ ( d ) = 1 t t t F q \F_{q} F q t + d t + d t + d F q \F_{q} F q
S = ∑ t ∈ F q ψ ( t + d ) = ∑ t ∈ F q ψ ( t ) ψ ( d ) = ψ ( d ) S . S
=
\sum_{t \in \F_{q}}\psi(t + d)
=
\sum_{t \in \F_{q}}\psi(t)\psi(d)
=
\psi(d)S. S = t ∈ F q ∑ ψ ( t + d ) = t ∈ F q ∑ ψ ( t ) ψ ( d ) = ψ ( d ) S . ψ ( d ) ≠ 1 \psi(d) \neq 1 ψ ( d ) = 1 S = 0 S = 0 S = 0
証明終わり □
次に，変数 x a x_{a} x a b ∈ F q b \in \F_{q} b ∈ F q
とおきます． これは，F q \F_{q} F q ( F q , + ) (\F_q,+) ( F q , + ) ( x a ) a ∈ F q (x_{a})_{a \in \F_{q}} ( x a ) a ∈ F q b ∈ F q b \in \F_q b ∈ F q
χ b ( a ) = ψ ( a b ) \chi_b(a)=\psi(ab) χ b ( a ) = ψ ( ab ) とおくと，χ b \chi_b χ b ( F q , + ) (\F_q,+) ( F q , + ) b b b F q \F_q F q b b b x b ∗ = ∑ a ψ ( a b ) x a x_b^\ast=\sum_a\psi(ab)x_a x b ∗ = ∑ a ψ ( ab ) x a ψ ( − a b ) \psi(-ab) ψ ( − ab ) ∑ c ∈ C ψ ( u ⋅ c ) \sum_{c\in C}\psi(u\cdot c) ∑ c ∈ C ψ ( u ⋅ c ) x b ∗ = ∑ a ψ ( a b ) x a x_b^\ast=\sum_a\psi(ab)x_a x b ∗ = ∑ a ψ ( ab ) x a a , b ∈ F q a, b \in \F_{q} a , b ∈ F q
H a , b = ψ ( a b ) H_{a, b} = \psi(ab) H a , b = ψ ( ab ) を考えると，x b ∗ ≔ ∑ a ∈ F q ψ ( a b ) x a (9.1) x_{b}^{\ast}
\coloneqq
\sum_{a \in \F_{q}} \psi(ab) x_{a}
\tag{9.1} x b ∗ : = a ∈ F q ∑ ψ ( ab ) x a ( 9.1 )
x b ∗ = ∑ a ∈ F q H a , b x a x_{b}^{\ast} = \sum_{a \in \F_{q}} H_{a, b} x_{a} x b ∗ = a ∈ F q ∑ H a , b x a と書けます．
Pólya計数では，巡回指数に
s ℓ ↦ ∑ a ∈ A w a ℓ s_{\ell} \mapsto \sum_{a \in A} w_{a}^{\ell} s ℓ ↦ a ∈ A ∑ w a ℓ を代入しました． ここでは，完全巡回指数に対して，加法群 ( F q , + ) (\F_q,+) ( F q , + )
§10 完全重み多項式版MacWilliams恒等式と完全巡回指数 完全重み多項式に対するMacWilliams恒等式を証明します． これは，完全巡回指数に対する変数変換の公式でもあります．
定理10.1（完全重み多項式版MacWilliams恒等式）．
C ≤ F q E C \leq \F_{q}^{E} C ≤ F q E b ∈ F q b \in \F_{q} b ∈ F q
x b ∗ = ∑ a ∈ F q ψ ( a b ) x a x_{b}^{\ast}
= \sum_{a \in \F_{q}}\psi(ab) x_{a} x b ∗ = a ∈ F q ∑ ψ ( ab ) x a と定める．このとき
cwe C ⊥ ( ( x a ) a ∈ F q ) = 1 ∣ C ∣ cwe C ( ( x b ∗ ) b ∈ F q ) (10.1) \cwe_{C^{\perp}}((x_{a})_{a \in \F_{q}})
=
\frac{1}{\card{C}}
\cwe_{C}((x_{b}^{\ast})_{b \in \F_{q}})
\tag{10.1} cwe C ⊥ (( x a ) a ∈ F q ) = ∣ C ∣ 1 cwe C (( x b ∗ ) b ∈ F q ) ( 10.1 ) が成り立つ．
証明 右辺の分子を展開する．
cwe C ( ( x b ∗ ) b ∈ F q ) = ∑ c ∈ C ∏ e ∈ E x c e ∗ = ∑ c ∈ C ∏ e ∈ E ( ∑ u e ∈ F q ψ ( u e c e ) x u e ) = ∑ c ∈ C ∑ u ∈ F q E ( ∏ e ∈ E ψ ( u e c e ) ) ∏ e ∈ E x u e . \begin{aligned}
\cwe_{C}((x_{b}^{\ast})_{b \in \F_{q}})
&=
\sum_{c \in C} \prod_{e \in E} x_{c_{e}}^\ast \\
&=
\sum_{c \in C} \prod_{e \in E}
\left(
\sum_{u_{e} \in \F_{q}} \psi(u_{e} c_{e}) x_{u_{e}}
\right) \\
&=
\sum_{c \in C}
\sum_{u \in \F_q^E}
\left(\prod_{e \in E} \psi(u_{e} c_{e}) \right)
\prod_{e \in E} x_{u_{e}}.
\end{aligned} cwe C (( x b ∗ ) b ∈ F q ) = c ∈ C ∑ e ∈ E ∏ x c e ∗ = c ∈ C ∑ e ∈ E ∏ u e ∈ F q ∑ ψ ( u e c e ) x u e = c ∈ C ∑ u ∈ F q E ∑ ( e ∈ E ∏ ψ ( u e c e ) ) e ∈ E ∏ x u e . 加法指標の性質より
∏ e ∈ E ψ ( u e c e ) = ψ ( ∑ e ∈ E u e c e ) = ψ ( u ⋅ c ) \prod_{e \in E} \psi(u_{e} c_{e})
=
\psi\left(\sum_{e \in E} u_{e} c_{e} \right)
=
\psi(u \cdot c) e ∈ E ∏ ψ ( u e c e ) = ψ ( e ∈ E ∑ u e c e ) = ψ ( u ⋅ c ) である．したがって和の順序を入れ替えると
cwe C ( ( x b ∗ ) ) = ∑ u ∈ F q E ( ∑ c ∈ C ψ ( u ⋅ c ) ) ∏ e ∈ E x u e . (10.2) \cwe_{C}((x_{b}^{\ast}))
=
\sum_{u \in \F_{q}^{E}}
\left(
\sum_{c \in C} \psi(u \cdot c)
\right)
\prod_{e \in E} x_{u_{e}}.
\tag{10.2} cwe C (( x b ∗ )) = u ∈ F q E ∑ ( c ∈ C ∑ ψ ( u ⋅ c ) ) e ∈ E ∏ x u e . ( 10.2 ) ここで内側の和を調べる． u ∈ C ⊥ u \in C^{\perp} u ∈ C ⊥ c ∈ C c \in C c ∈ C u ⋅ c = 0 u \cdot c = 0 u ⋅ c = 0
∑ c ∈ C ψ ( u ⋅ c ) = ∣ C ∣ \sum_{c \in C}\psi(u \cdot c) = \card{C} c ∈ C ∑ ψ ( u ⋅ c ) = ∣ C ∣ である． 一方，u ∉ C ⊥ u \notin C^{\perp} u ∈ / C ⊥ c 0 ∈ C c_{0} \in C c 0 ∈ C u ⋅ c 0 ≠ 0 u \cdot c_{0} \neq 0 u ⋅ c 0 = 0 d ≔ u ⋅ c 0 d \coloneqq u \cdot c_{0} d : = u ⋅ c 0 d ≠ 0 d \neq 0 d = 0
S = ∑ c ∈ C ψ ( u ⋅ c ) S = \sum_{c \in C} \psi(u \cdot c) S = c ∈ C ∑ ψ ( u ⋅ c ) を考える． λ ∈ F q \lambda \in \F_{q} λ ∈ F q C C C λ c 0 ∈ C \lambda c_{0} \in C λ c 0 ∈ C c c c C C C c + λ c 0 c + \lambda c_{0} c + λ c 0 C C C
S = ∑ c ∈ C ψ ( u ⋅ ( c + λ c 0 ) ) = ∑ c ∈ C ψ ( u ⋅ c ) ψ ( λ d ) = ψ ( λ d ) S . S
=
\sum_{c \in C} \psi(u \cdot (c + \lambda c_{0}))
=
\sum_{c \in C} \psi(u \cdot c) \psi(\lambda d)
=
\psi(\lambda d)S. S = c ∈ C ∑ ψ ( u ⋅ ( c + λ c 0 )) = c ∈ C ∑ ψ ( u ⋅ c ) ψ ( λ d ) = ψ ( λ d ) S . d ≠ 0 d \neq 0 d = 0 λ ↦ λ d \lambda \mapsto \lambda d λ ↦ λ d ψ \psi ψ λ ∈ F q \lambda \in \F_{q} λ ∈ F q ψ ( λ d ) ≠ 1 \psi(\lambda d) \neq 1 ψ ( λ d ) = 1 S = 0 S=0 S = 0
よって
∑ c ∈ C ψ ( u ⋅ c ) = { ∣ C ∣ , u ∈ C ⊥ , 0 , u ∉ C ⊥ . \sum_{c \in C} \psi(u \cdot c)
=
\begin{cases}
\card{C}, & u\in C^{\perp},\\
0, & u\notin C^{\perp}.
\end{cases} c ∈ C ∑ ψ ( u ⋅ c ) = { ∣ C ∣ , 0 , u ∈ C ⊥ , u ∈ / C ⊥ . これを cwe C ( ( x b ∗ ) ) = ∑ u ∈ F q E ( ∑ c ∈ C ψ ( u ⋅ c ) ) ∏ e ∈ E x u e . (10.2) \cwe_{C}((x_{b}^{\ast}))
=
\sum_{u \in \F_{q}^{E}}
\left(
\sum_{c \in C} \psi(u \cdot c)
\right)
\prod_{e \in E} x_{u_{e}}.
\tag{10.2} cwe C (( x b ∗ )) = u ∈ F q E ∑ ( c ∈ C ∑ ψ ( u ⋅ c ) ) e ∈ E ∏ x u e . ( 10.2 )
cwe C ( ( x b ∗ ) ) = ∣ C ∣ ∑ u ∈ C ⊥ ∏ e ∈ E x u e = ∣ C ∣ cwe C ⊥ ( ( x a ) ) \begin{aligned}
\cwe_{C}((x_{b}^{\ast}))
&=
\card{C}
\sum_{u \in C^{\perp}} \prod_{e \in E} x_{u_{e}} \\
&=
\card{C}\,\cwe_{C^{\perp}}((x_{a}))
\end{aligned} cwe C (( x b ∗ )) = ∣ C ∣ u ∈ C ⊥ ∑ e ∈ E ∏ x u e = ∣ C ∣ cwe C ⊥ (( x a )) となる．両辺を ∣ C ∣ \card{C} ∣ C ∣
証明終わり □
証明の最後で得た等式は，正規化していない完全重み多項式について
cwe C ( ( x b ∗ ) b ∈ F q ) = ∣ C ∣ cwe C ⊥ ( ( x a ) a ∈ F q ) \cwe_{C}((x_{b}^{\ast})_{b \in \F_q})
=
\card{C}\,\cwe_{C^\perp}((x_{a})_{a \in \F_q}) cwe C (( x b ∗ ) b ∈ F q ) = ∣ C ∣ cwe C ⊥ (( x a ) a ∈ F q ) という形です． 一方，cZ C = ∣ C ∣ − 1 cwe C \cZ_C=\card{C}^{-1}\cwe_C cZ C = ∣ C ∣ − 1 cwe C
cZ C ( ( x b ∗ ) b ∈ F q ) = cwe C ⊥ ( ( x a ) a ∈ F q ) \cZ_{C}((x_{b}^{\ast})_{b \in \F_q})
=
\cwe_{C^\perp}((x_{a})_{a \in \F_q}) cZ C (( x b ∗ ) b ∈ F q ) = cwe C ⊥ (( x a ) a ∈ F q ) が得られます． つまり，この段階で出てくるのは双対符号の完全重み多項式 です．
完全巡回指数同士で書きたい場合は，さらに cZ C ⊥ = ∣ C ⊥ ∣ − 1 cwe C ⊥ \cZ_{C^\perp}=\card{C^\perp}^{-1}\cwe_{C^\perp} cZ C ⊥ = C ⊥ − 1 cwe C ⊥ dim C + dim C ⊥ = n \dim C+\dim C^\perp=n dim C + dim C ⊥ = n ∣ C ∣ ∣ C ⊥ ∣ = q n \card{C}\card{C^\perp}=q^n ∣ C ∣ C ⊥ = q n
cZ C ⊥ ( ( x a ) ) = ∣ C ∣ q n cZ C ( ( x b ∗ ) ) \cZ_{C^{\perp}}((x_{a}))
=
\frac{\card{C}}{q^{n}}\,
\cZ_{C}((x_{b}^{\ast})) cZ C ⊥ (( x a )) = q n ∣ C ∣ cZ C (( x b ∗ )) という形になります． したがって，「本稿の正規化では，完全巡回指数に指標表変換を施すと双対符号の完全重み多項式が出る」という主張と， 「完全巡回指数同士で書くと係数 ∣ C ∣ / q n \card{C}/q^n ∣ C ∣ / q n
この証明は，普通の指標論的証明と非常に近いものです． ただし，ここでは各符号語を「完全巡回指数の単項式」と見て， 指標表変換によって完全巡回指数を変換しています． この意味で，MacWilliams恒等式は
符号から作った平行移動置換群の完全巡回指数に対する指標表変換
として読むことができます．
§11 Hamming重み多項式への特殊化 最後に，完全重み多項式版から通常のMacWilliams恒等式を導きます． 変数を
x 0 = X , x a = Y ( a ≠ 0 ) x_{0} = X,
\qquad
x_{a} = Y \quad(a \neq 0) x 0 = X , x a = Y ( a = 0 ) と特殊化します．
このとき，b = 0 b=0 b = 0
x 0 ∗ = ∑ a ∈ F q x a = X + ( q − 1 ) Y . x_{0}^{\ast}
=
\sum_{a \in \F_{q}} x_{a}
=
X + (q - 1)Y. x 0 ∗ = a ∈ F q ∑ x a = X + ( q − 1 ) Y . 一方，b ≠ 0 b \neq 0 b = 0 補題 9.1 b ∈ F q b \in \F_{q} b ∈ F q ∑ a ∈ F q ψ ( a b ) = { q , b = 0 , 0 , b ≠ 0 \sum_{a \in \F_{q}}\psi(ab)
=
\begin{cases}
q, & b = 0,\\
0, & b \neq 0
\end{cases} a ∈ F q ∑ ψ ( ab ) = { q , 0 , b = 0 , b = 0 が成り立つ．
∑ a ∈ F q ψ ( a b ) = 0 \sum_{a \in \F_{q}} \psi(ab) = 0 a ∈ F q ∑ ψ ( ab ) = 0 なので
x b ∗ = ∑ a ∈ F q ψ ( a b ) x a = x 0 + Y ∑ a ∈ F q × ψ ( a b ) = X + Y ( ∑ a ∈ F q ψ ( a b ) − 1 ) = X − Y . \begin{aligned}
x_{b}^{\ast}
&=
\sum_{a \in \F_{q}} \psi(ab)x_{a} \\
&=
x_{0} + Y \sum_{a \in \F_{q}^{\times}} \psi(ab) \\
&=
X + Y\left( \sum_{a \in \F_{q}} \psi(ab) - 1 \right) \\
&=
X - Y.
\end{aligned} x b ∗ = a ∈ F q ∑ ψ ( ab ) x a = x 0 + Y a ∈ F q × ∑ ψ ( ab ) = X + Y a ∈ F q ∑ ψ ( ab ) − 1 = X − Y . したがって，完全重み多項式版MacWilliams恒等式
cwe C ⊥ ( ( x a ) ) = 1 ∣ C ∣ cwe C ( ( x b ∗ ) ) \cwe_{C^{\perp}}((x_{a}))
=
\frac{1}{\card{C}}\cwe_{C}((x_{b}^{\ast})) cwe C ⊥ (( x a )) = ∣ C ∣ 1 cwe C (( x b ∗ )) をこの特殊化で読むと，左辺は W C ⊥ ( X , Y ) W_{C^{\perp}}(X, Y) W C ⊥ ( X , Y )
1 ∣ C ∣ W C ( X + ( q − 1 ) Y , X − Y ) \frac{1}{\card{C}}
W_{C}\bigl( X + (q - 1)Y, X - Y \bigr) ∣ C ∣ 1 W C ( X + ( q − 1 ) Y , X − Y ) になります． よって次を得ます．
定理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 ) が成り立つ．
証明 ここまでで，群作用・巡回指数の見方からMacWilliams恒等式に到達しました． 証明の最後だけを見ると指標和の計算に見えますが， その前段階で，符号語を平行移動置換として見て，巡回指数に埋め込んでいる点が今回の見方です．
具体例で確認します． E = { 1 , 2 , 3 } E = \{ 1, 2, 3 \} E = { 1 , 2 , 3 }
C = { 000 , 111 } ≤ F 2 3 C = \{ 000, 111 \} \leq \F_{2}^{3} C = { 000 , 111 } ≤ F 2 3 を考えます．この双対符号は長さ 3 3 3
C ⊥ = { 000 , 110 , 101 , 011 } C^{\perp} =
\{ 000, 110, 101, 011 \} C ⊥ = { 000 , 110 , 101 , 011 } です．
まず，C C C
Ω C = { 1 , 2 , 3 } × F 2 \Omega_{C} = \{ 1, 2, 3 \} \times \F_{2} Ω C = { 1 , 2 , 3 } × F 2 です． 零語 000 000 000 6 6 6 111 111 111 { e } × F 2 \{ e \} \times \F_{2} { e } × F 2 0 0 0 1 1 1 2 2 2
Z G ( C ) , Ω C ( s 1 , s 2 , … ) = 1 2 ( s 1 6 + s 2 3 ) \Zcycle_{G(C),\Omega_C}(s_{1}, s_{2}, \dots)
=
\frac{1}{2}(s_{1}^{6} + s_{2}^{3}) Z G ( C ) , Ω C ( s 1 , s 2 , … ) = 2 1 ( s 1 6 + s 2 3 ) です．二元なので，
U 0 = s 1 2 , U 1 = s 2 U_{0} = s_{1}^{2},
\qquad
U_{1} = s_{2} U 0 = s 1 2 , U 1 = s 2 とおけば
2 Z G ( C ) , Ω C ( s 1 , s 2 , … ) = U 0 3 + U 1 3 = W C ( U 0 , U 1 ) 2\Zcycle_{G(C),\Omega_C}(s_{1}, s_{2}, \dots)
=
U_{0}^{3} + U_{1}^{3}
=
W_{C}(U_{0}, U_{1}) 2 Z G ( C ) , Ω C ( s 1 , s 2 , … ) = U 0 3 + U 1 3 = W C ( U 0 , U 1 ) となります． その後，U 0 = X U_{0}=X U 0 = X U 1 = Y U_{1}=Y U 1 = Y
W C ( X , Y ) = X 3 + Y 3 W_{C}(X,Y)=X^{3}+Y^{3} W C ( X , Y ) = X 3 + Y 3 が得られます．
次に完全重み多項式で見ると
cwe C ( x 0 , x 1 ) = x 0 3 + x 1 3 \cwe_{C}(x_{0}, x_{1}) = x_{0}^{3} + x_{1}^{3} cwe C ( x 0 , x 1 ) = x 0 3 + x 1 3 です． したがって，本稿でいう完全巡回指数は
cZ C ( x 0 , x 1 ) = 1 2 ( x 0 3 + x 1 3 ) \cZ_{C}(x_{0}, x_{1}) = \frac{1}{2}(x_{0}^{3} + x_{1}^{3}) cZ C ( x 0 , x 1 ) = 2 1 ( x 0 3 + x 1 3 ) です． F 2 \F_{2} F 2 ψ ( a ) = ( − 1 ) a \psi(a) = (-1)^{a} ψ ( a ) = ( − 1 ) a
x 0 ∗ = x 0 + x 1 , x 1 ∗ = x 0 − x 1 x_{0}^{\ast} = x_{0} + x_{1},
\qquad
x_{1}^{\ast} = x_{0} - x_{1} x 0 ∗ = x 0 + x 1 , x 1 ∗ = x 0 − x 1 です．したがって
1 ∣ C ∣ cwe C ( x 0 ∗ , x 1 ∗ ) = 1 2 ( ( x 0 + x 1 ) 3 + ( x 0 − x 1 ) 3 ) = x 0 3 + 3 x 0 x 1 2 . \begin{aligned}
\frac{1}{\card{C}} \cwe_{C}(x_{0}^{\ast}, x_{1}^{\ast})
&=
\frac{1}{2}\left((x_{0} + x_{1})^{3} + (x_{0} - x_{1})^{3} \right)\\
&=
x_{0}^{3} + 3x_{0}x_{1}^{2}.
\end{aligned} ∣ C ∣ 1 cwe C ( x 0 ∗ , x 1 ∗ ) = 2 1 ( ( x 0 + x 1 ) 3 + ( x 0 − x 1 ) 3 ) = x 0 3 + 3 x 0 x 1 2 . 一方，偶重み符号 C ⊥ = { 000 , 110 , 101 , 011 } C^{\perp} = \{ 000, 110, 101, 011 \} C ⊥ = { 000 , 110 , 101 , 011 }
cwe C ⊥ ( x 0 , x 1 ) = x 0 3 + 3 x 0 x 1 2 \cwe_{C^{\perp}}(x_{0}, x_{1})
=
x_{0}^{3} + 3x_{0} x_{1}^{2} cwe C ⊥ ( x 0 , x 1 ) = x 0 3 + 3 x 0 x 1 2 です． 確かに完全重み多項式版MacWilliams恒等式が成り立っています．
Hamming重み多項式に特殊化すれば，
W C ( X , Y ) = X 3 + Y 3 , W C ⊥ ( X , Y ) = X 3 + 3 X Y 2 W_{C}(X, Y) = X^{3} + Y^{3},
\qquad
W_{C^{\perp}}(X, Y) = X^{3} + 3XY^{2} W C ( X , Y ) = X 3 + Y 3 , W C ⊥ ( X , Y ) = X 3 + 3 X Y 2 です． MacWilliams恒等式は
1 2 W C ( X + Y , X − Y ) = 1 2 ( ( X + Y ) 3 + ( X − Y ) 3 ) = X 3 + 3 X Y 2 = W C ⊥ ( X , Y ) \begin{aligned}
\frac{1}{2}W_{C}(X + Y, X - Y)
&=
\frac{1}{2}\left((X + Y)^{3} + (X - Y)^{3} \right)\\
&=
X^{3} + 3XY^{2} =
W_{C^{\perp}}(X,Y)
\end{aligned} 2 1 W C ( X + Y , X − Y ) = 2 1 ( ( X + Y ) 3 + ( X − Y ) 3 ) = X 3 + 3 X Y 2 = W C ⊥ ( X , Y ) となります．
この例では，普通の巡回指数は，正規化を戻して適切に特殊化すると W C ( X , Y ) = X 3 + Y 3 W_{C}(X, Y) = X^{3} + Y^{3} W C ( X , Y ) = X 3 + Y 3 1 2 ( x 0 3 + x 1 3 ) \frac{1}{2}(x_{0}^{3} + x_{1}^{3}) 2 1 ( x 0 3 + x 1 3 ) x 0 3 + x 1 3 x_{0}^{3} + x_{1}^{3} x 0 3 + x 1 3
§13 この証明で群作用と巡回指数は何をしていたか 今回の証明で群作用と巡回指数が担っていた役割を整理します．
第一に，群作用は符号語を置換として見せました． 符号語 c ∈ C c\in C c ∈ C
a ↦ a + c e a\mapsto a+c_e a ↦ a + c e という平行移動を与えます． この平行移動をすべての座標のコピー { e } × F q \{e\}\times\F_q { e } × F q C C C G ( C ) G(C) G ( C )
第二に，普通の巡回指数はHamming重みを記録しました． 零座標では q q q q / p q/p q / p p p p G ( C ) G(C) G ( C ) C C C
第三に，完全巡回指数は非零値の種類まで記録しました． 普通の巡回指数では，非零の平行移動は同じサイクル型を持つため区別されません． そこで，置換の巡回型だけでなく，各座標ファイバーでの平行移動量 c e ∈ F q c_{e} \in \F_{q} c e ∈ F q x c e x_{c_{e}} x c e ∣ C ∣ \card{C} ∣ C ∣
第四に，Pólya計数は「群作用に沿った平均」の意味を与えました． Burnsideの補題では，軌道数は不動点数の平均として現れました． Pólya計数では，巡回指数に変数を代入することで，対称性を考慮した彩色を数えました． 今回の符号理論の証明でも，指標値 ψ ( u ⋅ c ) \psi(u\cdot c) ψ ( u ⋅ c ) c ∈ C c \in C c ∈ C C ⊥ C^{\perp} C ⊥
第五に，指標表変換が双対符号を取り出しました． 完全巡回指数の変数に
x b ∗ = ∑ a ∈ F q ψ ( a b ) x a x_{b}^{\ast} = \sum_{a \in \F_{q}} \psi(ab) x_{a} x b ∗ = a ∈ F q ∑ ψ ( ab ) x a という変換を入れると，展開の中に
∑ c ∈ C ψ ( u ⋅ c ) \sum_{c \in C}\psi(u\cdot c) c ∈ C ∑ ψ ( u ⋅ c ) が現れます． この和は，u ∈ C ⊥ u \in C^{\perp} u ∈ C ⊥ ∣ C ∣ \card{C} ∣ C ∣ 0 0 0 ∣ C ∣ / q n \card{C}/q^n ∣ C ∣ / q n
要点を一文で言えば，次のようになります．
MacWilliams恒等式は，符号から作った平行移動置換群の完全巡回指数に，有限体 F q \F_q F q ( F q , + ) (\F_q,+) ( F q , + )
§14 この回で見た概念 この回では，MacWilliams恒等式の証明を目標にしながら，群作用と巡回指数の基本的な道具を導入しました． 整理すると次のようになります．
群作用 群の元を集合上の置換として実現する構造です． 符号理論では，符号語を各座標のコピー { e } × F q \{e\}\times\F_q { e } × F q
軌道 一つの点を群の元で動かして到達できる点全体です． 群作用によって集合は軌道に分解されます．
安定化群 ある点を固定する群の元全体です． 軌道・安定化群定理により，軌道の大きさと安定化群の大きさの積は群の位数になります．
不動点 ある群の元で動かない点です． Burnsideの補題では，不動点数の平均として軌道数を計算しました．
Burnsideの補題 軌道数を不動点数の平均として数える公式です． Pólya計数の基礎になります．
巡回型 置換を互いに交わらないサイクルに分解したときの，サイクル長ごとの個数です．
巡回指数 群の各元の巡回型を単項式として記録し，群全体で平均した多項式です． Pólya計数では，巡回指数に適切な変数を代入することで，彩色の軌道を数えます．
Pólya計数 対称性を考慮した彩色を数える方法です． 長さ ℓ \ell ℓ w a ℓ w_{a}^{\ell} w a ℓ P ℓ = ∑ a w a ℓ P_{\ell}=\sum_a w_a^\ell P ℓ = ∑ a w a ℓ
符号から作る置換群 符号語 c ∈ C c \in C c ∈ C E × F q E \times \F_{q} E × F q ( e , a ) ↦ ( e , a + c e ) (e, a) \mapsto (e, a + c_{e}) ( e , a ) ↦ ( e , a + c e )
完全巡回指数 普通の巡回指数そのものではなく，符号から来る各座標ファイバーでの平行移動量 c e ∈ F q c_{e} \in \F_{q} c e ∈ F q x c e x_{c_{e}} x c e ∣ C ∣ \card{C} ∣ C ∣
指標表変換 有限体 F q \F_q F q ( F q , + ) (\F_q,+) ( F q , + ) x b ∗ = ∑ a ψ ( a b ) x a x_{b}^{\ast} = \sum_{a} \psi(ab) x_{a} x b ∗ = ∑ a ψ ( ab ) x a ∣ C ∣ / q n \card{C}/q^n ∣ C ∣ / q n
§15 今回の系統の振り返り 今回の証明は，表面的には群作用・Burnsideの補題・Pólya計数・巡回指数の証明です． 一方，五つの系統に圧縮すると，これは
Fourier・指標・Poisson系
に近い証明です． 理由は，最終的に双対符号を取り出す原理が
∑ c ∈ C ψ ( u ⋅ c ) = { ∣ C ∣ , u ∈ C ⊥ , 0 , u ∉ C ⊥ \sum_{c\in C}\psi(u\cdot c)
=
\begin{cases}
\card{C}, & u \in C^{\perp},\\
0, & u\notin C^{\perp}
\end{cases} c ∈ C ∑ ψ ( u ⋅ c ) = { ∣ C ∣ , 0 , u ∈ C ⊥ , u ∈ / C ⊥ という指標直交性だからです．
ただし，今回の見方は通常の指標論的証明とは表情が違います． 通常の指標論的証明では，C ⊥ C^{\perp} C ⊥
したがって，今回の証明の深層にはFourier的な原理がありますが， 表面的な道具立ては群作用と巡回指数です． この違いが，この連載で見たい「同じ定理が違う分野の言葉で見える」という現象です．
§16 次回へ 最後に，連載上の次回予告を述べます． ここまでで，本稿の数学本文は完結しています． 次回は，MacWilliams恒等式を因子グラフと分割関数の側から見ます．
今回の証明では，符号語を置換として見て，群作用に沿った平均や巡回指数の言葉でMacWilliams恒等式を捉えました． 次回は，符号を局所制約の集まりとして見ます． つまり，符号語全体を一つの大きな集合として扱うのではなく， 各座標，各検査式，各状態変数に分解して，グラフ上の分配関数として表します．
次回の主役は，
局所制約 → 因子グラフ → 分割関数 → 双対グラフ → MacWilliams恒等式
です． 同じFourier・指標・Poisson系に属する証明であっても， 次回は「一括で変換する」のではなく， 局所的な変換をグラフ全体に貼り合わせる見方になります．
参考文献 [Cam02] Peter J. Cameron. Cycle index, weight enumerator, and Tutte polynomial . Electron. J. Combin., vol. 9, no. 1, pp. Note 2, 10, 2002. doi:10.37236/1663 引用箇所 巡回指数と符号の重み多項式の関係については， Cameron [Cam02] が， 線形符号に付随する置換群の巡回指数が， 正規化を除いて重み多項式になることを述べています． 完全巡回指数と完全重み多項式の関係については， 三枝崎–大浦 [MO19] を参照してください． また，Pólya計数や巡回指数の古典的な扱いについては Pólya [Ply37] ，Harary–Palmer [HP73] などを参照してください． 置換群の基本事項については Cameron [Cam95] も標準的です． 引用箇所 このように，符号から得られる置換群の普通の巡回指数が Hamming重み多項式を記録するという見方は， Cameron [Cam02] に現れるものです． 本稿では，この見方を，後で完全重み多項式に対応するように 平行移動量付きに精密化します． [MO19] Tsuyoshi Miezaki and Manabu Oura. On the cycle index and the weight enumerator . Des. Codes Cryptogr., vol. 87, no. 6, pp. 1237–1242, 2019. doi:10.1007/s10623-018-0518-x 引用箇所 巡回指数と符号の重み多項式の関係については， Cameron [Cam02] が， 線形符号に付随する置換群の巡回指数が， 正規化を除いて重み多項式になることを述べています． 完全巡回指数と完全重み多項式の関係については， 三枝崎–大浦 [MO19] を参照してください． また，Pólya計数や巡回指数の古典的な扱いについては Pólya [Ply37] ，Harary–Palmer [HP73] などを参照してください． 置換群の基本事項については Cameron [Cam95] も標準的です． 引用箇所 です． つまり，完全巡回指数は完全重み多項式を群の元にわたる平均として正規化したものです． 注意しておくと，本稿でいう完全巡回指数は，一般の置換群に対して標準的に定義される普通の巡回指数そのものではありません． 普通の巡回指数が置換のサイクル長だけを見るのに対して，本稿の cZ C \cZ_C cZ C { e } × F q \{e\}\times\F_q { e } × F q c e c_e c e cZ C \cZ_C cZ C c c c c e c_e c e s ( h , i ) s(h,i) s ( h , i ) cZ C \cZ_C cZ C ∣ C ∣ \card{C} ∣ C ∣ [MO19] が扱う完全巡回指数と完全重み多項式の関係に沿っています． 本稿では，そのうちMacWilliams恒等式の変数変換に必要な部分だけを取り出して説明します． [Ply37] G. Pólya. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen . Acta Math., vol. 68, no. 1, pp. 145–254, 1937. doi:10.1007/BF02546665 引用箇所 巡回指数と符号の重み多項式の関係については， Cameron [Cam02] が， 線形符号に付随する置換群の巡回指数が， 正規化を除いて重み多項式になることを述べています． 完全巡回指数と完全重み多項式の関係については， 三枝崎–大浦 [MO19] を参照してください． また，Pólya計数や巡回指数の古典的な扱いについては Pólya [Ply37] ，Harary–Palmer [HP73] などを参照してください． 置換群の基本事項については Cameron [Cam95] も標準的です． [HP73] Frank Harary and Edgar M. Palmer. Graphical enumeration . Academic Press, New York-London, pp. xiv+271, 1973 引用箇所 巡回指数と符号の重み多項式の関係については， Cameron [Cam02] が， 線形符号に付随する置換群の巡回指数が， 正規化を除いて重み多項式になることを述べています． 完全巡回指数と完全重み多項式の関係については， 三枝崎–大浦 [MO19] を参照してください． また，Pólya計数や巡回指数の古典的な扱いについては Pólya [Ply37] ，Harary–Palmer [HP73] などを参照してください． 置換群の基本事項については Cameron [Cam95] も標準的です． [Cam95] Peter J. Cameron. Permutation groups . Handbook of combinatorics, Vol.\ 1,\ 2, pp. 611–645, 1995 引用箇所 巡回指数と符号の重み多項式の関係については， Cameron [Cam02] が， 線形符号に付随する置換群の巡回指数が， 正規化を除いて重み多項式になることを述べています． 完全巡回指数と完全重み多項式の関係については， 三枝崎–大浦 [MO19] を参照してください． また，Pólya計数や巡回指数の古典的な扱いについては Pólya [Ply37] ，Harary–Palmer [HP73] などを参照してください． 置換群の基本事項については Cameron [Cam95] も標準的です． [MS77] F. J. MacWilliams and N. J. A. Sloane. The theory of error-correcting codes. II . North-Holland Publishing Co., Amsterdam-New York-Oxford, vol. Vol. 16, pp. i–ix and 370–762, 1977 引用箇所 完全重み多項式版MacWilliams恒等式そのものの標準的な扱いについては， MacWilliams–Sloane [MS77, Chapters 5 and 19] を参照してください． ただし，本稿で強調するのは，この恒等式を 符号から作る平行移動置換群の完全巡回指数として読む点です． [Ter99] Audrey Terras. Fourier analysis on finite groups and applications . Cambridge University Press, Cambridge, vol. 43, pp. x+442, 1999. doi:10.1017/CBO9780511626265 引用箇所 有限群上のFourier解析や指標表の標準的な背景については， Terras [Ter99] を参照してください． また，有限体のトレース写像と加法指標については Lidl–Niederreiter [LN83] が標準的です． [LN83] Rudolf Lidl and Harald Niederreiter. Finite fields . Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, vol. 20, pp. xx+755, 1983 引用箇所 有限群上のFourier解析や指標表の標準的な背景については， Terras [Ter99] を参照してください． また，有限体のトレース写像と加法指標については Lidl–Niederreiter [LN83] が標準的です．