Semidefinite lower bounds for covering codes

Definizione del Problema
Il documento affronta il problema di determinare $K_q(n, r)$, definito come la dimensione minima di un codice di copertura $q$-ario di lunghezza di parola $n$ e raggio di copertura $r$. Un insieme di parole codice $C \subseteq \{0, \dots, q-1\}^n$ ha raggio di copertura $r$ se l'unione delle sfere di Hamming di raggio $r$ centrate sulle parole codice copre l'intero spazio di Hamming. Un caso specifico di questo problema, $K_3(n, 1)$, è noto come il "problema del football pool", che cerca il numero minimo di pronostici richiesti per garantire al massimo un errore in $n$ partite di calcio. Mentre i limiti superiori sono tipicamente stabiliti costruendo codici espliciti, questo articolo si concentra sulla derivazione di limiti inferiori migliorati per $K_q(n, r)$.

Metodologia
Gli autori si basano sul lavoro di Gijswijt (2005), che ha introdotto un limite inferiore di programmazione semidefinita (SDP) per i codici di copertura utilizzando tagli di matrici. La metodologia presentata in questo articolo rafforza tale limite attraverso tre principali avanzamenti tecnici:

1. Vincoli della Gerarchia di Lasserre: Gli autori introducono nuovi vincoli semidefiniti ispirati alla gerarchia di Lasserre per programmi 0-1. Nello specifico, utilizzano il secondo livello di questa gerarchia, che comporta l'analisi della distribuzione di triple di parole codice. Ciò porta alla costruzione di una matrice $N$ derivata dal vettore incidente del codice, soggetta a disuguaglianze di copertura della forma $\sum \lambda_i A_i(u) \ge \beta$.
2. Riduzione della Simmetria tramite Algebre di Terwilliger: Per rendere computazionalmente trattabile la risultante SDP, gli autori impiegano la riduzione della simmetria. Utilizzano l'algebra di Terwilliger dello schema di Hamming (sia nei casi binari che non binari). Identificando le orbite di coppie e triple di parole codice sotto l'azione del gruppo di isometria $Aut(q, n)$ (e del suo sottogruppo stabilizzatore $Aut_0(q, n)$), riducono la dimensionalità delle variabili matriciali.
   • Per il caso binario ($q=2$), l'algebra $A_{2,n}$ viene diagonalizzata a blocchi tramite un $\ast$-isomorfismo $\phi$ che la mappa in una somma diretta di blocchi matriciali più piccoli, riducendo la complessità da $O(2^n)$ a $O(n^3)$ variabili.
   • Per il caso non binario ($q \ge 3$), una simile diagonalizzazione a blocchi è applicata all'algebra $A_{q,n}$, riducendo la complessità a $O(n^4)$ variabili.
3. Funzione Obiettivo Potenziata: Il documento propone una funzione obiettivo più potente. Invece di minimizzare il termine lineare standard relativo alla dimensione del codice, gli autori minimizzano la traccia della variabile matrice corrispondente al terzo momento della dimensione del codice ($|C|^3$). Essi dimostrano che questa funzione obiettivo cubica produce un limite inferiore strettamente più stretto rispetto agli obiettivi lineari o quadratici precedentemente utilizzati.

Contributi Chiave

• Framework Teorico: Il documento stabilisce un rigoroso framework SDP per i codici di copertura che generalizza i limiti di Schrijver per i codici correttori di errori al problema della copertura. Deriva formalmente i vincoli per la matrice $N$ e le matrici bordate $R(c, N)$ nel contesto della gerarchia di Lasserre.
• Algoritmi di Riduzione della Simmetria: Gli autori forniscono formule esplicite per la diagonalizzazione a blocchi delle relative algebre di Terwilliger per gli schemi di Hamming sia binari che non binari. Ciò include coefficienti combinatori dettagliati ($\eta$ e $\alpha$) necessari per tradurre i vincoli di taglio matriciale e i vincoli di Lasserre nello spazio delle variabili ridotto.
• Implementazione Computazionale: Gli autori hanno implementato questi limiti utilizzando aritmetica ad alta precisione (512-bit BigFloats) tramite il linguaggio di programmazione Julia e il risolutore SDPA-GMP. Hanno sviluppato un codice indipendente per validare la generazione delle SDP.

Risultati
Gli autori presentano nuovi limiti inferiori per $K_q(n, r)$ attraverso una vasta gamma di parametri ($q, n, r$). Questi risultati sono compilati nelle Tabelle 1, 2 e 3, che coprono i casi binari ($q=2$), ternari ($q=3$) e quaternari/quinari ($q=4, 5$).

• Caso Binario: I nuovi limiti migliorano i limiti inferiori precedentemente noti per vari valori di $n$ e $r$ (ad esempio, $K_2(13, 1)$, $K_2(21, 1)$, $K_2(13, 2)$). Gli autori notano che, sebbene avessero inizialmente trovato limiti migliorati per $K_2(18, 1)$ e $K_2(30, 1)$, questi specifici valori sono stati successivamente superati da Wu e Chen (2026).
• Caso Non Binario: Sono riportati miglioramenti significativi per i codici ternari (problema del football pool), come $K_3(13, 3)$ e $K_3(14, 4)$, nonché per $q=4$ e $q=5$.
• Scala Computazionale: Il documento riporta il numero di variabili e le dimensioni dei blocchi per le SDP ridotte tramite simmetria. Ad esempio, per $n=32$ nel caso binario, la SDP ridotta coinvolge 1.239 variabili con una somma dei quadrati delle dimensioni dei blocchi pari a 6.545. I tempi di risoluzione sono variati da pochi secondi a diversi giorni, a seconda della dimensione dell'istanza e del numero di coefficienti non nulli nei vincoli di disuguaglianza.

Significatività
Il documento afferma che le tecniche proposte portano a "limiti inferiori più stretti" che stabiliscono nuovi record per una vasta gamma di parametri dei codici di copertura. Estendendo l'approccio della gerarchia di Lasserre ai codici di copertura e utilizzando efficacemente la riduzione della simmetria, gli autori dimostrano che il divario tra i limiti noti inferiori e superiori può essere ridotto. Il lavoro fornisce un metodo sistematico per calcolare questi limiti, offrendo un'alternativa più potente ai limiti di programmazione lineare e ai precedenti approcci SDP che non sfruttavano appieno i vincoli della distribuzione delle triple o l'ottimizzazione specifica della funzione obiettivo. I risultati servono come benchmark aggiornati per il campo dei codici di copertura e del problema del football pool.