गणितप्रीप्रिंटसिद्धांतवाचनासाठी ३ मिनिटे

AI ची सिद्धता, माणसांसाठी पुन्हा रेखाटलेली

काही बिंदू काढा आणि त्यांपैकी काहींना रेषांनी जोडा. गणितज्ञ याला आलेख (graph) म्हणतात; बिंदू म्हणजे शिरोबिंदू, रेषा म्हणजे कडा, आणि एखाद्या बिंदूला स्पर्श करणाऱ्या रेषांची संख्या म्हणजे त्याची कोटी (degree). वृक्ष म्हणजे असा आलेख ज्यात एकही वळसा नसतो आणि जो एका तुकड्यात एकसंध राहतो, फांद्या फुटलेल्या डहाळीसारखा; t बिंदू असलेल्या वृक्षात नेहमी t − 1 रेषा असतात.

1960 च्या दशकाच्या सुरुवातीला, पॉल एर्डोश आणि व्हेरा टी. शोश यांनी एक साधा प्रश्न विचारला: किती रेषा असल्या की आलेखात दिलेल्या आकाराचा प्रत्येक वृक्ष असलाच पाहिजे? त्यांचे उत्तर, म्हणजे एर्डोश–शोश अटकळ (Erdős–Sós conjecture), अशी आहे:

जर एखाद्या आलेखाची सरासरी कोटी t − 2 पेक्षा जास्त असेल, तर त्यात t शिरोबिंदू असलेला प्रत्येक वृक्ष असतो.

ही मर्यादा नेमकी आहे. t − 1 बिंदूंच्या, प्रत्येक जोडी जोडलेल्या, पूर्ण आलेखाच्या वेगवेगळ्या प्रती घ्या: प्रत्येक बिंदूला नेमके t − 2 शेजारी असतात, तरीही कोणताही तुकडा t बिंदूंचा वृक्ष सामावण्याइतका मोठा नसतो. अडचण आहे सरासरी या शब्दात. प्रत्येक बिंदूला किमान t − 1 शेजारी असते, तर फांदीमागून फांदी वृक्ष सहज बसवता आला असता. पण सरासरी कोणत्याही एका बिंदूबद्दल काहीच सांगत नाही: काहींना शेकडो शेजारी असू शकतात, तर इतरांना जवळजवळ एकही नाही.

साठ वर्षांची अर्धवट उत्तरे

शोधनिबंधात सांगितलेल्या इतिहासानुसार, हा प्रश्न 1962–1964 चा आहे आणि दिलेला नमुना निर्माण होण्यासाठी किती कडा लागतात याचा अभ्यास करणाऱ्या गणितशाखेत तो केंद्रस्थानी आला. विशेष प्रकरणे एकामागून एक सुटली: तारे, मार्ग, दुहेरी तारे, कमी फांद्या असलेले वृक्ष. 1990 च्या दशकाच्या सुरुवातीला, चार गणितज्ञांनी — आयताई, कोमलोश, सिमोनोवित्स आणि सेमेरेडी — खूप मोठ्या वृक्षांसाठी सिद्धतेची घोषणा केली, पण अलीकडील शोधनिबंध नमूद करतात की त्याचे संपूर्ण हस्तलिखित कधीच प्रसिद्ध झाले नाही. आणखी अर्धवट निकाल 2021, 2024 आणि 2026 मध्ये आले. 4 सप्टेंबर 2026 रोजी, रीड आणि स्टाइन यांनी मोठ्या, दाट आलेखांसाठी एक सिद्धता प्रसिद्ध केली, जी AI शिवाय विकसित केल्याचे ते सांगतात.

मग एक अहवाल आला. सप्टेंबर 2026 मध्ये, टॉम आदामचेव्स्की आणि थॉमस ब्लूम यांनी FrontierMath Erdős नावाच्या दस्तऐवजात संपूर्ण अटकळीची सिद्धता GPT-6 Astra या AI प्रारूपाच्या प्रकाशनपूर्व आवृत्तीला श्रेय म्हणून दिली. मूळ गणनेचा युक्तिवाद सार्वजनिक आहे, आणि सोबतच्या एका भांडारात (repository) सिद्धतेसाठी AI ने स्वायत्तपणे केलेला शोध आणि Lean या सिद्धता-तपासणी भाषेतील औपचारिक पडताळणी नोंदवलेली आहे. अहवालाच्या लेखकांनी मानवी तज्ज्ञांना अधिक सविस्तर, पारंपरिक विवेचने लिहिण्याचे आवाहनही केले.

एका वेळी एक बिंदू उघड करत आलेख

कॅलिफोर्निया स्टेट युनिव्हर्सिटी, सॅक्रामेंटो येथील जे कमिंग्स त्या आवाहनाला उत्तर देतात. त्यांचा 27 पानांचा लेख AI चा मध्यवर्ती गणनेचा युक्तिवाद कायम ठेवतो, पण तो सांगण्याची पद्धत बदलतो:

  1. आलेख हळूहळू उघड करा. शिरोबिंदूंची एका विशिष्ट क्रमाने यादी करा आणि ते एकामागून एक उघड करा, सोबत आधीच दाखवलेल्या बिंदूंमधील कडाही.
  2. अधिक मागा. वृक्षाची कोणतीही प्रत शोधण्याऐवजी, अशी प्रत शोधा जिचे निवडलेले “मूळ” (root) अगदी पहिल्या शिरोबिंदूवर बसते. अधिक मागितल्याने सिद्धता सोपी होते.
  3. लवकर आलेले शेजारी मोजा. हे पहिल्या शिरोबिंदूचे असे शेजारी आहेत जे अशी प्रत दिसण्याच्या आधी येतात. प्रत्येक शक्य क्रमासाठी त्यांची बेरीज करा.
  4. एकूण संख्येला मर्यादा घाला. शिरोबिंदूंची किंवा क्रमातील संपूर्ण गटांची अदलाबदल करून — अशा चाली ज्या नेहमी उलटवता येतात — कमिंग्स दाखवतात की सर्व क्रमांवर सरासरी काढल्यास, लवकर आलेले शेजारी जास्तीत जास्त t − 2 असतात.

शेवटची पायरी छोटी आहे. जर आलेखात वृक्षाची एकही प्रत नसेल, तर पहिल्या शिरोबिंदूचा प्रत्येक शेजारी, प्रत्येक क्रमात, लवकर आलेला ठरेल. सर्व क्रमांवर सरासरी काढल्यास, ती नेमकी सरासरी कोटी असते — जी गृहीतकानुसार t − 2 पेक्षा जास्त आहे. विरोधाभास: वृक्ष तिथे असलाच पाहिजे.

ही सिद्धता फक्त कोटींची बेरीज वापरते, त्या कशा विखुरलेल्या आहेत हे नव्हे. कमिंग्स एक संभाव्यतावादी आवृत्तीही देतात, आणि चार आणि पाच शिरोबिंदूंचे वृक्ष ठोस आलेखांवर सोडवून दाखवतात.

सिद्धतेचे एक चित्र-पुस्तक

या लेखात 32 आकृत्या आहेत. तो एका अभिजात परिणामाने संपतो: पूर्ण आलेखाच्या सर्व रेषा q रंगांनी रंगवा, आणि आलेखात q(t − 2) + 2 शिरोबिंदू झाले की कोणत्यातरी एका रंगात दिलेला वृक्ष नेहमी असेल. शेवटच्या निवेदनात, कमिंग्स स्पष्ट करतात की त्यांनी हा मजकूर ChatGPT शी दीर्घ संवाद करत विकसित केला, की मांडणीच्या नव्या कल्पना — लवकर आलेले शेजारी, स्पष्ट विभाजने, रेखाचित्रे — त्यांच्या स्वतःच्या आहेत, आणि की त्यांनी सर्व काही तपासले असून पूर्ण जबाबदारी ते स्वीकारतात.

ते आपल्या विवेचनाची तुलना रिओर्डन आणि स्कॉट, वुड आणि फ्रेडरिक्सन यांच्या इतर अलीकडील विवेचनांशी करतात, आणि नमूद करतात की ही पद्धत आधीच दिशा असलेल्या जाळ्यांपर्यंत आणि “अधिआलेखांपर्यंत” (hypergraphs) विस्तारली गेली आहे, आणि त्यांपैकी काही विस्तारांचे श्रेयही GPT-6 Astra ला दिले गेले आहे. ते लिहितात की त्यांचे योगदान म्हणजे “युक्तिवादाचे वाचककेंद्री, दृश्य विवेचन, अटकळीचे नवे निराकरण नव्हे.”