Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric

तकनीकी सारांश: रैंडम गैबुडिलिन कोड रैंक मेट्रिक में लिस्ट डिकोडिंग क्षमता प्राप्त करते हैं

समस्या विवरण
गैबुडिलिन कोड (Gabidulin codes) रैंक-मेट्रिक के रीड-सॉलमन (Reed–Solomon) कोड के एनालॉग हैं और मैक्सिमम रैंक डिस्टेंस (MRD) कोड्स के एक प्राथमिक वर्ग का निर्माण करते हैं। जबकि रीड-सॉलमन कोड्स को जॉनसन बाउंड (Johnson bound) तक (और हाल ही में रैंडम कोड्स के लिए जनरलाइज्ड सिनग्ल्टन बाउंड तक) लिस्ट डिकोडेबल होने के रूप में अच्छी तरह से समझा गया है, गैबुडिलिन कोड्स की लिस्ट डिकोडेबिलिटी एक लंबे समय से खुला प्रश्न बना हुआ है, जिसके परिणाम मुख्य रूप से नकारात्मक रहे हैं। पूर्व कार्य (रविव और वाचर-ज़े द्वारा) ने प्रदर्शित किया कि विशिष्ट गैबुडिलिन कोड्स यूनिक डिकोडिंग रेडियस के परे कॉम्बिनेटोरियल रूप से लिस्ट डिकोडेबल भी नहीं हैं। इस शोध पत्र द्वारा संबोधित केंद्रीय प्रश्न यह है कि क्या गैबुडिलिन कोड्स को रैंक मेट्रिक में यूनिक डिकोडिंग रेडियस से परे लिस्ट डिकोड किया जा सकता है, विशेष रूप से क्या वे इष्टतम जनरलाइज्ड सिनग्ल्टन बाउंड प्राप्त कर सकते हैं।

कार्यप्रणाली और ढांचा
लेखक इस समस्या को रैंडम रीड-सॉलमन कोड्स की लिस्ट डिकोडेबिलिटी पर हालिया सफलताओं (ब्रेकेंसिक, गोपी और माकम - BGM) के समानांतर एक सैद्धांतिक ढांचा स्थापित करके हल करते हैं। कार्यप्रणाली तीन स्तंभों पर आधारित है:

1. हायर ऑर्डर MRD कोड्स: शोध पत्र एक सामान्य फील्ड एक्सटेंशन $F/F_q$ पर तीन अलग-अलग "हायर ऑर्डर MRD कोड्स" की अवधारणाओं को परिभाषित करता है:

   • GKP($\ell$): वे कोड जो क्रम $\ell$ तक के सभी जेनेरिक कर्नेल पैटर्न (Generic Kernel Patterns) को प्राप्त करते हैं। एक कर्नेल पैटर्न सबस्पेस का एक टुपल है जो उनके इंटरसेक्शन पर डाइमेंशन बाधा को संतुष्ट करता है।
   • MRD($\ell$): वे कोड जहाँ जेनरेटर मैट्रिक्स के तहत किसी भी $\ell$ सबस्पेस के इमेज का इंटरसेक्शन, संगत सबस्पेस के एक सिम्बोलिक (जेनेरिक) मैट्रिक्स के तहत इमेज के इंटरसेक्शन के समान डाइमेंशन रखता है।
   • LD-MRD($\le\ell$): वे कोड जो रैंक मेट्रिक में $(\rho, \ell)$-एवरेज-रेडियस लिस्ट डिकोडेबल हैं, जहाँ $\rho$ जनरलाइज्ड सिनग्ल्टन बाउंड रेडियस है।

2. तुल्यता प्रमेय (Equivalence Theorems): लेखक सिद्ध करते हैं कि ये तीनों अवधारणाएं समान हैं। विशेष रूप से, एक लीनियर कोड GKP($\ell$) है यदि और केवल यदि वह MRD($\ell$) है, और एक कोड MRD($\ell+1$) है यदि और केवल यदि उसका ड्यूल LD-MRD($\le\ell$) है। यह तुल्यता समस्या को सिद्ध करने को लिस्ट डिकोडेबिलिटी को सिद्ध करने में बदलने के लिए कम कर देती है कि रैंडम गैबुडिलिन कोड्स GKP प्रॉपर्टी को संतुष्ट करते हैं।

3. GM-MRD प्रमेय: मुख्य तकनीकी योगदान "जनरलाइज्ड MDS फॉर MRD" (GM-MRD) प्रमेय की सिद्धि है। यह प्रमेय बताता है कि सिम्बोलिक गैबुडिलिन कोड्स (जो एक फंक्शन फील्ड पर परिभाषित हैं) सभी जेनेरिक कर्रल पैटर्न प्राप्त करते हैं। इसका प्रमाण GM-MDS प्रमेय के लिए उपयोग की जाने वाली इंडक्टिव तकनीकों को अनुकूलित करता है, लेकिन इसे $q$-लीनियराइज्ड पॉलिनोमिअल्स (जो गैबुडिलिन कोड्स को परिभाषित करते हैं) के नॉन-कम्यूटेटिव स्वभाव के कारण महत्वपूर्ण नई चुनौतियों का सामना करना पड़ता है। लेखक इन कंपोजिशन से उत्पन्न संरचनात्मक जटिलता को प्रबंधित करने के लिए "s-एडमिसिबल टुपल्स" (s-admissible tuples) की अवधारणा पेश करते हैं।

मुख्य परिणाम
शोध पत्र निम्नलिखित मुख्य परिणाम स्थापित करता है:

• इष्टतम लिस्ट डिकोडेबिलिटी: उच्च संभाव्यता के साथ, पर्याप्त बड़े अल्फाबेट्स ($F_{q^m}$) पर रैंडम गैबुडिलिन कोड्स रैंक मेट्रिक में जनरलाइज्ड सिनग्ल्टन बाउंड प्राप्त करते हैं। विशेष रूप से, $R = k/n$ दर वाले कोड के लिए, कोड किसी भी लिस्ट साइज $L$ के लिए $(\frac{L}{L+1}(1-R), L)$-एवरेज-रेडियस लिस्ट डिकोडेबल है, बशर्ते कि फील्ड एक्सटेंशन डिग्री $m$ पर्याप्त रूप से बड़ा हो (विशेष रूप से $m = \Omega_\ell(n^2)$)।
• GM-MRD प्रमेय: लेखक सिद्ध करते हैं कि सिम्बोलिक गैबुडिलिन कोड्स सभी $\ell$ के लिए GKP($\ell$) हैं। इसका तात्पर्य है कि रैंडम गैबुडिलिन कोड्स, पर्याप्त बड़े फील्ड साइज के साथ, उच्च संभाव्यता के साथ GKP($\ell$) हैं (श्वार्ट्ज-ज़िपल लेम्मा के माध्यम से विशिष्ट डिटर्मिनेंट पॉलिनोमिअल्स के शून्य होने से बचने के लिए)।
• फील्ड साइज लोअर बाउंड: शोध पत्र एक मिलान लोअर बाउंड भी स्थापित करता है, जो दिखाता है कि गैबुडिलिन कोड्स के लिए $m = \Omega_\ell(n^2)$ होना औसत-रेडियस लिस्ट डिकोडेबिलिटी के लिए जनरलाइज्ड सिनग्ल्टन बाउंड प्राप्त करने हेतु आवश्यक है।
• सुधार नोट: लेखक एक त्रुटि नोट (erratum) शामिल करते हैं जिसमें बताया गया है कि मूल प्रमाण में एक विशिष्ट प्रमेय (थ्योरम 4.7) को एक अतिरिक्त धारणा ($q \ge m-1$) की आवश्यकता थी, जो लीनियर प्रोजेक्शन के तहत सबस्पेस इंटरसेक्शन के डाइमेंशन के संबंध में एक सूक्ष्म त्रुटि के कारण थी। यह धारणा मुख्य प्रमेयों तक प्रसारित होती है, जिससे मुख्य सकारात्मक परिणामों के लिए $q \ge n-k-1$ की आवश्यकता होती है, हालांकि जेनेरिक इंटरसेक्शन फॉर्मूला और तुल्यता परिणाम इस प्रतिबंध के बिना भी मान्य रहते हैं।

महत्व और दावे
यह शोध पत्र यह दावा करके एक लंबे समय से खुले प्रश्न को हल करता है कि रैंक मेट्रिक में इष्टतम कॉम्बिनेटोरियल लिस्ट डिकोडेबिलिटी वाले गैबुडिलिन कोड्स का अस्तित्व है। इस कार्य का महत्व निम्नलिखित संदर्भों में है:

• सैद्धांतिक एकीकरण: यह हायर-ऑर्डर MDS कोड्स के सिद्धांत को प्रतिबिंबित करते हुए, हायर-ऑर्डर MRD कोड्स के लिए एक एकीकृत सिद्धांत प्रदान करता है, और GM-MRD प्रमेय को सिद्ध करता है, जो पिछले ज्ञात GM-MDS प्रमेय से स्पष्ट रूप से अधिक मजबूत है (क्योंकि यह केवल जीरो पैटर्न के बजाय कर्रल पैटर्न को संबोधित करता है)।
• क्रिप्टोग्राफिक निहितार्थ: इसके परिणाम रैंक-मेट्रिक कोड-आधारित क्रिप्टोसिस्टम्स (जैसे LIGA) के सुरक्षा विश्लेषण को प्रभावित करते हैं। गैबुडिलिन कोड्स के लिए रैंडम सिनड्रोम डिकोडिंग (RSD) समस्या के लिस्ट सर्च वर्जन की हार्डनेस को पहले उच्च माना जाता था क्योंकि आउटपुट लिस्ट के एक्सपोनेंशियल होने की संभावना थी। यह कार्य दिखाता है कि रैंडम गैबुडिलिन कोड्स के लिए, लिस्ट साइज जनरलाइज्ड सिनग्ल्टन बाउंड द्वारा सीमित है, जिससे उन स्कीम्स के लिए सुरक्षा मापदंडों के पुनर्मूल्यांकन की आवश्यकता हो सकती है जो गैबुडिलिन कोड्स की लिस्ट डिकोडिंग की हार्डनेस पर निर्भर करती हैं।
• स्यूडो-रैंडमनेस (Pseudorandomness): यह कार्य रैंक-मेट्रिक कोड्स को स्यूडो-रैंडमनेस से जोड़ता है, यह सुझाव देता है कि गैबुडिलिन कोड्स डाइमेंशन एक्सपैंडर्स और एक्सट्रैक्टर्स जैसे कार्यों के लिए इष्टतम ऑब्जेक्ट के रूप में कार्य कर सकते हैं, उनके हैमिंग-मेट्रिक समकक्षों की तरह।

लेखक स्पष्ट निर्माण (explicit constructions) के संबंध में विनम्र रहते हैं, यह नोट करते हुए कि जबकि रैंडम कोड्स ये पैरामीटर्स प्राप्त करते हैं, समान पैरामीटर्स वाले गैबुडिलिन कोड्स के स्पष्ट निर्माण खोजना एक खुला प्रश्न बना हुआ है। वे यह भी रेखांकित करते हैं कि फील्ड साइज की आवश्यकता ($m = \Omega(n^2)$) लिस्ट साइज पर निर्भर एक स्थिरांक (constant) के आधार पर इष्टतम है।