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

Technical Summary: Angle Between Two Vectors Over Finite Fields and an Application to Projective Unique Decoding

Problem Statement
In Euclidean space ($\mathbb{R}^n$), the geometric concepts of distance and angle are fundamental, with the angular metric derived elegantly from the inner product. However, over finite fields ($\mathbb{F}_q^n$), the standard inner product fails to provide a robust geometric framework; specifically, nonzero vectors can be self-orthogonal ($u \cdot u = 0$), and orthogonality does not faithfully capture geometric perpendicularity. While the Hamming distance ($d_H$) serves as a reliable metric for coding theory, there has been no established, satisfactory notion of "angle" or "parallelism" for vectors over finite fields that functions as a genuine metric. This paper addresses the gap in defining an angular metric on $\mathbb{F}_q^n$ that is invariant under scalar multiplication and descends to the projective space $\mathbb{P}(\mathbb{F}_q^n)$.

Methodology
The author introduces the Hamming angle, denoted $\text{angle}_H(u, v)$, defined for nonzero vectors $u, v \in \mathbb{F}_q^n$ as:
$$\text{angle}_H(u, v) := \min_{c \in \mathbb{F}_q^\star} d_H(u, cv)$$
where $d_H$ is the standard Hamming distance and $\mathbb{F}_q^\star$ is the multiplicative group of the field. This definition effectively measures the minimum Hamming distance between a vector $u$ and the punctured line spanned by $v$.

The methodology proceeds through three main analytical steps:

1. Metric Verification: The paper rigorously proves that $\text{angle}_H$ satisfies the three axioms of a metric (identity of indiscernibles up to scalar, symmetry, and the triangle inequality) when viewed on the projective space.
2. Algorithmic Analysis: A linear-time algorithm ($O(n)$) is proposed to compute $\text{angle}_H$ by partitioning vector coordinates based on zero/nonzero patterns and maximizing the agreement count for specific scalar ratios.
3. Coding Theory Application: The concept is applied to linear codes to derive an angular version of the unique decoding theorem. The relationship between $\text{angle}_H(u, C)$ and the standard Hamming distance to a code $d_H(u, C)$ is carefully analyzed, particularly distinguishing cases where the zero vector is the closest point.

Key Contributions and Results

1. Definition and Metric Properties (Theorem 3.2):
   The primary contribution is the proof that $\text{angle}_H$ satisfies the metric axioms up to scalar multiplication. Specifically:

   • $\text{angle}_H(u, v) = 0$ if and only if $u$ and $v$ span the same projective point ($u = cv$).
   • $\text{angle}_H(u, v) = \text{angle}_H(v, u)$.
   • The triangle inequality holds: $\text{angle}_H(u, w) \leq \text{angle}_H(u, v) + \text{angle}_H(v, w)$.
     Consequently, $\text{angle}_H$ descends to a well-defined integer-valued metric on the projective space $\mathbb{P}(\mathbb{F}_q^n)$.

2. Computational Efficiency (Proposition 4.3):
   Despite the definition involving a minimization over $q-1$ scalars, the paper demonstrates that $\text{angle}_H(u, v)$ can be computed in $O(n)$ time. This is achieved by counting coordinate agreements for specific ratios $u_i/v_i$ and determining the maximum agreement count.

3. Geometric Distinctions (Section 4.4):
   The paper highlights qualitative differences between the Hamming angle and the Euclidean angle:

   • Inner Product Failure: Unlike in $\mathbb{R}^n$, $u \cdot v = 0$ does not imply a specific "right angle" in the Hamming sense. Vectors can be orthogonal in the inner-product sense yet have a small Hamming angle.
   • Statistical Distance Analogy: The maximum Hamming angle ($n$) occurs precisely when the supports of $u$ and $v$ are disjoint (analogous to disjoint supports in statistical distance), a property not present in Euclidean geometry.
   • Case $q=2$: For binary fields, the Hamming angle coincides exactly with the Hamming distance, as the only nonzero scalar is 1.

4. Angular Unique Decoding (Theorem 5.4):
   The paper proves an angular analog of the classical unique decoding theorem. For a linear code $C$ with minimum distance $d$, if a received vector $u$ satisfies $\text{angle}_H(u, C) < d/2$, then there exists a unique codeword direction $[c^\star] \in \mathbb{P}(C)$ closest to $u$. The proof relies on the triangle inequality of $\text{angle}_H$ to show that two distinct projective codewords cannot both be within distance $d/2$ of $u$.

5. Relation to Proximity-Gap (Section 5.3):
   The author discusses the connection between this angular framework and the "proximity-gap" problem (studying affine lines relative to codes). While $\text{angle}_H$ is invariant under scalar multiplication and does not directly capture affine geometry, the paper notes that the triangle inequality provides a uniqueness obstruction similar to that used in proximity-gap proofs. It suggests that the angular framework offers a "projective shadow" of these problems.

Significance and Claims
The paper claims to be the first attempt to define a notion of angle for vectors over finite fields that is interpreted from the perspectives of geometry, coding theory, and cryptography. Its significance lies in:

• Providing a geometric vocabulary for "parallelism" in finite fields where the inner-product picture fails.
• Establishing a rigorous metric structure on projective space over finite fields.
• Offering a clean, projective refinement of the unique decoding theorem, demonstrating that the classical $d/2$ decoding radius applies to projective directions as well as specific codewords.
• Laying the groundwork for future extensions to higher-dimensional angles (Grassmannian counterparts) and affine proximity-gap problems.

The author maintains a modest tone, noting that the angular unique decoding theorem is a "natural projective sibling" to the classical theorem rather than a strengthening of it, and explicitly leaves the development of a full "projective proximity-gap" problem as a direction for future work.