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

技術要約：単位三角形におけるハイロンの問題の認定された最適構成（$n \le 8$）

問題の定義
本論文は、面積が $1/2$ である単位直角三角形 $T = \{(x, y) \in \mathbb{R}^2 : x \ge 0, y \ge 0, x + y \le 1\}$ という特定の領域内におけるハイロンの三角形問題を取り扱う。目的は、$n$ 個の点を $T$ 内に配置し、これら $n$ 個の点のうちの3点から形成されるすべての三角形の最小面積を最大化することである。$\Delta^\triangle_n$ をこの達成可能な最大最小面積とする。単位正方形については広範な厳密解が存在するが、本研究は単位単体（unit simplex）に焦点を当てている。アフィン変換は面積比を保存するものの、三角形を正方形に写すわけではないため、領域固有の解析が必要となる。

手法
著者らは、先行研究 [1] で単位正方形のために開発された混合整数二次制約計画法（MIQCP）フレームワークを用い、これを三角形の領域に適応させている。手法の核となるのは、以下の2つの構造的知見に基づいている。

1. 境界構造 (命題 1): $n \ge 5$ の場合、最適構成が $T$ の3つの頂点をすべて占有していない限り、少なくとも4つの点が境界 $\partial T$ 上にある最適構成（またはその面積保存アフィン像）が存在する。決定的なことに、三角形の1つの辺にはこれら境界点のうち2点が乗り、他の2つの辺には少なくとも各1点が乗る必要がある。
2. 対称性の低減 (系 1): 三角形の（ヤコビアンの絶対値が1である頂点置換による）アフィン $S_3$ 対称性を利用して、2つの境界点を持つ辺（脚 $e_1$ として選択）を固定し、点を反時計回りにラベル付けする。これにより、4つの境界点を固定し、残存する鏡映対称性を打破することで探索空間を削減する。

最適化モデル（式1）は、すべての三角形の面積が変数 $z$ 以下であることを保証する制約条件下で $z$ を最大化する。面積計算における双線形項は、代入（$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}$。これは1パラメータの族であり、著者らは代表的な端点を列挙している。
  • $n=6$: $1/16$。これは2パラメータの族であり、有理数表現の代表値が提供されている。
  • $n=7$: $7/144$。最適構成は $1/12$ グリッド上に存在する。
• $n=8$ に対する数値的認定: $n=8$ については、閉形式の表現は知られていない。著者らは、Chen, Zeng, および Zhou [7] による、最適値が特定の7次多項式の唯一の実数根であるという予想を裏付けている。
  • 数値解は250桁の精度で認定されている。
  • 著者らは、この7次多項式のガロア群が対称群 $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$ の最適家族を特徴付けることが挙げられている。