66

数理解析研究所講究録
第2003巻 2016年 66-73

Triply even codes constructed from distance regular graphs
弘前大学理工学研究科

別宮耕一

Koichi BETSUMIYA

Graduate School of Science and Technology,
Hirosaki University

2016年1月6日

序
ここでは,代表的な距離正則グラフであるJohnson グラフ J(n, 2) とHammingグラフ

H(2, n) から極大な立方重偶符号を構成法し,それらの性質を述べる.
なお,立方重偶符号の基本的な性質については [1] による.紹介する例はMagma[2] を用いて計算した.

1

立方重偶符号
二元体 \mathb {F}_{2} 上の線型符号 C のすべての符合語の Hamming 重みが8の倍数であるとき, Cを立方重偶符号という.立方重偶符号 C が極大であるとは, C を含む立方重偶符号が存在しないことをいう.

2

極大性の判定法
本原稿を執筆時点で,立方重偶符号の極大性を判定する一般的な方法は確立できていな

い.ここでは,ある種の立方重偶符号の極大性を判定するために有用な補題を述べる [1].
この補題は立方重偶符号が極大であるための十分条件を与える.
補題1. C を立方重偶符号とする.このとき,

C\subset(C*C)^{\perp} となる.

証明. u_{1}, u_{2}, u_{3}\in C について,wt (u_{1}+u_{2})= wt (u_{1})+\mathrm{w}\mathrm{t}(u_{2})-2\mathrm{w}\mathrm{t}(u_{1}*u_{2})\equiv 0(mod8) となるので, \mathrm{w}\mathrm{t}(u_{1}*u_{2})\equiv 0 (mod4) となる.同様にして, \mathrm{w}\mathrm{t}(u_{1}*u_{2}*u_{3})\equiv 0(mod2) が得られる.従って,任意の u_{1} u2, u3\in C について, u_{1} \perp(u_{2}*u_{3}) となるので,,

C\subset(C*C)^{\perp} となる口

命題2. C を長さ n の立方重偶符号とする.

(i) C=(C*C)^{\perp} ならば,

C は極大立方重偶符号である.

(ii) n\not\equiv 0 (mod8) で, C+\langle 1\rangle=(C*C)^{\perp} ならば,

C は極大立方重偶符号である.

67

証明.まず,(i) を示す.

D\supset C を立方重偶符号とする.補題1と仮定より,

C\subset D\subset(D*D)^{\perp}\subset(C*C)^{\perp}=Cとなる.これは C=D となることを示している.
D\supset C を立方重偶符号とする.補題1と仮定より,

次に,(ii) を示す.

C\subset D\subset(D*D)^{\perp}\subset(C*C)^{\perp}=C+\{1\}となる.もし, C\subsetneq D とすると, 1\in D となるが,これは,D が立方重偶符号であることに矛盾する.口3

重偶符号を用いた構成法
距離正則グラフから極大な立方重偶符号を構成する方法を述べる前に,自明な立方重偶符号の構成法について述べ,その立方重偶符号を極大なものに拡張する方法を述べる [1].
まず,

u=(u_{1}, \ldots, u_{n_{1}}))v=(v_{1}, . . . , v_{n_{2}}) に対して, (u|v)=(u_{1}, . . . , u_{n_{1}}, v_{1}, . . . , v_{n_{2}})の重偶符号を C に対して, \mathcal{D}(C) :=\{(u|u)\in \mathbb{F}_{2}^{2n}|u\in C\} とと記号を定義する.長さnすると, \mathcal{D}(C) は明らかに立方重偶符号となるが,極大ではない.この \mathcal{D}(C) を極大な立方重偶符号に拡張する方法を述べる.

D_{1}\subset \mathbb{F}_{2}^{n_{1} , D2\subset \mathbb{F}_{2}^{n_{2} に対して, D_{1}\oplus D_{2}:=\{(u|v)\in \mathbb{F}_{2}^{n_{1}+n_{2}}|u\in D_{1}, v\in D2\} と表記し, D_{1} とD2の直和と呼ぶ.非自明な符号の直和と置換同値な符号を可約といい,可約でないものを既約という.

Dを既約な重偶自己双対符号とする. 0, 1\in D に対して,\overline{\mathcal{D}}(D)=\mathcal{D}(D)+\{(0|1)) と定義すると次が成立する.
本節では以下 D を既約な重偶双対符号とする.

定理3. \tilde{\mathcal{D} (D) は極大な立方重偶符号となる.

証明の前に,必要な補題を示す.
補題4.

(D*D)^{\perp}=\langle 1\rangle.

証明. v\in(D*D)^{\perp},

x, y\in D について,D^{\perp}=D となる.今, \{ 1,{ j_{1} i2,

.

.

.

,

(v*x)\cdot y=v\cdot(x*y)=0 となるので, (v*x)\inn\} のベキ集合と \mathb {F}_{2}^{n} を同一視して,

v=\{i_{1}, i2, . . . , i_{t}\},D_{1}:=\{(u_{i_{1}}, \ldots, u_{i_{t}})\in \mathbb{F}_{2}^{t}| (u\mathrm{l}, . . . , u_{n})\in D\},
D_{2}:=\{(u_{j_{1}}, \ldots, u_{j_{s}})\in \mathbb{F}_{2}^{s}|(u_{1}, \ldots, u_{n})\in D\} と定義すると, D\cong D_{1}\oplus D_{2} となる.
1+v=

,

.

.

.

,

is} としたとき,

よって,もし, v\not\in\langle 1\} とすると,

補題5.

D が既約であることに矛盾する.

(\tilde{\mathcal{D} (D)*\overline{\mathcal{D} (D) ^{\perp}=\tilde{\mathcal{D} (D).

\square68

証明. \dim D=k とする.補題4より,\tilde{\mathcal{D}}(D)*\tilde{\mathcal{D}}(D)=D\oplus\{0\}+\mathcal{D}(D)*\mathcal{D}(D)=D\oplus\{0\}+\mathcal{D}(D*D)=D\oplus\{0\}+\mathcal{D}(\langle 1\rangle^{\perp}) となるので, \dim(\tilde{\mathcal{D}}(D)*\overline{\mathcal{D}}(D))=k+2k-1=

3k-1=4k-\dim\overline{\mathcal{D}}(D) となる.補題1より, (\tilde{\mathcal{D} (D)*\overline{\mathcal{D} (D) ^{\perp}\supset\overline{\mathcal{D} (D) となるので,
口(\tilde{\mathcal{D} (D)*\tilde{\mathcal{D} (D) ^{\perp}=\overline{\mathcal{D} (D) となる
定理3の証明.補題5, 命題2(i) より,\tilde{\mathcal{D} (D) は極大立方重偶符号となる

命題6. i\in\{1, . . . , k\} について, C_{i} を立方重偶自己同型符号とし,

口(C_{i}*C_{i})^{\perp}=C_{i} とする.このとき, C_{1}\oplus\cdots\oplus C_{k} は極大立方重偶符号となる.

証明. C:=C_{1}\oplus\cdots\oplus C_{k} とすると, C*C=\oplus_{i=1}^{k}C_{i}*C_{i}=\oplus_{i=1}^{k}C_{i}^{\perp}=C^{\perp} となる.
系7. D_{1}

,

.

.

.

,

Dk を既約な重偶自己同型符号とする.このとき,\square\tilde{\mathcal{D} (D_{1})\oplus\cdots\oplus\tilde{\mathcal{D} (D_{k}) は極大立方重偶符号となる.
例8. Hs を[8, 4, 4] 拡張 Hamming 符号とする.Hs は既約な重偶自己双対符号である.

\tilde{\mathcal{D} (H_{8}) は[16, 5, 8] Reed‐Muller 符号 \mathrm{R}\mathrm{M}(4,1) と同値であり,極大立方重偶符号となる.
距離正則グラフを用いた構成法

44.1

千吉良‐原田‐北詰符号

G を $\Omega$_{n}:=\{1, . . . , n\} 上の置換群とする.

I(G):=\{g\in G\backslash \{1_{G}\}|g^{2}=1_{G}\} とし,\mathrm{F}\mathrm{i}\mathrm{x}_{ $\Omega$}.(g):=\{x\in$\Omega$_{n}|x^{g}=x\} と表記することとする.本節では $\Omega$_{n} のべキ集合と \mathb {F}_{2}^{n} を自然に同一視する.この同一視のもとで, \mathrm{C}\mathrm{H}\mathrm{K}(G, $\Omega$):=\{\mathrm{F}\mathrm{i}\mathrm{x}_{$\Omega$_{n} (g)\in \mathbb{F}_{2}^{n}|g\in I(G)\rangle^{\perp} と定義する.この符号を千吉良‐原田‐北詰符号と呼ぶ [5].
4.2

Johnson グラフ J(n, 2) を用いた構成法

X:=\left(\begin{ar ay}{l} $\Omega$_{n}\ k \end{ar ay}\right), E\{\{ $\alpha$, $\beta$\}\in\left(\begin{ar ay}{l} X\\ 2 \end{ar ay}\right) | $\alpha$\cap $\beta$|=k-1\} とする.このとき隣接構造

J(n, k)=(X, E) をJohnson グラフと呼ぶ.
Johnson

グラフ

J(n, 2) の自己同型群はn次対称群と同型である.つまり,Aut (J(n, 2))\cong S_{n} であることはよ く知られている

[6].

この

S_{n} と J(n, 2)て,千吉良‐原田‐北詰符号 CHK (S_{n}, \left(\begin{ar ay}{l $\Omega$_{n}\ 2 \end{ar ay}\right) を構成する. i\in\{0 1 \} について,,

W_{i}:=\{ left(\begin{ar y}{l A\ 2 \end{ar y}\right)\cup\left(\begin{ar y}{l $\Omega$_{n}\backsla hA\ 2 \end{ar y}\right)とし,A\subset$\Omega$_{n},\overline{W_{i}}:=\{$\Omega$_{n}\backslash A|A\in W_{i}\} とすると次が成立する.

|A|\equiv i(mod2)

\}

につい

69

定理9. n\equiv 2 (mod4)のとき,\mathrm{C}\mathrm{H}\mathrm{K}(S_{n}, \left(\begin{ar ay}{l} $\Omega$_{n}\ 2 \end{ar ay}\right) =\overline{W}_{0}\cup W_{1} となる.

証明の前に,必要な補題を示す.

Y\subset\left(\begin{ar ay}{l $\Omega$_{n}\ 2 \end{ar ay}\right) が次の条件をみたすものとする.

補題10.

(i) ある \{u, v, w\}\in\left(\begin{ar ay}{l} $\Omega$_{n}\ 3 \end{ar ay}\right) について,(ii)(^{\{u,v' w\}}2 ) \subset Y,|\{(Y, \mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar ay}{l} $\Omega$_{n}\ 2 \end{ar ay}\right)( $\sigma$) | $\sigma$\in I(S_{n})\}|=1.

\mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar ay}{l} $\Omega$_{n}\ 2 \end{ar ay}\right)( $\sigma$)=\{\{i, j\}\in\left(\begin{ar ay}{l} $\Omega$_{n}\ 2 \end{ar ay}\right)|\{i^{ $\sigma$}, j^{ $\sigma$}\}=\{i, j\}\} とする.

ただし,

このとき,ある A\subset$\Omega$_{n} について,

Y=\left(\begin{ar ay}{l} A\ 2 \end{ar ay}\right)\cup(^{$\Omega$_{n_{2} \backslash A} ) となる.

証明. Y=$\Omega$_{n} の場合は補題が成立するので,以下, Y\subset>$\Omega$_{n} とする. A をグラフ $\Gamma$_{Y}=($\Omega$_{n}, Y) の最大クリークとすると,(i) より, |A|-\geq 3 となる. A:=$\Omega$_{n}\backslash A とする.
まず, |A|\equiv 0 (mod2) の場合を考える.
し,A=\{u_{1}, . . . , u_{k}\}\cup\{v_{1}, . . . , v_{k}\} を A の分割と\overline{A}=\{x_{1}, . . . , x_{l}\}\cup\{x_{1}, . . . , v_{l}\} を且の分割とする.
$\sigma$:=(u_{1}v_{1})(u_{2}v_{2})\cdots(u_{k}v_{k})(x_{1}y_{1})\cdots(x_{l}y_{l}),$\sigma$':=(u_{1}x_{1})(v_{1}y_{1})(x_{1}y_{1})(u_{1}v_{1}) $\sigma$.
とする. A が $\Gamma$_{Y} の最大クリークであることより,\{u, x_{1}\}\not\in Y となる u\in A が存在する.

$\sigma$''=(uu_{1})$\sigma$'(uu_{1}) とする.
(ii) より,(Y, { \{u, x_{1}(Y,\mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar ay}{l $\Omega$_{n}\ 2 \end{ar ay}\right)($\sigma$')=0=(Y,\mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar ay}{l $\Omega$_{n}\ 2 \end{ar ay}\right)($\sigma$') となるため, (Y, \{\{u_{1}, x_{1}となる.よって, \{u_{1}, x_{1}\}\not\in Y が得られる. u_{1}\in A, x_{1}\in

=

は任意の

Y\subset\left(\begin{ar ay}{l A\ 2 \end{ar ay}\right)\cup\left(\begin{ar ay}{l A\ 2 \end{ar ay}\right)- となる.
逆に,(ii) より, (Y, \mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar ay}{l $\Omega$_{n}\ 2 \end{ar ay}\right)( $\sigma$) =(Y, \mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar ay}{l $\Omega$_{n}\ 2 \end{ar ay}\right)($\sigma$') となるため, (Y, \{\{u_{1}, v_{1}\}, \{x_{1} yl

元であるため,,(Y, { \{u_{1}, x_{1}\}, \{v_{1}, y_{1}
任意の元なので,=0となる.よって, \{x_{1}, y_{1}\}\in Y が得られるが,

,

.

.

.

,

y_{1}\in\overline{A} はY\supset\left(\begin{ar ay}{l A\ 2 \end{ar ay}\right)- となる.従って, Y=\left(\begin{ar ay}{l A\ 2 \end{ar ay}\right)\cup\left(\begin{ar ay}{l A\ 2 \end{ar ay}\right)- が得られる.

次に, |A|\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d} 2) の場合を考える. A= \{ uo, u_{1}\{ xo, x_{1}x_{1},=

x_{l}\}\cup { y_{1}

,

.

.

.

,

yl} をそれぞれ A

,

,

.

.

.

,

u_{k}\}\cup\{v_{1}, . . . , v_{k}\}, \overline{A}=の分割とする.ここで,$\tau$\in

I(Sのを次のように定義する.

$\tau$=(u_{0}x_{0})(u_{1}v_{1})(u_{2}v_{2})\cdots(u_{k}v_{k})(x_{1}y_{1})\cdots(x_{l}y_{l})A が ($\Omega$_{n}, Y) の最大クリークであることより,$\tau$'':=(uu_{0}) $\tau$(uu_{0}) とすると,(ii) より,\{u, x_{0}\}\not\in Y となる u\in A が存在する.今,(Y,\mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar ay}{l $\Omega$_{n}\ 2 \end{ar ay}\right)($\tau$) =(Y,\mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar ay}{l $\Omega$_{n}\ 2 \end{ar ay}\right)($\tau$') となるので,(Y, \{\{u_{0}, x_{0} =(Y, \{\{u, x_{0} =070が得られる.従って, \{ uo, xo\}\not\in Y となる. uo\in A,

xo\in 万は任意の元なので,

Y\subset\left(\begin{ar y}{l A\ 2 \end{ar y}\right)\cup\left(\begin{ar y}{l A\ 2 \end{ar y}\right)- となる.
逆に,$\tau$':=(u_{1}x_{1})(v_{1}y_{1})(x_{1}y_{1})(u_{1}v_{1}) $\tau$ とすると,(ii) より,(Y, \mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar ay}{l $\Omega$_{n}\ 2 \end{ar ay}\right)($\tau$') となるので,(Y, \{\{u_{1}, v_{1}\}, \{x_{1}, y_{1}=(Y, \{\{u_{1}, x_{1}\}, \{v_{1}, y_{1}=(Y,\mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar ay}{l $\Omega$_{n}\ 2 \end{ar ay}\right)($\tau$)=O.

\{x_{1}, y1\} \in Y となる. x_{1}, y1\in 万は任意の元なので, Y\supset\left(\begin{ar ay}{l A\ 2 \end{ar ay}\right)- が得\squareられる.よって, Y=\left(\begin{ar ay}{l A\ 2 \end{ar ay}\right)\cup\left(\begin{ar ay}{l A\ 2 \end{ar ay}\right)- となり,補題が示された.

が得られる.従って,

定理9の証明. n\equiv 2 (mod4)より,任意の $\sigma$\in I(S_{n}) について,となるので,もし,(Y, \mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar ay}{l} $\Omega$_{n}\ 2 \end{ar ay}\right)( $\sigma$) \equiv k(\mathrm{m}\mathrm{o}\mathrm{d} 2)とすると,|\mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar y}{l $\Omega$_{n}\ 2 \end{ar y}\right)($\sigma$)|\equiv1 (mod2)($\Omega$_{n}\backslash Y, \mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar ay}{l} $\Omega$_{n}\ 2 \end{ar ay}\right)( $\sigma$) \equiv 1+k(mod2)となる. |Y|\equiv 1 (mod2)のとき,Ramsay の定理 [8, Chapter 9] より,R2 ( 3, 3)=6となるので,グラフ ($\Omega$_{n}, Y) の中に頂点数が3以上のクリークは存在しないとすると,その補グラフ ($\Omega$_{n}, \overline{Y}) が頂点数が3以上のクリークを含む.従って,補題10より,\{Y\subset\left(\begin{ar y}{l $\Omega$_{n}\ 2 \end{ar y}\right) |\{(Y, \mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar ay}{l} $\Omega$_{n}\ 2 \end{ar ay}\right)( $\sigma$) | $\sigma$\in I(S_{n})\}|=1\}=W_{0}\cup W_{1}\cup\overline{W}_{0}\cup\overline{W}_{1}
実際,\{(Y,\mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar y}{l $\Omega$_{n}\ 2 \end{ar y}\right)($\sigma$)| \sigma$\inI(S_{n})\= left\{ begin{ar y}{l \{1 }&\mathrm{i}\mathrm{f}Y\inW_{0}\cup\overline{W}_{1\ \{0 }&\mathrm{i}\mathrm{f}Y\in overline{W}_{0\cupW_{1} \end{ar y}\right.
となるので,CHK(S_{n},\left(\begin{ar ay}{l $\Omega$_{n}\ 2 \end{ar ay}\right)=\langle\{ mathrm{F}\mathrm{i}\mathrm{x}\left(\begin{ar ay}{l $\Omega$_{n}\ 2 \end{ar ay}\right)($\sigma$)|$\sigma$\inI(S_{n})\} rangle^{\perp}=\overline{W}_{0}\cupW_{1}が得られる.口$\Omega$_{n}=A_{1}\cup A_{2}\cup A_{3}\cup A_{4} を |A_{1}\cup A_{2}|\equiv|A_{1}\cup A_{3}|\equiv 0 (mod2)をみたす分割とする.

\overline{\left(\begin{ar ay}{l A_{1}\cupA_{2}\ 2 \end{ar ay}\right)\cup\left(\begin{ar ay}{l A_{3}\cupA_{4}\ 2 \end{ar ay}\right)}+\overline{\left(\begin{ar ay}{l A_{1}\cupA_{3}\ 2 \end{ar ay}\right)\cup\left(\begin{ar ay}{l A_{2}\cupA_{4}\ 2 \end{ar ay}\right)}=\left(\begin{ar ay}{l A_{1}\cupA_{4}\ 2 \end{ar ay}\right)\cup\left(\begin{ar ay}{l A_{2}\cupA_{3}\ 2 \end{ar ay}\right) となるので, \overline{W}0 は線形部分空間となっている.
ここで,J(n, 2) の隣接行列を生成行列とする線形二元符号を T_{n} とする.このとき,ここまでの議論を踏まえると, \overline{W}_{0}=T_{n} となることが分かり,以下の先行の結果を直ちに導出することができる.

定理11 (Haemers, Peeters and van Rijckevorsel [7, Subsection 4.1]). n\equiv 2 (mod4) とする.このとき, T_{n} の重み枚挙多項式は

W_{T_{n} (x,y)=\displaystyle\sum_{l=0}^{\lfo r(n-1)/4\rflo r}\left(\begin{ar ay}{l n\ 2l \end{ar ay}\right)x^{2l(n-2l)}y^{(^{n})-2l(n-21)}2

71となる.特に, T_{n} は次元 n-2 の立方重偶符号となる.

更に, T_{n}*T_{n} の次元を計算し,命題2(ii) を適用することで,次が確認できる.
定理12 ([1]). T_{n} は極大立方重偶符号である.
4 3
\cdot

Hamming グラフ H(2, n) を用いた構成法

X:=$\Omega$_{n}^{d} E:=\{\{(a_{1}, \ldots, a_{d}), (b_{1}, \ldots, b_{d})\}\in\left(\begin{array}{l} X\\ 2 \end{array}\right)|d_{H}((a_{1}\ldots, a_{d}), (b_{1}, \ldots, b_{d}))=d1\} とする.ただし, d_{H} はHamming 距離とする.つまり, d_{H}((a_{1}\ldots, a_{d}) , (b_{1}, \ldots, b_{d})):=\#\{i\in\{1, . . . , d\}|a_{i}\neq b_{i}\} と定義される.このとき隣接構造 H(d, n)= (X, E) を,

Hamming グラフと呼ぶ.

H(2, n) の隣接行列を生成行列とする線形二元符号を \overline{H}_{n} とし, H(2, n) の隣接行列の偶数個の行ベクトルの和全体がなす \tilde{H}_{n} の部分符号を H_{n} とする.

Hamming グラフ H(2, n) の自己同型群について,Aut (H(2, n))\cong S_{n} ?2となることはよ‐
く知られている [6]

この S_{n} ?2とH(2, n) に関する千吉良‐原田‐北詰符号 |(S_{n}?2, H(2, n))について,次が成立する.
定理13. m を正整数, n=4m とする.このとき千吉良‐原田‐北詰符号は CHK(Sn?2, $\Omega$_{n}^{2} )=\overline{H}_{n} となり,次元は 2n-2 である.加えて, H_{n} は極大立方重偶符号となり,次元は 2n-3となる.更に,重み枚挙多項式は

W_{H_{n}(x,y)=\displayst le\sum_{=0}^{2_7}n^{2}x^{8u}y^{16rn^{2}-8u}\sum_{st=m^{2}-u\left(\begin{ar y}{l 4m\ 2(m-t) \end{ar y}\right)\left(\begin{ar y}{l 4m\ 2(m-s) \end{ar y}\right)u-m\leqt,s\leqm.
となる.

証明の前に,必要となる記号の導入と補題を示す.

$\sigma$\in I(S_{n}?2) に対して, \mathrm{F}\mathrm{i}\mathrm{x}_{$\Omega$_{n}^{2} ( $\sigma$) をsupport とする n\times n 行列を E_{ $\sigma$} と表すこととする.
つまり, E_{ $\sigma$}=(f_{ij}) を (i, j)\in \mathrm{F}\mathrm{i}\mathrm{x}_{$\Omega$_{n}^{2} ( $\sigma$) のときん =1,
で定める.

(i, j)\not\in \mathrm{F}\mathrm{i}\mathrm{x}_{$\Omega$_{n}^{2} ( $\sigma$) のときfij =0

x=(x_{1}, \ldots, x_{n})\in \mathbb{F}_{2}^{n} に対して, n\times n 行列を R_{x}={}^{t}(x_{1}\cdots x_{n} ) (1\cdots 1) と定める.

補題14. A を \mathb {F}_{2} を成分とする nx n 行列とする.もし,任意の $\sigma$\in I(S_{n} ?2 ) に対して,(A, E_{ $\sigma$})=0 とすると, \mathrm{w}\mathrm{t}(x)+\mathrm{w}\mathrm{t}(y)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d} 2) をみたす,ある x, y\in \mathbb{F}_{2}^{n} について,
A=R_{x}+ 究四となる.
証明. A=(a_{ij}) と定め, \{x, y\}, \{z, w\}\in\left(\begin{ar ay}{l} $\Omega$_{n}\ 2 \end{ar ay}\right) とする.適当な番号付けの下で $\Omega$_{n}\backslash \{x, y\}=72\{u_{1}, . . . , u_{n-2}\} と定め,同様に $\Omega$_{n}\backslash \{z, w\}=\{v_{1}, . . . , v_{n-2}\} と定める.更に,置換を次のように定める.

$\sigma$:=((u_{1}, u_{2})\cdots(u_{n-3}, u_{n-2}), (v_{1}, v_{2})\cdots(v_{n-3}, v_{n-2}))\in S_{n}\times S_{n}\subset S_{n}?2.
その設定の下で (A, E_{ $\sigma$})=\#\{(i, j)\in\{x, y\}\times\{z, w\}|a_{ij}=1\} となることが分かる.もし(A, E_{ $\sigma$})=0 ならば, (a_{xw}, a_{yw})\in\{(a_{xz}, a_{yz}), (1+a_{xz}, 1+a_{yz})\} となる.従って,任意に対して,(a_{i1}, \ldots, a_{in})+(a_{11} , . . . , a_{1n}) (a_{1i}, . . . , a_{ni})+(a_{11}, . . . , a_{n1})\in\{0 1 \} なることが分かる.これは,ある x, y\in \mathbb{F}_{2}^{n} について, A=R_{x}+^{t}R_{y} となることを意味する.
逆に $\tau$\in S_{n}t2 を (x, y)\in$\Omega$_{n}^{2} について (x, y)^{ $\tau$}=(y, x) と定める.このとき x, y\in \mathbb{F}_{2}^{n} について, (R_{x}+{}^{t}R_{y}, E_{ $\tau$})=\#\{i\in$\Omega$_{n}|a_{ii}=1\}\equiv \mathrm{w}\mathrm{t}(x+y)(\mathrm{m}\mathrm{o}\mathrm{d} 2) が得られる.次に,($\sigma$_{1}, $\sigma$_{2})\in S_{n}\times S_{n} とし, $\tau$\in S_{n} ?2を先に定めたものとする.もし, (($\sigma$_{1}, $\sigma$_{2}) $\tau$)^{2}=1 とす
ると, $\sigma$_{1}=$\sigma$_{2}^{-1} となる.従って, $\sigma$\in S_{n} に対して $\alpha$:=( $\sigma,\ \sigma$^{-1}) $\tau$ と定めると, x, y\in \mathbb{F}_{2}^{n}について, (R_{x}+{}^{t}R_{y}, E_{ $\alpha$})\equiv \mathrm{w}\mathrm{t}(x+y) (mod2)となることが分かる.
,,

よって,補題は証明された.ロ定理13の証明.まず,に選び,x, y\in \mathbb{F}_{2}^{n} をwt (x)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d} 2) ,2a :=\mathrm{w}\mathrm{t}(x) and 2b:=\mathrm{w}\mathrm{t}(y)wt\mathrm{w}\mathrm{t}(y)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d} 2) となるようと定める.更に A :=R_{x}+{}^{t}R_{y} とすると(A)=2b(4m-2a)+2a(4m-2b)=-8(m-a)(m-b)+8m^{2}.
となる.従って,n\equiv 0(mod4) に関して, H_{n} が立方重偶符号となることが分かる.

更に, A=R_{x}+{}^{t}R_{y} について, \#\{(u, v)\in \mathbb{F}_{2}^{n}|A=R_{u} 十 {}^{t}R_{v}\}=\#\{(x, y) (1+x, 1+,y)\}=2 となることと,補題14より,|\mathrm{C}\mathrm{H}\mathrm{K}(S_{n} ? 2, $\Omega$_{n}^{2})|=\# { R_{x}+t_{R_{y}}|x, y\in \mathbb{F}_{2}^{n} wt (x+y)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d} 2) },=\displaystle\frac{1}2\sum_{k=0}^{n\sum_{l=0}^{n-1}\left(\begin{ar y}{l n\ k \end{ar y}\right)\left(\begin{ar y}{l n&-1\ &l \end{ar y}\right)=2^{2n-2},|H_{n}|=\#\{R_{x}+t_{R_{y}}|x, y\in \mathbb{F}_{2}^{n}, \mathrm{w}\mathrm{t}(x)\equiv 0 (mod2), \mathrm{w}\mathrm{t}(y)\equiv 0 (mod2) \}=\displaystle\frac{1}2\sum_{k=0}^{n-1}\sum_{l=0}^{n-1}\left(\begin{ar y}{l n&-1\ &k \end{ar y}\right)\displaystle\ ft(\begin{ar y}{l n&-1\ &l \end{ar y}\right)=2^{2n-3}となることが分かる.つまり \dim CHK (S_{n}l2, $\Omega$_{n}^{2})=2n-2, \dim H_{n}=2n-3 となる.

加えて, u:=-(m-a)(m-b)+m^{2} とすると,」H_{n} の重み枚挙多項式が得られる.

73\dim(H_{n}*H_{n})\geq(n-1)^{2}+2 となることを示す.

ここで,そのために,まず\mathcal{E}:=\{A\in \mathbb{F}_{2}^{n\times n}|A^{t}(1\cdots 1)={}^{t}(0\cdots 0), (1\cdots 1)A=(0\cdots 0)\}とすると, \mathcal{E}\subset H_{n}*H_{n} が得られる.なぜなら,任意の \mathcal{E} の元は\{R_{\{i,n\}}\circ {}^{t}R_{\{j,n\}}|i, j\in\{1, . . . , n-1\}\}の一次結合で得られる.ただし,

0はHadamard積を表す.次に E_{1}

,

.

.

.

,

E_{(n-1)^{2}} を \mathcal{E} の基底とする.そのとき,
E_{1}

,

.

.

.

E_{(n-1)^{2}}, R_{\{n\}}=R_{\{1,n\}}\circ R_{\{2,n\}}, {}^{t}R_{\{n\}}={}^{t}R_{\{1,n\}}\circ {}^{t}R_{\{2,n\}}は H_{n}*H_{n} において一次独立となる.よって \dim(H_{n}*H_{n})\geq(n-1)^{2}+2 が言えた.

補題1より, H_{n}\subset(H_{n}*H_{n})^{\perp} となるので, \dim(H_{n}*H_{n})^{\perp}\leq n^{2}-(n-1)^{2}-2=2n-3となることが分かる.従って H_{n}=(H_{n}*H_{n})^{\perp} となり,命題2となるので, H_{n} は極大立

方重偶符号となる

口

参考文献[1] K. Betsumiya and A. Munemasa, On triply even binary codes, J. London Math.
Soc.

(2) 86 (2012), 1‐16, doi: 10. 1112/\mathrm{j}\mathrm{l}\mathrm{m}\mathrm{s}/\mathrm{j}\mathrm{d}\mathrm{r}054.

[2] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user
language, J. Symbolic Comput., 24 (1997), 235‐265.

[3] K. Betsumiya, DATABASE: Triply even codes of length 48,
http: / \mathrm{w}\mathrm{w}\mathrm{w}.

st. hirosaki‐u. ac.

\mathrm{j}\mathrm{p}/\sim \mathrm{b}\mathrm{e}\mathrm{t}\mathrm{s}\mathrm{u}\mathrm{m}\mathrm{i}/\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{y}-\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}/[4] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance‐regular graphs, Ergebnisseder Mathematik und ihrer Grenzgebiete (3)[5] C. Naoki,

H. Masaaki and K.

18, Springer‐Verlag, Berlin, 1989.

Masaaki, Permutationgroups andbinary self‐

orthogonal codes, J. Algebra, 309 (2007), no. 2, 610‐621.

[6] I. A. Faradžev, A. A. Ivanov, M. H. Klin and A. J. Woldar, Investigations in\urcorner

algebraic theory of combinatorial objects, Mathematics and its Applications (Soviet

Series), 84, Kluwer Academic Publishers Group, Dordrecht, 1994, \mathrm{x}\mathrm{i}\mathrm{i}+510.
[7] W.H. Haemers, R. Peeters and J.M. van Rijckevorsel, Binary codes of strongly
regular graphs, Des. Codes Cryptogr. 17 (1999), no. 1‐3, 187‐209.

[8] R. Diestel, Graph Theory, 3rd edition, GTM 173, Springer‐Verlag, 2005