非チェーン環上の $\mathcal{C}_{D}$-符号からの最適二進符号

基本情報

• 論文ID: 2510.09057
• タイトル: Optimal binary codes from $\mathcal{C}_{D}$-codes over a non-chain ring
• 著者: Ankit Yadav, Ritumoni Sarma, Anuj Kumar Bhagat（インド工科大学デリー校）
• 分類: cs.IT math.IT
• 発表日: 2025年10月10日（arXiv プレプリント）
• 論文リンク: https://arxiv.org/abs/2510.09057v1

要旨

本論文は、非チェーン環 $\mathcal{R} := \mathbb{F}_2[x,y]/\langle x^2, y^2, xy-yx\rangle$ 上の $\mathcal{C}_D$-符号の部分体符号 $\mathcal{C}_{D}^{(2)}$ を研究している。定義集合 $D$ は単体複体構成に基づいている。著者らは、様々な $D$ に対応する $\mathcal{C}_D^{(2)}$ のハミング重み分布とパラメータを決定し、複数の距離最適な無限符号族を特定し、これらの符号が最小符号および自己直交符号であるための十分条件を提供している。さらに、構成された二重符号から2つの強正則グラフ族を得ている。

研究背景と動機

問題背景

1. 距離最適符号の重要性: 固定されたパラメータ $n$ と $k$ に対して、距離最適符号は最大可能な誤り検出・訂正能力を実現する。これは符号理論の主要な目標の一つである。
2. 既存の構成方法:
   • Gray写像：有限環上の符号から有限体上の符号を構成
   • 単体複体：Chang と Hyun が最初に最適線形符号の構成に導入
3. 先行研究の限界: Shi と Li は文献27で環 $\mathcal{R}$ 上の $\mathcal{C}_D$-符号の Lee 重み分布とその Gray 像を研究したが、部分体符号の研究には至っていない。

研究動機

1. パラメータ改善: 二進部分体符号 $\mathcal{C}_D^{(2)}$ が文献27の二進 Gray 像と比較してより良いパラメータを持つことを証明
2. 理論の完成: 単体複体に基づく符号族に対する最小性と自己直交性の理論的条件を提供
3. 応用の拡張: 二重符号を強正則グラフの構成に応用

核心的貢献

1. 部分体符号のハミング重み分布の決定: 単体複体構成に基づく様々な定義集合 $D$ に対して、$\mathcal{C}_D^{(2)}$ の重み分布を完全に特徴付けた
2. 複数の距離最適符号族の構成: 複数の無限距離最適二進線形符号族を特定し、一部は Griesmer 界に到達
3. 最小性と自己直交性条件の確立: $\mathcal{C}_D^{(2)}$ が最小符号および自己直交符号であるための十分条件を提供
4. パラメータ優位性の証明: 部分体符号が Gray 像符号と比較してより良いパラメータ性能を持つことを証明
5. 強正則グラフの構成: 二重投影符号を利用して2つの強正則グラフ族を構成

方法の詳細

タスク定義

環 $\mathcal{R} = \mathbb{F}_2[x,y]/\langle x^2, y^2, xy-yx\rangle$ 上の線形符号 $\mathcal{C}_D$ を研究する。ここで：

• 定義集合 $D$ は単体複体構成に基づいている
• 目標は、その二進部分体符号 $\mathcal{C}_D^{(2)}$ の性質を分析すること

理論的枠組み

1. 環構造と基

環 $\mathcal{R}$ の各要素は $a + bu + cv + duv$ と表現できる。ここで $a,b,c,d \in \mathbb{F}_2$、$u = x + \langle x^2, y^2\rangle$、$v = y + \langle x^2, y^2\rangle$ である。

$\mathbb{F}_2$-基として $\mathcal{B} = \{b_1 = 1+u+v, b_2 = u+v, b_3 = u, b_4 = uv\}$ を選択する。

2. 部分体符号の構成

$\mathbb{F}_2$-値トレース写像 $\tau: \mathcal{R} \to \mathbb{F}_2$ を利用する： $\tau(a + bu + cv + duv) = a + b + c + d$

定理 3.3: $D = b_1D_1 + b_2D_2 + b_3D_3 + b_4D_4$ ならば、$\mathcal{C}_D^{(2)}$ は行列により生成される： $G^{(2)} = \begin{pmatrix} G_1 + G_4 \\ G_3 \\ G_2 \\ G_1 \end{pmatrix}$

3. 重み計算公式

$(x_1,x_2,x_3,x_4) \in (\mathbb{F}_2^m)^4$ に対して： $\text{wt}(c_D^{(2)}(x_1,x_2,x_3,x_4)) = \frac{|D|}{2} - \frac{1}{2}\sum_{d_1 \in D_1} (-1)^{(x_1+x_4)d_1} \sum_{d_2 \in D_2} (-1)^{x_3d_2} \sum_{d_3 \in D_3} (-1)^{x_2d_3} \sum_{d_4 \in D_4} (-1)^{x_1d_4}$

核心的技術革新

1. ブール関数技法

ブール関数 $\psi(\cdot | Y): \mathbb{F}_2^m \to \mathbb{F}_2$ を定義する： $\psi(x_1 | Y) = \prod_{i \in Y}(1-\alpha_i) = \begin{cases} 1, & \text{if } \text{Supp}(x_1) \cap Y = \emptyset \\ 0, & \text{if } \text{Supp}(x_1) \cap Y \neq \emptyset \end{cases}$

2. 単体複体の応用

単体複体 $\Delta_X$ とその補集合 $\Delta_X^c$ の性質を利用する： $\sum_{t \in \Delta_Y} (-1)^{x_1 t} = 2^{|Y|}\psi(x_1 | Y)$$\sum_{t \in \Delta_Y^c} (-1)^{x_1 t} = 2^m\delta_{0,x_1} - 2^{|Y|}\psi(x_1 | Y)$

実験設定

理論的検証

本論文は主に理論的研究であり、数学的証明により結果を検証している。著者らは MAGMA コンピュータ代数システムを使用して具体例を検証した。

検証例

例 4.8: $m=4$, $X=Y=Z=\emptyset$, $W=\{1,2,3\}$

• パラメータ $[120, 7, 60]$ の二重最適二進線形符号を得た
• 重み列挙式：$x^{120} + 15x^{56}y^{64} + 112x^{60}y^{60}$
• この符号は最小かつ自己直交であり、量子誤り訂正符号 $[[120, 106, 3]]$ を構成できる

実験結果

主要な理論的結果

定理 4.2 は6種類の異なる定義集合に対応する符号パラメータを与える：

1. 一重符号: $D = b_1\Delta_X + b_2\Delta_Y + b_3\Delta_Z + b_4\Delta_W$
   • パラメータ: $[2^{|X|+|Y|+|Z|+|W|}, |X|+|Y|+|Z|+|W|, 2^{|X|+|Y|+|Z|+|W|-1}]$
   • 距離最適条件: $|X|+|Y|+|Z|+|W| \geq 2$
2. 二重符号: $D = b_1\Delta_X^c + b_2\Delta_Y + b_3\Delta_Z + b_4\Delta_W$（$|X| < m$）
   • パラメータ: $[(2^m-2^{|X|})2^{|Y|+|Z|+|W|}, m+|Y|+|Z|+|W|, (2^m-2^{|X|})2^{|Y|+|Z|+|W|-1}]$
   • Griesmer 界に到達し、距離最適
3. 四重符号: $D = b_1\Delta_X^c + b_2\Delta_Y^c + b_3\Delta_Z + b_4\Delta_W$
   • パラメータ: $[(2^m-2^{|X|})(2^m-2^{|Y|})2^{|Z|+|W|}, 2m+|Z|+|W|, (2^m-2^{|X|}-2^{|Y|})2^{m+|Z|+|W|-1}]$
   • 距離最適条件: $2^{|X|+|Y|+|Z|+|W|} \leq m+|Z|+|W|+\min\{|X|,|Y|\}$

最小性と自己直交性の条件

定理 4.7 は十分条件を提供する：

• 自己直交性: 各符号語の重みが4の倍数である場合（定理2.2を利用）
• 最小性: $\frac{\text{wt}_{\min}}{\text{wt}_{\max}} > \frac{1}{2}$ である場合（補題2.3を利用）

強正則グラフの構成

定理 4.12 と 4.13 は2つの強正則グラフ族を構成する：

• 第1族パラメータ: $(2^{m+|Y|+|Z|+|W|}, (2^m-2^{|X|})2^{|Y|+|Z|+|W|}, (2^m-2^{|X|+1})2^{|Y|+|Z|+|W|}, (2^m-2^{|X|})2^{|Y|+|Z|+|W|})$
• 第2族パラメータ: $(2^{m+|Y|+|Z|+|W|}, 2^{|X|+|Y|+|Z|+|W|}-1, 2^{|X|+|Y|+|Z|+|W|}-2, 0)$

関連研究

歴史的発展

1. Gray写像法: Hammons らが最初に Gray 写像を適用して最適非線形符号を構成
2. 単体複体法: Chang と Hyun が単体複体を導入して最適線形符号を構成
3. 環上の符号理論: 様々な有限環上の符号構成に関する研究

本論文の貢献の位置付け

• Shi と Li の研究を拡張し、Gray 像から部分体符号へ転換
• より体系的な理論的枠組みを提供
• パラメータ優位性と最適性を証明

結論と考察

主要な結論

1. 複数の距離最適二進線形符号族の構成に成功
2. 最小性と自己直交性の理論的判定基準を確立
3. 部分体符号が Gray 像符号と比較してパラメータ優位性を持つことを証明
4. 符号理論からグラフ理論への応用を実現

限界

1. 単一の極大要素を持つ単体複体のみを考慮
2. 2つの極大要素を持つ複体への拡張は計算が過度に複雑
3. 一部の距離最適性条件は比較的厳格

今後の方向性

1. 異なるアルファベット上の $\mathcal{C}_D$-符号の部分体符号を研究
2. 2つの極大要素を持つ単体複体を探索
3. より一般的な距離最適性条件を探索

深い評価

利点

1. 理論的貢献が顕著: 部分体符号の重み分布を体系的に分析し、理論的空白を埋めた
2. 方法の革新性が強い: 単体複体、ブール関数、トレース写像を巧妙に組み合わせた
3. 結果の完全性が良好: 完全な重み分布表とパラメータ公式を提供
4. 応用価値が高い: 構成された符号は量子誤り訂正符号と強正則グラフに利用可能

不足点

1. 計算複雑性が高い: 複雑な単体複体に対して計算が非常に煩雑
2. 実用性の検証が不十分: 大規模数値実験と実際の応用テストが不足
3. 推般性が限定的: 方法は特定の環構造に主に適用可能

影響力

1. 学術的価値: 代数符号理論に新しい研究方向を提供
2. 実用的価値: 構成された最適符号は通信システムに潜在的応用がある
3. 再現性: 理論結果は完全だが、理解には高度な数学的背景が必要

適用場面

1. 高効率誤り訂正が必要な通信システム
2. 量子情報処理における量子誤り訂正符号
3. 組合せ数学における強正則グラフの構成
4. 暗号学における秘密分散方式

参考文献

論文は35篇の関連文献を引用している。主なものは以下の通り：

• 27 Shi, M. と Li, X. の先行研究（本論文が直接拡張）
• 9 Chang, S. と Hyun, J.Y. の単体複体に関する開拓的研究
• 13 Hammons ら Gray 写像に関する古典的研究
• 12 Griesmer の符号長界に関する基礎理論