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

Abstract

We study Heilbronn's triangle problem in the unit right triangle, where $n$ points are placed to maximize the smallest of the $\left(\genfrac{}{}{0ex}{}{n}{3}\right)$ triangle areas they span. We prove a boundary-structure result: unless all three vertices are occupied, some optimal configuration with $n\ge 5$ has at least four points on the boundary, one edge carrying two of them. With the affine $S_3$ symmetry this fixes four boundary points and $n$ orientation variables in a mixed-integer model that certifies global optimality for all $n\le 8$: for $n=8$ apparently the first proof, and for $n=7$ an independent confirmation of the symbolic-computation proof of Zeng and Chen. For $n\le 7$ we obtain exact optima with explicit configurations. For $n=8$ the optimum is conjectured to be the real root of a septic obtained by Chen, Zeng and Zhou, which our reconstruction confirms to $250$ digits. We show its Galois group is $S_7$, so on that conjecture no expression in radicals exists.

Topics & keywords