🔢 mathematics

Binary LCD Codes and Their Graph Representations

यह शोध पत्र उन सरल ग्राफों और दूरी-नियमित (डिस्टेंस-रेगुलर) ग्राफों का एक पूर्ण लक्षण वर्णन प्रदान करता है जिनके आसन्नता आव्यूह (एडजसेंसी मैट्रिसेस) बाइनरी लीनियर कॉम्प्लीमेंट्री ड्यूल (एलसीडी) कोड उत्पन्न करते हैं, जो विशिष्ट ग्राफ परिवारों के लिए पिछले परिणामों को एकीकृत करता है और इन निष्कर्षों को कॉन्फ्रेंस ग्राफों से असमान कोडों को अलग करने और इडेम्पोटेंट (आइडम्पोटेंट) आसन्नता आव्यूहों वाले छोटे ग्राफों को वर्गीकृत करने में लागू करता है।

मूल लेखक: Keita Ishizuka

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

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

CC BY 4.0

मूल लेखक: Keita Ishizuka

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

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

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

इस शोध पत्र की खोजों का सरल शब्दों में विवरण यहाँ दिया गया है:

1. दो दुनियाएँ

कोड की दुनिया (LCD कोड्स): इन्हें विशेष "गुप्त संदेशों" के रूप में सोचें। इन संदेशों की एक प्रमुख विशेषता यह है कि वे एक बहुत ही विशिष्ट तरीके से "स्व-जांच" (self-checking) करने वाले होते हैं। यदि आप उस संदेश को खोजने का प्रयास करते हैं जो कोड के भीतर छिपा है और उसका अपना "परछाई" (गणितीय विपरीत) भी है, तो आपको कुछ नहीं मिलता। यह उन्हें बहुत सुरक्षित और क्रिप्टोग्राफी के लिए उपयोगी बनाता है।
ग्राफ की दुनिया: इसे बिंदुओं (vertices) और रेखाओं (edges) के सरल मानचित्रों के रूप में सोचें। इसमें कोई लूप (एक बिंदु जो खुद से जुड़ता हो) या एक ही दो बिंदुओं के बीच दोहरी रेखाएँ नहीं होती हैं।

2. बड़ी खोज: "इडम्पोटेंट" (Idempotent) सेतु

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

लेकिन केवल कोई भी नेटवर्क नहीं। नेटवर्क को एक अजीब नियम का पालन करना चाहिए जिसे इडम्पोटेंस (idempotence) कहा जाता है।

उपमा (Analogy): कल्पना कीजिए कि आपके पास एक नेटवर्क मैप है। यदि आप किसी भी बिंदु से उसके पड़ोसी तक एक "कदम" लेते हैं, और फिर वहां से एक और "कदम" लेते हैं, तो यह दो बार करने का परिणाम बाइनरी गणित की दुनिया में (जहाँ 1+1=0 होता है) एक ही बार करने के बराबर होता है।
अनुवाद:
- यदि आपके पास एक कोड है जो इस तरह से काम करता है, तो आप एक मानचित्र बना सकते हैं जो उसे पूरी तरह से दर्शाता है।
- यदि आपके पास एक मानचित्र है जहाँ बिंदु और रेखाएँ इस "डबल-स्टेप" नियम का पालन करती हैं, तो आप एक गुप्त कोड लिख सकते हैं जो उसे पूरी तरह से दर्शाता है।
- महत्वपूर्ण बात: यदि दो कोड एक-दूसरे के "शफल" (shuffled) संस्करण हैं, तो उनके मानचित्र केवल एक-दूसरे के "पुनः नामित" (renamed) संस्करण होते हैं (आइसोमोर्फिक)। इसका अर्थ है, "क्या ये दो कोड समान हैं?" इस पहेली को सुलझाना, "क्या ये दो मानचित्र समान हैं?" को सुलझाने के बिल्कुल समान है।

3. खेल के नियम (एक मानचित्र को कैसे काम करने योग्य बनाया जाता है?)

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

एक डिस्टेंस-रेगुलर ग्राफ को एक पूरी तरह से सममित (symmetrical) शहर के रूप में सोचें जहाँ हर मोहल्ला बिल्कुल एक जैसा दिखता है। शोध पत्र कहता है कि यह शहर एक वैध कोड तभी उत्पन्न करेगा जब शहर के लेआउट के बारे में तीन विशिष्ट संख्याएँ एक विशिष्ट तरीके से "इवन" (even) या "ऑड" (odd) हों:

डिग्री (Degree): शहर के प्रत्येक व्यक्ति के पास दोस्तों की संख्या सम (even) होनी चाहिए।
पड़ोसी (Neighbors): यदि दो लोग दोस्त हैं, तो उनके पास आपसी मित्रों की संख्या विषम (odd) होनी चाहिए।
अजनबी (Strangers): यदि दो लोग दोस्त नहीं हैं, तो उनके पास आपसी मित्रों की संख्या सम (even) होनी चाहिए।

यदि कोई शहर इन तीन नियमों का पालन करता है, तो वह एक पूर्ण कोड बनाता है। यदि वह एक भी नियम तोड़ता है, तो वह विफल हो जाता है।

4. प्रसिद्ध शहरों पर नियमों को लागू करना

लेखक ने यह देखने के लिए कि कौन से नेटवर्क परीक्षण पास करते हैं, इन नियमों का प्रसिद्ध प्रकार के नेटवर्क पर परीक्षण किया:

कम्प्लीट ग्राफ्स (सब एक-दूसरे को जानते हैं): ये काम करते हैं, लेकिन केवल तभी जब लोगों की कुल संख्या विषम (odd) हो। (जैसे, 3, 5, 7 लोग काम करते हैं; 4, 6, 8 नहीं करते)।
साइकिल ग्राफ्स (लोगों का एक घेरा): केवल एक त्रिकोण (3 लोग) काम करता है। एक वर्ग, पंचभुज या बड़ा घेरा नियमों में विफल रहता है।
हैमिंग ग्राफ्स (जैसे एक 3D क्यूब): ये केवल तभी काम करते हैं जब उन्हें बनाने के लिए उपयोग किए गए वर्णमाला (alphabet) का आकार विषम हो।
जॉनसन ग्राफ्स: ये केवल तभी काम करते हैं जब वस्तुओं की कुल संख्या विषम हो।

5. एक रहस्य को सुलझाना: "कॉन्फ्रेंस ग्राफ" पहेली

अन्य शोधकर्ताओं (हेमर्स एट अल.) के संबंध में एक प्रसिद्ध अवलोकन था जो "कॉन्फ्रेंस ग्राफ्स" (एक विशेष प्रकार का नेटवर्क) के बारे में था। उन्होंने देखा कि:

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

यह शोध पत्र इसे सिद्ध करता है। क्योंकि लेखक ने एक पूर्ण सेतु बनाया है जहाँ "अलग मानचित्र = अलग कोड," अब यह गणितीय रूप से गारंटीकृत है कि यदि आपके पास दो अलग-अलग कॉन्फ्रेंस ग्राफ्स (एक विशिष्ट आकार गुण के साथ) हैं, तो वे दो पूरी तरह से अलग गुप्त कोड बनाएंगे। यह समझाता है कि पिछले शोधकर्ताओं ने यह पैटर्न क्यों देखा।

6. "मास फॉर्मूला" जनगणना

अंत में, लेखक ने मानचित्रों को गिनने के लिए एक चतुर गिनती तकनीक (जिसे "मास फॉर्मूला" कहा जाता है) का उपयोग किया, जिसे मूल रूप से कोड के लिए डिज़ाइन किया गया था।

13 बिंदुओं तक के हर संभव मानचित्र को बनाने के बजाय (जिसमें बहुत समय लगेगा), उन्होंने पहले कोडों को गिना।
अपने सेतु के कारण, कोडों को गिनना स्वचालित रूप से मानचित्रों को गिनना बन गया।
परिणाम: उन्होंने 13 बिंदुओं तक के 1,208 अद्वितीय, वैध मानचित्रों को सफलतापूर्वक वर्गीकृत किया। उन्होंने पाया कि इनमें से कई प्रसिद्ध आकृतियाँ (जैसे पेटर्सन ग्राफ का चचेरा भाई) थीं और उन्होंने पुष्टि की कि कोई भी "ट्री" (tree) आकार (शाखाओं वाली संरचनाएं जैसे पारिवारिक वृक्ष) कभी भी काम नहीं कर सकता, क्योंकि उनमें "पत्तियाँ" (leaves) होती हैं जिनके पास केवल एक ही मित्र होता है (जो "सम मित्र" के नियम का उल्लंघन करता है)।

सारांश

यह शोध पत्र गणितज्ञों के लिए एक "रोसेटा स्टोन" है। यह सिद्ध करता है कि एक विशिष्ट प्रकार का सुरक्षित कोड और एक विशिष्ट प्रकार का नेटवर्क एक ही सिक्के के दो पहलू हैं। यह एक सरल चेकलिस्ट देता है कि कब एक नेटवर्क एक अच्छा कोड बनाता है, यह बताता है कि अलग-अलग नेटवर्क अलग-अलग कोड क्यों बनाते हैं, और हजारों अद्वितीय नेटवर्क को सूचीबद्ध करने के लिए कोड-गिनती की युक्तियों का उपयोग करता है।

तकनीकी सारांश: बाइनरी LCD कोड और उनके ग्राफ प्रतिनिधित्व

समस्या विवरण

यह शोध पत्र इस मौलिक समस्या का समाधान करता है कि कौन से सरल ग्राफ (बिना लूप या बहु-किनारों वाले ग्राफ) अपने आसन्न आव्यूह (adjacency matrices) के माध्यम से बाइनरी लीनियर कॉम्प्लीमेंट्री ड्यूल (LCD) कोड उत्पन्न करते हैं। जबकि पिछले शोधों ने ग्राफ स्पेक्ट्रा और कोड आयामों के बीच संबंध स्थापित किया था, और विशिष्ट ग्राफ परिवारों (जैसे स्ट्रॉन्गली रेगुलर ग्राफ) के लिए LCD कोड प्रदान करने हेतु पर्याप्त स्थितियाँ दी थीं, एक पूर्ण लक्षण वर्णन (characterization) का अभाव था। इसके अतिरिक्त, LCD कोड के लिए कोड तुल्यता (code equivalence) और ग्राफ आइसोमोर्फिज्म (graph isomorphism) के बीच संबंध, जो कि ग्राफ आइसोमोर्फिज्म (GI) तक सीमित है, एक रचनात्मक द्वैत (bijection) की कमी थी जो ग्राफों को कोडिंग-सैद्धांतिक उपकरणों के आधार पर व्यवस्थित रूप से वर्गीकृत करने में सुविधा प्रदान कर सके।

मुख्य चुनौती यह निर्धारित करना है कि किसी ग्राफ का आसन्न आव्यूह $A$ , $\mathbb{F}_2$ पर इडेम्पोटेंट (idempotent, यानी $A^2 = A$ ) होने के लिए आवश्यक और पर्याप्त स्थितियाँ क्या हैं, क्योंकि यह गुण $A$ के रो स्पैन (row span) के एक LCD कोड बनाने के समतुल्य है।

कार्यप्रणाली

लेखक एल्जेब्रिक कोडिंग थ्योरी और एल्जेब्रिक ग्राफ थ्योरी को संयोजित करने वाला एक दोहरी दृष्टिकोण अपनाता है:

ऑर्थोगोनल प्रोजेक्टर और इडेम्पोटेंस: शोध पत्र इस संरचनात्मक गुण का उपयोग करता है कि एक बाइनरी कोड $C$ तब LCD होता है जब उसका ऑर्थोगोनल प्रोजेक्टर $\Pi_C$ एक सममित आव्यूह (symmetric matrix) होता है जो $\Pi_C^2 = \Pi_C$ को संतुष्ट करता है। लेखक स्थापित करता है कि बाइनरी इवन (even) LCD कोड के लिए, यह प्रोजेक्टर ठीक उसी प्रकार होता है जैसे एक सरल ग्राफ का आसन्न आव्यूह।
संयोजन संबंधी लक्षण वर्णन (Combinatorial Characterization): $\mathbb{F}_2$ पर इडेम्पोटेंस स्थिति $A^2 = A$ का विश्लेषण करके, शोध पत्र ग्राफ संरचना पर संयोजन संबंधी बाधाओं को व्युत्पन्न करता है, विशेष रूप से शीर्ष डिग्री (vertex degrees) और आसन्न तथा गैर-आसन्न शीर्षों के बीच सामान्य पड़ोसियों (common neighbors) की संख्या के संबंध में।
डिस्टेंस-रेगुलर ग्राफ (DRG) विश्लेषण: शोध पत्र DRGs के दूरी आव्यूहों (distance matrices) के तीन-पद पुनरावृत्ति संबंध (three-term recurrence relation) को लागू करता है। यह इडेम्पोटेंस स्थिति को इंटरसेक्शन ऐरे मापदंडों $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$ पर स्पष्ट पैरिटी (parity) बाधाओं में कम करने की अनुमति देता है।
वर्गीकरण के लिए मास फॉर्मुला (Mass Formulas): इडेम्पोटेंट आसन्न आव्यूह वाले ग्राफों को वर्गीकृत करने के लिए, शोध पत्र बाइनरी LCD कोडों के लिए मौजूदा मास फॉर्मुला (Carlet et al. द्वारा विकसित) का लाभ उठाता है। असमान कोडों (inequivalent codes) और गैर-आइसोमोर्फिक ग्राफों के बीच एक द्वैत (bijection) स्थापित करके, लेखक व्यापक ग्राफ गणना (enumeration) से बचता है, बल्कि LCD कोडों के ज्ञात वर्गीकरण का उपयोग करके संबंधित ग्राफों के वर्गीकरण का अनुमान लगाता है।

मुख्य योगदान

1. DRGs का आवश्यक और पर्याप्त लक्षण वर्णन

शोध पत्र उन डिस्टेंस-रेगुलर ग्राफों का पूर्ण लक्षण वर्णन प्रदान करता है जो बाइनरी इवन LCD कोड उत्पन्न करते हैं। एक DRG के लिए जिसका इंटरसेक्शन ऐरे $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$ है, आसन्न आव्यूह एक LCD कोड उत्पन्न करता है यदि और केवल यदि:

$b_0 \equiv 0 \pmod 2$ (वैलेंसी सम है);
$a_1 \equiv 1 \pmod 2$ , जहाँ $a_1 = b_0 - b_1 - c_1$ ;
$c_2 \equiv 0 \pmod 2$ ।

यह परिणाम Key और Rodrigues द्वारा दिए गए स्ट्रॉन्गली रेगुलर ग्राफ्स (SRGs) के लिए पर्याप्त स्थितियों का सामान्यीकरण और सुदृढ़ीकरण करता है, जो सभी डिस्टेंस-रेगुलर ग्राफों के दायरे को बढ़ाता है।

2. तुल्यता-संरक्षण द्वैत (Equivalence-Preserving Bijection)

शोध पत्र निम्नलिखित के बीच एक द्वैत (bijection) स्थापित करता है:

लंबाई $n$ के बाइनरी इवन LCD कोड;
$n$ शीर्षों वाले सरल ग्राफ जिनका $\mathbb{F}_2$ पर इडेम्पोटेंट आसन्न आव्यूह है।

महत्वपूर्ण रूप से, यह द्वैत तुल्यता को संरक्षित करता है: दो कोड क्रमपरिवर्तन तुल्य (permutation equivalent) हैं यदि और केवल यदि उनके संगत ग्राफ आइसोमोर्फिक हैं। यह कोडिंग थ्योरी और ग्राफ थ्योरी के बीच समस्याओं के अनुवाद की अनुमति देता है।

3. संयोजन संबंधी स्थितियाँ

एक सरल ग्राफ एक बाइनरी इवन LCD कोड प्रदान करता है यदि और केवल यदि:

प्रत्येक शीर्ष की डिग्री सम है;
कोई भी दो आसन्न शीर्षों के बीच सामान्य पड़ोसियों की संख्या विषम है;
कोई भी दो गैर-आसन्न शीर्षों के बीच सामान्य पड़ोसियों की संख्या सम है।

4. छोटे ग्राफों का वर्गीकरण

द्वैत और मास फॉर्मुला का उपयोग करते हुए, शोध पत्र अधिकतम 13 शीर्षों वाले इडेम्पोटेंट आसन्न आव्यूह वाले सभी सरल ग्राफों को वर्गीकृत करता है। $n \le 13$ की लंबाई वाले 22,213 बाइनरी LCD कोडों में से, लेखक 1,208 गैर-आइसोमोर्फिक ग्राफों की पहचान करता है, जिसमें ज्ञात परिवार जैसे पूर्ण ग्राफ (complete graphs), पूर्ण मल्टीपार्टाइट ग्राफ (complete multipartite graphs), और विशिष्ट स्ट्रॉन्गली रेगुलर ग्राफ शामिल हैं।

परिणाम

विशिष्ट ग्राफ परिवारों का लक्षण वर्णन

सामान्य DRG प्रमेय कई प्रसिद्ध ग्राफ परिवारों के लिए सटीक मानदंड प्रदान करता है:

पूर्ण ग्राफ ( $K_n$ ): एक LCD कोड उत्पन्न करता है यदि और केवल यदि $n$ विषम है।
चक्र ग्राफ ( $C_n$ ): केवल $C_3$ (जो $K_3$ है) एक LCD कोड उत्पन्न करता है; $n \ge 4$ वाले चक्र LCD कोड उत्पन्न नहीं करते हैं।
हैमिंग ग्राफ ( $H(n, m)$ ): एक LCD कोड उत्पन्न करता है यदि और केवल यदि $m$ विषम है।
जॉनसन ग्राफ ( $J(n, k)$ ): एक LCD कोड उत्पन्न करता है यदि और केवल यदि $n$ विषम है।
ग्रासमैन ग्राफ ( $J_q(n, k)$ ): एक LCD कोड उत्पन्न करता है यदि और केवल यदि $n$ विषम है और $q$ विषम है। यदि $q$ सम है, तो वे कभी भी LCD कोड उत्पन्न नहीं करते हैं।

कॉन्फ्रेंस ग्राफ और हेमर्स का अवलोकन

शोध पत्र कॉन्फ्रेंस ग्राफ (पैरामीटर्स $(q, (q-1)/2, (q-5)/4, (q-1)/4)$ वाले SRGs) के संबंध में हेमर्स, पीटर्स और वैन रिक्केवोर्सल के एक कम्प्यूटेशनल अवलोकन को संबोधित करता है।

सैद्धांतिक प्रमाण: शोध पत्र सिद्ध करता है कि एक कॉन्फ्रेंस ग्राफ एक बाइनरी इवन LCD कोड उत्पन्न करता है यदि और केवल यदि $q \equiv 1 \pmod 8$ ।
तुल्यता: यह पुष्टि करता है कि $q \equiv 1 \pmod 8$ वाले गैर-आइसोमोर्फिक कॉन्फ्रेंस ग्राफ असमान कोड उत्पन्न करते हैं। यह उस अवलोकन के लिए एक सैद्धांतिक स्पष्टीकरण प्रदान करता है कि इस वर्ग के गैर-आइसोमोर्फिक ग्राफ विशिष्ट मामलों जैसे $srg(25, 12, 5, 6)$ के लिए पहले से सत्यापित केवल कम्प्यूटेशनल रूप से भिन्न कोड उत्पन्न करते हैं।

कम्प्यूटेशनल वर्गीकरण

$n \le 13$ के लिए, वर्गीकरण प्रकट करता है:

ज्ञात परिवारों के 44 ग्राफ (6 पूर्ण ग्राफ, 3-36 पूर्ण मल्टीपार्टाइट ग्राफ, 2 स्ट्रॉन्गली रेगुलर ग्राफ)।
इन विशिष्ट ग्राफों द्वारा उत्पन्न कोड को ग्रासल (Grassl) की तालिकाओं के अनुसार अनुकूलतम (optimal) के रूप में पुष्टि की गई है।

महत्व और दावे

शोध पत्र यह दावा करता है कि वह एक संरचनात्मक पत्राचार स्थापित करके LCD कोड थ्योरी और ग्राफ थ्योरी के बीच के अंतर को पाटता है जो आवश्यक और पर्याप्त दोनों है।

एकीकरण: लक्षण वर्णन पूर्ण, हैमिंग, जॉनसन और ग्रासमैन ग्राफों के उपचार को डिस्टेंस-रेगुलैरिटी के एकल ढांचे के तहत एकीकृत करता है।
सैद्धांतिक स्पष्टीकरण: यह गैर-आइसोमोर्फिक कॉन्फ्रेंस ग्राफों के असमान कोड उत्पन्न करने के अवलोकन के लिए पहला सैद्धांतिक औचित्य प्रदान करता है, जो केवल अनुभवजन्य सत्यापन से आगे बढ़ता है।
पद्धतिगत नवाचार: यह कार्य प्रदर्शित करता है कि मास फॉर्मुला, जो पारंपरिक रूप से कोडों के वर्गीकरण के लिए उपयोग किए जाते हैं, का प्रभावी ढंग से विशिष्ट एल्जेब्रिक गुणों (इडेम्पोटेंट आसन्न आव्यूह) वाले ग्राफों को वर्गीकृत करने के लिए पुन: उपयोग किया जा सकता है, जो ग्राफ गणना के लिए एक नया उपकरण प्रदान करता है।
खुली समस्याएँ: शोध पत्र विनम्रतापूर्वक नोट करता है कि जबकि पैले ग्राफ (Paley graph) $srg(41, 20, 9, 10) $के लिए सबसे बड़ा न्यूनतम दूरी प्राप्त करता है, यह एक खुला प्रश्न बना हुआ है कि क्या पैले ग्राफ सभी$ q \equiv 1 \pmod 8 $और$ q > 41$ वाले कॉन्फ्रेंस ग्राफ के लिए एकमात्र ऑप्टिमाइज़र है।