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

Technical Summary: Certified Optimal Configurations for Heilbronn's Problem in the Unit Triangle ($n \le 8$)

Problem Definition
This paper addresses Heilbronn's triangle problem within the specific domain of the unit right triangle $T = \{(x, y) \in \mathbb{R}^2 : x \ge 0, y \ge 0, x + y \le 1\}$, which has an area of $1/2$. The objective is to determine the placement of $n$ points within $T$ that maximizes the minimum area among all triangles formed by triples of these points. Let $\Delta^\triangle_n$ denote this maximum achievable minimum area. While extensive exact results exist for the unit square, this work focuses on the unit simplex, noting that affine transformations preserve area ratios but do not map triangles to squares, necessitating domain-specific analysis.

Methodology
The authors employ a Mixed-Integer Quadratically Constrained Programming (MIQCP) framework, previously developed for the unit square in a companion paper [1], adapted here for the triangular domain. The core of the methodology relies on two structural insights:

1. Boundary Structure (Proposition 1): For $n \ge 5$, unless an optimal configuration occupies all three vertices of $T$, there exists an optimal configuration (or an area-preserving affine image of one) with at least four points on the boundary $\partial T$. Crucially, one edge of the triangle must carry two of these boundary points, while the other two edges carry at least one each.
2. Symmetry Reduction (Corollary 1): Utilizing the affine $S_3$ symmetry of the triangle (permuting vertices with Jacobian modulus 1), the authors fix the edge carrying two boundary points (chosen as the leg $e_1$) and label the points counterclockwise. This reduces the search space by fixing four boundary points and breaking residual reflection symmetries.

The optimization model (Equation 1) maximizes a variable $z$ subject to constraints ensuring $z$ is less than or equal to the absolute area of every triangle formed by the $n$ points. The bilinear terms in the area calculations are handled via substitution ($w_{ij} = x_i y_j$), and binary variables $b_t$ manage the orientation of the signed areas. The problem is solved to proven global optimality using the Gurobi 13 solver.

Key Contributions and Results
The paper provides the first certified global optimality proofs for $n=7$ and $n=8$ in the unit triangle, closing significant gaps left by previous grid search and branch-and-bound methods.

• Exact Solutions for $n \le 7$: The authors recover exact optima with explicit coordinate configurations:
  • $n=3, 4$: Classical results ($1/2$ and $1/6$).
  • $n=5$: $\frac{3}{2} - \sqrt{2}$. The solution is a one-parameter family; the authors list a representative endpoint.
  • $n=6$: $1/16$. This is a two-parameter family; a rational representative is provided.
  • $n=7$: $7/144$. The optimal configuration lies on a $1/12$-grid.
• Numerical Certification for $n=8$: For $n=8$, no closed-form expression is known. The authors confirm a conjecture by Chen, Zeng, and Zhou [7] that the optimum is the unique real root of a specific septic (degree-7) polynomial.
  • The numerical solution is certified to 250 digits.
  • The authors prove that the Galois group of this septic polynomial is the symmetric group $S_7$. Consequently, the optimal value and coordinates cannot be expressed in radicals, explaining why previous literature lists only numerical approximations.
• Efficiency: The proposed MIQCP model solves $n=7$ in 22.6 seconds and $n=8$ in 2324 seconds on a single machine. This contrasts sharply with previous efforts: a grid search for $n=7$ left an 18% gap, and a branch-and-bound approach for $n=8$ required 11,000 CPU hours to achieve a gap of only $2.7 \times 10^{-5}$.

Significance and Claims
The paper claims to establish the first optimality proofs for $n=7$ and $n=8$ in the unit triangle. By leveraging the boundary structure result, the authors reduce the continuous optimization problem to a tractable mixed-integer model that certifies global optimality.

For $n=8$, the work bridges the gap between numerical conjecture and rigorous certification. While the authors do not prove that the specific set of 11 minimal triangles identified by Chen, Zeng, and Zhou is the only minimal set (a condition required to fully prove the conjecture), their reconstruction confirms the conjectured root to extreme precision and validates the Galois group properties. The paper concludes that the primary remaining open question for $n=8$ is demonstrating that all eleven specific triangles in the conjectured set are simultaneously minimal. Future work is identified as extending these certificates to $n \ge 9$ and characterizing the optimal families for $n=5$ and $n=6$.