Angle Between Two Vectors over Finite Fields and an Application to Projective Unique Decoding

技術的サマリー：有限体上の二つのベクトル間の角度と、射影的一意復号への応用

問題提起
ユークリッド空間（$\mathbb{R}^n$）において、距離と角度の幾何学的概念は基礎的であり、角度計量は内積からエレガントに導出されます。しかし、有限体（$\mathbb{F}_q^n$）上では、標準的な内積は堅牢な幾何学的枠組みを提供することに失敗します。具体的には、非ゼロベクトルが自己直交（$u \cdot u = 0$）となり得る点や、直交性が幾何学的な垂直性を忠実に捉えない点です。ハミング距離（$d_H$）は符号理論にとって信頼性の高い計量として機能しますが、有限体上のベクトルに対して、真の計量として機能する「角度」や「平行性」の確立された満足すべき概念は存在しませんでした。本論文は、スカラー倍に対して不変であり、射影空間 $\mathbb{P}(\mathbb{F}_q^n)$ に誘導される $\mathbb{F}_q^n$ 上の角度計量を定義する際のギャップを埋めることを扱います。

手法
著者は、非ゼロベクトル $u, v \in \mathbb{F}_q^n$ に対して定義されるハミング角度 $\text{angle}_H(u, v)$ を導入します：
$$\text{angle}_H(u, v) := \min_{c \in \mathbb{F}_q^\star} d_H(u, cv)$$
ここで、$d_H$ は標準的なハミング距離であり、$\mathbb{F}_q^\star$ は体の乗法群です。この定義は、ベクトル $u$ と $v$ によって張られる穴あき線（punctured line）との間の最小ハミング距離を実質的に測定します。

手法は、以下の 3 つの主要な分析ステップを経て進められます：

1. 計量性の検証：論文は、射影空間上で見た場合、$\text{angle}_H$ が計量の 3 つの公理（スカラー倍までの同一視、対称性、三角不等式）を満たすことを厳密に証明します。
2. アルゴリズム的分析：ベクトルの座標をゼロ/非ゼロのパターンに基づいて分割し、特定のスカラー比に対する一致回数を最大化することで、$\text{angle}_H$ を線形時間（$O(n)$）で計算するアルゴリズムが提案されます。
3. 符号理論への応用：この概念を線形符号に適用し、一意復号定理の角度版を導出します。$\text{angle}_H(u, C)$ と符号 $C$ までの標準的なハミング距離 $d_H(u, C)$ の関係を慎重に分析し、特にゼロベクトルが最接近点となる場合を区別します。

主要な貢献と結果

1. 定義と計量性質（定理 3.2）：
   主要な貢献は、$\text{angle}_H$ がスカラー倍まで計量公理を満たすことの証明です。具体的には：

   • $\text{angle}_H(u, v) = 0$ であることと、$u$ と $v$ が同じ射影点を張る（$u = cv$）ことは同値です。
   • $\text{angle}_H(u, v) = \text{angle}_H(v, u)$ が成り立ちます。
   • 三角不等式が成立します：$\text{angle}_H(u, w) \leq \text{angle}_H(u, v) + \text{angle}_H(v, w)$。
     したがって、$\text{angle}_H$ は射影空間 $\mathbb{P}(\mathbb{F}_q^n)$ 上で定義された整数值計量として誘導されます。

2. 計算効率（命題 4.3）：
   定義が $q-1$ 個のスカラーにわたる最小化を含んでいるにもかかわらず、論文は $\text{angle}_H(u, v)$ が $O(n)$ 時間で計算可能であることを示しています。これは、特定の比 $u_i/v_i$ に対する座標の一致回数を数え、最大一致回数を決定することによって達成されます。

3. 幾何学的相違点（第 4.4 節）：
   論文は、ハミング角度とユークリッド角度の質的な相違点を強調しています：

   • 内積の失敗：$\mathbb{R}^n$ と異なり、$u \cdot v = 0$ はハミング的な意味での特定の「直角」を意味しません。内積の意味で直交するベクトルであっても、ハミング角度が小さくなる可能性があります。
   • 統計的距離のアナロジー：最大ハミング角度（$n$）は、$u$ と $v$ のサポートが互いに素であるときに正確に発生します（統計的距離における互いに素なサポートに類似）。これはユークリッド幾何学には存在しない性質です。
   • 場合 $q=2$：2 元体では、非ゼロスカラーが 1 のみであるため、ハミング角度はハミング距離と完全に一致します。

4. 角度による一意復号（定理 5.4）：
   論文は、古典的な一意復号定理の角度版を証明します。最小距離 $d$ を持つ線形符号 $C$ について、受信ベクトル $u$ が $\text{angle}_H(u, C) < d/2$ を満たす場合、$u$ に最も近い一意の符号語方向 $[c^\star] \in \mathbb{P}(C)$ が存在します。証明は、$\text{angle}_H$ の三角不等式に依存しており、2 つの異なる射影符号語がともに $u$ から距離 $d/2$ 以内にあり得ないことを示します。

5. 近接ギャップとの関係（第 5.3 節）：
   著者は、この角度枠組みと「近接ギャップ」問題（符号に対するアフィン直線の研究）との間のつながりを議論します。$\text{angle}_H$ はスカラー倍に対して不変であり、アフィン幾何を直接捉えるものではありませんが、論文は三角不等式が近接ギャップの証明で用いられるものと同様の一意性の障害を提供することを指摘しています。これは、角度枠組みがこれらの問題の「射影的な影」を提供することを示唆しています。

意義と主張
本論文は、幾何学、符号理論、暗号理論の観点から解釈される、有限体上のベクトルに対する角度の概念を定義する最初の試みであると主張しています。その意義は以下の点にあります：

• 内積の図式が失敗する有限体における「平行性」のための幾何学的語彙を提供すること。
• 有限体上の射影空間に厳密な計量構造を確立すること。
• 一意復号定理の明快な射影的洗練を提供し、古典的な $d/2$ 復号半径が特定の符号語だけでなく、射影的な方向に対しても適用可能であることを示すこと。
• 高次元の角度（グラスマン多様体に対応するもの）やアフィン近接ギャップ問題への将来の拡張の基礎を築くこと。

著者は謙虚なトーンを維持しており、角度による一意復号定理は古典的定理の「自然な射影的な兄弟」であり、それを強化するものではないと述べています。また、「射影的近接ギャップ」問題の完全な発展を将来の課題として明示的に残しています。