Evolving Local Corrections for Global Constructions in Combinatorics

यहाँ जेर्गेली बर्त्ज़ी (Gergely Bérczi) के शोध पत्र "Evolving Local Corrections for Global Constructions in Combinatorics" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र संयोजन विज्ञान (combinatorics) की तीन प्रमुख खुली समस्याओं को संबोधित करता है जहाँ एक वैश्विक संरचना (global structure) के अस्तित्व की परिकल्पना की गई है, लेकिन स्पष्ट निर्माण या प्रमाण मिलना अभी भी कठिन है। इन समस्याओं में एक सामान्य संरचनात्मक विशेषता है: इन्हें एक विशाल विविक्त स्थान (discrete space) में एक "वैश्विक न्यूनतम" (एक वैध प्रमाण/certificate) खोजने के रूप में मॉडल किया जा सकता है, जो छोटे, स्थानीय सुधार चरणों (local correcting steps) को लागू करके प्राप्त किया जाता है।

अध्ययन की गई तीन विशिष्ट समस्याएँ हैं:

1. ग्राफ पुनर्निर्माण अनुमान (Graph Reconstruction Conjecture): क्या एक परिमित सरल ग्राफ को उसके "डेक" (शीर्ष-हटाए गए उप-ग्राफों का मल्टीसेट) से अद्वितीय रूप से (आइसोमोर्फिज्म तक) पुनर्गठित किया जा सकता है? यह शोध पत्र द्विपक्षीय ग्राफों (bipartite graphs) और समतलीय ग्राफों (planar graphs) (विशेष रूप से गैर-अधिकतम, द्विकोंनज (biconnected) ग्राफ जिनका न्यूनतम डिग्री $\ge 3$ हो) पर केंद्रित है।
2. एलन-टार्सी अनुमान (Alon-Tarsi Conjecture): सम $n$ के लिए, लैटिन वर्गों (Latin squares) का हस्ताक्षरित गणना (signed enumeration) गैर-शून्य ($E_n - O_n \neq 0$) है। लक्ष्य एक चिह्न-विपरीत इनवोल्यूशन (sign-reversing involution) का निर्माण करना है जो अधिकांश लैटिन वर्गों को युग्मित करे, और एक छोटे अवशेष सेट (residual set) को छोड़ दे जिसका चिह्न प्रभावी हो।
3. रोटा का आधार अनुमान (Rota's Basis Conjecture): यदि रैंक-$n$ के $n$ विलगित आधार (disjoint bases) दिए गए हैं, तो क्या उन्हें एक $n \times n$ ग्रिड में पुनर्व्यवस्थित किया जा सकता है जहाँ प्रत्येक कॉलम भी एक आधार हो? यह शोध पत्र $\mathbb{F}_2$ पर रैखिक मैट्रॉइड (linear matroids) पर ध्यान केंद्रित करता है और अमान्य कॉलमों को ठीक करने के लिए स्थानीय विनिमय (local exchanges) करने की नीति खोजता है।

2. कार्यप्रणाली: अल्फाइवॉल्व (AlphaEvolve)

लेखक AlphaEvolve का उपयोग करते हैं, जो एक प्रयोगात्मक इंजन है जो गणितीय प्रमाणों की खोज को एक विकासवादी अनुकूलन समस्या (evolutionary optimization problem) के रूप में मानता है। किसी एकल स्थिर वस्तु (जैसे कोई विशिष्ट ग्राफ या लैटिन वर्ग) की खोज करने के बजाय, यह प्रणाली एल्गोरिदम (Python स्क्रिप्ट्स) की खोज करती है जो इन वस्तुओं को उत्पन्न करते हैं या आवश्यक सुधार करते हैं।

• इवॉल्वेबल ब्लॉक (The Evolvable Block): एक पायथन फ़ंक्शन (जैसे, find_best_certificate) जो एक संभावित समाधान या एक स्थानीय चाल (local move) प्रस्तावित करता है।
• हार्नेस (Harness/Evaluator): एक निश्चित मॉड्यूल जो गणितीय नियमों को एनकोड करता है। यह उम्मीदवार को लेता है, उसे परीक्षण सेट पर चलाता है, और एक स्केलर स्कोर लौटाता है।
  • स्कोरिंग रणनीति (Scoring Strategy): हार्नेस एक स्तरीय स्कोरिंग प्रणाली का उपयोग करता है। कठिन बाधाएं (जैसे, "लैटिन वर्ग होना चाहिए") गैर-परक्राम्य हैं। मृदु मेट्रिक्स (जैसे, "साइन-फ्लिप दर," "वैध कॉलमों की संख्या," "चालों की स्थानीयता") खोज को "प्रमाण-नुमा" (proof-shaped) समाधानों की ओर निर्देशित करते हैं।
  • सममिति प्रबंधन (Symmetry Handling): मनमाने लेबलिंग के प्रति ओवरफिटिंग को रोकने के लिए, हार्नेस उम्मीदवारों का मूल्यांकन यादृच्छिक सममिति संचालन (शीर्षों, पंक्तियों, कॉलमों या प्रतीकों के क्रमपरिवर्तन) के तहत करता है और स्कोर को 'वर्स्ट-केस' सांख्यिकी का उपयोग करके एकत्रित करता है।
• विकासवादी प्रक्रिया (Evolutionary Process): प्रणाली पुनरावृत्ति के साथ 'इवॉल्वेबल कोड ब्लॉक' को फिर से लिखती है। यह उन संशोधनों को प्राथमिकता देती है जो स्कोर में सुधार करते हैं, जिससे प्रभावी रूप से एक ह्यूरिस्टिक या एल्गोरिदम विकसित होता है जो वैश्विक समाधान तक पहुँचने के लिए स्थानीय सुधार करता है।

3. मुख्य योगदान और परिणाम

A. ग्राफ पुनर्निर्माण (Graph Reconstruction)

• द्विपक्षीय ग्राफ (Bipartite Graphs):
  • परिणाम: AlphaEvolve ने 1,420 द्विपक्षीय ग्राफों के बेंचमार्क पर 100% पुनर्निर्माण प्राप्त करने वाला एक एल्गोरिदम खोजा।
  • तंत्र: विकसित एल्गोरिदम वैश्विक डिग्री और "पड़ोसी-डिग्री प्रोफाइल" (एक शीर्ष के डिग्री का मल्टीसेट) को पुनर्गठित करता है। यह शीर्षों को इन अपरिवर्तनीय गुणों (invariants) के आधार पर "प्रकारों" में वर्गीकृत करता है और एक बाधा-युक्त असाइनमेंट समस्या को हल करने के लिए मिन-कॉस्ट फ्लो (min-cost flow) का उपयोग करता है। यह अस्पष्टता को हल करने के लिए "दो-हटाव संगतता हस्ताक्षर" (two-deletion compatibility signatures) का उपयोग करके इसे और परिष्कृत करता है।
  • अनुमान: उच्च-डिग्री, 2-कनेक्टेड, गैर-नियमित द्विपक्षीय ग्राफों में, निम्न-क्रम के अपरिवर्तनीय (डिग्री और पड़ोसी प्रोफाइल) ग्राफ को अद्वितीय रूप से निर्धारित करते हैं, शेष अस्पष्टता दो-हटाव निरंतरता द्वारा हल की जाती है।
• समतलीय ग्राफ (Planar Graphs):
  • परिणाम: सिस्टम ने एक सरल, सटीक-सत्यापन एल्गोरिदम खोजा जिसने कठोर समतलीय बेंचमार्क पर 100% पुनर्निर्माण प्राप्त किया।
  • तंत्र: यूलर के बाउंड (समतलीय ग्राफों में $\le 5$ डिग्री वाला एक शीर्ष होता है) का लाभ उठाते हुए, एल्गोरिदम न्यूनतम-डिग्री वाले शीर्ष के लिए संभावित पड़ोसियों को सूचीबद्ध करता है, त्रिकोण गणनाओं का उपयोग करके उन्हें फ़िल्टर करता है, और सटीक डेक समानता के माध्यम से उम्मीदवार को सत्यापित करता है।
  • अनुमान: द्विकोंज (Biconnected) समतलीय ग्राफ जिनका $\delta \ge 3$ है, एक बहुपद समय (polynomial time) में चलने वाली सीमित-डिग्री खोज रणनीति के माध्यम से पुनर्निर्मित योग्य हैं।

B. एलन-टार्सी अनुमान (Alon-Tarsi Conjecture)

• परिणाम: सिस्टम ने सम क्रम ($n=8, 10, 12, 14, 26$) के लिए लैटिन वर्गों के लिए 98–100% पर कार्य करने वाले 'साइन-रिवर्सिंग इनवोल्यूशन' के रूप में नियतात्मक मानचित्र (deterministic maps) विकसित किए।
• तंत्र: विकसित एल्गोरिदम विषम-चक्र व्यापार (odd-cycle trades) का उपयोग करते हैं। दो पंक्तियों (या कॉलम/प्रतीक) द्वारा प्रेरित क्रमपरिवर्तन में विषम-लंबाई वाले चक्रों की पहचान करके और इन चक्रों के साथ तत्वों को बदलकर, एल्गोरिदम लैटिन वर्ग के चिह्न को बदल देता है जबकि उसकी वैधता बनाए रखता है।
  • अवशेष पूर्वाग्रह (Residual Bias): बिना युग्मित हुए कुछ वर्गों (अवशेष सेट) को पाया गया कि वे अत्यधिक एक ही चिह्न (जैसे, सभी सम या सभी विषम) के हैं, जो हस्ताक्षरित योग को अधिकतम करता है।
  • स्थिरता (Stability): विकसित मानचित्रों में "स्थिरता जाँच" शामिल है ताकि यह सुनिश्चित हो सके कि मानचित्र एक वास्तविक इनवोल्यूशन ($F(F(L)) = L$) है और यह आइसोटोपी (पंक्तियों, कॉलमों और प्रतीकों के क्रमपरिवर्तन) के तहत सुदृढ़ है।
• अनुमान: प्रत्येक सम $n$ के लिए, दो-लाइन चक्र व्यापारों का एक नियतात्मक स्कैन क्रम मौजूद है जिससे प्रेरित मानचित्र एक छोटे अवशेष सेट को छोड़कर सभी लैटिन वर्गों पर एक साइन-रिवर्सिंग इनवोल्यूशन के रूप में कार्य करता है, जिसका हस्ताक्षरित योग गैर-शून्य है।

C. रोटा का आधार अनुमान (Rota's Basis Conjecture)

• परिणाम: सिस्टम ने ऐसे 'ग्रिडी लोकल-एक्सचेंज पॉलिसी' विकसित किए जिन्होंने $\mathbb{F}_2$ पर रैंक 5, 7 और एक परिवर्तनशील-रैंक बेंचमार्क (5–13) के परीक्षण उदाहरणों में से 100% के लिए $n$ विलगित ट्रांसवर्सल आधारों का सफलतापूर्वक निर्माण किया।
• तंत्र: नीतियां एक स्कोरिंग फ़ंक्शन का उपयोग करती हैं जो संतुलित करती है:
  • प्रगति (Progress): उन चालों को पुरस्कृत करना जो पूर्ण कॉलम को पूरा करती हैं।
  • ट्रैप से बचाव (Trap Avoidance): उन चालों को दंडित करना जो छोटे निर्भरता सर्किट (dependency circuits/traps) बनाते हैं।
  • रणनीतिक बलिदान (Strategic Sacrifice): एक "पूर्ण" कॉलम को तोड़ने की अनुमति देना यदि वह एक महत्वपूर्ण निर्भरता सर्किट (एक "वीर बलिदान") को हल करता है।
  • पैमाना जागरूकता (Scale Awareness): परिवर्तनशील-रैंक नीति गतिशील "प्रेशर" और "ट्रैप एनर्जी" मेट्रिक्स का उपयोग करती है जो रैंक $n$ के साथ स्केल होते हैं, जिससे एल्गोरिदम को समस्या के आकार के आधार पर अपनी आक्रामकता को अनुकूलित करने की अनुमति मिलती है।
• अनुमान: $\mathbb{F}_2^n$ में वेक्टर के सर्किट-समृद्ध पूल्स (circuit-rich pools) के लिए, विकसित स्केल-अवेयर पॉलिसी का एक नियतात्मक डी-रैंडमाइजेशन (de-randomization) आवश्यक ट्रांसवर्सल आधारों का सफलतापूर्वक निर्माण कर सकता है।

4. महत्व और निहितार्थ

• गणितीय अभ्यास में बदलाव: यह शोध पत्र प्रदर्शित करता है कि AI-संचालित विकासवादी खोज (evolutionary search) रचनात्मक संयोजन विज्ञान (constructive combinatorics) के लिए एक शक्तिशाली "परिकल्पना जनरेटर" के रूप में कार्य कर सकती है। यह मानव प्रमाण का स्थान नहीं लेती बल्कि स्पष्ट एल्गोरिदम और संरचनात्मक पैटर्न उत्पन्न करती है जो पारंपरिक गणितीय विश्लेषण के योग्य हैं।
• लोकल-टू-ग्लोबल सिद्धांत: यह कार्य इस ह्यूरिस्टिक की पुष्टि करता है कि कठिन वैश्विक अस्तित्व संबंधी समस्याओं के समाधान अक्सर "विविक्त ल्यपुनोव ट्रैजेक्टरीज" (discrete Lyapunov trajectories) के माध्यम से प्राप्त किए जा सकते हैं—अर्थात स्थानीय चालों के ऐसे अनुक्रम जो दोष (defect) माप को एकदिष्ट रूप से कम करते हैं।
• नए अनुमान (New Conjectures): यह शोध पत्र सीधे विकसित एल्गोरिदम से प्राप्त विशिष्ट, परीक्षण योग्य अनुमान (अनुमान 4-11) तैयार करता है। ये अनुमान मूल खुली समस्याओं की तुलना में अधिक सटीक हैं, जो भविष्य के प्रमाणों के लिए ठोस मार्ग (जैसे, विशिष्ट प्रकार के व्यापार या प्रवाह बाधाएं) प्रदान करते हैं।
• सहयोगी के रूप में AI: "विकासवादी ट्रेस" (evolutionary trace) की व्याख्या करने के लिए AI-जनित सारांशों (Gemini के माध्यम से) का उपयोग यह उजागर करता है कि एक नया वर्कफ़्लो कैसे विकसित हो रहा है, जहाँ AI गणितज्ञों को यह समझने में मदद करता है कि खोज क्यों सफल या विफल हुई, जिससे महत्वपूर्ण मोड़ और संरचनात्मक अंतर्दृष्टि की पहचान होती है।