💻 computer science

Towards Solving the Gilbert-Pollak Conjecture via Large Language Models

यह शोध पत्र एक ऐसे एआई (AI) सिस्टम को प्रस्तुत करता है जो निष्पादन योग्य ज्यामितीय लेम्मा (geometric lemmas) उत्पन्न करने और उन्हें परिष्कृत करने के लिए लार्ज लैंग्वेज मॉडल्स का लाभ उठाता है, जिससे स्टाइनर अनुपात (Steiner ratio) के लिए 0.8559 का एक नया प्रमाणित निचला स्तर प्राप्त हुआ है और यह जिल्बर्ट-पोलाक अनुमान (Gilbert-Pollak Conjecture) की ओर महत्वपूर्ण प्रगति करता है।

मूल लेखक: Yisi Ke, Tianyu Huang, Yankai Shu, Di He, Jingchu Gai, Liwei Wang

प्रकाशित 2026-05-22

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Yisi Ke, Tianyu Huang, Yankai Shu, Di He, Jingchu Gai, Liwei Wang

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक शहर के योजनाकार (city planner) हैं जो घरों के एक समूह को सड़कों से जोड़ना चाहते हैं। आपके पास इसे करने के दो तरीके हैं:

"प्रत्यक्ष" तरीका (न्यूनतम स्पैनिंग ट्री - Minimum Spanning Tree): आप घरों को सीधे एक-दूसरे से जोड़ते हैं। आप कोई नए चौराहे नहीं बना सकते; आप बस मौजूदा घरों के बीच रेखाएं खींचते हैं।
"स्मार्ट" तरीका (स्टाइनर मिनिमल ट्री - Steiner Minimal Tree): आपको शहर में कहीं भी नए, अदृश्य चौराहे (जिन्हें 'स्टाइनर पॉइंट्स' कहा जाता है) बनाने की अनुमति है। इन अतिरिक्त केंद्रों को जोड़कर, आप अक्सर एक ऐसा नेटवर्क बना सकते हैं जो प्रत्यक्ष तरीके की तुलना में छोटा और कम डामर (asphalt) का उपयोग करता है।

बड़ा सवाल:
"स्मार्ट" तरीका "प्रत्यक्ष" तरीके की तुलना में कितना छोटा हो सकता है?

1968 में, गणितज्ञों गिलबर्ट और पोलक ने एक प्रसिद्ध अनुमान लगाया था। उन्होंने कहा था: "चाहे आप घरों को किसी भी तरह से व्यवस्थित करें, स्मार्ट तरीका, प्रत्यक्ष तरीके की लंबाई के 86.6% (विशेष रूप से $\sqrt{3}/2$ ) से कम नहीं होगा।"

द दशकों तक, गणितज्ञों ने इसे सिद्ध करने की कोशिश की। वे यह सिद्ध करने में सफल रहे कि यह लंबाई का कम से कम 82.4% है, लेकिन वे वहीं अटक गए। यह गणितीय समस्या एक विशाल, उलझी हुई गांठ की तरह थी जिसे मानव मस्तिष्क सुलझा नहीं पा रहा था क्योंकि इसमें बहुत सारे संभावित आकार और कोणों की जांच करनी थी।

नया दृष्टिकोण: AI "लेम्मा फैक्ट्री" (Lemma Factory)
यह शोध पत्र बताता है कि कैसे एक AI (लार्ज लैंग्वेज मॉडल) इस गांठ को सुलझाने में मदद करता है। लेकिन AI पूरी समस्या को एक साथ हल करने की कोशिश नहीं करता है—यह वैसा ही है जैसे किसी रोबोट से एक सेकंड में पूरा उपन्यास लिखने के लिए कहना। इसके बजाय, शोधकर्ताओं ने उसके लिए एक विशेष 'फैक्ट्री' बनाई।

यहाँ यह प्रणाली कैसे काम करती है, इसे एक सरल उपमा (analogy) से समझते हैं:

1. "प्रमाण" (Proof) एक विशाल जिग्सॉ पहेली है

86.6% के नियम को सिद्ध करने के लिए, आपको सड़क नेटवर्क के हर संभावित आकार की जांच करनी होगी। यह एक-एक करके करना असंभव है।
इसके बजाय, गणितज्ञ 'इंडक्शन' (induction) नामक रणनीति का उपयोग करते हैं। वे कहते हैं: "यदि हम यह सिद्ध कर सकें कि जब भी हम नेटवर्क के एक टुकड़े को अलग करते हैं, तो बचा हुआ हिस्सा अभी भी नियमों का पालन करता है, तो पूरा हिस्सा भी नियमों का पालन करेगा।"

इसे करने के लिए, उन्हें 'लेम्मा' (lemmas) नामक छोटे, विशिष्ट नियमों की आवश्यकता होती है। लेम्मा को एक एकल, पूर्ण पहेली के टुकड़े के रूप में सोचें जो कहता है: "यदि सड़कें इस प्रकार दिखती हैं, तो हम निश्चित रूप से जानते हैं कि लंबाई कम से कम इतनी है।"

2. AI का काम: पहेली के टुकड़े बनाना

शोधकर्ताओं ने AI को पूरी पहेली हल करने के लिए नहीं कहा। उन्होंने उससे कुछ बहुत छोटा करने को कहा: कोड लिखना जो इन पहेली के टुकड़ों को बनाता है।

प्रतिबंध (Constraint): AI को बताया जाता है, "आप केवल ऐसा कोड लिख सकते हैं जो एक विशिष्ट ज्यामितीय आकार (जैसे कि 'ट्रैप्ड रेगुलर पॉइंट' या '4-पॉइंट ट्री') का वर्णन करता हो।"
आउटपुट: AI एक छोटा प्रोग्राम (एक "लेम्मा") लिखता है जो कहता है, "यदि सड़क की लंबाई $X, Y, Z$ है, तो कुल लंबाई $W$ द्वारा सीमित है।"
सुरक्षा जाल (Safety Net): AI के कोड पर आँख मूंदकर भरोसा नहीं किया जा सकता। इसे एक सख्त गणितीय कैलकुलेटर (जैसे कि 'मैथेमैटिका' नामक एक अत्यंत सटीक कैलकुलेटर) में डाला जाता है। यदि कैलकुलेटर कहता है कि कोड गलत है, तो AI फिर से प्रयास करता है। यदि यह कहता है "सही है," तो उस टुकड़े को संग्रह में जोड़ दिया जाता है।

3. "रिफ्लेक्शन" लूप: कमजोरियों को ढूंढना

यह सबसे चतुर हिस्सा है। यह प्रणाली केवल बेतरतीब ढंग से अनुमान नहीं लगाती है।

सिस्टम वर्तमान संग्रह के टुकड़ों का उपयोग करके 86.6% के नियम को सिद्ध करने का प्रयास करता है।
यह विफल हो जाता है। यह एक विशिष्ट "अवरोध" (bottleneck) पाता है—सड़कों का एक अजीब आकार जहाँ वर्तमान टुकड़े फिट नहीं बैठते।
सिस्टम AI को बताता है: "हे, तुम यहाँ विफल रहे। इस विशिष्ट आकार को देखो। जाओ और इस सटीक स्थान के लिए एक नया पहेली का टुकड़ा लिखो।"
AI एक नया लेम्मा बनाता है, कैलकुलेटर उसकी जांच करता है, और यदि वह काम करता है, तो सिस्टम फिर से प्रयास करता है।

यह एक वीडियो गेम की तरह है जहाँ आप बार-बार एक दीवार से टकराते हैं, और गेम आपको ठीक वही जगह बताता है जहाँ आपको आगे बढ़ने के लिए पुल बनाना है।

परिणाम

लगभग 10 दौर के इस "प्रयास करें, विफल हों, चिंतन करें, सुधारें" लूप के बाद, सिस्टम ने पहेली के टुकड़ों का एक ऐसा संग्रह बनाया जो इतना मजबूत था कि वह अंततः एक नया, अधिक सटीक नियम सिद्ध कर सका:

स्मार्ट तरीका, प्रत्यक्ष तरीके की लंबाई का कम से कम 85.59% है।

यह लगभग 40 वर्षों से चले आ रहे पिछले रिकॉर्ड (82.4%) की तुलना में एक बड़ी प्रगति है।

यह क्यों महत्वपूर्ण है (शोध पत्र के अनुसार)

यह सस्ता है: पूरा शोध प्रोजेक्ट कंप्यूटर समय में केवल कुछ सौ डॉलर की लागत आया।
यह तेज़ है: AI को वह करने में केवल कुछ दिन का "सोचने" का समय (और कुछ हज़ार कॉल) लगा जो इंसान दशकों में नहीं कर सके।
यह सटीक (Rigorous) है: AI ने केवल "अनुमान" नहीं लगाया। इसने ऐसा कोड तैयार किया जिसे गणितीय रूप से 100% सही प्रमाणित किया गया है। अंतिम प्रमाण एक मानक गणितीय प्रमाण है जो AI से स्वतंत्र होकर अपने आप में खड़ा है।

संक्षेप में: शोधकर्ताओं ने AI को एक प्रतिभाशाली गणितज्ञ बनने के लिए नहीं कहा। उन्होंने उसे एक कुशल, अथक सहायक बनने के लिए कहा जो छोटे, सत्यापित उपकरण (लेम्मा) बनाता है ताकि मनुष्यों को उस समस्या को हल करने में मदद मिल सके जो पहले सुलझाने के लिए बहुत बड़ी थी। उन्होंने एक "ब्लैक बॉक्स" AI को एक पारदर्शी, चरण-दर-चरण खोज इंजन में बदल दिया।

तकनीकी सारांश: लार्ज लैंग्वेज मॉडल्स के माध्यम से गिल्बर्ट-पोलक अनुमान (Gilbert-Pollak Conjecture) को हल करने की दिशा में

1. समस्या विवरण

यह शोध पत्र गिल्बर्ट-पोलक अनुमान (1968) को संबोधित करता है, जो कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन और कम्प्यूटेशनल ज्योमेट्री में एक महत्वपूर्ण खुला प्रश्न है। यह अनुमान प्रस्तावित करता है कि यूक्लिडियन प्लेन (Euclidean plane) में बिंदुओं के किसी भी परिमित सेट के लिए, स्टाइनर मिनिमल ट्री (SMT) और यूक्लिडियन मिनिमम स्पैनिंग ट्री (MST) की लंबाई के बीच का अनुपात $\sqrt{3}/2 \approx 0.866$ द्वारा निम्न-बद्ध (lower-bounded) है। इस अनुपात को स्टाइनर अनुपात (Steiner ratio) कहा जाता है।

जबकि इस अनुमान को कम संख्या में बिंदुओं ( $n \le 6$ ) के लिए सत्यापित किया गया है, किसी भी $n$ के लिए सामान्य निम्न-सीमा (general lower bound) 1985 के बाद से स्थिर रही है। पिछला स्टेट-ऑफ-द-आर्ट निम्न-सीमा, जिसे चुंग और ग्राहम (1985) द्वारा स्थापित किया गया था, 0.824 है। प्रगति विश्लेषण के लिए आवश्यक टोपोलॉजिकल संरचनाओं के कॉम्बिनेटोरियल विस्फोट और मैन्युअल व्युत्पत्ति में शामिल ज्यामितीय सत्यापन की जटिलता के कारण रुक गई है।

लेखक यह जांचते हैं कि क्या लार्ज लैंग्वेज मॉडल्स (LLMs), जिन्होंने प्रतियोगिता-स्तर की गणितीय दक्षता दिखाई है, को ऐसे खुले, अनुसंधान-स्तरीय अनुमानों को हल करने के लिए विस्तारित किया जा सकता है। वे नोट करते हैं कि LLMs को सीधे अनुमान को हल करने के लिए नैटिवली प्रॉम्प्ट करने से अक्सर हैलुसिनेशन (hallucinations) और तार्किक अंतराल उत्पन्न होते हैं, क्योंकि इसमें विशाल, अनियंत्रित खोज स्थान (search space) और प्रशिक्षण डेटा में अनुसंधान-स्तरीय अवधारणाओं की कमी होती है।

2. कार्यप्रणाली (Methodology)

लेखक एक नवीन AI प्रणाली का प्रस्ताव करते हैं जो सीधे एंड-टू-एंड प्रूफ जनरेशन से बचती है। इसके बजाय, प्रणाली समस्या को वेरिफिकेशन फंक्शन्स (verification functions) और रिफ्लेक्शन (reflection) द्वारा संचालित एक संरचित, पुनरावृत्ति खोज प्रक्रिया में विभाजित करती है।

2.1. सत्यापन ढांचा (The Verification Framework)

गणितीय रणनीति का मुख्य आधार एक इंडक्शन-आधारित रिडक्शन तर्क (Du & Hwang, 1983) है। एक निम्न-सीमा $\rho$ को सिद्ध करने के लिए, आपको यह दिखाना होगा कि किसी भी ज्यामितीय विन्यास $w$ के लिए, एक ट्री का एक विशिष्ट "विभाजन" (splitting) मौजूद है ताकि एक विशिष्ट स्प्लिटिंग फंक्शन $F_\tau(w, \rho) \le 0$ हो।

वेरिफिकेशन फंक्शन्स: निरंतर मिनिमैक्स समस्या को सुलभ बनाने के लिए, प्रणाली वेरिफिकेशन फंक्शन्स पेश करती है। ये स्प्लिटिंग फंक्शन्स के ऊपरी स्तर (upper bounds) हैं जो विशिष्ट संरचनात्मक बाधाओं (कोऑर्डिनेट एक्सिस के साथ यूनिमोडैलिटी) को पूरा करते हैं।
वर्टेक्स मैक्सिमम प्रॉपर्टी (Vertex Maximum Property): एक प्रमुख सैद्धांतिक योगदान इन वेरिफिकेशन फंक्शन्स के लिए यह सिद्ध करना है कि एक बाउंडेड हाइपररेक्टेंगल पर इनका ग्लोबल मैक्सिममम इसके किसी एक वर्टेक्स (शीर्ष) पर प्राप्त होता है। यह एक अनंत निरंतर डोमेन के सत्यापन को वर्टेक्स चेक्स के एक परिमित सेट में बदल देता है।
ब्रांच-एंड-बाउंड (Branch-and-Bound): प्रणाली पैरामीटर स्पेस को पुनरावर्ती रूप से विभाजित करने के लिए ब्रांच-एंड-बाउंड एल्गोरिदम का उपयोग करती है, जो वर्टेक्स पर स्थिति को सत्यापित करती है और अनबाउंडेड क्षेत्रों के लिए मोनोटोनिसिटी की जाँच करती है।

2.2. LLM एजेंट और लेम्मा जनरेशन (Lemma Generation)

LLM से सीधे अनुमान सिद्ध करने के बजाय, प्रणाली उसे नियम-प्रतिबंधित ज्यामितीय लेम्मा (rule-constrained geometric lemmas) उत्पन्न करने का कार्य देती है जिन्हें निष्पादन योग्य कोड के रूप में लागू किया जाता है। खोज स्थान को दो विशिष्ट प्रकार के लेम्मा तक सीमित किया गया है:

ट्रैप्ड रेगुलर पॉइंट लेम्मा (Trapped Regular Point Lemmas): यह सिद्ध करना कि कुछ रैखिक बाधाओं के तहत, एक निहित रेगुलर पॉइंट एक बाउंडेड पॉलिगोनल क्षेत्र के भीतर सीमित है, जिससे दूरी की सीमाएं निर्धारित की जा सकें।
वैलिड 4-पॉइंट स्टाइनर ट्री लेम्मा (Valid 4-Point Steiner Tree Lemmas): यह सिद्ध करना कि विशिष्ट ऑर्थोगोनली कॉन्वेक्स स्थितियों के तहत, एक विशिष्ट 4-पॉइंट स्टाइनर ट्री टोपोलॉजी वैध है, जिससे सटीक लंबाई की गणना संभव हो सके।

LLM एजेंट एक लूप में कार्य करता है:

चयन (Selection): यह एक पूर्व-निर्धारित सेट से प्रासंगिक ज्यामितीय प्रेडिकेट्स (प्रकार A: अंतर्निहित गुण; प्रकार B: पर्याप्त ट्रैपिंग स्थितियां) का चयन करता है।
व्युत्पत्ति (Derivation): यह प्रेडिकेट्स के निहितार्थों को निकालने के लिए सिम्बोलिक टूल्स (Mathematica) का उपयोग करता है।
सरलीकरण (Simplification): यह जटिल बीजगणितीय क्षेत्रों को रैखिक या ऑर्थोगोनली कॉन्वेक्स बाधाओं में सरल बनाता है जो रिवॉर्ड मॉडल के अनुकूल हों।
कोडिंग (Coding): यह व्युत्पन्न शर्तों को C++ फंक्शन्स (X_cond, AX_upper_bound, आदि) के रूप में आउटपुट करता है जो वेरिफिकेशन फंक्शन्स के रूप में कार्य करते हैं।

2.3. पुनरावृत्ति प्रतिबिंब तंत्र (Iterative Reflection Mechanism)

प्रणाली बाधाओं को दूर करने के लिए एक लक्षित रिफ्लेक्शन तंत्र का उपयोग करती है:

मूल्यांकन (Evaluation): रिवॉर्ड मॉडल एक उम्मीदवार निम्न-सीमा $\rho$ को प्रमाणित करने का प्रयास करता है।
बाधा पहचान (Bottleneck Identification): यदि सत्यापन विफल रहता है, तो प्रणाली विशिष्ट "बॉटलनेक क्षेत्र" (अनसर्टिफाइड हाइपररेक्टेंगल का एक सेट) की पहचान करती है जहाँ वर्तमान लेम्मा अपर्याप्त हैं।
फीडबैक (Feedback): इस क्षेत्र को एक संरचित प्रॉम्प्ट में बदल दिया जाता है, जो LLM को विशेष रूप से उस बॉटलनेक के ज्यामितीय बाधाओं को लक्षित करने वाले नए लेम्मा बनाने का निर्देश देता है।
परिष्करण (Refinement): नए लेम्मा को मान्य किया जाता है और वेरिफिकेशन फंक्शन्स के सेट में जोड़ा जाता है, और प्रक्रिया दोहराई जाती है।

3. मुख्य योगदान

सैद्धांतिक खोज के लिए नवीन AI प्रणाली: यह शोध पत्र एक ऐसी प्रणाली प्रस्तुत करता है जो दशकों पुराने खुले प्रश्न के लिए मध्यवर्ती ज्यामितीय लेम्मा की खोज को सफलतापूर्वक स्वचालित करती है, जो मानक प्रतियोगिता-स्तर की समस्या समाधान से कहीं आगे है।
वेरिफिकेशन फंक्शन्स और वर्टेक्स प्रॉपर्टी: लेखक वेरिफिकेशन फंक्शन्स को औपचारिक रूप से परिभाषित करते हैं और "वर्टेक्स मैक्सिमम प्रॉपर्टी" को सिद्ध करते हैं, जो निरंतर डोमेन पर निम्न-सीमाओं के कठोर और कम्प्यूटेशनल रूप से सुलभ सत्यापन को सक्षम बनाता है।
विघटन रणनीति (Decomposition Strategy): पूर्ण प्रमाण के बजाय विशिष्ट, नियम-प्रतिबंधित लेम्मा (ट्रैप्ड पॉइंट्स और वैलिड 4-पॉइंट ट्री) के जनरेशन में समस्या को विभाजित करके, प्रणाली प्रभावी रूप से खोज स्थान को प्रबंधित करती है और हैलुसिनेशन को कम करती है।
बॉटलनेक-संचालित रिफ्लेक्शन: एक ऐसा रिफ्लेक्शन तंत्र जो जेनेरिक सेल्फ-करेक्शन के बजाय, उन विशिष्ट ज्यामितीय क्षेत्रों की पहचान करता है और उन्हें लक्षित करता है जो आगे के सुधार को रोक रहे हैं।

4. परिणाम

नई निम्न-सीमा (New Lower Bound): सिस्टम ने स्टाइनर अनुपात की प्रमाणित निम्न-सीमा को चुंग और ग्राहम (1985) के 0.824 से बढ़ाकर 0.8559 कर दिया।
दक्षता (Efficiency): संपूर्ण शोध कार्य को रिफाइनमेंट लूप के लगभग 10 पुनरावृत्तियों की आवश्यकता पड़ी।
संसाधन उपयोग (Resource Usage): इस प्रक्रिया में लगभग हजारों LLM कॉल्स शामिल थे और लगभग 4.6 घंटे के रीजनिंग समय में लगभग 0.5 मिलियन टोकन (लगभग 35K प्रति राउंड) का उपभोग हुआ। कुल कम्प्यूटेशनल लागत कुछ सौ डॉलर थी।
मजबूती (Robustness): विभिन्न LLM बैकबोन (GPT-5 और Gemini 3 Pro) का उपयोग करने वाले प्रयोगों ने समान निम्न-सीमा पर सुसंगत अभिसरण (convergence) दिखाया, जो मॉडल चयन के प्रति फ्रेमवर्क की मजबूती को प्रदर्शित करता है।
सत्यापन (Verification): सभी जनरेटेड लेम्मा की मैन्युअल रूप से शुद्धता के लिए जांच की गई थी, और अंतिम निम्न-सीमा को सिम्बोलिक टूल्स (Cylindrical Algebraic Decomposition) का उपयोग करके पूरे पैरामीटर स्पेस में कठोरता से सत्यापित किया गया था।

5. महत्व और दावे

शोध पत्र उन्नत गणितीय अनुसंधान के लिए LLM-आधारित प्रणालियों की मजबूत क्षमता को प्रदर्शित करने का दावा करता है, विशेष रूप से उन डोमेन में जिनमें गहन ज्यामितीय अंतर्ज्ञान और कॉम्बिनेटोरियल खोज की आवश्यकता होती है।

स्केलेबिलिटी (Scalability): लेखक तर्क देते हैं कि उनका दृष्टिकोण एक स्केलेबल प्रतिमान (paradigm) प्रदान करता है जहाँ LLMs रचनात्मक खोज और लेम्मा जनरेशन को संभालते हैं, जबकि सिम्बोलिक टूल्स औपचारिक सत्यापन को संभालते हैं। यह श्रम का विभाजन दोनों की शक्तियों का लाभ उठाता है।
सुलभता (Accessibility): केवल कुछ सौ डॉलर की कुल लागत के साथ, यह कार्य सुझाव देता है कि LLM-सहायता प्राप्त सैद्धांतिक अनुसंधान उन शोधकर्ताओं के लिए भी सुलभ है जिनके पास बड़े कंप्यूट बजट नहीं हैं।
सामान्यीकरण (Generalizability): लेखक दो डिजाइन सिद्धांतों का प्रस्ताव करते हैं जिन्हें वे अन्य गणितीय खोज समस्याओं पर स्थानांतरित होने योग्य मानते हैं:
1. एक संरचित रीजनिंग स्पेस का निर्माण करना, समस्या को एंड-टू-एंड प्रमाण के बजाय पैरामीटराइज्ड लेम्मा में विभाजित करके।
2. स्थानीयकृत वेरिफायर विफलताओं पर रिफ्लेक्ट करना, विशिष्ट बॉटलनेक क्षेत्रों को मॉडल में फीड करके लक्षित परिष्करण को निर्देशित करना।

शोध पत्र अपने अंतिम परिणाम के संबंध में विनम्रता बनाए रखता है, यह नोट करते हुए कि हालांकि निम्न-सीमा में महत्वपूर्ण सुधार हुआ है, लेकिन स्वयं अनुमान (0.866) अभी भी अप्रमाणित है। इसके अलावा, लेखक वर्तमान सीमाओं को स्वीकार करते हैं, जैसे कि लेम्मा की शुद्धता के लिए मानव सत्यापन पर निर्भरता और उच्च-आयामी या अधिक जटिल टोपोलॉजी के लिए सिम्बोलिक सत्यापन (CAD) की स्केलेबिलिटी संबंधी समस्याएं। वे सुझाव देते हैं कि भविष्य के कार्यों में पूरी तरह से स्वायत्त खोज प्राप्त करने के लिए औपचारिक प्रूफ असिस्टेंट (जैसे कि Lean) का उपयोग किया जा सकता है।