A dual linear programming bound for sphere packing in dimension 36

Résumé Technique : Une borne de programmation linéaire duale pour le compactage de sphères en dimension 36

Énoncé du Problème
L'article traite du problème du compactage de sphères en dimension $d=36$, en se concentrant spécifiquement sur la borne de programmation linéaire (LP) de Cohn–Elkies. Bien que la borne LP soit connue pour être exacte dans les dimensions 8 et 24, sa précision reste une question ouverte dans toutes les autres dimensions. L'auteur étudie si la borne de Cohn–Elkies, notée $\delta_{LP}(d)$, peut certifier l'optimalité du meilleur compactage actuellement connu, $\delta^*(d)$. En dimension 36, le meilleur compactage connu est la configuration de Kschischang–Pasupathy avec une densité centrale de $2^{18}/3^{10}$. L'objectif est de construire un « point dual-faisable » (une fonction auxiliaire spécifique) qui produit une borne inférieure pour $\delta_{LP}(36)$ strictement supérieure à la densité du compactage de Kschischang–Pasupathy. En cas de succès, cela prouve qu'aucune fonction de Cohn–Elkies ne peut certifier l'optimalité du compactage connu.

Méthodologie
La construction suit la méthode de Cohn et Triantafillou, utilisant l'espace des formes modulaires de poids 18 pour le sous-groupe congruence $\Gamma_0(24)$. Le cœur de la méthode consiste à trouver une paire de formes modulaires $(g, \tilde{g})$ de poids $k=18$ (où $k=d/2$) qui satisfont des contraintes de coefficients spécifiques pour générer une distribution valide pour la borne LP.

L'article détaille deux innovations méthodologiques critiques nécessaires pour résoudre ce problème en dimension 36, où les méthodes précédentes (réussies jusqu'en dimension 32) se heurtaient à des obstacles numériques et théoriques :

1. Génération de Contraintes (Formulation par Plan de Coupe) :
   Une relaxation de programmation linéaire naïve, imposant la non-négativité des coefficients uniquement jusqu'à un $n$ fini, produisait un optimum qui devenait immédiatement négatif après la plage imposée (spécifiquement pour $n \equiv 3, 9, 15, 21 \pmod{24}$). Inversement, un problème entièrement contraint avec des centaines de lignes était numériquement singulier pour les solveurs en virgule flottante et trop volumineux pour les méthodes simplex denses exactes.

   • Solution : L'auteur emploie une approche de génération de contraintes. Un LP rationnel exact est résolu sur un petit ensemble de travail. Les lignes violées (où les coefficients sont négatifs) sont identifiées exactement, ajoutées à l'ensemble des contraintes, et le LP est résolu à nouveau. En dimension 36, ce processus a convergé en un seul cycle, produisant un sommet rationnel exact dont les développements en $q$ restent non négatifs bien au-delà de la plage imposée.

2. Constante de Deligne Sensible au Levage (Lift-Aware) :
   Prouver la « positivité éventuelle » (que les coefficients restent non négatifs pour tout $n > n_0$) nécessite de borner la partie cuspidale des formes modulaires. La borne de Deligne standard utilise une norme $\ell_1$ des coordonnées dans la base de levage de nouvelles formes (newform-lift).

   • Solution : L'auteur identifie que la norme $\ell_1$ naïve est « perteuse » dans ce contexte car le certificat est dominé par un levage d'anciennes formes profond unique (la nouvelle forme de niveau un décalée par $e=24$). La constante naïve échouait marginalement au seuil de vérification. L'auteur introduit une constante « sensible au levage », $C_w = \sum_{f,e} |\lambda_{f,e}| e^{-(k-1)/2}$, qui supprime la contribution des levages profonds par le facteur $e^{-(k-1)/2}$. Cette constante raffinée est dix ordres de grandeur plus petite, permettant à la vérification de se clore avec une marge significative.

Résultats Clés
L'article construit un point dual-faisable explicite $(g, \tilde{g})$ et dérive les résultats suivants :

• Borne Duale : Le certificat construit établit que la borne de programmation linéaire de Cohn–Elkies en dimension 36 satisfait :
  $$\delta_{LP}(36) \geq 146.1036\dots = 32.9104\dots \times \frac{2^{18}}{3^{10}}$$
• Comparaison avec le Compactage Connu : Cette borne inférieure dépasse la densité du compactage de Kschischang–Pasupathy ($2^{18}/3^{10}$) par un facteur d'au moins 32,91.
• Implication : Par conséquent, aucune fonction auxiliaire de Cohn–Elkies ne peut certifier le compactage de Kschischang–Pasupathy comme optimal en dimension 36. La borne LP est strictement supérieure à la densité du meilleur compactage connu.
• Rigueur de la Vérification : Le certificat est exact. Le point dual est un vecteur rationnel avec des numérateurs d'environ 128 chiffres. La non-négativité des coefficients est vérifiée par arithmétique exacte jusqu'à $n=800$. Pour $n > 800$, la positivité éventuelle est prouvée en utilisant la constante de Deligne sensible au levage et des bornes de queue explicites, avec toutes les constantes certifiées via l'arithmétique d'intervalles par arrondi extérieur.

Signification et Revendications
L'article revendique plusieurs contributions significatives au domaine du compactage de sphères et des formes modulaires :

1. Extension des Bornes Connues : Il s'agit de la première borne duale construite dans une dimension supérieure à 32. Cela étend la table existante de Cohn–Triantafillou (qui couvrait $d=12, 16, 20, 28, 32$), Li ($3 \le d \le 13$), et de Courcy-Ireland et al. ($d=6$).
2. Avancée Méthodologique : Le papier souligne que la formulation par génération de contraintes est essentielle pour atteindre l'optimum sûr de la queue dans les hautes dimensions où le LP dense exact est intraitable. De plus, il démontre que la constante de Deligne sensible au levage est nécessaire pour une vérification rigoureuse dans les cas dominés par des levages d'anciennes formes profonds, un scénario où les bornes standards échouent.
3. Nature du Résultat : L'auteur note que bien que l'énoncé dual soit fort (l'écart est important), la « non-optimalité stricte » (prouver $\delta_{LP}(36) > \delta_{max}(36)$ où $\delta_{max}$ est la véritable densité optimale) reste hors de portée. Une non-optimalité stricte nécessiterait une borne supérieure indépendante en dessous de $32,91 \times \delta^*$, un seuil actuellement inatteignable par les techniques de bornes à trois points existantes.
4. Reproductibilité : L'ouvrage souligne que la vérification repose uniquement sur l'algèbre linéaire rationnelle exacte et l'arithmétique d'intervalles, indépendamment des systèmes de calcul formel dotés de mécanismes de formes modulaires. Tout le code, les reçus et les données exactes sont fournis dans des fichiers annexes.

L'article conclut que la dimension 36 représente un régime qualitativement différent où le compactage record connu est faible par rapport à la borne LP, rendant l'énoncé dual fort mais la question de l'optimalité stricte plus difficile à résoudre.