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

Sintesi Tecnica: Angolo tra Due Vettori su Campi Finiti e un'Applicazione alla Decodifica Unica Proiettiva

Enunciato del Problema
Nello spazio euclideo ($\mathbb{R}^n$), i concetti geometrici di distanza e angolo sono fondamentali, con la metrica angolare derivata elegantemente dal prodotto scalare. Tuttavia, sui campi finiti ($\mathbb{F}_q^n$), il prodotto scalare standard non riesce a fornire un quadro geometrico robusto; in particolare, vettori non nulli possono essere auto-ortogonali ($u \cdot u = 0$), e l'ortogonalità non cattura fedelmente la perpendicolarità geometrica. Sebbene la distanza di Hamming ($d_H$) serva come metrica affidabile per la teoria dei codici, non è esistita una nozione stabilita e soddisfacente di "angolo" o "parallelismo" per vettori su campi finiti che funzioni come una vera e propria metrica. Questo lavoro affronta il vuoto nella definizione di una metrica angolare su $\mathbb{F}_q^n$ che sia invariante rispetto alla moltiplicazione per scalari e che discenda allo spazio proiettivo $\mathbb{P}(\mathbb{F}_q^n)$.

Metodologia
L'autore introduce l'angolo di Hamming, denotato $\text{angle}_H(u, v)$, definito per vettori non nulli $u, v \in \mathbb{F}_q^n$ come:
$$\text{angle}_H(u, v) := \min_{c \in \mathbb{F}_q^\star} d_H(u, cv)$$
dove $d_H$ è la distanza di Hamming standard e $\mathbb{F}_q^\star$ è il gruppo moltiplicativo del campo. Questa definizione misura efficacemente la minima distanza di Hamming tra un vettore $u$ e la retta forata generata da $v$.

La metodologia procede attraverso tre principali fasi analitiche:

1. Verifica della Metrica: Il lavoro dimostra rigorosamente che $\text{angle}_H$ soddisfa i tre assiomi di una metrica (identità degli indiscernibili fino a scalare, simmetria e disuguaglianza triangolare) quando considerata sullo spazio proiettivo.
2. Analisi Algoritmica: Viene proposto un algoritmo a tempo lineare ($O(n)$) per calcolare $\text{angle}_H$ partizionando le coordinate del vettore in base ai pattern zero/non-zero e massimizzando il conteggio degli accordi per specifici rapporti scalari.
3. Applicazione alla Teoria dei Codici: Il concetto è applicato ai codici lineari per derivare una versione angolare del teorema della decodifica unica. La relazione tra $\text{angle}_H(u, C)$ e la distanza di Hamming standard verso un codice $d_H(u, C)$ è analizzata con cura, distinguendo in particolare i casi in cui il vettore nullo è il punto più vicino.

Contributi e Risultati Chiave

1. Definizione e Proprietà Metriche (Teorema 3.2):
   Il contributo principale è la dimostrazione che $\text{angle}_H$ soddisfa gli assiomi metrici fino alla moltiplicazione per scalari. Nello specifico:

   • $\text{angle}_H(u, v) = 0$ se e solo se $u$ e $v$ generano lo stesso punto proiettivo ($u = cv$).
   • $\text{angle}_H(u, v) = \text{angle}_H(v, u)$.
   • Vale la disuguaglianza triangolare: $\text{angle}_H(u, w) \leq \text{angle}_H(u, v) + \text{angle}_H(v, w)$.
     Di conseguenza, $\text{angle}_H$ discende a una metrica ben definita a valori interi sullo spazio proiettivo $\mathbb{P}(\mathbb{F}_q^n)$.

2. Efficienza Computazionale (Proposizione 4.3):
   Nonostante la definizione implichi una minimizzazione su $q-1$ scalari, il lavoro dimostra che $\text{angle}_H(u, v)$ può essere calcolato in tempo $O(n)$. Ciò è ottenuto contando gli accordi di coordinate per specifici rapporti $u_i/v_i$ e determinando il conteggio massimo di accordi.

3. Distinzioni Geometriche (Sezione 4.4):
   Il lavoro evidenzia differenze qualitative tra l'angolo di Hamming e l'angolo euclideo:

   • Fallimento del Prodotto Scalare: A differenza di quanto avviene in $\mathbb{R}^n$, $u \cdot v = 0$ non implica un specifico "angolo retto" nel senso di Hamming. I vettori possono essere ortogonali nel senso del prodotto scalare e tuttavia avere un angolo di Hamming piccolo.
   • Analogia con la Distanza Statistica: L'angolo di Hamming massimo ($n$) si verifica precisamente quando i supporti di $u$ e $v$ sono disgiunti (analogo ai supporti disgiunti nella distanza statistica), una proprietà assente nella geometria euclidea.
   • Caso $q=2$: Per i campi binari, l'angolo di Hamming coincide esattamente con la distanza di Hamming, poiché l'unico scalare non nullo è 1.

4. Decodifica Unica Angolare (Teorema 5.4):
   Il lavoro dimostra un analogo angolare del classico teorema della decodifica unica. Per un codice lineare $C$ con distanza minima $d$, se un vettore ricevuto $u$ soddisfa $\text{angle}_H(u, C) < d/2$, allora esiste una direzione unica di parola di codice $[c^\star] \in \mathbb{P}(C)$ più vicina a $u$. La dimostrazione si basa sulla disuguaglianza triangolare di $\text{angle}_H$ per mostrare che due distinte parole di codice proiettive non possono entrambe trovarsi entro una distanza $d/2$ da $u$.

5. Relazione con il Proximity-Gap (Sezione 5.3):
   L'autore discute la connessione tra questo quadro angolare e il problema del "proximity-gap" (studio delle rette affini rispetto ai codici). Sebbene $\text{angle}_H$ sia invariante rispetto alla moltiplicazione per scalari e non catturi direttamente la geometria affine, il lavoro nota che la disuguaglianza triangolare fornisce un ostacolo all'unicità simile a quello utilizzato nelle dimostrazioni del proximity-gap. Si suggerisce che il quadro angolare offra una "ombra proiettiva" di tali problemi.

Significato e Affermazioni
Il lavoro si presenta come il primo tentativo di definire una nozione di angolo per vettori su campi finiti interpretata dalle prospettive della geometria, della teoria dei codici e della crittografia. Il suo significato risiede nel:

• Fornire un vocabolario geometrico per il "parallelismo" nei campi finiti dove l'immagine del prodotto scalare fallisce.
• Stabilire una struttura metrica rigorosa sullo spazio proiettivo su campi finiti.
• Offrire una raffinazione proiettiva pulita del teorema della decodifica unica, dimostrando che il classico raggio di decodifica $d/2$ si applica anche alle direzioni proiettive oltre che alle specifiche parole di codice.
• Porre le basi per future estensioni ad angoli di dimensioni superiori (corrispettivi grassmanniani) e a problemi di proximity-gap affini.

L'autore mantiene un tono modesto, notando che il teorema della decodifica unica angolare è un "fratello proiettivo naturale" del teorema classico piuttosto che un suo rafforzamento, e lascia esplicitamente lo sviluppo di un completo problema di "proximity-gap proiettivo" come direzione per lavori futuri.