🔢 mathematics

Counterexamples to Charpin's Conjecture on BCH codes

यह शोधपत्र प्रिमिटिव नैरो-सेंस (primitive narrow-sense) BCH कोड्स के एक अनंत परिवार का निर्माण करके चार्पिन के अनुमान (Charpin's conjecture) को गलत सिद्ध करता है, जिनके न्यूनतम दूरी (minimum distance) उनके बोस दूरी (Bose distance) से काफी अधिक है, और बाइनरी कोड्स के लिए यह अंतर कोड की लंबाई के घनमूल (cube root) के रूप में बढ़ता है।

मूल लेखक: Run Zheng, Yaoran Yang, Yutong Zhang, Maosheng Xiong

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

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

CC BY 4.0

मूल लेखक: Run Zheng, Yaoran Yang, Yutong Zhang, Maosheng Xiong

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

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

बड़ा सवाल जिसने दशकों से गणितज्ञों और इंजीनियरों को परेशान कर रखा है, वह यह है कि: ये कोड त्रुटियों (errors) को ठीक करने में कितने अच्छे हैं? इसे मापने के लिए, हम "न्यूनतम दूरी" (minimum distance) को देखते हैं, जो अनिवार्य रूप से वह संख्या है जिसे यह कोड पकड़ने और ठीक करने की गारंटी देता है। एक प्रसिद्ध नियम है, जिसे "बोस डिस्टेंस" (Bose distance) कहा जाता है, जो इस संख्या का एक सुरक्षित और रूढ़िवादी अनुमान देता है। लंबे समय तक, विशेषज्ञों का मानना था कि इन कोड्स की वास्तविक शक्ति इस सुरक्षित अनुमान से बहुत अधिक नहीं होती है। उन्हें लगा कि "सुरक्षित अनुमान" और "वास्तविक शक्ति" के बीच का अंतर छोटा और अनुमानित है, जैसे कि एक कार जो अपने स्पीडोमीटर द्वारा बताई गई गति से चार मील प्रति घंटा से अधिक तेज़ कभी नहीं चल सकती। यह विश्वास इतना मजबूत था कि इसने एक प्रसिद्ध अनुमान या "कंजैक्चर" (conjecture) का रूप ले लिया, जिसका नाम एक शोधकर्ता 'चारपिन' (Charpin) के नाम पर रखा गया था। यदि यह अनुमान सच होता, तो इसका मतलब होता कि हम सरल गणना करके आसानी से भविष्यवाणी कर सकते थे कि ये कोड कितनी अच्छी तरह काम करते हैं।

लेकिन क्या होगा अगर वह अनुमान गलत हो? क्या होगा अगर, सही परिस्थितियों में, ये कोड सुपरचार्ज्ड हों, और उन त्रुटियों को ठीक करने में सक्षम हों जितनी कोई सोच भी नहीं सकता था? यह बिल्कुल वही है जो शोधकर्ताओं की एक टीम ने अभी खोजा है। उन्होंने केवल एक छोटा सा अपवाद नहीं खोजा; उन्होंने इन कोड्स का एक पूरा नया परिवार खोज निकाला है जो नियमों को पूरी तरह से तोड़ देता है। उन्होंने सिद्ध किया कि अनुमानित दूरी और वास्तविक दूरी के बीच का अंतर केवल थोड़ा सा बड़ा नहीं है—यह बहुत बड़ा हो सकता है, और जैसे-जैसे कोड बड़े होते जाते हैं, यह बढ़ता जाता है। वास्तव में, कुछ कोड्स के लिए, वास्तविक शक्ति अनुमान से इतनी अधिक है कि पुराना नियम पूरी तरह से विफल हो जाता है। यह केवल एक छोटा सुधार नहीं है; यह इन डिजिटल सुरक्षा जालों के बारे में हमारी समझ में एक मौलिक बदलाव है, जो दिखाता है कि प्रकृति के पास हमारे सोचने की क्षमता से कहीं अधिक कौशल है।

बड़ी खोज: "चार-त्रुटि" नियम को तोड़ना

इस शोध पत्र में, लेखक—रन झेंग, याओरान यांग, युटोंग झांग और माओशेंग शियोंग—ने इन BCH कोड्स की सीमाओं का परीक्षण करने का निर्णय लिया। उनका मुख्य लक्ष्य यह देखना था कि क्या चारपिन का कंजैचर—कि अनुमानित दूरी और वास्तविक दूरी के बीच का अंतर हमेशा छोटा रहता है (विशेष रूप से बाइनरी कोड्स के लिए 4 से अधिक नहीं)—वास्तव में सत्य था।

उनकी पद्धति को समझने के लिए, कल्पना कीजिए कि BCH कोड्स एक किला (fortress) हैं। "बोस डिस्टेंस" बाहरी दीवार की ऊंचाई की तरह है जिस पर सभी सहमत हैं। "न्यूनतम दूरी" किले के सबसे मजबूत बिंदु की वास्तविक ऊंचाई है। वर्षों तक, लोगों ने माना कि सबसे मजबूत बिंदु सहमत दीवार से कुछ फीट से अधिक ऊंचा नहीं हो सकता। हालांकि, लेखकों ने किले के भीतर एक बहुत ऊंचे टॉवर के छिपे हुए, गुप्त प्रवेश द्वार को खोजने का निर्णय लिया।

उन्होंने "जनरलाइज्ड रीड-मुलर कोड्स" (Generalized Reed-Muller codes) नामक एक चतुर गणितीय तकनीक का उपयोग किया। इन्हें एक अलग प्रकार का कोड मानिए जिसके संदेशों के "वेट" (या आकार) के बारे में बहुत सख्त नियम होते हैं। लेखकों ने दिखाया कि उनके विशिष्ट BCH कोड वास्तव में इन सख्त कोड्स के भीतर छिपे हुए हैं। अपने "पैरेंट" कोड के सख्त नियमों के कारण, BCH कोड के संदेशों को बहुत अधिक "भारी" (जिसका अर्थ है कि वे अधिक त्रुटियों को संभाल सकते हैं) होने के लिए मजबूर किया जाता है, जितना कि मानक दीवार की ऊंचाई बताती है।

परिणाम क्या रहा? उन्होंने कोड्स का एक अनंत परिवार बनाया जहाँ वास्तविक न्यूनतम दूरी, बोस डिस्टेंस से स्पष्ट रूप से अधिक है। वास्तव में, उन्होंने एक विशिष्ट सेट के मापदंडों (जहाँ कोड की लंबाई $m$ से संबंधित है जो 10 से कम से अधिक है और 12 के बराबर नहीं है) के लिए सिद्ध किया कि यह अंतर केवल 4 जैसा छोटा नंबर नहीं है। जैसे-जैसे कोड लंबे होते जाते हैं, यह अंतर काफी बढ़ जाता है।

उदाहरण के लिए, यदि आप एक बाइनरी कोड (वह प्रकार जो अधिकांश कंप्यूटरों में उपयोग किया जाता है) लेते हैं जिसकी लंबाई $m=13$ से संबंधित है (जिसका अर्थ है कि कोड की लंबाई 8191 है), तो अनुमानित दूरी और वास्तविक दूरी के बीच का अंतर $2^{\lfloor(13-1)/3\rfloor-1}$ है। यह गणना एक 8 के अंतर को दर्शाती है, जो पहले से ही उस सीमा से दोगुना है जिसे चारपिन के कंजैचर ने अनुमति दी थी। लेकिन जैसे-जैसे आप कोड को बड़ा बनाते हैं (m को बढ़ाते हैं), यह अंतर केवल 8 पर नहीं रुकता; यह तेजी से फैलता है। यह कोड की लंबाई के क्यूब रूट (घनमूल) के रूप में बढ़ता है, जिसका अर्थ है कि बहुत बड़े कोड्स के लिए, वास्तविक शक्ति पुराने अनुमानों की तुलना में बहुत श्रेष्ठ है।

यह इतने लंबे समय तक छिपा क्यों रहा?

आप सोच सकते हैं, "यदि यह इतना बड़ी बात है, तो किसी ने इसे पहले क्यों नहीं खोजा?" लेखक बताते हैं कि उनके द्वारा खोजा गया सबसे छोटा काउंटर-एग्जांपल (counterexample) 8191 की कोड लंबाई की मांग करता है। पिछले कंप्यूटर खोजों ने, जिन्होंने इस कंजैचर को बनाने में मदद की थी, केवल 511 की लंबाई तक के कोड्स की जांच की थी। यह चूहों से भरे कमरे में एक विशाल हाथी को खोजने जैसा है; यदि आप केवल चूहों को देखते हैं, तो आप हाथी को कभी नहीं देख पाएंगे। उन्होंने जो घटना खोजी है, वह इतनी बड़ी है कि इसे पहले के छोटे पैमाने के प्रयोगों द्वारा नहीं देखा जा सकता था।

निष्कर्ष

यह शोध पत्र चारपिन के कंजैचर को निर्णायक रूप से गलत साबित करता है। यह दिखाता है कि प्रिमिटिव नैरो-सेंस (primitive narrow-sense) BCH कोड्स की न्यूनतम दूरी, बोस डिस्टेंस के ऊपर एक छोटे, निश्चित नंबर द्वारा सीमित नहीं है। इसके बजाय, यह अंतर मनमाना रूप से बड़ा हो सकता है, और जैसे-जैसे कोड लंबा होता जाता है, यह बढ़ता जाता है।

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

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

तकनीकी सारांश: चारपिन के अनुमान (Charpin's Conjecture) के प्रति उदाहरण

समस्या विवरण
बोस-चाउड्रुह्यू-हॉकक्वेम (BCH) कोड का सटीक न्यूनतम दूरी ( $d$ ) निर्धारित करना कोडिंग थ्योरी में एक मौलिक और अनसुलझी चुनौती बनी हुई है। जबकि बोस दूरी ( $d_B$ )—जो एक विशिष्ट कोड उत्पन्न करने वाली सबसे बड़ी डिज़ाइन की गई दूरी है—BCH बाउंड के माध्यम से एक तीक्ष्ण निचला बाउंड प्रदान करती है ( $d \ge d_B$ ), वास्तविक $d$ का मान सामान्यतः अज्ञात रहता है।

चारपिन ने अनुमान लगाया था कि बाइनरी प्रिमिटिव नैरो-सेंस (narrow-sense) BCH कोड के लिए, वास्तविक न्यूनतम दूरी और बोस दूरी के बीच का अंतर एक छोटे पूर्ण स्थिरांक (absolute constant) द्वारा सीमित है। विशेष रूप से, यह अनुमान लगाया गया था कि किसी भी पूर्णांक $\delta$ के लिए, जो वैध रेंज में हो, $d(C(2,m,\delta)) \le d_B(C(2,m,\delta)) + 4$ होगा। यदि यह अनुमान सत्य होता, तो न्यूनतम दूरी निर्धारित करने की समस्या को $q$ -साइक्लोटॉमिक कोसेट लीडर्स (coset leaders) की एक संयोजी (combinatorial) समस्या में बदल दिया जाता। 511 तक की कोड लंबाई के व्यापक संख्यात्मक सत्यापन के बावजूद, नैरो-सेंस BCH कोड के लिए कोई प्रमाण या प्रति-उदाहरण रिपोर्ट नहीं किया गया था।

कार्यप्रणाली
लेखक एक अनंत परिवार के प्रिमिटिव नैरो-सेंस BCH कोडों का निर्माण करके चारपिन के अनुमान का खंडन करते हैं, जहाँ न्यूनतम दूरी, बोस दूरी से काफी अधिक है। मुख्य कार्यप्रणाली में शामिल हैं:

सामान्यीकृत रीड-मुलर (GRM) कोड में एम्बेडिंग: लेखक विशिष्ट BCH कोडों को पंक्चर किए गए (punctured) GRM कोड ( $PGRM_q(\ell, m)$ ) के उप-कोड (subcodes) के रूप में पहचानते हैं। यह कोड्स के परिभाषित सेटों का विश्लेषण करके प्राप्त किया जाता है।
भार विभाज्यता बाधाएं (Weight Divisibility Constraints): परिमित क्षेत्रों (finite fields) पर बहुपदों के शून्य की संख्या पर 'एक्स के प्रमेय' (Ax's theorem) का लाभ उठाते हुए, लेखक यह स्थापित करते हैं कि इसमें शामिल GRM कोडों के कोडवर्ड्स को विशिष्ट भार विभाज्यता शर्तों को पूरा करना चाहिए। विशेष रूप से, $GRM_q(\ell, m)$ के कोडवर्ड्स का भार $q^{\lfloor (m-1)/\ell \rfloor}$ से विभाज्य होता है।
गैप फोर्सिंग (Gap Forcing): विभाज्यता संबंधी बाधाएं डिज़ाइन की गई दूरी के ठीक ऊपर एक विशिष्ट अंतराल के भीतर कोडवर्ड भारों को वर्जित करती हैं। यह BCH उप-कोड की न्यूनतम दूरी को अगले अनुमत भार तक जाने के लिए मजबूर करता है, जिससे $d$ और $d_B$ के बीच एक अंतराल (gap) उत्पन्न होता है।
कोसेट लीडर विश्लेषण: लेखक कठोरता से सिद्ध करते हैं कि उनके द्वारा निर्मित मापदंडों के लिए, डिज़ाइन की गई दूरी $\delta$ वास्तव में एक कोसेट लीडर है, जो यह सुनिश्चित करता है कि बोस दूरी $d_B$ ठीक $\delta$ है।

मुख्य योगदान और परिणाम
यह शोध पत्र निम्नलिखित मुख्य परिणाम (प्रमेय 1) प्रस्तुत करता है:

निर्माण: मान लीजिए $q$ एक अभाज्य घात (prime power) है, $m \ge 10$ और $m \neq 12$ है। $u = \lfloor m/4 \rfloor$ और $t = \lfloor (m-1)/3 \rfloor$ को परिभाषित करें। किसी भी पूर्णांक $s$ के लिए जहाँ $u \le s < t$ हो, डिज़ाइन की गई दूरी होगी:
$\delta = q^m - q^{m-1} - q^{m-1-u} - q^s - 1$
बोस दूरी: प्रिमिटिव नैरो-सेंस BCH कोड $C(q,m,\delta)$ की बोस दूरी ठीक $\delta$ ( $d_B = \delta$ ) है।
न्यूनतम दूरी: न्यूनतम दूरी इस प्रकार है: $d \ge \delta + q^s$ ।
बाइनरी केस समानता: बाइनरी केस ( $q=2$ ) के लिए, न्यूनतम दूरी ठीक $d = \delta + 2^s$ है।

चारपिन के अनुमान का खंडन
बाइनरी केस में $s = t - 1$ निर्धारित करके, लेखक कोडों का एक उप-परिवार प्राप्त करते हैं जहाँ न्यूनतम दूरी और बोस दूरी के बीच का अंतर है:
$d - d_B = 2^{\lfloor (m-1)/3 \rfloor - 1}$
यह अंतराल:

सभी $m \ge 13$ के लिए 4 से अधिक है।
$m$ के साथ चरघातांकीय (exponentially) रूप से बढ़ता है (या कोड की लंबाई के घनमूल के रूप में बढ़ता है)।
चारपिन के इस अनुमान का सीधा खंडन करता है कि अंतराल 4 तक सीमित है।

सबसे छोटा प्रति-उदाहरण $m=13$ (कोड लंबाई 8191) पर होता है, जो यह स्पष्ट करता है कि क्यों पिछला संख्यात्मक गणना जो 511 तक की लंबाई तक सीमित था, इस अनुमान को चुनौती नहीं दे सका।

महत्व
यह शोध पत्र प्रदर्शित करता है कि प्रिमिटिव नैरो-सेंस BCH कोड के लिए न्यूनतम दूरी और बोस दूरी के बीच का अंतर केवल छोटा ही नहीं, बल्कि अत्यधिक बड़ा हो सकता है, जो कोड की लंबाई के एक निश्चित घात के रूप में बढ़ता है। यह परिणाम इस अपेक्षा को अमान्य करता है कि $d$ और $d_B$ एक स्थिरांक द्वारा निकटता से जुड़े हुए हैं। फलस्वरूप, BCH कोड की सटीक न्यूनतम दूरी निर्धारित करना केवल कोसेट लीडर्स के संयोजी गुणों तक सीमित नहीं किया जा सकता; कोड के संरचनात्मक गुण (विशेष रूप से रीड-मुलर कोड और भार विभाज्यता के साथ उनका संबंध) एक महत्वपूर्ण भूमिका निभाते हैं। लेखक नोट करते हैं कि जबकि उन्होंने अंतराल के लिए एक निचला बाउंड स्थापित किया है, दी गई लंबाई के लिए $d - d_B$ का सटीक अधिकतम संभव मान अभी भी एक खुला प्रश्न है।

बड़ी खोज: "चार-त्रुटि" नियम को तोड़ना

यह इतने लंबे समय तक छिपा क्यों रहा?

निष्कर्ष

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