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

Resumo Técnico: Ângulo entre Dois Vetores sobre Corpos Finitos e uma Aplicação à Decodificação Única Projetiva

Enunciado do Problema
No espaço euclidiano ($\mathbb{R}^n$), os conceitos geométricos de distância e ângulo são fundamentais, com a métrica angular derivada elegantemente do produto interno. No entanto, sobre corpos finitos ($\mathbb{F}_q^n$), o produto interno padrão falha em fornecer uma estrutura geométrica robusta; especificamente, vetores não nulos podem ser auto-ortogonais ($u \cdot u = 0$), e a ortogonalidade não captura fielmente a perpendicularidade geométrica. Embora a distância de Hamming ($d_H$) sirva como uma métrica confiável para a teoria dos códigos, não havia uma noção estabelecida e satisfatória de "ângulo" ou "paralelismo" para vetores sobre corpos finitos que funcionasse como uma métrica genuína. Este artigo aborda a lacuna na definição de uma métrica angular em $\mathbb{F}_q^n$ que seja invariante sob multiplicação escalar e que desça ao espaço projetivo $\mathbb{P}(\mathbb{F}_q^n)$.

Metodologia
O autor introduz o ângulo de Hamming, denotado por $\text{angle}_H(u, v)$, definido para vetores não 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)$$
onde $d_H$ é a distância de Hamming padrão e $\mathbb{F}_q^\star$ é o grupo multiplicativo do corpo. Esta definição mede efetivamente a distância de Hamming mínima entre um vetor $u$ e a linha perfurada gerada por $v$.

A metodologia prossegue através de três etapas analíticas principais:

1. Verificação de Métrica: O artigo prova rigorosamente que $\text{angle}_H$ satisfaz os três axiomas de uma métrica (identidade dos indiscerníveis até escalar, simetria e a desigualdade triangular) quando vista no espaço projetivo.
2. Análise Algorítmica: Um algoritmo de tempo linear ($O(n)$) é proposto para calcular $\text{angle}_H$ partindo as coordenadas do vetor com base em padrões de zero/não-zero e maximizando a contagem de concordância para razões escalares específicas.
3. Aplicação à Teoria dos Códigos: O conceito é aplicado a códigos lineares para derivar uma versão angular do teorema da decodificação única. A relação entre $\text{angle}_H(u, C)$ e a distância de Hamming padrão a um código $d_H(u, C)$ é cuidadosamente analisada, distinguindo particularmente casos onde o vetor nulo é o ponto mais próximo.

Principais Contribuições e Resultados

1. Definição e Propriedades de Métrica (Teorema 3.2):
   A contribuição primária é a prova de que $\text{angle}_H$ satisfaz os axiomas de métrica até multiplicação escalar. Especificamente:

   • $\text{angle}_H(u, v) = 0$ se e somente se $u$ e $v$ geram o mesmo ponto projetivo ($u = cv$).
   • $\text{angle}_H(u, v) = \text{angle}_H(v, u)$.
   • A desigualdade triangular vale: $\text{angle}_H(u, w) \leq \text{angle}_H(u, v) + \text{angle}_H(v, w)$.
     Consequentemente, $\text{angle}_H$ desce a uma métrica bem definida com valores inteiros no espaço projetivo $\mathbb{P}(\mathbb{F}_q^n)$.

2. Eficiência Computacional (Proposição 4.3):
   Apesar da definição envolver uma minimização sobre $q-1$ escalares, o artigo demonstra que $\text{angle}_H(u, v)$ pode ser computado em tempo $O(n)$. Isso é alcançado contando as concordâncias de coordenadas para razões específicas $u_i/v_i$ e determinando a contagem máxima de concordância.

3. Distinções Geométricas (Seção 4.4):
   O artigo destaca diferenças qualitativas entre o ângulo de Hamming e o ângulo euclidiano:

   • Falha do Produto Interno: Ao contrário de $\mathbb{R}^n$, $u \cdot v = 0$ não implica um "ângulo reto" específico no sentido de Hamming. Vetores podem ser ortogonais no sentido do produto interno e ainda assim ter um ângulo de Hamming pequeno.
   • Analogia com Distância Estatística: O ângulo de Hamming máximo ($n$) ocorre precisamente quando os suportes de $u$ e $v$ são disjuntos (análogo a suportes disjuntos na distância estatística), uma propriedade não presente na geometria euclidiana.
   • Caso $q=2$: Para corpos binários, o ângulo de Hamming coincide exatamente com a distância de Hamming, pois o único escalar não nulo é 1.

4. Decodificação Única Angular (Teorema 5.4):
   O artigo prova um análogo angular do teorema clássico de decodificação única. Para um código linear $C$ com distância mínima $d$, se um vetor recebido $u$ satisfaz $\text{angle}_H(u, C) < d/2$, então existe uma direção de palavra-código única $[c^\star] \in \mathbb{P}(C)$ mais próxima de $u$. A prova baseia-se na desigualdade triangular de $\text{angle}_H$ para mostrar que duas direções de palavras-código projetivas distintas não podem estar ambas dentro da distância $d/2$ de $u$.

5. Relação com Proximidade-Vazio (Seção 5.3):
   O autor discute a conexão entre esta estrutura angular e o problema de "proximidade-vazio" (estudando linhas afins em relação a códigos). Embora $\text{angle}_H$ seja invariante sob multiplicação escalar e não capture diretamente a geometria afim, o artigo observa que a desigualdade triangular fornece uma obstrução de unicidade semelhante à usada em provas de proximidade-vazio. Sugere-se que a estrutura angular oferece uma "sombra projetiva" desses problemas.

Significância e Alegações
O artigo afirma ser a primeira tentativa de definir uma noção de ângulo para vetores sobre corpos finitos que seja interpretada a partir das perspectivas de geometria, teoria dos códigos e criptografia. Sua significância reside em:

• Fornecer um vocabulário geométrico para "paralelismo" em corpos finitos onde a imagem do produto interno falha.
• Estabelecer uma estrutura métrica rigorosa no espaço projetivo sobre corpos finitos.
• Oferecer um refinamento projetivo limpo do teorema de decodificação única, demonstrando que o raio de decodificação clássico $d/2$ aplica-se a direções projetivas, bem como a palavras-código específicas.
• Lançar as bases para futuras extensões a ângulos de dimensão superior (contrapartes de Grassmanniana) e problemas de proximidade-vazio afins.

O autor mantém um tom modesto, observando que o teorema de decodificação única angular é um "irmão projetivo natural" do teorema clássico, em vez de um fortalecimento dele, e deixa explicitamente o desenvolvimento de um problema completo de "proximidade-vazio projetivo" como uma direção para trabalhos futuros.