🔢 mathematics

Semidefinite and linear programming bounds for sum-rank-metric codes and non-existence results

यह शोध पत्र सेमिडेफिनेट और लीनियर प्रोग्रामिंग तकनीकों का लाभ उठाकर सम-रैंक-मेट्रिक कोड के आकार पर नए तीक्ष्ण ऊपरी सीमाएँ स्थापित करता है, जो मौजूदा विधियों पर उनकी श्रेष्ठता को प्रदर्शित करता है और कुछ इष्टतम और पूर्ण कोडों के अस्तित्वहीन होने को सिद्ध करने के लिए उनका उपयोग करता है।

मूल लेखक: Aida Abiad, Antonina P. Khramova, Sven C. Polak, Ferdinando Zullo

प्रकाशित 2026-05-01

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

CC BY 4.0

मूल लेखक: Aida Abiad, Antonina P. Khramova, Sven C. Polak, Ferdinando Zullo

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

कल्पना कीजिए कि आप एक सूटकेस पैक करने की कोशिश कर रहे हैं, लेकिन इसके अंदर क्या समा सकता है, इसके नियम बहुत अजीब हैं। आप केवल यह नहीं गिन रहे हैं कि आपके पास कितनी वस्तुएं हैं; आप यह माप रहे हैं कि वे एक-दूसरे से कितने "अलग" हैं, एक जटिल और बहु-स्तरीय तरीके से। यह सम-रैंक-मैट्रिक कोड्स (sum-rank-metric codes) की दुनिया है, जो डेटा को व्यवस्थित करने के लिए उपयोग किया जाने वाला एक गणितीय ढांचा है, जैसे कि अस्थिर नेटवर्क पर संदेश भेजने या कई कंप्यूटरों में फाइलें स्टोर करने के लिए।

इस शोध पत्र का मुख्य लक्ष्य एक सरल प्रश्न का उत्तर देना है: आप इस सूटकेस में वस्तुओं (कोडवर्ड्स) की कुल अधिकतम संख्या कितनी रख सकते हैं इससे पहले कि वे आपस में टकराने लगें? यदि वे बहुत करीब आ जाते हैं, तो डेटा खराब हो सकता है।

यहाँ रोजमर्रा के उपमाओं (analogies) का उपयोग करके शोध पत्र के निष्कर्षों का विवरण दिया गया है:

1. समस्या: एक हाइब्रिड सूटकेस

"सम-रैंक मैट्रिक" को एक ऐसे हाइब्रिड सूटकेस के रूप में सोचें जिसमें दो प्रकार के खांचे (compartments) हैं:

हैमिंग खांचे (The Hamming compartments): यह मानक सूटकेस की तरह है जहाँ आप गिनते हैं कि कितने मोजे गायब हैं या बदल दिए गए हैं।
रैंक खांचे (The Rank compartments): यह उन सूटकेस की तरह है जहाँ आपको कपड़ों के पैटर्न (जैसे, क्या पूरी शर्ट में सिलवटें हैं, या सिर्फ आस्तीन में?) की परवाह होती है।

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

2. पुराने उपकरण: एक रूलर (Scale) से मापना

इस शोध पत्र से पहले, गणितज्ञों ने अधिकतम आउटफिट्स का अनुमान लगाने के लिए "रूलर" (गणितीय सीमाएं/bounds) का उपयोग किया था।

लीनियर प्रोग्रामिंग (LP) बाउंड: कल्पना कीजिए कि आप वस्तुओं के बीच औसत स्थान को देखकर सूटकेस की क्षमता का अनुमान लगाने की कोशिश कर रहे हैं। यह एक अच्छा अनुमान है, लेकिन यह मान लेता है कि वस्तुएं एक बहुत ही सरल, अनुमानित तरीके से व्यवस्थित हैं।
रेशियो-टाइप बाउंड (Ratio-type Bound): यह एक अन्य रूलर है जो आपकी वस्तुओं के "पड़ोसियों" को देखता है। यह पूछता है, "यदि मैं एक आउटफिट चुनता हूँ, तो कितने अन्य आउटफिट उसके ठीक बगल में हैं?"

यह शोध पत्र दिखाता है कि कुछ विशिष्ट प्रकार के सूटकेसों के लिए (विशेष रूप से जब "रैंक" वाला हिस्सा ही एकमात्र महत्वपूर्ण चीज़ हो, या जब यह केवल एक मानक "हैमिंग" सूटकेस हो), ये दोनों रूलर वास्तव में एक ही उत्तर देते हैं। वे समकक्ष (equivalent) हैं।

3. नया उपकरण: 3D स्कैनर (SDP)

शोध पत्र की सबसे बड़ी नवीनता एक नया उपकरण पेश करना है जिसे सेमीडेफिनेट प्रोग्रामिंग (SDP) कहा जाता है।

उपमा: यदि पुराने उपकरणों (LP) ने वस्तुओं के जोड़ों (Item A और Item B) को देखा, तो नया SDP टूल एक साथ त्रिकों (triplets) (Item A, Item B, और Item C) को देखता है।
यह क्यों मायने रखता है: कल्पना कीजिए कि आप एक छोटी कार में तीन लोगों को फिट करने की कोशिश कर रहे हैं। यदि आप केवल यह देखते हैं कि व्यक्ति A और व्यक्ति B को कितनी जगह चाहिए, तो आपको लग सकता है कि वे फिट हो जाएंगे। लेकिन यदि आप तीनों को एक साथ देखते हैं, तो आपको एहसास होता है कि वे सभी आराम से नहीं बैठ सकते। SDP टूल उन "ग्रुप डायनेमिक्स" को पकड़ लेता है जिन्हें पुराने उपकरण मिस कर देते हैं।
परिणाम: लेखकों ने इस नए 3D स्कैनर को चलाने के लिए एक कंप्यूटर प्रोग्राम बनाया। उन्होंने पाया कि कई मामलों में, यह नया टूल कहता है, "वास्तव में, आप पुराने रूलर्स द्वारा अनुमानित संख्या से कम आउटफिट्स रख सकते हैं।" इसका मतलब है कि पुराने रूलर्स बहुत अधिक आशावादी थे। नया टूल अधिक सटीक और कड़ा (tighter) सीमा प्रदान करता है।

4. "असंभव" सूटकेस (Non-Existence Results)

अधिकतम सीमा जानने का अंतिम लक्ष्य यह सिद्ध करना है कि कुछ "परफेक्ट" सूटकेस अस्तित्व में नहीं हैं।

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

लेखकों ने अपने नए, अधिक सटीक रूलर्स (SDP और परिष्कृत LP बाउंड्स) का उपयोग करके विशिष्ट सूटकेस आकारों को देखा। उन्होंने पाया कि कई विशिष्ट आकारों के लिए, गणित यह सिद्ध करता है कि एक "परफेक्ट" या "मैक्सिमम डिस्टेंस" सूटकेस बनाना असंभव है।

यह एक विशिष्ट संख्या में ईंटों के साथ एक घर बनाने की कोशिश करने जैसा है जिन्हें एक पूर्ण वर्ग बनाना चाहिए। आप सोच सकते हैं कि यह संभव है, लेकिन यदि आप ईंटों को सटीक रूप से मापते हैं, तो आपको एहसास होता है कि गणित मेल नहीं खाता—घर को बनाया ही नहीं जा सकता। शोध पत्र कई विशिष्ट परिदृश्यों को सूचीबद्ध करता है जहाँ ऐसे "परफेक्ट" कोड गणितीय रूप से असंभव हैं।

सारांश

सेटिंग: डेटा त्रुटियों को मापने का एक जटिल तरीका (सम-रैंक मैट्रिक)।
लक्ष्य: आप सुरक्षित रूप से कितने डेटा आइटम स्टोर कर सकते हैं, इसकी अधिकतम संख्या ज्ञात करना।
नवाचार: एक नया गणितीय "3D स्कैनर" (SDP) जो केवल जोड़ों के बजाय वस्तुओं के समूहों (तीन वस्तुओं के समूह) को देखता है।
खोज: यह नया स्कैनर सिद्ध करता है कि पुराने अनुमान बहुत अधिक थे।
निष्कर्ष: क्योंकि सीमाएं हमारी सोच से अधिक सख्त हैं, इसलिए कई "परफेक्ट" डेटा स्टोरेज सिस्टम जिन्हें अस्तित्व में होने की उम्मीद थी, वास्तव में बनाना असंभव है।

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

यहाँ अबियाद, ख्रमोवा, पोलक और ज़ुलो के शोध पत्र "Semidefinite and linear programming bounds for sum-rank-metric codes and non-existence results" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र कोडिंग थ्योरी की एक मौलिक समस्या को संबोधित करता है: एक निर्धारित न्यूनतम दूरी $d$ वाले कोड के अधिकतम आकार, जिसे $A(q, n, m, d)$ द्वारा दर्शाया जाता है, का निर्धारण करना, जो सम-रैंक मीट्रिक (sum-rank metric) के अंतर्गत आता है।

संदर्भ: सम-रैंक मीट्रक, हैमिंग मीट्रिक (हैमिंग मीट्रिक - symbol-wise errors) और रैंक मीट्रिक (रैंक-प्रकार के errors) दोनों का सामान्यीकरण (generalization) है। यह मल्टीशॉट नेटवर्क कोडिंग, डिस्ट्रीब्यूटेड स्टोरेज और स्पेस-टाइम कोडिंग जैसे आधुनिक अनुप्रयोगों के लिए अत्यंत महत्वपूर्ण है।
चुनौती: जबकि हैमिंग और रैंक मीट्रिक के लिए बाउंड्स (bounds) मौजूद हैं, सम-रैंक मीट्रिक की हाइब्रिड प्रकृति अद्वितीय कॉम्बिनेटोरियल (combinatorial) और बीजगणितीय घटनाओं को जन्म देती है। मौजूदा बाउंड्स (जैसे कि सिनिंगलटन, हैमिंग, प्लॉटकिन और शास्त्रीय डेलसार्ट LP) अक्सर सटीक ऊपरी बाउंड प्रदान करने में विफल रहते हैं या विशिष्ट पैरामीटर व्यवस्थाओं में इष्टतम कोडों (जैसे कि मैक्सिमम सम-रैंक डिस्टेंस (MSRD) या परफेक्ट कोड) के अस्तित्व को खारिज करने में विफल रहते हैं।
लक्ष्य: स्पेक्ट्रल ग्राफ थ्योरी और ऑप्टिमाइज़ेशन तकनीकों (लीनियर प्रोग्रामिंग और सेमीडेफिनेट प्रोग्रामिंग) का उपयोग करके तीक्ष्ण (sharper) ऊपरी बाउंड प्राप्त करना और इन बाउंड्स का उपयोग चरम (extremal) कोडों के अस्तित्व संबंधी गैर-अस्तित्व परिणामों (non-existence results) को सिद्ध करने के लिए करना।

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

लेखक बीजगणितीय ग्राफ थ्योरी (algebraic graph theory), कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन और कम्प्यूटेशनल प्रयोगों को संयोजित करने वाला एक बहुआयामी दृष्टिकोण अपनाते हैं:

ग्राफ थ्योरेटिकल फ्रेमवर्क: वे सम-रैंक मीट्रिक स्पेस $F_q^{n \times m}$ को एक ग्राफ $\Gamma$ के साथ जोड़ते हैं जहाँ वर्टिस (vertices) कोडवर्ड्स हैं और एडजेस (edges) दूरी 1 का प्रतिनिधित्व करते हैं। अधिकतम कोड आकार खोजने की समस्या इस ग्राफ के इंडिपेंडेंस नंबर (independence number) को बाउंड करने के समतुल्य है।
स्पेक्ट्रल मेथड्स (Spectral Methods): वे सम-रैंक-मीट्रिक ग्राफ के एडजसेंसी मैट्रिक्स (adjacency matrix) के आइगेनवैल्यूज़ (eigenvalues) का उपयोग करके बाउंड्स प्राप्त करते हैं।
- रेशियो-टाइप बाउंड (Ratio-type Bound): ग्राफ के आइगेनवैल्यूज़ पर आधारित एक स्पेक्ट्रल बाउंड।
- लोवाज़ थीटा नंबर (Lovász Theta Number): एक बीजगणितीय-ग्राफ-थ्योरेटिकल बाउंड।
लीनियर प्रोग्रामिंग (LP):
- डेलसार्ट LP (Delsarte LP): सम-रैंक मीट्रिक के एसोसिएशन स्कीम पर आधारित, जो दूरियों के वितरण को बाधित करने के लिए दूसरे आइगेनमैट्रिक्स (eigenmatrix) का उपयोग करता है।
- रेशियो-टाइप LP (Ratio-type LP): माइनर पॉलिनॉमियल्स (minor polynomials) का उपयोग करके रेशियो-टाइप बाउंड से प्राप्त एक LP फॉर्मूलेशन।
सेमीडेफिनेट प्रोग्रामिंग (SDP):
- श्राइवर-टाइप SDP (Schrijver-type SDP): लेखक डेलसार्ट फ्रेमवर्क का विस्तार करने वाला एक नया SDP बाउंड पेश करते हैं। जबकि डेलसार्ट का LP युग्म-दूरी (pairwise distances) पर विचार करता है, यह SDP कोडवर्ड्स के ट्रिपल्स (triples) (विशेष रूप से शून्य वेक्टर वाले ट्रिपल्स) पर आधारित बाधाओं को शामिल करता है, जो इन ट्रिपल्स को एनकोड करने वाले मैट्रिक्स की पॉजिटिव सेमीडेफिनेटनेस (positive semidefiniteness) का लाभ उठाता है।
कम्प्यूटेशनल वेरिफिकेशन: लेखक विभिन्न पैरामीटर्स के लिए इन बाउंड्स की गणना करने और ज्ञात सैद्धांतिक बाउंड्स के विरुद्ध तुलना करने के लिए जॉर्डन सिमेट्री रिडक्शन पैकेज के साथ जूलिया (Julia) प्रोग्रामिंग भाषा का उपयोग करते हैं।

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

A. एक नया सेमीडेफिनेट प्रोग्रामिंग (SDP) बाउंड

यह शोध पत्र एक श्राइवर-टाइप SDP बाउंड पेश करता है।

तंत्र (Mechanism): यह ट्रिपल्स पर बाधाएं लगाकर युग्म-डेलसार्ट LP को मजबूत करता है।
प्रदर्शन: कम्प्यूटेशनल प्रयोगों से पता चलता है कि यह SDP बाउंड कई पैरामीटर व्यवस्थाओं में मौजूदा सर्वोत्तम बाउंड्स (डेलसार्ट LP, रेशियो-टाइप और शास्त्रीय कोडिंग बाउंड्स सहित) की तुलना में स्पष्ट रूप से बेहतर है।
पदानुक्रम (Hierarchy): यह शोध पत्र पदानुक्रम स्थापित करता है: $A(q, n, m, d) \leq \text{SDP} \leq \text{Delsarte LP}$ ।

B. चरम व्यवस्थाओं में LP बाउंड्स की समानता

लेखक डेलसार्ट LP बाउंड और रेशियो-टाइप LP बाउंड के बीच एक कठोर तुलना करते हैं:

रैंक-मीट्रिक केस ( $t=1$ ): वे सिद्ध करते हैं कि बिलिनियर फॉर्म्स ग्राफ (शुद्ध रैंक मीट्रिक) के लिए, डेलसार्ट LP का ऑप्टिमम, रेशियो-टाइप LP के ऑप्टिमम के बिल्कुल बराबर होता है। दोनों ही सिनिंगलटन बाउंड $q^{m(n-d+1)}$ के बराबर हैं।
हैमिंग केस ( $n_i=m_i=1$ ): वे सिद्ध करते हैं कि हैमिंग ग्राफ के लिए, दोनों बाउंड्स विशिष्ट स्थितियों (जैसे, जब $q \geq \max\{d, t-d+2\}$ ) के तहत समान होते हैं। वे विशिष्ट काउंटर-उदाहरण भी प्रदान करते हैं (जैसे, बाइनरी हैमिंग कोड्स) जहाँ बाउंड्स समान हैं लेकिन सिनिंगलटन बाउंड से कम हैं, जो यह दर्शाता है कि वे उन विशिष्ट मामलों में टाइट (tight) हैं।

C. इष्टतम कोडों के लिए गैर-अस्तित्व परिणाम (Non-Existence Results)

नवनिर्मित और परिष्कृत बाउंड्स का उपयोग करते हुए, यह शोध पत्र कुछ इष्टतम कोडों के गैर-अस्तित्व को सिद्ध करता है:

MSRD कोड्स: सिनिंगलटन बाउंड को प्राप्त करने वाले कोड। लेखक दिखाते हैं कि विशिष्ट पैरामीटर्स के लिए (जैसे, $m=n=(2, \dots, 2)$ के साथ $t \geq q-1$ और $d=3$ ), रेशियो-टाइप बाउंड सिनिंगलटन बाउंड से कम है, जिससे सिद्ध होता है कि इन व्यवस्थाओं में MSRD कोड मौजूद नहीं हैं।
परफेक्ट कोड्स (Perfect Codes): वे कोड जो स्फीयर-पैकिंग (Sphere-Packing) बाउंड को समानता के साथ प्राप्त करते हैं।
- वे उन स्थितियों के लिए स्पष्ट स्थितियाँ निकालते हैं जहाँ परफेक्ट कोड्स मौजूद नहीं हो सकते हैं।
- वे एडिटिव परफेक्ट कोड्स को खारिज करने के लिए कॉंग्रुएंस (congruence) तर्क (mod $p$ ) का उपयोग करते हैं।
- वे दिखाते हैं कि $d=3$ के लिए, रेशियो-टाइप बाउंड अक्सर स्फीयर-पैकिंग बाउंड से बेहतर प्रदर्शन करता है, जिससे उन पैरामीटर्स के लिए परफेक्ट कोड्स के गैर-अस्तित्व को सिद्ध किया जाता है जहाँ $t \not\equiv 1 \pmod q$ है।

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

तीक्ष्ण ऊपरी बाउंड (Tighter Upper Bounds): नया SDP बाउंड सम-रैंक कोड्स के लिए कई परीक्षण किए गए परिदृश्यों में सबसे सटीक ज्ञात ऊपरी बाउंड प्रदान करता है, जो डेलसार्ट LP से बेहतर है।
सैद्धांतिक एकीकरण (Theoretical Unification): रैंक-मीट्रिक मामले में डेलसार्ट और रेशियो-टाइप बाउंड्स की समानता का प्रमाण दो पहले से अलग दृष्टिकोणों को एकीकृत करता है, यह दिखाते हुए कि वे एक ही संरचनात्मक सीमा प्रदान करते हैं।
गैर-अस्तित्व प्रमेय (Non-Existence Theorems):
- Theorem 5.2/5.3: जब $t \geq q-1$ हो, तो $m=n=(2, \dots, 2)$ के लिए $d=3$ वाले MSRD कोड्स मौजूद नहीं होते हैं।
- Theorem 5.7/5.9: यदि $t \not\equiv 1 \pmod q$ हो, तो $m=(m, 1, \dots, 1)$ वाले स्थानों में $d=3$ वाले परफेक्ट कोड्स मौजूद नहीं होते हैं।
- Theorem 5.10/5.11: यदि $t(q+1) \not\equiv 1 \pmod{q^2}$ हो, तो $m=n=(2, \dots, 2)$ वाले स्थानों में $d=3$ वाले परफेक्ट कोड्स मौजूद नहीं होते हैं।

5. महत्व (Significance)

पद्धतिगत प्रगति (Methodological Advancement): यह सम-रैंक मीट्रिक के लिए प्रथम श्राइवर-टाइप SDP बाउंड का अनुप्रयोग है। यह प्रदर्शित करता है कि सम-रैंक मीट्रिक की "हाइब्रिड" प्रकृति को प्रभावी ढंग से पकड़ने के लिए शास्त्रीय LP से परे ऑप्टिमाइज़ेशन तकनीकों की आवश्यकता है।
खुले प्रश्नों का समाधान: यह शोध पत्र सम-रैंक सेटिंग में विभिन्न स्पेक्ट्रल और LP बाउंड्स के बीच संबंधों के बारे में प्रश्नों को हल करता है, यह स्पष्ट करता है कि वे कब समान होते हैं और कब भिन्न होते हैं।
व्यावहारिक प्रभाव: विशिष्ट पैरामीटर व्यवस्थाओं में परफेक्ट और MSRD कोड्स के गैर-अस्तित्व को सिद्ध करके, यह शोध पत्र शोधकर्ताओं को उन क्षेत्रों में इष्टतम निर्माणों की व्यर्थ खोजों से दूर रहने का मार्गदर्शन करता है और सुझाव देता है कि ज्ञात बाउंड्स ही वास्तविक सीमाएँ हैं।
भविष्य की दिशाएँ: यह कार्य बड़े पैरामीटर्स को संभालने के लिए SDP में सिमेट्री रिडक्शन (symmetry reduction) की क्षमता को उजागर करता है और यह सुझाव देता है कि सामान्य सम-रैंक सेटिंग में विभिन्न बाउंड्स के बीच का अंतर आगे के सैद्धांतिक अन्वेषण की मांग करता है।