A dual linear programming bound for sphere packing in dimension 36

Resumo Técnico: Um Limite de Programação Linear Dual para Empacotamento de Esferas na Dimensão 36

Enunciado do Problema
O artigo aborda o problema do empacotamento de esferas na dimensão $d=36$, focando especificamente no limite de programação linear (LP) de Cohn–Elkies. Embora o limite de LP seja conhecido por ser agudo (sharp) nas dimensões 8 e 24, sua agudeza permanece uma questão em aberto em todas as outras dimensões. O autor investiga se o limite de Cohn–Elkies, denotado por $\delta_{LP}(d)$, pode certificar a otimalidade do melhor empacotamento atualmente conhecido, $\delta^*(d)$. Na dimensão 36, o melhor empacotamento conhecido é a configuração de Kschischang–Pasupathy com uma densidade central de $2^{18}/3^{10}$. O objetivo é construir um "ponto dual-viável" (uma função auxiliar específica) que resulte em um limite inferior para $\delta_{LP}(36)$ estritamente maior que a densidade do empacotamento de Kschischang–Pasupathy. Se bem-sucedido, isso prova que nenhuma função de Cohn–Elkies pode certificar o empacotamento conhecido como ótimo.

Metodologia
A construção segue o método de Cohn e Triantafillou, utilizando o espaço das formas modulares de peso 18 para o subgrupo de congruência $\Gamma_0(24)$. O núcleo do método envolve encontrar um par de formas modulares $(g, \tilde{g})$ de peso $k=18$ (onde $k=d/2$) que satisfaçam restrições de coeficientes específicas para gerar uma distribuição válida para o limite de LP.

O artigo detalha duas inovações metodológicas críticas necessárias para resolver este problema na dimensão 36, onde métodos anteriores (bem-sucedidos em dimensões até 32) enfrentaram obstáculos numéricos e teóricos:

1. Geração de Restrições (Formulação de Corte de Plano):
   Uma relaxação de programação linear ingênua, impondo a não-negatividade dos coeficientes apenas até um $n$ finito, produziu um ótimo que se tornava negativo imediatamente após o intervalo imposto (especificamente para $n \equiv 3, 9, 15, 21 \pmod{24}$). Inversamente, um problema totalmente restringido com centenas de linhas era numericamente singular para solvers de ponto flutuante e grande demais para métodos simplex densos exatos.

   • Solução: O autor emprega uma abordagem de geração de restrições. Um LP racional exato é resolvido em um pequeno conjunto de trabalho. Linhas violadas (onde os coeficientes são negativos) são identificadas exatamente, adicionadas ao conjunto de restrições e o LP é resolvido novamente. Na dimensão 36, este processo convergiu em uma única rodada, produzindo um vértice racional exato cujas expansões $q$ permaneceram não-negativas muito além do intervalo imposto.

2. Constante de Deligne Sensível ao Levantamento (Lift-Aware):
   Provar a "positividade eventual" (que os coeficientes permanecem não-negativos para todo $n > n_0$) requer limitar a parte cuspidal das formas modulares. O limite padrão de Deligne utiliza uma norma $\ell_1$ das coordenadas no basis de levantamento de novas formas (newform-lift).

   • Solução: O autor identifica que a norma $\ell_1$ ingênua é "perdedora" (lossy) neste contexto porque o certificado é dominado por um único levantamento de oldform profundo (a newform de nível um deslocada por $e=24$). A constante ingênua falhou na verificação por uma margem mínima. O autor introduz uma constante "sensível ao levantamento", $C_w = \sum_{f,e} |\lambda_{f,e}| e^{-(k-1)/2}$, que suprime a contribuição de levantamentos profundos pelo fator $e^{-(k-1)/2}$. Esta constante refinada é dez ordens de magnitude menor, permitindo que a verificação fosse concluída com uma margem significativa.

Principais Resultados
O artigo constrói um ponto dual-viável explícito $(g, \tilde{g})$ e deriva os seguintes resultados:

• Limite Dual: O certificado construído estabelece que o limite de programação linear de Cohn–Elkies na dimensão 36 satisfaz:
  $$\delta_{LP}(36) \geq 146.1036\dots = 32.9104\dots \times \frac{2^{18}}{3^{10}}$$
• Comparação com o Empacotamento Conhecido: O limite inferior construído excede a densidade do empacotamento de Kschischang–Pasupathy ($2^{18}/3^{10}$) por um fator de pelo menos 32.91.
• Implicação: Consequentemente, nenhuma função auxiliar de Cohn–Elkies pode certificar o empacotamento de Kschischang–Pasupathy como ótimo na dimensão 36. O limite de LP é estritamente superior à densidade do melhor empacotamento conhecido.
• Rigor da Verificação: O certificado é exato. O ponto dual é um vetor racional com numeradores de aproximadamente 128 dígitos. A não-negatividade dos coeficientes é verificada por aritmética exata até $n=800$. Para $n > 800$, a positividade eventual é provada usando a constante de Deligne sensível ao levantamento e limites de cauda explícitos, com todas as constantes certificadas via aritmética de intervalo de arredondamento externo.

Significância e Alegações
O artigo alega várias contribuições significativas para o campo do empacotamento de esferas e formas modulares:

1. Extensão de Limites Conhecidos: Este é o primeiro limite dual construído em qualquer dimensão acima de 32. Ele estende a tabela existente de Cohn–Triantafillou (que cobria $d=12, 16, 20, 28, 32$), Li ($3 \le d \le 13$) e de Courcy-Ireland et al. ($d=6$).
2. Avanço Metodológico: O artigo destaca que a formulação de geração de restrições é essencial para alcançar o ótimo seguro de cauda em dimensões altas onde o LP denso exato é intratável. Além disso, demonstra que a constante de Deligne sensível ao levantamento é necessária para a verificação rigorosa em casos dominados por levantamentos de oldform profundos, um cenário onde os limites padrão falham.
3. Natureza do Resultado: O autor observa que, embora a afirmação dual seja forte (a lacuna é grande), a "não-agudeza estrita" (provar $\delta_{LP}(36) > \delta_{max}(36)$ onde $\delta_{max}$ é a verdadeira densidade ótima) permanece fora de alcance. A não-agudeza estrita exigiria um limite superior independente abaixo de $32.91 \times \delta^*$, um limiar atualmente inalcançável pelas técnicas de limite de três pontos existentes.
4. Reprodutibilidade: O trabalho enfatiza que a verificação depende unicamente de álgebra linear racional exata e aritmética de intervalo, independente de sistemas de álgebra computacional com maquinaria de formas modulares. Todo o código, recibos e dados exatos são fornecidos como arquivos auxiliares.

O artigo conclui que a dimensão 36 representa um regime qualitativamente diferente onde o empacotamento recorde conhecido é fraco em relação ao limite de LP, tornando a afirmação dual forte, mas a questão da otimalidade estrita mais difícil de resolver.