गणितज्ञ "सूरजमुखी की समस्या" को बताने लगे

60 साल पुरानी परिकल्पना को हल करने में एक बड़ी सफलता यह बताती है कि यादृच्छिक प्रणालियों के विकास के साथ उनमें कैसे क्रम दिखाई देने लगता है

गणितज्ञों और कंप्यूटर वैज्ञानिकों की एक टीम ने आखिरकार, पहली नज़र में, एक सरल कार्य को हल करने में प्रगति का प्रदर्शन किया, जिसने लगभग छह दशकों तक शोधकर्ताओं को त्रस्त किया।

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

“इस काम में, एक गणितीय विचार खुद को एक नए तरीके से प्रकट करता है, जो हमारे समय का मुख्य विचार बन जाएगा। इसका परिणाम स्वयं आश्चर्यजनक है, ”यरूशलेम में हिब्रू विश्वविद्यालय के गिल कलाई ने कहा।

सूरजमुखी की परिकल्पना वस्तुओं के सेट, या सेट को संदर्भित करती है। एक्स प्लेन पर बिंदुओं के सेट का उपयोग करके कल्पना करना सबसे आसान है। सबसे पहले, एक निश्चित संख्या का चयन करें जो प्रत्येक सेट में शामिल किया जाएगा। फिर यादृच्छिक छोरों को ड्रा करें ताकि प्रत्येक लूप, या सेट में चयनित अंकों की संख्या शामिल हो। छोरों को काट सकते हैं, और कुछ बिंदु कई सेटों में गिर सकते हैं, वेन आरेख जैसा दिखता है।

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

यदि आप बिंदुओं के इस सामान्य सबसेट को हटाते हैं, तो तीन सेट शून्य के आसपास स्थित होंगे, और एक दूसरे से पूरी तरह से अलग हो जाएंगे - जैसे सूरजमुखी के अंधेरे मध्य के आसपास की पंखुड़ियाँ। सबसे सरल सूरजमुखी को तीन सेट माना जाता है जो किसी अन्य के साथ अंतर नहीं करता है; इस तरह के द्वीपों को असहमति सेट कहा जाता है।



एर्दो और राडो ने सुझाव दिया कि जैसे-जैसे लूप की संख्या बढ़ती है, ऐसे सूरजमुखी अनिवार्य रूप से दिखाई देंगे, या तो डिसऑइंट सेट के रूप में, या सेट के रूप में एक दूसरे पर संकेतित तरीके से सुपरइम्पोज किए गए। यह सूरजमुखी की परिकल्पना गणित के एक अधिक सामान्य क्षेत्र का हिस्सा है जिसे रैमसे सिद्धांत कहा जाता है, जो अध्ययन करता है कि यादृच्छिक प्रणालियों के बढ़ते आकार के साथ उनमें कैसे क्रम दिखाई देने लगता है।

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

एर्दो और राडो ने जानना चाहा कि सूरजमुखी की गारंटी के लिए कितने सेट और किस आकार की जरूरत है। उन्होंने प्रत्येक सेट में अंकों की संख्या को दर्शाते हुए, पैरामीटर w को परिभाषित करके समस्या को हल करने की दिशा में पहला मामूली कदम उठाया। तब उन्होंने यह साबित कर दिया कि यह आकार ^{w के} सेटों के w ^{w के} बारे में सुनिश्चित करने के लिए है कि सूरजमुखी को तीन सेटों से युक्त होने की गारंटी दी जाती है। तो, यदि आप 100 अंकों के सेट का उपयोग करना चाहते हैं, तो आपको सूरजमुखी की उपस्थिति की गारंटी देने के लिए ¹⁰⁰ से ¹⁰⁰ सेट की आवश्यकता होगी।

उसी समय, एर्दो और राडो ने सुझाव दिया कि वास्तव में एक सूरजमुखी की गारंटी देने वाले सेटों की संख्या w ^{w की} तुलना में बहुत कम है - और डिग्री w में एक स्थिर की तरह अधिक है (उदाहरण के लिए, 3 ^w या 80 ^w या 5 000 000 ^w )। हालांकि, उन्हें अपना अनुमान साबित करने का कोई तरीका नहीं मिला।

"उन्होंने कहा कि यह कार्य बेहद सरल लग रहा था, और वे आश्चर्यचकित थे कि वे इसमें प्रगति हासिल नहीं कर सके।"

और वे अकेले नहीं थे। अपने पहले परिणाम और 60 साल बाद सामने आए इस नए कार्य की अवधि में, केवल दो गणितज्ञों ने इस मुद्दे पर कम से कम कुछ प्रगति की - और फिर वे धीरे-धीरे चले गए, 1997 में एक कदम और इस साल दूसरा ।

वाशिंगटन विश्वविद्यालय के अनूप राव ने कहा, "सभी ने पहले से ही उन सभी विचारों को आजमाया है, जो लोग सहज महसूस करते हैं ।" "और कोई भी Erd ands और Rado द्वारा निर्धारित बेस लाइन में सुधार करने में सक्षम नहीं था।"

लेकिन नए सबूतों ने एक बड़ी सफलता हासिल की।

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

"जब आपके पास तत्वों का एक सेट होता है जो सेट के एक बड़े समूह से संबंधित होता है, तो आप इस संरचना का उपयोग कर सकते हैं," सूरजमुखी की खोज के लिए, लव्ट ने कहा।

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

एक दूसरे, अधिक जटिल परिदृश्य में, वे विश्लेषण करते हैं कि क्या होगा यदि सेट दृढ़ता से प्रतिच्छेद नहीं करते हैं। इस मामले में, सूरजमुखी को प्राप्त करने का सबसे संभावित तरीका तीन डिसऑइंटमेंट सेट लेना है। हालांकि, यह साबित करने के लिए कि तीन अलग-अलग सेट अधिक थोड़े इंटरसेक्टिंग सेट में छिपे हुए हैं, आसान नहीं है।

यह वह जगह है जहाँ कंप्यूटर विज्ञान खेलने में आता है। दो सह-लेखक, लव्ट और झांग, कई सालों से कोशिश कर रहे हैं कि सूरजमुखी की समस्या का विश्लेषण करने के लिए उन्हीं उपकरणों का उपयोग किया जाए, जिनका उपयोग कंप्यूटर वैज्ञानिक बूलियन कार्यों का अध्ययन करने के लिए करते हैं। ये कार्य बिट्स - शून्य और शून्य के अनुक्रम पर कार्य करते हैं - और अंत में एक बिट का उत्पादन करते हैं, जो कि एक कम्प्यूटेशनल कथन सही है या गलत है। उदाहरण के लिए, एक बूलियन फ़ंक्शन को 1 वापस करने के लिए प्रोग्राम किया जा सकता है यदि इनपुट बिट्स में से कम से कम 1 एक है, और 0 यदि इनपुट बिट्स में से कोई भी 1 नहीं है।

तीन साल पहले, लव्ट और झांग ने महसूस किया कि एक ही सवाल के रूप में सामने आ सकता है कि क्या तीन सेटों में से कोई एक सेट है जो दृढ़ता से सेट नहीं करता है। सबसे पहले, सेट में प्रत्येक बिंदु पर एक लेबल असाइन करें: 1 यदि यह केवल इस सेट में निहित है, और किसी अन्य मामले में 0 है। एक बूलियन फ़ंक्शन 1 (सही) देता है यदि इनपुट पर प्रत्येक बिंदु 1 है - अर्थात, सेट का प्रत्येक बिंदु इस सेट में विशेष रूप से मौजूद है, जो इस सेट को असम्बद्ध बनाता है। सच्चा परिणाम बताता है कि सूरजमुखी खोजने के लिए उपयुक्त परिस्थितियां हैं।

इस पत्राचार को सख्ती से साबित करते हुए, शोधकर्ताओं ने सूरजमुखी की समस्या पर हमला करने के लिए बूलियन कार्यों के बारे में व्यापक ज्ञान का इस्तेमाल किया, जिसमें पहले संसाधनों की कमी थी। उन्होंने साबित किया कि (लॉग डब्ल्यू) ^{डब्ल्यू} सेट सूरजमुखी पाने के लिए पर्याप्त हैं। इस तरह के परिणाम परिकल्पना को साबित करने के लिए पर्याप्त नहीं है कि डिग्री डब्ल्यू में एक निश्चित निरंतर एक सूरजमुखी प्राप्त करने के लिए पर्याप्त है। लेकिन यह एर्दो और राडो द्वारा प्राप्त w की तुलना में बेहतर परिणाम का एक क्रम है, और यह मोटे तौर पर सेट की संख्या के साथ मेल खाता है जो उन्होंने भविष्यवाणी की थी।

आधी सदी की असफलताओं के बाद, नया काम बताता है कि हम जल्द ही एक पूर्ण समाधान देखेंगे। यह इस बात की समझ को भी बेहतर बनाता है कि मौका के जंगली गणितीय प्रकृति में अनिवार्य रूप से विशेष रूप कैसे उत्पन्न होते हैं।