数理解析研究所講究録 1476 巻 2006 年 88-95

88

On self-dual codes of length 64 withprimitive automorphism groups

室蘭工業大学工学部

千吉良 直紀 (Naoki Chigira)Muroran Institute of Technology
山形大学理学部 原田 昌晃 (Masaaki Harada)
Yamagata University
千葉大学理学部 北詰 正顕 (Masaaki Kitazume)
Chiba University

1Introduction

を調べる上で extended Golay code が重要な役割を果たしていることはよく知られている。 他の単純群 (あるいはそれに近い群) が作用する code として」2 :2 が作用する長さ 100 の code を構成した ([2], この結$M_{24}$

どちらの code にも
果は 2004 年 12 月の数理研の集会で発表している)自己同型群が原始的に作用している。 100 次以下の原始的な作用をもつ群。

が不変にする自己同型群の存在を調べてみるとこれまで知られていたもの以外に 64 次のある原始置換群を自己同型にもつ self-dual code があることが分かった。 ここではその code の構$ffi_{\text{、}^{}\backslash }$特$/(\mathrm{g}$

づけや neighbor などの性質について述べる。 符号についての計算は基本的に MAGMA によるものである。

2Preliminaries
ここでは、 記号の準備、 および我々の議論で重要な役割を果たす定理について述べる。 詳しくは $[3, 5]$ を参照されたい。

89上の置換群とし $\sigma\in G$ に対して Fix(\sigma )とおく。 また $I(G)=\{\sigma|\sigma^{2}=1, \sigma\neq 1\}$ とする。
$G$を集合$\Omega$$=\{\mathrm{i}\in\Omega|\sigma(\mathrm{i})=\mathrm{i}\}$$C(G, \Omega)=C(G, |\Omega|)=\langle \mathrm{F}\mathrm{i}\mathrm{x}(\sigma)|\sigma\in I(G)\rangle^{[perp]}$とおく。
定理 21([3]). $G$ は上の置換群とし $D$ を長さcode とする。 このとき $D\subseteq C(G, \Omega)$ が成り立つ。
$\Omega$$|\Omega|$のself-orthogonal

古くから知られている散在型単純群に関連した self-orthogonal code は$C(G, \Omega)$ と一致していることが多い。 これらについては $[3, 5]$ を参照されたい。

self-dual code に注目するとこの定理より GG 不変な self-dual code が存在するならば $C(G, \Omega)$ の subcode として得られることになる。 さらにが self-orthogonal のときに限りが作用する self-dual code が存在する可能性があることになる。 しかしながらすべての位数 2 の元が$C(G, \Omega)^{[perp]}$$G$

固定点なしに作用する場合には $C(G, \Omega)$ は全空間となってしまい、 全空間の GC 不変な subcode を探さなくてはならない。 そこでここでは、 いく

つかの位数 2 の元が固定点を持つ場合について考察する。

100 次以下の原始置換群でいくつかの位数 2 の元が固定点を持つものが作用する self-dual code で知られているものは以下の通りである。 表のうの code 以外は $C(G, \Omega)$ 自身が self-dual code である。
ち$J_{2}$uller code である。一般に $RM(m, 2m+1)=C(2^{2m+1}$ :$L_{2m+1}(2),$ $2^{2m+1})$ でこれは self-dual code である。
が self上述の通り self-dual code が存在する可能性があるのはorthogonal である場合に限るのであるが、 い つかの位数 2 の元が固定
が self-orthogonal に点を持つような 100 次以下の原始置換群でなるのは表にあげた self-dual code 以外には $C(S_{4}(3), 40),$ $C(J_{2},100)$ と
ここで $RM$ は Reed-M$C(G, \Omega)^{[perp]}$$\langle$$C(G, \Omega)^{[perp]}$90の場合しかない。 $C(S_{4}(3), 40)$ の場合には実際に self-dual code$|\Omega|=64$

は存在せず、 $C(J_{2},100)$ の場合には表にあげた code 以外には存在しない
そこで残るのは 64 次のところである。
$[3]_{\text{。}}$

3$n=64$64 次の原始置換群は全部で 74 個あることが知られている。 そのうちいが self-orthogona 垣こな
つかの位数 2 の元が固定点持ち、 かつるのは 16 個である。 その中で、 まず次の群を考える。
$C(G, \Omega)^{[perp]}$$\langle$$G=2^{6}$: 3 :$($$S_{4})$,: A7,$2^{6}$$2^{6}$:$U_{3}(3)$,$2^{6}$:$A_{8}$,$2^{6}$:$S_{4}(3)$のいずれかであるとする。 いずれの場合にも $C=C(G, 64)$ は [64, 43, 8]
は self-orthogonal [64, 21, 6]であり、code で自己同型群は :code である。 には GG 不変な self-dual code が含まれている可能性があるので、 の subcode を調べればよい。 方法はいろいろ考えられるが、 こ$2^{6}$$C^{[perp]}$$S_{6}(2)$

$C$

$C$

こでは次のことを用いて調べる。

定理 31 (Mallows-Sloane[8]). 長さ

minimum weight を$d$$d$の doubly

even self-dual code のとするとき $d \leq 4[\frac{n}{24}]+4$ が成り

定理 32 (Rains [9]).

weight を$n$$\text{長}$@$\Rightarrow\backslash \text{つ_{。}}$

even self-dual code の minimum$n$の singly

4$[ \frac{n}{24}]+4$$n\not\equiv 22(\mathrm{m}\mathrm{o}\mathrm{d} 24)$

4$[ \frac{n}{24}]+6$$n\equiv 22(\mathrm{m}\mathrm{o}\mathrm{d} 24)$とするとき $d\leq\{$が成$\mathfrak{h}_{-}\backslash [perp] 0_{\mathrm{o}}\infty$$n=64$ のときには $d\leq 12$ となる。 すなわち weight 12 以下の codewordが必ず存在する。 そこで $C$ の weight 12 以下の codewords を -orbit に分解しそれらから生成される code を構成し、 さらにそれをもとにしてself-dual code が存在するかどうかを調べればよい。
$G$定理 33([4]).

$2^{6}$:$A_{8^{A}}$

不変な self-dual code は(i) 2 つの同値な extremal singly even [64, 32, 12] code,(ii) 4 つ (うち 2 つずつは同値) の doubly even self-dual [64, 32, 8] code,に限る。 またこれらの code の自己同型群は$2^{6}$:$A_{8}$

同様の方法で探してみると: 3 :: $U_{3}(3),$64 の self-dual code は存在しないことも分かる。
$2^{6}$$($$S_{4}),$$2^{6}$である。
$2^{6}$:$S_{4}(3)$S 不変な長さ

\S 1

注意 34.
は$2^{6}$$2^{6}$:$A_{7}$$\subset 2^{6}$:$A_{8}$: A77 不変であるが、なので定理 33 で得られた 6 個の self-dual code$2^{6}$: A77 不変な長さ 64 の self-dual code は他には存在しない。

16 個のうち残りの 11 個も同じ $C(G, 64)$ をもつ次の 4 つのクラスに分けることが出来る。
$C(G, 64)$

$C(G, 64)^{[perp]}$[64, 45, 4][64, 48, 6][64, 49, 6][64, 51, 4][64, 19, 16][64, 16, 16]
$|||$

$|$

これらのいずれの場合にもが分かる$[64[64’, 1315,’ 16]16]$

$G$

$\#$

of such1
361$G$-不変な self-dual code は存在しないこと$1\text{。}$以上により、 いくつかの位数 2 の元が固定点を持つ場合、 原始置換群が自己同型群として作用すが作用する self-dual code は 64 次では :$2^{6}$$A_{8}$るもの 6 個しかないという結果が得られた。

定理 33 で得られた code のうち非同値なもので minimum weight が 12とする。 weightのものを, minimum weight が 8 のものを
$D_{2},$$D_{1}$$D_{3}$$\mathrm{e}\mathrm{n}\iota 1-$

nlerator $W_{D_{i}}(i=1,2,3)$ は$W_{D_{1}}=1+2456y^{12}+11264y^{14}+223020y^{16}+\cdots$$W_{D_{2}}=1+120y^{6}+5376y^{12}+455196y^{16}+\cdots$$W_{D_{3}}=1+64y^{8}+4256y^{12}+455084y^{16}+\cdots$となる。 $n=64$ の場合の extremal (すなわち minimum weight 12)のcode の weight enumerator は一般に次のような形で知られている。

.

定理 35(Conway-Sloane[6]) $n=64$ の extremal singly even self-dual code の weight enumerator は$W_{64,1}=1+(1312+16\beta)y^{12}+(22016-64\beta)y^{14}+\cdots$$(14\leq\beta\leq 104)$$W_{64,2}.=1+(1312+16\beta)y^{12}+(23040-64\beta)y^{14}+\cdots$$(0\leq\beta\leq 277)$,のいずれかである。
1 最後$\sigma>$$2$

クラスに氏 (東北大学)$\vee\supset$

いては講演後に存在しないことを示すことが出来た。 宗政昭弘には有益な助言をいただいた。

92

Conway-Sloane[6] では 「各$\beta$に対して code の存在、 非存在を示せ」 という問題が出されている。 この問題に関して最近の[7] によれば次の については存在が知られている。

$\mathrm{H}_{11}\mathrm{f}\mathrm{f}\mathrm{m}\mathrm{a}\mathrm{n}$による論説$\beta$$\beta$$W_{64,1}$$W_{64,2}$

14, 18, 44
2, 8, 9, 10, 16, 23, 30, 32, 37, 40, 44, 64

我々の WD、の weight enumerator をみると $\beta=184$ の $W_{64,2}$ の weightenumerator であることが分かり、 はこれまで存在が知られていなかった weight enumerator をもつ code であることが分かる。
$D_{1}$

系 36. $\beta=184$ である $W_{64,2}$ の weight enumerator をもつ singly evenself-dual[64, 32, 12] code が存在する。

Characterization of4$D_{1},$$D_{2},$$D_{3}$

ここでは、 得られた長さ 64 の code のグラフからの特徴づけを行う。
$V$を$\mathrm{F}_{q}$上 $2m$ 次元のベクトル空間としタイプ$\epsilon$の 2 次形式 $Q$ を持つ個のベクトルを頂点とし 2 点 $u,$ が $Q(u-v)=0$ でとする。 $V$ のあるときに辺で結ぶことにより出来るグラフを affine polar gaph といい$q^{2m}$$VO_{2m}^{\epsilon}(q)$$v$で表す。

$m=3,$ $q=2,$ $Q$ が十タイプの場合を考える。 Aut $(VO_{6}^{+}(2))\cong 2^{6}$ :$(O_{6}^{+}(2) : 2)$であることが知られている。 ここで、 $O_{6}^{+}(2)\cong A_{8}$ であり、
$O_{6}^{+}(2):2\cong S_{8}$ であることに注意する。
ベク トル 0 を含む VO ま (2) の maximum clique set (完全連結集合で最大のもの) は $V$ の極大全特異部分空間 (maximal totally isotropic subspace)に含まれるベクトルの集合に他ならない。 1 つ且 してそれを $X$ とおく。
$|X|=8$ である。 このとき$\mathrm{x}$$\mathcal{O}=${$X^{\sigma}|\sigma\in 2^{6}$とおくと $|\mathcal{O}|=120$ である ( $X$ のる。

$2^{6}$:$O_{6}^{+}(2)$$2^{6}$:$(O_{6}^{+}(2):では 2 つに分かれる。)$D=\langle \mathcal{O}\rangle$を対称差で F2 上の code とする。

: O ま (2)}2)$-orbit の長さは 240 であ83

定理 41 ([4]). $D$ は doubly even self-dual[64, 32, 8] code でである。
:$2^{6}$$\mathrm{A}\mathrm{u}\mathrm{t}(D)$$\cong$$O_{6}^{+}(2)$$|\mathcal{O}|=120$と同値であることがわかる。
に対して $|X_{1}\cap X_{2}|=0,2,8$ のいずれかとなる。 $|X_{1}\cap X_{2}|=2$であることから $D$ は$X_{1},$ $X_{2}\in \mathcal{O}$$D_{2}$のとき $|X_{1}+X_{2}|=12$ である。
$W=\langle X_{1}+X_{2}|X_{1},X_{2}\in \mathcal{O}, |X_{1}\cap X_{2}|=2\rangle$とおくと $W$ は $[64,3112]\rangle$ code となる。

定理 42.

$W^{[perp]}$は $D$ のほかにと同値な self-dual code と$D_{1}$$D_{3}$と同値なself-dual code を含む。
このように我々の code はグラフ $VO_{6}^{+}(2)$ を用いて構成することが出来る。
注意 4.3. $C(2^{6} : A_{8},64)$ には 6 個の self-dual code があったが、 残りの 3 つは$\mathcal{O}$の代わりにもう一方の

注意 44. 同様にして他の$2^{6}$:$O_{6}^{+}(2)$$V_{2m}^{\epsilon}(2)$graph-orbit をとることにより得られる。

で code を構成してみると$\mathrm{c}\mathrm{o}\mathrm{d}\in$’1$VO_{6}^{-}(2)$[64,$56|$ $4]$

$VO_{8}^{+}(2)$$[256$,$VO_{8}^{-}(2)$$[256\rangle$$\}$$1|$$2^{r}(]$$21$ $1$, 8]$VO_{10}^{+}(2)$$[1024,$$VO_{10}^{-}(2)$[1024, $;03]$$’,01]$$\in$$\xi$となり、 $VO_{6}^{+}(2)$ のときのようにはならない。

Neighbors of [64, 32, 8] codes

5

ここでは$C,$ $C’$$D_{1},$$C$$D_{2},$$D_{3}$のneighbor について考える。 長さ$n$のself-dual codeが neighbor であるとは $\dim(C\cap C’)=n/2-1$ であるときをいう。

$D_{2},$を$D_{3}$は互いに neighbor の関係にある。
code とする。 $M$ を $C$ の weight$\mathrm{s}\mathrm{e}\mathrm{l}\mathrm{f}-\mathrm{d}\mathrm{u}\mathrm{a}\mathrm{l}[n, n/2, d]$$d$のcodewordを行にもつ行列とする。 をすべての成分が 1 の codeword とする。
$\mathrm{j}$$x{}^{t}M=\mathrm{j}$84の解となるであり、$x$が存在するとき、$\langle C_{0}, x\rangle$$C_{0}=\langle x\rangle^{[perp]}\cap C$とおくと $\dim(C_{0})=n/2-1$と $\langle C_{0}, x+y\rangle(y\in C\backslash C_{0})$ はどちらも $C$ の neighbor でか

codeword を含まないものになっている。 rank $M=t$個ある。
ならばそのような code は 2の場合を考えたい。 これらの neighbor に extremal$C=D_{2}$ , またはなものがあるならば上述の方法ですべて得られることに注意する。
以外にはない。
$C=D_{2}$ の場合 rank $M=32$ となるので個の code が得られるが実$C=D_{3}$ の場合 rank $M=28$ なので 2) と 16 個の doubly even (う際 16 個の extremal singly even (うち 1 つは) が得られる。 15 個ずつは互いに同値となるので、 extremal
ち 1 つはとする。
doubly even の 1 つをsingly even の 1 つをとなる。 weight enumerator はつ $C$ のweight$d$の$\mathrm{x}2^{n/2-t}$$D_{3}$$D_{1},$$D_{3}$$\mathrm{x}2^{4}=32$$D_{1}$$D_{2}$$E_{2}$$E_{1},$$2^{3}.2^{3}.2^{3}.L_{3}(2),$$\mathrm{A}\mathrm{u}\mathrm{t}(E_{1})\cong$$\mathrm{A}\mathrm{u}\mathrm{t}(E_{2})\cong 2^{3}.2^{3}.2.2^{3}.L_{3}(2)$$W_{E_{1}}=1+2464y^{12}+18432y^{14}+226604y^{16}+\cdots$$W_{E_{2}}=1+8y^{8}+3136y^{12}+454972y^{16}+\cdots$

は $\beta=72$ の $W_{64,2}$ の weight enumerator になっている。となる。の neighbor を調べると $\beta=24$ の code も存在
同様の方法でさらに$E_{1}$$E_{2}$することが分かる。
定理 51. $\beta=24_{?}72$ である垣 64,2 の weight enumerator をもつ singly even
[64, 32, 12] self-dual code が存在する。

参考文献[1] W. Bosma and J. Cannon, Handbook of Magma Functions, Department of Mathematics, University of Sydney, Available online.
.maths .usyd.
at http:$//\mathrm{m}\mathrm{a}\mathrm{g}\mathrm{m}\mathrm{a}$$\mathrm{e}\mathrm{d}\mathrm{u}.\mathrm{a}\mathrm{u}/\mathrm{m}\mathrm{a}\mathrm{g}\mathrm{m}\mathrm{a}/$[2] N. Chigira, M. Harada and M. Kitazume, Some self-dual codes invariant under the Hall-Janko group, submitted.
[3] N. Chigira, M. Harada and M. Kitazume, Finite permutation groups
and self-orthogonal codes, submitted.
[4] N. Chigira, M. Harada and M. Kitazume, On self-dual codes of length
64 with primitive automorphism groups , in preparation,

95[5] 千吉良直紀, 原田昌晃, 北詰正顕, 有限置換群と自己直交符号, 第 22回代数的組合せ論シンポジウム報告集 (掲載予定)[6]$\mathrm{J}.\mathrm{H}$. Conway and N.J.A. Sloane, A new upper bound on the minimal

distance of self-dual codes, IEEE Trans. Inform. Theory 36 (1990),1319-1333.
[7]. Huffman, On the classification and enumeration of self-dual
codes, Finite Fields Appl. 11 (2005), 451-490,$\mathrm{W}.\mathrm{C}$[8] C. L. Mallows and N. J. A. Sloane, An upper bound for self-dual
codes, Inform. Contr. 22 (1973), 188-200.
[9] E. M. Rains, Shadow bounds for self-dual codes, IEEE Trans. Inform.
Theory 44 (1998), 134-139.