Semidefinite lower bounds for covering codes

Problemdefinition
Die Arbeit befasst sich mit der Problemstellung der Bestimmung von $K_q(n, r)$, definiert als die minimale Größe eines $q$-ären Abdeckungscodes der Wortlänge $n$ und des Abdeckungsradius $r$. Eine Menge von Codewörtern $C \subseteq \{0, \dots, q-1\}^n$ hat den Abdeckungsradius $r$, wenn die Vereinigung der Hamming-Kugeln des Radius $r$, zentriert um die Codewörter, den gesamten Hamming-Raum abdeckt. Ein spezifischer Instanz dieses Problems, $K_3(n, 1)$, ist als „Fußballwetten-Problem“ bekannt, welches die Suche nach der minimalen Anzahl an Vorhersagen darstellt, um maximal einen Fehler in $n$ Fußballspielen zu garantieren. Während obere Schranken typischerweise durch die Konstruktion expliziter Codes etabliert werden, konzentriert sich diese Arbeit auf die Ableitung verbesserter unterer Schranken für $K_q(n, r)$.

Methodik
Die Autoren bauen auf der Arbeit von Gijswijt (2005) auf, die eine semidefinierte Programmierung (SDP)-untere Schranke für Abdeckungscodes mittels Matrix-Cuts einführte. Die in dieser Arbeit vorgestellte Methodik stärkt diese Schranke durch drei primäre technische Fortschritte:

1. Lasserre-Hierarchie-Constraints: Die Autoren führen neue semidefinierte Constraints ein, die von der Lasserre-Hierarchie für 0-1-Programme inspiriert sind. Speziell nutzen sie die zweite Ebene dieser Hierarchie, welche die Verteilung von Triples von Codewörtern analysiert. Dies führt zur Konstruktion einer Matrix $N$, die aus dem Inzidenzvektor des Codes abgeleitet ist, unterliegt jedoch Abdeckungsungleichungen der Form $\sum \lambda_i A_i(u) \ge \beta$.
2. Symmetriereduktion via Terwilliger-Algebren: Um die resultierende SDP rechnerisch handhabbar zu machen, wenden die Autoren eine Symmetriereduktion an. Sie nutzen die Terwilliger-Algebra des Hamming-Schemas (sowohl für den binären als auch für den nicht-binären Fall). Durch die Identifizierung der Orbits von Paaren und Triples von Codewörtern unter der Wirkung der Isometriegruppe $Aut(q, n)$ (und ihrer Stabilisatoruntergruppe $Aut_0(q, n)$) reduzieren sie die Dimensionalität der Matrixvariablen.
   • Für den binären Fall ($q=2$) wird die Algebra $A_{2,n}$ mittels eines $\ast$-Isomorphismus $\phi$, der sie auf eine direkte Summe kleinerer Matrixblöcke abbildet, blockdiagonalisiert, wodurch die Komplexität von $O(2^n)$ auf $O(n^3)$ Variablen reduziert wird.
   • Für den nicht-binären Fall ($q \ge 3$) wird eine ähnliche Blockdiagonalisierung auf die Algebra $A_{q,n}$ angewendet, was die Komplexität auf $O(n^4)$ Variablen reduziert.
3. Verbesserte Zielfunktion: Die Arbeit schlägt eine leistungsfähigere Zielfunktion vor. Anstatt den Standard-Linearterm bezüglich der Codegröße zu minimieren, minimieren die Autoren die Spur der Matrixvariable, die dem dritten Moment der Codegröße ($|C|^3$) entspricht. Sie beweisen, dass diese kubische Zielfunktion eine strikt engere untere Schranke liefert als die zuvor verwendeten linearen oder quadratischen Zielfunktionen.

Zentrale Beiträge

• Theoretischer Rahmen: Die Arbeit etabliert einen rigorosen SDP-Rahmen für Abdeckungscodes, der Schrijvers Schranken für Fehlerkorrekturcodes auf das Abdeckungsproblem generalisiert. Sie leitet formal die Constraints für die Matrix $N$ und die erweiterten Matrizen $R(c, N)$ im Kontext der Lasserre-Hierarchie her.
• Algorithmen zur Symmetriereduktion: Die Autoren liefern explizite Formeln für die Blockdiagonalisierung der relevanten Terwilliger-Algebren für sowohl binäre als auch nicht-binäre Hamming-Schemata. Dies beinhaltet detaillierte kombinatorische Koeffizienten ($\eta$ und $\alpha$), die erforderlich sind, um die Matrix-Cut-Ungleichungen und Lasserre-Constraints in den reduzierten Variablenraum zu übertragen.
• Kommerzielle Implementierung: Die Autoren implementierten diese Schranken unter Verwendung von Hochpräzisionsarithmetik (512-Bit BigFloats) über die Programmiersprache Julia und den SDPA-GMP Solver. Sie entwickelten einen unabhängigen Code, um die Generierung der SDPs zu validieren.

Ergebnisse
Die Autoren präsentieren neue untere Schranken für $K_q(n, r)$ über einen breiten Bereich von Parametern ($q, n, r$). Diese Ergebnisse sind in den Tabellen 1, 2 und 3 zusammengefasst und decken binäre ($q=2$), ternäre ($q=3$) sowie quarternäre/quinternäre ($q=4, 5$) Fälle ab.

• Binärer Fall: Die neuen Schranken verbessern die zuvor bekannten unteren Schranken für verschiedene Werte von $n$ und $r$ (z. B. $K_2(13, 1)$, $K_2(21, 1)$, $K_2(13, 2)$). Die Autoren merken an, dass sie zwar anfänglich verbesserte Schranken für $K_2(18, 1)$ und $K_2(30, 1)$ fanden, diese spezifischen Werte jedoch nachträglich von Wu und Chen (2026) übertroffen wurden.
• Nicht-binärer Fall: Signifikante Verbesserungen werden für ternäre Codes (Fußballwetten-Problem) berichtet, wie etwa $K_3(13, 3)$ und $K_3(14, 4)$, sowie für $q=4$ und $q=5$.
• Komputationelle Skalierbarkeit: Die Arbeit gibt die Anzahl der Variablen und Blockgrößen der symmetriereduzierten SDPs an. Beispielsweise umfasst das reduzierte SDP für $n=32$ im binären Fall 1.239 Variablen mit einer Summe der quadrierten Blockgrößen von 6.545. Die Rechenzeiten variierten von Sekunden bis hin zu mehreren Tagen, abhängig von der Größe der Instanz und der Anzahl der Nicht-Null-Koeffizienten in den Ungleichheitsconstraints.

Bedeutung
Die Arbeit behauptet, dass die vorgeschlagenen Techniken zu „schärferen unteren Schranken“ führen, die Rekorde für eine Vielzahl von Parametern der Abdeckungscodes aufstellen. Durch die Erweiterung des Lasserre-Hierarchie-Ansatzes auf Abdeckungscodes und die effektive Nutzung der Symmetriereduktion zeigen die Autoren, dass die Lücke zwischen bekannten unteren und oberen Schranken verkleinert werden kann. Die Arbeit bietet eine systematische Methode zur Berechnung dieser Schranken und stellt eine leistungsfähigere Alternative zu Linearen-Programmierung-Schranken und bisherigen SDP-Ansätzen dar, die die Constraints der Triple-Verteilung oder die Optimierung der spezifischen Zielfunktion nicht vollständig ausgenutzt haben. Die Ergebnisse dienen als aktualisierte Benchmarks für das Feld der Abdeckungscodes und des Fußballwetten-Problems.