Semidefinite and linear programming bounds for sum-rank-metric codes and non-existence results

1. Enunciato del Problema

Il lavoro affronta il problema fondamentale nella teoria dei codici di determinare la dimensione massima, indicata come $A(q, n, m, d)$, di un codice con una distanza minima prescritta $d$ all'interno della metrica somma-rango.

• Contesto: La metrica somma-rango generalizza sia la metrica di Hamming (errori simbolo per simbolo) sia la metrica di rango (errori di tipo rango). È cruciale per applicazioni moderne come il coding di rete multishot, lo storage distribuito e il coding spazio-temporale.
• Sfida: Sebbene esistano limiti per le metriche di Hamming e di rango, la natura ibrida della metrica somma-rango genera fenomeni combinatori e algebrici unici. I limiti esistenti (ad esempio Singleton, Hamming, Plotkin e il classico Delsarte LP) spesso non forniscono limiti superiori stretti o non riescono a escludere l'esistenza di codici ottimali (come codici a Massima Distanza Somma-Rango (MSRD) o codici perfetti) in specifici regimi di parametri.
• Obiettivo: Derivare limiti superiori più precisi utilizzando la teoria spettrale dei grafi e tecniche di ottimizzazione (Programmazione Lineare e Programmazione Semidefinita) e utilizzare questi limiti per dimostrare risultati di non-esistenza per codici estremali.

2. Metodologia

Gli autori adottano un approccio multiforme che combina teoria algebrica dei grafi, ottimizzazione combinatoria ed esperimenti computazionali:

• Quadro Teorico dei Grafi: Associato allo spazio metrico somma-rango $F_q^{n \times m}$ un grafo $\Gamma$ in cui i vertici sono le parole del codice e gli spigoli rappresentano distanza 1. Il problema di trovare la dimensione massima del codice è equivalente al limitare il numero di indipendenza di questo grafo.
• Metodi Spettrali: Sfruttano gli autovalori della matrice di adiacenza del grafo della metrica somma-rango per derivare limiti.
  • Limite di tipo Rapporto: Un limite spettrale basato sugli autovalori del grafo.
  • Numero di Lovász Theta: Un limite di tipo algebrico-teorico sui grafi.
• Programmazione Lineare (LP):
  • LP di Delsarte: Basato sullo schema di associazione della metrica somma-rango, utilizzando la seconda matrice degli autovalori per vincolare la distribuzione delle distanze.
  • LP di tipo Rapporto: Una formulazione LP derivata dal limite di tipo Rapporto utilizzando polinomi minori.
• Programmazione Semidefinita (SDP):
  • SDP di tipo Schrijver: Gli autori introducono un nuovo limite SDP che estende il quadro di Delsarte. Mentre l'LP di Delsarte considera le distanze a coppie, questo SDP incorpora vincoli basati su terzine di parole del codice (specificamente terzine contenenti il vettore nullo), sfruttando la semidefinità positiva di una matrice che codifica queste terzine.
• Verifica Computazionale: Gli autori utilizzano il linguaggio di programmazione Julia con il pacchetto di riduzione della simmetria di Jordan per calcolare questi limiti per vari parametri, confrontandoli con i limiti teorici noti.

3. Contributi Chiave

A. Un Nuovo Limite di Programmazione Semidefinita (SDP)

Il lavoro introduce un limite SDP di tipo Schrijver per la metrica somma-rango.

• Meccanismo: Rafforza l'LP di Delsarte a coppie imponendo vincoli sulle terzine di parole del codice.
• Prestazioni: Gli esperimenti computazionali mostrano che questo limite SDP migliora strettamente i migliori limiti esistenti (inclusi LP di Delsarte, di tipo Rapporto e limiti classici di codifica) in diversi regimi di parametri.
• Gerarchia: Il lavoro stabilisce la gerarchia: $A(q, n, m, d) \leq \text{SDP} \leq \text{LP di Delsarte}$.

B. Equivalenza dei Limiti LP in Regimi Estremali

Gli autori eseguono un confronto rigoroso tra il limite LP di Delsarte e il limite LP di tipo Rapporto:

• Caso Metrica di Rango ($t=1$): Dimostrano che per i grafi delle forme bilineari (pura metrica di rango), l'ottimo dell'LP di Delsarte è esattamente uguale all'ottimo dell'LP di tipo Rapporto. Entrambi sono uguali al limite di Singleton $q^{m(n-d+1)}$.
• Caso di Hamming ($n_i=m_i=1$): Dimostrano che per i grafi di Hamming, i due limiti sono equivalenti sotto condizioni specifiche (ad esempio, quando $q \geq \max\{d, t-d+2\}$). Forniscono anche controesempi specifici (ad esempio, codici di Hamming binari) dove i limiti sono uguali ma strettamente inferiori al limite di Singleton, dimostrando che i limiti sono stretti in quei casi specifici.

C. Risultati di Non-Esistenza per Codici Estremali

Utilizzando i limiti appena derivati e raffinati, il lavoro dimostra la non-esistenza di certi codici ottimali:

• Codici MSRD: Codici che raggiungono il limite di Singleton. Gli autori mostrano che per parametri specifici (ad esempio $m=n=(2, \dots, 2)$ con $t \geq q-1$ e $d=3$), il limite di tipo Rapporto è strettamente inferiore al limite di Singleton, dimostrando che i codici MSRD non esistono in questi regimi.
• Codici Perfetti: Codici che raggiungono il limite del riempimento della sfera con uguaglianza.
  • Derivano condizioni esplicite che coinvolgono il volume delle sfere nella metrica somma-rango dove i codici perfetti non possono esistere.
  • Utilizzano argomenti di congruenza (mod $p$) per escludere codici perfetti additivi.
  • Mostrano che per $d=3$, il limite di tipo Rapporto spesso supera strettamente il limite del riempimento della sfera, dimostrando così la non-esistenza di codici perfetti per parametri dove $t \not\equiv 1 \pmod q$.

4. Risultati Chiave

1. Limiti Superiori più Stretti: Il nuovo limite SDP fornisce i limiti superiori più stretti noti per i codici somma-rango in molti scenari testati, superando l'LP di Delsarte.
2. Unificazione Teorica: La dimostrazione dell'equivalenza tra i limiti di Delsarte e di tipo Rapporto nel caso della metrica di rango unifica due approcci precedentemente distinti, mostrando che producono lo stesso limite strutturale.
3. Teoremi di Non-Esistenza:
   • Teorema 5.2/5.3: I codici MSRD con $d=3$ non esistono per $m=n=(2, \dots, 2)$ quando $t \geq q-1$.
   • Teorema 5.7/5.9: I codici perfetti con $d=3$ non esistono negli spazi con $m=(m, 1, \dots, 1)$ se $t \not\equiv 1 \pmod q$.
   • Teorema 5.10/5.11: I codici perfetti con $d=3$ non esistono negli spazi con $m=n=(2, \dots, 2)$ se $t(q+1) \not\equiv 1 \pmod{q^2}$.

5. Significato

• Avanzamento Metodologico: Questa è la prima applicazione di limiti SDP di tipo Schrijver alla metrica somma-rango. Dimostra che sono necessarie tecniche di ottimizzazione oltre l'LP classico per catturare efficacemente la natura "ibrida" della metrica somma-rango.
• Risoluzione di Questioni Aperte: Il lavoro risolve questioni riguardanti la relazione tra diversi limiti spettrali e LP nell'ambito somma-rango, chiarificando quando sono equivalenti e quando divergono.
• Impatto Pratico: Dimostrando la non-esistenza di codici perfetti e MSRD in specifici regimi di parametri, il lavoro guida i ricercatori lontano da ricerche inutili per costruzioni ottimali in quelle aree e suggerisce che i limiti noti sono probabilmente i veri limiti.
• Direzioni Future: Il lavoro evidenzia il potenziale della riduzione della simmetria nell'SDP per gestire parametri più grandi e suggerisce che il divario tra diversi limiti nell'impostazione generale somma-rango merita ulteriori indagini teoriche.

In sintesi, il lavoro avanza significativamente la comprensione dei codici nella metrica somma-rango introducendo potenti nuovi strumenti di ottimizzazione (SDP), unificando i metodi spettrali esistenti e fornendo dimostrazioni definitive di non-esistenza per codici ottimali in casi precedentemente irrisolti.