🤖 AI

Improved lower bounds for the Shannon capacity of odd cycles

यह शोध पत्र एक लार्ज लैंग्वेज मॉडल के साथ पुनरावृत्तिपूर्ण सहयोग के माध्यम से उनके स्ट्रॉन्ग प्रोडक्ट्स (strong products) में बड़े स्वतंत्र सेटों (independent sets) का निर्माण करके विषम चक्रों $C_7$ , $C_{11}$ , $C_{13}$ , और $C_{15}$ की शैनन क्षमता (Shannon capacity) के लिए बेहतर निचली सीमाओं (lower bounds) को प्रस्तुत करता है।

मूल लेखक: Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

प्रकाशित 2026-07-31

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक शोर वाले वॉकी-टॉकी चैनल के माध्यम से एक गुप्त संदेश भेजने की कोशिश कर रहे हैं। हर बार जब आप बोलते हैं, तो स्टैटिक (static) आपके शब्दों को बिगाड़ सकता है, जिससे "हाँ" का अर्थ "ना" हो सकता है। सूचना सिद्धांत (information theory) की दुनिया में, वैज्ञानिक एक बहुत ही विशिष्ट प्रश्न पूछते हैं: हम कितनी तेज़ गति से संदेश भेज सकते हैं ताकि प्राप्तकर्ता उन्हें बिना किसी त्रुटि के पूरी तरह से समझ सके, चाहे हवा में कितना भी शोर क्यों न हो? इस सीमा को शैनन क्षमता (Shannon capacity) कहा जाता है।

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

पेचीदा बात यह है कि हम इन मानचित्रों को मिलाकर और भी बड़े, अधिक जटिल मानचित्र बना सकते हैं। इन मानचित्रों को एक साथ जोड़ने से, हम कभी-कभी बहुत बड़े सुरक्षित संदेशों के समूह पा सकते हैं जिन्हें हम पहले नहीं देख पा रहे थे। कुछ आकृतियों के लिए, जैसे सम-संख्या वाले छल्ले (even-numbered rings), हम उत्तर को पूरी तरह से जानते हैं। लेकिन विषम-संख्या वाले छल्लों (जैसे 7-पक्षीय या 11-पक्षीय आकृति) के लिए, उत्तर दशकों से एक जिद्दी रहस्य बना हुआ है। यह एक मुड़े हुए, गांठदार ब्रेसलेट पर गैर-स्पर्श करने वाले स्थानों के सबसे बड़े समूह को खोजने जैसा है, और अब तक कोई भी पूर्णतः सर्वोत्तम व्यवस्था नहीं खोज पाया है।

यह शोध पत्र इस बारे में है कि कैसे शोधकर्ताओं की एक टीम ने इन जिद्दी विषम छल्लों से निपटने के लिए एक बहुत ही नए प्रकार के सहायक का उपयोग करने का निर्णय लिया: एक लार्ज लैंग्वेज मॉडल (LLM), जो उसी प्रकार का AI है जो स्मार्ट चैटबॉट्स को शक्ति देता है। केवल कोड लिखने के बजाय, उन्होंने AI को एक रचनात्मक साथी की तरह माना। उन्होंने AI से इन विषम छल्लों के लिए सुरक्षित संदेशों की सर्वोत्तम-ज्ञात व्यवस्थाओं को देखने और फिर उन्हें थोड़ा सा बदलने (tweak करने) के लिए कहा ताकि उन्हें और भी बड़ा बनाया जा सके।

परिणाम आश्चर्यजनक रूप से सफल रहे। टीम ने, AI के साथ मिलकर, 7, 11, 13 और 15 पक्षों वाले छल्लों के लिए नए, बड़े सुरक्षित संदेशों के समूह खोज निकाले। 7-पक्षीय छल्ले के लिए, उन्होंने 134,753 सुरक्षित संदेशों का समूह खोजा, जो पिछले रिकॉर्ड 367 से कहीं अधिक है। 11-पक्षीय छल्ले के लिए, उन्होंने 21,909 संदेश खोजे। 13-पक्षीय छल्ले के लिए 62,530, और 15-पक्षीय छल्ले के लिए एक विशाल 8,076,974 संदेश खोजे।

ये संख्याएँ केवल अंकों की सूची जैसी लग सकती हैं, लेकिन ये हमारे इस ज्ञान में वास्तविक सुधार का प्रतिनिधित्व करती हैं कि बिना किसी त्रुटि के कितनी जानकारी भेजी जा सकती है। इन बड़े समूहों को खोजकर, शोधकर्ताओं ने सिद्ध किया कि इन विशिष्ट शोर वाले चैनलों के लिए अधिकतम गति उतनी अधिक है जितनी कि हम पहले सोचते थे। उदाहरण के लिए, 7-पक्षीय छल्ले के लिए, गति सीमा अब ज्ञात है कि 3.258020 से अधिक है, जबकि पहले यह केवल 3.257865 से अधिक ज्ञात थी।

जो बात इस कहानी को विशेष रूप से रोमांचक बनाती है वह केवल संख्याएँ नहीं हैं, बल्कि यह भी है कि वे कैसे खोजी गईं। शोधकर्ताओं ने पारंपरिक कंप्यूटर खोज विधियों का उपयोग करने की कोशिश की, जैसे कि सिमुलेटेड एनीलिंग (simulated annealing - जो पहेली के टुकड़ों को एक बॉक्स में हिलाने और फिट करने जैसा है), लेकिन वे विधियाँ इन नए, बड़े समूहों को खोजने में विफल रहीं। AI द्वारा निर्मित स्थानीय खोज एल्गोरिदम (local search algorithms) भी इन नई ऊंचाइयों तक नहीं पहुँच सके। यह केवल AI के साथ एक निरंतर संवाद के माध्यम से ही संभव हुआ, जहाँ शोधकर्ताओं ने उसे संकेत दिए और AI ने मौजूदा पैटर्न में रचनात्मक संशोधनों का सुझाव दिया।

यह शोध पत्र यह दावा नहीं करता है कि इसने सभी विषम छल्लों के लिए शैनन क्षमता की पूरी पहेली को हल कर दिया है; वह समस्या अभी भी अनसुलझी है। हालाँकि, यह दिखाता है कि मानव गणितीय अंतर्ज्ञान को आधुनिक AI की पैटर्न पहचानने की शक्ति के साथ जोड़कर, हम अपने ज्ञान की सीमाओं को आगे बढ़ा सकते हैं। शोधकर्ताओं ने अपने प्रत्येक नए संदेश समूह को यह सुनिश्चित करने के लिए सत्यापित किया कि वे गणितीय रूप से सही हैं, जिससे यह सिद्ध हुआ कि AI ने केवल अनुमान नहीं लगाया, बल्कि वास्तव में वैध, बड़े समाधान खोजे जिन्हें मानव विशेषज्ञों ने मिस कर दिया था। यह सुझाव देता है कि जटिल गणितीय पहेलियों को हल करने का भविष्य मनुष्यों और AI के एक टीम के रूप में मिलकर काम करने में निहित हो सकता है, जहाँ AI एक रचनात्मक चिंगारी के रूप में कार्य करता है जो हमें संख्याओं के नृत्य में अगला कदम देखने में मदद करता है।

तकनीकी सारांश: विषम चक्रों (Odd Cycles) के शैनन क्षमता (Shannon Capacity) के लिए बेहतर निम्नतम सीमाएँ (Lower Bounds)

समस्या विवरण
एक ग्राफ $G$ का शैनन क्षमता $\Theta(G)$ एक शोर वाले चैनल (noisy channel) पर परिभाषित $G$ द्वारा मात्रात्मक रूप से अधिकतम शून्य-त्रुटि संचार दर को मापता है। इसे $\Theta(G) = \sup_{d \in \mathbb{N}} \alpha(G^d)^{1/d}$ के रूप में परिभाषित किया गया है, जहाँ $\alpha(G^d)$ $G$ के $d$ -वें स्ट्रॉग प्रोडक्ट (strong product) का स्वतंत्रता संख्या (independence number) है। जबकि सम चक्रों (even cycles) के लिए $\Theta(C_p) = p/2$ और $C_5$ के लिए $\Theta(C_5) = \sqrt{5}$ है, $r > 2$ वाले विषम चक्रों $C_{2r+1}$ के मान अज्ञात बने हुए हैं। $\Theta(C_7)$ का निर्धारण करना एक अत्यंत कठिन खुला प्रश्न है। स्थापित निम्नतम सीमाओं को स्थापित करने के लिए मानक दृष्टिकोण $C_k^d$ के स्ट्रॉग प्रोडक्ट्स में बड़े स्वतंत्र सेट्स (independent sets) का निर्माण करना है ताकि $\alpha(C_k^d)^{1/d}$ की मात्रा को अधिकतम किया जा सके।

कार्यप्रणाली (Methodology)
लेखक स्वतंत्र सेट्स के स्पष्ट कॉम्बिनेटोरियल कंस्ट्रक्शन (combinatorial constructions) खोजने के लिए एक लार्ज लैंग्वेज मॉडल (LLM), विशेष रूप से ChatGPT-5.6 Sol Pro, के साथ एक पुनरावृत्ति अंतःक्रिया (iterative interaction) का उपयोग करते हैं। यह कार्यप्रणाली पारंपरिक ह्यूरिस्टिक खोज (जैसे सिम्युलेटेड एनीलिंग या लोकल सर्च एल्गोरिदम) से भिन्न है, जिन्हें लेखक बताते हैं कि व्यापक प्रयासों के बावजूद रिपोर्ट की गई सीमाओं तक पहुँचने में विफल रहे।

प्रक्रिया में शामिल था:

प्रॉम्प्टिंग (Prompting): लेखकों ने LLM को विशिष्ट पैरामीटर प्रदान किए: चक्र की लंबाई ( $k$ ), उत्पाद आयाम ( $d$ ), सर्वोत्तम ज्ञात मौजूदा कंस्ट्रक्शन, और सुधार के लिए लक्षित कार्डिनैलिटी (cardinality)।
जनरेशन और निष्पादन (Generation and Execution): मॉडल ने खोज प्रोग्राम जनरेट किए, उन्हें अपने वातावरण में निष्पादित किया, और कैंडिडेट स्वतंत्र सेट्स वापस किए।
पुनरावृत्ति परिशोधन (Iterative Refinement): लेखकों ने मॉडल द्वारा प्राप्त प्रारंभिक परिणामों से आगे जाने के लिए फॉलो-अप प्रॉम्प्ट्स का उपयोग किया।
सत्यापन (Verification): सभी निर्मित सेट्स को लेखकों द्वारा कठोरता से सत्यापित किया गया ताकि यह सुनिश्चित हो सके कि वे वैध स्वतंत्र सेट्स हैं (अर्थात, कोई भी दो वेक्टर $k$ के मॉड्यूल $k$ में प्रत्येक कोआर्डिनेट में 1 से अधिक अंतर नहीं रखते हैं)।

मुख्य योगदान और परिणाम
यह शोध पत्र चार विशिष्ट विषम चक्रों के लिए उनके स्ट्रॉग प्रोडक्ट्स में बड़े स्वतंत्र सेट्स का निर्माण करके उनके शैनन क्षमता के लिए बेहतर निम्नतम सीमाएं प्रस्तुत करता है:

$C_7$ (7-चक्र): लेखकों ने $C_7^{10}$ के स्ट्रॉग 10-प्रोडक्ट में 134,753 आकार का एक स्वतंत्र सेट निर्मित किया। यह पिछले सर्वोत्तम ज्ञात मान $367^{1/5}$ (जो $C_7^5$ में आकार-367 के स्वतंत्र सेट से प्राप्त हुआ था) में सुधार करता है।
- नया निम्नतम मान: $\Theta(C_7) \geq 134753^{1/10} > 3.258020$ (पहले $> 3.257865$ था)।
- कंस्ट्रक्शन रणनीति: इस सेट को पोलाक और श्राइवर के आकार-367 के सेट $R$ को संशोधित करके प्राप्त किया गया था। लेखकों ने $R$ से विशिष्ट वेक्टर्स को हटाकर एक उपसमुच्चय $B$ बनाया, फिर $R$ और विशिष्ट रूपांतरणों से प्राप्त अतिरिक्त वेक्टर्स का उपयोग करके अंतिम सेट $I$ का निर्माण किया।
$C_{11}$ (11-चक्र): $C_{11}^6$ में 21,909 आकार का एक स्वतंत्र सेट पाया गया।
- नया निम्नतम मान: $\Theta(C_{11}) \geq 21909^{1/6} > 5.289773$ (पहले $148^{1/3} > 5.289572$ था)।
- कंस्ट्रक्शन रणनीति: $C_{11}^3$ में आकार-148 के सेट से शुरू करते हुए, लेखकों ने विशिष्ट उपसमुच्चय ($DL, DR, BL, BR $) और सहायक वेक्टर सेट्स ($ F_A, F_B, \dots$) को परिभाषित किया ताकि 6-प्रोडक्ट में सेट का निर्माण किया जा सके।
$C_{13}$ (13-चक्र): $C_{13}^6$ में 62,530 आकार का एक स्वतंत्र सेट पाया गया।
- नया निम्नतम मान: $\Theta(C_{13}) \geq 62530^{1/6} > 6.300109$ (पहले $247^{1/3} > 6.274305$ था)।
- कंस्ट्रक्शन रणनीति: LLM ने $\mathbb{Z}_{13}^4$ में 370 वेक्टर्स के एक बड़े स्वतंत्र सेट $S$ को खोजने के लिए एक ऑक्सिलरी ग्राफ $G_A$ (134 वेक्टर्स वाला) पर रैंडमाइज्ड लोकल सर्च लागू किया। अंतिम सेट $I$ को $\{x \in \mathbb{Z}_{13}^6 : Ax \in S\}$ के रूप में परिभाषित किया गया।
$C_{15}$ (15-चक्र): $C_{15}^8$ में 8,076,974 आकार का एक स्वतंत्र सेट पाया गया।
- नया निम्नतम मान: $\Theta(C_{15}) \geq 8076974^{1/8} > 7.301399$ (पहले $2842^{1/4} > 7.301397$ था)।
- कंस्ट्रक्शन रणनीति: $C_{15}^4$ में आकार-2842 के सेट से शुरू करते हुए, लेखकों ने बेस सेट $R$ बनाने के लिए विशिष्ट वेक्टर्स को हटाया और अन्य को जोड़ा। अंतिम सेट को $B \times B$ (जहाँ $B \subset R$ ) और एडजेसेंसी कंडीशंस के आधार पर लुकअप टेबल्स ( $W_0, W_1$ ) द्वारा निर्धारित वेक्टर्स के साथ मिलकर बनाया गया।

इसके अतिरिक्त, शोध पत्र कई व्यक्तिगत स्ट्रॉग प्रोडक्ट्स के स्वतंत्रता नंबरों पर बेहतर निम्नतम सीमाएं भी रिपोर्ट करता है जो सीधे शैनन क्षमता सीमाओं में सुधार नहीं करती हैं (जैसे, $\alpha(C_{11}^4) \geq 766$ , $\alpha(C_{15}^3) \geq 383$ )।

महत्व और दावे
शोध पत्र का दावा है कि ये परिणाम $\Theta(C_7)$ , $\Theta(C_{11})$ , और $\Theta(C_{15})$ के ज्ञात निम्नतम स्तरों के लिए मामूली सुधार हैं, और $\Theta(C_{13})$ के लिए अधिक महत्वपूर्ण सुधार हैं।

इस कार्य का प्राथमिक महत्व इसकी कार्यप्रणाली में निहित है:

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

लेखक संख्यात्मक सुधारों के परिमाण (उदाहरण के लिए, $\Theta(C_{15})$ में छठे दशमलव स्थान तक की वृद्धि) के संबंध में विनम्र हैं, लेकिन वे खोज प्रक्रिया की नवीनता पर जोर देते हैं। सभी कंस्ट्रक्शन और कोड एक सार्वजनिक रिपॉजिटरी में उपलब्ध कराए गए हैं।

इसी तरह के और पेपर