From Computational Certification to Exact Coordinates: Heilbronn's Triangle Problem on the Unit Square Using Mixed-Integer Optimization

この論文は、混合整数非線形計画法と厳密な記号計算を統合した「最適化後に精密化」フレームワークを開発し、ヘイルブロン三角形問題において$n=9$のケースを標準的なデスクトップで 15 分以内に証明可能な大域的最適解として解き、2002 年の構成が真に最適であることを初めて証明するとともに、$n=5$から$9$までのすべての最適配置の厳密な座標を導出したことを報告しています。

要約

🎯 問題の正体：「最も広い三角形」を見つけるゲーム

まず、この問題が何なのかを想像してみてください。

• 舞台： 1 メートル×1 メートルの正方形の部屋（単位正方形）。
• ルール： その部屋の中に、9 人（n=9 の場合）の人を配置します。
• 目的： 9 人のうち、**「どんな 3 人を選んでも、その 3 人が作る三角形の面積が、できるだけ広く（大きく）なるように」**配置すること。

つまり、「3 人が集まると狭い三角形（面積が小さい）になってしまう」というのを防ぎ、「一番狭い三角形」さえも最大限に広げたいという、究極の「公平な配置」を探すゲームです。

🕵️‍♂️ 従来の方法：「根性で探す」の限界

これまで、この問題を解こうとした人々は、コンピューターに「ありとあらゆるパターンを試させて」答えを見つけようとしていました。
しかし、9 人になると組み合わせが膨大になり、**「1 日中、スーパーコンピューターを動かし続けても、答えが確実かどうか証明できない」**という壁にぶつかっていました。まるで、広大な森で「一番高い木」を探すために、木を一本ずつ測り続けるようなものです。

⚡ 新しい方法：「 optimize-then-refine（まず最適化、その後で精密化）」

この論文の著者たちは、**「まず大まかに探して、その後で精密に仕上げる」**という 2 段階の戦略を取りました。

ステップ 1：「大まかな地図」を作る（混合整数計画最適化）

まず、コンピューターに「だいたいどこに人がいればいいか」を計算させます。
ここで重要なのが、**「対称性を壊す」**という工夫です。

• 例え話： 部屋をぐるぐる回したり、鏡に映したりしても、配置は同じ「答え」です。でも、コンピューターは「左に人がいる場合」と「右に人がいる場合」を別々の問題として一生懸命計算してしまいます。
• 工夫： 「左端の壁には必ず人がいる」「上から時計回りに名前をつける」など、「こうでなければダメ」というルールを事前に決めておくことで、コンピューターの無駄な作業を 9 割以上カットしました。
• 結果： これにより、9 人の配置問題を、**「標準的なデスクトップ PC で 15 分」**で解けるようになりました（前は 1 日かかっていました！）。これで「答えの候補」が見つかり、それが「本当に最適かどうか」の証明（証明書）も手に入ります。

ステップ 2：「精密な測量」をする（記号計算）

ステップ 1 で見つかったのは「0.7127...」のような**「おおよその数字」**でした。しかし、数学的には「正確な形（√65 などを含む厳密な数）」を知りたいものです。

• 例え話： ステップ 1 で「宝の場所はおそらくこの辺り」と特定しました。ステップ 2 では、その場所の**「正確な座標」**を、数式を使って「√65」のようなきれいな形に変換します。
• 方法： 「一番狭い三角形の面積はすべて等しいはずだ」というルールを使って、連立方程式を解き、**「厳密な答え」**を導き出しました。

🏆 今回の成果：何がわかったの？

1. 9 人（n=9）の正解が証明された：
   2002 年に誰かが「これがおそらく正解」と提案した配置が、**「間違いなく世界で一番広い」**ことが、初めて数学的に証明されました。
2. きれいな「厳密な答え」が見つかった：
   単なる「0.12345...」という数字ではなく、「√65（ルート 65）を使ったきれいな分数」のような、数学的に美しい形での答えが、5 人から 9 人までのすべてのケースで得られました。
3. 驚きのパターン発見：
   最適解を調べると、「一番狭い三角形」以外の三角形の面積が、いくつかの決まった値に「固まって（クラスター化）」いることがわかりました。
   • 例え話： 9 人が作った三角形の面積を並べると、「一番小さいもの」の他に、「中くらいのもの」が 3 つのグループに分かれて固まっているような、不思議な秩序が見えました。これは、この問題が持つ隠された「美しさ」や「規則性」を示唆しています。

🌟 まとめ

この論文は、「強力なコンピューター計算（大まかな探偵）」と「美しい数学の論理（精密な測量）」を組み合わせることで、長年解けなかったパズルのピースを、驚くほど速く、かつ完璧にはめ込むことに成功しました。

• 以前： 1 日かかっても確信が持てなかった。
• 今回： 15 分で証明でき、きれいな数式で答えが出た。

これは、数学の難問を解くための新しい「魔法の道具」が完成したことを意味しており、今後、より難しい問題（10 人、11 人など）を解くための道を開いた素晴らしい研究です。

技術概要

ヘイルブロン三角形問題における計算証明から厳密座標へ：混合整数最適化を用いたアプローチ

論文の技術的サマリー（日本語）

本論文は、離散幾何学の古典的な問題である「ヘイルブロン三角形問題（Heilbronn triangle problem）」に対し、**「最適化→精密化（optimize-then-refine）」**という新しい枠組みを提案し、混合整数非線形計画法（MINLP）と厳密な記号計算を統合して解決を試みた研究です。特に、$n=9$ のケースにおいて、従来の計算時間（約 1 日）を 1 桁以上短縮し、15 分以内でグローバル最適解を証明することに成功しました。また、$n=5$ から $n=9$ までのすべての最適配置の厳密な座標を導出しました。

以下に、問題定義、手法、主要な貢献、結果、および意義について詳細をまとめます。

---

1. 問題定義

ヘイルブロン三角形問題は、単位正方形 $[0, 1]^2$ 内に $n$ 個の点を配置したとき、それらの点のいずれか 3 点で構成される三角形の面積の最小値を最大化する配置を見つける問題です。この最大最小面積を $\Delta_n$ と表します。

• 背景: ハンス・ヘイルブロン（Hans Heilbronn）にちなんで名付けられました。
• 現状: $n$ が小さい場合の最適解は長年研究されてきましたが、$n=9$ 以上の厳密な証明や、$n$ が大きい場合の漸近挙動については未解決の部分が多く残っていました。
• 既存の課題: 数値的な最適解は得られていたものの、それが真のグローバル最適解であることを数学的に証明すること、および座標を厳密な代数的形式（厳密解）で導出することは困難でした。

2. 提案手法：最適化→精密化フレームワーク

著者は、数値計算による「グローバル最適性の証明」と、代数的計算による「厳密座標の導出」を 2 段階で行うフレームワークを構築しました。

ステップ 1: グローバル最適化による数値証明

• 混合整数非線形計画モデル（MINLP）の構築:
  • 三角形の面積を行列式（シューレース公式）で表現し、絶対値を含む非線形制約を処理するために、符号変数（バイナリ変数）を導入しました。
  • 対称性の破れ（Symmetry Breaking）戦略: 最適配置の凸包の境界構造に関する理論的性質（Proposition 3）を利用し、単位正方形の境界上に少なくとも 5 点が存在すること、およびそれらが特定の順序で配置されることを仮定してモデルに制約を加えました。これにより、回転や反転、点のラベル付けの対称性を大幅に削減し、探索空間を劇的に縮小しました。
  • 符号の固定: 境界構造に基づき、特定の三角形の面積の符号（正負）を事前に決定し、バイナリ変数を固定することでモデルを強化しました。
• ソルバー: 商用ソルバー Gurobi を使用し、上記の強化されたモデルを解くことで、数値的な最適値と、その解がグローバル最適であることを保証する「数値証明書」を取得しました。

ステップ 2: 厳密な記号計算による精密化

• 構造の特定: ステップ 1 の数値解から、「どの三角形が最小面積（クリティカル三角形）であるか」「どの点が境界上にあるか」という構造情報を抽出しました。
• 多項式方程式系の構築: クリティカル三角形の面積が等しいという条件、および境界条件に基づき、未知の座標変数に関する多項式方程式系を構築しました。
• 厳密解の導出: 計算機代数システム（SymPy）を用いて、上記の方程式系を厳密に解き、代数的数（平方根などを含む）で表された厳密な座標を導出しました。
  • $n=9$ のように直接解くのが困難な場合、数値解から代数的な体（例：$\mathbb{Q}(\sqrt{65})$）を特定し、数値を記号に変換する「数値→記号」の手法を適用しました。

3. 主要な貢献

1. 強力な混合整数定式化の開発:
   • 境界構造に基づく対称性の破れ戦略と、行列式の構造的特徴の活用により、既存のモデルよりもはるかに強力なモデルを構築しました。
   • これにより、$n=9$ の問題を標準的なデスクトップ PC で約 15 分で解き、従来の約 1 日（Monji et al., 2025）から 1 桁以上高速化しました。
2. 厳密座標の導出と最適性の証明:
   • 数値的な最適性証明と記号計算を組み合わせることで、Comellas と Yebra (2002) が見つけた $n=9$ の配置がグローバル最適であることを初めて証明しました。
   • $n=5$ から $n=9$ までのすべての最適配置について、厳密な代数的座標を導出しました。これにより、既存の結果を確認・簡略化し、以前は数値近似のみだったものを厳密な形で提供しました。
3. 構造的な発見と新たな研究課題:
   • 最適配置において、クリティカル三角形（最小面積を持つ三角形）の数が $n$ とともに増加する傾向があること、および非クリティカル三角形の面積が少数の異なる値に「クラスター（集積）」する現象を発見しました。
   • この「面積のクラスター化」は、極値点集合の組合せ幾何学における新しい研究課題として提示されました。
4. 再現性の確保:
   • 全ての構成データ、コード、入力ファイルを公開し、研究の再現性を担保しました。

4. 主要な結果

• 計算性能の向上:
  • $n=9$ の証明に要した時間が、従来の 1 日（24 時間）から 15 分（908 秒）に短縮されました。
  • $n=5 \sim 8$ についても、数秒から数十秒で証明を完了しました。
• 厳密解の導出:
  • $n=5$: $\Delta_5 = \sqrt{3}/9$ を確認。
  • $n=6$: $\Delta_6 = 1/8$ を確認（1 パラメータ族の解が存在）。
  • $n=7$: $\Delta_7 \approx 0.083859$。座標は $19f^3 - 27f^2 + 11f - 1 = 0$の根$f$ を用いて表されます。
  • $n=8$: $\Delta_8 = (\sqrt{13}-1)/36$。Comellas-Yebra の結果を証明し、座標形式を簡略化しました。
  • $n=9$: $\Delta_9 = (-11 + 9\sqrt{65})/320$。Comellas-Yebra の配置が最適であることを初めて証明しました。
• 構造的特徴:
  • 最適配置では、単位正方形の境界上に少なくとも 5 点が存在することが確認されました。
  • 非クリティカル三角形の面積が特定の値に集積する現象（$n=8$ では 56 個の三角形のうち、最小値を除く 44 個が数種類の値に分類される）が観察されました。

5. 意義と将来展望

• 手法の革新性: 混合整数最適化（MINLP）ソルバーの成熟度を示すとともに、数値解を「厳密解」へと昇華させるための「最適化→精密化」フレームワークは、他の離散幾何学の問題（パッキング、カバリング問題など）にも適用可能な汎用的なアプローチとして意義があります。
• 理論への貢献: 従来の数値的な発見を数学的に厳密に裏付けることで、ヘイルブロン問題の理解を深めました。特に、$n=9$ の最適性の証明は、長年の未解決課題に対する重要な進展です。
• 今後の課題:
  • $n=10$ 以上のグローバル最適性の証明（計算リソースの増強が必要）。
  • クリティカル三角形の数の下限の理論的証明。
  • 非クリティカル三角形の面積がクラスター化する現象の数学的説明（隠れた対称性の解明）。

本論文は、計算機科学（最適化アルゴリズム）と純粋数学（記号計算、幾何学）の融合によって、古典的な数学的問題に新たな光を当てた画期的な研究と言えます。