सीव सिद्धांत: Difference between revisions
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
{{Short description|Ways to estimate the size of sifted sets of integers}} | {{Short description|Ways to estimate the size of sifted sets of integers}} | ||
चालनी सिद्धांत [[संख्या सिद्धांत]] में सामान्य तकनीकों का एक सेट है, जिसे पूर्णांकों के छने हुए सेटों की गणना करने, या अधिक यथार्थवादी रूप से आकार का अनुमान लगाने के लिए डिज़ाइन किया गया है। छने हुए सेट का प्रोटोटाइपिक उदाहरण कुछ निर्धारित सीमा ''X'' तक [[अभाज्य संख्या]]ओं का सेट है। इसके अनुरूप, चालनी का प्रोटोटाइपिक उदाहरण एराटोस्थनीज की चालनी, या अधिक सामान्य [[पौराणिक छलनी|पौराणिक चालनी]] है। इन विधि का उपयोग करके अभाज्य संख्याओं पर सीधा हमला जल्द ही त्रुटि शब्दों के संचय के रास्ते में स्पष्ट रूप से दुर्गम बाधाओं तक पहुँच जाता है। बीसवीं शताब्दी में संख्या सिद्धांत के प्रमुख पहलुओं में से एक में, चालनी क्या होनी चाहिए, इसके एक अनुभवहीन विचार के साथ सामने वाले हमले की कुछ कठिनाइयों से बचने के विधि खोजे गए थे। | '''चालनी सिद्धांत''' [[संख्या सिद्धांत]] में सामान्य तकनीकों का एक सेट है, जिसे पूर्णांकों के छने हुए सेटों की गणना करने, या अधिक यथार्थवादी रूप से आकार का अनुमान लगाने के लिए डिज़ाइन किया गया है। छने हुए सेट का प्रोटोटाइपिक उदाहरण कुछ निर्धारित सीमा ''X'' तक [[अभाज्य संख्या]]ओं का सेट है। इसके अनुरूप, चालनी का प्रोटोटाइपिक उदाहरण एराटोस्थनीज की चालनी, या अधिक सामान्य [[पौराणिक छलनी|पौराणिक चालनी]] है। इन विधि का उपयोग करके अभाज्य संख्याओं पर सीधा हमला जल्द ही त्रुटि शब्दों के संचय के रास्ते में स्पष्ट रूप से दुर्गम बाधाओं तक पहुँच जाता है। बीसवीं शताब्दी में संख्या सिद्धांत के प्रमुख पहलुओं में से एक में, चालनी क्या होनी चाहिए, इसके एक अनुभवहीन विचार के साथ सामने वाले हमले की कुछ कठिनाइयों से बचने के विधि खोजे गए थे। | ||
एक सफल दृष्टिकोण संख्याओं के एक विशिष्ट छने हुए सेट (उदाहरण के लिए अभाज्य संख्याओं का सेट) को दूसरे, सरल सेट (उदाहरण के लिए लगभग अभाज्य संख्याओं का सेट) द्वारा अनुमानित करना है, जो सामान्यतः मूल सेट से कुछ बड़ा होता है, और विश्लेषण करना आसान होता है। अधिक परिष्कृत चालनी भी सीधे सेटों के साथ काम नहीं करती हैं, किंतु इन सेटों पर सावधानीपूर्वक चुने गए वजन कार्यों के अनुसार उनकी गिनती करती हैं (इन सेटों के कुछ तत्वों को दूसरों की तुलना में अधिक "वजन" देने के विकल्प)। इसके अतिरिक्त, कुछ आधुनिक अनुप्रयोगों में, चालनी का उपयोग छने हुए सेट के आकार का अनुमान लगाने के लिए नहीं किया जाता है, किंतु एक ऐसे फलन का उत्पादन करने के लिए किया जाता है जो सेट पर बड़ा होता है और ज्यादातर इसके बाहर छोटा होता है, जबकि सेट के विशिष्ट फलन की तुलना में विश्लेषण करना आसान होता है। | एक सफल दृष्टिकोण संख्याओं के एक विशिष्ट छने हुए सेट (उदाहरण के लिए अभाज्य संख्याओं का सेट) को दूसरे, सरल सेट (उदाहरण के लिए लगभग अभाज्य संख्याओं का सेट) द्वारा अनुमानित करना है, जो सामान्यतः मूल सेट से कुछ बड़ा होता है, और विश्लेषण करना आसान होता है। अधिक परिष्कृत चालनी भी सीधे सेटों के साथ काम नहीं करती हैं, किंतु इन सेटों पर सावधानीपूर्वक चुने गए वजन कार्यों के अनुसार उनकी गिनती करती हैं (इन सेटों के कुछ तत्वों को दूसरों की तुलना में अधिक "वजन" देने के विकल्प)। इसके अतिरिक्त, कुछ आधुनिक अनुप्रयोगों में, चालनी का उपयोग छने हुए सेट के आकार का अनुमान लगाने के लिए नहीं किया जाता है, किंतु एक ऐसे फलन का उत्पादन करने के लिए किया जाता है जो सेट पर बड़ा होता है और ज्यादातर इसके बाहर छोटा होता है, जबकि सेट के विशिष्ट फलन की तुलना में विश्लेषण करना आसान होता है। | ||
== मूल चालनी सिद्धांत == | == मूल चालनी सिद्धांत == | ||
अंकन की जानकारी के लिए अंत में देखें। | अंकन की जानकारी के लिए अंत में देखें। | ||
Line 63: | Line 63: | ||
चालनी सिद्धांत की तकनीकें अधिक शक्तिशाली हो सकती हैं, किंतु वे [[समता समस्या (छलनी सिद्धांत)|समता समस्या (चालनी सिद्धांत)]] नामक एक बाधा से सीमित प्रतीत होती हैं, जो सामान्यतः यह प्रमाणित करती है कि चालनी सिद्धांत विधियों में विषम संख्या में अभाज्य कारकों के साथ संख्याओं के बीच अंतर करने में अत्यधिक कठिनाई होती है। और अभाज्य गुणनखंडों की सम संख्या वाली संख्याएँ का यह समता समस्या अभी भी बहुत अच्छी तरह से समझी नहीं गई है। | चालनी सिद्धांत की तकनीकें अधिक शक्तिशाली हो सकती हैं, किंतु वे [[समता समस्या (छलनी सिद्धांत)|समता समस्या (चालनी सिद्धांत)]] नामक एक बाधा से सीमित प्रतीत होती हैं, जो सामान्यतः यह प्रमाणित करती है कि चालनी सिद्धांत विधियों में विषम संख्या में अभाज्य कारकों के साथ संख्याओं के बीच अंतर करने में अत्यधिक कठिनाई होती है। और अभाज्य गुणनखंडों की सम संख्या वाली संख्याएँ का यह समता समस्या अभी भी बहुत अच्छी तरह से समझी नहीं गई है। | ||
संख्या सिद्धांत में अन्य विधि की तुलना में | संख्या सिद्धांत में अन्य विधि की तुलना में चालनी सिद्धांत तुलनात्मक रूप से प्राथमिक है इस अर्थ में कि इसे [[बीजगणितीय संख्या सिद्धांत]] या [[विश्लेषणात्मक संख्या सिद्धांत]] से परिष्कृत अवधारणाओं की आवश्यकता नहीं है। फिर भी अधिक उन्नत चालनी अभी भी बहुत जटिल और आलोचनावादी हो सकती हैं (विशेषकर जब संख्या सिद्धांत में अन्य गहरी तकनीकों के साथ संयुक्त) और संपूर्ण पाठ्यपुस्तकें संख्या सिद्धांत के इस एकल उपक्षेत्र के लिए समर्पित की गई हैं; एक उत्कृष्ट संदर्भ है {{harv|Halberstam|Richert|1974}} और एक अधिक आधुनिक पाठ है {{harv|Iwaniec|Friedlander|2010}}. | ||
इस लेख में चर्चा की गई चालनी विधियाँ [[पूर्णांक गुणनखंडन]] चालनी विधियों जैसे कि [[द्विघात छलनी|द्विघात चालनी]] और सामान्य संख्या क्षेत्र चलनी से निकटता से संबंधित नहीं हैं। वे गुणनखंडन विधियाँ एराटोस्थनीज की चालनी के विचार का उपयोग कुशलतापूर्वक यह निर्धारित करने के लिए करती हैं कि संख्याओं की सूची के किन सदस्यों को पूरी तरह से छोटे अभाज्य संख्याओं में विभाजित किया जा सकता है। | इस लेख में चर्चा की गई चालनी विधियाँ [[पूर्णांक गुणनखंडन]] चालनी विधियों जैसे कि [[द्विघात छलनी|द्विघात चालनी]] और सामान्य संख्या क्षेत्र चलनी से निकटता से संबंधित नहीं हैं। वे गुणनखंडन विधियाँ एराटोस्थनीज की चालनी के विचार का उपयोग कुशलतापूर्वक यह निर्धारित करने के लिए करती हैं कि संख्याओं की सूची के किन सदस्यों को पूरी तरह से छोटे अभाज्य संख्याओं में विभाजित किया जा सकता है। |
Revision as of 16:18, 7 July 2023
चालनी सिद्धांत संख्या सिद्धांत में सामान्य तकनीकों का एक सेट है, जिसे पूर्णांकों के छने हुए सेटों की गणना करने, या अधिक यथार्थवादी रूप से आकार का अनुमान लगाने के लिए डिज़ाइन किया गया है। छने हुए सेट का प्रोटोटाइपिक उदाहरण कुछ निर्धारित सीमा X तक अभाज्य संख्याओं का सेट है। इसके अनुरूप, चालनी का प्रोटोटाइपिक उदाहरण एराटोस्थनीज की चालनी, या अधिक सामान्य पौराणिक चालनी है। इन विधि का उपयोग करके अभाज्य संख्याओं पर सीधा हमला जल्द ही त्रुटि शब्दों के संचय के रास्ते में स्पष्ट रूप से दुर्गम बाधाओं तक पहुँच जाता है। बीसवीं शताब्दी में संख्या सिद्धांत के प्रमुख पहलुओं में से एक में, चालनी क्या होनी चाहिए, इसके एक अनुभवहीन विचार के साथ सामने वाले हमले की कुछ कठिनाइयों से बचने के विधि खोजे गए थे।
एक सफल दृष्टिकोण संख्याओं के एक विशिष्ट छने हुए सेट (उदाहरण के लिए अभाज्य संख्याओं का सेट) को दूसरे, सरल सेट (उदाहरण के लिए लगभग अभाज्य संख्याओं का सेट) द्वारा अनुमानित करना है, जो सामान्यतः मूल सेट से कुछ बड़ा होता है, और विश्लेषण करना आसान होता है। अधिक परिष्कृत चालनी भी सीधे सेटों के साथ काम नहीं करती हैं, किंतु इन सेटों पर सावधानीपूर्वक चुने गए वजन कार्यों के अनुसार उनकी गिनती करती हैं (इन सेटों के कुछ तत्वों को दूसरों की तुलना में अधिक "वजन" देने के विकल्प)। इसके अतिरिक्त, कुछ आधुनिक अनुप्रयोगों में, चालनी का उपयोग छने हुए सेट के आकार का अनुमान लगाने के लिए नहीं किया जाता है, किंतु एक ऐसे फलन का उत्पादन करने के लिए किया जाता है जो सेट पर बड़ा होता है और ज्यादातर इसके बाहर छोटा होता है, जबकि सेट के विशिष्ट फलन की तुलना में विश्लेषण करना आसान होता है।
मूल चालनी सिद्धांत
अंकन की जानकारी के लिए अंत में देखें।
हम गैर-ऋणात्मक संख्याओं के कुछ गणनीय अनुक्रम से प्रारंभ करते हैं। सबसे मूलभूत स्थिति में यह क्रम किसी सेट का केवल संकेतक फलन है जिसे हम छानना चाहते हैं। चूँकि यह अमूर्तन अधिक सामान्य स्थितियों की अनुमति देता है। इसके बाद हम अभाज्य संख्याओं का एक सामान्य सेट पेश करते हैं जिसे सिफ्टिंग सीमा कहा जाता है और एक फलन के रूप में तक उनका उत्पाद होता है
.
चालनी सिद्धांत का लक्ष्य छानने के कार्य का अनुमान लगाना है
के स्थिति में यह केवल संख्याओं के उपसमूह की कार्डिनैलिटी की गणना करता है, जो कि के अभाज्य कारकों के सहअभाज्य हैं।
लीजेंड्रे की पहचान
हम लिजेंड्रे की पहचान के साथ छानने के कार्य को फिर से लिख सकते हैं
मोबियस फलन और के तत्वों से प्रेरित कुछ फलन का उपयोग करते है ।
उदाहरण
मान लीजिए कि और मोबियस फलन प्रत्येक प्राइम के लिए नकारात्मक है, इसलिए हमें मिलता है
सर्वांगसमता योग का अनुमान
तब कोई यह मान लेता है कि को इस प्रकार लिखा जा सकता है
जहाँ एक घनत्व है, जिसका अर्थ है एक गुणात्मक कार्य
और X, का एक सन्निकटन है और कुछ शेष पद है। छानने का कार्य बन जाता है
या संक्षेप में
फिर कोई के लिए क्रमशः और की ऊपरी और निचली सीमाएं खोजकर सिफ्टिंग फ़ंक्शन का अनुमान लगाने का प्रयास करता है।
छानने के कार्य का आंशिक योग बारी-बारी से अधिक और कम होता है, इसलिए शेष अवधि बहुत बड़ी होगी। इसे सुधारने के लिए ब्रून का विचार यह था कि सिफ्टिंग फ़ंक्शन में को एक वजन अनुक्रम के साथ प्रतिस्थापित किया जाए, जिसमें प्रतिबंधित मोबियस फ़ंक्शन सम्मिलित हों। दो उपयुक्त अनुक्रमों और को चुनना और सिफ्टिंग कार्यों को से निरूपित करना और , कोई भी मूल स्थानांतरण कार्यों के लिए निचली और ऊपरी सीमाएं प्राप्त कर सकता है
तब से गुणनात्मक है, कोई पहचान के साथ भी काम कर सकता है
नोटेशन: नोटेशन के संबंध में सावधानी का एक शब्द, साहित्य में व्यक्ति अतिरिक्त सेट के साथ अनुक्रमों के सेट की पहचान करता है। इसका अर्थ यह है कि कोई अनुक्रम को परिभाषित करने के लिए लिखता है। इसके अतिरिक्त साहित्य में योग को कभी-कभी किसी सेट की कार्डिनैलिटी के रूप में नोट किया जाता है, जबकि हमने को पहले से ही इस सेट की कार्डिनैलिटी के रूप में परिभाषित किया है। हमने और . के सबसे बड़े सामान्य भाजक के लिए अभाज्य संख्याओं और के सेट को दर्शाने के लिए का उपयोग किया।
छानने के प्रकार
आधुनिक चालनी में ब्रून चालनी , सेलबर्ग चलनी, तुरान चालनी , [[बड़ी चालनी ]], बड़ी चालनी और गोल्डस्टन-पिंटज़-येल्ड्रिम चालनी सम्मिलित हैं। चालनी सिद्धांत का एक मूल उद्देश्य संख्या सिद्धांत में जुड़वां अभाज्य अनुमान जैसे अनुमानों को सिद्ध करने का प्रयास करना था। जबकि चालनी सिद्धांत के मूल व्यापक उद्देश्य अभी भी अधिक सीमा तक अप्राप्त हैं, कुछ आंशिक सफलताएँ मिली हैं, विशेष रूप से अन्य संख्या सैद्धांतिक उपकरणों के संयोजन में मुख्य आकर्षण में सम्मिलित हैं:
- ब्रून का प्रमेय, जो दर्शाता है कि जुड़वां अभाज्य संख्याओं के व्युत्क्रमों का योग अभिसरण करता है (जबकि सभी अभाज्य अभाज्य संख्याओं के व्युत्क्रमों का योग भिन्न होता है);
- चेन का प्रमेय, जो दिखाता है कि अनंत रूप से कई अभाज्य संख्याएँ हैं जैसे कि p + 2 या तो एक अभाज्य है या एक अर्ध अभाज्य (दो अभाज्य संख्याओं का गुणनफल); चेन जिंगरुन का एक समीप से संबंधित प्रमेय यह प्रमाणित करता है कि प्रत्येक पर्याप्त बड़ी सम संख्या एक अभाज्य और दूसरी संख्या का योग है जो या तो एक अभाज्य या अर्धभाज्य है। इन्हें क्रमशः जुड़वां प्राइम अनुमान और गोल्डबैक अनुमान से लगभग चूक माना जा सकता है।
- चालनी सिद्धांत की मौलिक प्रमेयिका, जो प्रमाणित करती है कि यदि कोई एन संख्याओं के एक सेट को छान रहा है, तो वह पुनरावृत्तियों के बाद चालनी में बचे तत्वों की संख्या का स्पष्ट अनुमान लगा सकता है, परन्तु कि है पर्याप्त रूप से छोटे (1/10 जैसे अंश यहां अधिक विशिष्ट हैं)। यह लेम्मा सामान्यतः अभाज्य संख्याओं को छानने के लिए बहुत अशक्त है (जिसके लिए सामान्यतः पुनरावृत्तियों जैसी किसी चीज की आवश्यकता होती है), किंतु लगभग अभाज्य संख्याओं के संबंध में परिणाम प्राप्त करने के लिए यह पर्याप्त हो सकती है।
- फ्रीडलैंडर-इवानीक प्रमेय, जो प्रमाणित करता है कि के रूप के अनंत रूप से कई अभाज्य हैं।
- झांग का प्रमेय (Zhang 2014), जो दर्शाता है कि एक सीमित दूरी के अंदर अभाज्य संख्याओं के अनंत जोड़े हैं। मेनार्ड-ताओ प्रमेय ((मेनार्ड 2015) ) झांग के प्रमेय को अभाज्य संख्याओं के इच्छानुसार से लंबे अनुक्रमों के लिए सामान्यीकृत करता है।
चालनी सिद्धांत की तकनीक
चालनी सिद्धांत की तकनीकें अधिक शक्तिशाली हो सकती हैं, किंतु वे समता समस्या (चालनी सिद्धांत) नामक एक बाधा से सीमित प्रतीत होती हैं, जो सामान्यतः यह प्रमाणित करती है कि चालनी सिद्धांत विधियों में विषम संख्या में अभाज्य कारकों के साथ संख्याओं के बीच अंतर करने में अत्यधिक कठिनाई होती है। और अभाज्य गुणनखंडों की सम संख्या वाली संख्याएँ का यह समता समस्या अभी भी बहुत अच्छी तरह से समझी नहीं गई है।
संख्या सिद्धांत में अन्य विधि की तुलना में चालनी सिद्धांत तुलनात्मक रूप से प्राथमिक है इस अर्थ में कि इसे बीजगणितीय संख्या सिद्धांत या विश्लेषणात्मक संख्या सिद्धांत से परिष्कृत अवधारणाओं की आवश्यकता नहीं है। फिर भी अधिक उन्नत चालनी अभी भी बहुत जटिल और आलोचनावादी हो सकती हैं (विशेषकर जब संख्या सिद्धांत में अन्य गहरी तकनीकों के साथ संयुक्त) और संपूर्ण पाठ्यपुस्तकें संख्या सिद्धांत के इस एकल उपक्षेत्र के लिए समर्पित की गई हैं; एक उत्कृष्ट संदर्भ है (Halberstam & Richert 1974) और एक अधिक आधुनिक पाठ है (Iwaniec & Friedlander 2010).
इस लेख में चर्चा की गई चालनी विधियाँ पूर्णांक गुणनखंडन चालनी विधियों जैसे कि द्विघात चालनी और सामान्य संख्या क्षेत्र चलनी से निकटता से संबंधित नहीं हैं। वे गुणनखंडन विधियाँ एराटोस्थनीज की चालनी के विचार का उपयोग कुशलतापूर्वक यह निर्धारित करने के लिए करती हैं कि संख्याओं की सूची के किन सदस्यों को पूरी तरह से छोटे अभाज्य संख्याओं में विभाजित किया जा सकता है।
साहित्य
- Cojocaru, Alina Carmen; Murty, M. Ram (2006), An introduction to sieve methods and their applications, London Mathematical Society Student Texts, vol. 66, Cambridge University Press, ISBN 0-521-84816-4, MR 2200366
- Motohashi, Yoichi (1983), Lectures on Sieve Methods and Prime Number Theory, Tata Institute of Fundamental Research Lectures on Mathematics and Physics, vol. 72, Berlin: Springer-Verlag, ISBN 3-540-12281-8, MR 0735437
- Greaves, George (2001), Sieves in number theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 43, Berlin: Springer-Verlag, doi:10.1007/978-3-662-04658-6, ISBN 3-540-41647-1, MR 1836967
- Harman, Glyn (2007). प्राइम-डिटेक्टिंग छलनी. London Mathematical Society Monographs. Vol. 33. Princeton, NJ: Princeton University Press. ISBN 978-0-691-12437-7. MR 2331072. Zbl 1220.11118.
- Halberstam, Heini; Richert, Hans-Egon (1974). छलनी के तरीके. London Mathematical Society Monographs. Vol. 4. London-New York: Academic Press. ISBN 0-12-318250-6. MR 0424730.
- Iwaniec, Henryk; Friedlander, John (2010), Opera de cribro, American Mathematical Society Colloquium Publications, vol. 57, Providence, RI: American Mathematical Society, ISBN 978-0-8218-4970-5, MR 2647984
- Hooley, Christopher (1976), Applications of sieve methods to the theory of numbers, Cambridge Tracts in Mathematics, vol. 70, Cambridge-New York-Melbourne: Cambridge University Press, ISBN 0-521-20915-3, MR 0404173
- Maynard, James (2015). "अभाज्य संख्याओं के बीच छोटे अंतराल". Annals of Mathematics. 181 (1): 383–413. arXiv:1311.4600. doi:10.4007/annals.2015.181.1.7. MR 3272929.
- Tenenbaum, Gérald (1995), Introduction to Analytic and Probabilistic Number Theory, Cambridge studies in advanced mathematics, vol. 46, Translated from the second French edition (1995) by C. B. Thomas, Cambridge University Press, pp. 56–79, ISBN 0-521-41261-7, MR 1342300
- Zhang, Yitang (2014). "अभाज्य संख्याओं के बीच सीमित अंतराल". Annals of Mathematics. 179 (3): 1121–1174. doi:10.4007/annals.2014.179.3.7. MR 3171761.
बाहरी संबंध
- Bredikhin, B.M. (2001) [1994], "Sieve method", Encyclopedia of Mathematics, EMS Press