22 वर्षांच्या शंकेनंतर संदेश मिसळणे ते वाहून नेण्यापेक्षा सरस ठरले

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

प्रश्न असा आहे की या स्वातंत्र्यामुळे कधी जास्त माहिती पुढे जाऊ शकते का. शोधनिबंध दिशाहीन (अनडायरेक्टेड) नेटवर्क्सवर लक्ष केंद्रित करतो, जिथे केबल कोणत्याही दिशेने माहिती वाहून नेऊ शकते पण दोन्ही दिशा एकच क्षमता वाटून घेतात.

एकामागून एक प्रकरणांत खरी ठरलेली अटकळ

2004 मध्ये ली (Li) आणि ली (Li) यांनी अटकळ मांडली की या परिस्थितीत कोडिंग अपूर्णांकी राउटिंगपेक्षा (फ्रॅक्शनल राउटिंग) कोणताही फायदा देत नाही; हार्वी (Harvey), क्लाइनबर्ग (Kleinberg) आणि रसाला लेहमन (Rasala Lehman) यांनी स्वतंत्रपणे हीच अटकळ मांडली. पुढच्या दोन दशकांत ती नेटवर्क्सच्या एकामागून एक वर्गासाठी खरी ठरत गेली — दोन सत्रे, काही समतलीय नेटवर्क्स, जास्तीत जास्त सहा कोडिंग नोड्स असलेली नेटवर्क्स, आणि आणखी — पण सर्वसाधारणपणे तिचा निकाल कधीच लागला नाही. संगणनाच्या जटिलता-सिद्धांतातील इतर निकाल, जसे बाह्य स्मृतीत पूर्णांकांच्या क्रमवारीसाठी आणि गुणाकार-परिपथांसाठीच्या खालच्या मर्यादा, तर ती गृहीत धरून सिद्ध केले गेले होते.

ज्ञात सिद्धांताने आधीच पणाला लागलेल्या गोष्टींना मर्यादा घातली होती: कोडिंग राउटिंगपेक्षा जास्तीत जास्त लॉगरिदमिक पटीनेच सरस ठरू शकते. आणि ब्रेव्हरमन (Braverman), गर्ग (Garg) आणि श्वार्ट्झमन (Schvartzman) यांच्या 2017 च्या एका निकालाने दाखवले होते की कोडिंगला काटेकोर फायदा असलेले एकच नेटवर्क सापडले तरी ते खूप मोठ्या अंतरात विस्तारता येईल. सगळे काही एक मर्यादित उदाहरण शोधण्यावर येऊन ठेपले होते.

बेरीज पुरेशी आहे

परिशिष्टात मूलभूत युक्ती दिली आहे, जी मिसळणे का मदत करू शकते हे दाखवते. एका केंद्र v भोवती अनेक स्रोत ठेवा, त्यांचे प्राप्तकर्ते दुसऱ्या केंद्र w भोवती, आणि v व w ला एका केबलने जोडा. प्रत्येक स्रोताकडे इतर प्राप्तकर्त्यांकडे जाणारे लहान बाजूचे मार्गही आहेत. तीन फेऱ्यांमध्ये मधली केबल सर्व संदेशांची बेरीज वाहून नेते; प्रत्येक प्राप्तकर्त्याला ती बेरीज आणि बाजूच्या मार्गांवरून आलेले इतर संदेश मिळतात, आणि वजाबाकी करून तो आपला संदेश परत मिळवतो. मधल्या केबलशिवाय प्रत्येक स्रोत त्याच्या प्राप्तकर्त्यापासून पाच टप्पे (हॉप्स) दूर असतो.

हाउप्लर (Haeupler), वाइट्स (Wajc) आणि झुझिच (Zuzic) यांच्या आधीच्या कामातील ही युक्ती कोडिंगला जलद बनवते, पण केवळ तिच्या जोरावर अधिक वाहून नेता येत नाही: लांब मार्गावरही उच्च दराची पाइपलाइन चालवता येते.

नेटवर्कमध्ये बदललेला परिपथ

टोरांटो विद्यापीठातील शिनदान झांग (Xindan Zhang) आणि बाओचुन ली (Baochun Li), तसेच सिंगहुआ विद्यापीठातील झोंगपेंग ली (Zongpeng Li) यांनी हरवलेली पायरी शोधली. ते एका लहान कोडला उलटवता येणाऱ्या गणनेत बदलतात — उलटवता येणाऱ्या पूर्णांक-बेरजांचा एक परिपथ, जो गणना करतो, निकालाची प्रत काढतो, आणि मग आपले मधले काम पूर्ववत करतो. मग ते एक नवे नेटवर्क तयार करतात ज्याच्या भौतिक केबल्स त्या परिपथाच्या तारा आहेत, आणि गणनेतील प्रत्येक रजिस्टरला, कच्च्या कामाच्या रजिस्टर्ससह, स्वतःची प्रेषक–प्राप्तकर्ता मागणी देतात.

तारांलगत “वेळेचा” काळजीपूर्वक हिशोब बाकीचे काम करतो. सर्व तारांवर बेरीज केल्यास लांबी मागण्यांना पार कराव्या लागणाऱ्या किमान अंतरांशी तंतोतंत जुळते. पण नेमून दिलेल्या मागण्या काही विशिष्ट गेट्स टाळू शकत नाहीत, ज्यांची किंमत दोन अतिरिक्त एकके असते. त्यामुळे राउटिंग पूर्ण दरापासून काटेकोरपणे कमी पडते, तर कोड प्रत्येक केबल नेमकी एकदाच वापरतो आणि अनेक ब्लॉक्सवर पाइपलाइन केल्यास एकच्या दराजवळ पोहोचतो.

काय सिद्ध झाले

एक मर्यादित जोडलेले नेटवर्क, ज्यात प्रत्येक नोड जास्तीत जास्त तीन इतर नोड्सशी जोडलेला आहे आणि प्रत्येक केबलची क्षमता एक एकक आहे, ज्यावर एक साधा द्विमान रेषीय कोड शक्य तितक्या सर्वोत्तम अपूर्णांकी राउटिंगलाही मागे टाकतो. 2004 ची अटकळ चुकीची आहे.
हीच पूर्णांक-रचना प्रत्येक मर्यादित क्षेत्रावर (फील्ड) आणि प्रत्येक अक्षुल्लक मर्यादित आबेलियन गटावर एकाच वेळी चालते.
प्रतींना पुनःपुन्हा एकत्र करून लेखक नेटवर्क्सची अनंत कुटुंबे तयार करतात, जिथे कोडिंग पूर्ण दराजवळ पोहोचते तर राउटिंग 1/log n च्या एखाद्या घातासारखे घसरते — एक पॉलिलॉगरिदमिक फायदा.

शोधनिबंध आपल्या प्रतिउदाहरणातील नोड्सची संख्या देत नाही. त्याचा केवळ मूलभूत घटकच 13,122 फेऱ्या चालणारा कोड आहे.

यंत्राने तपासलेले

मर्यादित प्रतिउदाहरण आणि कुटुंबाविषयीचे प्रमेय, दोन्ही Lean या सिद्धता-सहाय्यकात औपचारिक केले आहेत. लेखकांच्या मते, 2,472 घोषणा आणि 1,755 प्रमेयांच्या तपासणीत दिसते की सिद्धता फक्त Lean ची तीन मानक स्वयंसिद्धे वापरतात, कोणतीही अपूर्ण सिद्धता नाही; नव्या वातावरणातील एक स्वतंत्र पुनर्तपासणीही यशस्वी झाली, मात्र त्याच Lean गाभ्यासह (कर्नल).

काय अजून खुले आहे

लेखक तीन प्रश्न मांडतात: त्यांच्या मर्यादित उदाहरणावर फायद्याचा खरा आकार, ज्ञात लॉगरिदमिक कमाल मर्यादा प्रत्यक्षात गाठली जाते का, आणि एखादे लहान प्रतिउदाहरण अस्तित्वात आहे का. त्यांचे शेवटचे वाक्य सद्यस्थिती सांगते: “असे दिसते की दिशाहीन नेटवर्क्समध्ये कोडिंग खरोखर मदत करते; ते किती मदत करू शकते हे अजून पाहायचे आहे.”

AI वापर जाहीर. एका तळटिपेत म्हटले आहे की OpenAI च्या GPT-6 Astra ने सिद्धता आणि Lean कोड विकसित करण्यात मदत केली.