Heilbronn's Problem in the Unit Triangle: Certified Optimal Configurations for up to $n\le 8$

Résumé Technique : Configurations Optimales Certifiées pour le Problème de Heilbronn dans le Triangle Unitaire ($n \le 8$)

Définition du Problème
Cet article traite du problème du triangle de Heilbronn dans le domaine spécifique du triangle rectangle unitaire $T = \{(x, y) \in \mathbb{R}^2 : x \ge 0, y \ge 0, x + y \le 1\}$, qui a une aire de $1/2$. L'objectif est de déterminer le placement de $n$ points à l'intérieur de $T$ afin de maximiser l'aire minimale parmi tous les triangles formés par des triplets de ces points. Soit $\Delta^\triangle_n$ cette aire minimale maximale réalisable. Bien que des résultats exacts étendus existent pour le carré unitaire, ce travail se concentre sur le simplexe unitaire, en notant que les transformations affines préservent les rapports d'aire mais ne transforment pas les triangles en carrés, ce qui nécessite une analyse propre au domaine.

Méthodologie
Les auteurs utilisent un cadre de Programmation Quadratique avec Contraintes Mixtes (MIQCP), précédemment développé pour le carré unitaire dans un article compagnon [1], adapté ici pour le domaine triangulaire. La méthodologie centrale repose sur deux intuitions structurelles :

1. Structure de la Frontière (Proposition 1) : Pour $n \ge 5$, à moins qu'une configuration optimale n'occupe les trois sommets de $T$, il existe une configuration optimale (ou une image affine préservant l'aire de celle-ci) avec au moins quatre points sur la frontière $\partial T$. Crucialement, un côté du triangle doit porter deux de ces points de frontière, tandis que les deux autres côtés en portent au moins un chacun.
2. Réduction par Symétrie (Corollaire 1) : En utilisant la symétrie affine $S_3$ du triangle (permutant les sommets avec un module jacobien de 1), les auteurs fixent le côté portant deux points de frontière (choisi comme la jambe $e_1$) et étiquettent les points dans le sens antihoraire. Cela réduit l'espace de recherche en fixant quatre points de frontière et en brisant les symétries de réflexion résiduelles.

Le modèle d'optimisation (Équation 1) maximise une variable $z$ sous réserve de contraintes garantissant que $z$ est inférieur ou égal à l'aire absolue de chaque triangle formé par les $n$ points. Les termes bilinéaires dans les calculs d'aire sont gérés via une substitution ($w_{ij} = x_i y_j$), et des variables binaires $b_t$ gèrent l'orientation des aires signées. Le problème est résolu avec une optimalité globale prouvée grâce au solveur Gurobi 13.

Contributions Clés et Résultats
L'article fournit les premières preuves d'optimalité globale certifiées pour $n=7$ et $n=8$ dans le triangle unitaire, comblant ainsi d'importantes lacunes laissées par les méthodes de recherche sur grille et de branch-and-bound précédentes.

• Solutions Exactes pour $n \le 7$ : Les auteurs récupèrent des optima exacts avec des configurations de coordonnées explicites :
  • $n=3, 4$ : Résultats classiques ($1/2$ et $1/6$).
  • $n=5$ : $\frac{3}{2} - \sqrt{2}$. La solution est une famille à un paramètre ; les auteurs listent un point terminal représentatif.
  • $n=6$ : $1/16$. Il s'agit d'une famille à deux paramètres ; un représentant rationnel est fourni.
  • $n=7$ : $7/144$. La configuration optimale se situe sur une grille de $1/12$.
• Certification Numérique pour $n=8$ : Pour $n=8$, aucune expression en forme fermée n'est connue. Les auteurs confirment une conjecture de Chen, Zeng et Zhou [7] selon laquelle l'optimum est l'unique racine réelle d'un polynôme septique (de degré 7) spécifique.
  • La solution numérique est certifiée à 250 décimales.
  • Les auteurs prouvent que le groupe de Galois de ce polynôme septique est le groupe symétrique $S_7$. Par conséquent, la valeur optimale et les coordonnées ne peuvent être exprimées en radicaux, ce qui explique pourquoi la littérature précédente ne liste que des approximations numériques.
• Efficacité : Le modèle MIQCP proposé résout $n=7$ en 22,6 secondes et $n=8$ en 2324 secondes sur une seule machine. Cela contraste fortement avec les efforts précédents : une recherche sur grille pour $n=7$ laissait un écart de 18 %, et une approche de branch-and-bound pour $n=8$ a nécessité 11 000 heures CPU pour atteindre un écart de seulement $2,7 \times 10^{-5}$.

Signification et Revendications
L'article affirme établir les premières preuves d'optimalité pour $n=7$ et $n=8$ dans le triangle unitaire. En exploitant le résultat de la structure de la frontière, les auteurs réduisent le problème d'optimisation continue à un modèle entier mixte traitable qui certifie l'optimalité globale.

Pour $n=8$, le travail comble le fossé entre la conjecture numérique et la certification rigoureuse. Bien que les auteurs ne prouvent pas que l'ensemble spécifique des 11 triangles minimaux identifiés par Chen, Zeng et Zhou est le seul ensemble minimal (une condition nécessaire pour prouver pleinement la conjecture), leur reconstruction confirme la racine conjecturée avec une précision extrême et valide les propriétés du groupe de Galois. L'article conclut que la principale question ouverte restante pour $n=8$ est de démontrer que les onze triangles spécifiques de l'ensemble conjecturé sont simultanément minimaux. Les travaux futurs sont identifiés comme l'extension de ces certificats à $n \ge 9$ et la caractérisation des familles optimales pour $n=5$ et $n=6$.