HN 日本語サマリー

← 一覧へ戻る
AI・機械学習

AI支援による11個の正方形の最適パッキング証明

AI-assisted proof of optimal packing for 11 squares (github.com)

109 pointsby bluepeter51 コメント

要約

このプロジェクトは、11個の正方形を可能な限り小さく配置する問題(最適パッキング問題)に対する、AI支援による厳密な最適性証明をLean証明支援系で実現したものです。証明はネイティブ数値証明書によって検証され、エラーゼロで完了しました。最適配置の辺長は特定の数式で表され、その値は約3.8770835900228141773となります。

全文翻訳

Leanによる11個の正方形のパッキング

最適パッキングの完全な最適性証明が、ネイティブ数値証明書とともに検証を通過しました。 EvolvingProgramsの検証実行は、7,920のローカルLeanモジュールすべてを受け入れ、最終監査レポートではゼロの誤りが報告されています。このリポジトリは、コミット 1bf942a7af1ea330e95489d8997deebd4227ca71 から、これらの正確な証明ソースとピン留めされたビルド構成をインポートしています。証拠と範囲については、検証レポートを参照してください。

選択された計算負荷の高い正確な数値証明書のチェックには native_decide が使用されます。ジオメトリ、チェッカーの健全性、および証明の組み立ては、通常のLean証明を維持します。その結果、最終定理はLeanのカーネルとネイティブコンパイラを信頼しています。これはカーネルのみの検証主張ではありません。承認された数値宣言とその正確なソースハッシュは、verification/native-certificates.jsonに記録されています。

最適な辺の長さは

[ T = \frac{6u+4}{1+2u-u^2}, ]

ここで u は

[ 5u^8-10u^7-2u^6+14u^5+12u^4-6u^3+2u^2+2u-1=0 ]

の (9/25,37/100) における唯一の根です。

この構成は約 3.8770835900228141773 に達します。モデルは、任意の向き、合法的な境界接触、および互いに離散した開いた内部を許可します。ElevenSquare/Optimality.lean の公開ステートメントと完全なT03ソースツリーは、このリポジトリの以前のメインブランチから変更されていません。

エントリーポイント

| ファイル |
| --- | --- |
| ElevenSquare/Foundations.lean | ジオメトリ、正確な端点、到達可能な構成、閉じたセルカバー、および有限ケースの削減。 |
| ElevenSquare/Pending/ | 元の公開インターフェース。現在は統合された証明によって解決されています。ディレクトリ名は歴史的なものです。 |
| ElevenSquare/Interop/Wand125/ | 組み込まれたアップストリーム証明結果への接続。 |
| ElevenSquare/Tasks/ | 幾何学的引数、チェッカー、証明データ、およびローカル解析証明。 |
| Sqpack/ | 組み込まれた証明チェッカー、生成された証明、および簡略化。 |
| ElevenSquare/Optimality.lean | 無条件の最適性および辺長下限定理。 |
| ElevenSquare/Verification.lean | 公開証明ターゲットのアクシオムクエリ。 |

検証の再現

プロジェクトは Lean 4.34.1 と Mathlib リビジョン d13f23b723b8a846827a245b89c10fc7d3f11612 をピン留めしています。lake-manifest.json は変更しないでください。LinuxでPython 3、Git、curl、tarを使用している場合:

bash scripts/run_verification.sh --bootstrap --jobs 2

macOSでは、まず elan ランチャーをインストールしてから、同じコマンドを使用してください。elan が既にインストールされている場合、ブートストラップはピン留めされたツールチェーンと依存関係キャッシュを準備できます。マシンに適したワーカー数を選択してください。モジュールはシリアルにコンパイルされます。既存の有効なレシートは再利用可能です。完全な再実行を強制するには --fresh を追加してください。Ctrl-C はランナーをクリーンに停止します。

このコマンドは、すべてのローカルモジュールをチェックし、最終的なソース、レシート、依存関係、およびアクシオムの監査を実行します。最終結果では、OPTIMALITY_PROVED_WITH_NATIVE_CERTIFICATES、ゼロの誤り、および trust_model: lean_kernel_and_native_compiler を要求します。コンパイルされたモジュールの100%に到達しただけでは不十分です。

Leanなしのソースのみのチェックは次のとおりです。

python3 scripts/check_sources.py

手動ワークフローとUbuntuの手順も再開可能な検証をサポートしています。プッシュはワークフローを開始しません。成功したソース実行はEvolvingProgramsのより大きなランナーを使用しました。これはコールドビルドランタイムまたは2〜3時間のmacOS保証を確立するものではありません。

このスナップショットで、履歴的なマテリアライゼーションコマンドや verify.py --setup を実行しないでください。これらは、置き換えられた生成ソースを復元します。ビルドオブジェクトとログは、無視される .lake/ および .verification/ ディレクトリに属します。

謝辞と出典

EvolvingPrograms、@ctjlewis、およびすべてのプロジェクト貢献者に、フォーマル化と検証作業に感謝します。個々の貢献者およびアップストリームのクレジットについては、ACKNOWLEDGEMENTS.mdを参照してください。ソース履歴については、PROVENANCE.mdを参照してください。組み込まれた通知については、integrations/wand125を参照してください。歴史的な簡略化ノートと部分的な監査記録は保持されています。それらの古い未完了ステートメントは、完了した実行レポートによって置き換えられています。