🔢 mathematics

Lean-verified lower bounds for the Shannon capacity of odd cycles

यह शोध पत्र गओ और इट्टी एट अल के हालिया तरीकों पर आधारित एक पुनरावृत्ति प्रक्रिया का उपयोग करके, कई छोटे विषम चक्रों ( $C_7, C_{11}, C_{13}, C_{15}, C_{19}, C_{21}, C_{23}$ ) की शैनन क्षमताओं के लिए लीन (Lean) में पूर्णतः औपचारिक रूप से प्रस्तुत नए निचले स्तर के मान (lower bounds) प्रस्तुत करता है।

मूल लेखक: Pjotr Buys, Sven Polak, Jeroen Zuiddam

प्रकाशित 2026-08-03

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

CC BY 4.0

मूल लेखक: Pjotr Buys, Sven Polak, Jeroen Zuiddam

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

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

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

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

सुरक्षित अंतर्संबंधों का खेल

आइए देखते हैं कि लेखकों ने वास्तव में क्या किया। वे ऐसे ग्राफों को देख रहे थे जो विषम संख्या में बिंदुओं वाले सरल छल्लों (rings) की तरह दिखते हैं: 7, 11, 13, आदि बिंदुओं वाला एक रिंग। लंबे समय से, गणितज्ञों को 5-बिंदुओं वाले रिंग के लिए "गति सीमा" (Shannon capacity) पता थी। लेकिन 7 या अधिक बिंदुओं वाले रिंगों के लिए, उत्तर कोहरे में फंसा हुआ था। हम जानते थे कि यह कम से कम एक निश्चित संख्या थी, लेकिन हमें नहीं पता था कि क्या यह इससे अधिक हो सकती है।

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

इसे ऐसे सोचिए: यदि आपके पास 2 लोगों की एक टीम है जो बिना झगड़े के मिलकर काम कर सकती है, और आप ऐसी दो टीमों को मिलाते हैं, तो आप उम्मीद कर सकते हैं कि एक 4 लोगों की टीम बनेगी। लेकिन इस विशेष ट्रिक के साथ, लेखकों ने पाया कि वे उन्हें जोड़कर एक ऐसी टीम बना सकते हैं जिसमें 5 लोग हों और वे सभी पूरी तरह से तालमेल में हों। इस ट्रिक को बार-बार दोहराकर, मानचित्रों को ऊपर की ओर स्टैक करते हुए, वे इन सुरक्षित टीमों को विशाल समूहों में विकसित कर सके।

नए रिकॉर्ड

टीम ने सात अलग-अलग विषम रिंगों पर इस रेसिपी को लागू किया: 7, 11, 13, 15, 19, 21, और 23 बिंदुओं वाले रिंग। प्रत्येक के लिए, उन्होंने एक ज्ञात सुरक्षित समूह से शुरुआत की और अपने "स्टैकिंग" मशीन को कई बार चलाया। परिणाम, उनके द्वारा गणना किए गए सटीक नंबरों के साथ, एक नया, उच्च लोअर बाउंड (lower bound) था।

यहाँ उन्होंने क्या पाया, वे नंबर ठीक वैसे ही हैं जैसे उन्होंने गणना किए:

7-बिंदुओं वाले रिंग के लिए, उन्होंने सिद्ध किया कि क्षमता कम से कम 3.258805369885 है। यह पिछले सर्वोत्तम अनुमान से थोड़ा अधिक है।
11-बिंदुओं वाले रिंग के लिए, नया फ्लोर (floor) 5.294502522149 है।
13-बिंदुओं वाले रिंग के लिए, उन्होंने सीमा को 6.302455083464 तक धकेल दिया।
15-बिंदुओं वाले रिंग के लिए, संख्या 7.301600534487 है।
19-बिंदुओं वाले रिंग के लिए, वे 9.357192705918 तक पहुँचे।
21-बिंदुओं वाले रिंग के लिए, बाउंड (bound) 10.342455853338 है।
और 23-बिंदुओं वाले रिंग के लिए, उन्होंने पाया कि क्षमता कम से कम 11.328224257774 है।

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

डिजिटल रेफरी

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

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

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

यह क्यों मायने रखता है

आप सोच सकते हैं, "तो क्या हुआ? हमें बस इतना पता चला कि नंबर थोड़ा अधिक है।" उत्तर इस समस्या की प्रकृति में निहित है। दशकों से, इन विषम रिंगों की क्षमता एक खुला प्रश्न रही है। हम जानते थे कि उत्तर (Lovász bound) के निचले स्तर और ऊपरी स्तर के बीच कहीं है, लेकिन हम इसे सटीक रूप से निर्धारित नहीं कर पा रहे थे। हर बार जब हम निचले स्तर (lower limit) को ऊपर धकेलते हैं, भले ही वह एक बहुत छोटे अंश के लिए हो, हम अंतर को कम कर देते हैं। हम वास्तविक उत्तर के और करीब पहुँच रहे हैं।

यह कार्य दिखाता है कि भले ही समस्या लंबे समय से अटकी हुई हो, यदि आपके पास सही उपकरण और अपने काम की जाँच करने के लिए पर्याप्त धैर्य है, तो अभी भी सुधार की गुंजाइश है। लेखकों ने पूरी समस्या को हल नहीं किया है, लेकिन उन्होंने कुछ और धुंधले कोनों को साफ किया है, यह सिद्ध करते हुए कि 7, 11, 13, 15, 19, 21, और 23 के रिंगों के लिए, हम पहले की तुलना में थोड़ा तेज़ी से संवाद कर सकते हैं।

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

समस्या विवरण
यह शोध पत्र विषम चक्रों $C_n$ (जहाँ $n \geq 7$ ) के लिए शैनन क्षमता, $\Theta(G)$ , निर्धारित करने की दीर्घकालिक खुली समस्या को संबोधित करता है। शैनन क्षमता को $\Theta(G) := \sup_{d \geq 1} \alpha(G^{\boxtimes d})^{1/d}$ के रूप में परिभाषित किया गया है, जहाँ $\alpha$ स्वतंत्रता संख्या (independence number) है और $\boxtimes$ स्ट्रॉन्ग ग्राफ उत्पाद (strong graph product) है। जबकि लोवाज़ (Lovász) ने थीटा फंक्शन $\vartheta(G)$ का उपयोग करके $\Theta(C_5) = \sqrt{5}$ निर्धारित किया था, सात या उससे अधिक लंबाई वाले सभी विषम चक्रों के लिए सटीक क्षमताएं अज्ञात बनी हुई हैं। मुख्य चुनौती उच्च स्ट्रॉन्ग पावर वाले चक्रों में बड़े स्वतंत्र सेट (independent sets) खोजने में निहित है ताकि ज्ञात निचली सीमाओं में सुधार किया जा सके।

कार्यप्रणाली (Methodology)
लेखक एक "गैजेट निर्माण" (gadget construction) और एक "उत्पाद लेम्मा" (product lemma) पर आधारित एक पुनरावृत्ति प्रक्रिया (iterative procedure) का उपयोग करते हैं जो हाल ही में गाओ (Gao, 2026) द्वारा प्रस्तावित किया गया था, जो स्वयं इट्टी, रोसिन, कार्सेंटेंसन और रेकमान (Itty, Rosin, Carstensen, and Reichman, 2026) की विधियों पर आधारित है। कार्यप्रणाली का मुख्य भाग निम्नलिखित है:

वैध टुपल्स (Valid Tuples): एक ग्राफ $G$ के लिए, एक वैध टुपल $\tau = (I, S, f_0, f_1, X)$ को परिभाषित किया गया है, जहाँ $I$ एक स्वतंत्र सेट है, $S \subseteq I$ है, और $f_0, f_1$ विशिष्ट मैपिंग हैं जो सख्त पड़ोस संबंधी बाधाओं (neighborhood constraints) को संतुष्ट करती हैं। यह टुपल एक "प्रोफ़ाइल" $\Pi(\tau) = (|I|, |S|, |X|, |X \setminus (N_G[f_0(S)] \cup N_G[f_1(S)])|)$ उत्पन्न करता है।
उत्पाद संचालन (Product Operation): प्रोफ़ाइल पर एक बाइनरी ऑपरेशन $\star$ को परिभाषित किया गया है। प्रमेय 1 स्थापित करता है कि यदि $\tau$ और $\tau'$ ग्राफ $G$ और $H$ के लिए वैध टुपल हैं, तो $G \boxtimes H$ के लिए एक वैध टुपल मौजूद होता है जिसका प्रोफ़ाइल व्यक्तिगत प्रोफ़ाइलों का $\star$ -उत्पाद होता है।
पुनरावृत्ति निर्माण (Iterative Construction): एक विशिष्ट विषम चक्र की एक विशिष्ट गणनात्मक रूप से खोजी गई वैध टुपल से शुरू करते हुए, लेखक उच्च शक्तियों के लिए प्रोफ़ाइल उत्पन्न करने के लिए $\star$ -उत्पाद को पुनरावृत्ति से लागू करते हैं। यह प्रक्रिया $C_n^{\boxtimes d}$ की स्ट्रॉन्ग पावर में ऐसे स्वतंत्र सेटों का निर्माण करती है जो आधार स्वतंत्र सेट्स के सरल कार्टेशियन उत्पादों से बड़े होते हैं।
औपचारिक सत्यापन (Formal Verification): कार्यप्रणाली का एक महत्वपूर्ण घटक इन सीमाओं का लीन (Lean) प्रूफ असिस्टेंट में पूर्ण औपचारिकीकरण (formalization) है। आधार टुपल्स (सेट $I, S, X$ और मैप्स $f_0, f_1$ ) को स्पष्ट लिटरेल्स (literals) के रूप में एनकोड किया गया है, और उनकी वैधता को लीन वातावरण के भीतर यांत्रिक रूप से सत्यापित किया गया है।

मुख्य योगदान और परिणाम
यह शोध पत्र सात छोटे विषम चक्रों ( $C_7, C_{11}, C_{13}, C_{15}, C_{19}, C_{21}, C_{23}$ ) के लिए शैनन क्षमताओं के नए, बेहतर निचली सीमा प्रस्तुत करता है। ये सीमाएँ विशिष्ट आधार वैध टुपल्स की पहचान करके और पुनरावृत्ति उत्पाद प्रक्रिया को लागू करके प्राप्त की गई हैं। परिणाम इस प्रकार हैं:

$\Theta(C_7)$ : सुधार कर $\geq 3.258805369885\dots$ किया गया (पूर्व में गाओ 2026 द्वारा $3.2587891\dots$ )। यह निर्माण $C_7^{\boxtimes 5}$ में एक आधार टुपल का उपयोग करता है जिसे शक्ति 200 तक पुनरावृत्त किया गया है।
$\Theta(C_{11})$ : सुधार कर $\geq 5.294502522149\dots$ किया गया (पूर्व में इट्टी आदि 2026 द्वारा $5.2897736\dots$ )। आधार टुपल $C_{11}^{\boxtimes 3}$ में है, जिसे शक्ति 174 तक पुनरावृत्त किया गया है।
$\Theta(C_{13})$ : सुधार कर $\geq 6.302455083464\dots$ किया गया (पूर्व में इट्टी आदि 2026 द्वारा $6.3001091\dots$ )। आधार टुपल $C_{13}^{\boxtim 6}$ में है, जिसे शक्ति 432 तक पुनरावृत्त किया गया है।
$\Theta(C_{15})$ : सुधार कर $\geq 7.301600534487\dots$ किया गया (पूर्व में इट्टी आदि 2026 द्वारा $7.3013990\dots$ )। आधार टुपल $C_{15}^{\boxtimes 4}$ में है, जिसे शक्ति 4096 तक पुनरावृत्त किया गया है।
$\Theta(C_{19})$ : सुधार कर $\geq 9.357192705918\dots$ किया गया (पूर्व में बाउमर्ट आदि 1971 द्वारा $9.3571200\dots$ )। आधार टुपल $C_{19}^{\boxtimes 4}$ में है, जिसे शक्ति 16384 तक पुनरावृत्त किया गया है।
$\Theta(C_{21})$ : सुधार कर $\geq 10.342455853338\dots$ किया गया (पूर्व में बाउमर्ट आदि 1971 द्वारा $10.3422729\dots$ )। आधार टुपल $C_{21}^{\boxtimes 4}$ में है, जिसे शक्ति 4096 तक पुनरावृत्त किया गया है।
$\Theta(C_{23})$ : सुधार कर $\geq 11.328224257774\dots$ किया गया (पूर्व में बाउमर्ट आदि 1971 द्वारा $11.3278379\dots$ )। आधार टुपल $C_{23}^{\boxtimes 4}$ में है, जिसे शक्ति 2048 तक पुनरावृत्त किया गया है।

सुधार, हालांकि संख्यात्मक रूप से छोटे हैं (सीमा $10^{-5}$ से $10^{-3}$ के बीच), इन विशिष्ट चक्रों के लिए वर्तमान अत्याधुनिक (state-of-the-art) स्थिति का प्रतिनिधित्व करते हैं।

महत्व और दावे
यह शोध पत्र मुख्य रूप से इन परिणामों के कठोर सत्यापन के माध्यम से अपनी महत्ता का दावा करता है। पूरे निर्माण और परिणामी सीमाओं को लीन (Lean) में औपचारिक रूप देकर, लेखक यह सुनिश्चित करते हैं कि जटिल कॉम्बिनेटोरियल तर्क और विशिष्ट सेट निर्माण मानवीय त्रुटि से मुक्त हैं। यह कार्य प्रारंभिक निर्माणों की खोज के लिए बड़े भाषा मॉडल (LLMs) का उपयोग करने वाली हालिया शोध की दिशा का अनुसरण करता है (जैसा कि [IRCR26] और [Gao26] में देखा गया है), लेकिन खुद को बेस टुपल्स की वैधता और पुनरावृत्ति उत्पाद प्रमेय के अनुप्रयोग की पूर्णतः औपचारिक, मशीन-चेक किए गए प्रमाण प्रदान करके अलग करता है। लेखक विषम चक्रों के लिए सामान्य समस्या को हल करने का दावा नहीं करते हैं, न ही वे गाओ के मौजूदा उत्पाद लेम्मा के अनुप्रयोग के अलावा कोई नया सैद्धांतिक ढांचा प्रस्तावित करते हैं; बल्कि, वे इन विशिष्ट उदाहरणों के लिए सर्वोत्तम ज्ञात संख्यात्मक निचली सीमाएँ प्रदान करते हैं, जो गणितीय निश्चितता के साथ सत्यापित हैं।

सुरक्षित अंतर्संबंधों का खेल

नए रिकॉर्ड

डिजिटल रेफरी

यह क्यों मायने रखता है

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