🔢 mathematics

Semidefinite lower bounds for covering codes

यह शोध पत्र विभिन्न मापदंडों में नए रिकॉर्ड स्थापित करने के लिए लासेरे-प्रेरित बाधाओं (Lasserre-inspired constraints), सममिति न्यूनीकरण (symmetry reduction) और उन्नत उद्देश्य फलनों (improved objective functions) जैसी उन्नत तकनीकों को एकीकृत करके, कवरिंग कोड्स के न्यूनतम आकार, $K_q(n,r)$ , के लिए सुदृढ़ सेमीडेफिनेट प्रोग्रामिंग निचली सीमाओं (semidefinite programming lower bounds) को प्रस्तुत करता है।

मूल लेखक: Dion Gijswijt, Sven Polak

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

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

CC BY 4.0

मूल लेखक: Dion Gijswijt, Sven Polak

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

कल्पना कीजिए कि आप सीमित संख्या में गोलाकार कालीनों (rugs) का उपयोग करके एक विशाल, बहु-आयामी फर्श को ढंकने की कोशिश कर रहे हैं। आपका लक्ष्य कम से कम कालीनों का उपयोग करना है जबकि यह सुनिश्चित करना है कि फर्श का हर एक कोना कम से कम एक कालीन से ढका हुआ हो। यदि आप एक छोटा सा भी अंतराल छोड़ देते हैं, तो आप सफल नहीं होंगे।

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

विशिष्ट प्रश्न जो यह शोध पत्र पूछता है वह है: "न्यूनतम कितने कालीनों (संदेशों) का उपयोग हमें पूर्ण कवरेज की गारंटी देने के लिए करना ही होगा?"

सटीक उत्तर खोजना अविश्वसनीय रूप से कठिन है। यह अनंत आयामों वाले कमरे में फर्नीचर की एकदम सही व्यवस्था खोजने जैसा है। एक आदर्श व्यवस्था खोजने के बजाय, लेखक एक लोअर बाउंड (lower bound) सिद्ध करने पर ध्यान केंद्रित करते हैं। दूसरे शब्दों में, वे यह सिद्ध करना चाहते हैं कि: "आप कितने भी चतुर क्यों न हों, आप इससे कम कालीनों के साथ इसे नहीं कर सकते।"

द "फुटबॉल पूल" एनालॉजी (Football Pool Analogy)

यह शोध पत्र एक मजेदार वास्तविक दुनिया का उदाहरण बताता है जिसे "फुटबॉल पूल प्रॉब्लम" कहा जाता है। कल्पना कीजिए कि आप $n$ फुटबॉल मैचों पर दांव लगा रहे हैं। प्रत्येक मैच के 3 संभावित परिणाम हैं: होम विन (Home win), ड्रॉ (Draw), या अवे विन (Away win)। आप कुछ बेटिंग स्लिप्स (एक कोड) खरीदना चाहते हैं ताकि चाहे परिणाम कुछ भी हों, आपकी कम से कम एक स्लिप में केवल एक गलत भविष्यवाणी हो।

यदि आप 10 मैचों के सभी संभावित परिणामों को कवर करना चाहते हैं, तो जीतने की गारंटी के लिए आपको कितनी स्लिप्स खरीदनी होंगी? यह शोध पत्र विभिन्न परिदृश्यों के लिए आवश्यक न्यूनतम स्लिप्स की गणना करने में मदद करता है।

उन्होंने इसे कैसे हल किया: "गणितीय आवर्धक लेंस" (Mathematical Magnifying Glass)

पहले, गणितज्ञ इस न्यूनतम संख्या का अनुमान लगाने के लिए सरल रैखिक समीकरणों (linear equations) का उपयोग करते थे। इसे ऐसे समझें कि जैसे आप एक घुमावदार रेखा को मापने के लिए रूलर (पैमाने) का उपयोग कर रहे हैं; यह एक मोटा विचार देता है, लेकिन यह बहुत सटीक नहीं है।

लेखकों ने एक बहुत अधिक शक्तिशाली उपकरण बनाया है: सेमीडेफिनेट प्रोग्रामिंग (SDP)।

एनालॉजी: यदि पुराना तरीका एक रूलर था, तो यह नया तरीका एक हाई-रिज़ॉल्यूशन 3D स्कैनर है। यह केवल बिंदुओं के जोड़ों को नहीं देखता है; यह यह भी देखता है कि बिंदुओं के त्रिक (triplets) आपस में एक साथ कैसे क्रिया करते हैं।
"लासेरे पदानुक्रम" (Lasserre Hierarchy): लेखकों ने अनुकूलन सिद्धांत (optimization theory) से एक तकनीक उधार ली है (जिसे लासेरे पदानुक्रम कहा जाता है), जो आपके स्कैन में अधिक और अधिक विवरण जोड़ने जैसा है। वे "3-पॉइंट" स्तर पर रुक गए क्योंकि इससे ऊपर जाने पर गणित इतना भारी हो जाता है कि सुपरकंप्यूटर भी संघर्ष करने लगेंगे।

गुप्त हथियार: समरूपता (Symmetry)

इस "3D स्कैनर" के साथ सबसे बड़ी समस्या डेटा की विशाल मात्रा है। यदि आपके पास 20 फुटबॉल मैचों के लिए एक कोड है, तो संभावित व्यवस्थाओं की संख्या ब्रह्मांड में मौजूद परमाणुओं की संख्या से भी अधिक है।

इसे हल करने के लिए, लेखकों ने सिमेट्री रिडक्शन (Symmetry Reduction) का उपयोग किया।

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

उन्होंने क्या पाया

इस शक्तिशाली "स्कैनर" और "सिमेट्री शॉर्टकट" का उपयोग करके, लेखकों ने कई अलग-अलग परिदृश्यों (विभिन्न मैचों की संख्या, विभिन्न प्रकार के परिणामों) के लिए नए, सख्त लोअर बाउंड की गणना की।

परिणाम: उन्होंने साबित किया कि कई विशिष्ट मामलों के लिए, आपको पहले की तुलना में अधिक कालीनों की आवश्यकता है।
प्रभाव: उन्होंने इन गणितीय समस्याओं के लिए "रिकॉर्ड बुक्स" को अपडेट किया। उदाहरण के लिए, उन्होंने दिखाया कि कुछ फुटबॉल पूल परिदृश्यों के लिए, पुराने अनुमान बहुत आशावादी थे, और जीत की गारंटी देने के लिए आपको वास्तव में एक बड़े सुरक्षा जाल की आवश्यकता है।

सारांश

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

समस्या की परिभाषा
यह शोधपत्र $K_q(n, r)$ को निर्धारित करने की समस्या को संबोधित करता है, जिसे $n$ शब्द लंबाई और $r$ कविंग रेडियस (covering radius) वाले $q$ -ary कविंग कोड के न्यूनतम आकार के रूप में परिभाषित किया गया है। एक कोडवर्ड सेट $C \subseteq \{0, \dots, q-1\}^n$ का कविंग रेडियस $r$ तब होता है जब कोडवर्ड्स के केंद्र में स्थित $r$ त्रिज्या वाले हैमिंग बॉल्स (Hamming balls) का संघ (union) संपूर्ण हैमिंग स्पेस को कवर करता है। इस समस्या का एक विशिष्ट उदाहरण, $K_3(n, 1)$ , "फुटबॉल पूल समस्या" के रूप में जाना जाता है, जो $n$ फुटबॉल मैचों में अधिकतम एक त्रुटि सुनिश्चित करने के लिए आवश्यक पूर्वानुमानों की न्यूनतम संख्या की खोज करता है। जबकि ऊपरी सीमाएँ (upper bounds) आमतौर पर स्पष्ट कोड बनाकर स्थापित की जाती हैं, यह शोधपत्र $K_q(n, r)$ के लिए बेहतर निचली सीमाओं (lower bounds) को प्राप्त करने पर ध्यान केंद्रित करता है।

कार्यप्रणाली
लेखक गेजविज्ट (Gijiewijt, 2005) के कार्य पर आधारित हैं, जिसने मैट्रिक्स कट्स (matrix cuts) का उपयोग करके कविंग कोड के लिए एक सेमीडेफिनेट प्रोग्रामिंग (SDP) निचली सीमा पेश की थी। प्रस्तुत शोधपत्र तीन प्राथमिक तकनीकी प्रगतियों के माध्यम से इस सीमा को सुदृढ़ करता है:

लैसेरे पदानुक्रम बाधाएं (Lasserre Hierarchy Constraints): लेखक 0-1 प्रोग्रामों के लिए लैसेरे पदानुक्रम से प्रेरित नई सेमीडेफिनेट बाधाएं पेश करते हैं। विशेष रूप से, वे दूसरे स्तर के पदानुक्रम का उपयोग करते हैं, जिसमें कोडवर्ड के त्रिकों (triples) के वितरण का विश्लेषण शामिल है। इससे एक मैट्रिक्स $N$ का निर्माण होता है जो कोड के इनसिडेंस वेक्टर (incidence vector) से व्युत्पन्न है, जो $\sum \lambda_i A_i(u) \ge \beta$ के रूप में कविंग असमानताओं (covering inequalities) के अधीन है।
टेरविलीजर बीजगणित (Terwilliger Algebras) के माध्यम से समरूपता न्यूनीकरण (Symmetry Reduction): परिणामी SDP को गणनात्मक रूप से सुलभ बनाने के लिए, लेखक समरूपता न्यूनीकरण का उपयोग करते हैं। वे हैमिंग स्कीम (बाइनरी और नॉन-बाइनरी दोनों मामलों) के टेरविलीजर बीजगणित का उपयोग करते हैं। इसोमेट्री समूह $Aut(q, n) $(और इसके स्टेबलाइज़र सबग्रुप$ $(औरइसकेस्टेबलाइज़रसबग्रुप$ Aut_0(q, n)$) के तहत कोडवर्ड के जोड़ों और त्रिकों के ऑर्बिट्स (orbits) की पहचान करके, वे मैट्रिक्स वेरिएबल्स के आयाम को कम करते हैं।
- बाइनरी मामले ( $q=2$ ) के लिए, बीजगणित $A_{2,n}$ को एक $\ast$ -आइसोमोर्फिज्म $\phi$ का उपयोग करके ब्लॉक-डायगोनलाइज किया जाता है, जो इसे छोटे मैट्रिक्स ब्लॉक्स के डायरेक्ट सम (direct sum) में मैप करता है, जिससे जटिलता $O(2^n)$ से घटकर $O(n^3)$ वेरिएबल्स हो जाती है।
- नॉन-बाइनरी मामले ( $q \ge 3$ ) के लिए, $A_{q,n}$ बीजगणित के लिए इसी तरह का ब्लॉक-डायगोनलाइजेशन लागू किया जाता है, जिससे जटिलता $O(n^4)$ वेरिएबल्स तक कम हो जाती है।
उन्नत उद्देश्य फलन (Enhanced Objective Function): शोधपत्र एक अधिक शक्तिशाली उद्देश्य फलन का प्रस्ताव करता है। कोड के आकार से संबंधित मानक रैखिक पद को न्यूनतम करने के बजाय, लेखक कोड के आकार के तीसरे क्षण (third moment, $|C|^3$ ) से संबंधित मैट्रिक्स वेरिएबल के ट्रेस (trace) को न्यूनतम करते हैं। वे सिद्ध करते हैं कि यह क्यूबिक उद्देश्य (cubic objective) पिछले रैखिक या द्विघात उद्देश्यों की तुलना में कड़ाई से अधिक सटीक निचली सीमा प्रदान करता है।

प्रमुख योगदान

सैद्धांतिक ढांचा: शोधपत्र कविंग कोड के लिए एक कठोर SDP ढांचे को स्थापित करता है जो एरर-करेक्टिंग कोड के लिए श्राइवर (Schrijver) की सीमाओं को कविंग समस्या के लिए सामान्यीकृत करता है। यह लैसेरे पदानुक्रम के संदर्भ में मैट्रिक्स $N$ और बॉर्डरेड मैट्रिसेस $R(c, N)$ के लिए बाधाओं को औपचारिक रूप से व्युत्पन्न करता है।
समरूपता न्यूनीकरण एल्गोरिदम: लेखक बाइनरी और नॉन-बाइनरी हैमिंग स्कीम्स के लिए प्रासंगिक टेरविलीजर बीजगणित के ब्लॉक-डायगोनलाइजेशन के लिए स्पष्ट सूत्र प्रदान करते हैं। इसमें मैट्रिक्स कट असमानताओं और लैसेरे बाधाओं को कम किए गए वेरिएबल स्पेस में अनुवादित करने के लिए आवश्यक विस्तृत कॉम्बिनेटरियल गुणांक ( $\eta$ और $\alpha$ ) शामिल हैं।
कंप्यूटेशनल कार्यान्वयन: लेखकों ने जूलिया (Julia) प्रोग्रामिंग भाषा और SDPA-GMP सॉल्वर के माध्यम से हाई-प्रिसिजन अंकगणित (512-बिट BigFloats) का उपयोग करके इन सीमाओं को लागू किया। उन्होंने SDP के निर्माण को मान्य करने के लिए स्वतंत्र कोड विकसित किया।

परिणाम
लेखक मापदंडों ( $q, n, r$ ) की एक विस्तृत श्रृंखला में $K_q(n, r)$ के लिए नई निचली सीमाएं प्रस्तुत करते हैं। ये परिणाम तालिकाओं 1, 2 और 3 में संकलित हैं, जो बाइनरी ( $q=2$ ), टेनरी ( $q=3$ ), और क्वाटरनरी/क्विनेरी ( $q=4, 5$ ) मामलों को कवर करते हैं।

बाइनरी मामला: नए परिणाम विभिन्न $n$ और $r$ मानों के लिए पहले से ज्ञात निचली सीमाओं में सुधार करते हैं (जैसे, $K_2(13, 1)$ , $K_2(21, 1)$ , $K_2(13, 2)$ )। लेखक नोट करते हैं कि हालांकि उन्होंने शुरू में $K_2(18, 1)$ और $K_2(30, 1)$ के लिए बेहतर सीमाएं पाई थीं, लेकिन इन विशिष्ट मानों को बाद में वू और चेन (Wu and Chen, 2026) द्वारा पार कर लिया गया था।
नॉन-बाइनरी मामला: टेनरी कोड (फुटबॉल पूल समस्या), जैसे कि $K_3(13, 3)$ और $K_3(14, 4)$ , साथ ही $q=4$ और $q=5$ के लिए महत्वपूर्ण सुधार दर्ज किए गए हैं।
कंप्यूटेशनल पैमाना: शोधपत्र वेरिएबल्स की संख्या और ब्लॉक आकारों का विवरण प्रस्तुत करता है। उदाहरण के लिए, बाइनरी मामले में $n=32$ के लिए, रिड्यूस्ड SDP में 1,239 वेरिएबल्स शामिल हैं जिनका स्क्वेर्ड ब्लॉक साइज का योग 6,545 है। समाधान का समय इंस्टेंस के आकार और असमानता बाधाओं में गैर-शून्य गुणांकों की संख्या के आधार पर सेकंड से लेकर कई दिनों तक रहा।

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

द "फुटबॉल पूल" एनालॉजी (Football Pool Analogy)

उन्होंने इसे कैसे हल किया: "गणितीय आवर्धक लेंस" (Mathematical Magnifying Glass)

गुप्त हथियार: समरूपता (Symmetry)

उन्होंने क्या पाया

सारांश

इसी तरह के और पेपर