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

1. Formulação do Problema

O artigo aborda o problema fundamental na teoria de códigos de determinar o tamanho máximo, denotado por $A(q, n, m, d)$, de um código com uma distância mínima prescrita $d$ dentro da métrica soma-rank.

• Contexto: A métrica soma-rank generaliza tanto a métrica de Hamming (erros símbolo a símbolo) quanto a métrica de Rank (erros do tipo rank). É crucial para aplicações modernas como codificação de rede em múltiplos disparos, armazenamento distribuído e codificação espaço-tempo.
• Desafio: Embora existam limites para as métricas de Hamming e Rank, a natureza híbrida da métrica soma-rank cria fenômenos combinatórios e algébricos únicos. Limites existentes (por exemplo, Singleton, Hamming, Plotkin e o clássico Delsarte LP) frequentemente falham em fornecer limites superiores apertados ou falham em descartar a existência de códigos ótimos (como códigos de Distância Máxima Soma-Rank (MSRD) ou códigos perfeitos) em regimes específicos de parâmetros.
• Objetivo: Derivar limites superiores mais precisos utilizando teoria espectral de grafos e técnicas de otimização (Programação Linear e Programação Semidefinida) e usar esses limites para provar resultados de não existência para códigos extremos.

2. Metodologia

Os autores empregam uma abordagem multifacetada combinando teoria algébrica de grafos, otimização combinatória e experimentos computacionais:

• Estrutura Teórica de Grafos: Eles associam o espaço da métrica soma-rank $F_q^{n \times m}$ a um grafo $\Gamma$ onde os vértices são palavras-código e as arestas representam distância 1. O problema de encontrar o tamanho máximo do código é equivalente a limitar o número de independência deste grafo.
• Métodos Espectrais: Eles utilizam os autovalores da matriz de adjacência do grafo da métrica soma-rank para derivar limites.
  • Limite do Tipo Razão: Um limite espectral baseado nos autovalores do grafo.
  • Número de Lovász Theta: Um limite de teoria algébrica de grafos.
• Programação Linear (LP):
  • LP de Delsarte: Baseado no esquema de associação da métrica soma-rank, utilizando a segunda matriz de autovalores para restringir a distribuição de distâncias.
  • LP do Tipo Razão: Uma formulação LP derivada do Limite do Tipo Razão usando polinômios menores.
• Programação Semidefinida (SDP):
  • SDP do Tipo Schrijver: Os autores introduzem um novo limite SDP que estende o quadro de Delsarte. Enquanto o LP de Delsarte considera distâncias entre pares, este SDP incorpora restrições baseadas em triplos de palavras-código (especificamente triplos contendo o vetor nulo), aproveitando a semidefinição positiva de uma matriz que codifica esses triplos.
• Verificação Computacional: Os autores utilizam a linguagem de programação Julia com o pacote de redução de simetria de Jordan para calcular esses limites para vários parâmetros, comparando-os com limites teóricos conhecidos.

3. Contribuições Principais

A. Um Novo Limite de Programação Semidefinida (SDP)

O artigo introduz um limite SDP do tipo Schrijver para a métrica soma-rank.

• Mecanismo: Ele fortalece o LP de Delsarte de pares impondo restrições a triplos de palavras-código.
• Desempenho: Experimentos computacionais mostram que este limite SDP melhora estritamente os melhores limites existentes (incluindo LP de Delsarte, do Tipo Razão e limites clássicos de codificação) em vários regimes de parâmetros.
• Hierarquia: O artigo estabelece a hierarquia: $A(q, n, m, d) \leq \text{SDP} \leq \text{LP de Delsarte}$.

B. Equivalência de Limites LP em Regimes Extremos

Os autores realizam uma comparação rigorosa entre o limite LP de Delsarte e o limite LP do Tipo Razão:

• Caso de Métrica de Rank ($t=1$): Eles provam que, para grafos de formas bilineares (métrica de rank pura), o ótimo do LP de Delsarte é exatamente igual ao ótimo do LP do Tipo Razão. Ambos são iguais ao limite de Singleton $q^{m(n-d+1)}$.
• Caso de Hamming ($n_i=m_i=1$): Eles provam que, para grafos de Hamming, os dois limites são equivalentes sob condições específicas (por exemplo, quando $q \geq \max\{d, t-d+2\}$). Eles também fornecem contra-exemplos específicos (por exemplo, códigos de Hamming binários) onde os limites são iguais, mas estritamente menores que o limite de Singleton, demonstrando que os limites são apertados nesses casos específicos.

C. Resultados de Não Existência para Códigos Extremos

Usando os limites recém-derivados e refinados, o artigo prova a não existência de certos códigos ótimos:

• Códigos MSRD: Códigos que atingem o limite de Singleton. Os autores mostram que, para parâmetros específicos (por exemplo, $m=n=(2, \dots, 2)$ com $t \geq q-1$ e $d=3$), o limite do Tipo Razão é estritamente menor que o limite de Singleton, provando que códigos MSRD não existem nesses regimes.
• Códigos Perfeitos: Códigos que atingem o limite de Empacotamento de Esferas com igualdade.
  • Eles derivam condições explícitas envolvendo o volume de bolas na métrica soma-rank onde códigos perfeitos não podem existir.
  • Eles usam argumentos de congruência (mod $p$) para descartar códigos perfeitos aditivos.
  • Eles mostram que, para $d=3$, o limite do Tipo Razão frequentemente supera estritamente o limite de Empacotamento de Esferas, provando assim a não existência de códigos perfeitos para parâmetros onde $t \not\equiv 1 \pmod q$.

4. Resultados Chave

1. Limites Superiores Mais Apertados: O novo limite SDP fornece os limites superiores mais apertados conhecidos para códigos soma-rank em muitos cenários testados, superando o LP de Delsarte.
2. Unificação Teórica: A prova de equivalência entre os limites de Delsarte e do Tipo Razão no caso de métrica de rank unifica duas abordagens anteriormente distintas, mostrando que elas produzem o mesmo limite estrutural.
3. Teoremas de Não Existência:
   • Teorema 5.2/5.3: Códigos MSRD com $d=3$ não existem para $m=n=(2, \dots, 2)$ quando $t \geq q-1$.
   • Teorema 5.7/5.9: Códigos perfeitos com $d=3$ não existem em espaços com $m=(m, 1, \dots, 1)$ se $t \not\equiv 1 \pmod q$.
   • Teorema 5.10/5.11: Códigos perfeitos com $d=3$ não existem em espaços com $m=n=(2, \dots, 2)$ se $t(q+1) \not\equiv 1 \pmod{q^2}$.

5. Significado

• Avance Metodológico: Esta é a primeira aplicação de limites SDP do tipo Schrijver à métrica soma-rank. Demonstra que técnicas de otimização além do LP clássico são necessárias para capturar efetivamente a natureza "híbrida" da métrica soma-rank.
• Resolução de Questões Abertas: O artigo resolve questões sobre a relação entre diferentes limites espectrais e LP no cenário soma-rank, esclarecendo quando são equivalentes e quando divergem.
• Impacto Prático: Ao provar a não existência de códigos perfeitos e MSRD em regimes específicos de parâmetros, o artigo orienta os pesquisadores a evitar buscas fúteis por construções ótimas nessas áreas e sugere que os limites conhecidos são provavelmente os limites verdadeiros.
• Direções Futuras: O trabalho destaca o potencial da redução de simetria em SDP para lidar com parâmetros maiores e sugere que a lacuna entre diferentes limites no cenário geral soma-rank merece investigação teórica adicional.

Em resumo, o artigo avança significativamente a compreensão dos códigos de métrica soma-rank introduzindo poderosas novas ferramentas de otimização (SDP), unificando métodos espectrais existentes e fornecendo provas definitivas de não existência para códigos ótimos em casos anteriormente não resolvidos.