Semidefinite lower bounds for covering codes

Probleemdefinitie
Het artikel behandelt het probleem van het bepalen van $K_q(n, r)$, gedefinieerd als de minimale grootte van een $q$-aire dekkingcode met woordlengte $n$ en dekkingsstraal $r$. Een verzameling codewoorden $C \subseteq \{0, \dots, q-1\}^n$ heeft een dekkingsstraal $r$ als de unie van Hamming-ballen met straal $r$ gecentreerd rond de codewoorden de gehele Hamming-ruimte dekt. Een specifieke instantie van dit probleem, $K_3(n, 1)$, staat bekend als het "voetbalpoolprobleem", dat zoekt naar het minimale aantal voorspellingen vereist om maximaal één fout in $n$ voetbalwedstrijden te garanderen. Hoewel bovengrenzen doorgaans worden vastgesteld door het construeren van expliciete codes, richt dit artikel zich op het afleiden van verbeterde ondergrenzen voor $K_q(n, r)$.

Methodologie
De auteurs bouwen voort op het werk van Gijswijt (2005), die een semidefiniet programmeerbare (SDP) ondergrens introduceerde voor dekkingscodes met behulp van matrix-cuts. De gepresenteerde methodologie versterkt deze grens via drie primaire technische vooruitgangen:

1. Lasserre-hiërarchie beperkingen: De auteurs introduceren nieuwe semidefiniete beperkingen geïnspireerd door de Lasserre-hiërarchie voor 0-1 programma's. Specifiek maken zij gebruik van het tweede niveau van deze hiërarchie, wat het analyseren van de distributie van triples van codewoorden met zich meebrengt. Dit leidt tot de constructie van een matrix $N$ afgeleid van de incidentievector van de code, onderworpen aan dekkingsongelijkheden van de vorm $\sum \lambda_i A_i(u) \ge \beta$.
2. Symmetrie-reductie via Terwilliger-algebra's: Om de resulterende SDP computationeel hanteerbaar te maken, passen de auteurs symmetrie-reductie toe. Zij maken gebruik van de Terwilliger-algebra van het Hamming-schema (zowel voor het binaire als het niet-binaire geval). Door de banen (orbits) van paren en triples van codewoorden te identificeren onder de werking van de isometriegroep $Aut(q, n)$ (en de stabilisator-subgroep $Aut_0(q, n)$), reduceren zij de dimensionaliteit van de matrixvariabelen.
   • Voor het binaire geval ($q=2$) wordt de algebra $A_{2,n}$ blokdiagonaal gedegenereerd met behulp van een $\ast$-isomorfisme $\phi$ dat deze mapt naar een directe som van kleinere matrixblokken, waardoor de complexiteit wordt gereduceerd van $O(2^n)$ naar $O(n^3)$ variabelen.
   • Voor het niet-binaire geval ($q \ge 3$) wordt een vergelijkbare blokdiagonaal degeneratie toegepast op de algebra $A_{q,n}$, wat de complexiteit reduceert tot $O(n^4)$ variabelen.
3. Verbeterde objectieffunctie: Het artikel stelt een krachtigere objectieffunctie voor. In plaats van het minimaliseren van de standaard lineaire term gerelateerd aan de codegrootte, minimaliseren de auteurs de trace van de matrixvariabele die overeenkomt met het derde moment van de codegrootte ($|C|^3$). Zij bewijzen dat deze kubische objectieffunctie een strikt nauwere ondergrens oplevert dan de eerder gebruikte lineaire of kwadratische objectieffuncties.

Kernbijdragen

• Theoretisch Kader: Het artikel vestigt een rigoureus SDP-kader voor dekkingscodes dat de Schrijver-grenzen voor foutcorrigerende codes generaliseert naar het dekkingprobleem. Het leidt formeel de beperkingen af voor de matrix $N$ en de begrensde matrices $R(c, N)$ binnen de context van de Lasserre-hiërarchie.
• Symmetrie-reductie Algoritmen: De auteurs bieden expliciete formules voor de blokdiagonaal degeneratie van de relevante Terwilliger-algebra's voor zowel binaire als niet-binaire Hamming-schema's. Dit omvat gedetailleerde combinatorische coëfficiënten ($\eta$ en $\alpha$) die nodig zijn om de matrix-cut beperkingen en Lasserre-beperkingen te vertalen naar de gereduceerde variabelenruimte.
• Computationele Implementatie: De auteurs hebben deze grenzen geïmplementeerd met behulp van hoog-precieze rekenkunde (512-bit BigFloats) via de programmeertaal Julia en de SDPA-GMP solver. Zij hebben onafhankelijke code ontwikkeld om de generatie van de SDP's te valideren.

Resultaten
De auteurs presenteren nieuwe ondergrenzen voor $K_q(n, r)$ over een breed scala aan parameters ($q, n, r$). Deze resultaten zijn samengevat in Tabellen 1, 2 en 3, die de binaire ($q=2$), ternaire ($q=3$) en quaternionale/quinaire ($q=4, 5$) gevallen dekken.

• Binair Geval: De nieuwe grenzen verbeteren de eerder bekende ondergrenzen voor diverse waarden van $n$ en $r$ (bijv. $K_2(13, 1)$, $K_2(21, 1)$, $K_2(13, 2)$). De auteurs merken op dat hoewel zij aanvankelijk verbeterde grenzen vonden voor $K_2(18, 1)$ en $K_2(30, 1)$, deze specifieke waarden later zijn overtroffen door Wu en Chen (2026).
• Niet-binair Geval: Significante verbeteringen worden gerapporteerd voor ternaire codes (voetbalpoolprobleem), zoals $K_3(13, 3)$ en $K_3(14, 4)$, evenals voor $q=4$ en $q=5$.
• Computationele Schaal: Het artikel rapporteert het aantal variabelen en blokgroottes voor de gesymmetrie-gereduceerde SDP's. Zo bevat een gereduceerde SDP voor $n=32$ in het binaire geval 1.239 variabelen met een som van de kwadraten van de blokgroottes van 6.545. De rekentijden varieerden van seconden tot enkele dagen, afhankelijk van de omvang van de instantie en het aantal niet-nul coëfficiënten in de ongelijkheidsbeperkingen.

Significantie
Het artikel beweert dat de voorgestelde technieken leiden tot "scherpere ondergrenzen" die nieuwe records vestigen voor een breed scala aan parameters van dekkingscodes. Door de Lasserre-hiërarchie-aanpak uit te breiden naar dekkingscodes en effectief gebruik te maken van symmetrie-reductie, demonstreren de auteurs dat de kloof tussen bekende onder- en bovengrenzen kan worden verkleind. Het werk biedt een systematische methode voor het berekenen van deze grenzen en biedt een krachtiger alternatief voor lineaire programmeringsgrenzen en eerdere SDP-benaderingen die de triple-distributie beperkingen of de specifieke optimalisatie van de objectieffunctie niet volledig benutten. De resultaten dienen als geüpdatete benchmarks voor het vakgebied van de dekkingscodes en het voetbalpoolprobleem.