MacWilliams恒等式で学ぶマトロイドとTutte多項式入門

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

を考えます．ここで

です． 本稿では，符号語 $c \in \F_{q}^{E}$ に対して $c$ の台 (support) とHamming重み (Hamming weight) を

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

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

これがMacWilliams恒等式です．

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

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

• （有限）体とは何か

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

• Hamming重みとは何か

• 双対符号とは何か

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

本稿は第1回から第6回を前提にしません． ただし，連載としての見通しを保つため，今回も最初に「どの証明系統を見ているのか」を確認しておきます． この連載では，MacWilliams恒等式の証明手法を大きく次の五つの系統に分けて眺めています：

1. Fourier・指標・Poisson系．

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

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

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

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

今回扱うのは，このうち「マトロイド・Tutte多項式系」です． つまり，第7回の目標は，MacWilliams恒等式の証明を案内役として，符号に付随するマトロイドとTutte多項式，そして両者を結ぶGreeneの定理に入門することです．

今回注意しておきたいのは，本稿ではマトロイド理論を体系的に展開しないという点です． マトロイドには，独立集合，基，サーキット，閉包，フラット，マイナー，表現可能性など，多くの基本概念があります． しかし，MacWilliams恒等式へ到達するために必要なのは，符号 $C \leq \F_{q}^{E}$ から得られる階数関数と，その階数関数で定義されるTutte多項式です． 今後，「符号理論からのマトロイド理論入門」という記事を書くことも検討しているので，体系的なマトロイド理論はそこで丁寧に扱うことにします． そこで本稿では，マトロイドの入口は最短距離で通り，重み多項式とTutte多項式の関係に比重を置きます．

符号理論から見ると，マトロイドが自然に現れる理由は次の通りです． 座標集合 $E$ の一部 $A \subseteq E$ だけを見ると，符号 $C$ は制限符号 $\res{C}{A} = \{ \res{c}{A} \in \F_{q}^{A} \mid c \in C \} \leq \F_{q}^{A}$ を与えます． その次元

は，$A$ に残した座標が，符号 $C$ の情報をどれだけ見分けられるかを測っています． この関数 $r_{C}$ がマトロイドの階数関数になります． 一方，重み多項式は，符号語の台の大きさを数え上げる多項式です． したがって，Greeneの定理は大まかに言えば，

座標部分集合ごとの制限の次元を集めたTutte多項式から，符号語の台の分布を復元できる．

という主張です．この一文が，今回の証明の中心にあります．

本稿の流れは次のようになります． まず，階数関数によりマトロイドを定義し，符号 $C \leq \F_{q}^{E}$ から $r_{C}(A) = \dim_{\F_{q}}(\res{C}{A})$ によってマトロイド $M(C)$ を作ります． 次に，双対符号・穿孔・短縮が，マトロイドの双対・削除・縮約に対応することを確認します． その後，Tutte多項式

を導入し，特殊値，双対性，削除・縮約公式を見ます．最後に，Greeneの定理

を証明し，Tutte多項式の双対性からMacWilliams恒等式を導きます．

マトロイドは Whitney [Whi35] によって導入されました． Tutte多項式のマトロイド版の基本文献としては Crapo [Cra69] があり，符号の重み多項式とTutte多項式の関係は Greene [Gre76] によるものです． この定理を出発点として，線形符号の性質がTutte多項式からどのように読み取れるかを概観する文献として， Britz–Cameron [BC22] があります． マトロイド理論の標準的な教科書としては Oxley [Oxl11] をご参照ください．

本稿では，マトロイドを階数関数によって定義します． わざわざ「階数関数によって」と述べている通り，マトロイドには同値な定義がいくつもあり， 暗黙同型 (cryptomorphism) という関係で結び付いています． おおよそ，位相空間が開集合・閉集合・開核作用素・閉包作用素のそれぞれに公理があり， 一つが定まると残りも自ずと定まる，という話に似ています． マトロイドには独立集合族・従属集合族・基族・サーキット族・フラット族・超平面族をはじめ， 数多くの公理系があり，今回は階数関数の公理を採用する形になります． これは，符号理論から入る本稿では最も自然な定式化です． 符号 $C \leq \F_{q}^{E}$ からは，各座標部分集合 $A \subseteq E$ に対して制限符号 $\res{C}{A}$ の次元が直接得られます． この「部分集合ごとの次元」を抽象化したものが，ここでいう階数関数です．

この意味で，マトロイドは線形代数に現れる「次元」の概念を抽象化したものと解釈できます． Whitney [Whi35] によって導入された「マトロイド」は「行列(matrix)+のようなもの(-oid)」に由来しています． 実際，線形符号の生成行列を考えてみると，$\res{C}{A}$ の次元というのは， 生成行列の $A$ でラベル付けされた部分の部分行列の階数に対応しています． 実際，$G$ を $C$ の生成行列とすると，$\res{C}{A}$ は， $G$ の $A$ に属する列だけを残した部分行列 $\res{G}{A}$ の行空間です． すなわち，

となります．つまり，$M(C)$ は生成行列の列ベクトルたちの線形従属性を記録していると見ることもできます． この意味で確かにマトロイドは「行列っぽいもの」と見ることができます．

三つ目の条件 (R3)$r(A \cup B) + r(A \cap B) \leq r(A) + r(B)$．(R3) は劣モジュラ性 (submodularity) と呼ばれています． 線形代数で出てくる次元定理 $\dim (V + W) + \dim (V \cap W) = \dim V + \dim W$ ($V$, $W$ は共通の体上のベクトル空間) の等号を不等号で置き換えたものになります． 直感的には，二つの部分集合を別々に見たときの情報量の和は，合併と共通部分に分けて見たときの情報量の和以上である，という条件です． Tutte多項式は階数関数だけで定義できるため，本稿ではこの定義だけで十分です．

階数関数から，必要な用語を取り出しておきます． $I \subseteq E$ が独立 (independent) であるとは $r_{M}(I) = \card{I}$ が成り立つことをいいます． また，$B \subseteq E$ が $M$ の基 (basis, 複: bases) であるとは $r_{M}(B) = \card{B} = r_{M}(E)$ が成り立つことをいいます． 本稿では特に，Tutte多項式の特殊値 $\Tutte_{M}(2, 1)$ を解釈するときに，この言葉を使います．

$e \in E$ がループ (loop) であるとは $r_{M}(\{ e \}) = 0$ であることをいいます． また，$e \in E$ が余ループ (coloop) または地峡 (isthmus，複：isthmi)であるとは $r_{M}(E) - r_{M}(E \setminus \{ e \}) = 1$ であることをいいます．

今回は主題と外れるので詳しく解説しませんが，Whitney [Whi35] の原論文にも登場する通り， マトロイドはグラフの階数も同時に抽象化しており，上の「ループ」や「地峡」という用語は グラフのループ（自己閉路）や地峡（橋）に由来しています．

一様マトロイドは，今回使う具体例のほとんどを支える基本例です． 特に，単一ループ，単一余ループ，反復符号や偶重み符号から出る小さなマトロイドは，一様マトロイドとして書けます．

一様マトロイドの特別な場合として，$U_{n, n}$ を自由マトロイド (free matroid) と呼びます． この場合，任意の $A \subseteq E$ に対して $r(A) = \card{A}$ です． また，$U_{0, n}$ では任意の $A \subseteq E$ に対して $r(A) = 0$ です． 特に $E = \emptyset$ の場合の $U_{0, 0}$ を空マトロイド (empty matroid) と呼びます．

ここから，符号理論側の対象をマトロイドの言葉へ翻訳します． この節で行うことは一つだけです． 符号 $C$ を各座標部分集合へ制限し，その次元を記録します． この「各制限符号の次元を記録したもの」がマトロイドになります．

$C \leq \F_{q}^{E}$ を線形符号とし，$S \subseteq E$ とします． $c \in \F_{q}^{E}$ を $E$ で添え字付けられたベクトル $c = (c_{i})_{i \in E}$ という見方から，$E$ から $\F_{q}$ への写像 $c \colon E \to \F_{q}, \, i \mapsto c_{i}$ という見方へ変えたとき，制限写像 $\res{c}{S} \colon S \to \mathbb{F}_{q}$ は $S$ で添え字付けられた部分を取り出したベクトル $\res{c}{S} = (c_{i})_{i \in S}$ と対応します． そこで，$S$ への制限符号 (restricted code) を

と定めます． つまり $\res{C}{S}$ は，$C$ の符号語から座標集合 $E \setminus S$ を取り除いて得られる 穿孔符号 $C^{E \setminus S}$ です．

証明

有界性 (R1)$0\leq r(A) \leq \card{A}$．(R1)

任意の $A \subseteq E$ に対して $\res{C}{A} \leq \F_{q}^{A}$ であるから，

$$0 \leq r_{C}(A) \leq \dim_{\F_{q}} \F_{q}^{A} = \card{A}$$

となり，有界性 (R1)$0\leq r(A) \leq \card{A}$．(R1) が成り立つ．

単調性 (R2)$A \subseteq B$ ならば $r(A) \leq r(B)$．(R2)

$A \subseteq B \subseteq E$ のとき，$\res{C}{A}$ は $\res{C}{B}$ をさらに $A$ に制限した像 $\res{\res{C}{B}}{A}$ であるため， $r_{C}(A) \leq r_{C}(B)$ となる．

劣モジュラ性 (R3)$r(A \cup B) + r(A \cap B) \leq r(A) + r(B)$．(R3)

$A, B \subseteq E$ とする． 制限写像 $\res{C}{A} \to \res{C}{A \cap B}$ と $\res{C}{B} \to \res{C}{A \cap B}$ を用いて，線形空間

$$P \coloneqq \{ (u, v) \in \res{C}{A} \oplus \res{C}{B}: \res{u}{A \cap B} = \res{v}{A \cap B} \}$$

を考える．この $P$ は写像

$$\res{C}{A} \oplus \res{C}{B} \to \res{C}{A\cap B},\quad (u,v)\mapsto \res{u}{A\cap B}-\res{v}{A\cap B}$$

の核であり，この写像は全射である． 実際，任意の $w \in \res{C}{A \cap B}$ に対し， $w = \res{c}{A \cap B}$ となる $c \in C$ を取れば， $(\res{c}{A}, 0)$ はこの写像で $w$ に送られる． したがって，階数・退化次数の定理から，

$$\begin{aligned} \dim_{\F_{q}} P &= \dim_{\F_{q}} \res{C}{A} + \dim_{\F_{q}} \res{C}{B} - \dim_{\F_{q}} \res{C}{A \cap B} \\ &= r_{C}(A) + r_{C}(B) - r_{C}(A \cap B) \end{aligned}$$

となる． 一方，$\res{C}{A \cup B}$ の元を $A$ と $B$ に制限すると $P$ の元が得られ，この対応は単射である． つまり，$\dim \res{C}{A \cup B} \leq \dim_{\F_{q}} P$ であるから，

$$r_{C}(A \cup B) \leq r_{C}(A) + r_{C}(B) - r_{C}(A \cap B)$$

となり，劣モジュラ性が従う．

証明終わり□

この階数関数で定まる $E$ 上のマトロイド $M(C)$ を $C$ に付随するマトロイド (matroid associated with $C$) という． まずは小さな例で，この定義が何を見ているのかを確認します．

二つの例は，いずれも一様マトロイドになりました． もちろん，符号から得られるマトロイドがいつも一様マトロイドになるわけではありません． （例えば，$C = \{ 000, 100, 011, 111 \} \leq \F_{2}^{\{ 1, 2, 3 \}}$ に付随するマトロイドを考えてみてください．） しかし，反復符号や偶重み符号は，この後に出てくるTutte多項式の計算を手で追うにはちょうどよい大きさです．

MacWilliams恒等式に向かうには，次に双対と座標の除去を扱う必要があります． 符号理論では双対符号，穿孔符号，短縮符号が現れます． マトロイド側では，これらに対応する操作が双対，削除，縮約です．

Tutte多項式とMacWilliams恒等式をつなぐには，双対，削除，縮約を階数関数で扱えるようにしておく必要があります． まず，符号に対して双対符号があるように，マトロイドにも双対があります．

マトロイドの双対は実際にマトロイドになり，双対マトロイドともいいます．

証明

$r_{M^{\ast}} = r^{\ast}$ がマトロイドの階数関数の公理を満たすことを確かめればよい．

有界性 (R1)$0\leq r(A) \leq \card{A}$．(R1)

$r_{M}$ は階数関数の公理を満たすことに注意する． $S \subseteq E$ と $e \in E \setminus S$ に対して $r_{M}$ の劣モジュラ性を用いると，

$$r_{M}(S \cup \{ e \}) + r_{M}(S \cap \{ e \}) \leq r_{M}(S) + r_{M}(\{ e \}) \leq r_{M}(S) + 1$$

となる．$e \notin S$ より， $r_{M}(S \cap \{ e \}) = r_{M}(\emptyset) = 0$ に注意すれば， $r_{M}(S \cup \{ e \}) \leq r_{M}(S) + 1$ を得る． これを繰り返すと，$S \subseteq E$ と $T \subseteq E \setminus S$ に対して

$$r_{M}(S \cup T) \leq r_{M}(S) + \card{T} \tag{4.1}$$

が得られる．これを $S = E \setminus A$, $T = A$ に適用すると

$$r_{M}(E) \leq r_{M}(E \setminus A) + \card{A}$$

となる．したがって

$$\card{A} - r_{M}(E) + r_{M}(E \setminus A) \geq 0$$

である．単調性より $r_{M}(E\setminus A) \leq r_M(E)$ であるから

$$r_{M^{\ast}}(A) = \card{A} - r_{M}(E) + r_{M}(E \setminus A) \leq \card{A}$$

を得る．

単調性 (R2)$A \subseteq B$ ならば $r(A) \leq r(B)$．(R2)

$A \subseteq B$ のとき，$E \setminus B \subseteq E \setminus A$ であり， $$r_{M}(S \cup T) \leq r_{M}(S) + \card{T} \tag{4.1}$$(4.1) を $S = E \setminus B$， $T = B \setminus A$ に適用すると，

$$\begin{aligned} r_{M}(E \setminus A) &= r_{M}\bigl( (E \setminus B) \cup (B \setminus A) \bigr) \\ &\leq r_{M}(E \setminus B) + \card{B \setminus A} \end{aligned}$$

両辺に $\card{A} - r_{M}(E)$ を加えると，

$$\begin{aligned} r_{M^{\ast}}(A) &= \card{A} - r_{M}(E) + r_{M}(E \setminus A) \\ &\leq \card{A} - r_{M}(E) + r_{M}(E \setminus B) + \card{B \setminus A} \\ &= \card{B} - r_{M}(E) + r_{M}(E \setminus B) = r_{M^{\ast}}(B) \end{aligned}$$

となり，単調性 (R2)$A \subseteq B$ ならば $r(A) \leq r(B)$．(R2) が示された．

劣モジュラ性 (R3)$r(A \cup B) + r(A \cap B) \leq r(A) + r(B)$．(R3)

$E \setminus (A \cup B) = (E \setminus A) \cap (E \setminus B)$ と $E \setminus (A \cap B) = (E \setminus A) \cup (E \setminus B)$ に注意すれば，$r_{M^{\ast}}$ の劣モジュラ性は $r_{M}$ の劣モジュラ性そのものである． 実際，

$$\begin{aligned} &r^{\ast}(A) + r^{\ast}(B) - r^{\ast}(A \cup B) - r^{\ast}(A \cap B)\\ &= r(E \setminus A) + r(E \setminus B)\\ &\quad - r(E \setminus (A \cap B)) - r(E \setminus(A \cup B)) \end{aligned}$$

となり，右辺は $r$ の劣モジュラ性から非負である．

以上により，定義定義 4.1（双対マトロイド）$M = (E, r_{M})$ をマトロイドとする． 関数 $r^{\ast} \colon 2^{E} \to \mathbb{Z}$ を， 各 $A \subseteq E$ に対して $$r^{\ast}(A) \coloneqq \card{A} - r_{M}(E) + r_{M}(E \setminus A)$$ で定める．このとき，$(E, r^{\ast})$ を $M$ の双対 (dual) と呼び， $M^{\ast}$ で表す．定義 4.1は確かにマトロイドを定める．

証明終わり□

特に，双対マトロイド $M^{\ast}$ の階数は

です．また，この公式から $(M^{\ast})^{\ast}=M$ も直ちに従います． $M^{\ast}$ は以下で示すように双対符号 $C^{\perp}$ に対応しており， これらの事実は $\dim C^{\perp} = \card{E} - \dim C$ や $(C^{\perp})^{\perp} = C$ を抽象化したものとなっています．

証明

$k \coloneqq \dim C$ とおき，$A \subseteq E$ とする． 射影 $C^{\perp} \to \res{C^{\perp}}{A}$ の核は， $A$ 上で $0$ になる $C^{\perp}$ の符号語全体である． この核を $E \setminus A$ に制限すると， $\res{C}{E \setminus A} \leq \F_{q}^{E \setminus A}$ の直交空間と同一視できる． 実際，$A$ 上で零である $u \in C^{\perp}$ は，$E \setminus A$ 上のベクトル $w$ と同一視でき， このとき任意の $c \in C$ に対して $0 = u \cdot c = w \cdot \res{c}{E \setminus A}$ であるから，$w$ は $\res{C}{E \setminus A}$ の直交補空間に属する．逆向きも， $w$ を $A$ 上で零として延長すればよい． したがって，その次元は

$$\card{E \setminus A} - r_{C}(E \setminus A)$$

である．よって

$$\begin{aligned} r_{C^{\perp}}(A) &= \dim C^{\perp} -\bigl(\card{E \setminus A} - r_{C}(E \setminus A) \bigr)\\ &= (n - k) - \card{E \setminus A} + r_{C}(E \setminus A) \\ &= \card{A} - r_{C}(E) + r_{C}(E \setminus A) \end{aligned}$$

となるが，これは定義定義 4.1（双対マトロイド）$M = (E, r_{M})$ をマトロイドとする． 関数 $r^{\ast} \colon 2^{E} \to \mathbb{Z}$ を， 各 $A \subseteq E$ に対して $$r^{\ast}(A) \coloneqq \card{A} - r_{M}(E) + r_{M}(E \setminus A)$$ で定める．このとき，$(E, r^{\ast})$ を $M$ の双対 (dual) と呼び， $M^{\ast}$ で表す．定義 4.1の双対階数関数そのものである．

証明終わり□

命題 4.3（双対符号と双対マトロイド）任意の線形符号 $C \leq \F_{q}^{E}$ に対して $$M(C^{\perp}) = M(C)^{\ast}$$ が成り立つ．命題 4.3は，この回の中で最も重要な翻訳の一つです． 双対符号を取ることは，付随するマトロイドを双対にすることと一致します． したがって，後でTutte多項式の双対性を使うと，それはそのまま双対符号の重み多項式に関する恒等式へ反映されます．

次に，削除と縮約です． マトロイド側では階数関数で定義します． 符号側では，削除は座標を削る穿孔，縮約に対応する操作は短縮です．

削除と縮約の階数関数も，定義 2.1（マトロイド）有限集合 $E$ と整数値関数 $r \colon 2^{E} \to \mathbb{Z}$ の組 $M = (E, r)$ がマトロイド (matroid) であるとは， 任意の $A, B \subseteq E$ に対して次を満たすことをいう：

1. $0\leq r(A) \leq \card{A}$．
2. $A \subseteq B$ ならば $r(A) \leq r(B)$．
3. $r(A \cup B) + r(A \cap B) \leq r(A) + r(B)$．

$E$ を $M$ の台集合 (ground set)， $r$ を $M$ の階数関数 (rank function) という． $M$ を強調したい場合は $r_{M}$ と書く． また，$r(A)$ を $A$ の階数 (rank) といい， $r(M) \coloneqq r(E)$ を $M$ の階数という．定義 2.1の三条件を満たします． 削除は $r_{M}$ の定義域を小さくしたものなので明らかに従います． 縮約については，$r_{M}(A \cup S) \geq r_{M}(S)$ より非負性が従い，上界 $r_{M}(A \cup S) - r_{M}(S) \leq \card{A}$ は命題 4.2任意のマトロイド $M$ に対し，双対 $M^{\ast}$ はマトロイドである．命題 4.2の証明に現れた 「元をいくつか加えたとき階数は高々加えた元の個数しか増えない」という不等式 $$r_{M}(S \cup T) \leq r_{M}(S) + \card{T} \tag{4.1}$$(4.1) から従います． 単調性は $r_{M}$ の単調性から従います． 劣モジュラ性は，$A, B \subseteq E \setminus S$ に対して劣モジュラ性を $A \cup S$ と $B \cup S$ に適用すれば

となることから従います．

混乱を防ぐために表にまとめておきます．

記号	操作	得られる符号の座標集合
$\res{C}{S}$	$S$ へ制限する	$S$
$C^{S}$	$S$ を穿孔して削る	$E \setminus S$
$C_{S}$	$S$ 上で $0$ の符号語だけを取り，$S$ を削る	$E\setminus S$
$C(S)$	台が $S$ に含まれる符号語の部分符号	$E$ 上の部分符号

以下の命題から，マトロイドの削除・縮約が符号の穿孔・短縮に対応していることがわかります：

証明

$A \subseteq E \setminus S$ とする． 穿孔については

$$r_{C^{S}}(A) = \dim(\res{(\res{C}{E \setminus S})}{A}) = \dim(\res{C}{A}) = r_{C}(A)$$

であるから，確かに $M(C^{S}) = M(C) \backslash S$ となる．

短縮については，制限写像 $\res{C}{A \cup S} \to \res{C}{S}$ を考える． これは全射であり，その核は，$S$ 上で $0$ になる $C$ の符号語を $A \cup S$ に制限したものである． さらに $S$ 座標を取り除くと，この核は $\res{C_{S}}{A}$ と同一視できる． よって

$$r_{C_{S}}(A) = \dim(\res{C_{S}}{A}) = \dim(\res{C}{A \cup S}) - \dim(\res{C}{S}) = r_{C}(A \cup S) - r_{C}(S)$$

となり，これはまさに $M(C)/S$ の階数関数である．

証明終わり□

削除と縮約（そして穿孔と短縮）はそれぞれ双対の操作です． 実際，階数関数から直接計算すると，任意の $S\subseteq E$ に対して

が成り立ちます． 符号側では，これは双対符号を取ると穿孔と短縮が入れ替わるという事実

に対応しています．

ここからTutte多項式に入ります． ここまでで準備したマトロイドの情報は，すべて階数関数 $r_{M}$ に入っています． Tutte多項式は，その階数関数を使って，すべての部分集合を階数の損失と従属度合ごとに数え上げる二変数多項式です． ただし，Tutte多項式からマトロイドを復元することは一般にはできないことには注意してください．

定義式だけを見ると少し唐突に見えるかもしれません．しかし，各 $A \subseteq E$ に対する 被加数部の二つの指数

には，それぞれ意味があります． 前者は $A$ が全体の階数（マトロイドの階数）にどれだけ届いていないかを測っています． 後者について，$\card{A} = r_{M}(A)$ のとき $A$ が独立であると言ったことを思い出してください． つまり後者は，$A$ の中にどれだけ従属性が含まれているか（「従属」であることに関してどれだけ余裕があるか）を測ります． Tutte多項式は，この二つの量をすべての $A \subseteq E$ について集めたものです． 前者を $A$ の階数不足 (rank defect)，後者を $A$ の退化次数 (nullity) と呼ぶこともあります．

定義 2.1（マトロイド）有限集合 $E$ と整数値関数 $r \colon 2^{E} \to \mathbb{Z}$ の組 $M = (E, r)$ がマトロイド (matroid) であるとは， 任意の $A, B \subseteq E$ に対して次を満たすことをいう：

1. $0\leq r(A) \leq \card{A}$．
2. $A \subseteq B$ ならば $r(A) \leq r(B)$．
3. $r(A \cup B) + r(A \cap B) \leq r(A) + r(B)$．

$E$ を $M$ の台集合 (ground set)， $r$ を $M$ の階数関数 (rank function) という． $M$ を強調したい場合は $r_{M}$ と書く． また，$r(A)$ を $A$ の階数 (rank) といい， $r(M) \coloneqq r(E)$ を $M$ の階数という．定義 2.1 に記した階数関数の公理より，指数 $r_{M}(E) - r_{M}(A)$, $\card{A} - r_{M}(A)$ はいずれも非負整数です． したがって，$\Tutte_{M}(x, y)$ は二変数の整数係数多項式になります．

Tutte多項式において，空マトロイド $U_{0, 0}$，単一ループ $U_{0, 1}$， 単一余ループ $U_{1, 1}$ が（単純ではあるものの）重要な役割を果たすので， まずはこれら3つのTutte多項式を求めてみましょう．

空マトロイド，単一ループ，単一余ループが重要となるのは，削除・縮約公式の初期値としても現れるためです． 特に，単一ループが $y$ を，単一余ループが $x$ を与えることが，後の公式でそのまま現れます．

次の特殊値は，Tutte多項式の意味を掴むために有用です．

証明

$(x - 1)^{0}$ や $(y - 1)^{0}$ は通常通り $1$ であることに注意する．

$x = 1$, $y = 1$ のとき，項が $0$ にならないためには指数部がいずれも $0$，すなわち

$$r_{M}(E) - r_{M}(A) = 0 \quad\text{かつ}\quad \card{A} - r_{M}(A) = 0$$

となることが必要十分条件である．これは $A$ が基であることと同値である． したがって $\Tutte_M(1, 1)$ は基の個数に等しくなる．

次に $x = 2$, $y = 1$ とする．このとき任意の $A \subseteq E$ に対して

$$(x - 1)^{r_{M}(E) - r_{M}(A)} = 1$$

となるため，項が $0$ でないためには $(y - 1)$ の指数が $0$，すなわち

$$\card{A} - r_{M}(A) = 0$$

となることが必要十分条件である． これは $A$ が独立であることと同値である．

証明終わり□

Tutte多項式の基本性質を二つ確認します． 一つ目は双対性です．

証明

双対マトロイドの定義より，

$$r_{M^{\ast}}(E \setminus A) = \card{E \setminus A} - r_{M}(E) + r_{M}(A)$$

である．したがって

$$\card{E \setminus A} - r_{M^{\ast}}(E \setminus A) = r_{M}(E) - r_{M}(A)$$

である．また $r_{M^{\ast}}(E) = \card{E} - r_{M}(E)$ であるから，

$$r_{M^{\ast}}(E) - r_{M^{\ast}}(E \setminus A) = \card{A} - r_M(A)$$

も従う．したがって，

$$\begin{aligned} \Tutte_{M^{\ast}}(x, y) &= \sum_{A \subseteq E} (x - 1)^{r_{M^{\ast}}(E) - r_{M^{\ast}}(A)} (y - 1)^{\card{A} - r_{M^{\ast}}(A)}\\ &= \sum_{B \subseteq E} (x - 1)^{\card{B} - r_{M}(B)} (y - 1)^{r_{M}(E) - r_{M}(B)}\\ &=\Tutte_{M}(y, x) \end{aligned}$$

となり，所望の結果が得られた．

証明終わり□

二つ目は削除・縮約公式です． これはTutte多項式を再帰的に計算するための基本公式です．

証明

$E^{\prime} \coloneqq E \setminus\{ e \}$ とおく．

(i)$e$ がループならば $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$(i)

$e$ がループであると仮定する． このとき任意の $A \subseteq E^{\prime}$ に対して

$$r_{M}(A \cup \{ e \}) = r_{M}(A), \qquad r_{M}(E) = r_{M}(E^{\prime})$$

である． Tutte多項式の和を $e$ を含む部分集合と含まない部分集合へ分けて総和を計算すると

$$\begin{aligned} \Tutte_{M}(x, y) &= \sum_{e \in D \subseteq E} (x - 1)^{r_{M}(E) - r_{M}(D)} (y - 1)^{\card{D} - r_{M}(D)}\\ &\qquad + \sum_{e \notin S \subseteq E} (x - 1)^{r_{M}(E) - r_{M}(S)} (y - 1)^{\card{S} - r_{M}(S)} \\ &= \sum_{D^{\prime} \subseteq E^{\prime}} (x - 1)^{r_{M}(E^{\prime}) - r_{M}(D^{\prime})} (y - 1)^{\bigl( \card{D^{\prime}} + 1 \bigr) - r_{M}(D^{\prime})} \\ &\qquad + \sum_{S \subseteq E^{\prime}} (x - 1)^{r_{M \backslash e}(E^{\prime}) - r_{M \backslash e}(S)} (y - 1)^{\card{S} - r_{M \backslash e}(S)} \\ &= (y - 1) \Tutte_{M \backslash e}(x, y) + \Tutte_{M \backslash e}(x, y) \\ &= y\Tutte_{M \backslash e}(x, y) \end{aligned}$$

となり，(i)$e$ がループならば $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$(i) が従う．

(ii)$e$ が余ループならば $$\Tutte_{M}(x, y) = x\Tutte_{M/e}(x, y).$$(ii)

$e$ が余ループの場合は双対性から従う． 実際，$e$ が $M$ の余ループであることは，$e$ が $M^{\ast}$ のループであることと同値である． また $(M/e)^{\ast} = M^{\ast} \backslash e$ である． よって，(i)$e$ がループならば $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$(i) と 命題 6.1（Tutte多項式の双対性）任意のマトロイド $M$ に対して $$\Tutte_{M^{\ast}}(x, y) = \Tutte_{M}(y, x)$$ が成り立つ．命題 6.1 より

$$\begin{aligned} \Tutte_M(x, y) &= \Tutte_{M^{\ast}}(y, x)\\ &= x\Tutte_{M^{\ast} \backslash e}(y, x)\\ &= x\Tutte_{(M/e)^{\ast}}(y, x)\\ &= x\Tutte_{M/e}(x, y) \end{aligned}$$

となり，(ii)$e$ が余ループならば $$\Tutte_{M}(x, y) = x\Tutte_{M/e}(x, y).$$(ii) が従う．

(iii)$e$ がループでも余ループでもなければ $$\Tutte_{M}(x, y) = \Tutte_{M \backslash e}(x, y) + \Tutte_{M/e}(x, y).$$(iii)

$e$ はループでも余ループでもないとする． このとき $r_{M}(\{ e \}) = 1$ かつ $r_{M}(E) = r_{M}(E^{\prime})$ である． $e$ を含まない部分集合からの寄与は，定義からそのまま $\Tutte_{M \backslash e}(x, y)$ である． $e$ を含む部分集合を $A \cup \{e\}$，ただし $A \subseteq E^{\prime}$，と書くと， 縮約の階数公式より

$$r_{M/e}(A) = r_{M}(A \cup \{ e \}) - 1, \qquad r_{M/e}(E^{\prime}) = r_{M}(E) - 1$$

となる．したがって $e$ を含む部分集合からの寄与は $\Tutte_{M/e}(x, y)$ である． 以上より

$$\Tutte_{M}(x, y) = \Tutte_{M \backslash e}(x, y) + \Tutte_{M/e}(x, y)$$

が得られる．

証明終わり□

この種の削除・縮約型の不変量は，Tutte–Grothendieck型不変量（または単にT–G不変量）として扱われることが多いです． Tutte多項式の基本性質，普遍性，および応用についての古典的な概説としては Brylawski–Oxley [BO92] が標準的です．

上の公式を少し一般化しておくと，重み多項式との関係が見えやすくなります． 次の形の再帰を満たすマトロイド不変量 $\widetilde{\Tutte}_{M}(s, t, a, b)$ を考えます：

1. $\widetilde{\Tutte}_{U_{0, 0}}(s, t, a, b) = 1$,

2. $e$ がループのとき， $\widetilde{\Tutte}_{M}(s, t, a, b) = s\widetilde{\Tutte}_{M \backslash e}(s, t, a, b)$,

3. $e$ が余ループのとき， $\widetilde{\Tutte}_{M}(s, t, a, b) = t\widetilde{\Tutte}_{M/e}(s, t, a, b)$,

4. $e$ がループでも余ループでもないとき，

   $$\widetilde{\Tutte}_{M}(s, t, a, b) = a\widetilde{\Tutte}_{M \backslash e}(s, t, a, b) + b \widetilde{\Tutte}_{M/e}(s, t, a, b).$$

台集合の大きさに関する帰納法で見ると，一意性が分かります． 空マトロイドで値が決まり，非空の場合は一つの元 $e$ を選べば， 右辺は台集合が一つ小さいマトロイドの値で書かれるためです． 通常のTutte多項式から単純に正規化をし直すことで，その解が次のように得られます． ただし，ここでは $a$, $b$ を可逆な形式的パラメータとして扱います． より厳密には，適切な係数環で考えるか，分母を払った形で読むことにします．

証明

右辺を $\displaystyle \overline{\Tutte}_{M}(s, t, a, b) \coloneqq a^{\card{E} - r_{M}(E)} b^{r_{M}(E)} \Tutte_{M}\left( \frac{t}{b}, \frac{s}{a} \right)$ とおいたとき， $\overline{\Tutte}_{M}(s, t, a, b)$ が実際に上の (a)$\widetilde{\Tutte}_{U_{0, 0}}(s, t, a, b) = 1$,(a)，(b)$e$ がループのとき， $\widetilde{\Tutte}_{M}(s, t, a, b) = s\widetilde{\Tutte}_{M \backslash e}(s, t, a, b)$,(b)，(c)$e$ が余ループのとき， $\widetilde{\Tutte}_{M}(s, t, a, b) = t\widetilde{\Tutte}_{M/e}(s, t, a, b)$,(c)，および(d)$e$ がループでも余ループでもないとき， $$\widetilde{\Tutte}_{M}(s, t, a, b) = a\widetilde{\Tutte}_{M \backslash e}(s, t, a, b) + b \widetilde{\Tutte}_{M/e}(s, t, a, b).$$(d) の漸化式を満たすことを確かめることで $\widetilde{\Tutte}_{M}(s, t, a, b) = \overline{\Tutte}_{M}(s, t, a, b)$ であることを示す．

(a)$\widetilde{\Tutte}_{U_{0, 0}}(s, t, a, b) = 1$,(a)

$U_{0,0}$ の台集合は空集合，階数は $0$ であるから， 例 5.2（空マトロイドと一点マトロイド）空マトロイド $U_{0, 0}$ では，和を取る部分集合は $\emptyset$ だけであるため $$\Tutte_{U_{0, 0}}(x, y) = (x - 1)^{0 - 0}(y - 1)^{0 - 0} = 1$$ である． 単元集合 $E = \{ e \}$ 上の $U_{0, 1}$ では $e$ がループであり， $$\Tutte_{U_{0,1}}(x, y) = (x - 1)^{0 - 0}(y - 1)^{0 - 0} + (x - 1)^{0 - 0}(y - 1)^{1 - 0} = 1 + (y - 1) = y$$ となる． 一方，$U_{1, 1}$ では $e$ が余ループであり， $$\Tutte_{U_{1,1}}(x, y) = (x - 1)^{1 - 0}(y - 1)^{0 - 0} + (x - 1)^{1 - 1}(y - 1)^{1 - 1} = (x - 1) + 1 = x$$ となる．例 5.2 より，

$$\overline{\Tutte}_{U_{0, 0}}(s, t, a, b) = a^{0-0}b^{0}\Tutte_{U_{0,0}}\left( \frac{t}{b}, \frac{s}{a} \right) = 1$$

となり，所望の結果を得る．

(b)$e$ がループのとき， $\widetilde{\Tutte}_{M}(s, t, a, b) = s\widetilde{\Tutte}_{M \backslash e}(s, t, a, b)$,(b)

$e$ がループのとき，$r_{M \backslash e}(E \setminus \{ e \}) = r_{M}(E)$ であるから， 命題 6.2（削除・縮約公式）$M$ を $E$ 上のマトロイドとし，$e \in E$ とする． このとき，以下が成り立つ：

1. $e$ がループならば $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$
2. $e$ が余ループならば $$\Tutte_{M}(x, y) = x\Tutte_{M/e}(x, y).$$
3. $e$ がループでも余ループでもなければ $$\Tutte_{M}(x, y) = \Tutte_{M \backslash e}(x, y) + \Tutte_{M/e}(x, y).$$

命題 6.2(i)$e$ がループならば $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$(i) より，

$$\begin{aligned} \overline{\Tutte}_{M}(s, t, a, b) &= a \cdot a^{\card{E \setminus \{ e \}} - r_{M \backslash e}(E \setminus \{ e \})} b^{r_{M \backslash e}(E \setminus \{ e \})} \frac{s}{a} \Tutte_{M \backslash e}\left( \frac{t}{b}, \frac{s}{a} \right) \\ &= s\overline{\Tutte}_{M \backslash e}(s, t, a, b) \end{aligned}$$

となり，所望の結果を得る．

(c)$e$ が余ループのとき， $\widetilde{\Tutte}_{M}(s, t, a, b) = t\widetilde{\Tutte}_{M/e}(s, t, a, b)$,(c)

$e$ が余ループのとき，$r_{M/e}(E \setminus \{ e \}) = r_{M}(E) - 1$ であるから， 命題 6.2（削除・縮約公式）$M$ を $E$ 上のマトロイドとし，$e \in E$ とする． このとき，以下が成り立つ：

1. $e$ がループならば $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$
2. $e$ が余ループならば $$\Tutte_{M}(x, y) = x\Tutte_{M/e}(x, y).$$
3. $e$ がループでも余ループでもなければ $$\Tutte_{M}(x, y) = \Tutte_{M \backslash e}(x, y) + \Tutte_{M/e}(x, y).$$

命題 6.2(ii)$e$ が余ループならば $$\Tutte_{M}(x, y) = x\Tutte_{M/e}(x, y).$$(ii) より，

$$\begin{aligned} \overline{\Tutte}_{M}(s, t, a, b) &= a^{\card{E \setminus \{ e \}} - r_{M/e}(E \setminus \{ e \})} b^{r_{M/e}(E \setminus \{ e \})} \cdot b \cdot \frac{t}{b} \Tutte_{M/e}\left( \frac{t}{b}, \frac{s}{a} \right) \\ &= t\overline{\Tutte}_{M/e}(s, t, a, b) \end{aligned}$$

となり，所望の結果を得る．

(d)$e$ がループでも余ループでもないとき， $$\widetilde{\Tutte}_{M}(s, t, a, b) = a\widetilde{\Tutte}_{M \backslash e}(s, t, a, b) + b \widetilde{\Tutte}_{M/e}(s, t, a, b).$$(d)

$e$ がループでも余ループでもないとき， 命題 6.2（削除・縮約公式）$M$ を $E$ 上のマトロイドとし，$e \in E$ とする． このとき，以下が成り立つ：

1. $e$ がループならば $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$
2. $e$ が余ループならば $$\Tutte_{M}(x, y) = x\Tutte_{M/e}(x, y).$$
3. $e$ がループでも余ループでもなければ $$\Tutte_{M}(x, y) = \Tutte_{M \backslash e}(x, y) + \Tutte_{M/e}(x, y).$$

命題 6.2(iii)$e$ がループでも余ループでもなければ $$\Tutte_{M}(x, y) = \Tutte_{M \backslash e}(x, y) + \Tutte_{M/e}(x, y).$$(iii) より，

$$\begin{aligned} \overline{\Tutte}_{M}(s, t, a, b) &= a^{\card{E} - r_{M}(E)} b^{r_{M}(E)} \left(\Tutte_{M \backslash e} \left( \frac{t}{b}, \frac{s}{a} \right) + \Tutte_{M/e} \left( \frac{t}{b}, \frac{s}{a} \right) \right) \\ &= a \cdot a^{\card{E \setminus \{ e \}} - r_{M \backslash e}(E \setminus \{ e \})} b^{r_{M \backslash e}(E \setminus \{ e \})} \Tutte_{M \backslash e}\left( \frac{t}{b}, \frac{s}{a} \right) \\ &\quad + a^{\card{E \setminus \{ e \}} - r_{M/e}(E \setminus \{ e \})} b \cdot b^{r_{M/e}(E \setminus \{ e \})} \Tutte_{M/e}\left( \frac{t}{b}, \frac{s}{a} \right) \\ &= a\overline{\Tutte}_{M \backslash e}(s, t, a, b) + b\overline{\Tutte}_{M/e}(s, t, a, b) \end{aligned}$$

となり，所望の結果を得る．

証明終わり□

実際，右辺が上の四つの再帰を満たすことを，命題 6.2（削除・縮約公式）$M$ を $E$ 上のマトロイドとし，$e \in E$ とする． このとき，以下が成り立つ：

1. $e$ がループならば $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$
2. $e$ が余ループならば $$\Tutte_{M}(x, y) = x\Tutte_{M/e}(x, y).$$
3. $e$ がループでも余ループでもなければ $$\Tutte_{M}(x, y) = \Tutte_{M \backslash e}(x, y) + \Tutte_{M/e}(x, y).$$

命題 6.2から直接確認できます． すると，上の主張は削除・縮約に関する四つの再帰式を満たす多項式はすべてTutte多項式から得られるという強力な事実です． この意味で，Tutte多項式は削除・縮約が絡むマトロイド不変量の中で最も偉いものの一つであるという見方ができます． この見方は，Greeneの定理を「重み多項式はTutte多項式の特殊化である」と読むための近道になります．

いよいよ，符号の重み多項式とTutte多項式を結びます． ここで一度，何を示したいのかを整理しておきます． Tutte多項式は，マトロイドの削除・縮約に対して非常にきれいな再帰を満たしました． 一方，符号の重み多項式も，座標を一つ穿孔するか短縮するかによって再帰的に分解できます． Greeneの定理は，この二つの再帰が同じ形をしていることを，明示的な変数変換として書いたものです．

まず，重み多項式側の再帰を確認しておきます． ここでは $e \in E$ を一つ固定し，$M(C)$ において $e$ がループか余ループか，あるいはそのどちらでもないかで場合分けします． 符号に付随するマトロイド $M(C)$ では， $e$ がループであることは，すべての符号語が座標 $e$ に $0$ を持つことと同値です． 実際，$r_{C}(\{ e \}) = \dim \res{C}{\{ e \}} = 0$ となるためには，$\res{C}{\{ e \}} = \{ 0 \}$ であることが必要十分で， これはすべての符号語が座標 $e$ に $0$ を持つことと同値です．

一方，$e$ が余ループであることは，座標 $e$ だけで非零となる符号語が $C$ に存在することと同値です． これは階数を考えるより，双対性に着目した方が理解しやすいかもしれません． 余ループは双対マトロイドでのループであり，双対マトロイドは双対符号とちゃんと対応していました． $e$ が余ループであることは，すべての双対符号 $C^{\perp}$ の符号語が座標 $e$ に $0$ を持つということです． 座標 $e$ だけ非零で，残りがすべて零であるような語はそのようなベクトルと直交するため，$C$ の符号語であり， 逆に $C$ に座標 $e$ だけ非零で，残りがすべて零の符号語が存在すれば，$C^{\perp}$ のすべての符号語は座標 $e$ に $0$ を持ちます． もう少し代数的な説明をすると，$e$ が余ループであるとは，$r_{C}(E) - r_{C}(E \setminus \{ e \}) = 1$ を満たすことでした． これは $C \to \res{C}{E \setminus \{ e \}}$ という射影の核が一次元になることと同値です． この核は $e$ 以外の座標がすべて $0$ であるような符号語全体になります．

証明

$E^{\prime} \coloneqq E \setminus \{ e \}$ とおく．

(i)$e$ が $M(C)$ のループならば $$W_{C}(X, Y) = X W_{C^{\{ e \}}}(X, Y).$$(i)

$e$ はループであると仮定する． このとき $r_{C}(\{ e \}) = 0$ であるから，すべての符号語は座標 $e$ に $0$ を持つ． したがって，$C$ の各符号語は $C^{\{ e \}}$ の符号語に零座標を一つ付け足して延長したものである． 重みは変わらず，長さだけが $1$ 増えるため，重み多項式には $X$ が掛かる． よって $W_{C}(X, Y) = XW_{C^{\{ e \}}}(X, Y)$ となる． 形式的には，

$$\begin{aligned} W_{C}(X, Y) &= \sum_{c \in C} X^{\card{E} - \wt(c)} Y^{\wt(c)} \\ &= \sum_{c \in C} X \cdot X^{(\card{E} - 1) - \wt(\res{c}{E \setminus \{ e \}})} Y^{\wt(\res{c}{E \setminus \{ e \}})} \\ &= X \sum_{c^{\prime} \in C^{\{ e \}}} X^{\card{E \setminus \{ e \}} - \wt(c^{\prime})} Y^{\wt(c^{\prime})} = XW_{C^{\{ e \}}}(X, Y) \end{aligned}$$

である．

(ii)$e$ が $M(C)$ の余ループならば $$W_{C}(X, Y) = \bigl( X + (q - 1)Y \bigr) W_{C_{\{ e \}}}(X, Y).$$(ii)

$e$ は余ループであると仮定する． このとき $r_{C}(E) - r_{C}(E^{\prime}) = 1$ であるから， 射影 $C \to \res{C}{E^{\prime}} = C^{\{ e \}}$ の核は一次元である． その核は座標 $e$ だけに台を持つ一次元部分空間である． 特に，座標 $e$ だけで非零である符号語が存在する． 任意の $c \in C$ からそのような符号語の適当なスカラー倍を引けば，$E^{\prime}$ 上の値を変えずに座標 $e$ を $0$ にすることができる． したがって，$C^{\{ e \}} = C_{\{ e \}}$ であり，$C_{\{ e \}}$ の各符号語は $C$ の中で $q$ 通りに持ち上がる． そのうち一つは座標 $e$ が $0$ で，残り $q - 1$ 個は座標 $e$ が非零である． 前者は重み多項式に $X$ を掛け，後者は $Y$ を掛けるため， 以上の議論を形式的にまとめると

$$\begin{aligned} W_{C}(X, Y) &= \sum_{c^{\prime} \in C_{\{ e \}}} \left( X \cdot X^{\card{E^{\prime}}-\wt(c^{\prime})}Y^{\wt(c^{\prime})} + (q - 1)Y \cdot X^{\card{E^{\prime}} - \wt(c^{\prime})} Y^{\wt(c^{\prime})} \right) \\ &= \bigl( X + (q - 1)Y \bigr) W_{C_{\{ e \}}}(X, Y) \end{aligned}$$

となる．

(iii)$e$ が $M(C)$ のループでも余ループでもなければ $$W_{C}(X, Y) = YW_{C^{\{ e \}}}(X, Y) + (X - Y)W_{C_{\{ e \}}}(X, Y).$$(iii)

$e$ はループでも余ループでもないと仮定する． 余ループでないことから $r_{C}(E) = r_{C}(E^{\prime})$ であり， 射影 $C \to C^{\{ e \}}$ は単射となる． したがって，$C^{\{ e \}}$ の各符号語は $C$ の符号語と一対一に対応する． さらにループでないことから，座標 $e$ への射影 $C \to \F_{q}$ は非零である． 値域は一次元空間 $\F_{q}$ であるから，この写像は全射であり，その核は $C$ の余次元 $1$ の部分空間である． その核を $E^{\prime}$ に制限したものが $C_{\{ e \}}$ であるから， $C^{\{ e \}}$ の符号語のうち，$C$ へ持ち上げたときに座標 $e$ に $0$ を持つものがまさに $C_{\{ e \}}$ である．

したがって，$C^{\{ e \}}$ の符号語を二つに分ける． $C_{\{ e \}}$ に属するものは，$C$ では零座標が一つ付け足されるため $X$ を掛け， $C_{\{ e \}}$ に属さないものは，非零座標が一つ付け足されるため $Y$ を掛ける．

$$W_{C}(X, Y) = \underbrace{\sum_{\substack{c \in C \\ e \notin \supp(c)}} X^{\card{E} - \wt(c)} Y^{\wt(c)}}_{\eqqcolon W_{C}^{-}(X, Y)} + \underbrace{\sum_{\substack{c \in C \\ e \in \supp(c)}} X^{\card{E} - \wt(c)} Y^{\wt(c)}}_{\eqqcolon W_{C}^{+}(X, Y)}$$

とすると，$W_{C_{\{ e \}}}(X, Y) = W_{C}^{-}/X$ かつ $W_{C^{\{ e \}}}(X, Y) = W_{C}^{-}(X, Y)/X + W_{C}^{+}/Y$ である．したがって，

$$\begin{aligned} W_{C}(X, Y) &= W_{C}^{-}(X, Y) + W_{C}^{+}(X, Y) \\ &= Y W_{C^{\{ e \}}}(X, Y) + (X - Y)W_{C_{\{ e \}}}(X, Y) \end{aligned}$$

となり，所望の結果を得る．

証明終わり□

命題 7.1（重み多項式の穿孔・短縮再帰）$C \leq \F_{q}^{E}$ を線形符号とし，$e \in E$ とする．

1. $e$ が $M(C)$ のループならば $$W_{C}(X, Y) = X W_{C^{\{ e \}}}(X, Y).$$
2. $e$ が $M(C)$ の余ループならば $$W_{C}(X, Y) = \bigl( X + (q - 1)Y \bigr) W_{C_{\{ e \}}}(X, Y).$$
3. $e$ が $M(C)$ のループでも余ループでもなければ $$W_{C}(X, Y) = YW_{C^{\{ e \}}}(X, Y) + (X - Y)W_{C_{\{ e \}}}(X, Y).$$

命題 7.1 と 命題 4.6（穿孔・短縮と削除・縮約）任意の線形符号 $C \leq \F_{q}^{E}$ と任意の $S \subseteq E$ に対して $$M(C^{S}) = M(C) \backslash S, \qquad M(C_{S}) = M(C)/S$$ が成り立つ．命題 4.6 を合わせると， 重み多項式の再帰は，マトロイドの削除・縮約再帰と同じ台集合上で動いていることが分かります． ただし，係数はTutte多項式そのものの係数とは異なります． Tutte多項式では，ループ，余ループ，それ以外の場合の係数はそれぞれ $y$, $x$, $1$, $1$ でした． 重み多項式では，それらが $X$, $X + (q - 1)Y$, $Y$, $X - Y$ に置き換わります． この置き換えを正確に反映したものが，Greeneの定理です．

一見すると，$r_{C}(A) = \dim \res{C}{A}$ は「座標集合 $A$ から見える像の次元」だけを記録しており， 個々の符号語の重みを直接数えているようには見えません． しかし，台が $A$ に含まれる符号語の個数は $\card{C(A)} = q^{k - r_{C}(E \setminus A)}$ で決まります．この事実が，Tutte多項式から重み多項式が出てくる核心です．

命題 7.1（重み多項式の穿孔・短縮再帰）$C \leq \F_{q}^{E}$ を線形符号とし，$e \in E$ とする．

1. $e$ が $M(C)$ のループならば $$W_{C}(X, Y) = X W_{C^{\{ e \}}}(X, Y).$$
2. $e$ が $M(C)$ の余ループならば $$W_{C}(X, Y) = \bigl( X + (q - 1)Y \bigr) W_{C_{\{ e \}}}(X, Y).$$
3. $e$ が $M(C)$ のループでも余ループでもなければ $$W_{C}(X, Y) = YW_{C^{\{ e \}}}(X, Y) + (X - Y)W_{C_{\{ e \}}}(X, Y).$$

命題 7.1 と 命題 4.6（穿孔・短縮と削除・縮約）任意の線形符号 $C \leq \F_{q}^{E}$ と任意の $S \subseteq E$ に対して $$M(C^{S}) = M(C) \backslash S, \qquad M(C_{S}) = M(C)/S$$ が成り立つ．命題 4.6 を合わせれば，

となるので所望の結果は再帰から直ちに得られます． しかし，以下ではこの再帰的な見方を背景に置きつつ， 部分集合ごとの台の数え上げから直接証明を試みます． この利点は，変数変換に現れる因子がどこから来るかを明示しやすいためです． また，右辺は一見すると有理式に見えますが，以下の証明で各項の分母が打ち消し合うことが分かります． したがって，Greeneの恒等式は多項式としての等式です．

証明

まず，射影 $C \to \res{C}{E \setminus A}$ の核が $C(A)$ であるから

$$\dim C(A) = k - r_{C}(E \setminus A)$$

が成り立つ．

固定した符号語 $c \in C$ に対して，$S = \supp(c)$ とおくと

$$X^{n - \wt(c)} Y^{\wt(c)} = \sum_{S \subseteq A \subseteq E}(X - Y)^{n - \card{A}} Y^{\card{A}}$$

が成り立つ．実際，右辺は

$$Y^{\card{S}} \sum_{B \subseteq E \setminus S}(X - Y)^{\card{E \setminus S} - \card{B}} Y^{\card{B}} =Y^{\card{S}}X^{\card{E \setminus S}}$$

である．

したがって，和の順序を入れ替えると

$$\begin{aligned} W_{C}(X, Y) &= \sum_{c \in C} \sum_{\supp(c) \subseteq A \subseteq E}(X - Y)^{n - \card{A}} Y^{\card{A}} \\ &= \sum_{A \subseteq E} \card{C(A)}(X - Y)^{n - \card{A}}Y^{\card{A}} \\ &= \sum_{A \subseteq E} q^{k - r_{C}(E \setminus A)}(X - Y)^{n - \card{A}} Y^{\card{A}} \end{aligned}$$

が得られる．ここで $B = E \setminus A$ と書き換えると

$$W_{C}(X, Y) = \sum_{B \subseteq E} q^{k - r_{C}(B)}(X - Y)^{\card{B}} Y^{n - \card{B}}$$

となる．

一方，

$$u \coloneqq \frac{X + (q - 1)Y}{X - Y}, \qquad v \coloneqq \frac{X}{Y}$$

とおくと，

$$u - 1 = \frac{qY}{X - Y}, \qquad v - 1 = \frac{X - Y}{Y}$$

である．したがって

$$\begin{aligned} &Y^{n - k}(X - Y)^{k}\Tutte_{M(C)}(u, v) \\ &\quad= \sum_{B \subseteq E} Y^{n - k}(X - Y)^{k} \left(\frac{qY}{X - Y}\right)^{k - r_{C}(B)} \left(\frac{X - Y}{Y}\right)^{\card{B} - r_{C}(B)}\\ &\quad= \sum_{B \subseteq E} q^{k-r_{C}(B)}(X - Y)^{\card{B}} Y^{n - \card{B}} \end{aligned}$$

を得る．これは先ほど得た $W_{C}(X, Y)$ の表示と一致する．

証明終わり□

Greeneの定理に現れる置換には，幾何的に分かりやすい性質があります．

とおくと

です．つまり，重み多項式は，Tutte平面上の双曲線 $(u - 1)(v - 1) = q$ に沿ったTutte多項式の評価として現れます．

例 7.3（二元反復符号での確認）で見たように，二元反復符号 $C = \{ 000, 111 \}$ では $$\Tutte_{M(C)}(x, y) = x + y + y^{2}$$ である．ここで $q = 2$, $n = 3$, $k = 1$ であるから，Greeneの定理は $$W_{C}(X,Y) = Y^{2}(X - Y) \left( \frac{X + Y}{X - Y} + \frac{X}{Y} + \frac{X^{2}}{Y^{2}} \right)$$ を与える．右辺を整理すると $$W_{C}(X, Y) = X^{3} + Y^{3}$$ となり，反復符号の重み多項式と一致する．例 7.3では，右辺の分母が実際に消えて， 重み多項式そのものが得られることを確認しました． 一般の場合にも，同じキャンセルが定理の証明中で起きています． つまり，Greeneの定理は「Tutte多項式を有理関数として評価している」のではなく， Tutte多項式の特殊化が重み多項式を与えるという多項式恒等式です．

最後に，Greeneの定理からMacWilliams恒等式を導きます．

証明

$n = \card{E}$，$k = \dim C$ とおく． 命題 4.3（双対符号と双対マトロイド）任意の線形符号 $C \leq \F_{q}^{E}$ に対して $$M(C^{\perp}) = M(C)^{\ast}$$ が成り立つ．命題 4.3 より $M(C^{\perp}) = M(C)^{\ast}$ である． また $\dim C^{\perp} = n - k$ である． Greeneの定理とTutte多項式の双対性より

$$\begin{aligned} W_{C^{\perp}}(X, Y) &=Y^{k}(X - Y)^{n - k} \Tutte_{M(C)^{\ast}}\left( \frac{X + (q - 1)Y}{X - Y}, \frac{X}{Y} \right)\\ &=Y^{k}(X - Y)^{n - k} \Tutte_{M(C)}\left( \frac{X}{Y}, \frac{X + (q - 1)Y}{X - Y} \right) \end{aligned}$$

が得られる．

一方，Greeneの定理を $C$ に対して適用し，$X$ の代わりに $X + (q - 1)Y$， $Y$ の代わりに $X - Y$ を代入すると，

$$\begin{aligned} &W_{C}(X + (q - 1)Y, X - Y)\\ &=(X - Y)^{n - k}(qY)^{k} \times \Tutte_{M(C)}\left( \frac{qX}{qY}, \frac{X + (q - 1)Y}{X - Y} \right)\\ &= q^{k} Y^{k}(X - Y)^{n - k} \Tutte_{M(C)}\left( \frac{X}{Y}, \frac{X + (q - 1)Y}{X - Y} \right) \end{aligned}$$

となる．ここで $\card{C} = q^{k}$ であるから，両辺を $\card{C}$ で割れば上で得た $W_{C^{\perp}}(X, Y)$ と一致する．

証明終わり□

ここまでの証明で使った構造をまとめると，次の三点です． 第一に，符号 $C$ から，座標制限の次元 $r_{C}(A) = \dim(\res{C}{A})$ によってマトロイド $M(C)$ が得られます． この階数関数は，座標部分集合 $A$ が符号 $C$ の情報をどれだけ見分けられるかを測っています．

第二に，双対符号は双対マトロイドに対応します ($M(C^{\perp})=M(C)^{\ast}$). これは，符号理論側の双対性とマトロイド側の双対性が同じ構造を見ていることを意味します．

第三に，重み多項式はTutte多項式の特殊化です：

この式は，重み多項式が，符号語を直接数えているだけでなく，座標部分集合ごとの階数情報からも復元できることを示しています．

この三点を組み合わせると，Tutte多項式の双対性

が，そのままMacWilliams恒等式になります． つまり，今回の証明では，MacWilliams恒等式の変数変換は突然現れたものではありません． Tutte平面上の変数入れ替えと，Greeneの定理に現れる特殊化が組み合わさった結果として現れています．

この回で使った概念を，役割ごとに整理しておきます．

階数関数としてのマトロイド

有限集合 $E$ 上の写像 $r \colon 2^{E} \to \mathbb{Z}$ で， 有界性，単調性，劣モジュラ性を満たすものとして定義しました．

符号に付随するマトロイド

線形符号 $C \leq \F_{q}^{E}$ に対して， $r_{C}(A) = \dim(\res{C}{A})$ により $M(C)$ を定義しました．

双対マトロイド

階数関数 $r_{M^{\ast}}(A) = \card{A} - r_{M}(E) + r_{M}(E \setminus A)$ によって定義しました．符号では $M(C^{\perp}) = M(C)^{\ast}$ が成り立ちます．

削除と縮約

マトロイドでは $r_{M \backslash S}(A) = r_{M}(A)$ と $r_{M/S}(A) = r_{M}(A \cup S)- r_{M}(S)$ によって定義しました． 符号では，削除は穿孔，縮約は短縮に対応します．

Tutte多項式

すべての $A \subseteq E$ に対して，$r_{M}(E) - r_{M}(A)$ と $\card{A} - r_{M}(A)$ を同時に記録する二変数多項式として定義しました．

Greeneの定理

符号の重み多項式を，付随するマトロイドのTutte多項式の特殊化として表す定理です．

この中で，MacWilliams恒等式の証明に直接必要だったのは，階数関数，双対，削除・縮約，Tutte多項式，Greeneの定理です． マトロイド理論にはほかにも重要な概念が多くありますが，本稿ではそれらを使わずに進みました． これは省略というより，今回の目的に合わせた選択です．

今回の系統は，「マトロイド・Tutte多項式系」でした． 座標部分集合ごとの制限符号の次元を集めることで， マトロイド $M(C)$ の構造が入り，そのTutte多項式が重み多項式を復元します． この見方では，MacWilliams恒等式は

双対符号に対応する操作は，Tutte多項式では変数 $x$ と $y$ を入れ替える操作である．

という形に整理されます． この整理が，Greeneの定理からMacWilliams恒等式が自然に出る理由です．

今回の証明は，符号理論とマトロイド理論の接点をかなり直接に使っています． より体系的なマトロイド理論，たとえばサーキット，閉包，フラット，単純化，マイナー，表現可能性などは， 別の機会に符号理論から見たマトロイド理論として改めて扱えればと思います．

Tutte多項式そのものの広がりについては， Ellis-Monaghan–Moffatt 編の Handbook [EM22] を参照すると， グラフ，マトロイド，統計物理，符号理論，結び目理論などへの応用の全体像を見渡すことができます．

次回は，MacWilliams恒等式を群作用と巡回指数の側から見ます．

今回の証明では，座標部分集合ごとの制限符号の次元からマトロイド構造を抽出し， Tutte多項式の双対性からMacWilliams恒等式を導きました． 次回は，符号語や座標に対する群作用を使い， 軌道，Burnsideの補題，Pólya計数，巡回指数の言葉で同じ恒等式を見直します．

つまり次回の主役は，

です． 同じMacWilliams恒等式であっても， 今回のように「座標部分集合ごとの制限符号の次元」を見るのではなく， 次回は「群作用による平均」と「軌道の数え上げ」を見ることになります．

参考文献

1. [Whi35] Hassler Whitney. On the Abstract Properties of Linear Dependence. Amer. J. Math., vol. 57, no. 3, pp. 509–533, 1935. doi:10.2307/2371182 引用箇所マトロイドは Whitney [Whi35] によって導入されました． Tutte多項式のマトロイド版の基本文献としては Crapo [Cra69] があり，符号の重み多項式とTutte多項式の関係は Greene [Gre76] によるものです． この定理を出発点として，線形符号の性質がTutte多項式からどのように読み取れるかを概観する文献として， Britz–Cameron [BC22] があります． マトロイド理論の標準的な教科書としては Oxley [Oxl11] をご参照ください．↩1 引用箇所この意味で，マトロイドは線形代数に現れる「次元」の概念を抽象化したものと解釈できます． Whitney [Whi35] によって導入された「マトロイド」は「行列(matrix)+のようなもの(-oid)」に由来しています． 実際，線形符号の生成行列を考えてみると，$\res{C}{A}$ の次元というのは， 生成行列の $A$ でラベル付けされた部分の部分行列の階数に対応しています． 実際，$G$ を $C$ の生成行列とすると，$\res{C}{A}$ は， $G$ の $A$ に属する列だけを残した部分行列 $\res{G}{A}$ の行空間です． すなわち，↩2 引用箇所今回は主題と外れるので詳しく解説しませんが，Whitney [Whi35] の原論文にも登場する通り， マトロイドはグラフの階数も同時に抽象化しており，上の「ループ」や「地峡」という用語は グラフのループ（自己閉路）や地峡（橋）に由来しています．↩3
2. [Cra69] Henry H. Crapo. The Tutte polynomial. Aequationes Math., vol. 3, pp. 211–229, 1969. doi:10.1007/BF01817442 引用箇所マトロイドは Whitney [Whi35] によって導入されました． Tutte多項式のマトロイド版の基本文献としては Crapo [Cra69] があり，符号の重み多項式とTutte多項式の関係は Greene [Gre76] によるものです． この定理を出発点として，線形符号の性質がTutte多項式からどのように読み取れるかを概観する文献として， Britz–Cameron [BC22] があります． マトロイド理論の標準的な教科書としては Oxley [Oxl11] をご参照ください．↩
3. [Gre76] Curtis Greene. Weight enumeration and the geometry of linear codes. Studies in Appl. Math., vol. 55, no. 2, pp. 119–128, 1976. doi:10.1002/sapm1976552119 引用箇所マトロイドは Whitney [Whi35] によって導入されました． Tutte多項式のマトロイド版の基本文献としては Crapo [Cra69] があり，符号の重み多項式とTutte多項式の関係は Greene [Gre76] によるものです． この定理を出発点として，線形符号の性質がTutte多項式からどのように読み取れるかを概観する文献として， Britz–Cameron [BC22] があります． マトロイド理論の標準的な教科書としては Oxley [Oxl11] をご参照ください．↩
4. [BC22] Thomas Britz and Peter J. Cameron. Codes. Handbook of the Tutte polynomial and related topics, pp. 328–344, 2022. doi:10.1201/9780429161612-16 引用箇所マトロイドは Whitney [Whi35] によって導入されました． Tutte多項式のマトロイド版の基本文献としては Crapo [Cra69] があり，符号の重み多項式とTutte多項式の関係は Greene [Gre76] によるものです． この定理を出発点として，線形符号の性質がTutte多項式からどのように読み取れるかを概観する文献として， Britz–Cameron [BC22] があります． マトロイド理論の標準的な教科書としては Oxley [Oxl11] をご参照ください．↩
5. [Oxl11] James Oxley. Matroid theory. Oxford University Press, Oxford, vol. 21, pp. xiv+684, 2011. doi:10.1093/acprof:oso/9780198566946.001.0001 引用箇所マトロイドは Whitney [Whi35] によって導入されました． Tutte多項式のマトロイド版の基本文献としては Crapo [Cra69] があり，符号の重み多項式とTutte多項式の関係は Greene [Gre76] によるものです． この定理を出発点として，線形符号の性質がTutte多項式からどのように読み取れるかを概観する文献として， Britz–Cameron [BC22] があります． マトロイド理論の標準的な教科書としては Oxley [Oxl11] をご参照ください．↩
6. [BO92] Thomas Brylawski and James Oxley. The Tutte polynomial and its applications. Matroid applications, vol. 40, pp. 123–225, 1992. doi:10.1017/CBO9780511662041.007 引用箇所この種の削除・縮約型の不変量は，Tutte–Grothendieck型不変量（または単にT–G不変量）として扱われることが多いです． Tutte多項式の基本性質，普遍性，および応用についての古典的な概説としては Brylawski–Oxley [BO92] が標準的です．↩
7. [EM22] Joanna A. Ellis-Monaghan and Iain Moffatt. Handbook of the Tutte polynomial and related topics. Chapman & Hall/CRC, Boca Raton, FL, pp. xix+784, 2022. doi:10.1201/9780429161612 引用箇所Tutte多項式そのものの広がりについては， Ellis-Monaghan–Moffatt 編の Handbook [EM22] を参照すると， グラフ，マトロイド，統計物理，符号理論，結び目理論などへの応用の全体像を見渡すことができます．↩