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

Sintesi Tecnica: Configurazioni Ottimali Certificate per il Problema di Heilbronn nel Triangolo Unitario ($n \le 8$)

Definizione del Problema
Questo articolo affronta il problema del triangolo di Heilbronn all'interno del dominio specifico del triangolo rettangolo unitario $T = \{(x, y) \in \mathbb{R}^2 : x \ge 0, y \ge 0, x + y \le 1\}$, che ha un'area di $1/2$. L'obiettivo è determinare la disposizione di $n$ punti all'interno di $T$ che massimizzi l'area minima tra tutti i triangoli formati da terne di questi punti. Sia $\Delta^\triangle_n$ questa area minima massima ottenibile. Mentre esistono estesi risultati esatti per il quadrato unitario, questo lavoro si concentra sul simplesso unitario, osservando che le trasformazioni affini preservano i rapporti di area ma non mappano i triangoli in quadrati, rendendo necessaria un'analisi specifica per il dominio.

Metodologia
Gli autori utilizzano un framework MIQCP (Programmazione Quadratica Vincolata con Variabili Intere Miste), precedentemente sviluppato per il quadrato unitario in un articolo correlato [1], qui adattato per il dominio triangolare. Il nucleo della metodologia si basa su due intuizioni strutturali:

1. Struttura del Confine (Proposizione 1): Per $n \ge 5$, a meno che una configurazione ottimale non occupi tutti e tre i vertici di $T$, esiste una configurazione ottimale (o un'immagine affine preservante l'area di una di esse) con almeno quattro punti sul confine $\partial T$. Fondamentalmente, un lato del triangolo deve ospitare due di questi punti sul confine, mentre gli altri due lati devono ospitarne almeno uno ciascuno.
2. Riduzione della Simmetria (Corollario 1): Utilizzando la simmetria affine $S_3$ del triangolo (permutando i vertici con modulo Jacobiano 1), gli autori fissano il lato che ospita i due punti sul confine (scelto come il cateto $e_1$) e numerano i punti in senso antiorario. Ciò riduce lo spazio di ricerca fissando quattro punti sul confine e rompendo le simmetrie di riflessione residue.

Il modello di ottimizzazione (Equazione 1) massimizza una variabile $z$ soggetta a vincoli che garantiscono che $z$ sia minore o uguale all'area assoluta di ogni triangolo formato dai $n$ punti. I termini bilineari nei calcoli dell'area sono gestiti tramite sostituzione ($w_{ij} = x_i y_j$), e le variabili binarie $b_t$ gestiscono l'orientamento delle aree con segno. Il problema viene risolto fino alla provenienza dell'ottimalità globale utilizzando il solver Gurobi 13.

Contributi Chiave e Risultati
L'articolo fornisce le prime prove di ottimalità globale certificata per $n=7$ e $n=8$ nel triangolo unitario, colmando significativi vuoti lasciati da precedenti ricerche tramite griglia e metodi branch-and-bound.

• Soluzioni Esatte per $n \le 7$: Gli autori recuperano ottimi esatti con configurazioni di coordinate esplicite:
  • $n=3, 4$: Risultati classici ($1/2$ e $1/6$).
  • $n=5$: $\frac{3}{2} - \sqrt{2}$. La soluzione è una famiglia a un parametro; gli autori elencano un endpoint rappresentativo.
  • $n=6$: $1/16$. Questa è una famiglia a due parametri; viene fornito un rappresentante razionale.
  • $n=7$: $7/144$. La configurazione ottimale risiede su una griglia di $1/12$.
• Certificazione Numerica per $n=8$: Per $n=8$, non è nota alcuna espressione in forma chiusa. Gli autori confermano una congettura di Chen, Zeng e Zhou [7] secondo cui l'ottimo è l'unica radice reale di un particolare polinomio settico (di grado 7).
  • La soluzione numerica è certificata a 250 cifre.
  • Gli autori dimostrano che il gruppo di Galois di questo polinomio settico è il gruppo simmetrico $S_7$. Di conseguenza, l'ottimo e le coordinate non possono essere espressi in radicali, spiegando perché la letteratura precedente elenca solo approssimazioni numeriche.
• Efficienza: Il modello MIQCP proposto risolve $n=7$ in 22,6 secondi e $n=8$ in 2324 secondi su una singola macchina. Ciò contrasta nettamente con gli sforzi precedenti: una ricerca su griglia per $n=7$ lasciava un gap del 18%, mentre un approccio branch-and-bound per $n=8$ richiedeva 11.000 ore CPU per ottenere un gap di soli $2,7 \times 10^{-5}$.

Significatività e Rivendicazioni
L'articolo sostiene di aver stabilito le prime prove di ottimalità per $n=7$ e $n=8$ nel triangolo unitario. Sfruttando il risultato della struttura del confine, gli autori riducono il problema di ottimizzazione continua a un modello misto-intero trattabile che certifica l'ottimalità globale.

Per $n=8$, il lavoro colma il divario tra congettura numerica e certificazione rigorosa. Sebbene gli autori non dimostrino che l'insieme specifico di 11 triangoli minimi identificati da Chen, Zeng e Zhou sia l'unico insieme minimale (una condizione necessaria per provare completamente la congettura), la loro ricostruzione conferma la radice congetturata con estrema precisione e valida le proprietà del gruppo di Galois. L'articolo conclude che la principale questione aperta rimanente per $n=8$ è dimostrare che tutti gli undici specifici triangoli nell'insieme congetturato siano simultaneamente minimi. Il lavoro futuro è identificato nell'estensione di questi certificati a $n \ge 9$ e nella caratterizzazione delle famiglie ottimali per $n=5$ e $n=6$.