On the Frobenius Number and Genus of a Collection of Semigroups Generalizing Repunit Numerical Semigroups

यहाँ Liu, Xin, Ye, और Yin के शोध पत्र "On the Frobenius Number and Genus of a Collection of Semigroups Generalizing Repunit Numerical Semigroups" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र विशिष्ट परिवारों के संख्यात्मक अर्धसमूहों (numerical semigroups) के लिए फ़्रोबेनियस समस्या (Frobenius Problem) को संबोधित करता है। दिए गए अपेक्षाकृत अभाज्य धनात्मक पूर्णांकों के एक सेट $A = (a_1, a_2, \dots, a_n)$ के लिए, समस्या निम्नलिखित को निर्धारित करने का प्रयास करती है:

• फ़्रोबेनियस संख्या $F(A)$: वह सबसे बड़ा पूर्णांक जिसे $A$ के तत्वों के गैर-ऋणात्मक पूर्णांक रैखिक संयोजन (non-negative integer linear combination) के रूप में व्यक्त नहीं किया जा सकता है।
• जीनस (Genus) $g(A)$: उन धनात्मक पूर्णांकों की गणना जिन्हें इस प्रकार के संयोजन के रूप में व्यक्त नहीं किया जा सकता।
• स्यूडो-फ़्रोबेनियस संख्याएँ और प्रकार (Pseudo-Frobenius Numbers and Type): अर्धसमूह के पूरक (complement) में अधिकतम तत्वों का सेट, जो अर्धसमूह द्वारा प्रेरित आंशिक क्रम (partial order) के अंतर्गत आते हैं, और इस सेट की कार्डिनैलिटी (प्रकार)।

जबकि $n=2$ (सिल्वेस्टर का सूत्र) और विशिष्ट अनुक्रमों (अंकगणितीय प्रगति, ज्यामितीय अनुक्रम) के लिए सूत्र मौजूद हैं, $n \geq 3$ के लिए बंद-रूप समाधान (closed-form solutions) खोजना सामान्यतः NP-hard है। लेखक एक सामान्यीकृत संग्रह पर ध्यान केंद्रित करते हैं जो कई ज्ञात परिवारों, जिनमें रेपुनिट (Repunit), मर्सिन (Mersenne), थाबिट (Thabit), और प्रोथ (Proth) संख्यात्मक अर्धसमूह शामिल हैं, को एकीकृत और विस्तारित करता है।

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

लेखक एपरी सेट (Apéry set) और परिवर्तन-निर्माण समस्याओं (change-making problems) के लिए लालची एल्गोरिदम (greedy algorithms) पर आधारित एक एकीकृत दृष्टिकोण अपनाते हैं।

A. सामान्यीकृत संग्रह (Generalized Collection - GCNS)

शोध पत्र एक सामान्य संग्रह संख्यात्मक अर्धसमूह (Collection GCNS) को परिभाषित करता है, जो निम्नलिखित द्वारा जनित है:
$$A = (a, h_1a + db_1, h_2a + db_2, \dots, h_ka + db_k)$$
जहाँ:

• $a, k \in \mathbb{P}$ (धनात्मक पूर्णांक), $a, k \geq 2$।
• $d \in \mathbb{Z} \setminus \{0\}$ (यह धनात्मक या ऋणात्मक हो सकता है, जो एक प्रमुख नवाचार है)।
• $\gcd(a, d) = 1$।
• अनुक्रम $B = (b_1, \dots, b_k)$ और $H = (h_1, \dots, h_k)$ पुनरावर्ती संरचनाओं का पालन करते हैं:
  • $b_1 = 1$, $b_{i+1} = s_i b_i + 1$ जहाँ $s_i \geq s_{i-1}$।
  • $h_i = u b_i + 1$ किसी $u \in \mathbb{P}$ के लिए।

B. एपरी सेट और न्यूनीकरण (The Apéry Set and Minimization)

कार्यप्रणाली का मुख्य भाग $\langle A \rangle$ में $a$ के एपरी सेट, $\text{Ap}(\langle A \rangle, a)$, को कंप्यूट करने पर आधारित है। इस सेट के तत्व, $N_r$ (शेषफल $r \pmod a$ के अनुरूप सेट में सबसे छोटा तत्व), एक न्यूनीकरण समस्या से प्राप्त होते हैं:
$$OH_B(M) = \min \left\{ \sum_{i=1}^k h_i x_i \;\middle|\; \sum_{i=1}^k b_i x_i = M, \; x_i \in \mathbb{N} \right\}$$
लेखक सिद्ध करते हैं कि उनके विशिष्ट अनुक्रम $B$ के लिए, लालची एल्गोरिदम (greedy algorithm) इस न्यूनीकरण समस्या के लिए इष्टतम समाधान प्रदान करता है (अर्थात, अनुक्रम $B$ "orderly" है)। यह किसी भी पूर्णांक $M$ के लालची प्रस्तुतीकरण (greedy presentation) के स्पष्ट निर्माण की अनुमति देता है।

C. एकदिष्टता की स्थितियाँ (Monotonicity Conditions)

एक विशिष्ट तकनीकी योगदान उस स्थिति को स्थापित करना है जिसके तहत फलन $N_{dr}(m)$ (एक विशिष्ट अवशेष वर्ग के लिए एपरी सेट तत्व का प्रतिनिधित्व करने वाला) भागफल $m$ के संबंध में एकदिष्ट रूप से बढ़ता है।

• उन्होंने एक पर्याप्त स्थिति व्युत्पन्न की है: $ua + d + k - 2 \geq \sum_{i=1}^{k-1} s_i$।
• इस स्थिति के तहत, एपरी सेट में अधिकतम तत्व (जो फ़्रोबेनियस संख्या निर्धारित करता है) सबसे बड़े अवशेष $r = a-1$ पर होता है।

3. मुख्य योगदान और परिणाम (Key Contributions and Results)

A. Collection GCNS के लिए एकीकृत सूत्र

शोध पत्र विशिष्ट बाधाओं के तहत सामान्य Collection GCNS के लिए $F(A)$ और $g(A)$ के बंद-रूप सूत्र प्रदान करता है (थ्योरम 2.12 और 2.13):

• फ़्रोबेनियस संख्या:
  $$F(A) = \left( \sum_{i=1}^k x_i \right) a + (a-1)(ua + d) - a$$
  जहाँ $(x_1, \dots, x_k)$, $a-1$ का लालची प्रस्तुतीकरण है।
• जीनस:
  $$g(A) = \frac{1}{a} \sum_{r=1}^{a-1} \left( \sum_{i=1}^k x_i^{(r)} \right) + \frac{(a-1)(ua + d - 1)}{2}$$
  जहाँ $x_i^{(r)}$, $r$ के लालची प्रस्तुतीकरण के गुणांक हैं।

B. रेपुनिट अर्धसमूहों का सामान्यीकरण (Collection CNS)

लेखक अपने GCNS परिणामों को Collection CNS के लिए विशिष्ट करते हैं, जहाँ $b_i = \frac{b^i-1}{b-1}$ और $h_i = b^i$ है। इसमें शामिल हैं:

• रेपुनिट अर्धसमूह (Repunit Semigroups): $S(b, n)$।
• मर्सिन अर्धसमूह (Mersenne Semigroups): $b=2$ का मामला।
• थाबिट अर्धसमूह (Thabit Semigroups): विशिष्ट पैरामीटर चयन।
• प्रोथ अर्धसमूह (Proth Semigroups): एक खुले प्रश्न का आंशिक समाधान।

इन मामलों के लिए, वे $a, b, d, n$ मापदंडों पर निर्भर $F(A)$ और $g(A)$ के स्पष्ट बहुपद सूत्र व्युत्पन्न करते हैं।

C. प्रोथ संख्यात्मक अर्धसमूह ओपन प्रॉब्लम का आंशिक समाधान

यह शोध पत्र श्रीवास्तव और थक्कर के ओपन प्रॉब्लम 1.3 को संबोधित करता है, जो $\{m2^{n+i} + 1\}$ द्वारा जनित प्रोथ संख्यात्मक अर्धसमूह $P_m(n)$ से संबंधित है।

• चुनौती: पिछले कार्यों ने केवल $m = 2^r + 1$ के मामले को हल किया था। मनमाने विषम $m$ के लिए सामान्य मामला खुला था।
• परिणाम: लेखक $(2^r + q)2^n$ (जहाँ $m = 2^r + q$) के लालची प्रस्तुतीकरण का विश्लेषण करके $F(P_m(n))$ और $g(P_m(n))$ की गणना करने की विधि प्रदान करते हैं।
• निष्कर्ष: वे $q$ (विषम संख्याओं) के विशिष्ट रेंज के लिए स्पष्ट सूत्र प्रदान करते हैं और लालची प्रस्तुतीकरण तथा संबंधित थ्योरमों का विवरण देने वाली एक तालिका (तालिका 1) तैयार करते हैं, जिसमें $q < 50$ शामिल है। यह उक्त ओपन प्रॉब्लम का एक महत्वपूर्ण आंशिक समाधान है।

D. ऋणात्मक $d$ नवाचार (Negative $d$ Innovation)

एक उल्लेखनीय विशेषता यह है कि शोध पत्र ऋणात्मक पूर्णांकों के लिए $d$ की अनुमति देता है। यह Collection GCNS के अनुप्रयोग को उन अर्धसमूहों तक विस्तारित करता है जहाँ जनरेटर मानक अंकगणितीय अर्थों में सख्ती से बढ़ते हुए नहीं हैं, जिससे फ़्रोबेनियस समस्या के समाधानों का दायरा व्यापक हो जाता है।

4. महत्व (Significance)

1. एकीकरण: शोध पत्र ने कई अलग-अलग परिवारों (रेपुनिट, मर्सिन, थाबिट, प्रोथ) के अध्ययन को एक एकल सैद्धांतिक ढांचे (Collection GCNS) के तहत सफलतापूर्वक एकीकृत किया है।
2. एल्गोरिद्मिक दक्षता: अपने अंतर्निहित अनुक्रमों के "orderly" होने को सिद्ध करके, लेखक जटिल फ़्रोबेनियस समस्या को एक सरल लालची एल्गोरिदम (greedy algorithm) में बदल देते हैं, जिससे कम्प्यूटेशनल गणना के बजाय स्पष्ट सूत्रों का निष्कर्षण संभव होता है।
3. ओपन प्रॉब्लम्स पर प्रगति: यह कार्य प्रोथ संख्यात्मक अर्धसमूह समस्या पर ठोस प्रगति करता है, जो $m = 2^r + 1$ के विशिष्ट मामले से आगे बढ़कर विषम पूर्णांकों के एक व्यापक वर्ग तक पहुँचता है।
4. सामान्यीकरण: इसकी कार्यप्रणाली ऋणात्मक $d$ के मामलों तक भी विस्तृत है, जो उन संख्यात्मक अर्धसमूहों की संरचना के बारे में नई अंतर्दृष्टि प्रदान करती है जिनका विश्लेषण पहले कठिन था।

संक्षेप में, यह शोध पत्र संख्यात्मक अर्धसमूहों के एक विस्तृत वर्ग के लिए फ़्रोबेनियस समस्या को हल करने के लिए एक शक्तिशाली, एकीकृत बीजगणितीय उपकरणसेट प्रदान करता है, जो उन इनवेरियंट्स (invariants) के लिए स्पष्ट सूत्र प्रदान करता है जो पहले अज्ञात थे या केवल विशिष्ट उप-मामलों के लिए गणनीय थे।