Semidefinite lower bounds for covering codes

Definição do Problema
O artigo aborda o problema de determinar $K_q(n, r)$, definido como o tamanho mínimo de um código de cobertura $q$-ário de comprimento de palavra $n$ e raio de cobertura $r$. Um conjunto de palavras-chave $C \subseteq \{0, \dots, q-1\}^n$ tem raio de cobertura $r$ se a união das bolas de Hamming de raio $r$ centradas nas palavras-chave cobre todo o espaço de Hamming. Uma instância específica deste problema, $K_3(n, 1)$, é conhecida como o "problema do futebol" (football pool problem), que busca o número mínimo de previsões necessárias para garantir, no máximo, um erro em $n$ partidas de futebol. Embora os limites superiores sejam tipicamente estabelecidos pela construção de códigos explícitos, este artigo foca na derivação de limites inferiores melhorados para $K_q(n, r)$.

Metodologia
Os autores baseiam-se no trabalho de Gijswijt (2005), que introduziu um limite inferior de programação semidefinida (SDP) para códigos de cobertura usando cortes de matrizes. A metodologia apresentada neste artigo fortalece esse limite através de três avanços técnicos primários:

1. Restrições da Hierarquia de Lasserre: Os autores introduzem novas restrições semidefinidas inspiradas na hierarquia de Lasserre para programas 0-1. Especificamente, eles utilizam o segundo nível desta hierarquia, que envolve a análise da distribuição de trios de palavras-chave. Isso leva à construção de uma matriz $N$ derivada do vetor de incidência do código, sujeita a desigualdades de cobertura da forma $\sum \lambda_i A_i(u) \ge \beta$.
2. Redução de Simetria via Álgebras de Terwilliger: Para tornar a SDP resultante computacionalmente tratável, os autores empregam redução de simetria. Eles utilizam a álgebra de Terwilliger do esquema de Hamming (tanto para casos binários quanto não binários). Ao identificar as órbitas de pares e trios de palavras-chave sob a ação do grupo de isometria $Aut(q, n)$ (e seu subgrupo estabilizador $Aut_0(q, n)$), eles reduzem a dimensionalidade das variáveis de matriz.
   • Para o caso binário ($q=2$), a álgebra $A_{2,n}$ é diagonalizada em blocos usando um $\ast$-isomorfismo $\phi$ que a mapeia para uma soma direta de blocos de matrizes menores, reduzindo a complexidade de $O(2^n)$ para $O(n^3)$ variáveis.
   • Para o caso não binário ($q \ge 3$), uma diagonalização em blocos semelhante é aplicada à álgebra $A_{q,n}$, reduzindo a complexidade para $O(n^4)$ variáveis.
3. Função Objetivo Aperfeiçoada: O artigo propõe uma função objetivo mais poderosa. Em vez de minimizar o termo linear padrão relacionado ao tamanho do código, os autores minimizam o traço da variável de matriz correspondente ao terceiro momento do tamanho do código ($|C|^3$). Eles provam que esta função objetivo cúbica produz um limite inferior estritamente mais apertado do que os objetivos lineares ou quadráticos utilizados anteriormente.

Principais Contribuições

• Estrutura Teórica: O artigo estabelece um framework de SDP rigoroso para códigos de cobertura que generaliza os limites de Schrijver para códigos de correção de erros para o problema de cobertura. Ele deriva formalmente as restrições para a matriz $N$ e as matrizes bordadas $R(c, N)$ dentro do contexto da hierarquia de Lasserre.
• Algoritmos de Redução de Simetria: Os autores fornecem fórmulas explícitas para a diagonalização em blocos das álgebras de Terwilliger relevantes para os esquemas de Hamming binários e não binários. Isso inclui coeficientes combinatórios detalhados ($\eta$ e $\alpha$) necessários para traduzir as desigualdades de corte de matriz e as restrições de Lasserre para o espaço de variáveis reduzido.
• Implementação Computacional: Os autores implementaram esses limites usando aritmética de alta precisão (512-bit BigFloats) via linguagem de programação Julia e o solver SDPA-GMP. Eles desenvolveram um código independente para validar a geração das SDPs.

Resultos
Os autores apresentam novos limites inferiores para $K_q(n, r)$ em uma ampla gama de parâmetros ($q, n, r$). Esses resultados estão compilados nas Tabelas 1, 2 e 3, cobrindo os casos binário ($q=2$), ternário ($q=3$) e quaternário/quinário ($q=4, 5$).

• Caso Binário: Os novos limites melhoram os limites inferiores conhecidos anteriormente para vários valores de $n$ e $r$ (ex: $K_2(13, 1)$, $K_2(21, 1)$, $K_2(13, 2)$). Os autores observam que, embora tenham inicialmente encontrado limites melhorados para $K_2(18, 1)$ e $K_2(30, 1)$, esses valores específicos foram posteriormente superados por Wu e Chen (2026).
• Caso Não Binário: Melhorias significativas são relatadas para códigos ternários (problema do futebol), como $K_3(13, 3)$ e $K_3(14, 4)$, bem como para $q=4$ e $q=5$.
• Escala Computacional: O artigo reporta o número de variáveis e tamanhos de blocos para as SDPs com redução de simetria. Por exemplo, para $n=32$ no caso binário, a SDP reduzida envolve 1.239 variáveis com uma soma de quadrados dos tamanhos dos blocos de 6.545. Os tempos de solução variaram de segundos a vários dias, dependendo do tamanho da instância e do número de coeficientes não nulos nas restrições de desigualdade.

Significância
O artigo afirma que as técnicas propostas levam a "limites inferiores mais agudos" que estabelecem novos recordes para uma ampla gama de parâmetros de códigos de cobertura. Ao estender a abordagem da hierarquia de Lasserre para códigos de cobertura e utilizar efetivamente a redução de simetria, os autores demonstram que o hiato entre os limites inferiores e superiores conhecidos pode ser estreitado. O trabalho fornece um método sistemático para computar esses limites, oferecendo uma alternativa mais poderosa aos limites de programação linear e às abordagens de SDP anteriores que não exploravam totalmente as restrições de distribuição de trios ou a otimização da função objetivo específica. Os resultados servem como benchmarks atualizados para o campo dos códigos de cobertura e o problema do futebol.