Exact Formulas for Coprime Representations of Even Integers Avoiding a Prime

यहाँ एंड्रेस एम. सालाज़ार के शोध पत्र "Exact Formulas for Coprime Representations of Even Integers Avoiding a Prime" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र योज्य संख्या सिद्धांत (additive number theory) की एक शास्त्रीय समस्या को संबोधित करता है: एक सम पूर्णांक $2n$ को दो धनात्मक पूर्णांकों, $h + k = 2n$ (जहाँ $h \le k$) के योग के रूप में व्यक्त करने के तरीकों की गणना करना, जो सख्त सह-अभाज्य (coprimality) बाधाओं के अधीन हों।

विशेष रूप से, लेखक एक निश्चित अभाज्य $p \ge 5$ के लिए गणना फलन (counting function) $g(2n, p)$ को परिभाषित करते हैं:
$$g(2n, p) = \#\left\{ (h, k) \in \mathbb{Z}_{>0}^2 : h + k = 2n, \, h \le k, \, \gcd(h, 6p) = \gcd(k, 6p) = 1 \right\}$$
शर्त $\gcd(x, 6p) = 1$ का अर्थ है कि योगखंडों $h$ और $k$ को 2, 3, या $p$ से विभाज्य नहीं होना चाहिए।

चुनौती: ऐसे फलनों के लिए 'सीव विधियों' (sieve methods) या 'मोबियस व्युत्क्रमण' (Möbius inversion) का उपयोग करके साहसिक अनुमान (asymptotic estimates) प्राप्त किए जा सकते हैं, लेकिन पूर्णतः स्पष्ट, बंद-रूप सटीक सूत्र (fully explicit, closed-form exact formulas) प्राप्त करना कठिन है। मानक 'समावेशन-अपवर्जन' (inclusion-exclusion) विधियाँ विभाजकों पर वैकल्पिक योगों वाले खंडवार आवधिक व्यंजकों (piecewise periodic expressions) को जन्म देती हैं, जो गणना फलन की अंतर्निहित 'एफाइन संरचना' (affine structure) को अस्पष्ट कर देती हैं और बड़े $n$ के लिए गणनात्मक रूप से अक्षम होती हैं।

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

लेखक अवशेष अंकगणित (residue arithmetic) और यूक्लिडियन एल्गोरिदम (Euclidean algorithm) पर आधारित एक नवीन दृष्टिकोण विकसित करते हैं, जो पारंपरिक समावेशन-अपवर्जन योगों से बचता है। यह कार्यप्रणाली चार मुख्य चरणों में आगे बढ़ती है:

A. कैनोनिकल रिमाइंडर ऑपरेटर (Canonical Remainder Operator)

शोध पत्र एक कैनोनिकल रिमाइंडर ऑपरेटर $\delta_k(x) = x - k\lfloor x/k \rfloor$ का उपयोग करता है, जो पूर्णांकों को $\{0, \dots, k-1\}$ में मानक प्रतिनिधियों में मैप करता है। अवशेष बाधाओं को बीजगणितीय रूप से संभालने के लिए इस ऑपरेटर के प्रमुख गुणों (योग और गुणन के साथ अनुकूलता) को स्थापित किया गया है।

B. यूक्लिडियन एल्गोरिदम के माध्यम से न्यूनतम समाधान (Minimal Solutions via Euclidean Algorithm)

एक मुख्य तकनीकी योगदान रैखिक अवशेष समीकरणों के रूप में $\delta_k(a_0 x) = b_0$ (जहाँ $\gcd(a_0, k)=1$) के न्यूनतम समाधान के लिए एक स्पष्ट सूत्र का व्युत्पत्ति है।

• सीधे मॉड्यूलर व्युत्क्रमों (modular inverses) का उपयोग करने के बजाय, लेखक पूरे 'एक्सटेंडेड यूक्लिडियन एल्गोरिदम' को $\delta_k$ ऑपरेटर के पदों में व्यक्त करते हैं।
• प्रमेय 3.2 यूक्लिडियन एल्गोरिदम द्वारा उत्पन्न अनुक्रमों को शामिल करते हुए न्यूनतम समाधान $x$ के लिए एक बंद-रूप अभिव्यक्ति प्रदान करता है। यह विशिष्ट अवशेष वर्गों की सीधी गणना को बिना पुनरावृत्ति खोज (iterative search) के संभव बनाता है।

C. अवशेष वर्गों द्वारा अपघटन (Decomposition by Residue Classes)

समस्या को $n$ के modulo 3 के अवशेष के आधार पर विभाजित किया जाता है। चूंकि $h$ और $k$, 6 के सह-अभाज्य हैं, इसलिए उन्हें $6z+1$ या $6z+5$ के रूप में होना चाहिए।

• यदि $n \equiv 0 \pmod 3$: एक योगखंड $\equiv 1 \pmod 6$ है, दूसरा $\equiv 5 \pmod 6$ है।
• यदि $n \equiv 1 \pmod 3$: दोनों योगखंड $\equiv 1 \pmod 6$ हैं।
• यदि $n \equiv 2 \pmod 3$: दोनों योगखंड $\equiv 5 \pmod 6$ हैं।

यह समस्या को पूर्णांकों के युग्मों $(z_1, z_2)$ की गणना करने में बदल देता है ताकि $z_1 + z_2 = m(n)$ (जहाँ $m(n)$, $n$ का एक रैखिक फलन है) हो सके, जबकि $z_i$ विशिष्ट अवशेष वर्गों को टालने की शर्त का पालन करता हो।

D. अवशेष वर्गों का अपवर्जन (Exclusion of Residue Classes)

चरण B में व्युत्पन्न न्यूनतम समाधानों का उपयोग करते हुए, लेखक उन विशिष्ट अवशेष वर्गों की पहचान करते हैं जिन्हें $\gcd(h, 6p)=1$ की स्थिति को पूरा करने के लिए बाहर किया जाना चाहिए।

• मान लीजिए $a(p)$, $6x \equiv -1 \pmod p$ का न्यूनतम समाधान है।
• मान लीजिए $b(p)$, $6x \equiv -5 \pmod p$ का न्यूनतम समाधान है।
  गणना की समस्या फिर से एक सीमित अंतराल में युग्मों $(s, t)$ की गणना करने में बदल जाती है जो विशिष्ट अवशेषों $a(p)$ और $b(p)$ को टालते हुए एक लक्ष्य मान के योग के बराबर हों।

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

1. स्पष्ट बंद-रूप सूत्र (Theorem 4.13):
   शोध पत्र $g(2n, p)$ के लिए सटीक सूत्र प्रदान करता है जिसे निम्नलिखित के माध्यम से व्यक्त किया गया है:

   • कैनोनिकल रिमाइंडर ऑपरेटर $\delta_k$।
   • प्रारंभिक स्टेप फंक्शन्स (Heaviside-like indicators)।
   • न्यूनतम समाधान $a(p)$ और $b(p)$।
     ये सूत्र खंडवार एफाइन (piecewise affine) हैं, जिसका अर्थ है कि $g(2n, p)$, $n$ के अंकगणितीय प्रगतियों (arithmetic progressions) के साथ एक रैखिक फलन की तरह व्यवहार करता है जो $3p$ के अवशेषों द्वारा निर्धारित होते हैं।

2. एल्गोरिदम दक्षता (Algorithmic Efficiency):

   • पूर्व-गणना (Precomputation): $a(p)$ और $b(p)$ को यूक्लिडियन एल्गोरिदम का उपयोग करके $O(\log p)$ समय में संगणना किया जा सकता है।
   • मूल्यांकन (Evaluation): एक बार पूर्व-गणना होने के बाद, किसी भी $n$ के लिए $g(2n, p)$ का मूल्यांकन करने के लिए केवल $O(1)$ अंकगणितीय संचालन की आवश्यकता होती है।
   • तुलना: यह प्रत्यक्ष गणना (ब्रूट-फोर्स), जिसमें $O(n)$ संचालन की आवश्यकता होती है, की तुलना में एक महत्वपूर्ण सुधार है।

3. संरचनात्मक अंतर्दृष्टि (Structural Insight):
   यह कार्य प्रकट करता है कि गणना फलन केवल आवधिक नहीं है बल्कि इसमें एक खंडवार एफाइन संरचना (piecewise affine structure) है जो $3$और$p$ के अवशेषों के बीच परस्पर क्रिया द्वारा नियंत्रित होती है। यह संरचना व्युत्पन्न सूत्रों में स्पष्ट है, लेकिन मानक 'सीव-आधारित' अनुमानों में छिपी रहती है।

4. परिणाम और सत्यापन (Results and Validation)

• सैद्धांतिक परिणाम: प्रमेय 4.13 $\delta_3(n)$ के आधार पर दो मामलों में गणना प्रक्रिया को एकीकृत करता है, जो सभी सम पूर्णांकों $2n$ और अभाज्य $p \ge 5$ के लिए एक पूर्ण समाधान प्रदान करता है।
• संगणनात्मक सत्यापन:
  • सूत्रों को एक ब्रूट-फोर्स ओरेकल (brute-force oracle) के विरुद्ध लागू और परीक्षण किया गया।
  • दायरा: सभी सम पूर्णांक $2n \le 10^5$ और अभाज्य $p \in \{5, 7, 11, 13, 17, 19, 23\}$ के लिए मान्य किया गया।
  • परिणाम: पूर्ण सहमति (350,000 परीक्षण मामले) देखी गई, जो व्युत्पन्न सूत्रों की शुद्धता की पुष्टि करती है।
• दृश्यीकरण (Visualization): शोध पत्र में फलन की खंडवार एफाइन प्रकृति को दिखाने वाले ग्राफ शामिल हैं, जहाँ समानांतर रैखिक परिवार $n$ के अवशेष वर्गों के अनुरूप होते हैं।

5. महत्व (Significance)

• संगणनात्मक संख्या सिद्धांत (Computational Number Theory): शोध पत्र सह-अभाज्य निरूपणों की गणना के लिए एक अत्यधिक कुशल एल्गोरिदम प्रदान करता है, जो जटिलता को $n$ के रैखिक से बदलकर प्रति क्वेरी (query) स्थिर समय (constant time) में ले आता है (पूर्व-गणना के बाद)। यह उच्च-आवृत्ति वाले प्रश्नों या बड़े $n$ के लिए आवश्यक अनुप्रयोगों के लिए महत्वपूर्ण है।
• विश्लेषणात्मक स्पष्टता (Analytic Clarity): जटिल समावेशन-अपवर्जन योगों को स्पष्ट एफाइन सूत्रों से बदलकर, यह शोध पत्र समस्या की अंकगणितीय संरचना को स्पष्ट करता है, जिससे $n$ और $p$ पर इसकी निर्भरता पारदर्शी हो जाती है।
• सामान्यीकरण (Generalizability): लेखक उल्लेख करते हैं कि यह विधि कई अभाज्य संख्याओं $\{2, 3, p_1, \dots, p_k\}$ वाले अपवर्जन सेटों के लिए स्वाभाविक रूप से विस्तारित होती है, जो कई सह-अभाज्य बाधाओं वाले अधिक जटिल योज्य समस्याओं को हल करने का मार्ग सुझाती है।

संक्षेप में, सालाज़र का कार्य यूक्लिडियन एल्गोरिदम का लाभ उठाकर विशिष्ट लेकिन मौलिक समस्या के लिए कुशल, बंद-रूप अभिव्यक्तियों को व्युत्पन्न करके, साहसिक अनुमानों और सटीक गणना के बीच के अंतर को पाटता है।