A dual linear programming bound for sphere packing in dimension 36

Technische Samenvatting: Een duale lineaire programmeringsgrens voor bolverpakking in dimensie 36

Probleemstelling
Het artikel behandelt het bolverpakkingsprobleem in dimensie $d=36$, met een specifieke focus op de Cohn–Elkies lineaire programmeringsgrens (LP-grens). Hoewel de LP-grens bekend staat als scherp in dimensies 8 en 24, blijft de scherpte een open vraag in alle andere dimensies. De auteur onderzoekt of de Cohn–Elkies-grens, aangeduid als $\delta_{LP}(d)$, de optimaliteit van de best bekende verpakking, $\delta^*(d)$, kan certificeren. In dimensie 36 is de best bekende verpakking de Kschischang–Pasupathy-configuratie met een centrumdichtheid van $2^{18}/3^{10}$. Het doel is om een "duaal-voldoende punt" (een specifieke hulpfunctie) te construeren dat een ondergrens voor $\delta_{LP}(36)$ oplevert die strikt groter is dan de dichtheid van de Kschischang–Pasupathy-verpakking. Indien succesvol, bewijst dit dat geen enkele Cohn–Elkies-functie de bekende verpakking als optimaal kan certificeren.

Methodologie
De constructie volgt de methode van Cohn en Triantafillou, waarbij gebruik wordt gemaakt van de ruimte van gewichts-18 modulaire vormen voor de congruentie-subgroep $\Gamma_0(24)$. De kern van de methode bestaat uit het vinden van een paar modulaire vormen $(g, \tilde{g})$ van gewicht $k=18$ (waarbij $k=d/2$) die aan specifieke coëfficiënt-beperkingen voldoen om een geldige distributie voor de LP-grens te genereren.

Het artikel beschrijft twee cruciale methodologische innovaties die vereist zijn om dit probleem in dimensie 36 op te lossen, waar eerdere methoden (die succesvol waren in dimensies tot en met 32) tegen numerieke en theoretische obstakels aanliepen:

1. Constraint Generation (Snijvlak-formulering):
   Een naïeve lineaire programmeringsrelaxatie, die enkel de niet-negativiteit van coëfficiënten afdwong tot een eindig $n$, produceerde een optimum dat direct na het afgedwongen bereik negatief werd (specifiek voor $n \equiv 3, 9, 15, 21 \pmod{24}$). Omgekeerd was een volledig beperkt probleem met honderden rijen numeriek singulier voor floating-point solvers en te groot voor exacte dichte simplex-methoden.

   • Oplossing: De auteur hanteert een constraint-generation benadering. Een exacte rationale LP wordt opgelost op een kleine werkset. Overtreden rijen (waar coëfficiënten negatief zijn) worden exact geïdentificeerd, toegevoegd aan de beperkingsset, waarna de LP opnieuw wordt opgelost. In dimensie 36 convergeerde dit proces in één ronde, wat een exacte rationale vertex opleverde waarvan de $q$-expansies ver buiten het afgedwongen bereik niet-negatief bleven.

2. Lift-bewuste Deligne-constante:
   Het bewijzen van "uiteindelijke positiviteit" (dat coëfficiënten voor alle $n > n_0$ niet-negatief blijven) vereist het begrenzen van het cuspidale deel van de modulaire vormen. De standaard Deligne-grens gebruikt een $\ell_1$-norm van de coördinaten in de nieuwe vorm-liftbasis.

   • Oplossing: De auteur stelt vast dat de naïeve $\ell_1$-norm in deze context "verlieslatend" is omdat het certificaat wordt gedomineerd door een enkele diepe oldform-lift (de level-één nieuwe vorm verschoven met $e=24$). De naïeve constante slaagde marginaal niet voor de verificatiedrempel. De auteur introduceert een "lift-bewuste" constante, $C_w = \sum_{f,e} |\lambda_{f,e}| e^{-(k-1)/2}$, die de bijdrage van diepe lifts onderdrukt door de factor $e^{-(k-1)/2}$. Deze verfijnde constante is tien ordes van grootte kleiner, waardoor de verificatie met een aanzienlijke marge kan worden afgerond.

Belangrijkste Resultaten
Het artikel construeert een expliciet duaal-voldoende punt $(g, \tilde{g})$ en leidt de volgende resultaten af:

• Duale Grens: Het geconstrueerde certificaat stelt vast dat de Cohn–Elkies lineaire programmeringsgrens in dimensie 36 voldoet aan:
  $$\delta_{LP}(36) \geq 146.1036\dots = 32.9104\dots \times \frac{2^{18}}{3^{10}}$$
• Vergelijking met Bekende Verpakking: Deze ondergrens overschrijdt de dichtheid van de Kschischang–Pasupathy-verpakking ($2^{18}/3^{10}$) met een factor van ten minste 32.91.
• Implicatie: Bijgevolg kan geen enkele Cohn–Elkies hulpfunctie de Kschischang–Pasupathy-verpakking als optimaal certificeren in dimensie 36. De LP-grens is strikt hoger dan de best bekende verpakkingsdichtheid.
• Rigoreuze Verificatie: Het certificaat is exact. Het duale punt is een rationale vector met $\approx 128$-cijferige tellers. De niet-negativiteit van de coëfficiënten wordt exact geverifieerd tot $n=800$. Voor $n > 800$ wordt de uiteindelijke positiviteit bewezen met behulp van de lift-bewuste Deligne-constante en expliciete tail bounds, waarbij alle constanten via outward-rounded intervalrekening zijn gecertificeerd.

Betekenis en Claims
Het artikel claimt verschillende significante bijdragen aan het veld van bolverpakking en modulaire vormen:

1. Uitbreiding van Bekende Grenzen: Dit is de eerste duale grens die is geconstrueerd in een dimensie boven de 32. Het breidt de bestaande tabel van Cohn-Triantafillou (die $d=12, 16, 20, 28, 32$ besloeg), Li ($3 \le d \le 13$) en de Courcy-Ireland et al. ($d=6$) uit.
2. Methodologische Vooruitgang: Het artikel benadrukt dat de constraint-generation formulering essentieel is om de tail-safe optimum te bereiken in hoge dimensies waar exacte dichte LP onhandelbaar is. Bovendien toont het aan dat de lift-bewuste Deligne-constante noodzakelijk is voor rigoureuze verificatie in gevallen die gedomineerd worden door diepe oldform lifts, een scenario waarin standaard grenzen falen.
3. Aard van het Resultaat: De auteur merkt op dat hoewel de duale stelling sterk is (het gat is groot), de "strikte niet-scherpte" (het bewijzen van $\delta_{LP}(36) > \delta_{max}(36)$ waarbij $\delta_{max}$ de ware optimale dichtheid is) buiten bereik blijft. Strikte niet-scherpte zou een onafhankelijke bovengrens vereisen die onder $32.91 \times \delta^*$ ligt, een drempel die momenteel onbereikbaar is met bestaande drie-punts grenstechnieken.
4. Reproduceerbaarheid: Het werk benadrukt dat de verificatie uitsluitend rust op exacte rationale lineaire algebra en intervalrekening, onafhankelijk van computer algebra systemen met modulaire vorm-mechanismen. Alle code, bewijsstukken en exacte data worden als bijlagen geleverd.

Het artikel concludeert dat dimensie 36 een kwalitatief ander regime vertegenwoordigt waar de bekende recordverpakking zwak is ten opzichte van de LP-grens, waardoor de duale stelling sterk is maar de vraag naar strikte optimaliteit moeilijker te beslechten is.