The Weight Distribution of the Third-Order Reed-Muller Code of Length 2048

तकनीकी सारांश: लंबाई 2048 के तीसरे-क्रम के रीड-मुलर कोड का भार वितरण (Weight Distribution)

समस्या विवरण
रीड-मुलर कोड $RM(r, m)$का भार वितरण कोडिंग सिद्धांत की एक शास्त्रीय समस्या है, फिर भी केवल$r \leqslant 2$ और उनके द्वैत (duals) $r \geqslant m-3$ के लिए ही इसके बंद-रूप (closed-form) समाधान ज्ञात हैं। तीसरे-क्रम के कोड ($r=3$) के लिए, 1024 ($RM(3, 10)$) तक की लंबाई के लिए व्यक्तिगत गणनाओं के माध्यम से पूर्ण वितरण स्थापित किए जा चुके हैं। यह शोध पत्र इस श्रृंखला के अगले चरण: लंबाई 2048 वाले तीसरे-क्रम के रीड-मुलर कोड$RM(3, 11)$ के भार वितरण की गणना को संबोधित करता है। एक माध्यमिक उद्देश्य दस चरों वाले सभी क्यूबिक रूपों (cubic forms) के लिए द्वितीय-क्रम की गैर-रैखिकता (second-order nonlinearity) $d_2(f)$ को निर्धारित करना है, जिससे $RM(3, 10)$के भीतर$RM(2, 10)$ के सापेक्ष कवरेज त्रिज्या (relative covering radius) $\rho_{2,3}(10)$ स्थापित हो सके।

कार्यप्रणाली
यह गणना सारवेट-प्रकार (Sarwate-type) की पुनरावृत्ति (recursion) पर आधारित है, जो $RM(3, m+1)$ के भार गणक (weight enumerator) को सभी क्यूबिक रूपों $f$ पर $f + RM(2, m)$ के वर्गed कोसेट भार गणकों (squared coset weight enumerators) के योग के रूप में व्यक्त करती है। चूंकि कोसेट गणक $f$ के $GL(m, 2)$-कक्षा (orbit) पर निर्भर करता है, इसलिए योग को कक्षा के आकार द्वारा भारित कक्षा प्रतिनिधियों (orbit representatives) में संक्षिप्त किया जा सकता है।

$m=10$ के लिए प्राथमिक बाधा कक्षाओं की विशाल संख्या (3,691,560 गैर-शून्य कक्षाएं) और एक एकल कोसेट गणक का मूल्यांकन करने की लागत है। ब्रियर और लैंग्विन (Brier and Langevin) द्वारा उपयोग किया जाने वाला मानक विभाजन सूत्र $m=10$ के लिए $2^{36}$ समरूप द्विघात रूपों (homogeneous quadratic forms) पर एक बाहरी गणना की आवश्यकता रखता है, जो पूर्ण कैटलॉग पास के लिए कम्प्यूटेशनल रूप से अव्यवहार्य है।

इससे निपटने के लिए, लेखक एक संरचनात्मक प्रमेय (प्रमेय 1) का उपयोग करते हैं: प्रत्येक गैर-अपभ्रष्ट (nondegenerate) बुलियन क्यूबिक रूप एक गैर-अपभ्रष्ट हाइपरप्लेन प्रतिबंध को स्वीकार करता है, केवल प्रत्येक विषम आयाम में एक एकल कक्षा को छोड़कर। $m=10$ (एक सम आयाम) के लिए, यह प्रमेय गारंटी देता है कि प्रत्येक गैर-अपभ्रष्ट कक्षा का एक हाइपरप्लेन पर प्रतिबंध भी गैर-अपभ्रष्ट होगा। यह विधि कोसेट गणक को $2^{36}$ के बजाय $2^{26}$ के कोटिएंट स्पेस (quotient space) के माध्यम से संगणना योग्य बनाती है, जिससे प्रति कक्षा $2^{10}$ का कारक बचता है।

परिणामी एफाइन कोसेट्स (affine cosets) पर कोसेट भार गणकों का मूल्यांकन फास्ट वाल्श-हाडामार्ड ट्रांसफॉर्म (fast Walsh–Hadamard transforms) का उपयोग करके किया जाता है। संपूर्ण कैटलॉग पास के लिए लगभग 65 CPU-वर्ष लगे। परिणामों की सटीकता को सत्यापित करने और दक्षता में सुधार करने के लिए, एक स्थानीय-खोज ह्यूरिस्टिक (greedy descent, $\tau$-moves, iterated local search, और beam search का संयोजन) विकसित किया गया। यह ह्यूरिस्टिक उन स्पष्ट द्विघात सुधारों $q$ को खोजता है जो $wt(f+q)$ को न्यूनतम करते हैं, जिससे पूर्ण सूची के एक अंश लागत पर कवरेज त्रिज्या के लिए प्रमाण (certificates) प्राप्त होते हैं।

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

1. $RM(3, 11)$ का भार वितरण:
   यह शोध पत्र $RM(3, 11)$का पूर्ण भार वितरण (तालिका 1) प्रस्तुत करता है। यह परिणाम दस चरों में बुलियन क्यूबिक रूपों की सभी 3,691,560 गैर-शून्य$GL(10, 2)$-कक्षाओं के वर्ग$d$ कोसेट भार गणकों को जोड़ने के साथ-साथ शून्य कक्षा के योगदान को जोड़कर असेंबल किया गया है।

2. द्वितीय-क्रम की गैर-रैखिकता और सापेक्ष कवरेज त्रिज्या:
   प्रत्येक कोसेट गणक का निम्नतम गैर-शून्य घातांक (exponent) प्रत्येक क्यूबिक रूप की द्वितीय-क्रम की गैर-रैखिकता $d_2(f)$ को दर्शाता है। गणना यह निर्धारित करती है कि दस चरों वाले सभी क्यूबिक रूपों पर $d_2(f)$ का अधिकतम मान 408 है।

• प्रमेय 3: $RM(3, 10)$में$RM(2, 10)$की सापेक्ष कवरेज त्रिज्या$\rho_{2,3}(10)$ ठीक 408 है।
• यह अधिकतम मान 179 विशिष्ट कक्षाओं पर प्राप्त होता है। इन कक्षाओं के प्रतिनिधियों और उनके "किसिंग नंबर" (न्यूनतम भार प्राप्त करने वाले द्विघात रूपों की गणना) को तालिका 2 में सूचीबद्ध किया गया है।
• सभी 179 चरम (extremal) रूप गैर-अपभ्रष्ट हैं।

3. कवरेज त्रिज्या पर सुधरा हुआ निचला स्तर (Lower Bound):
   यह परिणाम $RM(2, 10)$ के कवरेज त्रिज्या के सर्वोत्तम ज्ञात निचले स्तर को 400 से बढ़ाकर 408 कर देता है। 179 कक्षाएं इस स्तर के लिए स्पष्ट गवाह (witnesses) के रूप में कार्य करती हैं।

4. अल्टरनेटिंग रैंक (Alternating Rank) के साथ संबंध:
   यह शोध पत्र $d_2(f)$ और एक क्यूबिक रूप के अल्टरनेटिंग रैंक ($arank$) के बीच संबंध स्थापित करता है। एक व्युत्पन्न सीमा (प्रमेय 4) का उपयोग करते हुए, लेखक दिखाते हैं कि किसी भी रूप के लिए जिसका$d_2(f) = 408$है, उसका अल्टरनेटिंग रैंक कम से कम 6 होना चाहिए।$m=10$में, अधिकतम अल्टरनेटिंग रैंक 7 है। विश्लेषण से पता चलता है कि 179 में से 177 चरम कक्षाओं का$arank = 7$है, जबकि 2 का$arank = 6$है। यह निम्न आयामों ($m \leqslant 9$) के विपरीत है, जहाँ चरम रूपों को उस आयाम के लिए अधिकतम संभव अल्टरनेटिंग रैंक रखने के लिए मजबूर किया गया था।

5. ह्यूरिस्टिक खोज और कोसिकubic बाउंड्स:
   स्थानीय-खोज ह्यूरिस्टिक ने पूर्ण सूची के एक हज़ारवें हिस्से की लागत पर $\rho_{2,3}(10) \leqslant 408$ के बाउंड को सफलतापूर्वक पुनरुत्पादित किया। सात-डिग्री के रूपों पर लागू करने पर, इस ह्यूरिस्टिक ने $RM(7, 10)$में$RM(6, 10)$ की सापेक्ष कवरेज त्रिज्या के ऊपरी बाउंड को 50 से घटाकर 32 कर दिया (लेम्मा 2)।

महत्व
यह शोध पत्र मुख्य रूप से $RM(3, 11)$ के लिए भार वितरण को हल करके अपना महत्व दावा करता है, जो ज्ञात तीसरे-क्रम के कोड की श्रृंखला को आगे बढ़ाता है। गैर-अपभ्रष्ट हाइपरप्लेन प्रतिबंधों के संबंध में संरचनात्मक प्रमेय को एक महत्वपूर्ण सक्षमकर्ता (enabler) के रूप में प्रस्तुत किया गया है, जो पूर्ण कैटलॉग पास को वहां संभव बनाता है जहां पिछली विधियाँ "पहुंच से बाहर" थीं।

$\rho_{2,3}(10) = 408$ का निर्धारण कवरेज त्रिज्या साहित्य के लिए महत्वपूर्ण है, जो $RM(2, 10)$के लिए सर्वोत्तम ज्ञात निचले स्तर को अपडेट करता है। इसके अतिरिक्त, चरम कक्षाओं का विश्लेषण संरचनात्मक अंतर्दृष्टि प्रदान करता है: मोनॉमियल ट्रेस फॉर्म (जो पहले 400 का रिकॉर्ड रखते थे) से बाइनोमियल ट्रेस पॉलिनोमिअल्स की ओर बदलाव और अधिकतम अल्टरनेटिंग रैंक पर चरम रूपों का संकेंद्रण, उच्च आयामों ($m > 10$) में उच्च-गैर-रैखिकता वाले रूपों की खोज के लिए नए दिशा-निर्देश सुझाते हैं। लेखक उल्लेख करते हैं कि कोडिंग सिद्धांत और बुलियन फंक्शन विश्लेषण में आगे के अनुसंधान की सुविधा के लिए गणना डेटा और संदर्भ कोड उपलब्ध कराए गए हैं।