संख्या सिद्धांत में प्रभावी परिणाम: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Theorems whose content is effectively computable}}ऐतिहासिक कारणों से और [[डायोफैंटाइन समीकरण]] | {{short description|Theorems whose content is effectively computable}}ऐतिहासिक कारणों से और [[डायोफैंटाइन समीकरण|डायोफैंटाइन समीकरणों]] के समाधान के लिए आवेदन करने के लिए, [[संख्या सिद्धांत]] में परिणाम गणित की अन्य शाखाओं की तुलना में अधिक जांचे गए हैं जिससे यह देखा जा सके कि उनकी पदार्थ प्रभावी रूप से गणना योग्य है या नहीं।{{Citation needed|date=January 2022}}. जहां यह दावा किया जाता है कि [[पूर्णांक|पूर्णांकों]] की कुछ सूची परिमित है, सवाल यह है कि क्या सिद्धांत रूप में सूची को मशीन संगणना के बाद मुद्रित किया जा सकता है। | ||
== लिटलवुड का परिणाम == | == लिटलवुड का परिणाम == | ||
अप्रभावी परिणाम का प्रारंभिक उदाहरण 1914 का जे.ई. लिटलवुड का प्रमेय था,<ref>{{cite journal | first=J. E. | last= Littlewood | authorlink=J. E. Littlewood |title=अभाज्य संख्याओं के वितरण पर|journal=[[Comptes Rendus]]|volume= 158 |year=1914|pages= 1869–1872 | jfm=45.0305.01 }}</ref> कि अभाज्य संख्या प्रमेय में ψ(x) और π(x) दोनों के अंतर उनके स्पर्शोन्मुख अनुमानों के साथ | अप्रभावी परिणाम का प्रारंभिक उदाहरण 1914 का जे.ई. लिटलवुड का प्रमेय था,<ref>{{cite journal | first=J. E. | last= Littlewood | authorlink=J. E. Littlewood |title=अभाज्य संख्याओं के वितरण पर|journal=[[Comptes Rendus]]|volume= 158 |year=1914|pages= 1869–1872 | jfm=45.0305.01 }}</ref> कि अभाज्य संख्या प्रमेय में ψ(x) और π(x) दोनों के अंतर उनके स्पर्शोन्मुख अनुमानों के साथ अपरिमित रूप से बदलते हैं।<ref>{{cite book | ||
| last = Feferman | first = Solomon | authorlink = Solomon Feferman | | last = Feferman | first = Solomon | authorlink = Solomon Feferman | ||
| contribution = Kreisel's "unwinding" program | | contribution = Kreisel's "unwinding" program | ||
| Line 11: | Line 11: | ||
| publisher = A K Peters | location = Wellesley, MA | | publisher = A K Peters | location = Wellesley, MA | ||
| title = Kreiseliana | | title = Kreiseliana | ||
| year = 1996}} See p. 9 of the preprint version.</ref> 1933 में [[स्टेनली स्क्यूज़]] ने पहले चिन्ह परिवर्तन के लिए प्रभावी ऊपरी सीमा प्राप्त की,<ref>{{cite journal | first= S.|last= Skewes|authorlink= Stanley Skewes |title=On the difference π(''x'') − Li(''x'')|journal=[[Journal of the London Mathematical Society]]|volume=8|year=1933|pages= 277–283 | zbl=0007.34003 | jfm=59.0370.02 | doi=10.1112/jlms/s1-8.4.277}}</ref> अब | | year = 1996}} See p. 9 of the preprint version.</ref> 1933 में [[स्टेनली स्क्यूज़]] ने पहले चिन्ह परिवर्तन के लिए प्रभावी ऊपरी सीमा प्राप्त की,<ref>{{cite journal | first= S.|last= Skewes|authorlink= Stanley Skewes |title=On the difference π(''x'') − Li(''x'')|journal=[[Journal of the London Mathematical Society]]|volume=8|year=1933|pages= 277–283 | zbl=0007.34003 | jfm=59.0370.02 | doi=10.1112/jlms/s1-8.4.277}}</ref> अब [[स्टेनली स्क्यूज़|स्क्यूज़]]' संख्या के रूप में जाना जाता है। | ||
अधिक विस्तार से, संख्यात्मक अनुक्रम f (n) के लिए लिखना, इसके बदलते संकेत के बारे में प्रभावी परिणाम | अधिक विस्तार से, संख्यात्मक अनुक्रम f (n) के लिए लिखना, इसके बदलते संकेत के बारे में प्रभावी परिणाम अपरिमित रूप से अधिकांशतः प्रमेय होगा, जिसमें N के प्रत्येक मान के लिए, मान M > N ऐसा होता है कि f (N) और f (M ) के अलग-अलग संकेत हैं, और ऐसे कि एम की गणना निर्दिष्ट संसाधनों के साथ की जा सकती है। व्यावहारिक रूप में, M की गणना N के बाद से n के मान लेकर की जाएगी, और सवाल यह है कि 'आपको कितनी दूर जाना चाहिए?' पहला संकेत परिवर्तन खोजने के लिए विशेष स्थिति है। प्रश्न का हित यह था कि ज्ञात संख्यात्मक साक्ष्य ने संकेत में कोई परिवर्तन नहीं दिखाया: लिटिलवुड के परिणाम ने आश्वासन दी कि यह प्रमाण केवल छोटी संख्या का प्रभाव था, किंतु यहां 'छोटे' में बिलियन तक n के मान सम्मिलित थे। | ||
संगणनीयता की आवश्यकता परिणामों के [[गणितीय प्रमाण]] के लिए [[विश्लेषणात्मक संख्या सिद्धांत]] में उपयोग किए गए दृष्टिकोण पर प्रतिबिंबित करती है और इसके विपरीत है। उदाहरण के लिए यह [[लैंडौ संकेतन]] और इसके निहित स्थिरांकों के किसी भी उपयोग पर सवाल उठाता है: क्या ऐसे स्थिरांकों के लिए दावे शुद्ध [[अस्तित्व प्रमेय]] हैं, या क्या कोई ऐसा संस्करण पुनर्प्राप्त कर सकता है जिसमें 1000 (मान लें) अंतर्निहित स्थिरांक की जगह लेता है? दूसरे शब्दों में, यदि यह ज्ञात होता कि M> N के चिन्ह में परिवर्तन होता है और ऐसा ही | संगणनीयता की आवश्यकता परिणामों के [[गणितीय प्रमाण]] के लिए [[विश्लेषणात्मक संख्या सिद्धांत]] में उपयोग किए गए दृष्टिकोण पर प्रतिबिंबित करती है और इसके विपरीत है। उदाहरण के लिए यह [[लैंडौ संकेतन]] और इसके निहित स्थिरांकों के किसी भी उपयोग पर सवाल उठाता है: क्या ऐसे स्थिरांकों के लिए दावे शुद्ध [[अस्तित्व प्रमेय]] हैं, या क्या कोई ऐसा संस्करण पुनर्प्राप्त कर सकता है जिसमें 1000 (मान लें) अंतर्निहित स्थिरांक की जगह लेता है? दूसरे शब्दों में, यदि यह ज्ञात होता कि M> N के चिन्ह में परिवर्तन होता है और ऐसा ही | ||
: | : ''M'' = O(''G''(''N'')) | ||
कुछ स्पष्ट कार्य (गणित) जी के लिए, शक्तियों, लघुगणक और [[घातांक]] से निर्मित कहते हैं, जिसका अर्थ है केवल | कुछ स्पष्ट कार्य (गणित) जी के लिए, शक्तियों, लघुगणक और [[घातांक]] से निर्मित कहते हैं, जिसका अर्थ है केवल | ||
: | : ''M'' < ''A''.''G''(''N'') | ||
कुछ निरपेक्ष स्थिरांक A के लिए। A का मान, तथाकथित निहित स्थिरांक, को कम्प्यूटेशनल उद्देश्यों के लिए भी स्पष्ट करने की आवश्यकता हो सकती है। लन्दौ अंकन का लोकप्रिय परिचय होने का कारण यह है कि यह ठीक वही छुपाता है जो A है। प्रमाण के कुछ अप्रत्यक्ष रूपों में यह बिल्कुल भी स्पष्ट नहीं हो सकता है कि निहित स्थिरांक को स्पष्ट किया जा सकता है। | कुछ निरपेक्ष स्थिरांक A के लिए। A का मान, तथाकथित निहित स्थिरांक, को कम्प्यूटेशनल उद्देश्यों के लिए भी स्पष्ट करने की आवश्यकता हो सकती है। लन्दौ अंकन का लोकप्रिय परिचय होने का कारण यह है कि यह ठीक वही छुपाता है जो A है। प्रमाण के कुछ अप्रत्यक्ष रूपों में यह बिल्कुल भी स्पष्ट नहीं हो सकता है कि निहित स्थिरांक को स्पष्ट किया जा सकता है। | ||
| Line 45: | Line 45: | ||
* सीगल-वाल्फ़िज़ प्रमेय सीगल शून्य पर आधारित है। | * सीगल-वाल्फ़िज़ प्रमेय सीगल शून्य पर आधारित है। | ||
ठोस जानकारी जो सैद्धांतिक रूप से अधूरी रह गई थी, उसमें [[वर्ग संख्या (संख्या सिद्धांत)]] के लिए निचली सीमाएं | ठोस जानकारी जो सैद्धांतिक रूप से अधूरी रह गई थी, उसमें [[वर्ग संख्या (संख्या सिद्धांत)]] के लिए निचली सीमाएं सम्मिलित थीं ([[संख्या क्षेत्र]] के कुछ वर्गों के लिए [[आदर्श वर्ग समूह]] बढ़ते हैं); और हर के संदर्भ में [[बीजगणितीय संख्या]]ओं के सर्वोत्तम परिमेय संख्या सन्निकटन के लिए सीमाएँ [[एक्सल थ्यू]] के काम के बाद इन बाद वाले को सामान्यतः डायोफैंटाइन समीकरणों के परिणाम के रूप में पढ़ा जा सकता है। प्रमाण में [[लिउविल संख्या]]ओं के लिए उपयोग किया जाने वाला परिणाम प्रभावी है जिस तरह से यह [[औसत मूल्य प्रमेय]] प्रयुक्त करता है: किंतु सुधार (अब थू-सीगल-रोथ प्रमेय क्या है) नहीं थे। | ||
== बाद में काम == | == बाद में काम == | ||
बाद के परिणामों | बाद के परिणामों में विशेष रूप से [[एलन बेकर (गणितज्ञ)]] ने स्थिति बदल दी। गुणात्मक रूप से बोलते हुए, बेकर के प्रमेय अशक्त दिखते हैं, किंतु उनके पास स्पष्ट स्थिरांक हैं और वास्तव में मशीन संगणना के संयोजन के साथ प्रयुक्त किया जा सकता है, यह सिद्ध करने के लिए कि समाधान की सूची (पूर्ण होने का संदेह) वास्तव में संपूर्ण समाधान स्थित है। | ||
== सैद्धांतिक मुद्दे == | == सैद्धांतिक मुद्दे == | ||
विरोधाभास द्वारा | विरोधाभास द्वारा प्रमाण के बारे में अधिक ध्यान रखते हुए, यहां कठिनाइयों को मूल रूप से अलग-अलग प्रमाण विधियों से पूरा किया गया था। सम्मिलित तर्क [[संगणनीयता सिद्धांत]] और संगणनीय कार्यों की तुलना में प्रमाण सिद्धांत के समीप है। किंतु यह शिथिल रूप से [[अनुमान]] लगाया गया है कि कठिनाइयाँ [[कम्प्यूटेशनल जटिलता सिद्धांत]] के दायरे में हो सकती हैं। अप्रभावी परिणाम अभी भी '''A''' ''या'' '''B''', के रूप में सिद्ध हो रहे हैं, जहां हमारे पास यह बताने का कोई विधि नहीं है। | ||
'''स्थिरांक हैं और वास्तव में मशीन संगणना के संयोजन के साथ प्रयुक्त किया जा सकता है, यह सिद्ध करने के लिए कि समाधान की सूची (पूर्ण होने का संदेह) वास्तव में संपूर्ण समाधान स्थित है।''' | |||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 09:15, 26 April 2023
ऐतिहासिक कारणों से और डायोफैंटाइन समीकरणों के समाधान के लिए आवेदन करने के लिए, संख्या सिद्धांत में परिणाम गणित की अन्य शाखाओं की तुलना में अधिक जांचे गए हैं जिससे यह देखा जा सके कि उनकी पदार्थ प्रभावी रूप से गणना योग्य है या नहीं।[citation needed]. जहां यह दावा किया जाता है कि पूर्णांकों की कुछ सूची परिमित है, सवाल यह है कि क्या सिद्धांत रूप में सूची को मशीन संगणना के बाद मुद्रित किया जा सकता है।
लिटलवुड का परिणाम
अप्रभावी परिणाम का प्रारंभिक उदाहरण 1914 का जे.ई. लिटलवुड का प्रमेय था,[1] कि अभाज्य संख्या प्रमेय में ψ(x) और π(x) दोनों के अंतर उनके स्पर्शोन्मुख अनुमानों के साथ अपरिमित रूप से बदलते हैं।[2] 1933 में स्टेनली स्क्यूज़ ने पहले चिन्ह परिवर्तन के लिए प्रभावी ऊपरी सीमा प्राप्त की,[3] अब स्क्यूज़' संख्या के रूप में जाना जाता है।
अधिक विस्तार से, संख्यात्मक अनुक्रम f (n) के लिए लिखना, इसके बदलते संकेत के बारे में प्रभावी परिणाम अपरिमित रूप से अधिकांशतः प्रमेय होगा, जिसमें N के प्रत्येक मान के लिए, मान M > N ऐसा होता है कि f (N) और f (M ) के अलग-अलग संकेत हैं, और ऐसे कि एम की गणना निर्दिष्ट संसाधनों के साथ की जा सकती है। व्यावहारिक रूप में, M की गणना N के बाद से n के मान लेकर की जाएगी, और सवाल यह है कि 'आपको कितनी दूर जाना चाहिए?' पहला संकेत परिवर्तन खोजने के लिए विशेष स्थिति है। प्रश्न का हित यह था कि ज्ञात संख्यात्मक साक्ष्य ने संकेत में कोई परिवर्तन नहीं दिखाया: लिटिलवुड के परिणाम ने आश्वासन दी कि यह प्रमाण केवल छोटी संख्या का प्रभाव था, किंतु यहां 'छोटे' में बिलियन तक n के मान सम्मिलित थे।
संगणनीयता की आवश्यकता परिणामों के गणितीय प्रमाण के लिए विश्लेषणात्मक संख्या सिद्धांत में उपयोग किए गए दृष्टिकोण पर प्रतिबिंबित करती है और इसके विपरीत है। उदाहरण के लिए यह लैंडौ संकेतन और इसके निहित स्थिरांकों के किसी भी उपयोग पर सवाल उठाता है: क्या ऐसे स्थिरांकों के लिए दावे शुद्ध अस्तित्व प्रमेय हैं, या क्या कोई ऐसा संस्करण पुनर्प्राप्त कर सकता है जिसमें 1000 (मान लें) अंतर्निहित स्थिरांक की जगह लेता है? दूसरे शब्दों में, यदि यह ज्ञात होता कि M> N के चिन्ह में परिवर्तन होता है और ऐसा ही
- M = O(G(N))
कुछ स्पष्ट कार्य (गणित) जी के लिए, शक्तियों, लघुगणक और घातांक से निर्मित कहते हैं, जिसका अर्थ है केवल
- M < A.G(N)
कुछ निरपेक्ष स्थिरांक A के लिए। A का मान, तथाकथित निहित स्थिरांक, को कम्प्यूटेशनल उद्देश्यों के लिए भी स्पष्ट करने की आवश्यकता हो सकती है। लन्दौ अंकन का लोकप्रिय परिचय होने का कारण यह है कि यह ठीक वही छुपाता है जो A है। प्रमाण के कुछ अप्रत्यक्ष रूपों में यह बिल्कुल भी स्पष्ट नहीं हो सकता है कि निहित स्थिरांक को स्पष्ट किया जा सकता है।
'सीगल अवधि'
1900-1950 की अवधि में सिद्ध किए गए विश्लेषणात्मक संख्या सिद्धांत के कई प्रमुख परिणाम वास्तव में अप्रभावी थे। मुख्य उदाहरण थे:
- थू-सीगल-रोथ प्रमेय
- 1929 से अभिन्न बिंदुओं पर सीगल की प्रमेय
- श्रेणी संख्या 1 समस्या पर हंस हेइलब्रोन और एडवर्ड लिनफुट की 1934 की प्रमेय[4]
- 1935 का सीगल शून्य पर परिणाम[5]
- सीगल-वाल्फ़िज़ प्रमेय सीगल शून्य पर आधारित है।
ठोस जानकारी जो सैद्धांतिक रूप से अधूरी रह गई थी, उसमें वर्ग संख्या (संख्या सिद्धांत) के लिए निचली सीमाएं सम्मिलित थीं (संख्या क्षेत्र के कुछ वर्गों के लिए आदर्श वर्ग समूह बढ़ते हैं); और हर के संदर्भ में बीजगणितीय संख्याओं के सर्वोत्तम परिमेय संख्या सन्निकटन के लिए सीमाएँ एक्सल थ्यू के काम के बाद इन बाद वाले को सामान्यतः डायोफैंटाइन समीकरणों के परिणाम के रूप में पढ़ा जा सकता है। प्रमाण में लिउविल संख्याओं के लिए उपयोग किया जाने वाला परिणाम प्रभावी है जिस तरह से यह औसत मूल्य प्रमेय प्रयुक्त करता है: किंतु सुधार (अब थू-सीगल-रोथ प्रमेय क्या है) नहीं थे।
बाद में काम
बाद के परिणामों में विशेष रूप से एलन बेकर (गणितज्ञ) ने स्थिति बदल दी। गुणात्मक रूप से बोलते हुए, बेकर के प्रमेय अशक्त दिखते हैं, किंतु उनके पास स्पष्ट स्थिरांक हैं और वास्तव में मशीन संगणना के संयोजन के साथ प्रयुक्त किया जा सकता है, यह सिद्ध करने के लिए कि समाधान की सूची (पूर्ण होने का संदेह) वास्तव में संपूर्ण समाधान स्थित है।
सैद्धांतिक मुद्दे
विरोधाभास द्वारा प्रमाण के बारे में अधिक ध्यान रखते हुए, यहां कठिनाइयों को मूल रूप से अलग-अलग प्रमाण विधियों से पूरा किया गया था। सम्मिलित तर्क संगणनीयता सिद्धांत और संगणनीय कार्यों की तुलना में प्रमाण सिद्धांत के समीप है। किंतु यह शिथिल रूप से अनुमान लगाया गया है कि कठिनाइयाँ कम्प्यूटेशनल जटिलता सिद्धांत के दायरे में हो सकती हैं। अप्रभावी परिणाम अभी भी A या B, के रूप में सिद्ध हो रहे हैं, जहां हमारे पास यह बताने का कोई विधि नहीं है।
स्थिरांक हैं और वास्तव में मशीन संगणना के संयोजन के साथ प्रयुक्त किया जा सकता है, यह सिद्ध करने के लिए कि समाधान की सूची (पूर्ण होने का संदेह) वास्तव में संपूर्ण समाधान स्थित है।
संदर्भ
- ↑ Littlewood, J. E. (1914). "अभाज्य संख्याओं के वितरण पर". Comptes Rendus. 158: 1869–1872. JFM 45.0305.01.
- ↑ Feferman, Solomon (1996). "Kreisel's "unwinding" program" (PDF). Kreiseliana. Wellesley, MA: A K Peters. pp. 247–273. MR 1435765. See p. 9 of the preprint version.
- ↑ Skewes, S. (1933). "On the difference π(x) − Li(x)". Journal of the London Mathematical Society. 8: 277–283. doi:10.1112/jlms/s1-8.4.277. JFM 59.0370.02. Zbl 0007.34003.
- ↑ Heilbronn, H.; Linfoot, E. H. (1934). "On the imaginary quadratic corpora of class-number one". Quarterly Journal of Mathematics. Oxford Series. 5 (1): 293–301. doi:10.1093/qmath/os-5.1.293..
- ↑ *Sprindzhuk, V.G. (2001) [1994], "Diophantine approximation, problems of effective", Encyclopedia of Mathematics, EMS Press – comments on the ineffectiveness of the bound.
बाहरी संबंध
- Sprindzhuk, V.G. (2001) [1994], "Diophantine approximations", Encyclopedia of Mathematics, EMS Press
