A proof of the cyclotomic conjecture and the non-existence of almost Moore digraphs

कल्पना कीजिए कि आप एक कुशल वास्तुकार हैं जो दुनिया का सबसे कुशल शहर बनाने की कोशिश कर रहे हैं। आपके पास एक सख्त नियम है: हर इमारत (एक "नोड") केवल कुछ ही पड़ोसियों को संदेश भेज सकती है (डिग्री), और कोई भी संदेश किसी भी अन्य इमारत तक पहुँचने के लिए बहुत अधिक चरणों (व्यास/डायमीटर) का उपयोग नहीं कर सकता। गणित की दुनिया में, विशेष रूप से ग्राफ थ्योरी के एक क्षेत्र में, इसे "डिग्री-डायमीटर समस्या" के रूप में जाना जाता है। यह एक ऐसे कमरे में अधिकतम लोगों को पैक करने जैसा है जहाँ हर कोई केवल कुछ ही लोगों से हाथ मिला सकता है, और हर कोई कुछ ही परिचय के भीतर सभी से नमस्ते कह सकता है।

गणितज्ञ लंबे समय से एक "परफेक्ट" शहर के आकार के बारे में जानते हैं, जिसे मूर बाउंड (Moore bound) कहा जाता है, जो उन नियमों के तहत आपके द्वारा फिट किए जा सकने वाले अधिकतम इमारतों का प्रतिनिधित्व करता है। हालाँकि, ये पूर्ण शहर अविश्वसनीय रूप से दुर्लभ हैं; वे केवल कुछ सरल, उबाऊ परिदृश्यों में ही मौजूद होते हैं। इसने गणितज्ञों को एक लुभावना प्रश्न छोड़ दिया: क्या ऐसे "लगभग मूर डाइग्राफ्स" (almost Moore digraphs) मौजूद हैं जो पूर्ण आकार से केवल एक इमारत छोटे हैं? दशकों तक, शोधकर्ता इन लगभग-पूर्ण संरचनाओं की तलाश में रहे, यह सोचते हुए कि क्या वे जटिल, बड़े शहरों के लिए मौजूद हैं या क्या गणित के नियम उन्हें वर्जित करते हैं।

यह शोध पत्र, जिसे जसकरण कौर और हितेश कुमार ने लिखा है, एक अंतिम डिटेक्टिव रिपोर्ट की तरह है जो इस मामले को बंद कर देता है। लेखक सिद्ध करते हैं कि ये "लगभग पूर्ण" शहर किसी भी जटिल परिदृश्य के लिए मौजूद नहीं हैं जहाँ एक इमारत के एक से अधिक निकास पथ हों और पथ की लंबाई दो से अधिक हो। इसे हल करने के लिए, उन्होंने केवल शहर के मानचित्रों को ही नहीं देखा; उन्हें "साइक्लोटोमिक पॉलिनोमियल" (cyclotomic polynomials) की गहरी, अमूर्त दुनिया में उतरना पड़ा। इन पॉलिनोमियल्स को आप शहर के ढांचे के गुप्त डीएनए या अंतर्निहित संगीत स्कोर के रूप में देख सकते हैं। यह शोध पत्र इस बात को सिद्ध करता है कि जब शहर जटिल होता है, तो यह गणितीय डीएनए हमेशा एक विशिष्ट तरीके से टूट जाता है, जिससे यह प्रदर्शित होता है कि "लगभग पूर्ण" शहर बनाना गणितीय रूप से असंभव है।

लापता शहर का रहस्य

निर्देशित नेटवर्क (directed networks) की दुनिया में (जहाँ कनेक्शनों की एक विशिष्ट दिशा होती है, जैसे वन-वे सड़कें), गणितज्ञों के पास एक सूत्र है जो आपके पास प्रति इमारत निकासों की संख्या ($d$) और अधिकतम यात्रा समय ($k$) के साथ आपके द्वारा बनाए जा सकने वाले सबसे बड़े शहर के लिए है। यह सूत्र, $M_{d,k} = 1 + d + \dots + d^k$, "मूर बाउंड" है। यह सैद्धांतिक सीमा है।

हम जानते हैं कि इस सटीक सीमा तक पहुँचने वाले शहर लगभग अस्तित्वहीन हैं। वे केवल कुछ साधारण मामलों में ही दिखाई देते हैं, जैसे एक साधारण लूप या एक पूरी तरह से जुड़ा हुआ हब। इसलिए, बड़ा सवाल यह था: उन शहरों के बारे में क्या जो बस एक कदम छोटे हैं? ये "लगभग मूर डाइग्राफ्स" सफलता का लक्ष्य थे। यदि वे मौजूद होते, तो वे जटिल प्रणालियों के लिए सबसे कुशल नेटवर्क होते।

वर्षों तक, गणितज्ञों ने छोटे मामलों की जाँच की। उन्होंने विशिष्ट, बहुत छोटे सेटअपों के लिए कुछ पाए, लेकिन बड़े, अधिक दिलचस्प नंबरों के लिए, खोज खाली रही। समस्या यह थी कि उनके अस्तित्व को न होने के लिए सिद्ध करने हेतु साइक्लोटोमिक पॉलिनोमियल्स से जुड़े एक बहुत ही कठिन पहेली को हल करना आवश्यक था। ये विशेष गणितीय अभिव्यक्तियाँ हैं जो 'रूट्स ऑफ यूनिटी' (इकाई के मूल) से संबंधित हैं (सोचिए कि ये एक वृत्त की मौलिक आवृत्तियाँ हैं)।

ताले की कुंजी: साइक्लोटोमिक अनुमान (The Cyclotomic Conjecture)

इस शोध पत्र के लेखकों ने महसूस किया कि इन "लगभग पूर्ण" शहरों का अस्तित्व पूरी तरह से $F_{n,k}(x)$ नामक एक पॉलिनोमियल के एक विशिष्ट गुण पर निर्भर करता है। यह पॉलिनोमियल एक साइक्लोटोमिक पॉलिनोमियल ($\Phi_n$) में एक सरल योग ($1 + x + \dots + x^k$) को रखकर बनाया गया है।

1999 में, गिम्बर्ट नामक एक गणितज्ञ ने एक "साइक्लोटोमिक कंजेक्चर" प्रस्तावित किया था ताकि यह वर्णन किया जा सके कि यह पॉलिनोमियल $F_{n,k}(x)$ कब टूटेगा (रिड्यूसिबल होगा) और कब अखंड रहेगा (इरिड्यूसिबल होगा)।

• यदि पॉलिनोमियल अखंड (irreducible) रहता है, तो यह एक ठोस, अटूट ब्लॉक की तरह कार्य करता है।
• यदि यह टूट जाता है (reducible), तो यह छोटे टुकड़ों में विभाजित हो जाता है।

संबंध महत्वपूर्ण है: यदि पॉलिनोमियल एक विशिष्ट तरीके से टूट जाता है, तो इसका मतलब है कि एक "लगभग मूर" शहर अस्तित्व में हो सकता है। यदि पॉलिनोमियल अखंड रहता है, तो शहर असंभव है। पिछले शोधकर्ताओं ने छोटे नंबरों के लिए इसे सिद्ध किया था, लेकिन सामान्य मामला एक रहस्य बना रहा।

सफलता: अनुमान को सिद्ध करना

कौर और कुमार ने केवल छोटे नंबरों के लिए ही नहीं, बल्कि सभी नंबरों के लिए इस अनुमान को सिद्ध करने के लिए कदम उठाए। उन्होंने पॉलिनोमियल $F_{n,k}(x)$ को एक जटिल मशीन की तरह माना और इसके पुर्जों (मूलों और गुणांकों) के बीच की अंतःक्रिया को समझने के लिए इसे अलग-अलग किया।

उन्होंने एक सहायक पॉलिनोमियल $q(x)$ को परिभाषित किया, जो मूल रूप से एक ट्विस्ट के साथ साइक्लोटोमिक पॉलिनोमियल है। फिर उन्होंने $q(x)$ और उसके दर्पण प्रतिबिंब $q^\#(x)$ के बीच "ग्रेटेस्ट कॉमन डिविजर" (महत्तम समापवर्तक) का विश्लेषण किया। यह चरण यह जांचने जैसा था कि क्या मशीन में कोई ढीला पेंच है जिसके कारण वह बिखर सकती है।

उनके विश्लेषण ने एक सख्त नियम प्रकट किया:

1. यदि $k$ सम (even) है: तो पॉलिनोमियल केवल तभी टूटता है जब एक विशिष्ट संख्या $n$, $k+2$ को विभाजित करती है।
2. यदि $k$ विषम (odd) है: तो पॉलिनोमियल केवल तभी टूटता है जब $n$ सम हो और $2(k+2)$ को विभाजित करे।

अन्य सभी मामलों में, पॉलिनोमियल अखंड (irreducible) रहता है।

अंतिम निर्णय: कोई "लगभग पूर्ण" शहर नहीं

कंजेक्चर सिद्ध होने के बाद, लेखकों ने तर्क को शहर बनाने की समस्या पर लागू किया। उन्होंने दिखाया कि किसी भी ऐसे शहर के लिए जिसमें एक से अधिक निकास ($d > 1$) और दो से अधिक यात्रा समय ($k > 2$) हो, "लगभग मूर" शहर के अस्तित्व के लिए आवश्यक गणितीय शर्तें कभी पूरी नहीं होती हैं।

पॉलिनोमियल $F_{n,k}(x)$ ठीक उसी तरह अखंड रहता है जो शहर के निर्माण को रोकता है। फलस्वरूप, लेखकों ने सिद्ध किया कि ऐसे डाइग्राफ्स मौजूद नहीं हैं।

इसका अर्थ यह है कि आप इन नियमों के तहत जो भी जटिल नेटवर्क बनाने का प्रयास करेंगे, आप सैद्धांतिक अधिकतम आकार के एक नोड के भी करीब नहीं पहुँच पाएंगे। सबसे अच्छे नेटवर्क और सैद्धांतिक सीमा के बीच का अंतर कम से कम दो नोड्स का है। "लगभग पूर्ण" शहर एक गणितीय मिथक है।

शोध पत्र निष्कर्ष निकालता है कि इन मापदंडों के लिए निर्देशित डिग्री-डायमीटर समस्या का एक निश्चित उत्तर है: सबसे बड़ा संभव नेटवर्क हमेशा मूर बाउंड से कम से कम दो कदम छोटा होता है। "लगभग मूर" डाइग्राफ की खोज समाप्त हुई है; यह कभी अस्तित्व में था ही नहीं।