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

Technische Samenvatting: Gecertificeerde Optimale Configuraties voor Heilbronn's Probleem in de Eenheidsdriehoek ($n \le 8$)

Probleemdefinitie
Dit artikel behandelt het Heilbronn-driehoekprobleem binnen het specifieke domein van de eenheidsrechthoekige driehoek $T = \{(x, y) \in \mathbb{R}^2 : x \ge 0, y \ge 0, x + y \le 1\}$, die een oppervlakte heeft van $1/2$. Het doel is om de plaatsing van $n$ punten binnen $T$ te bepalen die de minimale oppervlakte van alle door triples van deze punten gevormde driehoeken maximaliseert. Laat $\Delta^\triangle_n$ de maximaal bereikbare minimale oppervlakte zijn. Terwijl er uitgebreide exacte resultaten bestaan voor de eenheidskwadraat, richt dit werk zich op de eenheids-simplex, waarbij wordt opgemerkt dat affiene transformaties oppervlakteverhoudingen behouden maar driehoeken niet naar vierkanten afbeelden, wat domeinspecifieke analyse noodzakelijk maakt.

Methodologie
De auteurs maken gebruik van een Mixed-Integer Quadratically Constrained Programming (MIQCP) raamwerk, dat eerder is ontwikkeld voor de eenheidskwadraat in een begeleidend artikel [1], en dat hier is aangepast voor het driehoekige domein. De kern van de methodologie berust op twee structurele inzichten:

1. Randstructuur (Propositie 1): Voor $n \ge 5$, tenzij een optimale configuratie alle drie de hoekpunten van $T$ bezet, bestaat er een optimale configuratie (of een oppervlaktebehoudende affiene afbeelding daarvan) met ten minste vier punten op de rand $\partial T$. Cruciaal is dat één zijde van de driehoek twee van deze randpunten moet bevatten, terwijl de andere twee zijden elk ten minste één punt bevatten.
2. Symmetrie-reductie (Corollary 1): Door gebruik te maken van de affiene $S_3$-symmetrie van de driehoek (het permuteren van hoekpunten met een Jacobiaan-modulus 1), fixeren de auteurs de zijde die de twee randpunten draagt (gekozen als de rechthoekszijde $e_1$) en labelen zij de punten tegen de klok in. Dit reduceert de zoekruimte door vier randpunten te fixeren en de resterende reflectiesymmetrieën te doorbreken.

Het optimalisatiemodel (Vergelijking 1) maximaliseert een variabele $z$ onder restricties die garanderen dat $z$ kleiner dan of gelijk is aan de absolute oppervlakte van elke driehoek gevormd door de $n$ punten. De bilineaire termen in de oppervlakteberekeningen worden afgehandeld via substitutie ($w_{ij} = x_i y_j$), en binaire variabelen $b_t$ beheren de oriëntatie van de getekende oppervlaktes. Het probleem wordt opgelost tot bewezen globale optimaliteit met de Gurobi 13 solver.

Belangrijkste Bijdragen en Resultaten
Het artikel levert de eerste gecertificeerde bewijzen voor globale optimaliteit voor $n=7$ en $n=8$ in de eenheidsdriehoek, waarmee significante hiaten laten van eerdere grid-zoekmethoden en branch-and-bound-methoden.

• Exacte Oplossingen voor $n \le 7$: De auteurs herstellen exacte optima met expliciete coördinatenconfiguraties:
  • $n=3, 4$: Klassieke resultaten ($1/2$ en $1/6$).
  • $n=5$: $\frac{3}{2} - \sqrt{2}$. De oplossing is een een-parameter familie; de auteurs vermelden een representatief eindpunt.
  • $n=6$: $1/16$. Dit is een twee-parameter familie; een rationele representant wordt verstrekt.
  • $n=7$: $7/144$. De optimale configuratie ligt op een $1/12$-grid.
• Numerieke Certificering voor $n=8$: Voor $n=8$ is geen gesloten vorm bekend. De auteurs bevestigen een conjectuur van Chen, Zeng, en Zhou [7] dat het optimum de unieke reële wortel is van een specifieke septische (graad-7) polynoom.
  • De numerieke oplossing is gecertificeerd tot 250 decimalen.
  • De auteurs bewijzen dat de Galois-groep van deze septische polynoom de symmetrische groep $S_7$ is. Bijgevolg kan de optimale waarde en de coördinaten niet in radicalen worden uitgedrukt, wat verklaart waarom eerdere literatuur slechts numerieke benaderingen vermeldt.
• Efficiëntie: Het voorgestelde MIQCP-model lost $n=7$ op in 22,6 seconden en $n=8$ in 2324 seconden op een enkele machine. Dit contrasteert scherp met eerdere inspanningen: een grid-zoekmethode voor $n=7$ liet een gat van 18% achter, en een branch-and-bound-benadering voor $n=8$ vereiste 11.000 CPU-uren om een gat van slechts $2,7 \times 10^{-5}$ te bereiken.

Significantie en Claims
Het artikel claimt de eerste optimaliteitsbewijzen voor $n=7$ en $n=8$ in de eenheidsdriehoek vast te stellen. Door gebruik te maken van het resultaat over de randstructuur, reduceren de auteurs het continue optimalisatieprobleem tot een hanteerbaar mixed-integer model dat globale optimaliteit certificeert.

Voor $n=8$ overbrugt het werk de kloof tussen numerieke conjectuur en rigoureuze certificering. Hoewel de auteurs niet bewijzen dat de specifieke verzameling van 11 minimale driehoeken geïdentificeerd door Chen, Zeng, en Zhou de enige minimale verzameling is (een voorwaarde die nodig is om de conjectuur volledig te bewijzen), bevestigt hun reconstructie de geconjectureerde wortel met extreme precisie en valideert het de eigenschappen van de Galois-groep. Het artikel concludeert dat de belangrijkste resterende open vraag voor $n=8$ het aantonen is dat alle elf specifieke driehoeken in de geconjectureerde verzameling simultaan minimaal zijn. Toekomstig werk wordt geïdentificeerd als het uitbreiden van deze certificaten naar $n \ge 9$ en het karakteriseren van de optimale families voor $n=5$ en $n=6$.