एक AI ने सुलझाई रंग भरने की पहेली

रेखाओं से जुड़े बिंदुओं का एक जाल लीजिए — जिसे गणितज्ञ ग्राफ़ कहते हैं। अब बिंदुओं को ऐसे रंगिए कि किसी रेखा से जुड़े दो बिंदुओं का रंग कभी एक न हो। जितने कम से कम रंगों से यह हो जाए, वह ग्राफ़ की वर्णिक संख्या (chromatic number) है। एक प्रसिद्ध विशेष मामला चार-रंग प्रमेय है, जो 1977 में सिद्ध हुआ, और जिसका शीर्षक ही सब कुछ कह देता है: “Every planar map is four colorable” (हर समतल नक़्शे को चार रंगों में रंगा जा सकता है)।

हैडविगर का 1943 का दाँव

1943 में, हैडविगर (Hadwiger) ने सभी ग्राफ़ों के लिए एक व्यापक नियम सुझाया। किसी ग्राफ़ को बिंदु या रेखाएँ हटाकर, और दो जुड़े बिंदुओं को एक में मिलाकर छोटा कीजिए। नतीजे को माइनर (minor) कहते हैं। हैडविगर ने उस सबसे बड़े पूर्ण ग्राफ़ को देखा — एक ऐसा समूह जिसमें हर बिंदु बाक़ी हर बिंदु से जुड़ा हो — जो इस तरह पाया जा सकता है, और अनुमान लगाया कि ज़रूरी रंगों की संख्या कभी उस समूह के आकार से ज़्यादा नहीं होती।

शोधपत्र इसे “ग्राफ़ सिद्धांत की सबसे पुरानी और सबसे बुनियादी समस्याओं में से एक” कहता है। यह सिर्फ़ छोटे मामलों के लिए सिद्ध है: पाँच तक के समूहों के लिए, जहाँ यह चार-रंग प्रमेय के बराबर या उसमें बदला जा सकने वाला निकलता है। छह से आगे, यह खुला है।

एक-एक लघुगणक करके क़रीब पहुँचना

चूँकि सटीक कथन हाथ नहीं आता, शोधकर्ताओं ने रंगों की संख्या को समूह के आकार के किसी ऐसे फलन से बाँधने की कोशिश की जो जितना हो सके उतना धीरे बढ़े। शोधपत्र प्रगति का ब्योरा देता है। दशकों तक, सबसे अच्छी सीमा अनुपात से थोड़ा तेज़ बढ़ती रही — एक ऐसे गुणक से जिसमें एक लघुगणक का वर्गमूल शामिल था। कुछ साल पहले, नोरिन, पोस्टल और सॉन्ग (Norin, Postle, Song) ने वह बाधा तोड़ी। फिर डेलकोर्ट और पोस्टल (Delcourt, Postle) ने इसे और सुधारा और, सबसे अहम, दिखाया कि काफ़ी छोटे ग्राफ़ों से निपटना ही पर्याप्त है। लियू और लुओ (Liu, Luo) ने अतिरिक्त गुणक को घटाकर तिहरे लघुगणक तक ला दिया।

स्वाभाविक मंज़िल है रैखिक हैडविगर अनुमान (linear Hadwiger conjecture): समूह के आकार का एक निश्चित गुणज हमेशा काफ़ी होता है। यही बात मॉन्ट्रियल की मैकगिल यूनिवर्सिटी के सर्गेई नोरिन (Sergey Norin) और ETH ज़्यूरिख़ के राफ़ाएल श्टाइनर (Raphael Steiner) अब सिद्ध करने का दावा करते हैं।

मशीन की भूमिका

लेखक साफ़ कहते हैं: उपपत्ति OpenAI के एक मॉडल, GPT-6 Astra, ने उनके निर्देशों पर चलते हुए खोजी। पहले उन्होंने उससे बहुत घने ग्राफ़ों का मामला सिद्ध करने को कहा, जिसे वे ग़ायब टुकड़ा मानते थे। वे लिखते हैं कि वह “सिर्फ़ कुछ घंटों और थोड़े प्रोत्साहन के बाद” सफल हो गया। जब उससे एक निर्भरता को स्पष्ट करने को कहा गया, तो उसने एक ख़ास आकार तक के ग्राफ़ों को कवर किया — पर ज़रूरी दायरे तक पूरी तरह नहीं। फिर उन्होंने उससे इस अंतर को पाटने के लिए एक मौलिक विचार माँगा, जिससे अंतिम उपपत्ति का “बूटस्ट्रैप” चरण निकला। वे कहते हैं कि संकुचनों (contractions) के बारे में एक सुझाव को छोड़कर, लेखकों के अपने ख़ास उपपत्ति-विचारों में से लगभग कोई नहीं बचा।

लेखन इंसानी है। OpenAI के एक और मॉडल ने प्रूफ़रीडिंग और संदर्भ-सूची में मदद की। लेखक बताते हैं कि OpenAI के Codex ने Lean उपपत्ति-सहायक में पूरी उपपत्ति का एक औपचारिक, मशीन से जाँचा जा सकने वाला संस्करण तैयार किया, जिसे AI के लिखे एक शुरुआती मसौदे के साथ ऑनलाइन डाला गया है। गणित की पूरी ज़िम्मेदारी वे ख़ुद लेते हैं।

उपपत्ति के अंदर

तर्क के दो हिस्से हैं:

1. छोटे ग्राफ़, कम रंग। उन ग्राफ़ों के लिए जो समूह-सीमा से बहुत बड़े नहीं हैं, लेखक दिखाते हैं कि समूह के आकार का लगभग चार गुना काफ़ी है। शुरुआत रीड और सीमोर (Reed, Seymour) के 1998 के एक नतीजे से होती है: रंग भरने का एक ढीला, “भिन्नात्मक” रूप पहले से ही गुणक दो के साथ रैखिक नियम का पालन करता है। नया काम ग्राफ़ में कुछ अतिरिक्त रेखाएँ जोड़कर और एक सहायक संरचना में विशाल मिलान (matchings) खोजकर भिन्नात्मक रंगाई को असली रंगाई में बदलता है।
2. एक बूटस्ट्रैप। दूसरा तर्क हर चरण में कवर किए गए ग्राफ़-आकारों के दायरे को घातांक में चार-तिहाई के गुणक से बढ़ाता है, बदले में स्थिरांक बड़ा हो जाता है। दस चरण दायरे को एक-तिहाई से लगभग 5.92 तक ले जाते हैं, जो डेलकोर्ट-पोस्टल न्यूनीकरण के लिए ज़रूरी 5 की दहलीज़ से आगे है। यह हिस्सा ग्यारफ़ाश (Gyárfás) की एक पुरानी तरकीब का इस्तेमाल करता है, जो लेखकों के अनुसार इस समस्या पर पहले कभी लागू नहीं की गई थी।

लेखक उपपत्ति को ज्ञात औज़ारों से बनी बताते हैं — “मौजूदा नतीजों के उत्तल आवरण (convex hull) के भीतर”, फिर भी उसके किसी स्पष्ट किनारे पर नहीं।

क्या खुला रह गया

स्थिरांक विशाल है: एक मोटा अनुमान लगभग 10¹⁰⁰ देता है। लेखकों को इसे 10¹⁰ से नीचे लाने की गुंजाइश दिखती है, लेकिन उनका मानना है कि इसे, मान लीजिए, 100 तक लाने के लिए नए विचार चाहिए होंगे। हैडविगर का सटीक अनुमान अछूता है: “हम अनिर्णीत हैं,” वे लिखते हैं। यह शोधपत्र एक प्रीप्रिंट है; नए गणित के 41 पन्नों को अब दूसरे विशेषज्ञों की कड़ी जाँच से गुज़रना होगा।