Sharper upper bounds for $q$-ary $B_2$ codes from Toeplitz SDPs

1. Problemstellung

Das Paper befasst sich mit der Bestimmung der asymptotischen Rate (Informationsdichte) von q-ären B2-Codes.

• Definition eines B2-Codes: Ein q-ärer Code $C_n \subset \{0, \dots, q-1\}^n$ der Länge $n$ ist ein B2-Code, wenn alle Summen $c_i + c_j$ (für $1 \le i \le j \le M$, wobei $M$ die Anzahl der Codewörter ist) über den reellen Zahlen paarweise verschieden sind. Für $q=2$ entspricht dies der Definition von 2-separablen Codes.
• Ziel: Die Bestimmung einer oberen Schranke für die Rate $R = \limsup_{n \to \infty} \frac{1}{n} \log_q |C_n|$.
• Herausforderung: Bisherige Schranken basierten oft auf vereinfachten informationstheoretischen Argumenten, bei denen die Entropie der Differenz zweier unabhängiger Zufallsvariablen $X$ und $Y$ (die Codewörter oder Suffixe repräsentieren) nur unter der schwachen Bedingung $P(X=Y) \ge 1/q$ maximiert wurde. Dies führte zu relativ groben oberen Schranken für die Entropie $H(X-Y)$ und damit für die Code-Rate.

2. Methodik

Der Autor entwickelt eine verfeinerte Methode, die die volle Fourier-analytische Struktur der Differenzverteilung $D = X - Y$ ausnutzt, anstatt nur die Kollisionswahrscheinlichkeit zu betrachten.

• Fourier-Darstellung der Differenz:
  Seien $X$ und $Y$ i.i.d. (unabhängig und identisch verteilt) mit Wahrscheinlichkeitsmassenfunktion (pmf) $p$ auf $\{0, \dots, q-1\}$. Die pmf der Differenz $D = X - Y$ (über den ganzen Zahlen) ist die Autokorrelation von $p$.
  Die charakteristische Funktion von $D$ ist $\psi_D(\theta) = |\phi(\theta)|^2$, wobei $\phi(\theta)$ die charakteristische Funktion von $X$ ist.
  Daraus folgt, dass die Fourier-Reihe der pmf von $D$, bezeichnet als $R(\theta) = \sum r_k e^{ik\theta}$, ein nichtnegatives trigonometrisches Polynom vom Grad höchstens $q-1$ sein muss.

• Konvexe Optimierung:
  Statt die Entropie $H(D)$ nur unter der Bedingung $r_0 = P(X=Y) \ge 1/q$ zu maximieren, formuliert der Autor ein Optimierungsproblem, bei dem die Nichtnegativität des Polynoms $R(\theta) \ge 0$ für alle $\theta \in [0, 2\pi]$ als zusätzliche Nebenbedingung eingeführt wird.
  Dies führt zu einer Schranke $h_q^F$, die strikt kleiner (besser) ist als die vorherige Schranke $\bar{h}_q$.

• Toeplitz-SDP-Formulierung:
  Die Bedingung, dass $R(\theta)$ ein nichtnegatives trigonometrisches Polynom ist, ist äquivalent dazu, dass die zugehörigen Toeplitz-Matrizen $T^{(N)}(r)$ (gebildet aus den Koeffizienten $r_k$) für alle $N \ge 1$ positiv semidefinit (PSD) sind.
  Da dies unendlich viele Bedingungen sind, wird das Problem numerisch durch eine abgeschnittene Toeplitz-SDP (Semidefinite Programming) gelöst, bei der die PSD-Bedingungen nur für $N \le N_{max}$ (hier $N_{max}=100$) überprüft werden. Dies liefert eine zertifizierte obere Schranke für die maximale Entropie.

• Einbindung in die Rate-Beweisführung:
  Die verbesserte Entropieschranke $h_q^F$ wird in das bekannte „Prefix-Suffix"-Argument für B2-Codes integriert. Durch Aufteilung der Codewörter in Präfixe und Suffixe und Nutzung der Injektivität der Differenzabbildung innerhalb von Klassen wird gezeigt, dass die Rate $R_b$ durch den Ausdruck $\frac{h_q^F}{\log q + h_q^F}$ nach oben beschränkt ist.

3. Wichtige Beiträge

1. Fourier-analytische Relaxierung: Einführung einer neuen Relaxierung für die Verteilung der Differenz $D=X-Y$, die die Eigenschaft nutzt, dass die charakteristische Funktion ein nichtnegatives trigonometrisches Polynom ist.
2. Äquivalenz zu Toeplitz-PSD: Explizite Herleitung der Äquivalenz zwischen der Nichtnegativität des Polynoms und einer unendlichen Familie von Toeplitz-PSD-Bedingungen, was die Verbindung zu klassischen Ergebnissen der positiven Definitheit herstellt.
3. Verbesserte Entropieschranke: Nachweis, dass diese Relaxierung zu einer strikt kleineren oberen Schranke für die Entropie $H(X-Y)$ führt als bisherige Methoden, die nur die Kollisionswahrscheinlichkeit berücksichtigten.
4. Numerische Ergebnisse: Berechnung neuer, verbesserter Rate-Obergrenzen für $q \in \{9, 10, 11, 12, 13\}$ mittels abgeschnittener Toeplitz-SDPs.

4. Ergebnisse

Die numerische Auswertung zeigt, dass die neuen Schranken für $q \in \{9, 10, 11, 12, 13\}$ die besten bisher in der Literatur bekannten Schranken übertreffen (insbesondere die von Lindström [3], Della Fiore–Dalai [5] und Wang [7]).

Tabelle I (Zusammenfassung der Rate-Obergrenzen $R_{new}$ vs. Literatur):

Hinweis: Alle Werte sind aufwärts gerundet.

Die Verbesserungen sind signifikant, insbesondere im Vergleich zu Lindströms klassischen Schranken, aber auch gegenüber den kürzlich veröffentlichten Arbeiten [5] und [7].

5. Bedeutung und Ausblick

• Theoretischer Fortschritt: Das Paper demonstriert, dass die Berücksichtigung der globalen Struktur (Fourier-Positivität) von Verteilungen, die als Autokorrelationen entstehen, zu strengeren informationstheoretischen Schranken führt als die Betrachtung lokaler Momente (wie $P(X=Y)$) allein.
• Methodische Innovation: Die Kombination von informationstheoretischen Argumenten mit semidefiniter Programmierung (SDP) und Fourier-Analyse bietet einen neuen Weg zur Analyse von Codes mit Summen-Eindeutigkeitsbedingungen.
• Zukünftige Richtungen: Der Autor schlägt vor, die Relaxierung weiter zu verschärfen, indem zusätzliche notwendige Bedingungen für Autokorrelationen (z. B. Momentenbedingungen durch den Träger $\{0, \dots, q-1\}$) hinzugefügt werden. Zudem könnte die Methode auf andere Code-Familien oder höhere Summenmengen (z. B. $B_h$-Bedingungen) erweitert werden.

Zusammenfassend liefert dieses Paper einen wesentlichen Fortschritt im Verständnis der Grenzen von q-ären B2-Codes durch die Anwendung moderner Optimierungstechniken auf klassische informationstheoretische Probleme.