Locally Repairable Codes with Availability via Elliptic Function Fields

技術的概要：楕円関数体による可用性を備えた局所修復可能符号

問題定義
可用性を備えた局所修復可能符号（LRC）は、現代の分散クラウドストレージシステムにおいて不可欠であり、そのサブセット内の一部ノードが利用できない場合でも、少数のノード（局所性）から失われたデータを復元可能にします（可用性）。単一の復元セット（$t=1$）を持つ最適 LRC は広範に研究されてきましたが、最適パラメータと柔軟な局所性を達成する複数の復元セット（$t \ge 2$）を持つ LRC の構成は依然として課題です。従来の構成法は、最大超特異楕円曲線または有理関数体に依存することが多く、適用可能な有限体と局所性パラメータの範囲を制限していました。具体的には、既存の手法は特性 $p \equiv 1 \pmod{3}$ または $p \equiv 1 \pmod{4}$ の有限体上の最適 LRC を提供することに苦慮しており、楕円関数体を用いた 2 つの復元セットを持つ LRC の構成は、厳格なパラメータをもたらすか、完全に分裂する点の欠如を補うために修正された代数幾何符号の技法を必要とする結果となっていました。

手法
著者は、楕円関数体およびその自己同型群から導出される代数幾何符号を採用します。手法は 2 つの主要な経路に分かれます：

1. 最適古典的 LRC（$t=1$）： 本論文は、ハッセ・ヴェイルの上限に近づくが必ずしも最大ではない、多くの有理点を持つ通常楕円曲線の使用を導入します。著者は、$\mathbb{F}_{p^2}$ 上で定義された 2 つの特定の通常楕円曲線の族を分析します：

   • $p = 3u^2 + 3u + 1$ である $y^2 = x^3 + b$ で定義される曲線。
   • $p = v^2 + 1$ かつ $p \equiv 1 \pmod 4$ である $y^2 = x^3 + ax$ で定義される曲線。
     これらの曲線の自己同型群（特に平移群と安定化部分群）を利用することで、著者は完全自己同型群の部分群を構成し、固定部分体を定義します。彼らのアプローチの新たな側面は、符号構成に用いられる関数 $e_i$ を決定するための代替手法です。完全に分裂する点の集合と修正された代数幾何技法に依存した先行研究とは異なり、この手法は部分群の性質を十分に活用し、関数が局所復元に必要な線形独立性と可逆性の条件を満たすことを保証します。

2. 2 つの復元セットを備えた LRC（$t=2$）： 著者は、楕円関数体の自己同型群を用いて 2 つの復元セットを持つ LRC を構成するための一般的な枠組みを提案します。従来の枠組み（関数空間の交わりが小さすぎるという制限）を克服するため、関数 $e_i$ に対する新たな構成を考案します。これにより、2 つの異なる復元セットに対応する関数空間が共通のリーマン・ロッホ空間内に存在し、十分に大きな交わりが保証されます。この枠組みは、部分群 $G = T_H A_1 A_2$（ここで $T_H$ は平移部分群、$A_1, A_2$ は安定化部分群）を用いて符号パラメータを定義します。この構成は、最大楕円関数体と、論文の第 1 部で紹介された特定の通常曲線の両方に適用されます。

主要な貢献と結果

• 最適古典的 LRC の新たな族： 本論文は、長さ $O(q + 2\sqrt{q})$ と柔軟な局所性を持つ $q$ 進最適 LRC のいくつかの新たな族を構成します。

  • 定理 1 および 2： これらの定理は、局所性 $r = h|A| - 1$ または $r = 2h - 1$ を持つ最適 $p^2$ 進 LRC の存在を確立します。重要なのは、これらの構成が特性 $p$ が $p \equiv 1 \pmod{12}$（具体的には $p = 3u^2 + 3u + 1$ または $p = v^2 + 1$）を満たす有限体に対して有効であり、楕円曲線の自己同型群を介して以前は利用可能ではなかったケースであることです。
  • 比較： 表 I に詳述されているように、これらの結果は既存の研究（例：Li ら、Ma および Xing）を補完し、特性の範囲を拡大し、同じ有限体上で異なる局所性パラメータを提供します。

• 可用性 $t=2$ のための一般枠組み：

  • 命題 3： 楕円関数体を用いて 2 つの復元セットを持つ LRC を構成するための一般枠組みを提供します。部分群 $A_1$ と $A_2$ のサイズに基づき、次元 $k$ と最小距離 $d$ の下限を確立します。
  • 定理 3 および 4： 命題 1 の最大楕円関数体および特定の通常曲線にそれぞれこの枠組みを適用します。これらの定理は、長さ $O(q + 2\sqrt{q})$（$q^2$ 進の場合は $O(q^2 + 2q)$）を持つ 2 つの復元セットを備えた LRC の族を導き出します。
  • 定理 7： 特性 2 の有限体（具体的には $q = 4^{2a+1}$）上での特殊な構成を提示し、局所性ペア $(5, 6)$ および $(8, 3)$ を持つ LRC を導き出します。

• 性能指標：

  • 構成された符号は、古典的 LRC については長さ $O(q + 2\sqrt{q})$ を、2 つの復元セットを持つ LRC については長さ $O(q^2 + 2q)$ を達成します。
  • 2 つの復元セットを持つ $q^2$ 進 LRC について、シングルトン欠損は $O\left(\frac{2\ell}{q^2 + 2q - 8\ell}\right)$ であることが示され、$q$ が増加するにつれて 0 に収束するため、漸近的な最適性を示しています。
  • 数値例（例：$\mathbb{F}_{5^6}$ 上）は、構成された符号が（有理関数体に基づくものなどの）従来の手法では達成不可能なパラメータを達成できることを示しています。

意義と主張
本論文は、最適局所修復可能符号の構成に利用可能な曲線の選択肢を広げると主張しています。最大超特異曲線から、多くの有理点を持つ通常曲線へと焦点を移すことで、特性 $p \equiv 1 \pmod 3$ および $p \equiv 1 \pmod 4$ の有限体に関する文献のギャップを埋めています。さらに、2 つの復元セットを持つ LRC に対する提案された枠組みは、修正された代数幾何符号の技法を必要とせず、より多様な局所性パラメータを可能にするため、従来の手法よりも柔軟なアプローチを提供します。著者は、次元の上限が保守的であること（実際の次元が理論的下限を超える数値例によって示されている）に留意しつつも、この枠組みが以前は達成不可能であった 2 つの復元セットを持つ符号の新たな族を生成することに成功したと述べています。また、この研究は、2 つを超える復元セットを持つ LRC の構成を将来の研究方向として強調しています。