💻 computer science

On existential Büchi arithmetic in two coprime bases

यह शोध पत्र दो सह-अभाज्य आधारों (coprime bases) के लिए बुची प्रेडिकेट्स (Büchi predicates) के साथ विस्तारित प्रेस्टर अरिथमेटिक (Presburger arithmetic) के अस्तित्व संबंधी खंड (existential fragment) की निर्णयक्षमता (decidability) को क्वांटिफायर-एलिमिनेशन तर्क प्रदान करके स्थापित करता है।

मूल लेखक: Joris Nieuwveld

प्रकाशित 2026-08-26

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Joris Nieuwveld

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

गणित लंबे समय से उन नियमों से आकर्षित रहा है जो संख्याओं को नियंत्रित करते हैं, विशेष रूप से यह कि हम उन्हें जोड़ और क्रम जैसे सरल ऑपरेशनों का उपयोग करके कैसे वर्णित कर सकते हैं। लगभग एक सदी से, प्रेसबर अंकगणित (Presburger arithmetic) के रूप में ज्ञात एक प्रणाली इस कार्य के लिए एक विश्वसनीय आधार के रूप में कार्य कर रही है। यह हमें केवल जोड़ और "कम है" की अवधारणा का उपयोग करके पूर्णांकों के बारे में प्रश्न पूछने की अनुमति देता है, और 1929 में विकसित एक पद्धति के कारण, हम जानते हैं कि इस प्रणाली के भीतर पूछे गए किसी भी प्रश्न का उत्तर 'हाँ' या 'नहीं' में दिया जा सकता है। हालाँकि, यह प्रणाली सीमित है; यह गुणा को नहीं संभाल सकती, जो अंकगणित की पूर्ण जटिलता को खोलने वाली कुंजी है। जब गुणा को जोड़ा जाता है, तो प्रणाली इतनी शक्तिशाली हो जाती है कि कोई भी एल्गोरिदम हर संभव प्रश्न का उत्तर देने की गारंटी नहीं दे सकता।

जोड़ की सरल दुनिया और गुणा की जटिल दुनिया के बीच के अंतर को पाटने के लिए, शोधकर्ताओं ने इस प्रणाली में कुछ विशिष्ट, सीमित उपकरणों को जोड़ने की खोज की है। ऐसा एक उपकरण एक प्रेडिकेट (predicate) है जो किसी विशिष्ट संख्या की उस सबसे बड़ी घात (power) की पहचान करता है जो किसी अन्य संख्या को विभाजित करती है। उदाहरण के लिए, यदि हम संख्या 12 को देखते हैं, तो 2 की सबसे बड़ी घात जो इसे विभाजित करती है वह 4 है, जबकि 3 की सबसे बड़ी घात 3 है। यह उपकरण, जिसे अक्सर बुची प्रेडिकेट (Buchì predicate) कहा जाता है, हमें पूर्ण रूप से गुणा को पेश किए बिना संख्याओं की घातों के बारे में बात करने की अनुमति देता है। दशकों से केंद्रीय प्रश्न यह रहा है कि जब हम एक साथ दो ऐसे उपकरणों का उपयोग करने का प्रयास करते हैं, विशेष रूप से दो अलग-अलग आधार संख्याओं के लिए जो एक सरल गुणात्मक संबंध साझा नहीं करते हैं, तो क्या होता है। यदि हम दो अलग-अलग आधारों की घातों का एक साथ उपयोग करके संख्याओं का वर्णन करने का प्रयास करते हैं, तो क्या प्रणाली हल करने योग्य बनी रहती है, या यह पूर्ण गुणा की अनसुलझी अराजकता में ढह जाती है?

ऑक्सफोर्ड विश्वविद्यालय के एक शोधकर्ता, जोरिस न्यूवेल्ड (Joris Nieuwveld) ने अब इस समस्या के एक विशिष्ट और महत्वपूर्ण मामले के लिए एक निर्णायक उत्तर प्रदान किया है। यह अध्ययन दो ऐसी आधार संख्याओं पर केंद्रित है जो सह-अभाज्य (coprime) हैं, जिसका अर्थ है कि उनका एक के अलावा कोई अन्य सामान्य गुणनखंड नहीं है, जैसे कि 2 और 3। जबकि पिछले कार्यों ने दिखाया था कि दो ऐसे आधारों का उपयोग करना आम तौर पर प्रणाली को अनिर्णय योग्य (undecidable) बना देता है, न्यूवेल्ड ने प्रदर्शित किया कि यदि हम अपने प्रश्नों को एक विशिष्ट, सरल रूप तक सीमित रखते हैं—केवल यह पूछना कि क्या कोई समाधान मौजूद है बिना सभी संभावित समाधानों का पूर्ण विवरण मांगे—तो प्रणाली हल करने योग्य बनी रहती है। शोधपत्र सिद्ध करता है कि इन सह-अभाज्य आधारों के लिए, एक विश्वसनीय विधि है जिससे यह निर्धारित किया जा सके कि दिया गया कथन सत्य है या असत्य, जिससे प्रभावी रूप से एक ऐसी समस्या को नियंत्रित किया जा सका जिसे पहले इस विशिष्ट विन्यास में असाध्य माना जाता था।

इस खोज का मार्ग घातांकीय वृद्धि (exponential growth) और मॉडुलर बाधाओं के परिदृश्य को पार करते हुए तय किया गया। शोधकर्ता ने जटिल तार्किक प्रश्नों को असमानताओं और मॉडुलर समीकरणों की एक प्रणाली में अनुवादित करके शुरुआत की, जिसमें दोनों आधारों की घातों को शामिल किया गया। इन घातों की कल्पना उन चरों (variables) के रूप में करें जो अविश्वसनीय रूप से बड़े हो सकते हैं, और समीकरण उन नियमों के रूप में जो यह निर्धारित करते हैं कि वे एक-दूसरे से कैसे संबंधित हैं। चुनौती यह निर्धारित करना था कि क्या इन संख्याओं का कोई संयोजन है जो सभी नियमों को एक साथ संतुष्ट करता है। इस दृष्टिकोण में समस्या को प्रबंधनीय परतों में तोड़ना, चरों को उनके आकार के आधार पर समूहों में विभाजित करना शामिल था। इन परतों की संरचना का विश्लेषण करके, शोधकर्ता यह पहचान सके कि कौन से चर एक दूसरे से मजबूती से बंधे हुए थे और कौन से स्वतंत्र रूप से भिन्न हो सकते थे।

समाधान का एक महत्वपूर्ण हिस्सा अन्य संख्याओं की घातों द्वारा विभाजित होने पर संख्याएँ कैसे व्यवहार करती हैं, इसकी गहरी समझ पर आधारित था। शोधपत्र संख्या सिद्धांत (number theory) के एक शक्तिशाली प्रमेय का उपयोग यह दिखाने के लिए करता है कि कुछ शर्तों के तहत, इन घातों के शेषफल (remainders) अनुमानित पैटर्न का पालन करते हैं। इस पूर्वानुमेयता ने शोधकर्ता को समस्या को महत्वपूर्ण रूप से सरल बनाने की अनुमति दी। प्रत्येक संख्या के लिए समाधान खोजने के बजाय, पद्धति ने अनंत संभावनाओं को मामलों के एक परिमित सेट (finite set) में बदल दिया जिसे जांचा जा सकता था। प्रमाण ने दिखाया कि यदि आधार सह-अभाज्य हैं, तो उनकी घातों के बीच की अंतःक्रियाएं इतनी सीमित होती हैं कि वे प्रणाली को हल करने के लिए बहुत अधिक अराजक होने से रोकती हैं।

परिणाम निर्णायता (decidability) की सीमाओं का एक महत्वपूर्ण स्पष्टीकरण है। यह पुष्टि करता है कि जबकि दो बुची प्रेडिकेट जोड़ना आम तौर पर एक अनसुलझी प्रणाली की ओर ले जाता है, अस्तित्वगत खंड (existential fragment)—वह भाग जो केवल एक समाधान के अस्तित्व के बारे में पूछता है—सह-अभाज्य आधारों के लिए निर्णाय योग्य रहता है। यह खोज इस विशिष्ट मामले के लिए एक लंबे समय से चले आ रहे खुले प्रश्न को सुलझाती है। शोधपत्र यह दावा नहीं करता है कि उसने सभी संभावित आधार युग्मों के लिए समस्या को हल कर लिया है, विशेष रूप से वे जो सह-अभाज्य नहीं हैं, जहाँ शेषफलों का व्यवहार बहुत अधिक अनियमित हो जाता है और वर्तमान विधियाँ लागू नहीं होती हैं। हालाँकि, सह-अभाज्य मामले के लिए, यह कार्य एक पूर्ण और कठोर प्रमाण प्रदान करता है कि एक निर्णय प्रक्रिया मौजूद है।

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

तकनीकी सारांश: दो सह-अभाज्य आधारों (Coprime Bases) में अस्तित्वपरक बुची अंकगणित (Existential Büchi Arithmetic) पर

समस्या विवरण
यह शोध पत्र पूर्णांकों पर प्रथम-क्रम तर्क (first-order logic) के अस्तित्वपरक खंड (existential fragment) की निर्णयक्षमता (decidability) को संबोधित करता है, जिसे क्रम (order), योग (addition), और दो बुची प्रेडिकेट्स (Büchi predicates) के साथ विस्तारित किया गया है, जिसे $\exists\text{FO}(\mathbb{Z}; <, +, V_\alpha, V_\beta)$ के रूप में दर्शाया गया है। यहाँ $V_z(x, y)$ तब सत्य होता है जब $y$ , $z$ की उस सबसे बड़ी घात (power) को दर्शाता है जो $x$ को विभाजित करती है।

संदर्भ विलेमेयर (Villemaire, 1992) द्वारा स्थापित किया गया है, जिन्होंने सिद्ध किया था कि जब $\alpha$ और $\beta$ गुणात्मक रूप से स्वतंत्र (multiplicatively independent) होते हैं, तो पूर्ण प्रथम-क्रम सिद्धांत $\text{FO}(\mathbb{Z}; <, +, V_\alpha, V_\beta)$ अनिर्णायक (undecidable) होता है, क्योंकि यह संरचना गुणन (multiplication) को एनकोड कर सकती है। बाद के शोध ने हिरोनिमी और शुल्ज़ (Hieronymi and Schulz, 2021) द्वारा दिखाया कि बुची प्रेडिकेट्स को कमजोर पावर प्रेडिकेट्स ( $\alpha^\mathbb{N}, \alpha^\mathbb{N}$ ) से बदलने पर भी अनिश्चित सिद्धांत प्राप्त होता है। हालाँकि, करीमोव आदि (Karimov et al., 2025) ने प्रदर्शित किया कि गुणात्मक रूप से स्वतंत्र आधारों के लिए पावर प्रेडिकेट्स के साथ सिद्धांत का अस्तित्वपरक खंड निर्णायक है।

इस शोध पत्र द्वारा संबोधित खुला प्रश्न यह है कि क्या अस्तित्वपरक खंड तब भी निर्णायक रहता है जब प्रेडिकेट्स सरल पावर सेट्स के बजाय अधिक सशक्त बुची प्रेडिकेट्स ( $V_\alpha, V_\beta$ ) हों। लेखक इस प्रश्न को विशेष रूप से तब हल करते हैं जब आधार $\alpha$ और $\beta$ सह-अभाज्य (coprime) होते हैं।

कार्यप्रणाली (Methodology)
प्रमाण एक क्वांटिफायर-एलिमिनेशन (quantifier-elimination) तर्क के माध्यम से आगे बढ़ता है जो एक अस्तित्वपरक सूत्र को रैखिक असमानताओं (linear inequalities) और मॉड्यूलर बाधाओं (modular constraints) की एक प्रणाली में परिवर्तित करता है जिसमें $\alpha$ और $\beta$ की घातें शामिल होती हैं। कार्यप्रणाली कई प्रमुख गणितीय उपकरणों और संरचनात्मक न्यूनीकरणों (structural reductions) पर निर्भर करती है:

असमानताओं की प्रणाली में न्यूनीकरण:
लेखक पहले अस्तित्वपरक सूत्र को "शुद्ध पावर वेरिएबल्स" ( $z^n$ ) और "रैखिक पावर वेरिएबल्स" ( $x \cdot z^n$ ) वाली एक प्रणाली में कम करते हैं। यह प्रणाली रैखिक असमानताओं ( $Ax > v$ ) और मॉड्यूलर बाधाओं से बनी होती है, जिनमें से कुछ स्थिर मापांक (constant moduli) के साथ हैं और अन्य परिवर्तनशील मापांक (variable moduli) के साथ (रूप $d \cdot z^n$ में)।
संरचनात्मक अपघटन (स्तर और बॉटम फैमिली):
वेरिएबल्स की जटिलता को प्रबंधित करने के लिए, लेखक वेरिएबल्स को उनके सापेक्ष परिमाणों के आधार पर "स्तरों" (levels) में विभाजित करते हैं। एक ही स्तर के वेरिएबल्स के बीच अनुपात एक स्थिरांक द्वारा सीमित होता है, जबकि अलग-अलग स्तरों के वेरिएबल्स के बीच अनुपात अनिश्चित रूप से बड़े हो सकते हैं।

स्तर (Levels): बहुभुज (polyhedron) $Ax > v$ के रिसेशन कोन (recession cone) के माध्यम से परिभाषित।
बॉटम फैमिली (Bottom Family): वेरिएबल्स का एक उपसमुच्चय (विशेष रूप से वे जिनमें "छोटे गुणांक" हैं) जिन्हें एक साथ माना जाता है। लेखक एक "बॉटम फैमिली" को इस प्रकार परिभाषित करते हैं कि इन वेरिएबल्स पर बहुभुज का प्रक्षेप (projection) "पतला" (thin) नहीं है (अर्थात, एक विशिष्ट रैखिक दिशा में सीमित नहीं है)।

पुनरावृत्ति न्यूनीकरण और सामान्यीकरण (Iterative Reduction and Normalization):
एल्गोरिदम का मुख्य भाग एक विशिष्ट गुणों की सूची (गुण 1–4c) को संतुष्ट करने के लिए प्रणाली को कम करने में निहित है। ये गुण सुनिश्चित करते हैं:

वेरिएबल्स क्रमबद्ध हैं ( $x_1 > \dots > x_t > 0$ )।
बहुभुज पतला नहीं है।
परिवर्तनशील मापांक वाले मॉड्यूलर बाधाओं को इस तरह से संभाला जाता है कि मापांक का आधार बॉटम फैमिली में न हो।
ऑर्थोगोनल उप-स्थान (orthogonal subspaces) घातांकीय आधारों के संबंध में विशिष्ट गैर-अपभ्रंश (non-degeneracy) स्थितियों को संतुष्ट करते हैं।

इन गुणों को प्राप्त करने में बेकर के प्रमेय (लॉगारिदम के लघु रूपों पर) का उपयोग घातांकों को सीमित करने के लिए और डायोफेंटाइन सन्निकटन (Diophantine approximation) पर क्रोनेकर के प्रमेय का उपयोग अनुपातों के घनत्व को सुनिश्चित करने के लिए किया जाता है।

मॉड्यूलर बाधाओं को संभालना:
परिवर्तनशील मापांक ( $x \equiv c \pmod{z^n}$ ) वाली मॉड्यूलर बाधाओं को संभालने में एक महत्वपूर्ण तकनीकी योगदान है। लेखक लेम्मा 33 का उपयोग करते हैं, जो सह-अभाज्य $\alpha$ और $\beta$ के संदर्भ में उनकी संरचना पर निर्भर करता है। यह लेम्मा बताता है कि अवशेषों (residues) का सेट $\{\beta^n \pmod{\alpha^m}\}$ बड़े $m$ के लिए संरचनात्मक रूप से स्थिर हो जाता है। यह लेखक को घातांकों को "बड़ा" (blow up) करने की अनुमति देता है, जिससे प्रभावी रूप से परिवर्तनशील मापांक बाधाओं को स्थिर मापांक बाधाओं (या निश्चित आवधिकता वाली बाधाओं) में बदला जा सकता है।
क्वांटिफायर एलिमिनेशन (Quantifier Elimination):
एक बार जब प्रणाली सामान्यीकृत हो जाती है और मापांक स्थिर हो जाते हैं, तो लेखक एक लिफ्टिंग तर्क लागू करते हैं। वे दिखाते हैं कि यदि प्रणाली संतुष्ट करने योग्य है, तो एक ऐसा समाधान मौजूद होता है जहाँ बॉटम फैमिली के बाहर के वेरिएबल्स पर्याप्त बड़े होते हैं। शेष वेरिएबल्स (जो बॉटम फैमिली में हैं) को विशिष्ट मॉड्यूलर क्लासेज के भीतर रैखिक पूर्णांकों के रूप में माना जाता है। इन रैखिक वेरिएबल्स को हटाकर, प्रणाली को वेरिएबल्स के एक छोटे सेट में बदल दिया जाता है, जो अंततः एक क्वांटिफायर-मुक्त निर्णय (quantifier-free decision) की ओर ले जाता है।

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

मुख्य प्रमेय: यह शोध पत्र सिद्ध करता है कि सह-अभाज्य पूर्णांक $\alpha, \beta \ge 2$ के लिए, अस्तित्वपरक खंड $\exists\text{FO}(\mathbb{Z}; <, +, V_\alpha, V_\beta)$ निर्णायक है।
पूर्व कार्य का सामान्यीकरण: यह परिणाम करीमोव आदि के कार्य (जो पावर प्रेडिकेट्स $\alpha^\mathbb{N}, \beta^\mathbb{N}$ पर लागू होता था) को अधिक अभिव्यंजक बुची प्रेडिकेट्स $V_\alpha, V_\beta$ तक विस्तारित करता है, जो सह-अभाज्यता की मजबूत शर्त के तहत है।
तकनीकी लेम्मा: शोध पत्र विशिष्ट लेम्मा (जैसे, लेम्मा 33) प्रदान करता है जो सह-अभाज्य आधारों के घातों के मॉड्यूलो (modulo) की संरचना का वर्णन करते हैं, जो परिवर्तनशील मापांक बाधाओं के न्यूनीकरण के लिए आवश्यक हैं।
एल्गोरिद्मिक निर्माण: प्रमाण रचनात्मक है, जो क्वांटिफायर्स को हटाने के लिए आवश्यक सीमाओं, विभाजनों और प्रतिस्थापनों (substitutions) की गणना करने की विधि प्रदान करता है।

महत्व और सीमाएँ
यह शोध पत्र विलेमेयर के मूल विस्तार के अस्तित्वपरक खंड के लिए निर्णयक्षमता के प्रश्न को हल करने का दावा करता है। लेखक स्पष्ट रूप से नोट करते हैं कि सह-अभाज्यता पर उनकी निर्भरता एक महत्वपूर्ण बाधा है।

सह-अभाज्यता पर निर्भरता: प्रमाण सह-अभाज्यता का दो बार उपयोग करता है: एक बेकर के प्रमेय (लेम्मा 12) के अनुप्रयोग में और, अधिक महत्वपूर्ण रूप से, $\beta^n \pmod{\alpha^m}$ की संरचना के संबंध में लेम्मा 33 में। लेखक कहते हैं कि गैर-सह-अभाज्य, गुणात्मक रूप से स्वतंत्र आधारों के लिए, अवशेषों का सेट अधिक अनियमित व्यवहार करता है (रैखिक रूप से बढ़ने के बजाय स्थिर होता है), और वे इस समस्या को कैसे दरकिनार करें, यह नहीं जानते।
क्षेत्र (Scope): यह परिणाम अस्तित्वपरक खंड के लिए विशिष्ट है। पूर्ण सिद्धांत अनिर्णायक बना रहता है।
भविष्य की दिशाएँ: लेखक चर्चा करते हैं कि तीन पावर प्रेडिकेट्स (जैसे, तीन पावर प्रेडिकेट्स) जैसे अधिक प्रेडिकेट्स तक विस्तार करने के लिए संभवतः लॉगारिदम की रैखिक स्वतंत्रता को संभालने के लिए शैनुएल के अनुमान (Schanuel's conjecture) की आवश्यकता होगी। वे यह भी नोट करते हैं कि सामान्य गुणात्मक रूप से स्वतंत्र (गैर-सह-अभाज्य) आधारों के लिए समस्या खुली है और इसके लिए संभवतः नए विचारों की आवश्यकता होगी, जिसमें बेकर के $p$ -adic संस्करण शामिल हो सकते हैं।

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

इसी तरह के और पेपर