The Length of Functional Batch and PIR Codes

यहाँ अल्तान बी. किलिच, अल्बर्टो रावाग्नानी और फ्लेवियो सैलिसोनी के शोध पत्र "The Length of Functional Batch and PIR Codes" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण और संदर्भ

यह शोध पत्र एक निश्चित विमा ($k$) और एक निश्चित सूची आकार ($t$) के लिए किसी भी परिमित क्षेत्र (finite field) $\mathbb{F}_q$ पर फंक्शनल बैच (Functional Batch) और फंक्शनल PIR (Private Information Retrieval) कोड के लिए आवश्यक न्यूनतम लंबाई ($n$) निर्धारित करने की मौलिक समस्या को संबोधित करता है।

• पृष्ठभूमि: PIR कोड एक उपयोगकर्ता को कई विलगित रिकवरी सेटों (disjoint recovery sets) के माध्यम से एक विशिष्ट डेटा सिंबल प्राप्त करने की अनुमति देते हैं, जिससे गोपनीयता सुनिश्चित होती है। बैच कोड इस अवधारणा को कई अलग-अलग प्रतीकों को एक साथ प्राप्त करने के लिए विस्तारित करते हैं। फंक्शनल कोड इन अवधारणाओं को और आगे बढ़ाते हुए, केवल कच्चे प्रतीकों के बजाय संग्रहीत डेटा के फंक्शन्स (रैखिक संयोजन) को प्राप्त करने की अनुमति देते हैं।
• अंतराल (The Gap): इन कोडों पर पिछला शोध लगभग विशेष रूप से बाइनरी फील्ड ($q=2$) पर केंद्रित रहा है। गैर-बाइनरी क्षेत्रों ($q > 2$) पर इन कोडों का व्यवहार काफी हद तक अनछुआ रहा है।
• मुख्य अनुमान (Key Conjecture): एक केंद्रीय खुला प्रश्न फंक्शनल बैच अनुमान (Zhang, Etzion, and Yaakobi) है, जो यह प्रस्तावित करता है कि बाइनरी $[k, 2^k-1]$ सिम्प्लेक्स कोड एक $2^{k-1}$-फंक्शनल बैच कोड है। यह परिमित एबेलियन समूहों (finite abelian groups) में एक कॉम्बिनेटोरियल मैचिंग समस्या के समतुल्य है।
• उद्देश्य: लेखकों का लक्ष्य गैर-बाइनरी क्षेत्रों से परिणामों को सामान्यीकृत करना, विशिष्ट मापदंडों के लिए सटीक मानों की गणना करना, कड़े बाउंड्स (bounds) स्थापित करना और न्यूनतम लंबाई कार्यों $FP(k, t, q)$तथा$FB(k, t, q)$ के एसिम्प्टोटिक व्यवहार का विश्लेषण करना है।

2. कार्यप्रणाली और संकेतन (Methodology and Notation)

लेखक दो प्राथमिक फलन (functions) को परिभाषित करते हैं:

• $FP(k, t, q)$:$\mathbb{F}_q$पर एक$k$-आयामी$t$-फंक्शनल PIR कोड की न्यूनतम लंबाई।
• $FB(k, t, q)$:$\mathbb{F}_q$पर एक$k$-आयामी$t$-फंक्शनल बैच कोड की न्यूनतम लंबाई।

कार्यप्रणाली दृष्टिकोण:

1. कॉम्बिनेटोरियल निर्माण (Combinatorial Construction): लेखक जनरेटर मैट्रिसेस का निर्माण इस प्रकार करते हैं कि उनके कॉलम को प्रोजेक्टिव स्पेस $PG(k-1, q)$ में बिंदुओं के रूप में माना जाता है। वे विश्लेषण करते हैं कि इन बिंदुओं को विशिष्ट वेक्टर सूचियों (रिकवरी सेट्स) के रूप में कैसे विभाजित किया जा सकता है।
2. पैरिटी और काउंटिंग तर्क: वे कॉलमों की आवश्यक संख्या पर निचली सीमा (lower bounds) प्राप्त करने के लिए पिजनहोल सिद्धांत (pigeonhole principles) और पैरिटी विश्लेषण (सम और विषम $q$ के बीच अंतर करना) का उपयोग करते हैं।
3. उप-योग्यता (Subadditivity): वे $k$ और $t$ में उप-योग्यता के गुण का लाभ उठाते हैं ताकि छोटे मापदंडों से बड़े मापदंडों तक परिणामों का विस्तार किया जा सके।
4. समूह सिद्धांत (Group Theory): विशिष्ट बाउंड्स के लिए, वे विशिष्ट रिकवरी विभाजनों के अस्तित्व को सिद्ध करने के लिए परिमित एबेलियन समूहों (विशेष रूप से "सीटिंग कपल प्रॉब्लम" और हॉल के मैरिज थ्योरम के वेरिएंट) के परिणामों का उपयोग करते हैं।
5. एसिम्प्टोटिक विश्लेषण: वे $t \to \infty$ होने पर अनुपात $n/t$ के सीमा (limit) का अध्ययन करने के लिए फेकेटे के लेम्मा (Fekete's Lemma) को लागू करते हैं और जब $k$ और $t$ दोनों बढ़ते हैं तो विकास दर का विश्लेषण करते हैं।

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

A. विशिष्ट मापदंडों के लिए सटीक मान

• विमा $k=2$: लेखक किसी भी प्राइम पावर $q$ के लिए $FB(2, t, q)$ का एक क्लोज्ड-फॉर्म सूत्र व्युत्पन्न करते हैं:
  $$FB(2, t, q) = \left\lceil \frac{2(q+1)t}{q+2} \right\rceil = t + \left\lceil \frac{qt}{q+2} \right\rceil$$
  यह ज्ञात बाइनरी परिणाम ($q=2 \implies t + \lceil t/2 \rceil$) का सामान्यीकरण है।
• क्रिटिकल थ्रेशोल्ड के गुणज (Multiples of Critical Thresholds): वे ज्ञात बाइनरी परिणामों को मनमाने क्षेत्रों तक सामान्यीकृत करते हैं। विशेष रूप से, $FP(k, t, q)$के लिए, वे दिखाते हैं कि यदि$t$, $\frac{q^k+q-2}{2}$ का एक गुणज है, तो लंबाई सटीक रूप से $s(q^k-1)$ होगी।
  $$FP\left(k, s \cdot \frac{q^k+q-2}{2}, q\right) = s(q^k - 1)$$
  यह बाइनरी सिम्प्लेक्स कोड के गुण के "प्राकृतिक" सामान्यीकरण की पहचान करता है।

B. बाउंड्स और फील्ड साइज निर्भरता

• निचली सीमाएँ (Lower Bounds):
  • वे एक लॉगरिदमिक निचली सीमा स्थापित करते हैं: $FB(k, t, q) \geq \frac{tk}{\log_{q-1}(t(q-1)+1)}$।
  • वे सिद्ध करते हैं कि पर्याप्त बड़े $q$ के लिए (विशेष रूप से $q \geq \binom{kt}{k-1}$), लंबाई स्थिर होकर ट्रिवियल अपर बाउंड पर आ जाती है: $FB(k, t, q) = kt$।
• ऊपरी सीमाएँ (Upper Bounds):
  • वे एक निर्माण प्रदान करते हैं जो दिखाता है कि $FB(k, 2, 2) \leq \lceil 3k/2 \rceil$।
  • वे सिद्ध करते हैं कि विशिष्ट मामले $t = q^k + q - 2$ के लिए, लंबाई $2(q^k - 1) + (q-2)k$ द्वारा सीमित है। यह सुझाव देता है कि फंक्शनल बैच अनुमान गैर-बाइनरी क्षेत्रों के लिए $k$ में एक "लीनियर एरर टर्म" तक सही है।
• असममिति (Asymmetry): पेपर प्रदर्शित करता है कि सामान्य रूप से $FB(k, t, q) \neq FB(t, k, q)$ है। विशेष रूप से, बड़े $k$ के लिए, $FB(k, t, q)$वास्तव में$FB(t, k, q)$ से काफी छोटा हो सकता है, जो किसी भी सरल समरूपता अनुमान (symmetry conjecture) को खारिज करता है।

C. एसिम्प्टोटिक व्यवहार (Asymptotic Behavior)

लेखक मापदंडों के बढ़ने पर कोड के व्यवहार का विश्लेषण करते हैं:

1. निश्चित $k$, $t \to \infty$:
   लंबाई और सूची आकार के अनुपात की सीमा मौजूद है और दी गई है:
   $$\lim_{t \to \infty} \frac{FB(k, t, q)}{t} = \lim_{t \to \infty} \frac{FP(k, t, q)}{t} = \frac{2(q^k - 1)}{q^k + q - 2}$$
   यह परिणाम पुष्टि करता है कि फंक्शनल बैच कोड की एसिम्प्टोटिक दक्षता फंक्शनल PIR कोड के समान है, चाहे क्षेत्र का आकार कुछ भी हो।
2. एक साथ विकास ($k, t \to \infty$):
   जब विमा और सूची आकार दोनों बढ़ते हैं, तो लंबाई उप-द्विघाती (sub-quadratically) रूप से बढ़ती है। विशेष रूप से:
   $$\lim_{n \to \infty} \frac{FB(k_n, t_n, q)}{k_n t_n} = 0$$
   इसके अलावा, वे स्थापित करते हैं कि सामान्यीकृत लंबाई लॉगरिदमिक रूप से बढ़ती है:
   $$1 \leq \liminf_{n \to \infty} \frac{FP(k_n, t_n, q) \log_q(t_n)}{k_n t_n} \leq \limsup_{n \to \infty} \frac{FB(k_n, t_n, q) \log_q(t_n)}{k_n t_n} < 4$$

4. महत्व और निहितार्थ

• सिद्धांत का सामान्यीकरण: यह कार्य पहली बार व्यवस्थित रूप से मनमाने परिमित क्षेत्रों पर फंक्शनल बैच और PIR कोडों का उपचार करता है, जो बाइनरी प्रतिबंध से आगे बढ़ता है जो साहित्य पर हावी था।
• फंक्शनल बैच अनुमान में अंतर्दृष्टि: गैर-बाइनरी क्षेत्रों के लिए सटीक मान और बाउंड की गणना करके, यह पेपर सुझाव देता है कि $\mathbb{F}_q$ पर फंक्शनल बैच अनुमान के लिए "सही" सूची आकार संभवतः $\frac{q^k+q-2}{2}$ है (बाइनरी मामले में $2^{k-1}$ के बजाय)।
• व्यावहारिक भंडारण दक्षता: परिणाम वितरित भंडारण प्रणालियों (distributed storage systems) में निजी और बैच पुनर्प्राप्ति का समर्थन करने के लिए आवश्यक न्यूनतम भंडारण ओवरहेड ($n$) के लिए ठोस सूत्र प्रदान करते हैं, विशेष रूप से गैर-बाइनरी वर्णमालाओं (alphabets) के लिए जो आधुनिक भंडारण प्रौद्योगिकियों (जैसे फ्लैश मेमोरी, डीएनए स्टोरेज) में आम हैं।
• कॉम्बिनेटोरियल संबंध: यह पेपर कोडिंग थ्योरी को परिमित एबेलियन समूहों में कॉम्बिनेटोरियल समस्याओं के साथ जोड़ता है, विशेष रूप से कोड की लंबाई को विभाजन (partitioning) और मिलान (matching) समस्याओं से संबंधित करता है, जो दोनों क्षेत्रों के शोधकर्ताओं को नए उपकरण प्रदान करता है।

संक्षेप में, यह पेपर फंक्शनल बैच और PIR कोडों के लिए एक व्यापक सैद्धांतिक ढांचा प्रदान करता है, जिसमें कम विमाओं के लिए सटीक समाधान, सामान्य मापदंडों के लिए कड़े बाउंड्स, और मनमाने परिमित क्षेत्रों पर उनके एसिम्प्टोटिक व्यवहार का पूर्ण लक्षण वर्णन शामिल है।