🔢 mathematics

Perfect codes in weakly metric association schemes

यह शोध पत्र बहुपद दुर्बल मीट्रिक एसोसिएशन स्कीम्स (polynomial weakly metric association schemes) की अवधारणा प्रस्तुत करता है और ली (Lee), एनआरटी (NRT), मिश्रित हैमिंग (mixed Hamming), और सम-रैंक (sum-rank) दूरियों सहित विभिन्न मीट्रिक्स में परफेक्ट कोड्स के लिए गैर-अस्तित्व संबंधी परिणाम प्राप्त करने के लिए लॉयड प्रमेय (Lloyd Theorem) को श्वार्ट्ज-ज़िपल लेम्मा (Schwartz-Zippel Lemma) के साथ संयोजित करता है।

मूल लेखक: Minjia Shi, Jing Wang, Patrick Solé

प्रकाशित 2026-06-02

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

CC BY 4.0

मूल लेखक: Minjia Shi, Jing Wang, Patrick Solé

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

कल्पना कीजिए कि आप एक विशाल, बहु-आयामी (multi-dimensional) गोदाम को एक जैसे, पूरी तरह से गोल बक्सों से भरने की कोशिश कर रहे हैं। आपका लक्ष्य इन बक्सों को इस तरह व्यवस्थित करना है कि गोदाम के फर्श का हर एक वर्ग इंच ठीक एक बॉक्स द्वारा कवर हो जाए, बिना किसी खाली जगह या ओवरलैप के। गणित और कोडिंग थ्योरी की दुनिया में, इसे एक "परफेक्ट कोड" (perfect code) खोजना कहा जाता है।

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

यहाँ वे इस रहस्य को सुलझाते हैं, जिसे सरल अवधारणाओं में विभाजित किया गया है:

1. गोदाम और उसके नियम (सेटिंग)

कोडिंग थ्योरी में, डेटा को संख्याओं की एक सूची के रूप में भेजा जाता है (जैसे 0 और 1 की एक लंबी स्ट्रिंग, या किसी अलग भाषा में संख्याएँ)।

स्थान (The Space): गोदाम को एक विशाल ग्रिड के रूप में सोचें जहाँ प्रत्येक बिंदु एक संभावित संदेश का प्रतिनिधित्व करता है।
दूरी (The Distance): आमतौर पर, हम दूरी को यह गिनकर मापते हैं कि कितने अक्षर अलग हैं (जैसे "cat" बनाम "bat" के बीच की दूरी 1 है)। लेकिन इस शोध पत्र में, वे दूरी को मापने के अधिक जटिल तरीकों को देखते हैं, जैसे कि ली मेट्रिक (Lee metric) (जहाँ संख्याएँ घड़ी की तरह घूमती हैं) या NRT मेट्रिक (जहाँ संख्या की स्थिति संख्या से अधिक महत्वपूर्ण होती है)।
परफेक्ट कोड (The Perfect Code): एक परफेक्ट कोड "केंद्र बिंदुओं" (संदेशों) का एक समूह है ताकि यदि आप प्रत्येक केंद्र के चारों ओर एक निश्चित आकार का घेरा (या गोला) खींचें, तो वे बिना ओवरलैप के पूरे गोदाम को कवर कर लें।

2. पुराना सुराग: लॉयड थ्योरम (The Old Clue: The Lloyd Theorem)

दशकों से, गणितज्ञों के पास लॉयड थ्योरम नामक एक उपकरण रहा है। इसे एक "जादुई चेकलिस्ट" के रूप में सोचें।

यदि एक परफेक्ट कोड हो सकता है, तो यह थ्योरम कहता है कि एक विशिष्ट गणितीय रेसिपी (एक बहुपद समीकरण/polynomial equation) में पूर्णांकों (whole numbers) के रूप में कुछ निश्चित "रूट्स" (solutions) होने चाहिए।
यदि रेसिपी में पर्याप्त पूर्णांक समाधान नहीं हैं, तो एक परफेक्ट कोड अस्तित्व में नहीं हो सकता।

हालाँकि, पुरानी चेकलिस्ट सीमित थी। यह साधारण, मानक गोदामों (जैसे हैमिंग मेट्रिक) के लिए अच्छी तरह काम करती थी, लेकिन ऊपर बताए गए अधिक जटिल, "अजीब" गोदामों (जैसे ली या NRT मेट्रिक्स) के लिए यह विफल हो गई या अस्पष्ट उत्तर देती थी।

3. नया उपकरण: श्वार्ट्ज-ज़िपेल लेम्मा (The New Tool: The Schwartz-Zippel Lemma)

लेखकों ने पुराने चेकलिस्ट को कंप्यूटर विज्ञान के एक नए, शक्तिशाली उपकरण श्वार्ट्ज-ज़िपेल लेम्मा के साथ जोड़ने का निर्णय लिया।

उपमा (The Analogy): कल्पना करें कि आपके पास एक विशाल, बहु-रंगीन केक (एक multi-variable polynomial) है। आप जानना चाहते हैं कि क्या केक पर कोई ऐसे स्थान हैं जो "शून्य" (खाली) हैं।
श्वार्ट्ज-ज़िपेल लेम्मा एक नियम की तरह है जो कहता है: "यदि आपके पास एक निश्चित संख्या में सामग्रियाँ (variables) और एक निश्चित जटिलता (degree) वाला केक है, तो आपके पास कितने खाली स्थान हो सकते हैं, इसकी एक सख्त सीमा है।"
ट्विस्ट: लेखकों ने महसूस किया कि इन जटिल गोदामों के लिए, "जादुई चेकलिस्ट" (लॉयड थ्योरम) उन समाधानों की मांग करती है जो श्वार्ट्ज-ज़िपेल नियम द्वारा निर्धारित सीमाओं के भीतर भौतिक रूप से संभव नहीं हैं।

4. "डिस्पर्शन" की समस्या (The "Dispersion" Problem)

इसे काम करने के लिए, उन्होंने एक नई अवधारणा डिस्पर्शन फंक्शन (Dispersion Function) पेश की।

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

5. निर्णय: "यहाँ कोई परफेक्ट कोड नहीं है" (The Verdict: "No Perfect Codes Here")

इन दोनों विचारों को मिलाकर, लेखकों ने एक "मास्टर थ्योरम" निकाला। उन्होंने इसे चार विशिष्ट प्रकार के जटिल गोदामों पर लागू किया:

ली मेट्रिक (Lee Metric): डिजिटल घड़ियों या मॉड्यूलर अंकगणित जैसी चीजों के लिए उपयोग किया जाता है।
NRT मेट्रिक (NRT Metric): रैंडम नंबर जेनरेट करने और डेटा ब्लॉक्स को संभालने के लिए उपयोग किया जाता है।
सम-रैंक मेट्रिक (Sum-Rank Metric): नेटवर्क कोडिंग (इंटरनेट पर डेटा भेजने) में उपयोग किया जाता है।
मिक्स्ड अल्फाबेट कोड (Mixed Alphabet Codes): जहाँ संदेश के विभिन्न भाग अलग-अलग "भाषाओं" का उपयोग करते हैं (जैसे, कुछ भाग बाइनरी हैं, अन्य बेस-3 हैं)।

परिणाम: इन चार परिदृश्यों में, कुछ शर्तों के तहत (आमतौर पर जब गोदाम बहुत बड़ा होता है या बक्से एक विशिष्ट आकार के होते हैं), गणित यह सिद्ध करता है कि परफेक्ट पैकिंग असंभव है। "भीड़" बहुत बड़ी है, और "नियम" एक सटीक फिट की अनुमति नहीं देते हैं।

6. उन्होंने क्या नहीं किया

यह ध्यान रखना महत्वपूर्ण है कि यह शोध पत्र क्या नहीं करता है:

उन्होंने बक्सों को पैक करने का नया तरीका नहीं बनाया।
उन्होंने यह नहीं कहा कि ये कोड बेकार हैं; उन्होंने केवल यह सिद्ध किया कि इन विशिष्ट सेटिंग्स में उनका परफेक्ट संस्करण मौजूद नहीं है।
उन्होंने सभी ली कोड्स (Lee codes) के बारे में 50 साल पुराने अनुमान (conjecture) को हल नहीं किया (वह अभी भी खुला है), लेकिन उन्होंने पुख्ता सबूत दिए कि बड़े आकार के लिए परफेक्ट कोड्स के अस्तित्व में होने की संभावना कम है।

सारांश

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

तकनीकी सारांश: वीकली मेट्रिक एसोसिएशन स्कीम्स में परफेक्ट कोड्स

समस्या विवरण
यह शोध पत्र उन परिमित मीट्रिक स्पेस (finite metric spaces) के मापदंडों को वर्गीकृत करने की मौलिक समस्या को संबोधित करता है जो $e$ -परफेक्ट कोड्स (ऐसे कोड्स जहाँ स्थान को त्रिज्या $e$ वाले विलगित बॉल्स में विभाजित किया जाता है) को स्वीकार करते हैं। जबकि लॉयड थ्योरम (Lloyd Theorem) मानक मीट्रिक एसोसिएशन स्कीम्स में ऐसे कोड्स के अस्तित्व के लिए एक आवश्यक शर्त प्रदान करता है (विशेष रूप से एक लॉयड बहुपद का पूर्णांक बिंदुओं पर शून्य होना), कई कोडिंग परिदृश्य जो अत्यंत महत्वपूर्ण हैं—जैसे कि ली मीट्रिक (Lee metric), एनआरटी (NRT) मीट्रिक, मिश्रित वर्णमाला (mixed alphabets), और सम-रैंक दूरी (sum-rank distance)—कड़ाई से मीट्रिक एसोसिएशन स्कीम की परिभाषा को संतुष्ट नहीं करते हैं। पिछले सामान्यीकरण, जैसे कि सोले (1989) द्वारा पेश किया गया "वीकली मेट्रिक एसोसिएशन स्कीम्स" (WMAS) की अवधारणा, ने एक सामान्यीकृत लॉयड थ्योरम तो स्थापित किया, लेकिन तीन दशकों से अधिक समय तक कोई गैर-अस्तित्व परिणाम (non-existence results) प्राप्त नहीं किए। मुख्य चुनौती इन व्यापक, गैर-मीट्रिक संदर्भों में परफेक्ट कोड्स के लिए प्रभावी गैर-अस्तित्व मानदंड विकसित करना है।

कार्यप्रणाली
लेखक नए गैर-अस्तित्व परिणामों को प्राप्त करने के लिए दो अलग-अलग गणितीय ढांचों को जोड़ते हैं:

WMAS में सामान्यीकृत लॉयड थ्योरम: वे वीकली मेट्रिक एसोसिएशन स्कीम्स के ढांचे का उपयोग करते हैं, जहाँ यदि एक $e$ -परफेक्ट कोड मौजूद है, तो लॉयड बहुपद $\Psi^{(e)}(j)$ को कम से कम $\Pi(e) - 1$ बार शून्य होना चाहिए। यहाँ $\Pi(e)$ एक "डिस्पर्सन फंक्शन" (dispersion function) है, जो अधिकतम $e$ दूरी पर तत्वों को देने वाली क्लासेज की संख्या गिनता है।
श्वार्ट्ज़-ज़िपेल लेम्मा (Schwartz-Zippel Lemma): वे सैद्धांतिक कंप्यूटर विज्ञान से श्वार्ट्ज़-ज़िपेल लेम्मा का अनुप्रयोग करते हैं, जो एक परिमित डोमेन पर एक गैर-शून्य बहुचर बहुपद (multivariate polynomial) के शून्य (zeros) की संख्या पर एक ऊपरी सीमा प्रदान करता है। विशेष रूप से, $r$ चरों वाला $S$ सेट पर कुल डिग्री $e$ वाला एक बहुपद अधिकतम $e \cdot |S|^{r-1}$ शून्य रख सकता है।

इन अवधारणाओं को जोड़ने के लिए, लेखक $r$ -पॉलीनोमियल एसोसिएशन स्कीम्स की अवधारणा पेश करते हैं। एक WMAS $r$ -पॉलीनोमियल है यदि इसके प्रथम आइगेन मान (eigenvalues) विशिष्ट बिंदुओं पर $r$ चरों में मूल्यांकन किए गए बहुपद हैं। लॉयड बहुपद को अधिकतम $e$ डिग्री वाले एक बहुचर बहुपद के रूप में मानकर, लेखक आवश्यक शून्य संख्या ( $\Pi(e) - 1$ ) की तुलना श्वार्ट्ज़-ज़िपेल बाउंड द्वारा अनुमत अधिकतम शून्य संख्या ( $e \cdot |S|^{r-1}$ ) से करते हैं। यदि $\Pi(e) - 1 > e \cdot |S|^{r-1}$ , तो एक विरोधाभास उत्पन्न होता है, जो यह सिद्ध करता है कि ऐसा कोई परफेक्ट कोड मौजूद नहीं हो सकता।

प्रमुख योगदान और परिणाम
यह शोध पत्र एक मास्टर थ्योरम (थ्योरम 2) स्थापित करता है, जो कहता है कि यदि इंडेक्स सेट और चरों की संख्या के सापेक्ष डिस्पर्सन फंक्शन पर्याप्त तेजी से बढ़ता है, तो किसी $r$ -पॉलीनोमियल WMAS में कोई $e$ -परफेक्ट कोड मौजूद नहीं होता है। इस सामान्य परिणाम को चार विशिष्ट कोडिंग परिदृश्यों पर लागू किया गया है:

ली मीट्रिक (Lee Metric):
- निश्चित वर्णमाला ( $q$ ): बड़े कोड लंबाई $n$ और $n$ के आनुपातिक कवरिंग रेडियस $e$ के लिए, लेखक गैर-अस्तित्व को सिद्ध करते हैं।
- निश्चित $e$ : निश्चित वर्णमाला आकार $q$ और पर्याप्त बड़े $n$ के लिए, यदि $e > (s+1) \cdot (s!)^2 / (s-1)$ (जहाँ $s = \lfloor q/2 \rfloor$ ), तो कोई परफेक्ट कोड मौजूद नहीं है। यह 50 साल पुराने एक अनुमान को असमयिक समर्थन प्रदान करता है कि $e > 1$ और $n > 2$ के लिए परफेक्ट $e$ -कोड मौजूद नहीं होते हैं।
सम-रैंक मीट्रिक (Sum-Rank Metric): नेटवर्क कोडिंग में प्रयुक्त, यह पेपर $t \to \infty$ होने पर गैर-अस्तित्व के लिए एक स्थिति व्युत्पन्न करता है। यदि ब्लॉकों के अनुपात $e/t \to a$ और आयाम $d$ इस प्रकार है कि $d < (1+a)^{1+a}/a^a - 1$ (अनुमानित रूप से $d < e^a$ ), तो परफेक्ट कोड मौजूद नहीं होते हैं।
मिश्रित वर्णमाला कोड (Mixed Alphabet Codes): हैमिंग स्कीम्स के डायरेक्ट प्रोडक्ट के लिए, यह पेपर सिद्ध करता है कि यदि कवरिंग रेडियस $e$ , $an $के रूप में स्केल करता है जहाँ$ a > 1/k $($ k$ विशिष्ट वर्णमाला समूहों की संख्या है), तो कोई परफेक्ट कोड मौजूद नहीं है।
एनआरटी (NRT) मीट्रिक (ऑर्डर्ड हैमिंग स्पेस): ली मीट्रिक के मामले के समान, ब्लॉक लंबाई $r$ पर निर्भर विशिष्ट थ्रेशोल्ड (threshold) से अधिक होने पर बड़े $n$ के लिए गैर-अस्तित्व सिद्ध किया गया है।

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

सीमाएँ और प्रति-उदाहरण (Counterexamples)
शोध पत्र स्पष्ट रूप से नोट करता है कि यह विधि सार्वभौमिक नहीं है। यह उन स्कीम्स के लिए विफल हो जाती है जहाँ डिस्पर्सन फंक्शन $\Pi(e)$ बहुत धीरे बढ़ता है या जहाँ चरों की संख्या बहुत अधिक होती है। विशेष रूप से:

होमोजेनियस मीट्रिक (Homogeneous Metric): स्थिति $\Pi(e) - 1 > e \cdot |S|^{r-1}$ बड़े $n$ के लिए नहीं बनी रहती, इसलिए थ्योरम यहाँ गैर-अस्तित्व सिद्ध नहीं कर सकता।
$q$ -ary जॉनसन स्कीम ( $q$ -ary Johnson Scheme): डिस्पर्सन फंक्शन की वृद्धि किसी भी स्वीकार्य मापदंडों के लिए असमानता को संतुष्ट करने के लिए अपर्याप्त है, जिसका अर्थ है कि थ्योरम इस स्कीम पर लागू नहीं होता है।

महत्व
इस शोध पत्र का प्राथमिक महत्व शास्त्रीय कोडिंग सिद्धांत (लॉयड थ्योरम) को कंप्यूटर विज्ञान से संयोजित करके (श्वार्ट्ज़-ज़िपेल) गैर-मीट्रिक सेटिंग्स में परफेक्ट कोड्स के अध्ययन को पुनर्जीवित करना है। पॉलीनोमियल वीकली मेट्रिक एसोसिएशन स्कीम्स की अवधारणा पेश करके, लेखक एक एकीकृत ढांचा तैयार करते हैं जो कोडिंग थ्योरी के चार प्रमुख मीट्रिक्स के लिए विषम (asymptotic) गैर-अस्तित्व परिणाम प्रदान करता है। यह कार्य मल्टीवेरिएट $P$ -पॉलीनोमियल स्कीम्स और $m$ -डिस्टेंस रेगुलर ग्राफ्स के हालिया विकास को शास्त्रीय कोडिंग समस्याओं से जोड़ता है, जो उन स्थानों पर परफेक्ट कोड्स की सीमाओं का विश्लेषण करने के लिए एक नया उपकरण प्रदान करता है जहाँ पारंपरिक मीट्रिक धारणाएँ विफल हो जाती हैं।