एका AI ने सोडवले रंगवण्याचे कोडे

रेषांनी जोडलेल्या बिंदूंचे एक जाळे घ्या — ज्याला गणितज्ञ आलेख (graph) म्हणतात. आता बिंदू असे रंगवा की रेषेने जोडलेल्या दोन बिंदूंचा रंग कधीही एकसारखा नसेल. हे शक्य करणारी रंगांची किमान संख्या म्हणजे त्या आलेखाची वर्णसंख्या (chromatic number). एक प्रसिद्ध विशेष उदाहरण म्हणजे 1977 मध्ये सिद्ध झालेले चार-रंग प्रमेय, ज्याचे शीर्षकच सगळे सांगते: “Every planar map is four colorable” (प्रत्येक सपाट नकाशा चार रंगांत रंगवता येतो).

हॅडविगरची 1943 ची पैज

1943 मध्ये, हॅडविगरने सर्व आलेखांसाठी एक व्यापक नियम सुचवला. बिंदू किंवा रेषा काढून टाकून, आणि जोडलेले दोन बिंदू एकत्र करून एक करून आलेख लहान करा. त्याच्या परिणामाला मायनर (minor) म्हणतात. अशा प्रकारे मिळू शकणाऱ्या सर्वात मोठ्या पूर्ण आलेखाकडे — असा समूह ज्यात प्रत्येक बिंदू इतर प्रत्येक बिंदूशी जोडलेला असतो — हॅडविगरने पाहिले, आणि लागणाऱ्या रंगांची संख्या त्या समूहाच्या आकारापेक्षा कधीही जास्त नसते असे अनुमान (conjecture) मांडले.

शोधनिबंध याला “आलेख सिद्धांतातील सर्वात जुन्या आणि सर्वात मूलभूत प्रश्नांपैकी एक” म्हणतो. तो फक्त लहान प्रकरणांसाठी सिद्ध झाला आहे: पाचपर्यंतच्या समूहांसाठी, जिथे तो चार-रंग प्रमेयाशी समतुल्य असल्याचे किंवा त्यात रूपांतरित करता येण्याजोगा असल्याचे दिसते. सहापासून पुढे, तो अनुत्तरित आहे.

एकेका लॉगॅरिदमने जवळ जाणे

नेमके विधान दाद देत नसल्याने, संशोधकांनी रंगांची संख्या समूहाच्या आकाराच्या एखाद्या फलाने, जे शक्य तितक्या सावकाश वाढेल अशा फलाने, मर्यादित करण्याचा प्रयत्न केला. शोधनिबंध ही प्रगती सांगतो. दशकानुदशके, सर्वोत्तम मर्यादा प्रमाणशीरपेक्षा थोडी वेगाने वाढत होती — एका लॉगॅरिदमच्या वर्गमुळाचा समावेश असलेल्या गुणकाने. काही वर्षांपूर्वी, नॉरिन (Norin), पोस्टल (Postle) आणि सॉंग (Song) यांनी तो अडसर तोडला. मग डेलकूर (Delcourt) आणि पोस्टल यांनी त्यात आणखी सुधारणा केली आणि, निर्णायकपणे, बऱ्यापैकी लहान आलेख हाताळणे पुरेसे आहे हे दाखवले. लिऊ (Liu) आणि लुओ (Luo) यांनी अतिरिक्त गुणक तिहेरी लॉगॅरिदमपर्यंत खाली आणला.

नैसर्गिक अंतिम टप्पा म्हणजे रेषीय हॅडविगर अनुमान: समूहाच्या आकाराची एक ठरावीक पट नेहमीच पुरेशी असते. मॉन्ट्रियलमधील मॅकगिल विद्यापीठाचे सर्गेई नॉरिन (Sergey Norin) आणि ETH झ्युरिकचे राफाएल श्टायनर (Raphael Steiner) आता हेच सिद्ध केल्याचा दावा करतात.

यंत्राने बजावलेली भूमिका

लेखक स्पष्ट सांगतात: सिद्धता OpenAI च्या GPT-6 Astra या प्रारूपाने, त्यांच्या सूचनांनुसार, शोधली. त्यांनी आधी त्याला अतिशय दाट आलेखांचे प्रकरण सिद्ध करायला सांगितले, जो हरवलेला तुकडा आहे असे त्यांना वाटत होते. ते यशस्वी झाले, ते लिहितात, “फक्त काही तासांनी आणि थोड्या प्रोत्साहनानंतर”. एक अवलंबित्व स्पष्ट करायला सांगितल्यावर, त्याने एका विशिष्ट आकारापर्यंतचे आलेख व्यापले — पण आवश्यक असलेली व्याप्ती पूर्णपणे नाही. मग त्यांनी ती दरी भरून काढण्यासाठी त्याच्याकडे एक मौलिक कल्पना मागितली, आणि त्यातून अंतिम सिद्धतेची “बूटस्ट्रॅप” पायरी निर्माण झाली. आकुंचनांबद्दलच्या (contractions) एका सूचनेव्यतिरिक्त, लेखकांच्या स्वतःच्या विशिष्ट सिद्धता-कल्पनांपैकी जवळजवळ कोणतीही टिकली नाही, असे ते म्हणतात.

लेखन माणसांचे आहे. OpenAI च्या आणखी एका प्रारूपाने मुद्रितशोधन आणि संदर्भसूचीत मदत केली. लेखक सांगतात की OpenAI च्या Codex ने Lean या सिद्धता-सहायकात संपूर्ण सिद्धतेची औपचारिक, यंत्राद्वारे तपासता येणारी आवृत्ती तयार केली, जी AI ने लिहिलेल्या सुरुवातीच्या मसुद्यासोबत ऑनलाइन टाकली आहे. गणिताची संपूर्ण जबाबदारी ते स्वतः घेतात.

सिद्धतेच्या आत

युक्तिवादाचे दोन भाग आहेत:

1. लहान आलेख, कमी रंग. समूह-मर्यादेपेक्षा फारसे मोठे नसलेल्या आलेखांसाठी, लेखक दाखवतात की समूहाच्या आकाराच्या सुमारे चौपट पुरेसे आहे. सुरुवातीचा बिंदू आहे रीड (Reed) आणि सेमूर (Seymour) यांचा 1998 चा निकाल: रंगवण्याचे एक शिथिल, “अपूर्णांकी” (fractional) रूप आधीच गुणक दोनसह रेषीय नियम पाळते. नवे काम आलेखात काही अतिरिक्त रेषा जोडून आणि एका सहायक रचनेत प्रचंड जुळण्या (matchings) शोधून अपूर्णांकी रंगवणे खऱ्या रंगवण्यात बदलते.
2. बूटस्ट्रॅप. दुसरा युक्तिवाद व्यापलेल्या आलेख-आकारांची व्याप्ती प्रत्येक पायरीवर घातांकात चार-तृतीयांश या गुणकाने वाढवतो, मोठ्या स्थिरांकाच्या मोबदल्यात. दहा पायऱ्या व्याप्ती एक तृतीयांशापासून सुमारे 5.92 पर्यंत नेतात, डेलकूर-पोस्टल रूपांतरणाला लागणाऱ्या 5 या उंबरठ्याच्या पलीकडे. हा भाग ग्यार्फाश (Gyárfás) यांची एक जुनी युक्ती वापरतो, जी या प्रश्नाला यापूर्वी कधीही लावली गेली नव्हती असे लेखक म्हणतात.

लेखक सिद्धतेचे वर्णन ज्ञात साधनांपासून बांधलेली असे करतात — “अस्तित्वात असलेल्या निकालांच्या बहिर्वक्र आवरणात (convex hull) सामावलेली”, तरीही त्याच्या एखाद्या उघड काठावर नसलेली.

काय अनुत्तरित राहते

स्थिरांक प्रचंड आहे: ढोबळ अंदाज सुमारे 10¹⁰⁰ देतो. लेखकांना तो 10¹⁰ च्या खाली आणण्यास वाव दिसतो, पण, समजा, 100 पर्यंत पोहोचण्यासाठी नव्या कल्पना लागतील असे त्यांना वाटते. हॅडविगरच्या नेमक्या अनुमानाला धक्काही लागलेला नाही: “आमचे अजून ठरलेले नाही,” ते लिहितात. शोधनिबंध हा प्रीप्रिंट आहे; नव्या गणिताच्या 41 पानांना आता इतर तज्ज्ञांच्या छाननीला सामोरे जावे लागेल.