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

Resumen Técnico: Ángulo entre Dos Vectores sobre Campos Finitos y una Aplicación a la Decodificación Única Proyectiva

Enunciado del Problema
En el espacio euclidiano ($\mathbb{R}^n$), los conceptos geométricos de distancia y ángulo son fundamentales, con la métrica angular derivada elegantemente del producto interno. Sin embargo, sobre campos finitos ($\mathbb{F}_q^n$), el producto interno estándar falla al proporcionar un marco geométrico robusto; específicamente, los vectores no nulos pueden ser auto-ortogonales ($u \cdot u = 0$), y la ortogonalidad no captura fielmente la perpendicularidad geométrica. Si bien la distancia de Hamming ($d_H$) sirve como una métrica fiable para la teoría de códigos, no ha existido una noción establecida y satisfactoria de "ángulo" o "paralelismo" para vectores sobre campos finitos que funcione como una métrica genuina. Este artículo aborda la brecha en la definición de una métrica angular en $\mathbb{F}_q^n$ que sea invariante bajo multiplicación escalar y que descienda al espacio proyectivo $\mathbb{P}(\mathbb{F}_q^n)$.

Metodología
El autor introduce el ángulo de Hamming, denotado $\text{angle}_H(u, v)$, definido para vectores no nulos $u, v \in \mathbb{F}_q^n$ como:
$$\text{angle}_H(u, v) := \min_{c \in \mathbb{F}_q^\star} d_H(u, cv)$$
donde $d_H$ es la distancia de Hamming estándar y $\mathbb{F}_q^\star$ es el grupo multiplicativo del campo. Esta definición mide efectivamente la distancia de Hamming mínima entre un vector $u$ y la línea punteada generada por $v$.

La metodología procede a través de tres pasos analíticos principales:

1. Verificación de Métrica: El artículo demuestra rigurosamente que $\text{angle}_H$ satisface los tres axiomas de una métrica (identidad de indiscernibles hasta escalar, simetría y la desigualdad triangular) cuando se observa en el espacio proyectivo.
2. Análisis Algorítmico: Se propone un algoritmo de tiempo lineal ($O(n)$) para calcular $\text{angle}_H$ mediante la partición de las coordenadas del vector basándose en patrones de cero/no cero y maximizando la cuenta de coincidencias para relaciones escalares específicas.
3. Aplicación a la Teoría de Códigos: El concepto se aplica a códigos lineales para derivar una versión angular del teorema de decodificación única. La relación entre $\text{angle}_H(u, C)$ y la distancia de Hamming estándar a un código $d_H(u, C)$ se analiza cuidadosamente, distinguiendo particularmente los casos donde el vector cero es el punto más cercano.

Contribuciones y Resultados Clave

1. Definición y Propiedades de Métrica (Teorema 3.2):
   La contribución principal es la prueba de que $\text{angle}_H$ satisface los axiomas de métrica hasta la multiplicación escalar. Específicamente:

   • $\text{angle}_H(u, v) = 0$ si y solo si $u$ y $v$ generan el mismo punto proyectivo ($u = cv$).
   • $\text{angle}_H(u, v) = \text{angle}_H(v, u)$.
   • Se cumple la desigualdad triangular: $\text{angle}_H(u, w) \leq \text{angle}_H(u, v) + \text{angle}_H(v, w)$.
     En consecuencia, $\text{angle}_H$ desciende a una métrica bien definida con valores enteros en el espacio proyectivo $\mathbb{P}(\mathbb{F}_q^n)$.

2. Eficiencia Computacional (Proposición 4.3):
   A pesar de que la definición implica una minimización sobre $q-1$ escalares, el artículo demuestra que $\text{angle}_H(u, v)$ puede calcularse en tiempo $O(n)$. Esto se logra contando las coincidencias de coordenadas para relaciones específicas $u_i/v_i$ y determinando la cuenta máxima de coincidencias.

3. Distinciones Geométricas (Sección 4.4):
   El artículo destaca diferencias cualitativas entre el ángulo de Hamming y el ángulo euclidiano:

   • Fallo del Producto Interno: A diferencia de en $\mathbb{R}^n$, $u \cdot v = 0$ no implica un "ángulo recto" específico en el sentido de Hamming. Los vectores pueden ser ortogonales en el sentido del producto interno y sin embargo tener un ángulo de Hamming pequeño.
   • Analogía con la Distancia Estadística: El ángulo de Hamming máximo ($n$) ocurre precisamente cuando los soportes de $u$ y $v$ son disjuntos (análogo a soportes disjuntos en la distancia estadística), una propiedad no presente en la geometría euclidiana.
   • Caso $q=2$: Para campos binarios, el ángulo de Hamming coincide exactamente con la distancia de Hamming, ya que el único escalar no nulo es 1.

4. Decodificación Única Angular (Teorema 5.4):
   El artículo prueba un análogo angular del teorema clásico de decodificación única. Para un código lineal $C$ con distancia mínima $d$, si un vector recibido $u$ satisface $\text{angle}_H(u, C) < d/2$, entonces existe una única dirección de palabra de código $[c^\star] \in \mathbb{P}(C)$ más cercana a $u$. La prueba se basa en la desigualdad triangular de $\text{angle}_H$ para mostrar que dos palabras de código proyectivas distintas no pueden estar ambas dentro de la distancia $d/2$ de $u$.

5. Relación con el Hueco de Proximidad (Sección 5.3):
   El autor discute la conexión entre este marco angular y el problema del "hueco de proximidad" (estudiar líneas afines relativas a códigos). Si bien $\text{angle}_H$ es invariante bajo multiplicación escalar y no captura directamente la geometría afín, el artículo señala que la desigualdad triangular proporciona una obstrucción de unicidad similar a la utilizada en las pruebas del hueco de proximidad. Sugiere que el marco angular ofrece una "sombra proyectiva" de estos problemas.

Significado y Afirmaciones
El artículo afirma ser el primer intento de definir una noción de ángulo para vectores sobre campos finitos que sea interpretada desde las perspectivas de la geometría, la teoría de códigos y la criptografía. Su importancia radica en:

• Proporcionar un vocabulario geométrico para el "paralelismo" en campos finitos donde la imagen del producto interno falla.
• Establecer una estructura métrica rigurosa en el espacio proyectivo sobre campos finitos.
• Ofrecer un refinamiento proyectivo y limpio del teorema de decodificación única, demostrando que el radio de decodificación clásico de $d/2$ aplica tanto a direcciones proyectivas como a palabras de código específicas.
• Sentar las bases para futuras extensiones a ángulos de dimensiones superiores (contrapartes de Grassmann) y problemas de hueco de proximidad afín.

El autor mantiene un tono modesto, señalando que el teorema de decodificación única angular es un "hermano proyectivo natural" del teorema clásico en lugar de un fortalecimiento del mismo, y deja explícitamente el desarrollo de un problema completo de "hueco de proximidad proyectivo" como una dirección para trabajo futuro.