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

Technische Zusammenfassung: Winkel zwischen zwei Vektoren über endlichen Körpern und eine Anwendung auf projektives eindeutiges Dekodieren

Problemstellung
Im euklidischen Raum ($\mathbb{R}^n$) sind die geometrischen Konzepte von Abstand und Winkel fundamental, wobei die Winkelmessung elegant aus dem Skalarprodukt abgeleitet wird. Über endlichen Körpern ($\mathbb{F}_q^n$) versagt jedoch das Standard-Skalarprodukt, einen robusten geometrischen Rahmen zu bieten; insbesondere können von Null verschiedene Vektoren selbstorthogonal sein ($u \cdot u = 0$), und Orthogonalität erfasst die geometrische Senkrechte nicht getreu. Während der Hamming-Abstand ($d_H$) als zuverlässige Metrik für die Kodierungstheorie dient, gab es bisher keine etablierte, zufriedenstellende Vorstellung von „Winkel" oder „Parallelität" für Vektoren über endlichen Körpern, die als echte Metrik fungiert. Dieser Beitrag schließt die Lücke bei der Definition einer Winkelmessung auf $\mathbb{F}_q^n$, die unter Skalarmultiplikation invariant ist und auf den projektiven Raum $\mathbb{P}(\mathbb{F}_q^n)$ übergeht.

Methodik
Der Autor führt den Hamming-Winkel ein, bezeichnet als $\text{angle}_H(u, v)$, definiert für von Null verschiedene Vektoren $u, v \in \mathbb{F}_q^n$ als:
$$\text{angle}_H(u, v) := \min_{c \in \mathbb{F}_q^\star} d_H(u, cv)$$
wobei $d_H$ der Standard-Hamming-Abstand ist und $\mathbb{F}_q^\star$ die multiplikative Gruppe des Körpers bezeichnet. Diese Definition misst effektiv den minimalen Hamming-Abstand zwischen einem Vektor $u$ und der punktierten Geraden, die von $v$ aufgespannt wird.

Die Methodik verläuft durch drei Hauptschritte der Analyse:

1. Metrik-Verifikation: Der Beitrag beweist rigoros, dass $\text{angle}_H$ die drei Axiome einer Metrik erfüllt (Identität der Ununterscheidbaren bis auf Skalare, Symmetrie und die Dreiecksungleichung), wenn sie auf dem projektiven Raum betrachtet wird.
2. Algorithmische Analyse: Ein linearer Algorithmus ($O(n)$) wird vorgeschlagen, um $\text{angle}_H$ zu berechnen, indem Vektorkoordinaten basierend auf Mustern von Null/Nicht-Null partitioniert und die Übereinstimmungszahl für spezifische Skalare-Verhältnisse maximiert wird.
3. Anwendung in der Kodierungstheorie: Das Konzept wird auf lineare Codes angewendet, um eine winkelmäßige Version des Satzes über eindeutiges Dekodieren abzuleiten. Die Beziehung zwischen $\text{angle}_H(u, C)$ und dem Standard-Hamming-Abstand zu einem Code $d_H(u, C)$ wird sorgfältig analysiert, insbesondere bei der Unterscheidung von Fällen, in denen der Nullvektor der nächste Punkt ist.

Hauptbeiträge und Ergebnisse

1. Definition und Metrik-Eigenschaften (Satz 3.2):
   Der Hauptbeitrag ist der Beweis, dass $\text{angle}_H$ die Metrik-Axiome bis auf Skalarmultiplikation erfüllt. Spezifisch:

   • $\text{angle}_H(u, v) = 0$ genau dann, wenn $u$ und $v$ denselben projektiven Punkt aufspannen ($u = cv$).
   • $\text{angle}_H(u, v) = \text{angle}_H(v, u)$.
   • Die Dreiecksungleichung gilt: $\text{angle}_H(u, w) \leq \text{angle}_H(u, v) + \text{angle}_H(v, w)$.
     Folglich geht $\text{angle}_H$ auf eine wohldefinierte, ganzzahlige Metrik auf dem projektiven Raum $\mathbb{P}(\mathbb{F}_q^n)$ über.

2. Berechnungseffizienz (Proposition 4.3):
   Trotz der Definition, die eine Minimierung über $q-1$ Skalare beinhaltet, zeigt der Beitrag, dass $\text{angle}_H(u, v)$ in $O(n)$ Zeit berechnet werden kann. Dies wird erreicht, indem die Übereinstimmung von Koordinaten für spezifische Verhältnisse $u_i/v_i$ gezählt und die maximale Übereinstimmungszahl bestimmt wird.

3. Geometrische Unterscheidungen (Abschnitt 4.4):
   Der Beitrag hebt qualitative Unterschiede zwischen dem Hamming-Winkel und dem euklidischen Winkel hervor:

   • Versagen des Skalarprodukts: Im Gegensatz zu $\mathbb{R}^n$ impliziert $u \cdot v = 0$ keinen spezifischen „rechten Winkel" im Sinne des Hamming-Winkels. Vektoren können im Sinne des Skalarprodukts orthogonal sein und dennoch einen kleinen Hamming-Winkel haben.
   • Analogie zum statistischen Abstand: Der maximale Hamming-Winkel ($n$) tritt genau dann auf, wenn die Träger von $u$ und $v$ disjunkt sind (analog zu disjunkten Trägern beim statistischen Abstand), eine Eigenschaft, die in der euklidischen Geometrie nicht vorhanden ist.
   • Fall $q=2$: Für binäre Körper fällt der Hamming-Winkel exakt mit dem Hamming-Abstand zusammen, da der einzige von Null verschiedene Skalar 1 ist.

4. Winkelmäßiges eindeutiges Dekodieren (Satz 5.4):
   Der Beitrag beweist ein winkelmäßiges Analogon des klassischen Satzes über eindeutiges Dekodieren. Für einen linearen Code $C$ mit Mindestabstand $d$, wenn ein empfangener Vektor $u$ die Bedingung $\text{angle}_H(u, C) < d/2$ erfüllt, dann existiert eine eindeutige Codewort-Richtung $[c^\star] \in \mathbb{P}(C)$, die $u$ am nächsten liegt. Der Beweis stützt sich auf die Dreiecksungleichung von $\text{angle}_H$, um zu zeigen, dass zwei verschiedene projektive Codewörter nicht beide innerhalb des Abstands $d/2$ von $u$ liegen können.

5. Beziehung zum Proximity-Gap (Abschnitt 5.3):
   Der Autor diskutiert die Verbindung zwischen diesem winkelmäßigen Rahmen und dem „Proximity-Gap"-Problem (Untersuchung affiner Linien bezüglich Codes). Während $\text{angle}_H$ unter Skalarmultiplikation invariant ist und die affine Geometrie nicht direkt erfasst, stellt der Beitrag fest, dass die Dreiecksungleichung eine Eindeutigkeitsbarriere bietet, die derjenigen in Proximity-Gap-Beweisen ähnelt. Es wird vorgeschlagen, dass der winkelmäßige Rahmen einen „projektiven Schatten" dieser Probleme bietet.

Bedeutung und Behauptungen
Der Beitrag beansprucht, der erste Versuch zu sein, eine Vorstellung von Winkeln für Vektoren über endlichen Körpern zu definieren, die aus den Perspektiven der Geometrie, Kodierungstheorie und Kryptographie interpretiert wird. Seine Bedeutung liegt in:

• Bereitstellung eines geometrischen Vokabulars für „Parallelität" in endlichen Körpern, wo das Bild des Skalarprodukts versagt.
• Etablierung einer rigorosen Metrik-Struktur auf dem projektiven Raum über endlichen Körpern.
• Angebot einer sauberen, projektiven Verfeinerung des Satzes über eindeutiges Dekodieren, die zeigt, dass der klassische Dekodier-Radius $d/2$ sowohl für projektive Richtungen als auch für spezifische Codewörter gilt.
• Schaffung der Grundlagen für zukünftige Erweiterungen auf winkelmäßige Konzepte höherer Dimension (Grassmannsche Gegenstücke) und affine Proximity-Gap-Probleme.

Der Autor bewahrt einen bescheidenen Ton und stellt fest, dass der Satz über winkelmäßiges eindeutiges Dekodieren ein „natürliches projektives Geschwister" des klassischen Satzes ist und keine Verstärkung desselben darstellt, und überlässt die Entwicklung eines vollständigen „projektiven Proximity-Gap"-Problems ausdrücklich als Richtung für zukünftige Arbeit.