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

Technische Samenvatting: Hoek tussen Twee Vectoren over Eindige Velden en een Toepassing op Projectieve Unieke Decoding

Probleemstelling
In de Euclidische ruimte ($\mathbb{R}^n$) zijn de geometrische concepten van afstand en hoek fundamenteel, waarbij de hoekmetriek elegant wordt afgeleid uit het inproduct. Echter, over eindige velden ($\mathbb{F}_q^n$) faalt het standaardinproduct om een robuust geometrisch kader te bieden; specifiek kunnen niet-nul vectoren zelf-orthogonaal zijn ($u \cdot u = 0$), en vangt orthogonaliteit de geometrische loodrechtheid niet getrouw. Hoewel de Hamming-afstand ($d_H$) als betrouwbare metriek voor coderingstheorie dient, bestaat er geen gevestigde, bevredigende notie van "hoek" of "parallelisme" voor vectoren over eindige velden die fungeert als een echte metriek. Dit artikel adresseert de lacune in het definiëren van een hoekmetriek op $\mathbb{F}_q^n$ die invariant is onder scalair vermenigvuldiging en neerdaalt naar de projectieve ruimte $\mathbb{P}(\mathbb{F}_q^n)$.

Methodologie
De auteur introduceert de Hamming-hoek, aangeduid als $\text{angle}_H(u, v)$, gedefinieerd voor niet-nul vectoren $u, v \in \mathbb{F}_q^n$ als:
$$\text{angle}_H(u, v) := \min_{c \in \mathbb{F}_q^\star} d_H(u, cv)$$
waarbij $d_H$ de standaard Hamming-afstand is en $\mathbb{F}_q^\star$ de multiplicatieve groep van het veld is. Deze definitie meet effectief de minimale Hamming-afstand tussen een vector $u$ en de gepuncteerde lijn opgespannen door $v$.

De methodologie verloopt via drie hoofdanalytische stappen:

1. Verificatie van de Metriek: Het artikel bewijst rigoureus dat $\text{angle}_H$ voldoet aan de drie axioma's van een metriek (identiteit van ononderscheidbaren tot op een scalar, symmetrie en de driehoeksongelijkheid) wanneer bekeken op de projectieve ruimte.
2. Algoritmische Analyse: Een lineaire-tijd algoritme ($O(n)$) wordt voorgesteld om $\text{angle}_H$ te berekenen door vectorcoördinaten te partitioneren op basis van nul/niet-nul patronen en het aantal overeenkomsten te maximaliseren voor specifieke scalairverhoudingen.
3. Toepassing in Coderingstheorie: Het concept wordt toegepast op lineaire codes om een hoekvariant van de unieke decoding-stelling af te leiden. De relatie tussen $\text{angle}_H(u, C)$ en de standaard Hamming-afstand tot een code $d_H(u, C)$ wordt zorgvuldig geanalyseerd, met name door gevallen te onderscheiden waar de nulvector het dichtstbijzijnde punt is.

Belangrijkste Bijdragen en Resultaten

1. Definitie en Metrische Eigenschappen (Stelling 3.2):
   De primaire bijdrage is het bewijs dat $\text{angle}_H$ voldoet aan de metriek-axioma's tot op scalair vermenigvuldiging. Specifiek:

   • $\text{angle}_H(u, v) = 0$ dan en slechts dan als $u$ en $v$ hetzelfde projectieve punt opspannen ($u = cv$).
   • $\text{angle}_H(u, v) = \text{angle}_H(v, u)$.
   • De driehoeksongelijkheid geldt: $\text{angle}_H(u, w) \leq \text{angle}_H(u, v) + \text{angle}_H(v, w)$.
     Bijgevolg daalt $\text{angle}_H$ neer tot een goed gedefinieerde, geheeltallige metriek op de projectieve ruimte $\mathbb{P}(\mathbb{F}_q^n)$.

2. Berekenings-efficiëntie (Propositie 4.3):
   Ondanks dat de definitie een minimalisatie over $q-1$ scalairen omvat, toont het artikel aan dat $\text{angle}_H(u, v)$ in $O(n)$ tijd kan worden berekend. Dit wordt bereikt door het tellen van coördinaatovereenkomsten voor specifieke verhoudingen $u_i/v_i$ en het bepalen van het maximale aantal overeenkomsten.

3. Geometrische Onderscheidingen (Sectie 4.4):
   Het artikel benadrukt kwalitatieve verschillen tussen de Hamming-hoek en de Euclidische hoek:

   • Falen van het Inproduct: In tegenstelling tot in $\mathbb{R}^n$, impliceert $u \cdot v = 0$ niet een specifieke "rechte hoek" in de Hamming-sens. Vectoren kunnen orthogonaal zijn in de zin van het inproduct en toch een kleine Hamming-hoek hebben.
   • Analogie met Statistische Afstand: De maximale Hamming-hoek ($n$) treedt precies op wanneer de supports van $u$ en $v$ disjunct zijn (analoog aan disjuncte supports in statistische afstand), een eigenschap die niet voorkomt in de Euclidische meetkunde.
   • Geval $q=2$: Voor binaire velden valt de Hamming-hoek exact samen met de Hamming-afstand, aangezien de enige niet-nul scalar 1 is.

4. Hoekmatige Unieke Decoding (Stelling 5.4):
   Het artikel bewijst een hoek-analoog van de klassieke stelling voor unieke decoding. Voor een lineaire code $C$ met minimale afstand $d$, als een ontvangen vector $u$ voldoet aan $\text{angle}_H(u, C) < d/2$, dan bestaat er een unieke codewoordrichting $[c^\star] \in \mathbb{P}(C)$ die het dichtst bij $u$ ligt. Het bewijs maakt gebruik van de driehoeksongelijkheid van $\text{angle}_H$ om aan te tonen dat twee verschillende projectieve codewoorden niet beide binnen afstand $d/2$ van $u$ kunnen liggen.

5. Relatie tot Proximity-Gap (Sectie 5.3):
   De auteur bespreekt de connectie tussen dit hoekmatige kader en het "proximity-gap"-probleem (het bestuderen van affiene lijnen ten opzichte van codes). Hoewel $\text{angle}_H$ invariant is onder scalair vermenigvuldiging en de affiene meetkunde niet direct vastlegt, merkt het artikel op dat de driehoeksongelijkheid een uniekheidsbelemmering biedt die vergelijkbaar is met die welke wordt gebruikt in proximity-gap-bewijzen. Het suggereert dat het hoekmatige kader een "projectieve schaduw" van deze problemen biedt.

Betekenis en Aanspraken
Het artikel claimt de eerste poging te zijn om een notie van hoek voor vectoren over eindige velden te definiëren die wordt geïnterpreteerd vanuit de perspectieven van meetkunde, coderingstheorie en cryptografie. De betekenis ligt in:

• Het verschaffen van een geometrische vocabulaire voor "parallelisme" in eindige velden waar het inproduct-beeld faalt.
• Het vestigen van een rigoureuze metriekstructuur op projectieve ruimte over eindige velden.
• Het bieden van een schone, projectieve verfijning van de stelling voor unieke decoding, waarbij wordt aangetoond dat de klassieke $d/2$ decodingstraal ook van toepassing is op projectieve richtingen en niet alleen op specifieke codewoorden.
• Het leggen van de basis voor toekomstige uitbreidingen naar hoeken in hogere dimensies (Grassmanniaanse tegenhangers) en affiene proximity-gap-problemen.

De auteur behoudt een bescheiden toon, merkt op dat de stelling voor hoekmatige unieke decoding een "natuurlijke projectieve broer" is van de klassieke stelling in plaats van een versterking daarvan, en laat de ontwikkeling van een volledig "projectief proximity-gap"-probleem expliciet over als een richting voor toekomstig werk.