On the $p$-adic Skolem Problem

तकनीकी सारांश: p-adic स्कोलेम समस्या पर

1. समस्या का विवरण
स्कोलेम समस्या (Skolem Problem) यह पूछती है कि क्या पूर्णांकों का एक दिया गया रैखिक पुनरावृत्ति अनुक्रम (linear recurrence sequence - LRS) शून्य पद रखता है। जबकि स्कोलेम-मालेक प्रमेय (Skolem-Mahler-Lech Theorem) (जो 90 वर्ष पहले सिद्ध किया गया था) यह स्थापित करता है कि एक गैर-अपभ्रंश (non-degenerate) LRS का शून्य सेट, परिमित सेट और परिमित अंकगणितीय प्रगति (arithmetic progressions) का मिश्रण होता है, इसका प्रमाण अप्रभावी (ineffective) है; यह एल्गोरिदम प्रदान नहीं करता है कि क्या ऐसा शून्य मौजूद है या नहीं। फलस्वरूप, स्कोलेम समस्या की निर्णयक्षमता (decidability) सैद्धांतिक कंप्यूटर विज्ञान में एक प्रमुख खुला प्रश्न बनी हुई है।

यह शोध पत्र इस समस्या के एक शिथिलन (relaxation) को संबोधित करता है: p-adic स्कोलेम समस्या। प्राकृतिक संख्याओं ($\mathbb{N}$) में शून्य खोजने के बजाय, लेखक जांच करते हैं कि क्या किसी दिए गए अभाज्य $p$ के लिए एक LRS, p-adic पूर्णांकों ($\mathbb{Z}_p$) के वलय (ring) में शून्य रखता है। इसके अलावा, वे संबंधित फलन समस्या (function problem) को भी संबोधित करते हैं: सभी ऐसे p-adic शून्यों के सटीक प्रतिनिधित्व की गणना करना। हालांकि p-adic संस्करण को हल करने से तुरंत मूल स्कोलेम समस्या हल नहीं होती है (क्योंकि p-adic शून्य पूर्णांक शून्य के अनुरूप नहीं हो सकते), लेखक प्रदर्शित करते हैं कि p-adic रूप से कार्य करना पूर्णांक शून्यों को खोजने के लिए एक व्यावहारिक दृष्टिकोण प्रदान करता है और मानक संख्या-सिद्धांतिक परिकल्पनाओं के तहत संबंधित समस्याओं के लिए निर्णयक्षमता परिणाम सक्षम करता है।

2. कार्यप्रणाली और एल्गोरिद्मिक ढांचा
मुख्य कार्यप्रणाली एक LRS $u = \langle u_n \rangle$ को एक सतत, विश्लेषणात्मक फलन $f: \mathbb{Z}_p \to \mathbb{Z}_p$ में विस्तारित करने पर आधारित है। यह p-adic अंतर्वेशन (p-adic interpolation) के माध्यम से प्राप्त किया जाता है:

• दिए गए विशेषता मूलों (characteristic roots) $\lambda_i$ वाले LRS के लिए, अनुक्रम को उप-अनुक्रमों $u_{Nn+\ell}$ (जहाँ $0 \le \ell < N$) में विभाजित किया जाता है जिन्हें p-adic घातांकीय (exponentials) और लघुगणक (logarithms)ों को शामिल करने वाले विश्लेषणात्मक फलनों $f_\ell(x)$ के रूप में दर्शाया जा सकता है।
• LRS के शून्यों को खोजने की समस्या इन विश्लेषणात्मक फलनों $f_\ell$ के $\mathbb{Z}_p$ के भीतर शून्यों को खोजने में बदल जाती है।

प्रस्तावित एल्गोरिदम सुनिश्चित करने के लिए कि प्रक्रिया समाप्त हो और सही रहे, दो अलग-अलग खोज रणनीतियों को जोड़ता है:

1. हेन्सेल लेम्मा खोज (Hensel's Lemma Search): एल्गोरिदम अवशेष वर्गों (residue classes) पर ब्रूट-फोर्स खोज करता है (बढ़ते हुए $r$ के लिए $p^r$ modulo)। यदि कोई अवशेष वर्ग एक सरल शून्य (जहाँ फलन का मान उसके व्युत्पन्न के मान के दोगुने से अधिक होता है) रखता है, तो हेन्सेल लेम्मा उस वर्ग में एक अद्वितीय शून्य की गारंटी देता है, जिसे मनचाही सटीकता तक अनुमानित किया जा सकता है।
2. परिमेय गणना (Rational Enumeration): एल्गोरिदम को बहु-शून्य (बहुलता $\ge 2$) के साथ एक चुनौती का सामना करना पड़ता है, जहाँ हेन्सेल की स्थिति कभी पूरी नहीं हो सकती, जिससे अनंत लूप (infinite loop) की स्थिति बन सकती है। इसे हल करने के लिए, लेखक p-adic शेन्युअल अनुमान (p-adic Schanuel Conjecture) से प्राप्त एक प्रमुख तकनीकी लेम्मा पर भरोसा करते हैं। यह लेम्मा सिद्ध करता है कि अपरिमेय घातांकीय बहुपदों (exponential polynomials) के लिए, $\ge 2$ की बहुलता वाला कोई भी सामान्य शून्य परिमेय (rational) होना चाहिए। फलस्वरूप, एल्गोरिदम इन बहु-शून्यों का पता लगाने के लिए परिमेय संख्याओं को सूचीबद्ध करने वाली एक समानांतर खोज चलाता है।

एल्गोरिदम सभी p-adic शून्यों का एक परिमित प्रतिनिधित्व ($\mathbb{Z}_p$ में डिस्क के रूप में) आउटपुट करता है और p-adic शेन्युअल अनुमान के अधीन समाप्त होता है।

3. मुख्य योगदान और सैद्धांतिक परिणाम
शोध पत्र निम्नलिखित मुख्य परिणाम प्रस्तुत करता है:

• p-adic स्कोलेम समस्या की निर्णयक्षमता: p-adic शेन्युअल अनुमान को मानते हुए, निर्णय समस्या $SP(\mathbb{Z}_p)$ (क्या p-adic शून्य मौजूद है?) निर्णय योग्य (decidable) है, और फलन समस्या $FSP(\mathbb{Z}_p)$ (सभी p-adic शून्यों की गणना करना) गणनीय (computable) है।
• बहु-शून्य पर तकनीकी लेम्मा: लेखक सिद्ध करते हैं कि यदि दो सह-अभाज्य (coprime) घातांकीय बहुपद एक साझा p-adic शून्य साझा करते हैं, तो वह शून्य परिमेय होना चाहिए (p-adic शेन्युअल अनुमान के तहत)। यह परिणाम एल्गोरिदम की समाप्ति सुनिश्चित करने के लिए महत्वपूर्ण है क्योंकि यह बहु-शून्यओं की खोज को परिमेय संख्याओं के सेट तक सीमित कर देता है।
• सिमल्टेनियस स्कोलेम समस्या की निर्णयक्षमता: उपरोक्त लेम्मा के प्रत्यक्ष अनुप्रयोग के रूप में, शोध पत्र सिद्ध करता है कि सिमल्टेनियस स्कोलेम समस्या (यह निर्धारित करना कि क्या दो सह-अभाज्य LRS एक सामान्य पूर्णांक शून्य साझा करते हैं) निर्णय योग्य है, फिर से p-adic शेन्युअल अनुमान को मानते हुए। यह एक नया LRS $w_n = v_n^2 + p u_n^2$ का निर्माण करके और उसके p-adic शून्यों का विश्लेषण करके प्राप्त किया गया है।
• कार्यान्वयन: लेखकों ने एल्गोरिदम को "स्कोलेम टूल" (SageMath के साथ एकीकृत) में लागू किया है। यह टूल उन मामलों को संभालता है जहाँ विशेषता बहुपद $\mathbb{Z}_p$ में विभाजित होता है।

4. प्रयोगात्मक परिणाम
लेखक क्रम 2 से 7 के यादृच्छिक रूप से उत्पन्न LRS का उपयोग करके प्रयोगों की रिपोर्ट करते हैं।

• केवल हेन्सेल एल्गोरिदम: एल्गोरिदम का एक सरलीकृत संस्करण, जो मानता है कि सभी शून्य सरल (बहुलता 1) हैं, ने 60-सेकंड के टाइमआउट के भीतर क्रम 4 तक लगभग 100% और क्रम 5 के लगभग 50% मामलों को सफलतापूर्वक हल किया।
• पूर्ण एल्गोरिदम: पूर्ण एल्गोरिदम, जिसमें परिमेय गणना चरण शामिल है, समान सफलता दर दिखाता है लेकिन इसमें रनटाइम अधिक है (क्रम 2-4 के लिए सरलीकृत संस्करण की तुलना में 1.3x से 1.5x धीमा)।
• अवलोकन: परीक्षण किए गए डेटासेट में, 1 से अधिक बहुलता वाले शून्य वाला कोई भी LRS नहीं पाया गया, जिससे पता चलता है कि ऐसे मामले व्यवहार में दुर्लभ हैं। टूल p-adic विस्तारों को परिमेय अनुमानों के साथ मिलान करके पूर्णांक और परिमेय शून्यों की प्रभावी ढंग से पहचान करता है।

5. महत्व और सीमाएँ
शोध पत्र का दावा है कि हालांकि प्रस्तावित एल्गोरिदम सामान्य स्कोलेम समस्या को हल नहीं करते हैं (क्योंकि वे हमेशा परिमेय और अपरिमेय p-adic शून्यों के बीच अंतर नहीं कर सकते, न ही यह गारंटी दे सकते हैं कि एक p-adic शून्य पूर्णांक शून्य के अनुरूप है), वे एक शक्तिशाली व्यावहारिक उपकरण प्रदान करते हैं।

• व्यावहारिक उपयोगिता: प्रस्तावित p-adic दृष्टिकोण LRS के पूर्णांक शून्यों को खोजने के लिए एक प्रभावी ह्यूरिस्टिक (heuristic) के रूप में कार्य करता है।
• सैद्धांतिक प्रगति: यह कार्य सिमल्टेनियस स्कोलेम समस्या के लिए एक सशर्त निर्णयक्षमता स्थापित करता है, जो LRS निर्णयक्षमता के व्यापक परिदृश्य में एक महत्वपूर्ण कदम है।
• सत्यता बनाम समाप्ति: लेखक इस बात पर जोर देते हैं कि एल्गोरिदम का आउटपुट अनिवार्य रूप से सही (unconditionally correct) होता है जब भी वह समाप्त होता है। p-adic शेन्युअल अनुमान का उपयोग केवल समाप्ति सुनिश्चित करने के लिए किया जाता है (यह सुनिश्चित करने के लिए कि परिमेय खोज सभी बहु-शून्यओं को पकड़ ले), न कि पहचाने गए शून्यों की सत्यता के लिए।

शोध पत्र निष्कर्ष निकालता है कि p-adic परिप्रेक्ष्य LRS शून्यों का विश्लेषण करने के लिए एक व्यवहार्य मार्ग प्रदान करता है, जो अप्रभावी सैद्धांतिक प्रमाणों और मानक संख्या-सिद्धांतिक धारणाओं के तहत प्रभावी कम्प्यूटेशनल विधियों के बीच के अंतर को पाटता है।