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

技术摘要：单位三角形内海尔布隆问题（Heilbronn's Problem）的认证最优配置（$n \le 8$）

问题定义
本文研究了在特定定义域——面积为 $1/2$ 的单位直角三角形 $T = \{(x, y) \in \mathbb{R}^2 : x \ge 0, y \ge 0, x + y \le 1\}$ 内的海尔布隆三角形问题。其目标是确定 $n$ 个点在 $T$ 内的放置方式，以最大化由这些点构成的所有三元组中最小三角形的面积。令 $\Delta^\triangle_n$ 表示该最大可实现的最小面积。虽然对于单位正方形已存在广泛的精确结果，但本研究侧重于单位单纯形（unit simplex），并指出尽管仿射变换保持面积比例，但并不将三角形映射为正方形，因此需要针对特定定义域进行分析。

方法论
作者采用了混合整数二次约束规划（MIQCP）框架，该框架此前已在关于单位正方形的伴随论文 [1] 中开发，此处针对三角形定义域进行了适配。该方法论的核心依赖于两个结构性见解：

1. 边界结构（命题 1）： 对于 $n \ge 5$，除非最优配置占据了 $T$ 的所有三个顶点，否则存在一个最优配置（或其面积保持的仿射像）至少有四个点位于边界 $\partial T$ 上。至关重要的是，三角形的一条边必须承载其中两个边界点，而另外两条边各至少承载一个点。
2. 对称性简化（推论 1）： 利用三角形的仿射 $S_3$ 对称性（通过雅可比模值为 1 的顶点置换），作者固定了承载两个边界点的边（选定为直角边 $e_1$），并按逆时针方向对点进行编号。这通过固定四个边界点减少了搜索空间，并打破了残余的反射对称性。

优化模型（等式 1）通过最大化变量 $z$ 来求解，同时受到约束条件的限制，确保 $z$ 小于或等于由 $n$ 个点形成的每一个三角形的绝对面积。面积计算中的双线性项通过代换（$w_{ij} = x_i y_j$）进行处理，并通过二值变量 $b_t$ 管理有向面积的方向。该问题使用 Gurobi 13 求解器求解，以实现证明的全局最优性。

主要贡献与结果
本文提供了单位三角形内 $n=7$ 和 $n=8$ 的首个认证全局最优性证明，填补了以往网格搜索和分支定界法留下的显著空白。

• $n \le 7$ 的精确解： 作者通过显式坐标配置恢复了精确最优解：
  • $n=3, 4$：经典结果（分别为 $1/2$ 和 $1/6$）。
  • $n=5$：$\frac{3}{2} - \sqrt{2}$。该解是一个单参数族；作者列出了一个代表性的端点。
  • $n=6$：$1/16$。这是一个双参数族；提供了一个有理数代表。
  • $n=7$：$7/144$。最优配置位于 $1/12$ 网格上。
• $n=8$ 的数值认证： 对于 $n=8$，目前尚无已知闭式表达式。作者证实了 Chen、Zeng 和 Zhou [7] 的一个猜想，即最优值是特定七次多项式的唯一实根。
  • 数值解被认证至 250 位小数。
  • 作者证明了该七次多项式的伽罗瓦群（Galois group）是对称群 $S_7$。因此，最优值和坐标无法用根式表示，这解释了为何以往文献仅列出数值近似值。
• 效率： 所提出的 MIQCP 模型在单机上求解 $n=7$ 耗时 22.6 秒，求解 $n=8$ 耗时 2324 秒。这与之前的尝试形成了鲜明对比：针对 $n=7$ 的网格搜索留下了 18% 的间隙，而针对 $n=8$ 的分支定界法在达到仅 $2.7 \times 10^{-5}$ 的间隙时，需要 11,000 CPU 小时。

意义与主张
本文声称建立了单位三角形内 $n=7$ 和 $n=8$ 的首个最优性证明。通过利用边界结构结果，作者将连续优化问题转化为可处理的混合整数模型，从而实现了全局最优性的认证。

对于 $n=8$，这项工作架起了数值猜想与严格认证之间的桥梁。虽然作者并未证明 Chen、Zeng 和 Zhou 所确定的这组 11 个最小三角形是唯一的最小集合（这是完全证明该猜想所必需的条件），但他们的重构工作将猜想的根精确到了极高的精度，并验证了伽罗瓦群的性质。论文最后指出，对于 $n=8$ 而言，主要的悬而未决问题在于证明猜想集合中的所有 11 个特定三角形同时达到最小。未来的工作方向被确定为将这些认证扩展到 $n \ge 9$，并刻画 $n=5$ 和 $n=6$ 的最优族。