🔢 mathematics

Proximity Gaps Conjecture Fails Near Capacity over Prime Fields

यह शोध पत्र सिद्ध करता है कि प्राइम फील्ड्स पर रीड-सोलोमन कोड्स के एक विशिष्ट परिवार के लिए, प्रोक्सिमिटी गैप्स कंजेक्चर (Proximity Gaps Conjecture) कोड की क्षमता दर (capacity rate) के $O(1/\log n)$ के भीतर के रेडियस पर विफल हो जाता है, जिससे क्राचुन और काज़ानिन द्वारा दिए गए एक स्केच को औपचारिक रूप दिया गया है।

मूल लेखक: Antonio Kambiré

प्रकाशित 2026-04-14

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

CC BY 4.0

मूल लेखक: Antonio Kambiré

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

यहाँ शोध पत्र "Proximity Gaps Conjecture Fails Near Capacity over Prime Fields" का सरल भाषा में अनुवाद दिया गया है, जिसमें रोजमर्रा के उदाहरणों का उपयोग किया गया है।

मुख्य विचार: एक टूटी हुई धारणा (A Broken Rule of Thumb)

कल्पना कीजिए कि आप नियमों के एक बहुत ही विशिष्ट सेट (एक Reed-Solomon code) का उपयोग करके एक गुप्त संदेश भेजने की कोशिश कर रहे हैं। ये नियम एक "जादुय ग्रिड" की तरह हैं जहाँ केवल कुछ खास पैटर्न वाले डॉट्स (बिंदुओं) की ही अनुमति है। यदि आप एक ऐसा संदेश भेजते हैं जो थोड़ा अस्त-व्यस्त है (जिसमें कुछ गलतियाँ हैं), तो प्राप्तकर्ता आमतौर पर इसे आसानी से ठीक कर सकता है।

लंबे समय तक, गणितज्ञों को एक "नियम" पर विश्वास था जिसे Proximity Gaps Conjecture कहा जाता है। यह सरल शब्दों में इस प्रकार काम करता है:

कन्जेक्चर (Conjecture): कल्पना कीजिए कि आपने कागज पर एक सीधी रेखा खींची है। यदि आप उस रेखा पर कई अलग-अलग बिंदु चुनते हैं, और प्रत्येक बिंदु एक वैध "जादुय पैटर्न" के बहुत करीब दिखता है, तो वह पूरी रेखा एक विशेष "डबल पैटर्न" (interleaved code) के करीब होनी चाहिए।

इसे इस तरह समझें: यदि आप लोगों की एक कतार देखते हैं, और लगभग हर व्यक्ति एक यूनिफॉर्म पहने हुए दिखता है, तो आप मान लेते हैं कि वह पूरी कतार एक मार्चिंग बैंड की है। आप यह उम्मीद नहीं करेंगे कि वह कतार अचानक रैंडम लोगों का एक अराजक मिश्रण होगी, सिर्फ इसलिए कि वे व्यक्तिगत रूप से एक जैसे दिख रहे हैं।

यह शोध पत्र सिद्ध करता है कि यह "नियम" गलत है जब आप सिस्टम को उसकी पूर्ण सीमा (capacity) के बिल्कुल करीब ले जाते हैं।

उपमा (The Analogy): "लगभग-परफेक्ट" रेखा

आइए उस विशिष्ट परिदृश्य को समझते हैं जिसे लेखकों ने इस नियम को तोड़ने के लिए बनाया।

1. सेटअप: जादुय ग्रिड और रेखा

कोड (ग्रिड): कल्पना कीजिए कि एक विशाल चेकरबोर्ड है जहाँ केवल विशिष्ट वर्ग ही "वैध" (valid) हैं।
रेखा: कल्पना कीजिए कि आप इस बोर्ड पर एक सीधी रेखा खींच रहे हैं। यह रेखा एक गणितीय सूत्र ($f + zg $) का प्रतिनिधित्व करती है। जैसे-जैसे आप वेरिएबल$ z$ को बदलते हैं, आप रेखा पर आगे बढ़ते हैं।
"निकट-कोडवर्ड्स" (Near-Codewords): लेखकों ने एक विशिष्ट रेखा खोजी है जहाँ, यदि आप रेखा पर कई अलग-अलग स्थानों पर रुकते हैं, तो प्रत्येक स्थान एक वैध चेकरबोर्ड पैटर्न जैसा लगभग दिखता है। यह इतना करीब है कि एक कंप्यूटर कहेगा, "यह निश्चित रूप से एक वैध पैटर्न है, बस इसमें थोड़ा सा शोर (noise) है।"

2. आश्चर्य: रेखा एक झूठ है

पुराने नियम (कन्जेक्चर) के अनुसार, यदि वे सभी बिंदु वैध दिखते हैं, तो वह पूरी रेखा एक "वैध डबल पैटर्न" होनी चाहिए।

लेखकों ने सिद्ध किया कि यह गलत है।
उन्होंने दिखाया कि एक ऐसी रेखा जहाँ:

बिंदु A: एक वैध पैटर्न जैसा 99% दिखता है।
बिंदु B: एक वैध पैटर्न जैसा 99% दिखता है।
बिंदु C: एक वैध पैटर्न जैसा 99% दिखता है।
...और इसी तरह सैकड़ों बिंदु।

लेकिन, वह रेखा स्वयं एक वैध पैटर्न नहीं है।
उन्होंने दिखाया कि यह एक "नकली" रेखा है जो केवल संयोग से कई वैध दिखने वाले बिंदुओं से होकर गुजरती है। यह उन लोगों की एक कतार की तरह है जिन्होंने लाल शर्ट पहनी है, लेकिन वे मार्चिंग बैंड नहीं हैं; वे बस रैंडम लोग हैं जिन्होंने एक ही दुकान से लाल शर्ट खरीदी है।

उन्होंने यह कैसे किया? (विधि/रेसिपी)

लेखकों ने केवल अनुमान नहीं लगाया; उन्होंने इस "नकली रेखा" को बनाने के लिए एक गणितीय मशीन बनाई। उन्होंने दो मुख्य सामग्रियों का उपयोग किया:

सामग्री 1: "ग्रुप होपिंग" (Group Hopping) का तरीका

उन्होंने एक मल्टीप्लिकेटिव सबग्रुप (multiplicative subgroup) नामक गणितीय संरचना का उपयोग किया।

उपमा: कल्पना कीजिए कि 100 घंटों वाली एक घड़ी है। यदि आप केवल 5 के गुणजों (5, 10, 15...) को देखते हैं, तो आपको एक विशिष्ट पैटर्न मिलता है।
उन्होंने एक ऐसी रेखा बनाई जहाँ "त्रुटियाँ" (errors - जो पैटर्न को अमान्य बनाती हैं) इस तरह छिपी होती हैं कि जब उन्हें विशिष्ट समूहों में जोड़ा जाता है, तो वे अधिकांश बोर्ड पर एक-दूसरे को पूरी तरह से रद्द (cancel) कर देती हैं। यह रेखा को कई बिंदुओं पर वैध दिखाता है, भले ही वह वैध न हो।

सामग्री 2: "प्राइम नंबर लॉटरी" (Prime Number Lottery)

यह सुनिश्चित करने के लिए कि यह तरीका काम करे, उन्हें एक विशिष्ट प्रकार के नंबर (एक अभाज्य संख्या/प्राइम नंबर) की आवश्यकता थी जो उनके बोर्ड के "आकार" के रूप में कार्य करे।

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

यह क्यों महत्वपूर्ण है?

आप पूछ सकते हैं, "गणित का कोई नियम टूट जाए तो किससे फर्क पड़ता है?"

यह सीमाओं को परिभाषित करता है: यह शोध पत्र हमें बताता है कि हम "परफेक्ट" ट्रांसमिशन रेट के कितने करीब जा सकते हैं, इससे पहले कि त्रुटि सुधार (error correction) के नियम टूटने लगें। यह ठीक वैसा ही है जैसे यह जानना कि कार के टायर कब सड़क से पकड़ खोना शुरू कर देते हैं।
सुरक्षा और क्रिप्टोग्राफी: कई आधुनिक एन्क्रिप्शन सिस्टम इन्हीं कोड्स पर निर्भर करते हैं। यदि हम सोचते कि "नियम" हमेशा सच होता, तो हमने शायद ऐसे सुरक्षा सिस्टम बनाए होते जो हमारी सोच से कहीं अधिक कमजोर होते। यह जानना कि नियम कहाँ विफल होता है, हमें मजबूत ताले बनाने में मदद करता है।
डेटा स्टोरेज: जब हम हार्ड ड्राइव या क्लाउड में डेटा स्टोर करते हैं, तो हम बिगड़े हुए बिट्स (corrupted bits) को ठीक करने के लिए इन कोड्स का उपयोग करते हैं। यह शोध इंजीनियरों को डेटा भ्रष्टाचार (data corruption) के सबसे खराब परिदृश्यों को समझने में मदद करता है।

एक वाक्य में सारांश

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

यहाँ एंटोनियो कैम्बिरे (Antonio Kambiré) के शोध पत्र "Proximity Gaps Conjecture Fails Near Capacity over Prime Fields" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र प्राइम फील्ड्स (prime fields) पर रीड-सोलोमन (RS) कोड के संदर्भ में प्रॉक्सिमिटी गैप्स कंजेक्चर (Proximity Gaps Conjecture) को संबोधित करता है।

कन्जैक्चर (अनुमान): पूर्व कार्य [2] में प्रस्तुत यह अनुमान यह प्रस्तावित करता है कि यदि एक एफाइन लाइन $f + zg $पर बिंदुओं का एक महत्वपूर्ण अंश रीड-सोलोमन कोड$ \mathcal{C}$ के "करीब" है, तो पूरी लाइन को एक निकटवर्ती कोडपेयर (codeword pair) द्वारा "व्याख्यायित" किया जाना चाहिए। विशेष रूप से, पेयर $[f, g]$ को संगत इंटरलीव्ड रीड-सोलोमन कोड $\mathcal{C}^2$ के करीब होना चाहिए (एक स्थिति जिसे कोरिलेटेड एग्रीमेंट कहा जाता है)।
गैप (अंतराल): जबकि यह घटना जॉनसन बाउंड (Johnson bound) तक अच्छी तरह से समझी जा चुकी है, जॉनसन बाउंड के ऊपर लेकिन सूचना-सैद्धांतिक क्षमता (information-theoretic capacity) ( $1 - k/n$ ) के पास इसके व्यवहार के बारे में स्पष्टता की कमी है।
उद्देश्य: लेखक क्षमता के निकट वाले क्षेत्र (near-capacity regime) में इस कन्जैचर को गलत सिद्ध करने का लक्ष्य रखते हैं। वे एक ऐसे RS कोड परिवार का निर्माण करना चाहते हैं जहाँ एक ऐसी रेखा मौजूद हो जिसमें कई बिंदु कोड के करीब हों, फिर भी वह रेखा स्वयं इंटरलीव्ड कोड के करीब न हो (अर्थात, कोरिलेटेड एग्रीमेंट विफल हो जाए)।

2. कार्यप्रणाली (Methodology)

इसका प्रमाण कोडिंग थ्योरी और मात्रात्मक संख्या सिद्धांत (quantitative number theory) का एक रचनात्मक प्रति-उदाहरण (constructive counterexample) है। कार्यप्रणाली दो मुख्य चरणों में आगे बढ़ती है:

A. कोडिंग-थ्योरेटिक निर्माण (The Counterexample)

लेखक शब्दों के स्पेस $\mathbb{F}_p^D$ के भीतर एक विशिष्ट रेखा $L = \{f + \lambda g \mid \lambda \in \mathbb{F}_p\}$ का निर्माण करते हैं।

पैरामीटर्स: वे एक कोड $\mathcal{C} = \text{RS}[\mathbb{F}_p, D, k]$ को परिभाषित करते हैं जहाँ $D$ , $\mathbb{F}_p^*$ के एक प्रिमिटिव $n$ -वें रूट ऑफ यूनिटी द्वारा जनरेट किया गया एक मल्टीप्लिकेटिव सबग्रुप है।
रेखा (The Line): फलन (functions) मोनोमियल्स के रूप में चुने गए हैं: $f = X^{rm}$ और $g = X^{(r-1)m}$ ।
तंत्र (The Mechanism):
1. वे एक सेट $H$ (एक सबग्रुप) को परिभाषित करते हैं और $H$ के $r$ अलग-अलग तत्वों के योगों पर विचार करते हैं।
2. किसी भी $\lambda$ के लिए जो ऐसे योग से बना है, बहुपद $X^{rm} - \lambda X^{(r-1)m}$ , $D$ के एक बड़े उपसमुच्चय (विशेष रूप से, $H$ के $r$ कॉसेट्स का यूनियन) पर शून्य हो जाता है।
3. यह शून्य होने का गुण यह दर्शाता है कि $f + \lambda g$ , आकार $(1-\delta)n$ के सेट पर एक निम्न-डिग्री बहुपद (डिग्री $\le (r-2)m$ ) के साथ सहमत (agree) होता है।
4. फलस्वरूप, हैमिंग दूरी $\Delta(f + \lambda g, \mathcal{C}) \le \delta$ होती है।
कोरिलेटेड एग्रीमेंट की विफलता: लेखक यह सिद्ध करते हैं कि भले ही रेखा के कई बिंदु $\mathcal{C}$ के करीब हों, लेकिन पेयर $[f, g]$ , $\mathcal{C}^2$ से दूर है। यदि कोरिलेटेड एग्रीमेंट लागू होता, तो $g$ को एक ऐसे सेट पर निम्न-डिग्री बहुपद के साथ सहमत होना पड़ता जो उसके डिग्री की अनुमति से बड़ा हो, जिससे एक विरोधाभास उत्पन्न होता।

B. मात्रात्मक संख्या-सिद्धांत संबंधी तर्क (Existence of Parameters)

यह सुनिश्चित करने के लिए कि प्रति-उदाहरण काम करे, लेखकों को एक ऐसा प्राइम $p$ और पर्याप्त संख्या में अलग-अलग स्केलर्स (sums) की उपस्थिति सिद्ध करनी होगी ताकि ये योग आपस में न टकराएं (अर्थात, अलग-अलग उपसमुच्चय के योग $p$ के मॉड्यूल में एक ही मान पर न आएं)।

लिनिक का प्रमेय (Linnik's Theorem): वे अंकगणितीय प्रगति (arithmetic progression) में सबसे छोटे प्राइम पर लिनिक के प्रमेय के एक मात्रात्मक संस्करण का उपयोग करते हैं। यह गारंटी देता है कि $[4s, 8s]$ अंतराल में एक प्राइम $p$ मौजूद है जहाँ $p \equiv 1 \pmod n$ है।
टकराव से बचाव (Collision Avoidance): वे उन "बुरे" प्राइम्स का विश्लेषण करते हैं जो अलग-अलग सबसेट सम्स को टकराने (collide) के लिए मजबूर करते हैं। विशिष्ट बहुपदों के रिसल्टेंट (resultant) को बाउंड करके, वे दिखाते हैं कि ऐसे बुरे प्राइम्स की संख्या अंतराल में कुल प्राइम्स की तुलना में नगण्य है।
परिणाम: यह सुनिश्चित करता है कि एक "अच्छा" प्राइम $p < n^A$ मौजूद है जहाँ अलग-अलग योगों की संख्या $|\mathcal{H}^{(r)}|$ , $n^C$ की तरह पॉलिनोमियल रूप से बड़ी है।

3. मुख्य योगदान (Key Contributions)

क्षमता के पास प्रॉक्सिमिटी गैप्स का खंडन: यह शोध पत्र पहला स्पष्ट निर्माण प्रदान करता है जो यह दर्शाता है कि प्राइम फील्ड्स पर रीड-सोलोमन कोड के लिए $\delta = (1 - k/n) - \Omega(1/\log n)$ रेडियस पर प्रॉक्सिमिटी गैप्स कन्जैचर विफल हो जाता है। यह क्षमता सीमा के असाधारण रूप से करीब है।
स्पष्ट पैरामीट्राइजेशन: पिछले रेखाचित्रों (sketches) के विपरीत, यह कार्य सभी बाउंड्स और पैरामीटर विकल्पों को स्पष्ट बनाता है। यह ब्लॉक लेंथ $n$ , डायमेंशन $k$ , फील्ड साइज $p$ , और डिस्टेंस पैरामीटर $\delta$ के बीच संबंध को परिभाषित करता है।
क्षेत्रों का संश्लेषण: यह प्रमाण बीजगणितीय कोडिंग थ्योरी (रीड-सोलोमन संरचना, मल्टीप्लिकेटिव सबग्रुप्स) को विश्लेषणात्मक संख्या सिद्धांत (लिनिक का प्रमेय, अंकगणितीय प्रगति में प्राइम्स का वितरण, रिसल्टेंट्स) के साथ सफलतापूर्वक जोड़ता है।
मात्रात्मक बाउंड्स: लेखक विशिष्ट स्थिरांक ( $C, \rho, A$ ) प्राप्त करते हैं जो यह दर्शाते हैं कि विफलता $n^C$ के पैमाने वाले बिंदुओं के लिए होती है, जो लिस्ट-डिकोडिंग अनुप्रयोगों के लिए महत्वपूर्ण है।

4. मुख्य परिणाम (Main Results)

प्रमेय 1 (Theorem 1): किसी भी स्थिरांक $C > 0$ और दर $\rho \in (0, 1/2)$ के लिए, अनंत रूप से कई ब्लॉक लेंथ $n$ और डायमेंशन $k$ मौजूद हैं कि:

एक प्राइम $p < n^A$ (जहाँ $A$ एक स्थिरांक है जो $\rho$ और $C$ पर निर्भर करता है) मौजूद है।
कोड $\mathcal{C} = \text{RS}[\mathbb{F}_p, D, k]$ $C = RS [F_{p}, D, k]$ के लिए (जहाँ $D$ $D$ , $n$ $n$ -वें रूट्स ऑफ यूनिटी का समूह है):
- शब्द $f, g \in \mathbb{F}_p^D$ मौजूद हैं।
- कम से कम $n^C$ अलग-अलग स्केलर्स $z \in \mathbb{F}_p$ मौजूद हैं कि हैमिंग दूरी $\Delta(f + zg, \mathcal{C}) \le \delta$ है।
- हालांकि, इंटरलीव्ड कोड के लिए दूरी $\Delta([f, g], \mathcal{C}^2) > \delta$ है।
यहाँ, $\delta = (1 - k/n) - \Omega(1/\log n)$ है, जिसका अर्थ है कि विफलता क्षमता सीमा के ठीक नीचे होती है।

5. महत्व (Significance)

सैद्धांतिक सीमाएँ: यह परिणाम प्रॉक्सिमिटी गैप्स कन्जैचर की सीमा को स्पष्ट करता है, यह प्रदर्शित करता है कि यह प्राइम फील्ड्स के लिए सूचना-सैद्धांतिक सीमा तक नहीं जाता है। यह सुझाव देता है कि "लिस्ट-डिकोडेबिलिटी" या "कर्व-डिकोडेबिलिटी" जैसे गुण उन क्षेत्रों में विफल हो सकते हैं जिन्हें पहले सुरक्षित माना जाता था।
क्रिप्टोग्राफी और FRI के निहितार्थ: रीड-सोलोमन कोड आधुनिक क्रिप्टोग्राफिक प्रोटोकॉल, विशेष रूप से FRI (Fast Reed-Solomon Interactive Oracle Proofs) के लिए आधारभूत हैं, जिनका उपयोग ज़ीरो-नॉलेज प्रूफ में किया जाता है। क्षमता के निकट उच्च-रेट वाले क्षेत्र में प्रॉक्सिमिटी गैप्स की विफलता यह संकेत देती है कि कन्जैचर पर आधारित कुछ सुरक्षा धारणाओं या साउंडनेस तर्कों का पुनर्मूल्यांकन करने की आवश्यकता हो सकती है।
समवर्ती कार्य (Concurrent Work): शोध पत्र उल्लेख करता है कि इसके परिणामों का उपयोग प्राइम फील्ड्स पर रीड-सोलोमन कोड की लिस्ट-डिकोडेबिलिटी के संबंध में कन्जैक्चर को औपचारिक रूप देने के लिए समवर्ती कार्य ( [3] के परिशिष्ट A.5 में) में किया गया था, जो कोडिंग थ्योरी के भविष्य के अनुसंधान के लिए एक आधारभूत निर्माण खंड के रूप में इसकी भूमिका को रेखांकित करता है।

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