$2$-quasi-perfect Lee codes and abelian Ramanujan graphs: a new construction and relationship

यहाँ शोधपत्र "2-Quasi-Perfect Lee Codes and Abelian Ramanujan Graphs: A New Construction and Relationship" (शोहई साताके द्वारा लिखित) का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोधपत्र परिमित क्षेत्रों (finite fields) पर 2-quasi-perfect Lee codes के निर्माण को संबोधित करता है।

• संदर्भ: एक ली कोड (Lee code) एक त्रुटि-सुधार कोड (error-correcting code) है जो ली दूरी (Lee distance) का उपयोग करता है। एक कोड $t$-perfect तब होता है जब वह $t$ त्रुटियों को ठीक करता है और संपूर्ण स्थान को त्रिज्या $t$ के साथ कवर करता है। एक कोड $t$-quasi-perfect तब होता है जब वह $t$ त्रुटियों को ठीक करता है लेकिन इसके लिए $t+1$ की कवरेज त्रिज्या (covering radius) की आवश्यकता होती है।
• चुनौती: परफेक्ट ली कोडों का निर्माण एक शास्त्रीय समस्या है (जो गोलम्ब-वेल्च अनुमान/Golomb-Welch conjecture द्वारा सीमित है), लेकिन विशेष रूप से अनिश्चित लंबाई के लिए quasi-perfect कोडों के स्पष्ट परिवारों का निर्माण करना एक महत्वपूर्ण खुला प्रश्न बना हुआ है।
• अंतराल (Gap): मौजूदा निर्माण (जैसे कैमारो-मार्टिनेज़ और मेसनगर-टैंग-की द्वारा) अक्सर विशिष्ट बहुपदों (polynomials) से प्राप्त पृथक परिवारों के रूप में दिखाई देते हैं। एक एकीकृत सैद्धांतिक ढांचे (unified theoretical framework) का अभाव है जो यह समझा सके कि क्यों कुछ बीजगणितीय संरचनाएं इन इष्टतम कोडों को उत्पन्न करती हैं और वे Abelian Ramanian graphs (इष्टतम स्पेक्ट्रल गैप वाले ग्राफ़) से कैसे संबंधित हैं।

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

लेखक कोडिंग थ्योरी, बीजगणितीय ज्यामिति (algebraic geometry), और स्पेक्ट्रल ग्राफ़ थ्योरी (spectral graph theory) के संश्लेषण का उपयोग करते हैं।

A. जेनेरिक निर्माण ढांचा (Generic Construction Framework)

यह शोधपत्र मेसनगर, टैंग और की द्वारा दिए गए जेनेरिक निर्माण का उपयोग करता है, जो एक वेक्टर स्पेस $\Gamma$ और एक जनरेटिंग सेट $H$ के आधार पर एक रैखिक कोड $C(\Gamma, H)$ को परिभाषित करता है।

• 2-Quasi-Perfectness के लिए शर्त: एक कोड 2-quasi-perfect है यदि और केवल यदि:
  1. योग समुच्चयों (sumsets) के संघ $\bigcup_{i=0}^2 H^{(i)}$ का आकार $2n^2 + 2n + 1$ के बराबर है (जहाँ $n$ कोड की लंबाई है)।
  2. संघ $\bigcup_{i=0}^3 H^{(i)}$ संपूर्ण स्थान $\Gamma$ को स्पैन (span) करता है।
  3. $\Gamma$ के आकार पर विशिष्ट सीमाएँ (bounds) पूरी होती हैं।
• ग्राफ संबंध: ये शर्तें दर्शाती हैं कि केली ग्राफ (Cayley graph) $Cay(\Gamma, H)$ का व्यास (diameter) 3 है। लेखक का मानना है कि $H$ का चयन इस प्रकार करना कि $Cay(\Gamma, H)$ एक Abelian Ramanujan graph (जो स्पेक्ट्रल गैप को न्यूनतम करता है) हो, एक आशाजनक रणनीति है, क्योंकि इन ग्राफ़ों में स्वाभाविक रूप से छोटा व्यास होता है।

B. नया स्पष्ट निर्माण (Theorem 4)

लेखक $\mathbb{F}_{q^2}$ (जहाँ $q = p^k, p \ge 5$) से व्युत्पन्न एक नए अनंत परिवार के कोड पेश करते हैं।

• जनरेटिंग सेट: $H_q = \{(a, a^3) \mid a \in \mathbb{F}_q^*\}$। यह सेट क्यूबिक वक्र $y = x^3$ के बिंदुओं का प्रतिनिधित्व करता है।
• प्रमाण रणनीति: यह प्रमाण जेनेरिक ढांचे की शर्तों को बीजगणितीय ज्यामिति का उपयोग करके सत्यापित करने पर निर्भर करता है:
  • बिंदुओं की गणना: $a = x+y$ और $b = x^3+y^3$ के समाधानों को गिनने के लिए कॉम्बिनेटोरियल तर्कों का उपयोग करना (लेम्मा 11)।
  • अपरिवर्तनीयता (Irreducibility): यह सिद्ध करना कि बहुपद $F_{a,b}(x,y) = xy(x+y) - a(x+y)^2 + a^2(x+y) + \frac{b-a^3}{3}$ पूर्णतः अपरिमेय (absolutely irreducible) है, सिवाय इसके कि $b=a^3$ (लेम्मा 12)।
  • समाधानों का अस्तित्व: क्यूबिक वक्र $C_{a,b}$ पर हासे-वील बाउंड (Hasse-Weil bound) को लागू करना ताकि यह सुनिश्चित किया जा सके कि $q \ge 14$ के लिए, गैर-शून्य समाधान $x, y, z$ मौजूद हैं जैसे कि $a = x+y+z$ और $b = x^3+y^3+z^3$ (लेम्मा 13)। यह व्यास की स्थिति की पुष्टि करता है।

C. मौजूदा निर्माणों का एकीकरण (Unification of Existing Constructions)

लेखक मेसनगर, टैंग और की (MTQ) द्वारा निर्मित कोडों का विश्लेषण करते हैं और उन्हें ज्ञात रमनुजन ग्राफ़ से जोड़ते हैं:

• ली के ग्राफ़ (Li's Graphs): विशिष्ट मापदंडों के लिए MTQ कोड, ली के ग्राफ़ (norm-1 तत्वों द्वारा जनरेट किए गए केली ग्राफ़) के अनुरूप हैं।
• फाइनाइट यूक्लिडियन ग्राफ़ (Finite Euclidean Graphs): MTQ कोड को फाइनाइट यूक्लिडियन ग्राफ़ (द्विघाती रूपों $Q(x,y)=1$ द्वारा जनरेट किए गए केली ग्राफ़) के उदाहरण के रूप में दिखाया गया है।
• तुल्यता (Equivalence): लेखक सिद्ध करते हैं कि एक गैर-अपभ्रंश द्विघाती रूप (non-degenerate quadratic form) से प्राप्त कोई भी कोड, निर्देशांक क्रमपरिवर्तन (coordinate permutation) और चिह्न परिवर्तनों तक सीमित, दो मानक MTQ परिवारों में से एक के तुल्य है।

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

1. कोडों का नया अनंत परिवार:

   • एक नया स्पष्ट $p$-ary ली कोड परिवार निर्मित किया गया है जिसकी लंबाई $n = \frac{q-1}{2}$ और आयाम (dimension) $k = \frac{q-1}{2} - 2k$ है (जहाँ $q=p^k \ge 14$)।
   • ये कोड सेट $H_q = \{(a, a^3)\}$ से प्राप्त होते हैं, जो पिछले MTQ निर्माणों में उपयोग किए गए जनरेटिंग सेट्स से भिन्न है।
   • नवीनता: ये कोड उन अभाज्य संख्याओं $p \equiv 1, 7 \pmod{12}$ के लिए नए पैरामीटर प्रदान करते हैं जहाँ पिछले निर्माण सीमित या अस्तित्वहीन थे।

2. सैद्धांतिक एकीकरण:

   • लेख ने ली कोड और Abelian Ramanujan graphs के बीच एक सेतु स्थापित किया है।
   • यह प्रदर्शित किया गया कि MTQ कोड अनिवार्य रूप से ली के ग्राफ़ और फाइनाइट यूक्लिडियन ग्राफ़ से प्राप्त हैं, जो दोनों रमनुजन होने के लिए जाने जाते हैं।
   • एक एकीकृत विवरण प्रदान किया गया है जो दिखाता है कि MTQ निर्माण सभी गैर-अपभ्रंश द्विघाती रूपों द्वारा जनरेट किए गए कोडों को कवर करता है।

3. संरचनात्मक अंतर्दृष्टि:

   • दिखाया गया है कि नए कोड (जो $y=x^3$ पर आधारित हैं) ज्ञात MTQ कोडों से संबद्ध केली ग्राफ़ के समरूप (isomorphic) नहीं हैं, भले ही वे कुछ मामलों में समान पैरामीटर साझा करते हों।
   • रेखांकित किया गया कि नया निर्माण फोरे (Forey) आदि [7] के हालिया कार्य से उपजा है जो 'लगभग रमनुजन ग्राफ़' (almost Ramanujan graphs) पर आधारित है।

4. परिणाम (Results)

• थ्योरम 4: सिद्ध करता है कि $p \ge 5$ और $q = p^k \ge 14$ के लिए, कोड $C(\mathbb{F}_q^2, H_q)$ एक 2-quasi-perfect ली कोड है जिसकी लंबाई $\frac{q-1}{2}$ और आयाम $\frac{q-1}{2} - 2k$ है।
• प्रपोजिशन 16 और 18: सिद्ध किया गया कि MTQ कोड, ली के ग्राफ़ और फाइनाइट यूक्लिडियन ग्राफ़ द्वारा जनरेट किए गए कोडों के साथ मेल खाते हैं, जो द्विघाती रूपों और रमनुजन ग्राफ़ के अंतर्गत इन कोडों के सिद्धांत को एकीकृत करते हैं।
• उदाहरण: नए कोडों की विशिष्ट बीजगणितीय संरचनाओं को दर्शाने के लिए छोटे अभाज्य संख्याओं ($p=17, 19, 23, 5$) के लिए स्पष्ट पैरिटी-चेक मैट्रसेस (parity-check matrices) प्रदान किए गए हैं।

5. महत्व (Significance)

• विषयों का मिलन (Bridging Disciplines): यह शोधपत्र सफलतापूर्वक कोडिंग थ्योरी को स्पेक्ट्रल ग्राफ़ थ्योरी के साथ एकीकृत करता है, यह सुझाव देता है कि quasi-perfect कोडों के "अच्छे" गुण (छोटा कवरेज रेडियस) रमनुजन ग्राफ़ के स्पेक्ट्रल गुणों (इष्टतम विस्तार) से आंतरिक रूप से जुड़े हुए हैं।
• एक खुले प्रश्न का समाधान: यह अनिश्चित लंबाई के quasi-perfect कोडों के निर्माण की कठिन समस्या में योगदान देता है, एक नया, सरल और स्पष्ट निर्माण प्रदान करता है।
• स्पेक्ट्रल बनाम संरचनात्मक द्वैत (Spectral vs. Structural Dichotomy): निष्कर्ष संबंधी टिप्पणियाँ एक दिलचस्प सैद्धांतिक अंतर्दृष्टि को उजागर करती हैं: जबकि रमनुजन ग्राफ़ स्पेक्ट्रल रूप से यादृच्छिक ग्राफ़ (pseudo-random) के समान होते हैं, 2-quasi-perfectness के लिए आवश्यक सख्त संरचनात्मक स्थितियाँ (नियत स्थानीय संरचना) ऐसे ग्राफ़ में भी दुर्लभ हैं। यह सुझाव देता है कि ऐसे कोड खोजने के लिए केवल स्पेक्ट्रल इष्टतमता ही पर्याप्त नहीं है; इसके लिए विशिष्ट बीजगणितीय संरेखण (algebraic alignments) की आवश्यकता होती है।
• भविष्य की दिशाएँ: यह कार्य अन्य Abelian Ramanujan ग्राफ़ों की जांच करने के लिए द्वार खोलता है ताकि और अधिक इष्टतम कोड परिवारों की खोज की जा सके, जिससे ली दूरी मेट्रिक (Lee distance metric) और ग्राफ़ स्पेक्ट्रा के बीच संबंध मजबूत होता है।