Sharper upper bounds for $q$-ary $B_2$ codes from Toeplitz SDPs

यहाँ स्टेफानो डेला फियोरे के शोध पत्र "Sharper upper bounds for q-ary B2 codes from Toeplitz SDPs" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र $q$-ary $B_2$ कोड्स के लिए अनंतस्पर्शी दर ऊपरी सीमाओं (asymptotic rate upper bounds) को निर्धारित करने की समस्या का समाधान करता है।

• परिभाषा: एक $q$-ary कोड $C_n \subset \{0, \dots, q-1\}^n$ एक $B_2$ कोड है यदि इसके कोडवर्ड्स के सभी युग्मों के योग (वास्तविक संख्याओं पर) विशिष्ट (distinct) हों। अर्थात, $c_i + c_j = c_k + c_l$ होने पर $\{i, j\} = \{k, l\}$ होना चाहिए।
• लक्ष्य: अधिकतम संभव अनंतस्पर्शी दर $R = \limsup_{n \to \infty} \frac{1}{n} \log_q |C_n|$ ज्ञात करना।
• संदर्भ: पिछले अनुमान (जैसे लिंडस्ट्रॉम, वांग, और लेखक का अपना पूर्व कार्य [5]) दो स्वतंत्र यादृच्छिक चरों (random variables) के अंतर $D = X - Y$ की एंट्रॉपी से जुड़े सूचना-सैद्धांतिक तर्कों पर निर्भर थे। हालाँकि, इन विधियों ने मोटे उत्तरोत्तर अनुमानों (coarse relaxations) का उपयोग किया, जो मुख्य रूप से केवल इस प्रतिबंध पर आधारित थे कि टकराव की प्रायिकता (collision probability) $P(X=Y) \ge 1/q$ है।

2. कार्यप्रणाली (Methodology)

लेखक दर सीमा के व्युत्पन्न में एंट्रॉपी अधिकतमकरण चरण को अंतर वितरण (difference distribution) की पूर्ण फूरियर-विश्लेषणात्मक संरचना (full Fourier-analytic structure) का लाभ उठाकर परिष्कृत करते हैं।

A. अंतर का फूरियर प्रतिनिधित्व (Fourier Representation of the Difference)

मान लीजिए $X$ और $Y$ $\{0, \dots, q-1\}$ पर i.i.d. यादृच्छिक चर हैं जिनका प्रायिकता द्रव्यमान फलन (pmf) $p$ है। अंतर $D = X - Y$ का एक pmf $r$ है।

• $D$ का अभिलक्षण फलन (characteristic function) $\psi_D(\theta) = |\phi(\theta)|^2$ है, जहाँ $\phi(\theta)$, $X$ का अभिलक्षण फलन है।
• फलस्वरूप, $r$ का pmf $p$ का ऑटोकोरिलेशन (autocorrelation) है।
• आवृत्ति क्षेत्र (frequency domain) में, त्रिकोणमितीय बहुपद $R(\theta) = \sum r_k e^{ik\theta}$ को सभी $\theta \in [0, 2\pi]$ के लिए गैर-ऋणात्मक (non-negative) होना चाहिए क्योंकि यह $|\phi(\theta)|^2$ के बराबर है।

B. उत्तल अनुकूलन सूत्रीकरण (Convex Optimization Formulation)

शोध पत्र $H(D)$ को बांधने के लिए एक नया एंट्रॉपी अधिकतमकरण समस्या तैयार करता है:

• उद्देश्य: $H(r) = -\sum r_k \log r_k$ को अधिकतम करना।
• प्रतिबंध (Constraints):
  1. $r_k \ge 0$ और $\sum r_k = 1$ (एक वैध pmf)।
  2. $r_{-k} = r_k$ (सममिति/symmetry)।
  3. $r_0 = P(X=Y) \ge 1/q$ (टकराव प्रतिबंध)।
  4. नया प्रतिबंध: सभी $\theta$ के लिए $R(\theta) \ge 0$। यह सुनिश्चित करता है कि $r$ विशिष्ट सपोर्ट पर एक वैध ऑटोकोरिलेशन है।

C. टोप्लिट्ज सेमीडेफिनेट प्रोग्रामिंग (Toeplitz Semidefinite Programming - SDP)

$R(\theta) \ge 0$ का गैर-ऋणात्मकता प्रतिबंध एक अनंत परिवार के टोप्लिट्ज पॉजिटिव सेमीडेफिनेट (PSD) प्रतिबंधों के समतुल्य है।

• Fejér–Riesz प्रमेय और धनात्मक त्रिकोणमितीय बहुपदों के गुणों के माध्यम से, $R(\theta) \ge 0$ तभी होता है जब $r_k$ द्वारा निर्मित टोप्लिट्ज मैट्रिसेस $T^{(N)}(r)$ सभी $N \ge 1$ के लिए PSD हों।
• लेखक इस समस्या के एक ट्रंकेटेड (truncated) संस्करण को संख्यात्मक रूप से हल करते हैं, जिसमें $N \le N_{max}$ (विशेष रूप से $N_{max}=100$) के लिए $T^{(N)}(r) \succeq 0$ लागू किया जाता है। यह समस्या को एक मानक उत्तल अनुकूलन समस्या में बदल देता है जिसे SDP सॉल्वर के माध्यम से हल किया जा सकता है।

3. मुख्य योगदान (Key Contributions)

1. फूरियर-विश्लेषणात्मक विश्राम (Fourier-Analytic Relaxation): शोध पत्र i.i.d. अंतर वितरण के लिए एक विश्राम प्रस्तुत करता है जो इस तथ्य का उपयोग करता है कि इसका अभिलक्षण फलन $q-1$ की घात वाला एक गैर-ऋणात्मक त्रिकोणमितीय बहुपद है।
2. टोप्लिट्ज SDP के साथ समानता: यह स्पष्ट रूप से त्रिकोणमितीय बहुपद की गैर-ऋणात्मकता और टोप्लिट्ज मैट्रिसेस के एक अनंत परिवार की धनात्मक अर्ध-निश्चितता (positive semidefiniteness) के बीच समानता स्थापित करता है, जिससे इस समस्या को संख्यात्मक SDP के माध्यम से हल करना संभव हो जाता है।
3. बेहतर एंट्रॉपी सीमा: पूर्ण स्पेक्ट्रल धनात्मकता (केवल टकराव की प्रायिकता के बजाय) को लागू करके, शोध पत्र पिछले तरीकों की तुलना में $H(X-Y)$ पर स्पष्ट रूप से छोटा ऊपरी आलेख (upper bound) प्राप्त करता है।
4. नई दर सीमाएँ (New Rate Bounds): परिष्कृत एंट्रॉपी सीमा को प्रीफिक्स-सफिक्स विधि (जो $B_2$ कोड के लिए एक मानक तकनीक है) में डाला जाता है ताकि नए, अधिक सटीक अनंतस्पर्शी ऊपरी आलेख प्राप्त किए जा सकें।

4. परिणाम (Results)

लेखक $q \in \{9, 10, 11, 12, 13\}$ के लिए नए आलेख का संख्यात्मक मूल्यांकन करते हैं। परिणाम शोध पत्र की तालिका I में संक्षेपित हैं:

• तुलना: नए आलेख ($R_{new}^q$) निम्नलिखित के सर्वोत्तम ज्ञात आलेखों से स्पष्ट रूप से कम (अधिक सटीक) हैं:
  • लिंडस्ट्रॉम [3]
  • डेला फियोरे-दलाई [5] (लेखक का पिछला कार्य)
  • वांग [7]
• विशिष्ट सुधार:
  • $q=9$ के लिए, आलेख पिछले सर्वश्रेष्ठ $\approx 0.5615$ से घटकर 0.5579 हो जाता है।
  • $q=13$ के लिए, आलेख $\approx 0.5555$ से घटकर 0.5521 हो जाता है।
• अभिसरण (Convergence): जैसे-जैसे ट्रंकेशन पैरामीटर $N_{max}$ बढ़ता है, संख्यात्मक मान स्थिर होते जाते हैं, जो सन्निकटन (approximation) की वैधता की पुष्टि करते हैं।

5. महत्व (Significance)

• सैद्धांतिक प्रगति: यह कार्य प्रदर्शित करता है कि स्पेक्ट्रल फैक्टराइजेशन (spectral factorization) प्रतिबंध (अर्थात, यह मानना कि कोई भी गैर-ऋणात्मक त्रिकोणमितीय बहुपद एक वैध अंतर वितरण के अनुरूप है) को अनदेखा करने से ढीले (loose) आलेख प्राप्त होते हैं। टोप्लिट्ज PSD संरचना को लागू करने से यह पकड़ में आता है कि एक अनुक्रम (sequence) एक गैर-ऋणात्मक अनुक्रम के ऑटोकोरिलेशन के रूप में कैसे कार्य करता है, जिससे एंट्रॉपी सीमा काफी सुदृढ़ हो जाती है।
• पद्धतिगत प्रभाव: यह कॉम्बिनेटोरियल कोडिंग थ्योरी को हार्मोनिक विश्लेषण और उत्तल अनुकूलन (SDP) के साथ जोड़ता है। यह दृष्टिकोण अन्य कोड परिवारों के लिए सीमाओं को सुधारने का एक व्यवस्थित तरीका प्रदान करता है जहाँ समस्या को संरचित डिस्क्रीट अंतरों की एंट्रॉपी को नियंत्रित करने में बदला जा सकता है।
• भावी दिशाएँ: शोध पत्र सुझाव देता है कि मोमेंट बाधाओं (moment constraints) को जोड़कर या उच्च-क्रम के समसेट (जैसे $B_h$ कोड) तक पद्धति का विस्तार करके और अधिक कसाव (tightening) संभव है, हालांकि इससे हार्मोनिक-एनालिटिक बाधाओं की जटिलता बढ़ जाएगी।

संक्षेप में, यह शोध पत्र एक सरल संभाव्यता प्रतिबंध के स्थान पर एक परिष्कृत स्पेक्ट्रल धनात्मकता प्रतिबंध का उपयोग करके $B_2$ कोड के सैद्धांतिक सीमाओं को सुधारने के लिए एक कठोर गणितीय ढांचा प्रदान करता है, जिसे सेमीडेफिनेट प्रोग्रामिंग (SDP) के माध्यम से हल किया जा सकता है।