論文の概要: Towards Solving the Gilbert-Pollak Conjecture via Large Language Models
- arxiv url: http://arxiv.org/abs/2601.22365v1
- Date: Thu, 29 Jan 2026 22:18:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-02 18:28:15.095901
- Title: Towards Solving the Gilbert-Pollak Conjecture via Large Language Models
- Title（参考訳）: 大規模言語モデルによるギルバート・ポラック概念の解法に向けて
- Authors: Yisi Ke, Tianyu Huang, Yankai Shu, Di He, Jingchu Gai, Liwei Wang,
- Abstract要約: 本稿では,Steiner比のより厳密な下界を得るための新しいAIシステムを提案する。
予想を解くために直接 LLM を誘導するのではなく、規則に制約された幾何学的補題を生成する。
これらの補題は、検証関数と呼ばれる特殊関数の集合を構成するために使われる。
- 参考スコア（独自算出の注目度）: 18.072160709262427
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Gilbert-Pollak Conjecture \citep{gilbert1968steiner}, also known as the Steiner Ratio Conjecture, states that for any finite point set in the Euclidean plane, the Steiner minimum tree has length at least $\sqrt{3}/2 \approx 0.866$ times that of the Euclidean minimum spanning tree (the Steiner ratio). A sequence of improvements through the 1980s culminated in a lower bound of $0.824$, with no substantial progress reported over the past three decades. Recent advances in LLMs have demonstrated strong performance on contest-level mathematical problems, yet their potential for addressing open, research-level questions remains largely unexplored. In this work, we present a novel AI system for obtaining tighter lower bounds on the Steiner ratio. Rather than directly prompting LLMs to solve the conjecture, we task them with generating rule-constrained geometric lemmas implemented as executable code. These lemmas are then used to construct a collection of specialized functions, which we call verification functions, that yield theoretically certified lower bounds of the Steiner ratio. Through progressive lemma refinement driven by reflection, the system establishes a new certified lower bound of 0.8559 for the Steiner ratio. The entire research effort involves only thousands of LLM calls, demonstrating the strong potential of LLM-based systems for advanced mathematical research.
- Abstract（参考訳）: ギルバート・ポラック予想(Gilbert-Pollak Conjecture \citep{gilbert 1968steiner})は、シュタイナー比(Steiner Ratio Conjecture)としても知られ、ユークリッド平面上の任意の有限点に対して、シュタイナー最小木は少なくとも$$\sqrt{3}/2 \approx 0.866$ である(シュタイナー比)。
1980年代を通しての一連の改善は0.824ドルという低い境界に達し、過去30年間に大きな進展は報告されなかった。
LLMの最近の進歩は、コンテストレベルの数学的問題に強い性能を示してきたが、オープンな研究レベルの問題に対処する可能性はほとんど未解決のままである。
本研究では,スタイナー比のより厳密な下界を得るための新しいAIシステムを提案する。
本研究は, LLM が直接的に予測を解くのではなく, 実行可能コードとして実装された規則制約付き幾何補題を生成することを課題としている。
これらの補題は、スタイナー比の理論的に証明された下界をもたらす検証関数と呼ばれる特殊関数の集合を構成するために用いられる。
反射によって駆動されるプログレッシブ・レムマの精製により、このシステムはステイナー比の0.8559という新しい認証下限を定めている。
研究全体の成果は、高度な数学的研究のためのLLMベースのシステムの強い可能性を示す、わずか数千のLLMコールを含んでいる。
関連論文リスト
- MOOSE-Star: Unlocking Tractable Training for Scientific Discovery by Breaking the Complexity Barrier [56.250921274032066]
MOOSE-Starは、トラクタブルなトレーニングとスケーラブルな推論を可能にする統合フレームワークである。
TOMATO-Starは、トレーニング用に108717の分解された論文(38,400GPU時間)のデータセットである。
論文 参考訳（メタデータ） (2026-03-04T06:11:18Z) - Model-Based and Sample-Efficient AI-Assisted Math Discovery in Sphere Packing [51.30643063554434]
上界の先導手法である三点法は、大高精度半確定プログラム(SDP)の解法に問題を還元する。
我々は、SDP構成を、ポリシーが一連の許容成分からSDP定式化を組み立てる逐次決定過程、SDPゲームとして定式化する。
従来からある幾何学的問題において,モデルに基づく探索が計算の進歩を推し進めることができることを示す。
論文 参考訳（メタデータ） (2025-12-04T14:11:52Z) - SuperARC: An Agnostic Test for Narrow, General, and Super Intelligence Based On the Principles of Recursive Compression and Algorithmic Probability [0.14061979259370275]
アルゴリズムの確率を基礎としたオープンエンドテストを導入する。
これはフロンティアモデルの定量的評価においてベンチマーク汚染を避けることができる。
圧縮はシステムの予測力と等価であり、直接的に比例することを示す。
論文 参考訳（メタデータ） (2025-03-20T23:11:30Z) - Concurrent Learning with Aggregated States via Randomized Least Squares Value Iteration [40.73142019282658]
ランダム化を注入することは、環境を連続的に探索するエージェントの社会に役立てるかどうかを考察する。
有限および無限水平環境における最悪の後悔境界を示す。
我々は空間の複雑さを$K$の係数で減らし、最悪ケースの後悔の上限を$sqrtK$だけ増やす。
論文 参考訳（メタデータ） (2025-01-23T05:37:33Z) - Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。
特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
論文 参考訳（メタデータ） (2024-11-04T00:34:56Z) - Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints [8.784438985280094]
線形制約が未知の多腕バンディットにおける純粋探索として問題を研究する。
まず、制約下での純粋な探索のために、サンプルの複雑さを低く抑えたラグランジアン緩和を提案する。
第二に、ラグランジアンの下界と凸の性質を利用して、トラック・アンド・ストップとガミファイド・エクスプローラー(LATSとLAGEX)の2つの計算効率の良い拡張を提案する。
論文 参考訳（メタデータ） (2024-10-24T15:26:14Z) - The Complexity of Algebraic Algorithms for LWE [0.0]
我々は、LWEシステム上でのGr"オブナー基底計算の複雑さを研究するために、Arora-Geモデルを再検討する。
我々は、Semaev & TentiのGr"obner基底アルゴリズムを有限の正則性を持つ任意の系に一般化する。
論文 参考訳（メタデータ） (2024-02-12T17:59:26Z) - Provably Convergent Federated Trilevel Learning [19.15328400013401]
三段階学習は三段階最適化(TLO)とも呼ばれ、意思決定プロセスの強力なモデリングツールとして認識されている。
本稿では,TLO問題を解決するために,非同期なフェデレーショントリレベル最適化手法を提案する。
論文 参考訳（メタデータ） (2023-12-19T04:03:47Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。
Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:59:30Z) - Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth [1.9643748953805935]
コンベックス関数を$gamma-$Holderian成長下で最小化するために、完全かつ不正確なPPAの漸近複雑性を導出する。
数値実験では, 既存の再起動バージョンよりも改善が見られた。
論文 参考訳（メタデータ） (2021-08-10T07:15:07Z) - Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon
Reinforcement Learning? [108.94173231481355]
長い地平線を計画する学習は、エピソード強化学習問題における中心的な課題である。
長地平線RLは、少なくともミニマックス感覚において、短地平線RLよりも困難ではないことを示す。
論文 参考訳（メタデータ） (2020-05-01T17:56:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。