Golay符号

三角不等式から球が交わらないことを示し、和集合の元を数える。

lem-golay-hamming-bound の等号により、$v$ からの距離が $t$ 以下の符号語 $c$ があり、$v-c\in v+C$ の重みは $d(v,c)\le t$ である。$u,u'\in v+C$ がともに重み $t$ 以下なら、$u-u'\in C$ で $\operatorname{wt}(u-u')\le2t< d$ なので $u=u'$ である。剰余類の個数は $\lvert\mathbb F_q^n\rvert/\lvert C\rvert=q^{n-k}$ である。$\square$

1 は $u,v$ がともに $1$ の座標の個数を数え、2 は $\mathbb F_3$ の $0$ でない元の平方が $1$ であることを使う。

隣接点は $\mathcal N(N)=\{u_0,\dots,u_4\}$、$\mathcal N(u_i)=\{N,u_{i-1},u_{i+1},l_i,l_{i+1}\}$、$\mathcal N(l_i)=\{S,l_{i-1},l_{i+1},u_i,u_{i-1}\}$、$\mathcal N(S)=\{l_0,\dots,l_4\}$ で、どれも $5$ 個である。
グラフの自己同型（辺を辺に写す頂点の置換）は対蹠の組を対蹠の組に写し、共通の隣接点の個数を保つ。回転 $u_i\mapsto u_{i+1}$、$l_i\mapsto l_{i+1}$ と、下の折りたたみの $\varphi$、$\psi$ が自己同型であり、これらで任意の 2 頂点の組を次の表のどれかに写せるので、表を確かめればよい。

対蹠なのは表の $N,S$ と $u_0,l_3$ だけで、ちょうど共通の隣接点が $0$ 個の組である。$\square$

$A$ は対称なので $B$ も対称である。各行の $1$ は、対角成分と、隣接しない $12-1-5=6$ 個の頂点の位置なので $7$ 個である。整数の行列として $AJ=JA=5J$、$J^2=12J$ だから
$$ B^2=(J-A)^2=J^2-JA-AJ+A^2=2J+A^2\equiv A^2\pmod2 $$
である。$A^2$ の $(v,v')$ 成分は $v$ と $v'$ の共通の隣接点の個数で、lem-golay-icosahedron により $v=v'$ なら $5$、$v\ne v'$ なら $0$ か $2$ なので、$\mathbb F_2$ では $A^2=I$ となり、$B^2=I$ である。
$v\ne v'$ の行の和は、$J$ の行が打ち消し合うので $A$ の 2 行の和に等しく、その $1$ の位置は対称差 $\mathcal N(v)\triangle\mathcal N(v')$ である。重みは $5+5-2\lvert\mathcal N(v)\cap\mathcal N(v')\rvert$ で、lem-golay-icosahedron により $10$ か $6$ である。$\square$

1：$M$ は $I_{12}$ を含むので階数 $12$ で、$\dim\mathcal G_{24}=12$ である。$B$ が対称で $B^2=I$（prop-golay-b）だから $MM^{\mathsf T}=I+BB^{\mathsf T}=I+B^2=2I=0$ であり、$M$ の行どうしの内積はすべて $0$ である。よって $\mathcal G_{24}\subset\mathcal G_{24}^\perp$ で、両辺の次元はともに $12$ だから $\mathcal G_{24}$ は自己双対である。$M$ の各行の重みは $1+7=8$ なので、lem-golay-weights の 1 により、すべての符号語の重みは $4$ の倍数である。
最小距離を調べる。符号語は $c=(x,xB)$（$x\in\mathbb F_2^{12}$）の形で、$y=xB$ とおくと $B^2=I$ より $x=yB$ である。$\operatorname{wt}(c)=\operatorname{wt}(x)+\operatorname{wt}(y)$ が $4$ の $0$ でない符号語 $c$ があったとする。$\operatorname{wt}(x)\le2$ か $\operatorname{wt}(y)\le2$ のどちらかが成り立つ。$\operatorname{wt}(x)\le2$ の場合、$x=0$ なら $c=0$ なので $x\ne0$ であり、$\operatorname{wt}(x)=1$ なら $y$ は $B$ の 1 行で重み $7$、$\operatorname{wt}(x)=2$ なら $y$ は $B$ の相異なる 2 行の和で重み $6$ 以上である（prop-golay-b）。どちらでも $\operatorname{wt}(c)\ge7$ となり矛盾する。$\operatorname{wt}(y)\le2$ の場合は、$x=yB$ なので $x$ と $y$ の役割を入れ替えて同じ議論が使える。よって重み $4$ の符号語はなく、$0$ でない符号語の重みは $8$ 以上である。$M$ の行の重みが $8$ なので最小距離は $8$ である。
2：座標 $j$ を除く写像 $\pi_j\colon\mathcal G_{24}\to\mathbb F_2^{23}$ は線形で、核の元は重み $1$ 以下の符号語なので $0$ だけである。よって像 $\pi_j(\mathcal G_{24})$ は $2^{12}$ 個の元をもつ $12$ 次元の符号で、1 座標を除くと重みは高々 $1$ しか減らないので、最小距離は $7$ 以上である。$t=3$ について
$$ 2^{12}\cdot V_2(23,3)=2^{12}\Bigl(1+23+\binom{23}2+\binom{23}3\Bigr)=2^{12}(1+23+253+1771)=2^{12}\cdot2^{11}=2^{23} $$
なので、lem-golay-hamming-bound の等号が成り立ち、完全符号である。最小距離がちょうど $7$ であることは次のように確かめる。$\mathcal G_{23}$（$j=24$）では、$M$ の最後の行は最後の座標が $B$ の対角成分 $1$ なので、それを除いた符号語の重みは $7$ である。ほかの $j$ でも、$\mathcal G_{24}$ の重み $8$ の符号語で $j$ 番目が $1$ のもの（$M$ の行で $j$ 番目が $1$ のもの）を除くと重み $7$ になる。$\square$

$T$ を $5$ 元部分集合とし、$j\in T$ をとる。座標 $j$ を除いた $\mathbb F_2^{23}$ で、$T\setminus\{j\}$ の座標だけが $1$ の重み $4$ の列を $v$ とする。thm-golay-binary の 2 により $\pi_j(\mathcal G_{24})$ は $3$ 個の誤りを訂正する完全符号なので、$d(v,c')\le3$ となる $c'\in\pi_j(\mathcal G_{24})$ がある。$d(v,0)=4$ なので $c'\ne0$ で、$\operatorname{wt}(c')\ge7$ である。$v$ と $c'$ がともに $1$ の座標の個数を $s$ とすると
$$ 3\ge d(v,c')=\operatorname{wt}(v)+\operatorname{wt}(c')-2s\ge4+7-2s $$
なので $s\ge4$、すなわち $c'$ は $v$ の $1$ の座標をすべて含み、さらに $\operatorname{wt}(c')\le3-4+2\cdot4=7$ だから $\operatorname{wt}(c')=7$ である。$\pi_j(c)=c'$ となる $c\in\mathcal G_{24}$ の重みは $7$ か $8$ で、thm-golay-binary の 1 により $4$ の倍数だから $8$ であり、$c$ の $j$ 番目の成分は $1$ である。よって $c$ の台は $T$ を含むオクタッドである。
一意性：相異なるオクタッドの台 $X,Y$ がともに $T$ を含めば、$\lvert X\cap Y\rvert\ge5$ で、対応する符号語の和の重みは $8+8-2\lvert X\cap Y\rvert\le6$ であり、$0$ でない。これは最小距離 $8$ に反する。
個数：各オクタッドは $\binom85=56$ 個の $5$ 元部分集合を含み、各 $5$ 元部分集合はちょうど 1 つのオクタッドに含まれるので、オクタッドの個数は $\binom{24}5/56=42504/56=759$ である。$\square$

要点は、$c\ne0$ について $\sum_{u\in\mathbb F_5}\chi(u)\chi(u+c)=-1$ となることである。

1：生成行列の行どうしの内積の行列は $I+CC^{\mathsf T}=6I\equiv0\pmod3$ なので、$\mathcal G_{12}$ は自己直交で、次元 $6$ は $12$ の半分だから自己双対である。lem-golay-weights の 2 により重みは $3$ の倍数である。符号語は $c=(x,xC)$ と書け、$y=xC$ とおくと prop-golay-c より $x=-yC$ である。重み $3$ の $0$ でない符号語があったとすると、$\operatorname{wt}(x)+\operatorname{wt}(y)=3$ なので $\operatorname{wt}(x)\le1$ か $\operatorname{wt}(y)\le1$ である。$\operatorname{wt}(x)=0$ なら $c=0$、$\operatorname{wt}(x)=1$ なら $y$ は $C$ の 1 行の $\pm1$ 倍で重み $5$ となり矛盾する。$\operatorname{wt}(y)\le1$ の場合も $x=-yC$ から同様に矛盾する。よって $0$ でない符号語の重みは $6$ 以上で、生成行列の行の重みは $1+5=6$ だから最小距離は $6$ である。
2：最後の座標を除く写像は、重み $1$ 以下の符号語が $0$ だけなので単射であり、$\mathcal G_{11}$ は $3^6$ 個の元をもつ $6$ 次元の符号で、最小距離は $5$ 以上である。生成行列の第 1 行は最後の成分が $C_{\infty4}=1$ なので、除くと重み $5$ になり、最小距離は $5$ である。$t=2$ について
$$ 3^6\cdot V_3(11,2)=3^6\Bigl(1+11\cdot2+\binom{11}2\cdot4\Bigr)=3^6(1+22+220)=3^6\cdot3^5=3^{11} $$
なので完全符号である。$\square$