On Reed-Muller subcodes, Grassmannian partitions and sum-free functions

तकनीकी सारांश: रीड-मुलर उपकोड्स (Reed-Muller subcodes), ग्रासमैनियन विभाजन (Grassmannian partitions) और सम-मुक्त फलन (sum-free functions) पर

समस्या विवरण
यह शोध पत्र कोडिंग थ्योरी और परिमित ज्यामिति (finite geometry) के तीन परस्पर जुड़े हुए विषयों को संबोधित करता है:

1. रीड-मुलर उपकोड (Reed-Muller Subcodes): रीड-मुलर कोड $RM(r, n)$ के रैखिक उपकोड्स का निर्माण जो सभी न्यूनतम भार वाले कोडवर्ड्स (minimum weight codewords) से बचते हैं, जिससे मूल कोड की तुलना में अधिक न्यूनतम दूरी (minimum distance) प्राप्त होती है।
2. सम-मुक्त फलनों (Sum-Free Functions) का अस्तित्व: $k$-वें क्रम के सम-मुक्त फलनों $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ के अस्तित्व की स्थितियों और आवश्यक सीमाओं का निर्धारण करना। एक फलन $k$-वें क्रम का सम-मुक्त तब होता है जब किसी भी $k$-आयामी अफ़ाइन उप-स्थान (affine subspace) पर उसके मानों का योग शून्य नहीं होता। जबकि कारलेट (Carlet) ने हाल ही में इस अवधारणा को पेश किया और ऐसे फलनों का एक अनंत परिवार (जहाँ $m=n$) प्रदान किया, $m < n$ के लिए और विशिष्ट क्रम $k \ge 3$ के लिए ऐसे फलनों का अस्तित्व काफी हद तक खुला प्रश्न बना हुआ है।
3. ग्रासमैनियन विभाजन (Grassmannian Partitioning): $\mathbb{F}_2^n$ के सभी $k$-आयामी रैखिक उप-स्थानों (Grassmannian) को स्थिर-आयामी उप-स्थान कोडों में विभाजित करने की समस्या। यह ग्रासमैन ग्राफ $J_2(n, k)$ के क्रोमैटिक संख्या $\chi(J_2(n, k))$ को निर्धारित करने के समतुल्य है, जहाँ शीर्ष (vertices) $k$-स्थान हैं और किनारे (edges) उन स्थानों को जोड़ते हैं जो $k-1$ आयाम में प्रतिच्छेद करते हैं।

कार्यप्रणाली (Methodology)
लेखक कोडिंग थ्योरी और सम-मुक्त फलनों के गुणों के बीच एक कठोर संबंध स्थापित करते हैं।

• पत्राचार निर्माण (Correspondence Construction): शोध पत्र सिद्ध करता है कि एक गैर-अपभ्रष्ट (non-degenerate) $(n-r)$-वें क्रम का सम-मुक्त फलन $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ एक $RM(r, n)$के को-डायमेंशन$m$वाले रैखिक उपकोड के अस्तित्व के समतुल्य है, जिसकी न्यूनतम दूरी$3 \cdot 2^{n-r-1}$है। यह फलन$F$ के मूल्यांकन वेक्टरों (evaluation vectors) का उपयोग करके उपकोड के लिए एक पैरिटी-चेक मैट्रिक्स का निर्माण करके प्राप्त किया जाता है।
• बीजीय विश्लेषण (Algebraic Analysis): लेखक बूलियन फलनों की बीजीय डिग्री (algebraic degree), उच्च-क्रम डेरिवेटिव के गुणों, और रीड-मुलर कोड की संरचना (विशेष रूप से फ्लैट्स और उनके सममित अंतर के माध्यम से न्यूनतम और द्वितीय-न्यूनतम भार वाले कोडवर्ड्स का लक्षण वर्णन) का उपयोग करते हैं ताकि सम-मुक्त फलनों के अस्तित्व के लिए आवश्यक शर्तें प्राप्त की जा सकें।
• ग्राफ कलरिंग हेतु फलन (Graph Coloring via Functions): लेखक ग्रासमैन ग्राफ पर कलरिंग को परिभाषित करने के लिए "विटनेस फंक्शन" $\omega_F(A) = \sum_{x \in A} F(x)$ का उपयोग करते हैं। यह सुनिश्चित करके कि आसन्न शीर्ष (adjacent vertices - वे उप-स्थान जो $k-1$ आयाम में प्रतिच्छेद करते हैं) भिन्न गैर-शून्य मानों पर मैप होते हैं, लेखक वैध कलरिंग का निर्माण करते हैं।
• संगणनात्मक सत्यापन (Computational Verification): छोटे आयामों ($n=5, 6, 7$) के लिए, लेखक ज्ञात 'ऑलमोस्ट परफेक्ट नॉन-लीनियर' (APN) फलनों के बीच मल्टी-ऑर्डर सम-मुक्त फलनों के अस्तित्व को सत्यापित करने के लिए संगणनात्मक खोज (computational searches) करते हैं।

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

1. तुल्यता प्रमेय (Theorem 1.1):
   शोध पत्र एक द्वैत पत्राचार (bijective correspondence) स्थापित करता है: एक गैर-अपभ्रष्ट $(n-r)$-वें क्रम का सम-मुक्त $(n, m)$-फलन तभी मौजूद होता है जब $RM(r, n)$के को-डायमेंशन$m$वाले एक रैखिक उपकोड का अस्तित्व हो जिसकी न्यूनतम दूरी$3 \cdot 2^{n-r-1}$ हो।

   • महत्व: यह रीड-मुलर उपकोड्स का एक नया परिवार प्रदान करता है जो $RM(r, n)$के सभी न्यूनतम भार वाले कोडवर्ड्स से बचते हैं। इन उपकोड्स की न्यूनतम दूरी मूल कोड की तुलना में$1.5$गुना अधिक है, और इनका को-डायमेंशन केवल$n$है।$2 < r < n-2$ की सीमा के लिए, ये कोड नए प्रतीत होते हैं।

2. $m$ पर नई निचली सीमाएँ (Theorem 3.5):
   लेखक $k$-वें क्रम के सम-मुक्त फलनों के अस्तित्व के लिए आउटपुट डायमेंशन $m$ पर पहली गैर-तुच्छ निचली सीमा (non-trivial lower bound) प्राप्त करते हैं। $2 \le k \le n-2$ के लिए, यदि एक $(n, m)$-फलन $k$-वें क्रम का सम-मुक्त है, तो:
   $$m \ge \max\{n - k + 2, k + 2\}$$
   यह परिणाम बताता है कि $m < n$ के लिए, कुछ $k$ की श्रेणियों के लिए ऐसे फलन मौजूद नहीं हो सकते, जो पिछले ज्ञान को परिष्कृत करता है जो केवल $m=n$ के मामले तक सीमित था।

3. ज्ञात परिवारों की गैर-अपभ्रष्टता (Theorem 3.6):
   शोध पत्र सिद्ध करता है कि कारलेट द्वारा प्रस्तुत पावर फंक्शन्स $F_{k,j}(x) = x^{(2^{jk}-1)/(2^j-1)}$ का अनंत परिवार $k < n$ के लिए गैर-अपभ्रष्ट है। यह पुष्टि करता है कि इन फलनों को वास्तव में पूर्ण आउटपुट स्पेस डायमेंशन $n$ की आवश्यकता है और सम-मुक्त गुण बनाए रखते हुए इन्हें निम्न-आयामी फलनों में कम नहीं किया जा सकता है।

4. सुधारित ग्रासमैन ग्राफ कलरिंग (Theorem 5.1):
   लेखक पिछले कलरिंग परिणामों का सामान्यीकरण करते हैं। वे दिखाते हैं कि यदि $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ का एक बीजगणितीय डिग्री $k$ वाला फलन मौजूद है जो $(k-1)$-वें और $k$-वें क्रम का दोनों प्रकार से सम-मुक्त है, तो ग्रासमैन ग्राफ $J_2(n+1, k)$ में $\binom{m}{1}_2 = 2^m - 1$ रंगों के साथ एक वैध कलरिंग संभव है।

   • अनुप्रयोग: विषम आयामों में 'इनवर्स फंक्शन' (जो $\{1, 2, n-2, n-1\}$-ऑर्डर सम-मुक्त है) का उपयोग करके, लेखक $J_2(n+1, n-1)$ के लिए एक कलरिंग प्राप्त करते हैं।
   • विशिष्ट परिणाम: $n=5$ के लिए, क्यूबिक $\{2, 3\}$-ऑर्डर सम-मुक्त फलनों ($x^7$ और $x^{21}$) की उपस्थिति $J_2(6, 3)$ के लिए $\chi(J_2(6, 3)) \le 31$ का सीमा निर्धारित करती है, जो पहले ज्ञात ऊपरी सीमाओं में सुधार करती है।

5. मल्टी-ऑर्डर फलनों पर संगणनात्मक निष्कर्ष:
   शोध पत्र रिपोर्ट करता है कि $n=6$ के लिए, कोई भी ज्ञात APN फलन तृतीय या चतुर्थ क्रम का सम-मुक्त नहीं है। $n=7$ के लिए, केवल गोल्ड APN फलनों ($x^{15}, x^{77}, x^{85}$) के समकक्ष फलन ही चौथे क्रम के सम-मुक्त पाए गए। यह सुझाव देता है कि मल्टी-ऑर्डर सम-मुक्त फलन दुर्लभ हैं और उनका निर्माण कठिन है।

महत्व और दावे
शोध पत्र यह दावा करता है कि यह $k$-वें क्रम के सम-मुक्त फलनों और उन्नत न्यूनतम दूरी वाले रीड-मुलर उपकोड्स के निर्माण के बीच सीधा संबंध स्थापित करने वाला पहला कार्य है। यह संबंध उन उपकोड्स को उत्पन्न करने के लिए एक नया बीजगणिक उपकरण प्रदान करता है जो न्यूनतम भार वाले कोडवर्ड्स से बचते हैं।

इसके अतिरिक्त, यह कार्य $m < n$ के लिए सम-मुक्त फलनों के अस्तित्व के लिए पहली गैर-तुच्छ आवश्यक शर्तें प्रदान करता है, जो कारलेट द्वारा उठाए गए एक विशिष्ट खुले प्रश्न को संबोधित करता है। ग्रासमैन ग्राफ के क्रोमैटिक संख्या से इन फलनों को जोड़कर, यह $k > 2$ के मामलों के लिए $\chi(J_2(n, k))$ पर ऊपरी सीमाओं में सुधार करने का एक तरीका प्रदान करता है।

लेखक नए सम-मुक्त फलनों के निर्माण के संबंध में स्वयं को विनम्र रखते हैं, यह नोट करते हुए कि ज्ञात पावर फंक्शन्स के अलावा वास्तव में नए उदाहरण बनाना कठिन है। वे $k \ge 3$ के लिए मल्टी-ऑर्डर सम-मुक्त फलनों के अस्तित्व को एक महत्वपूर्ण खुले प्रश्न के रूप में देखते हैं जिसके कोडिंग थ्योरी (गैर-रैखिक कोड) और ग्राफ थ्योरी दोनों के लिए निहितार्थ हैं।