🔢 mathematics

New upper bounds on covering codes K_q(n,R) for alphabets of size six and seven

यह शोध पत्र फोकस्ड लोकल सर्च के माध्यम से प्राप्त और कई स्वतंत्र विधियों द्वारा सत्यापित, वर्णमाला आकारों $q \in \{6,7\}$ के लिए मानक तालिकाओं $K_q(n,R)$ के नौ प्रविष्टियों के लिए बेहतर ऊपरी सीमाएँ प्रस्तुत करता है।

मूल लेखक: Mark Marosi

प्रकाशित 2026-08-21

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

CC BY 4.0

मूल लेखक: Mark Marosi

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

एक विशाल, बहु-आयामी ग्रिड की कल्पना करें जहाँ प्रत्येक बिंदु प्रतीकों के एक अद्वितीय संयोजन का प्रतिनिधित्व करता है, जैसे कि कई डायल वाला एक ताला, जिसमें प्रत्येक डायल के कई संभावित सेटिंग्स हों। गणित में, इस ग्रिड को 'हैमिंग स्पेस' (Hamming space) कहा जाता है, और इसके बिंदु विशिष्ट वर्णों के बने शब्द होते हैं। एक "कोड" (code) वास्तव में चुने हुए बिंदुओं का एक सावधानीपूर्वक चयनित संग्रह है। कवरिंग कोड्स का लक्ष्य इस ग्रिड में कम से कम बिंदुओं को रखना है, जबकि यह सुनिश्चित करना है कि पूरे स्थान का प्रत्येक बिंदु चुने गए कम से कम एक बिंदु के करीब हो। "करीब" को एक विशिष्ट दूरी सीमा द्वारा परिभाषित किया जाता है; यदि आप उस दूरी के भीतर हैं, तो माना जाता है कि आप कवर हो गए हैं। यह समस्या केवल एक अमूर्त पहेली नहीं है; यह इस बात का आधार है कि डेटा को कितनी विश्वसनीयता से संग्रहीत और प्रसारित किया जाता है, जिससे यह सुनिश्चित होता है कि संचार के दौरान कुछ प्रतीक खराब होने पर भी मूल संदेश को पुनः प्राप्त किया जा सके। दशकों से, गणितज्ञ विभिन्न आकारों के ग्रिडों को कवर करने के लिए आवश्यक बिंदुओं की न्यूनतम संख्या खोजने का प्रयास कर रहे हैं, जिससे उनके सर्वोत्तम ज्ञात उत्तरों की तालिकाएँ बनाई जाती हैं जो इस क्षेत्र के मानचित्र के रूप में कार्य करती हैं।

एक दशक से अधिक समय तक, बड़े वर्ण समूहों वाले कुछ जटिल परिदृश्यों के लिए यह मानचित्र अपडेट होने से रुक गया था। छह या सात अलग-अलग प्रतीकों वाले ग्रिडों के लिए इन कठिन मामलों में अंतिम प्रमुख संशोधन 2011 में हुआ था, और तब से इन मामलों के प्रविष्टियाँ स्थिर रही हैं। मौजूदा उत्तर, जो बड़े और सरल समाधानों को बड़े समाधानों में संयोजित करने वाले सामान्य गणितीय नियमों से प्राप्त किए गए थे, गहन और लक्षित खोज का परिणाम नहीं थे। ये नियम एक सुरक्षित ऊपरी सीमा (upper limit) प्रदान करते थे—एक गारंटी कि एक निश्चित आकार के भीतर एक समाधान मौजूद है—लेकिन वे आवश्यक रूप से सबसे छोटा संभव समाधान नहीं पाते थे। यह ऐसा था जैसे मानचित्रकारों ने एक खजाने के चारों ओर एक मोटा अनुमान लगाकर एक बड़ा घेरा खींच दिया हो, बजाय इसके कि वे सटीक स्थान खोजने के लिए जमीन की खुदाई करें।

एक नए अध्ययन ने अंततः इस लंबे समय से चले आ रहे ठहराव को तोड़ दिया है, जिसमें छह या सात के वर्ण आकार वाले नौ विशिष्ट परिदृश्यों के लिए बिंदुओं के काफी छोटे संग्रह खोजे गए हैं। शोधकर्ताओं ने, एक आर्टिफिशियल इंटेलिजेंस सिस्टम के साथ मिलकर काम करते हुए, पुराने, व्यापक गणितीय नियमों पर भरोसा नहीं किया। इसके बजाय, उन्होंने मौजूदा बड़े समाधानों को लिया और उन्हें बेहतर बनाने के लिए एक केंद्रित खोज पद्धति का उपयोग किया। यह प्रक्रिया एक बड़ी, थोड़ी अक्षम व्यवस्था से शुरू करने और फिर यह देखने के लिए सूक्ष्म, सटीक समायोजन करने के समान है कि क्या उस व्यवस्था को और अधिक कसा जा सकता है। सिस्टम ग्रिड में एक ऐसे बिंदु को चुनता था जो अभी तक कवर नहीं हुआ था, फिर यह देखता था कि मौजूदा बिंदुओं में से एक को उसे कवर करने के लिए बदलने का सबसे अच्छा तरीका क्या है, और फिर इस प्रक्रिया को हजारों बार दोहराता था। इस 'लोकल सर्च' (local search) पद्धति ने सिस्टम को पुराने सामान्य नियमों की सीमाओं से बाहर निकलने और अधिक कुशल व्यवस्थाएं खोजने में सक्षम बनाया जो सामने ही छिपी हुई थीं।

परिणाम ठोस और विशिष्ट हैं। सात की लंबाई वाले ग्रिड के लिए जिसमें छह प्रतीक हैं, शोधकर्ताओं ने 232 बिंदुओं वाला एक कोड पाया, जो पिछले ऊपरी स्तर (upper bound) 246 से बेहतर है। एक अन्य मामले में, छह प्रतीकों वाले आठ की लंबाई वाले ग्रिड के लिए, उन्होंने आवश्यक बिंदुओं की संख्या को पिछले ऊपरी स्तर 1,080 से घटाकर 1,045 कर दिया। सबसे नाटकीय सुधार छह प्रतीकों वाले आठ की लंबाई वाले एक परिदृश्य में हुआ, जहाँ नया कोड केवल 167 बिंदुओं की आवश्यकता रखता है, जो पिछले ऊपरी स्तर 216 से 49 बिंदुओं की कमी है। कुल मिलाकर, नौ नए, छोटे कोड खोजे गए। ये सैद्धांतिक अनुमान नहीं हैं; शोधकर्ताओं ने प्रत्येक नौ कोड के लिए बिंदुओं की सटीक सूची प्रदान की है, जिससे कोई भी परिणामों को सत्यापित कर सके। पूर्ण निश्चितता सुनिश्चित करने के लिए, उन्होंने प्रत्येक कोड की जाँच चार अलग-अलग, स्वतंत्र कंप्यूटर प्रोग्रामों का उपयोग करके की। ये प्रोग्राम अलग-अलग तरीकों से काम करते थे: कुछ ने एक डिजिटल मानचित्र पर प्रत्येक कवर किए गए बिंदु को चिह्नित किया, जबकि अन्य ग्रिड के प्रत्येक संभावित बिंदु से निकटतम कोड बिंदु की दूरी की गणना करते थे। तथ्य यह है कि सभी विधियों ने सहमति व्यक्त की, इसने पुष्टि की कि नए कोड वैध हैं और कवरिंग रेडियस (covering radius) बिल्कुल वैसा ही है जैसा दावा किया गया है।

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

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

तकनीकी सारांश: छह और सात के वर्णमाला (Alphabets) के लिए नए अपर बाउंड्स $K_q(n, R)$

समस्या विवरण
यह शोध पत्र $K_q(n, R)$ के लिए अपर बाउंड्स (upper bounds) निर्धारित करने की समस्या को संबोधित करता है, जिसे $n$ लंबाई वाले $q$ -ary कोड के न्यूनतम कार्डिनैलिटी (cardinality) के रूप में परिभाषित किया गया है जिसका कवरेज रेडियस (covering radius) $R$ है। एक कोड $C \subseteq \mathbb{Z}_q^n$ का कवरेज रेडियस $R$ तब होता है जब हैमिंग स्पेस $\mathbb{Z}_q^n$ का प्रत्येक शब्द कम से कम एक कोडवर्ड से दूरी $R$ के भीतर हो। यह अध्ययन विशेष रूप से $q \in \{6, 7\}$ के वर्णमाला और $n \le 10$ की लंबाई पर केंद्रित है। लेखक नोट करते हैं कि इन बाउंड्स के लिए मानक संदर्भ तालिकाएं, जिन्हें केरी (Kéri) द्वारा बनाए रखा जाता है (अंतिम बार 2011 में अपडेट किया गया था), $q \ge 5$ के लिए उस तिथि के बाद से कोई सुधार नहीं देख पाई हैं। इस कार्य में लक्षित प्रविष्टियाँ पहले केवल सामान्य बीजगणितीय निर्माणों (जैसे डायरेक्ट सम और प्रोडक्ट रूल्स) से व्युत्पन्न की गई थीं, न कि स्पष्ट खोज (explicit search) से, जिससे ज्ञात अपर बाउंड्स और सैद्धांतिक स्फीयर-कवरिंग लोअर बाउंड्स के बीच एक "सापेक्ष ढीलापन" (relative slack) रह गया था।

कार्यप्रणाली (Methodology)
लेखक मौजूदा कोड्स में सुधार करने के लिए वॉकसैट (WalkSAT) वंश की जड़ों वाला और टैबू सर्च (tabu search) के समान एक केंद्रित लोकल सर्च एल्गोरिदम का उपयोग करते हैं। यह कार्यप्रणाली तीन प्राथमिक घटकों से बनी है:

खोज अवस्था और अपडेट (Search State and Updates): खोज $M$ कोडवर्ड्स के एक मल्टीसेट (multiset) को बनाए रखती है और $\mathbb{Z}_q^n$ के प्रत्येक शब्द के लिए कवरेज काउंट को ट्रैक करती है। दक्षता सुनिश्चित करने के लिए, एल्गोरिदम लेम्मा 1 (Lemma 1) से प्राप्त एक विशिष्ट अपडेट तंत्र का उपयोग करता है। जब किसी कोडवर्ड के एक सिंगल कोऑर्डिनेट को बदला जाता है, तो रेडियस- $R$ बॉल से बाहर जाने वाले शब्दों का सेट और नए बॉल में प्रवेश करने वाले शब्दों का सेट, शेष कोऑर्डिनेट्स में ठीक दूरी $R$ पर स्थित शब्दों द्वारा इंडेक्स किया जाता है। यह एल्गोरिदम को प्रत्येक मूव पर ठीक $2S$ कवरेज काउंटर अपडेट करने की अनुमति देता है, जहाँ $S = \binom{n-1}{R}(q-1)^R$ , जिससे पूरे स्पेस का पुन: स्कैन करने से बचा जा सकता है।
खोज रणनीति (Search Strategy): एल्गोरिदम एक रैंडम अनकवर्ड (uncovered) शब्द $u$ चुनता है और संभावित मूव्स की पहचान करता है: $u$ से दूरी $R+1$ पर स्थित कोडवर्ड्स को $u$ की ओर एक कोऑर्डिनेट खिसकाया जाता है। यदि ऐसा कोई कोडवर्ड मौजूद नहीं है, तो न्यूनतम दूरी वाले कोडवर्ड्स का उपयोग किया जाता है। सभी उम्मीदवारों का सटीक मूल्यांकन किया जाता है और समानांतर (parallel) रूप से किया जाता है। सबसे अच्छे उम्मीदवार को प्रतिबद्ध (commit) किया जाता है, और बराबरी होने पर रैंडमली निर्णय लिया जाता है। ठहराव (stagnation) से बचने के लिए, एक कोडवर्ड को अनकवर्ड शब्द की ओर "टेलीपोर्ट" किया जाता है। पैरामीटर अध्ययनों ने संकेत दिया कि सभी कैंडिडेट मूव्स का सटीक मूल्यांकन करना सैंपलिंग रणनीतियों की तुलना में बेहतर रहा, और मूव की संख्या के बजाय मूव की गुणवत्ता अधिक महत्वपूर्ण थी (सिमुलेटेड एनीलिंग कम प्रभावी थी)।
सीडिंग और डिसेंट (Seeding and Descent): खोज को उन्हीं सामान्य विधियों से निर्मित कोड्स के साथ सीड (seed) किया जाता है जिन्होंने पिछले अपर बाउंड्स को बनाया था (जैसे डायरेक्ट सम)। सुधार प्रक्रिया में एक "रिमूव-एंड-रिपेयर" (remove-and-repair) डिसेंट शामिल है: जिस कोडवर्ड का "प्राइवेट कवरेज" (शब्द जो केवल उसी कोडवर्ड द्वारा कवर किए गए हैं) सबसे कम है उसे हटा दिया जाता है, और परिणामी कमी को लोकल सर्च के माध्यम से सुधारा जाता है। यदि सफल होता है, तो प्रक्रिया $M-1$ कोडवर्ड्स के साथ दोहराई जाती है। छोटे घटकों पर इस "फैक्टर अटैक" (factor attack) ने सीडिंग के लिए निर्णायक भूमिका निभाई, जबकि डिसेंट चरण ने प्रारंभिक निर्माणओं की कठोर उत्पाद संरचना (product structure) को तोड़ दिया।

हार्डवेयर और कार्यान्वयन
सभी गणनाएँ एक सिंगल NVIDIA GH200 नोड पर इसके 64-कोर ग्रेस (Grace) CPU का उपयोग करके की गईं। जबकि एक CUDA पोर्ट भी बनाया गया था, यह पाया गया कि यह लेटेंसी-बाउंड (latency-bound) था और इन विशिष्ट इंस्टेंस साइज के लिए CPU की तुलना में धीमा था। मूव थ्रूपुट बड़े इंस्टेंस के लिए लगभग 1,300 मूव्स/सेकंड से लेकर छोटे इंस्टेंस के लिए 400,000 मूव्स/सेकंड तक भिन्न हुआ। प्रत्येक एंट्री के लिए खोज अभिसरण (convergence) से पहले रोक दी गई थी, जिससे पता चलता है कि बढ़ी हुई गणना समय के साथ और सुधार संभव हो सकते हैं।

प्रमुख परिणाम
अध्ययन $q \in \{6, 7\}$ और $n \le 10$ की रेंज में नौ विशिष्ट प्रविष्टियों के लिए बेहतर अपर बाउंड्स की रिपोर्ट करता है। नए बाउंड्स हैं:

$K_6(7, 3) \le 232$ (पिछले बाउंड 246 से 14 का सुधार)
$K_6(8, 3) \le 1045$ (35 का सुधार)
$K_6(8, 4) \le 167$ (49 का सुधार)
$K_6(9, 4) \le 703$ (35 का सुधार)
$K_6(9, 5) \le 123$ (21 का सुधार)
$K_6(10, 4) \le 2951$ (1 का सुधार)
$K_6(10, 5) \le 610$ (5 का सुधार)
$K_7(8, 4) \le 329$ (14 का सुधार)
$K_7(9, 4) \le 1743$ (100 का सुधार)

सबसे महत्वपूर्ण सापेक्ष सुधार $K_6(8, 4)$ के लिए 23% की कमी है। सभी नौ कोड्स को सहायक फाइलों (ancillary files) में स्पष्ट रूप से प्रदान किया गया है।

सत्यापन (Verification)
परिणामों की वैधता सुनिश्चित करने के लिए, प्रत्येक दावा किए गए कोड को चार स्वतंत्र, गहन सत्यापन विधियों के अधीन किया गया:

बॉल मार्किंग (Ball marking): प्रत्येक कोडवर्ड के भीतर की दूरी $R$ के भीतर के सभी शब्दों को बिटमैप पर मार्क करना।
मीट-इन-द-मिडल (Meet-in-the-middle): एक कोऑर्डिनेट स्प्लिट पर बिटसेट कवरेज।
मिन-डिस्टेंस स्कैन (Min-distance scan): निकटतम कोडवर्ड की दूरी की गणना करने के लिए सभी $q^n$ शब्दों की गणना करना।
हैमिंग-ग्राफ डायलेशन (Hamming-graph dilation): दूरियों की गणना किए बिना कोड के इंडिकेटर वेक्टर का $R$ -फोल्ड नेबरहुड डायलेशन कंप्यूट करना।
इसके अतिरिक्त, एक पांचवें, स्वतंत्र रूप से लिखे गए डायलेशन वेरीफायर ने सभी परिणामों की पुष्टि की। सबसे बड़ा सत्यापन (जिसमें $6^{10} \approx 60$ मिलियन शब्द शामिल थे) कुछ ही सेकंडों में पूरा हो गया।

महत्व और दावे
शोध पत्र दावा करता है कि ये 2011 के बाद $q \ge 5$ के साथ $K_q(n, R)$ के किसी भी अपर बाउंड में पहले सुधार हैं। लेखक इस सफलता का श्रेय आधुनिक, बड़े पैमाने के लोकल सर्च हार्डवेयर को उन प्रविष्टियों पर लागू करने को देते हैं जिन्हें पहले केवल सामान्य बीजगणितीय निर्माणों द्वारा संबोधित किया गया था। परिणाम प्रदर्शित करते हैं कि "प्लेन लोकल सर्च", जब निर्माण-आधारित इंकम्बेंट्स (incumbents) के साथ सीड किया जाता है, तो उन मामलों में विरासत में मिले अंकगणितीय बाउंड्स से बेहतर प्रदर्शन कर सकता है जहाँ स्लैब (slack) महत्वपूर्ण (4×–10×) है। इसके विपरीत, विधि उन सेल्स को सुधारने में विफल रही जो पहले से ही समर्पित खोज या बीजगणितीय निर्माण का विषय थे (जहाँ स्लैक $\le 3\times$ था)।

लेखक केरी की तालिकाओं में $K_{17}(7, 2)$ के संबंध में एक आंतरिक विसंगति देखते हैं, जिसे उन्होंने देखा तो लेकिन नए निर्माण के साथ हल नहीं किया। वे इन नए बाउंड्स को मौजूदा लोअर-बाउंड साहित्य के साथ मिलाकर एक मर्ज की गई, मशीन-रीडेबल टेबल प्रकाशित करने का इरादा रखते हैं।

लेखकत्व और AI योगदान
शोध पत्र स्पष्ट रूप से बताता है कि खोज और सत्यापन पाइपलाइन को स्वायत्त रूप से AI सिस्टम क्लॉड (Claude - Anthropic) द्वारा डिजाइन, कार्यान्वित और संचालित किया गया था। मानव लेखक का योगदान प्रारंभिक विचार (फ्रीज की गई तालिकाओं पर आधुनिक हार्डवेयर लागू करना), पद्धतिगत मार्गदर्शन और कम्प्यूटेशनल संसाधनों के प्रावधान तक सीमित है। AI सिस्टम को परिणामों के प्राथमिक योगदानकर्ता के रूप में माना जाता है।

तकनीकी सारांश: छह और सात के वर्णमाला (Alphabets) के लिए नए अपर बाउंड्स Kq(n,R)K_q(n, R)Kq​(n,R)

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

तकनीकी सारांश: छह और सात के वर्णमाला (Alphabets) के लिए नए अपर बाउंड्स $K_q(n, R)$