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

Resumen Técnico: Configuraciones Óptimas Certificadas para el Problema de Heilbronn en el Triángulo Unitario ($n \le 8$)

Definición del Problema
Este artículo aborda el problema del triángulo de Heilbronn dentro del dominio específico del triángulo rectángulo unitario $T = \{(x, y) \in \mathbb{R}^2 : x \ge 0, y \ge 0, x + y \le 1\}$, el cual tiene un área de $1/2$. El objetivo es determinar la ubicación de $n$ puntos dentro de $T$ que maximice el área mínima entre todos los triángulos formados por ternas de estos puntos. Sea $\Delta^\triangle_n$ esta área mínima máxima alcanzable. Mientras que existen extensos resultados exactos para el cuadrado unitario, este trabajo se centra en el simplex unitario, observando que las transformaciones afines preservan las proporciones de área pero no mapean triángulos a cuadrados, lo que requiere un análisis específico del dominio.

Metodología
Los autores emplean un marco de Programación Cuadrática con Restricciones Enteras Mixtas (MIQCP), desarrollado previamente para el cuadrado unitario en un artículo complementario [1], adaptado aquí para el dominio triangular. El núcleo de la metodología se basa en dos intuiciones estructurales:

1. Estructura de la Frontera (Proposición 1): Para $n \ge 5$, a menos que una configuración óptima ocupe los tres vértices de $T$, existe una configuración óptima (o una imagen afín preservadora de área de una) con al menos cuatro puntos en la frontera $\partial T$. Crucialmente, un lado del triángulo debe portar dos de estos puntos de la frontera, mientras que los otros dos lados portan al menos uno cada uno.
2. Reducción de Simetría (Corolario 1): Utilizando la simetría afín $S_3$ del triángulo (permutando vértices con módulo de Jacobiano 1), los autores fijan el lado que porta los dos puntos de la frontera (elegido como la pierna $e_1$) y etiquetan los puntos en sentido antihorario. Esto reduce el espacio de búsqueda al fijar cuatro puntos de la frontera y romper las simetrías de reflexión residuales.

El modelo de optimización (Ecuación 1) maximiza una variable $z$ sujeta a restricciones que aseguran que $z$ sea menor o igual al área absoluta de cada triángulo formado por los $n$ puntos. Los términos bilineales en los cálculos de área se gestionan mediante sustitución ($w_{ij} = x_i y_j$), y las variables binarias $b_t$ gestionan la orientación de las áreas con signo. El problema se resuelve hasta alcanzar la optimalidad global probada utilizando el solver Gurobi 13.

Contribuciones Clave y Resultados
El artículo proporciona las primeras pruebas de optimalidad global certificadas para $n=7$ y $n=8$ en el triángulo unitario, cerrando brechas significativas dejadas por métodos previos de búsqueda en cuadrícula y de rama y cota.

• Soluciones Exactas para $n \le 7$: Los autores recuperan óptimos exactos con configuraciones de coordenadas explícitas:
  • $n=3, 4$: Resultados clásicos ($1/2$ y $1/6$).
  • $n=5$: $\frac{3}{2} - \sqrt{2}$. La solución es una familia de un parámetro; los autores enumeran un extremo representativo.
  • $n=6$: $1/16$. Esta es una familia de dos parámetros; se proporciona un representante racional.
  • $n=7$: $7/144$. La configuración óptima reside en una cuadrícula de $1/12$.
• Certificación Numérica para $n=8$: Para $n=8$, no se conoce una expresión de forma cerrada. Los autores confirman una conjetura de Chen, Zeng y Zhou [7] de que el óptimo es la raíz real única de un séptico (grado 7) específico.
  • La solución numérica está certificada a 250 dígitos.
  • Los autores demuestran que el grupo de Galois de este polinomio séptico es el grupo simétrico $S_7$. En consecuencia, el valor óptimo y las coordenadas no pueden expresarse en radicales, lo que explica por qué la literatura previa solo lista aproximaciones numéricas.
• Eficiencia: El modelo MIQCP propuesto resuelve $n=7$ en 22.6 segundos y $n=8$ en 2324 segundos en una sola máquina. Esto contrasta fuertemente con esfuerzos previos: una búsqueda en cuadrícula para $n=7$ dejó un error del 18%, y un enfoque de rama y cota para $n=8$ requirió 11,000 horas de CPU para lograr un error de solo $2.7 \times 10^{-5}$.

Significancia y Reivindicaciones
El artículo afirma establecer las primeras pruebas de optimalidad para $n=7$ y $n=8$ en el triángulo unitario. Al aprovechar el resultado de la estructura de la frontera, los autores reducen el problema de optimización continua a un modelo de enteros mixtos tratable que certifica la optimalidad global.

Para $n=8$, el trabajo cierra la brecha entre la conjetura numérica y la certificación rigurosa. Aunque los autores no prueban que el conjunto específico de 11 triángulos mínimos identificados por Chen, Zeng y Zhou sea el único conjunto mínimo (una condición requerida para probar completamente la conjetura), su reconstrucción confirma la raíz conjeturada con extrema precisión y valida las propiedades del grupo de Galois. El artículo concluye que la principal cuestión abierta restante para $n=8$ es demostrar que los once triángulos específicos en el conjunto conjeturado son simultáneamente mínimos. Se identifica como trabajo futuro la extensión de estos certificados a $n \ge 9$ y la caracterización de las familias óptimas para $n=5$ y $n=6$.