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{F}_q^n$ 上关于标量乘法不变、并能诱导出射影空间 $\mathbb{P}(\mathbb{F}_q^n)$ 上的角度度量。

方法论
作者引入了汉明角度，记为 $\text{angle}_H(u, v)$，定义为非零向量 $u, v \in \mathbb{F}_q^n$ 的：
$$\text{angle}_H(u, v) := \min_{c \in \mathbb{F}_q^\star} d_H(u, cv)$$
其中 $d_H$ 是标准汉明距离，$\mathbb{F}_q^\star$ 是域的乘法群。该定义有效地测量了向量 $u$ 与由 $v$ 张成的去心直线之间的最小汉明距离。

方法论通过三个主要分析步骤展开：

1. 度量验证：本文严格证明了当在射影空间上观察时，$\text{angle}_H$ 满足度量的三个公理（不可分辨性同一性至标量倍数、对称性以及三角不等式）。
2. 算法分析：提出了一种线性时间复杂度（$O(n)$）的算法来计算 $\text{angle}_H$，该算法基于零/非零模式对向量坐标进行划分，并针对特定标量比率最大化一致计数。
3. 编码理论应用：将该概念应用于线性码，推导出唯一解码定理的角度版本。仔细分析了 $\text{angle}_H(u, 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$ 的情况：对于二元域，汉明角度与汉明距离完全一致，因为唯一的非零标量是 1。

4. 角度唯一解码（定理 5.4）：
   本文证明了经典唯一解码定理的角度类比。对于最小距离为 $d$ 的线性码 $C$，如果接收向量 $u$ 满足 $\text{angle}_H(u, C) < d/2$，则存在唯一的码字方向 $[c^\star] \in \mathbb{P}(C)$ 最接近 $u$。证明依赖于 $\text{angle}_H$ 的三角不等式，表明两个不同的射影码字不可能同时位于 $u$ 的距离 $d/2$ 范围内。

5. 与邻近间隙的关系（第 5.3 节）：
   作者讨论了该角度框架与“邻近间隙”问题（研究相对于码的仿射直线）之间的联系。虽然 $\text{angle}_H$ 对标量乘法不变且不直接捕捉仿射几何，但本文指出三角不等式提供了一种类似于邻近间隙证明中使用的唯一性障碍。这表明角度框架为这些问题提供了一个“射影阴影”。

意义与主张
本文声称是首次尝试从几何、编码理论和密码学的角度定义有限域上向量的角度概念。其意义在于：

• 为内积图景失效的有限域中的“平行性”提供了几何词汇。
• 在有限域上的射影空间建立了严格的度量结构。
• 提供了一个简洁的、射影化的唯一解码定理改进版，证明了经典的 $d/2$ 解码半径不仅适用于特定码字，也适用于射影方向。
• 为未来扩展到更高维角度（格拉斯曼流形对应物）和仿射邻近间隙问题奠定了基础。

作者保持了谦逊的语气，指出角度唯一解码定理是经典定理的一个“自然的射影兄弟”，而非对其的加强，并明确将完整“射影邻近间隙”问题的开发留作未来工作的方向。