💻 computer science

Feasibility of Primality in Bounded Arithmetic

यह शोध पत्र दो बीजगणितीय अभिगृहीतों (algebraic axioms) के अंतर्गत $S^1_2 + iWPHP$ में इसकी वैधता को सिद्ध करके और यह प्रदर्शित करके कि ये अभिगृहीत, प्रमुख संख्या-सिद्धांतिक और बीजगणितीय परिणामों के नए औपचारिक रूपों (formalizations) के साथ, $VTC^0_2$ में सिद्ध करने योग्य हैं, सीमित अंकगणित सिद्धांत $T^{count}_2$ (तथागत $VTC^0_2$ ) के भीतर AKS अभाजता परीक्षण (primality test) की शुद्धता स्थापित करता है।

मूल लेखक: Raheleh Jalali, Ondřej Ježil

प्रकाशित 2026-04-08✓ Author reviewed ⓘ

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

CC BY 4.0

मूल लेखक: Raheleh Jalali, Ondřej Ježil

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

एक बड़ी तस्वीर: "व्यवहार्य" (Feasible) प्रमाण

कल्पना कीजिए कि आपके पास गणितीय सत्यों का एक विशाल पुस्तकालय है। कुछ सत्य सिद्ध करना आसान है; अन्य इतने जटिल हैं कि उन्हें सिद्ध करने में ब्रह्मांड की आयु से भी अधिक समय लगेगा, भले ही आपके पास सबसे तेज़ सुपरकंप्यूटर क्यों न हो।

2002 में, गणितज्ञों ने AKS एल्गोरिदम की खोज की, जो एक जादुई रेसिपी है जो आपको बता सकती है कि कोई संख्या "प्राइम" (जैसे 7 या 13) है या "कंपोजिट" (जैसे 8 या 15)। यह एक सुपर-फास्ट मेटल डिटेक्टर होने जैसा है जो कभी गलती नहीं करता।

लेकिन यहाँ एक पहेली है: सिर्फ इसलिए कि हमारे पास एक तेज़ मशीन है जो काम करती है, क्या इसका मतलब यह है कि हमारे पास उस मशीन के काम करने का एक तेज़ प्रमाण (proof) है?

यह शोध पत्र पूछता है: क्या हम केवल "व्यवहार्य" तर्क का उपयोग करके यह सिद्ध कर सकते हैं कि AKS एल्गोरिदम सही है? गणित की दुनिया में, "व्यवहार्य" का अर्थ आमतौर पर एक ऐसा प्रमाण है जिसके लिए अनंत संसाधनों या असंभव गणनाओं की आवश्यकता नहीं होती। लेखक, राहेलेह जलाल और ओन्ड्रेज़ जेज़िल कहते हैं कि हाँ। वे पूरे AKS एल्गोरिदम के प्रमाण को एक बहुत ही सख्त, "लीन" (lean) तार्किक प्रणाली जिसे $VTC_0^2$ कहा जाता है, में फिट करने में सफल रहे।

इसे इस तरह समझें: उन्होंने एक विशाल, जटिल वास्तुशिल्प ब्लूप्रिंट (AKS प्रमाण) लिया और दिखाया कि इसे केवल सरल, पूर्व-निर्मित ईंटों (बुनियादी अंकगणितीय नियमों) का उपयोग करके बनाया जा सकता है, जिसमें किसी भारी क्रेन या अनंत आपूर्ति की आवश्यकता नहीं है।

हमारी कहानी के पात्र

यह समझने के लिए कि उन्होंने यह कैसे किया, आइए हमारे पात्रों से मिलें:

AKS एल्गोरिदम (जासूस): एक जासूस जो यह जाँचता है कि कोई संख्या प्राइम है या नहीं। यह तेज़ और विश्वसनीय है।
लक्ष्य प्रणाली ( $VTC_0^2$ ): यह जासूस का कार्यालय है जहाँ अंतिम प्रमाण रहता है। यह एक बहुत छोटा, सख्त कार्यालय है। यहाँ जासूस बहुत बुद्धिमान है लेकिन उसके पास बहुत सीमित उपकरण हैं। वह जटिल मशीनरी का उपयोग नहीं कर सकता; वह केवल बुनियादी जोड़, गुणा और साधारण गिनती का उपयोग कर सकता है। जबकि यह प्रणाली मानक गणित की पूर्ण शक्ति की तुलना में "कमजोर" मानी जाती है, यह यहाँ आवश्यक विशिष्ट प्रकार के कथनों के मामले में अन्य प्रणालियों (जैसे $T_2$ ) की तुलना में वास्तव में अधिक शक्तिशाली है। यह अंतिम लक्ष्य है: इन कड़े प्रतिबंधों के भीतर एल्गोरिदम के काम करने को सिद्ध करना।
"जादुई अभिलेख" (GFLT और RUB): ये वे विशेष उपकरण हैं जिन्हें लेखकों को छोटे कार्यालय में केस सुलझाने में मदद करने के लिए आविष्कार करना पड़ा।

चुनौती: यह कठिन क्यों है?

AKS एल्गोरिदम को सिद्ध करना कठिन है क्योंकि यह बहुपदों (polynomials - X वाले समीकरण) और मूलों/जड़ों (roots - उन समीकरणों के समाधान) से जुड़ी कुछ गहरी बीजगणितीय युक्तियों पर निर्भर करता है।

कल्पना कीजिए कि AKS एल्गोरिदम एक संख्या प्राइम है या नहीं, यह जाँचने के लिए एक विशाल, जटिल समीकरण के व्यवहार की जाँच कर रहा है।

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

समाधान: दो नए उपकरण

छोटे कार्यालय में प्रमाण को काम करने योग्य बनाने के लिए, लेखकों ने दो "जादुई अभिलेख" (नियम जो उन्होंने अपने नियम पुस्तिका में जोड़े) पेश किए।

1. "सामान्यीकृत फर्माट का लघु प्रमेय" (GFLT)

यह क्या है: एक प्रसिद्ध गणितीय नियम (फर्माट का लघु प्रमेय) कहता है कि यदि आपके पास एक अभाज्य संख्या है, तो कुछ गणितीय पैटर्न एक बहुत ही विशिष्ट तरीके से दोहराए जाते हैं। AKS एल्गोरिदम इस पैटर्न के एक अधिक जटिल संस्करण पर निर्भर करता है।
उपमा: एक घड़ी की कल्पना करें। यदि आप जानते हैं कि समय 12:00 बजे हैं, तो आप जानते हैं कि 12 घंटों के बाद, फिर से 12:00 बजेंगे। यह एक सरल पैटर्न है। AKS एल्गोरिदम को यह जानने की आवश्यकता है कि यदि आपके पास एक "प्राइम क्लॉक" है, तो संख्याओं का एक बहुत अधिक जटिल नृत्य हमेशा शुरुआती बिंदु पर ही वापस आएगा।
समाधान: लेखकों ने छोटे कार्यालय में एक नियम जोड़ा कि, "हम यह स्वीकार करते हैं कि यह जटिल नृत्य काम करता है, भले ही हम अभी इस नृत्य के हर एक चरण को सिद्ध न कर सकें।" यह जासूस को भारी काम को छोड़कर यह मानने की अनुमति देता है कि पैटर्न बना रहेगा।

2. "रूट अपर बाउंड" (RUB)

यह क्या है: बीजगणित में, $N$ डिग्री का एक बहुपद (polynomial) अधिकतम $N$ समाधान (roots) रख सकता है। AKS प्रमाण को संख्या प्राइम है या नहीं, यह सिद्ध करने के लिए इन समाधानों को गिनने की आवश्यकता होती है।
उपमा: एक बाड़ वाले बगीचे की कल्पना करें। आप जानते हैं कि बगीचे में अधिकतम 5 फूल हैं। AKS प्रमाण को हर एक फूल की ओर इशारा करने और कहना है, "यह एक है, यह दो है..."
समस्या: छोटे कार्यालय में, यदि बगीचा विशाल है और फूल एक जटिल भूलभुलैया में छिपे हुए हैं, तो जासूस आसानी से फूलों को नहीं गिन सकता।
समाधान: लेखकों ने एक "रूट अपर बाउंड" टूल जोड़ा। यह एक जादुई मानचित्र की तरह है जो तुरंत बगीचे के हर फूल को 1 से 5 तक के नंबर के साथ लेबल कर देता है। यह आपको यह नहीं बताता कि फूल कहाँ हैं, लेकिन यह गारंटी देता है कि यदि आपको एक फूल मिलता है, तो आप उसे एक अद्वितीय आईडी नंबर दे सकते हैं, और आपके पास नंबर खत्म नहीं होंगे। यह जासूस को समीकरण के "मूलों" (roots) को बिना भटके गिनने की अनुमति देता है।

प्रमाण की यात्रा

लेखकों ने केवल इन उपकरणों को समस्या पर नहीं थोपा; उन्होंने दो-चरणीय रणनीति का उपयोग करके चरण-दर-चरण एक पुल बनाया:

चरण 1: मॉड्यूलर चरण ( $S_1^2$ + Axioms): सबसे पहले, उन्होंने दिखाया कि यदि आपके पास एक बुनियादी तार्किक प्रणाली ( $S_1^2$ ) है और आप बस यह मानते हैं कि दो जादुई अभिलेख (GFLT और RUB) सत्य हैं, तो आप AKS एल्गोरिदम को काम करते हुए सिद्ध कर सकते हैं। यह चरण AKS प्रमाण के मूल तर्क को अलग करता है, यह दिखाता है कि इसे चलाने के लिए किन अतिरिक्त नियमों की आवश्यकता है।
चरण 2: समेकन चरण ( $VTC_0^2$ ): फिर, वे अपनी लक्षित प्रणाली, $VTC_0^2$ $V T C_{0}^{2}$ पर गए। उन्होंने सिद्ध किया कि यह प्रणाली वास्तव में स्वयं जादुई अभिलेखों को सत्य होने के लिए सिद्ध करने के लिए पर्याप्त रूप से मजबूत है।
- उन्होंने एक चतुर गिनती वाली ट्रिक (जैसे कि एक संख्या फैक्टोरियल में कितनी बार विभाजित होती है) का उपयोग करके "सामान्यीकृत फर्माट" नियम को सिद्ध किया।
- उन्होंने "रूट अपर बाउंड" नियम को यह दिखाकर सिद्ध किया कि आप इन समीकरणों के मूलों को एल्गोरिदम के माध्यम से ढूंढ सकते हैं और लेबल कर सकते हैं, ठीक वैसे ही जैसे ताश की गड्डी को छाँटना।

इन बिंदुओं को जोड़कर, उन्होंने दिखाया कि "अतिरिक्त नियम" जिन्हें प्रमाण के लिए आवश्यक माना गया है, वे केवल धारणाएँ नहीं हैं, बल्कि तथ्य हैं जिन्हें $VTC_0^2$ प्रणाली स्वयं सत्यापित कर सकती है।

भव्य निष्कर्ष

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

यह क्यों मायने रखता है?

गणित में विश्वास: यह पुष्टि करता है कि AKS एल्गोरिदम केवल भाग्य से काम करने वाला कोई "ब्लैक बॉक्स" नहीं है। यह ठोस, मौलिक तर्क पर निर्मित है जिसके लिए अनंत शक्ति की आवश्यकता नहीं होती।
कंप्यूटर विज्ञान: यह हमें बताता है कि प्राइमलिटी (primality) को सिद्ध करने की जटिलता एक विशिष्ट अर्थ में "व्यवहार्य" है। यह काउंटिंग हाइरार्की (Counting Hierarchy) के भीतर फिट बैठती है।
"रिवर्स मैथमेटिक्स" का खेल: यह उस खेल का हिस्सा है जहाँ गणितज्ञ किसी प्रमेय को सिद्ध करने के लिए आवश्यक तर्क की बिल्कुल न्यूनतम मात्रा खोजने का प्रयास करते हैं। लेखकों ने इस प्रमाण के लिए एक बहुत ही निचला स्तर पाया, जिससे पता चलता है कि प्राइमलिटी टेस्टिंग गणित के व्यापक परिदृश्य में एक बहुत ही "स्वाभाविक" और "सरल" अवधारणा है।

संक्षेप में

लेखकों ने एक जटिल, हाई-टेक प्रमाण (AKS) लिया और दिखाया कि इसे केवल सरल, पूर्व-निर्मित ईंटों का उपयोग करके विघटित और पुनर्गठित किया जा सकता है। उन्होंने पहले उन सटीक अतिरिक्त ईंटों की पहचान की (GFLT और RUB) जो प्रमाण को एक बुनियादी प्रणाली में काम करने के लिए आवश्यक थे, और फिर दिखाया कि उनकी लक्षित प्रणाली ( $VTC_0^2$ ) उन ईंटों का निर्माण स्वयं करने के लिए पर्याप्त रूप से सक्षम है।

"व्यवहार्यता" पर एक नोट: यहाँ सूक्ष्म होना महत्वपूर्ण है। मानक गणित की पूर्ण शक्ति की तुलना में प्रणाली $VTC_0^2$ वास्तव में बहुत "कमजोर" है। हालाँकि, यह "पॉलीनोमियल-टाइम" तर्क (सबसे सख्त व्यवहार्य परिभाषा) के बिल्कुल समान नहीं है। इसकी जटिलता काउंटिंग हाइरार्की के अनुरूप है, जो साधारण पॉलीनोमियल-टाइम तर्क से वास्तव में अधिक शक्तिशाली है। इसलिए, जबकि यह प्रमाण गणितीय तर्क के मानकों के अनुसार अविश्वसनीय रूप से कुशल और "लीन" है, यह अभी भी कंप्यूटर दक्षता के पूर्ण न्यूनतम से थोड़ा अधिक शक्तिशाली क्षेत्र में काम करता है।

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

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

यह शोध पत्र अभाज्यता परीक्षण (primality testing) के प्रमाण की व्यवहार्यता (feasibility) संबंधी प्रश्न को संबोधित करता है। विशेष रूप से, यह पूछता है: AKS अभाज्यता परीक्षण की शुद्धता का औपचारिक प्रमाण कितना "व्यवहार्य" (कंप्यूटेशनल जटिलता के संदर्भ में) है?

यद्यपि AKS एल्गोरिदम (अग्रवाल, कायल और सक्सेना, 2002) अभाज्यता परीक्षण के लिए पहला नियत-समय (deterministic polynomial-time) एल्गोरिदम है, इसकी शुद्धता का प्रमाण गैर-तुच्छ संख्या-सिद्धांत और बीजगणितीय कथनों (जैसे कि साइक्लोटोमिक बहुपदों के गुण, फर्मा का लिटिल थ्योरम, और मूलों की गणना/root counting) पर निर्भर करता है। लेखक इस प्रमाण को बाउंडेड अरिथमेटिक (bounded arithmetic) के भीतर औपचारिक रूप देने का लक्ष्य रखते हैं, जो कि एक ऐसा क्षेत्र है जहाँ सिद्धांत विशिष्ट जटिलता वर्गों (complexity classes) के अनुरूप होते हैं।

मुख्य चुनौती यह है कि मानक बाउंडेड अरिथमेटिक सिद्धांत (जैसे $S^1_2$ ) अतिरिक्त अभिगृहीतों (axioms) के बिना AKS प्रमाण के लिए आवश्यक कुछ बीजगणितीय तथ्यों को सिद्ध करने के लिए बहुत कमजोर हैं। लेखक उस सबसे कमजोर सिद्धांत को निर्धारित करने का प्रयास कर रहे हैं जो AKS एल्गोरिदम की शुद्धता को सिद्ध करने में सक्षम है, जिसे $\text{AKSCorrect}$ कहा गया है।

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

लेखक एक मॉड्यूलर औपचारिकीकरण रणनीति (modular formalization strategy) का उपयोग करते हैं, जिसमें वे AKS शुद्धता प्रमाण को तार्किक घटकों में तोड़ते हैं और प्रत्येक भाग के लिए आवश्यक न्यूनतम सिद्धांत को निर्धारित करते हैं।

AKS प्रमाण का विखंडन (Decomposition of the AKS Proof): वे मूल AKS प्रमाण को लेम्मा (A से H तक) के एक अनुक्रम में पुनर्गठित करते हैं और प्रत्येक चरण के लिए आवश्यक विशिष्ट बीजगणितीय और संख्या-सिद्धांत उपकरणों की पहचान करते हैं।
सहायक अभिगृहीतों का परिचय (Introduction of Auxiliary Axioms): कमजोर सिद्धांतों और AKS प्रमाण की आवश्यकताओं के बीच के अंतर को पाटने के लिए, वे दो विशिष्ट बीजगणितीय अभिगृहीतों को पेश करते हैं:
- सामान्यीकृत फर्मा का लिटिल थ्योरम (Generalized Fermat's Little Theorem - GFLT): एक औपचारिकीकरण जो यह बताता है कि विशिष्ट मापदंडों के लिए $(X+a)^p \equiv X^p + a \pmod{p, X^r-1}$ होता है।
- रूट अपर बाउंड (Root Upper Bound - RUB): एक अभिगृहीत जो एक फलन प्रतीक $\iota$ पेश करता है जो एक विरल बहुपद (sparse polynomial) के मूलों को पूर्णांकों के साथ इनजेक्टिव रूप से मैप करता है, जो बहुपद की डिग्री द्वारा सीमित होते हैं। यह मूलों की गणना करने की आवश्यकता को प्रतिस्थापित करता है, जो कमजोर सिद्धांतों में कठिन है।
मध्यवर्ती सिद्धांत में औपचारिकीकरण (Formalization in Intermediate Theory): वे पहले सिद्धांत $S^1_2 + \text{iWPHP} + \text{RUB} + \text{GFLT}$ में AKS की शुद्धता को सिद्ध करते हैं। यहाँ, $\text{iWPHP}$ 'इनजेक्टिव वीक पिजनहोल प्रिंसिपल' है। यह मध्यवर्ती सिद्धांत प्रमाण के मॉड्यूलर विखंडन का प्रतिनिधित्व करता है, जो परिणाम प्राप्त करने के लिए आवश्यक "बुनियादी" अभिगृहीतों को अलग करता है।
मजबूत सिद्धांत में व्युत्पत्ति (Derivation in Stronger Theory): वे फिर यह प्रदर्शित करते हैं कि सिद्धांत $VTC^0_2$ (स्मैश फंक्शन और बहुपद-समय कार्यों के साथ $VTC^0$ का एक विस्तार) मध्यवर्ती सिद्धांत के परिणामों को सिद्ध करता है। विशेष रूप से, $VTC^0_2$ यह सिद्ध करता है कि अभिगृहीत $\text{iWPHP}$ , $\text{RUB}$ , और $\text{GFLT}$ सत्य हैं।
तकनीकी औपचारिकीकरण (Technical Formalizations): लेखक निम्नलिखित का नया औपचारिकीकरण प्रदान करते हैं:
- $PV_1$ में लेजेंड्रे का फॉर्मूला (फैक्टोरियल के अभाज्य गुणनखंड के लिए)।
- $PV_1$ में साइक्लोटोमिक बहुपद और परिमित क्षेत्रों (finite fields) पर विस्तार।
- $VTC^0$ में बहुपद विभाजन के लिए कुंग-सीविंगकिंग (Kung–Sieveking) एल्गोरिदम की शुद्धता।

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

A. कमजोर सिद्धांतों में बीजगणितीय संरचनाओं का औपचारिकीकरण

लेजेंड्रे का फॉर्मूला: $PV_1$ में सिद्ध, जो $n!$ में अभाज्य $p$ की घात स्थापित करता है। यह संख्याओं के लघुत्तम समापवर्त्य (LCM) को बांधने के लिए महत्वपूर्ण है, जो AKS एल्गोरिदम में पैरामीटर $r$ के अस्तित्व को सिद्ध करने में एक प्रमुख चरण है।
साइक्लोटोमिक बहुपद: लेखक $PV_1$ के भीतर परिमित क्षेत्रों $\mathbb{Z}/p\mathbb{Z}$ के साइक्लोटोमिक विस्तारों के अस्तित्व को सिद्ध करते हैं। यह AKS प्रमाण में "इंट्रोस्पेक्टिव" तर्क के लिए आवश्यक अपरिमेय बहुपद $h$ के निर्माण की अनुमति देता है।
बहुपद विभाजन: वे $VTC^0$ में उच्च-डिग्री वाले बहुपदों को विभाजित करने के लिए कुंग-सीविंगकिंग एल्गोरिदम की शुद्धता को सत्यापित करते हैं, जो बाउंडेड अरिथमेटिक के लिए एक स्वतंत्र रुचि का विषय है।

B. रूट अपर बाउंड (RUB) अभिगृहीत

पेपर में मनमाने डिग्री के विरल बहुपदों को संभालने के लिए RUB को एक नए अभिगृहीत के रूप में पेश किया गया है। बीजगणित के मूलभूत प्रमेय (Fundamental Theorem of Algebra) को औपचारिक बनाने के पिछले प्रयासों के विपरीत (जो केवल कम-डिग्री वाले बहुपदों के लिए काम करते थे), RUB मूलों से इंडेक्स तक एक इनजेक्टिव मैपिंग प्रदान करता है। यह पूर्ण गणना क्षमताओं की आवश्यकता के बिना लेम्मा G (इंट्रोस्पेक्टिव बहुपदों के सेट के आकार पर ऊपरी सीमा) को सिद्ध करने के लिए आवश्यक है।

C. सिद्धांतों का पदानुक्रम (Hierarchy of Theories)

लेखक निम्नलिखित तार्किक श्रृंखला स्थापित करते हैं:

$PV_1$ : बुनियादी बीजगणितीय संरचनाओं और लेजेंड्रे के फॉर्मूले को औपचारिक बनाता है।
$S^1_2 + \text{iWPHP} + \text{RUB} + \text{GFLT}$ : प्रमाण के मॉड्यूलर विखंडन का प्रतिनिधित्व करता है, जिसमें AKS एल्गोरिदम की शुद्धता को सिद्ध करने के लिए आवश्यक विशिष्ट अभिगृहीत शामिल हैं।
$VTC^0_2$ : एक व्यापक सिद्धांत के रूप में, $VTC^0_2$ यह सिद्ध करता है कि मध्यवर्ती सिद्धांत में उपयोग किए गए अभिगृहीत ( $\text{iWPHP}$ , $\text{RUB}$ , और $\text{GFLT}$ ) $\Sigma^B_1$ -परिभाषित फलनों के लिए सत्य हैं। फलस्वरूप, $VTC^0_2$ AKS एल्गोरिदम की शुद्धता को सिद्ध करता है।
$T^{count}_2$ : चूंकि $VTC^0_2$ , $\Sigma^B_1$ वाक्यों के लिए $T^{count}_2$ पर कंजर्वेटिव है, इसलिए परिणाम $T^{count}_2$ तक विस्तृत होता है। ध्यान दें कि $VTC^0_2$ इस पेपर के प्रासंगिक $\Sigma^B_1$ कथनों के संबंध में $T^{count}_2$ से अधिक मजबूत है; यह एक कमजोर विकल्प नहीं है, बल्कि वह सिद्धांत है जो मध्यवर्ती प्रणाली के अभिगृहीतों को मान्य करता है।

4. मुख्य परिणाम (Main Results)

प्रमेय (Theorem): सिद्धांत $VTC^0_2$ (और समतुल्य रूप से $\Sigma^B_1$ $Σ_{1}^{B}$ वाक्यों के लिए $T^{count}_2$ ) वाक्य $\text{AKSCorrect}$ $AKSCorrect$ को सिद्ध करता है।
- $\text{AKSCorrect}$ कथन है: $\forall x (\text{Prime}(x) \leftrightarrow \text{AKSPrime}(x))$ ।
उप-प्रमेय (Corollary): AKS एल्गोरिदम की शुद्धता एक ऐसे सिद्धांत में सिद्ध की जा सकती है जो $TC^0$ (कॉन्स्टेंट-डेप्थ थ्रेशोल्ड सर्किट) के अनुरूप है, जिसे बहुपद-समय कार्यों के साथ विस्तारित किया गया है।
विशिष्ट लेम्मा प्रमाण:
- लेम्मा C और D: $S^1_2$ में लेजेंड्रे के फॉर्मूला का उपयोग करके सिद्ध किया गया है ताकि यह दिखाया जा सके कि एक उपयुक्त $r$ मौजूद है जिससे $\text{ord}_r(n) > \log^2 n$ हो।
- लेम्मा H: $S^1_2 + \text{iWPHP} + \text{RUB} + \text{GFLT}$ में सिद्ध किया गया है, यह दिखाते हुए कि यह मानना कि $n$ भाज्य (composite) है, लेम्मा F और लेम्मा G के फलनों के संयोजन के माध्यम से इनजेक्टिव वीक पिजनहोल प्रिंसिपल (iWPHP) के साथ विरोधाभास की ओर ले जाता है।

5. महत्व (Significance)

बाउंडेड रिवर्स मैथमेटिक्स: यह कार्य बाउंडेड अरिथमेटिक सिद्धांतों की अंतर्निहित शक्ति के बारे में गहरी अंतर्दृष्टि प्रदान करता है। यह दर्शाता है कि कम्प्यूटेशनल नंबर थ्योरी के मौलिक परिणाम (जैसे AKS प्रमाण) को काउंटिंग पदानुक्रम (counting hierarchy) के अनुरूप सिद्धांतों द्वारा पकड़ा जा सकता है, बशर्ते विशिष्ट बीजगणितीय अभिगृहीत उपलब्ध हों।
प्रूफ कॉम्प्लेक्सिटी (Proof Complexity): इस परिणाम के प्रोपोज़िशनल प्रूफ कॉम्प्लेक्सिटी पर निहितार्थ हैं। चूंकि $VTC^0_2$ AKS की शुद्धता को सिद्ध करता है, इसलिए एक विशिष्ट प्रोपोज़िशनल प्रूफ सिस्टम (जो $VTC^0_2$ के अनुरूप है) मौजूद है जहाँ विभिन्न लंबाई के इनपुट के लिए AKS की शुद्धता व्यक्त करने वाले ताऊटोलॉजी (tautologies) को कुशलतापूर्वक सिद्ध किया जा सकता है।
विटनेसिंग और एल्गोरिदम: औपचारिकीकरण बाउंडेड अरिथमेटिक में अस्तित्व संबंधी कथनों की सिद्धता को बहुपद-समय एल्गोरिदम के अस्तित्व से जोड़ता है। हालांकि पेपर नोट करता है कि गुणनखंड समस्या (factorization problem) के लिए विटनेसिंग अभी भी तुच्छ (trivial) बनी हुई है, लेकिन स्वयं अभाज्यता परीक्षण का औपचारिकीकरण "व्यवहार्य" गणित के लिए आवश्यक तार्किक शक्ति को समझने की दिशा में एक महत्वपूर्ण कदम है।
बीजगणितीय औपचारिकीकरण: यह पेपर बाउंडेड अरिथमेटिक के भीतर बीजगणित को औपचारिक बनाने की स्थिति को आगे बढ़ाता है, विशेष रूप से साइक्लोटोमिक बहुपदों और विरल बहुपदों के संबंध में, जिनका पहले या तो उपचार नहीं किया गया था या आंशिक रूप से किया गया था।
जटिलता चेतावनी (Complexity Caveat): यह ध्यान रखना महत्वपूर्ण है कि $VTC^0_2$ काउंटिंग पदानुक्रम ( $TC^0$ को बहुपद-समय कार्यों के साथ विस्तारित) के अनुरूप है, जो कि सख्त बहुपद-समय तर्क ( $P$ ) की तुलना में काफी मजबूत माना जाता है। जबकि $VTC^0_2$ गणितीय तर्क के मानकों के अनुसार बहुत कमजोर है, इसे सख्त अर्थों में "व्यवहार्य" (feasible) प्रणाली के रूप में वर्णित नहीं किया जाना चाहिए। क्या परिणाम को वास्तव में व्यवहार्य (बहुपद-समय) सिद्धांत तक नीचे लाया जा सकता है, यह एक खुला प्रश्न है।

निष्कर्ष (Conclusion)

जलाली और जेज़िल सफलतापूर्वक सिद्ध करते हैं कि AKS अभाज्यता परीक्षण की शुद्धता बाउंडेड अरिथमेटिक सिद्धांत $VTC^0_2$ का एक प्रमेय है। RUB अभिगृहीत को पेश करके और $PV_1$ और $S^1_2$ में प्रमुख बीजगणितीय लेम्मा को औपचारिक रूप देकर, वे AKS एल्गोरिदम की कॉम्बिनेटरियल प्रकृति और कमजोर अरिथमेटिक सिद्धांतों की तार्किक सीमाओं के बीच के अंतर को पाटते हैं। प्रमाण को एक मध्यवर्ती सिद्धांत (विशिष्ट अभिगृहीतों के साथ $S^1_2$ ) के भीतर मॉड्यूलर बनाया गया है, जिसे बाद में $VTC^0_2$ के भीतर पूरी तरह से समाहित दिखाया गया है। यह स्थापित करता है कि अभाज्यता परीक्षण काउंटिंग पदानुक्रम के अनुरूप एक सिद्धांत के भीतर तार्किक रूप से "व्यवहार्य" है, हालांकि क्या यह सख्ती से बहुपद-समय सिद्धांत में रहता है, यह एक खुला प्रश्न बना हुआ है।