数理解析研究所講究録 1228 巻 2001 年 51-6051

小関多項式と符号の被覆半径の計算
田辺顕一朗 (Kenichiro Tanabe)
筑波大学数学系

Institute of Mathematics, University of Tsukuba
e-mail:tanabe@math.tsukuba.ac.jp

1

イントロダクション
この講演では原田昌晃、小関道夫との共同研究 [2] で行った、符号の被覆半径およびコセット重み枚挙多項式の小関多項式を用いた計算について話します。方針は小関 [5] と同じですが、ある有限群の不変式環に関する結果を用いてより大きな長さの符号に対してそれらの値が計算出来るようになったことが特徴です。 コセット重み枚挙多項式に関しては今まで知られていた方法 (補題 1 参照) よりは符号によっては、 より少ない労力で計算が出来るようになります。

1997 年、小関 [4] によって符号の小関多項式が導入されました。論文 [4]の中では小関多項式は Jacobi 多項式と呼ばれていますが、全く別の多項式に対して既に同じ名前が付けられていることもありここでは小関多項式と呼ぶことにします。
最初に符号に関して紹介しておきます。三元体 F3 上の 次元ベクトル空間の部分空間 $C$ を三元体上の長さ の線形符号と呼びます。他の有限体に対しても符号は同様に定義できますが、 ここでは三元体上の線形符号しか扱いません。以 T 簡単に三元体上の線形符号 $C$ のことを符号と呼びます。
$n$

$n$

$\mathrm{F}_{3}^{n}$$a=(a_{k}),$ $b=(b_{k})\in \mathrm{F}_{3}^{n}$$|\{k|a_{k}\neq 0\}|$とと $i,j\in\{0,1,2\}$ に対して、 \equiv n-己号$\mathrm{w}\mathrm{t}_{ij}(a, b):=|$$\mathrm{w}\mathrm{t}(a):=${ $k|a_{k}=i$ and $b_{k}=j$ } を準備します。 ま$|$た内積 $(a, b):= \sum_{k=1}^{n}a_{k}b_{k}$ を定義します。符号 $C$ に対してその直交空間$C^{[perp]}:=${$a\in \mathrm{F}_{3}^{n}|(a,$$c)=0$ , for all $c\in C$ } を定義します。 C=C，鯔

たす符号 $C$ は self-dual であると呼ばれます。商ベクトル空間の元$U$ を $C$ のコセットと呼びます。 また垣をコセット重み枚挙多項式と呼びます。 $a\in U$ がを満たす時、$U$はのコセットリーダーであると呼ばれます。 コセットリーダーの重みをそのコセットの重みと呼ぶことにします。
$\mathrm{F}_{3}^{n}/C$$U(x)= \sum_{u\in U}x^{\mathrm{w}\mathrm{t}(u)}$$\mathrm{w}\mathrm{t}(a)\leq \mathrm{w}\mathrm{t}(b)(^{\forall}b\in U)$

$a$

52
符号 $C$ に対して、$\mathrm{F}_{3}^{n}=\bigcup_{\mathrm{C}}\epsilon c\{a\in \mathrm{F}_{3}^{n}|\mathrm{w}\mathrm{t}(a-c)\leq r\}$.

を満たす非負の整数 の最小値を符号の被覆半径と呼び、 ここでは $\rho(C)$で表すことにします。与えられた符号に対してその被覆半径を決定するのは符号理論における重要な問題の一つです。簡単に$r$$\rho(C)=\max_{a\in \mathrm{F}_{3}^{n}}\min_{c\in C}\mathrm{w}\mathrm{t}(a+c)$#こ対して $W_{a+C}(x)$ が分かれば、 $\rho(C)$が示せます。 これから全てのが決定できまることに注意します。符号の被覆半径の計算には次の結果が$a\in \mathrm{F}_{3}^{n}$有用です。
補題 1(Delsarte[l])(1) $\rho(C)\leq|\{\mathrm{w}\mathrm{t}(a)|0\neq a\in C^{[perp]}\}|=:D(C)$ が成り立つ $D(C)$ は
Delsarte bound と呼ばれる o(2) $W_{a+C}(y)$ の $D(C)-1$ 次までの係数が分かれば $W_{a+C}.(y)$ は計算出$\text{。}$来る。
が分かります。 し(1) から各 $a\in$ 架に対してたがって全てのとなる全てのではなく、に対して W。+c(y) を計算すれば良いことが分かります。 また[こ注意すると (2)ならばから $P_{a}(C)$ $:=\{c\in C|\mathrm{w}\mathrm{t}(c)<\mathrm{w}\mathrm{t}(a)+D(C)\}$ に対してを計算すれば $W_{a+}c(x)$ を決定出来ることが分かります。
をと符号 $C$ に対して $x,$ $y,$ $u,$小関多項式の紹介をします。
変数とする多項式$\min_{\beta\in a+C}\mathrm{w}\mathrm{t}(\beta)\leq D(C)$$\mathrm{w}\mathrm{t}(a)\leq D(C)$$a\in \mathrm{F}_{3}^{n}$$a\in \mathrm{F}_{3}^{n}$$\mathrm{w}\mathrm{t}(c)\geq$$\mathrm{w}\mathrm{t}(a)+D(C)$$\mathrm{w}\mathrm{t}(a+c)\geq \mathrm{w}\mathrm{t}(c)-\mathrm{w}\mathrm{t}(a)\geq D(C)$$\text{、}$$\sum_{\beta\in P_{a}(C)}x^{\mathrm{w}\mathrm{t}(\beta)}$$v,$ $w$$a\in \mathrm{F}_{3}^{n}$$O(C, a;x, y, u, v, w)$$:=$$\sum_{c\in C}x^{\mathrm{w}\mathrm{t}_{00}(a,c)}y^{\mathrm{w}\mathrm{t}_{01}(a,c)+\mathrm{w}\mathrm{t}_{02}(a,c)}$$\mathrm{x}u^{\mathrm{w}\mathrm{t}_{10}(a,c)+\mathrm{w}\mathrm{t}_{20}(a,c)}v^{\mathrm{w}\mathrm{t}_{11}(a,c)+\mathrm{w}\mathrm{t}_{22}(a,c)}w^{\mathrm{w}\mathrm{t}_{12}(a,c)+\mathrm{w}\mathrm{t}_{21}(a.c)}$を$a$に関する $C$ の小関多項式と呼びます。

$x$

$y$

$y$

$u$

$v$

$w$$u$

$w$

$v$

53
小関多項式において変数を以 T のように置き換えると、$O(C, a;1, x, x, x, 1)$$=$$\sum_{c\in C}x^{\mathrm{w}\mathrm{t}_{01}(a,c)+\mathrm{w}\mathrm{t}_{02}(a,c)+\mathrm{w}\mathrm{t}_{10}(a,c)+\mathrm{w}\mathrm{t}_{20}(a,c)+\mathrm{w}\mathrm{t}_{11}(a,c)+\mathrm{w}\mathrm{t}_{22}(a.c)}$$=$$\sum_{c\in C}x^{\mathrm{w}\mathrm{t}(a+c)}=W_{a+C}(x)$となり、 コセット重み枚挙多項式.

$W\text{。}+C$(x) が計算できます。 したがって小関多項式が分かれば、符号の被覆半径が決定できます。
以上小関多項式から符号の被覆半径及びコセット重み枚挙多項式が得られることを見てきたわけですが、一般に与えられた符号に対してその小関多項式を計算するのは困難な問題です。 しかし以 T に見るように符号が self-dual である場合には有限群の不変式論の方から小関多項式に関する情報を得ることが可能になります。 まず次の結果が成り立つことに注意します。

補題 2(小関 [5]) $C$ が self-dual ならば小関多項式は次の行列の作用の Tで不変である。

1$L_{1}$$L_{2}$$:=$$:=$

ここで, $=e^{2\pi\sqrt{-1}/3}$ .

20001-10000 10 1011$\frac{1}{\sqrt{3}}\{\begin{array}{lllll}1 1 0 0 02 -1 0 0 00 0 \mathrm{l} 1 10 0 1 \omega^{2} \omega 0 0 1 \prime.v \omega^{2}\prime\end{array}\},$

diag$\omega^{2}$$\omega$$1$$(1, \omega, 1, \omega, \omega)$

and$’.v$$\omega^{2}$.

,さらにもし $C\ni(1, \ldots, 1)$ ならば$L_{3}:=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(\omega, 1, \omega, 1,1)$でも不変となる。
’L2)、または上の補題から小関多項式は不変式環の元となるわけですが、 これらの不変式環について次の結果が得られてい$\mathbb{C}[x, y, u, v, w]^{\langle L_{1}}$ます。

補題 3(田辺 [6])$\mathbb{C}[x, y, u, v, w]^{\langle L_{1},L_{2}\rangle}$と$\mathbb{C}[x, y, u, v, w]^{\langle L_{1},L_{2},L_{3}\rangle}$を具体的に与えることが出来る。
より正確に (ま、例えば$\mathbb{C}[x, y, u, v, w]^{\langle L_{1},L_{2},L_{3}\rangle}$の場合に (ま次の具体的に与えることが出来ます$\mathbb{C}[x, y, u, v, w]^{\langle L_{1},L_{2},L_{3}\rangle}$$=$$\oplus_{i=1}^{864}\eta_{i}\mathbb{C}[\theta_{1}, \theta_{2}, \theta_{3}, \theta_{4}, \theta_{5}]$.

.

$\mathbb{C}[x, y, u, v, w]^{\langle L_{1}}:^{L_{2},L}$の生$\{\eta_{i}\}$

達を

542.

$:=$$(x^{4}+8xy^{3})^{3}$$\theta_{2}$$:=$$(x^{6}-20x^{3}y^{3}-8y^{6})^{2}$$\theta_{3}$$:=$$(4u^{4}+4u(v+w)^{3})^{3}$$\theta_{4}$$:=$$(8u^{6}-20u^{3}(v+w)^{3}-(v+w)^{6})^{2}$$\theta_{5}$$:=$$(v-w)^{12}$$\theta_{1}$

.

.
.

.

符号の被覆半径の計算$\mathrm{F}_{3}$上の extremal self-dual code は長さ 24 までは分類されています (特に長さ 24 の符号は二つ) 。長さ 28 は 32 個以上あることが知られています。
プレプリント [2] では補題 3 を用いて長さ 24 の二つ、 また Huffman[3] が構成した長さ 28 の extremal self-dual code の小関多項式 (結果としてコセット重み枚挙多項式と被覆半径も) を計算しました。実はそれらの符号の被覆半径は既によく知られていて、そちらに関しては新しい結果ではありません。 コセット重み枚挙多項式に関しては新しい結果です。長さ 32以上は計算量が多すぎて今のところ出来ていません。

ここでは長さ 28 の場合を例に取り、計算方法を紹介します。
$\mathrm{w}\mathrm{t}(a)=i$$a\in \mathrm{F}_{3}^{28}\mathrm{s}.\mathrm{t}$.

に対して小関多項式 $O(a, C;x, y, u, v, w)$ を計算していきます。

補題 1(1) から $\mathrm{w}\mathrm{t}(a)\leq D(C)=7$ まで決めればよいことに注意します。
まず補題 3 から可能な小関多項式を求めておきます。

(1) 次数 28 の斉次不変式$f\in R:=\mathbb{C}[x, y, u, v, w]_{28}^{\langle L_{1},L_{2},L_{3}\rangle}$( の変数$f$$u,$ $v,$ $w$,に関する次数) $=i$ .

を補題 3 で得られている $R$ の生或元を使ってパラメータ付きで表す。

55
それを$f$$=$$\sum_{n_{x},n_{y},n_{u},n_{v},n_{w}}\gamma_{n_{x},n_{y},n_{u},n_{v},n_{w}}x^{n_{x}}y^{n_{y}}u^{n_{u}}v^{n_{v}}w^{n_{w}}$$\gamma_{n_{x},n_{y},n_{u},n_{v},n_{w}}\in \mathbb{C}$.

.と展開しておく。

(2) $d:= \min\{\mathrm{w}\mathrm{t}(c)|0\neq c\in C\}$ とおくと $C$ (ま extremal であるから$d=3\lfloor n/12\rfloor+3$(i)(ii)となる。 この事に注意して、条件$f(1,1,1,1,1)=|C|$ .

.

$n_{y}+n_{v}+n_{w}<3\lfloor n/12\rfloor+3\Rightarrow\gamma_{n_{x},n_{y},n_{u},n_{v},n_{w}}=0$から係数のパレメータの数を減らす。の場合は次のようになります。表に載っていないその他を用いて表せます。の係数もパラメータ例えば$\mathrm{w}\mathrm{t}(a)=6$$s_{2},$$\ldots,$$s_{10}$

次に実際に符号の元を使って小関多項式を決定します。

56(3) 整数 If に対して、目的の符号の部分集合 Cに対して $O(a, c_{\leq K} ; x, y, u, v, w)$ を (計算機等を考える 適当なを用いて) 計算すれば (2) で残ったパラメータの値が決定されるので小関多項式が計算できる。 もちろん の値は出来るだけ小さいほ$\leq K:=\{c\in C|\mathrm{w}\mathrm{t}(c)\underline{<}I\acute{\mathrm{t}}\}$$I\acute{\mathrm{t}}$$\text{。}$$I\acute{\mathrm{t}}$うが計算は楽になる。
例えばタ$s_{2},$の場合には、上の表を見て $K=9$ ととればパラメーが計算できます。今までの方法 (補題 1(2)) だと $P_{a}(C)=$$\mathrm{w}\mathrm{t}(a)=6$$\ldots,$$s_{10}$$\{c\in C|\mathrm{w}\mathrm{t}(c)<\mathrm{w}\mathrm{t}(a)+D(C)\}=c_{\leq 13}=\{c\in C|\mathrm{w}\mathrm{t}(c)\in\{0_{1}9,12\}\}$(80809 個) を用いてコセット重み枚挙多項式を計算しなければなりません
でしたが、上記の方法だと $\{c\in C|\mathrm{w}\mathrm{t}(c)\in\{0,9\}\}$ ( $2185$ 個) を用いれば計算できることが分かります。 このようなことは任意の符号、任意の重みに対して成立するわけではありません (例えば長さ 24 に対してはどちらのの値は変わらない) 。しかし補題 1(2) に対応する結果
方法でも必要な$I\dot{\mathrm{t}}$に関する次数で $D(C)-1$ 次までの係数が分かれば $O(a, C;x, y, u, v, w)$ は計算出来る。

$(*)O(a, C;x, y, u, v, w)$ の $y,$ $u,$

$v$の値は大は成り立つので、少なくとも今までの方法に較べて使用するきくはならないことは分かります。
(こ対し上の計算 (1) $-(3)$ を全ての $i(0\leq i\leq 7)$ とて行います (実際は $i\leq 6$ までで良い) この結果から実際に現れるコセッ
ト重み枚挙多項式と、それをコセット重み枚挙多項式としてもつコセットの数が次のように勘定出来ます。
$I\dot{\mathrm{t}}$$a\in \mathrm{F}_{3}^{28}(\mathrm{w}\mathrm{t}(a)\leq i)$$\text{。}$に関する最低の次数が(4) 計算できた小関多項式を見て、 $y,$より小さくなった場合は は $a+C$ のコセットリーダではないので$v,$ $w$$\mathrm{w}\mathrm{t}(a)$$a$その(5)$a$は数えない。

をコセットリーダとする $O(a, C;1, x, x, x, 1)$ で $a+C$ のコセソ
ト重み枚挙多項式が計算できる。 コセット重み枚挙多項式 $f(x)$ に対$a$$\text{。}$して.
$\frac{|\{a\dagger 1\supset \text{セ}\backslash \backslash y\text{ト}\mathrm{t})-F^{\backslash }|O(a,C,1,x,x,x,1)=f(x)\}|}{(f(x)\text{の}\ovalbox{\tt\small REJECT}\{\mathrm{g}\text{次の}\mathrm{f}\mathrm{f}_{\backslash }\text{数})}.$

カ $f(x)$ をコセット重み枚挙多項式としてもつコセットの数となる。
$\dot{\mathrm{a}}$計算した長さ 28 の符号のコセット重み分布 ($=$

コセット重み枚挙多項式) を載せておきます。表の最後の行の数はそのようなコセット重み分布を持つコセットの数です。

57

58

59

60
パラメータの値
$b$
み36
19656

106552$(t_{1} , t_{2})$$(0, 0)$$(0, 1)$$(2, 2)$$(2, 1)$

$\#$

13104

39312

58968

58968

$(t_{1} , t_{2})$$(4, 0)$$(6, 0)$$(6, 1)$

$\#$

39312

58968

58968

$(t_{1}, t_{2})$$(1, 0)$$(1, 1)$$(1, 3)$$(1, 4)$

$\#$

39312

39312

$(1, 5)$$(1, 6)$294840(1, 1158968

393120294840(1, 7235872

432432

,$3$

$t$

$\#$

4

5

$(t_{1}$$t_{2}$$\#$$(t_{1}, t_{2})$

$\#$

2, 1)

$(2, 2)$

11793658968$(2, 3)$$(2, 4)$

$\#$

19656

117936$\#$

6(2, 0)

19656$(t_{1}, t_{2})$$(t_{1}, t_{2})$

$t$

$\#$
$t$

$\#$
$t$

$\#$
$t$

$\#$

3, 439312
2176904
6117936105896827728$(1, 9)$58968

32751847235872
1178624(2, 758968

42751848176904
142808$(3, 3)$39312
5412776
9236600
1519656

参考文献[1] P. Delsarte, Four fundamental parameters of acode and their combinatorial significance, Inform.
. $23$ (1973), 407-438.
$Con\mathrm{t}\mathrm{r}$[2] M. Harada, M. Ozeki, and K. Tanabe On the Covering Radius ofTernary Extremal Self-Dual Codes, preprint.

[3]$\mathrm{W}.\mathrm{C}$. Huffman, On extremal self-dual ternary codes of lengths 28

to 40, IEEE Trans. Inform. Theory 38 (1992), 1395-1400.

[4] M. Ozeki, On the notion of Jacobi polynomials for codes, Math.
Proc. Cambridge Philos. Soc. Vol. 121 (1997), 15-30.
[5] M. Ozeki, On the covering radius problems for ternary self-dual
codes, Th eoretical $Com$ pu . Sci. , (to appear).
$\mathrm{t}$[6] K. Tanabe, Modified Jacobi polynomials of ternary codes and theinvariant ring of arelated group, preprint.