A dual linear programming bound for sphere packing in dimension 36

Sintesi Tecnica: Un limite di programmazione lineare duale per l'impacchettamento di sfere in dimensione 36

Enunciato del problema
Il saggio affronta il problema dell'impacchettamento di sfere nella dimensione $d=36$, concentrandosi specificamente sul limite di programmazione lineare (LP) di Cohn–Elkies. Sebbene il limite LP sia noto per essere stretto nelle dimensioni 8 e 24, la sua capacità di essere stretto rimane una questione aperta in tutte le altre dimensioni. L'autore indaga se il limite di Cohn–Elkies, denotato con $\delta_{LP}(d)$, possa certificare l'ottimalità del miglior impacchettamento attualmente noto, $\delta^*(d)$. Nella dimensione 36, il miglior impacchettamento noto è la configurazione di Kschischang–Pasupathy con una densità centrale di $2^{18}/3^{10}$. L'obiettivo è costruire un "punto dualmente ammissibile" (una specifica funzione ausiliaria) che fornisca un limite inferiore per $\delta_{LP}(36)$ strettamente maggiore della densità dell'impacchettamento di Kschischang–Pasupathy. Se l'operazione ha successo, ciò prova che nessuna funzione di Cohn–Elkies può certificare l'ottimalità dell'impacchettamento noto.

Metodologia
La costruzione segue il metodo di Cohn e Triantafillou, utilizzando lo spazio delle forme modulari di peso 18 per il sottogruppo congruente $\Gamma_0(24)$. Il nucleo del metodo consiste nel trovare una coppia di forme modulari $(g, \tilde{g})$ di peso $k=18$ (dove $k=d/2$) che soddisfino specifici vincoli sui coefficienti per generare una distribuzione valida per il limite LP.

Il saggio dettaglia due innovazioni metodologiche critiche necessarie per risolvere questo problema nella dimensione 36, dove i metodi precedenti (riusciti fino alla dimensione 32) hanno incontrato ostacoli numerici e teorici:

1. Generazione dei vincoli (formulazione cutting-plane):
   Un rilassamento ingenuo della programmazione lineare, imponendo la non negatività dei coefficienti solo fino a un $n$ finito, ha prodotto un ottimo che diventava immediatamente negativo subito dopo l'intervallo imposto (specificamente per $n \equiv 3, 9, 15, 21 \pmod{24}$). Viceversa, un problema completamente vincolato con centinaia di righe era numericamente singolare per i solver a virgola mobile e troppo grande per i metodi simplex densi esatti.

   • Soluzione: L'autore impiega un approccio di generazione dei vincoli. Viene risolta una LP razionale esatta su un piccolo insieme di lavoro. I vincoli violati (dove i coefficienti sono negativi) vengono identificati esattamente, aggiunti all'insieme dei vincoli e la LP viene risolta nuovamente. Nella dimensione 36, questo processo è confluito in un unico round, producendo un vertice razionale esatto le cui espansioni in $q$ rimangono non negative ben oltre l'intervallo imposto.

2. Costante di Deligne "consapevole del lift" (Lift-Aware):
   Dimostrare la "positività eventuale" (che i coefficienti rimangano non negativi per ogni $n > n_0$) richiede il controllo della parte cuspidale delle forme modulari. Il limite standard di Deligne utilizza una norma $\ell_1$ delle coordinate nella base del lift delle nuove forme.

   • Soluzione: L'autore identifica che la norma $\ell_1$ ingenua è "dispersiva" in questo contesto perché il certificato è dominato da un singolo lift di un oldform profondo (la nuova forma di livello uno traslata di $e=24$). La costante ingenua ha fallito la soglia di verifica per un margine minimo. L'autore introduce una costante "consapevole del lift", $C_w = \sum_{f,e} |\lambda_{f,e}| e^{-(k-1)/2}$, che sopprime il contributo dei lift profondi tramite il fattore $e^{-(k-1)/2}$. Questa costante raffinata è più piccola di dieci ordini di grandezza, permettendo alla verifica di chiudersi con un margine significativo.

Risultati Chiave
L'autore costruisce un punto dualmente ammissibile esplicito $(g, \tilde{g})$ e deriva i seguenti risultati:

• Limite Duale: Il certificato costruito stabilisce che il limite di programmazione lineare di Cohn–Elkies nella dimensione 36 soddisfa:
  $$\delta_{LP}(36) \geq 146.1036\dots = 32.9104\dots \times \frac{2^{18}}{3^{10}}$$
• Confronto con l'Impacchettamento Noto: Il limite inferiore costruito supera la densità dell'impacchettamento di Kschischang–Pasupathy ($2^{18}/3^{10}$) di un fattore di almeno 32.91.
• Implicazione: Di conseguenza, nessuna funzione ausiliaria di Cohn–Elkies può certificare l'impacchettamento di Kschischang–Pasupathy come ottimale nella dimensione 36. Il limite LP è strettamente superiore alla densità dell'impacchettamento noto.
• Rigore della Verifica: Il certificato è esatto. Il punto duale è un vettore razionale con numeratori di circa 128 cifre. La non negatività dei coefficienti è verificata tramite aritmetica esatta fino a $n=800$. Per $n > 800$, la positività eventuale è provata utilizzando la costante di Deligne consapevole del lift e limiti di coda espliciti, con tutti i costanti certificati tramite aritmetica di intervalli con arrotondamento esterno.

Significato e Rivendicazioni
Il saggio rivendica diversi contributi significativi nel campo dell'impacchettamento di sfere e delle forme modulari:

1. Estensione dei Limiti Noti: Questo è il primo limite duale costruito in qualsiasi dimensione superiore a 32. Estende la tabella esistente di Cohn–Triantafillou (che copriva $d=12, 16, 20, 28, 32$), Li ($3 \le d \le 13$) e de Courcy-Ireland et al. ($d=6$).
2. Avanzamento Metodologico: Il saggio evidenzia come la formulazione di generazione dei vincoli sia essenziale per raggiungere l'ottimo sicuro rispetto alla coda in dimensioni elevate dove la LP densa esatta è intrattabile. Inoltre, dimostra che la costante di Deligne consapevole del lift è necessaria per la verifica rigorosa in casi dominati da lift di oldform profondi, uno scenario in cui i limiti standard falliscono.
3. Natura del Risultato: L'autore nota che, sebbene l'enunciato duale sia forte (il divario è ampio), la "non-strettezza rigorosa" (dimostrare $\delta_{LP}(36) > \delta_{max}(36)$ dove $\delta_{max}$ è la vera densità ottimale) rimane fuori portata. La non-strettezza rigorosa richiederebbe un limite superiore indipendente inferiore a $32.91 \times \delta^*$, una soglia attualmente irraggiungibile dalle tecniche di limite a tre punti esistenti.
4. Riproducibilità: Il lavoro sottolinea che la verifica si basa esclusivamente sull'algebra lineare razionale esatta e sull'aritmetica degli intervalli, indipendentemente dai sistemi di algebra computazionale con meccanismi di forme modulari. Tutto il codice, le ricevute e i dati esatti sono forniti come file accessori.

Il saggio conclude che la dimensione 36 rappresenta un regime qualitativamente diverso in cui l'impacchettamento record noto è debole rispetto al limite LP, rendendo l'enunciato duale forte ma la questione dell'ottimalità rigorosa più difficile da risolvere.