Gaps of Binary Numerical Semigroups and of Binary Inclusion-Exclusion Polynomials

तकनीकी सारांश: बाइनरी संख्यात्मक अर्धसमूहों (Binary Numerical Semigroups) और बाइनरी समावेश-अपवर्जन बहुपदों (Binary Inclusion-Exclusion Polynomials) के अंतराल (Gaps)

समस्या विवरण
यह कार्य बाइनरी समावेश-अपवर्जन बहुपदों, जिन्हें $Q_{\{p,q\}}(x)$ द्वारा दर्शाया गया है, के "गैपसेट्स" (gapsets) के संरचनात्मक गुणों और संबद्ध बाइनरी संख्यात्मक अर्धसमूह $\langle p, q \rangle$ में क्रमिक तत्वों के बीच की दूरियों को संबोधित करता है। बहुपद को इस प्रकार परिभाषित किया गया है:
$$Q_{\{p,q\}}(x) := \frac{(1-x^{pq})(1-x)}{(1-x^p)(1-x^q)}$$
जहाँ $p$ और $q$ सह-अभाज्य (coprime) पूर्णांक हैं और $q \ge p \ge 3$ है। जब $p$ और $q$ अभाज्य होते हैं, तो Q_{\{p,q}}, साइक्लोटोमिक बहुपद $\Phi_{pq}$ में परिवर्तित हो जाता है।

बहुपद का गैपसेट $G(f)$, क्रमिक गैर-शून्य गुणांकों के घातांकों के बीच के अंतरों के सेट को दर्शाता है। पिछले शोध (जैसे, होंग एट अल., झांग, कैफ्यूरे और सेसरैटो) ने विशिष्ट स्थितियों (जैसे, $q \equiv \pm 1 \pmod p$) के तहत $\Phi_{pq}$ के सबसे बड़े अंतरालों के लिए विशिष्ट परिणाम स्थापित किए थे, लेकिन सामान्य बाइनरी मामले के लिए संपूर्ण गैपसेट का पूर्ण विवरण एक खुला प्रश्न बना हुआ था। यह शोध भी बाइनरी संख्यात्मक अर्धसमूह $\langle p, q \rangle = \{ iq + jp \mid i, j \ge 0 \}$ में क्रमिक तत्वों के बीच सभी संभावित दूरियों के सेट को चित्रित करने का प्रयास करता है।

कार्यप्रणाली (Methodology)
इस शोध का मुख्य तकनीकी योगदान अवशेष प्रणालियों (residue systems) के रैखिक क्रमपरिवर्तन (linear permutations) के एक विशिष्ट गुण का विश्लेषण है। मान लीजिए $p$ एक मापांक (modulus) है और $u$ एक पूर्णांक है जो $p$ के साथ सह-अभाज्य है। क्रमपरिवर्तन $n \mapsto \langle un \rangle_p$ द्वारा दिया जाता है, जहाँ $\langle x \rangle_p$ का अर्थ $x$ का $p$ के सापेक्ष न्यूनतम गैर-ऋणात्मक अवशेष है।

लेखक एक "डोमिनेंट पेयर" (dominant pair) $(a, b)$ को $a < b$ के रूप में परिभाषित करते हैं जो निम्नलिखित दो में से एक असमानता को संतुष्ट करता है:

1. $\max(\langle ua \rangle_p, \langle ub \rangle_p) < \min_{a < n < b} \langle un \rangle_p$
2. $\min(\langle ua \rangle_p, \langle ub \rangle_p) > \max_{a < n < b} \langle un \rangle_p$

इन जोड़ों का विश्लेषण करने के लिए, शोध पत्र $p$ और $u$ के गुणात्मक व्युत्क्रम (multiplicative inverse, जिसे $r_1$ कहा जाता है) पर लागू यूक्लिडियन एल्गोरिदम से प्राप्त $p$ के अवशेष तंत्र के एक प्रतिनिधित्व को प्रस्तुत करता है। यूक्लिडियन एल्गोरिदम अनुक्रमों $(r_i)$ और $(Z_i)$ को $r_{i-1} = Z_i r_i + r_{i+1}$ के माध्यम से उत्पन्न करता है।

लेखक किसी भी पूर्णांक $n \in [0, p)$ के लिए एक विशिष्ट प्रतिनिधित्व $n = R(z) = \sum z_i (-1)^{i-1} r_i$ का निर्माण करते हैं, जहाँ $z$ गुणांकों का एक टुपल (tuple) है जो यूक्लिडियन एल्गोरिदम के मापदंडों द्वारा प्रतिबंधित है। यह प्रतिनिधित्व $\langle un \rangle_p$ का उसके गुणांकों $z_i$ के संदर्भ में स्पष्ट मूल्यांकन करने की अनुमति देता है।

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

1. डोमिनेंट पेयर्स का अभिलक्षण (Characterization of Dominant Pairs):
   शोध पत्र यह सिद्ध करता है कि डोमिनेंट पेयर्स के अंतरों $\{b-a\}$ का सेट ठीक वही है:
   $$D_\Delta(p, u) = \{ r_{i-1} - z r_i \mid 0 \le z \le Z_i - 1, \ 1 \le i \le t \}$$
   जहाँ $t$ यूक्लिडियन एल्गोरिदम के चरणों की संख्या है। यह परिणाम संभव अंतरों को यूक्लिडियन अनुक्रम के इंडेक्स $i$ के आधार पर सेटों $D_i$ में विभाजित करता है।

2. संख्यात्मक अर्धसमूहों के गैपसेट्स (Gapsets of Numerical Semigroups):
   $u$ को $p$ के मॉड्यूल में $q$ के गुणात्मक व्युत्क्रम के रूप में सेट करके, लेखक डोमिनेंट पेयर्स को संख्यात्मक अर्धसमूह $\langle p, q \rangle$ से जोड़ते हैं।

• मान लीजिए $S(p, q)$ अंतराल $[0, (p-1)(q-1)]$ में प्रतिनिधित्व योग्य पूर्णांकों का सेट है और $N(p, q)$ गैर-प्रतिनिधित्व योग्य पूर्णांकों का सेट है।
• क्रमिक प्रतिनिधित्व योग्य पूर्णांकों और क्रमिक गैर-प्रतिनिधित्व योग्य पूर्णांकों के बीच की दूरियों का सेट, $S_\Delta(p, q) = \{ \ell_{j+1} - \ell_j \}$, और $N_\Delta(p, q) = \{ n_{j+1} - n_j \}$, पूरी तरह से वर्णित है।
• प्रमेय 1: $S_\Delta(p, q) = N_\Delta(p, q)$ है, सिवाय इसके कि यदि $q = p+1$, तो $S_\Delta(p, q) = N_\Delta(p, q) \cup \{2\}$ होगा। दोनों सेट $D_\Delta(p, x_1)$ के समान हैं, जहाँ $x_1 \equiv q^{-1} \pmod p$।

3. बाइनरी समावेश-अपवर्जन बहुपदों के गैपसेट्स:
   शोध पत्र स्थापित करता है कि बहुपद $Q_{\{p,q\}}$ के अंतराल क्रमिक प्रतिनिधित्व योग्य या गैर-प्रतिनिधित्व योग्य पूर्णांकों के ब्लॉकों की लंबाई के अनुरूप होते हैं। विशेष रूप से, गैपसेट $G(p, q)$ को इस प्रकार दिया गया है:
   $$G(p, q) = \{ \ell_{j+1} - \ell_j - 1 \mid \ell_{j+1} > \ell_j + 1 \}$$
   प्रमेय 2: गैपसेट सेटों के संघ (union) $G_i$ का संघ है:
   $$G(p, q) = \bigcup_{i=1}^t G_i, \quad \text{जहाँ } G_i = \{ r_{i-1} - z r_i - 1 \mid 0 \le z \le Z_i - 1 \}$$
   (अंतिम सेट $G_t$ के लिए थोड़े संशोधन के साथ)। यह सभी संभावित अंतरालों का एक पूर्ण, रचनात्मक विवरण प्रदान करता है।

4. गैपसेट्स की संख्या पर सीमाएँ (Bounds on the Number of Gaps):
   प्रमेय 3: शोध पत्र गैपसेट की कार्डिनैलिटी (cardinality), $\#G(p, q)$ पर तीक्ष्ण सीमाएँ प्रदान करता है।

• ऊपरी सीमा: $\#G(p, q) \le p - 1$।
• निचली सीमा: $\#G(p, q) \ge k$, जहाँ $k$ को $F_k < p \le F_{k+1}$ ($F_k$ फाइबोनैकी संख्याएँ) द्वारा परिभाषित किया गया है।
  लेखक उल्लेख करते हैं कि यह निहितार्थ है कि $\#G(p, q) > c \log p$ है, जहाँ $c$ एक स्थिरांक है।

महत्व और दावे
शोध पत्र का दावा है कि यह बाइनरी समावेश-अपवर्जन बहुपदों के वर्ग के लिए गैपसेट्स का "पूर्ण विवरण" प्रदान करता है, जो पिछले परिणामों का सामान्यीकरण करता है जो विशिष्ट मामलों (जैसे, $q \equiv \pm 1 \pmod p$) या विशिष्ट अंतरालों (जैसे, सबसे बड़ा या दूसरा सबसे बड़ा) तक सीमित थे।

प्राथमिक महत्व अवशेष प्रणालियों के रैखिक क्रमपरिवर्तन के विश्लेषण में बाइनरी साइक्लोटोमिक बहुपदों के गैप समस्या को कम करने में निहित है। लेखक यूक्लिडियन एल्गोरिदम पर आधारित अवशेष प्रणाली का एक प्रतिनिधित्व प्रस्तुत करते हैं जो डोमिनेंट पेयर्स की शर्तों को "काफी पारदर्शी" बनाता है। शोध पत्र यह भी तर्क देता है कि यह प्रतिनिधित्व स्वतंत्र रुचि का है और भविष्य में अन्य क्षेत्रों में इसके अनुप्रयोग हो सकते हैं, हालांकि यह उन्हें निर्दिष्ट नहीं करता है।

ये परिणाम बाइनरी साइक्लोटोमिक बहुपदों और बाइनरी संख्यात्मक अर्धसमूहों में अंतरालों की समझ को एकीकृत करते हैं, यह दिखाते हुए कि अर्धसमूह में क्रमिक तत्वों के बीच की दूरियों का सेट संबद्ध रैखिक क्रमपरिवर्तन के डोमिनेंट पेयर्स के अंतरों के सेट के समान है। कार्य इन गैपसेट्स की जटिलता को भी मापता है, यह दिखाते हुए कि गैपसेट्स की संख्या $p$ के मामले में (फाइबोनैकी इनपुट) $\log p$ के साथ लघुगणकीय (logarithmically) रूप से बढ़ती है और सर्वोत्तम मामले में $p$ द्वारा रैखिक रूप से सीमित होती है।