गूगल रिसर्चर, लॉन्ग आउट ऑफ मैथ, क्रैक डेविलिश प्रॉब्लम अबाउट सेट्स

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

साक्स और गिल्मर ने दोपहर का भोजन किया, लेकिन उन्होंने गणित के बारे में बात नहीं की। वास्तव में, 2015 में रटगर्स में खत्म होने के बाद से गिल्मर ने गणित के बारे में गंभीरता से नहीं सोचा था। तभी उन्होंने फैसला किया कि वह अकादमिक क्षेत्र में करियर नहीं बनाना चाहते हैं और इसके बजाय खुद को प्रोग्राम करना सिखाना शुरू कर दिया है। जैसा कि उन्होंने और सैक्स ने खाया, गिल्मर ने अपने पुराने गुरु को Google में अपनी नौकरी के बारे में बताया, जहाँ वे मशीन लर्निंग और आर्टिफिशियल इंटेलिजेंस पर काम करते हैं।

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

"मुझे लगता है कि बहुत से लोग समस्या के बारे में तब तक सोचते हैं जब तक वे संतुष्ट नहीं हो जाते कि वे समझते हैं कि यह कठिन क्यों है। मैंने शायद अधिकांश लोगों की तुलना में इस पर अधिक समय बिताया है," गिल्मर ने कहा।

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

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

आधा भरा

संघ-बंद अनुमान सेट नामक संख्याओं के संग्रह के बारे में है, जैसे कि {1, 2} और {2, 3, 4}। आप सेट पर संचालन कर सकते हैं, जिसमें उनका संघ लेना शामिल है, जिसका अर्थ है उन्हें जोड़ना। उदाहरण के लिए, {1, 2} और {2, 3, 4} का मिलन {1, 2, 3, 4} है।

सेट का एक संग्रह, या परिवार, "यूनियन-क्लोज्ड" माना जाता है, यदि परिवार में किन्हीं दो सेटों का मिलन परिवार में किसी भी मौजूदा सेट के बराबर होता है। उदाहरण के लिए, चार सेटों के इस परिवार पर विचार करें:

{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}।

किसी भी जोड़ी को मिलाएं और आपको एक ऐसा सेट मिलता है जो पहले से ही परिवार में है, जिससे परिवार संघ बंद हो जाता है।

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

फ्रेंकल ने अनुमान लगाया कि यदि समुच्चयों का एक परिवार संघ-बंद है, तो इसमें कम से कम एक तत्व (या संख्या) होना चाहिए जो कम से कम आधे सेट में दिखाई दे। यह दो कारणों से एक प्राकृतिक सीमा थी।

सबसे पहले, संघ-बंद परिवारों के आसानी से उपलब्ध उदाहरण हैं जिनमें सभी तत्व ठीक 50% सेट में दिखाई देते हैं। उदाहरण के लिए, सभी अलग-अलग सेटों की तरह, आप संख्या 1 से 10 तक बना सकते हैं। ऐसे 1,024 सेट हैं, जो संघ-बंद परिवार बनाते हैं, और 10 तत्वों में से प्रत्येक 512 में प्रकट होता है। और दूसरा, जिस समय फ्रेंकल ने अनुमान लगाया था उस समय किसी ने संघ-बंद परिवार का उदाहरण प्रस्तुत नहीं किया था जिसमें अनुमान सही नहीं था।

तो 50% सही भविष्यवाणी की तरह लग रहा था।

इसका मतलब यह नहीं था कि इसे साबित करना आसान था। फ्रेंकल के शोधपत्र के बाद के वर्षों में, बहुत कम परिणाम आए हैं। गिल्मर के काम से पहले, वे कागजात केवल थ्रेसहोल्ड स्थापित करने में कामयाब रहे जो कि परिवार में सेट की संख्या के साथ भिन्न होते हैं (जैसा कि सभी आकारों के सेट परिवारों के लिए समान 50% सीमा होने के विपरीत)।

"ऐसा लगता है कि यह आसान होना चाहिए, और यह बहुत सी समस्याओं के समान है जो आसान हैं, लेकिन इसने हमलों का विरोध किया है," कहा विल सॉविन कोलंबिया विश्वविद्यालय के।

प्रगति की कमी ने समस्या की पेचीदा प्रकृति और इस तथ्य को प्रतिबिंबित किया कि कई गणितज्ञ इसके बारे में नहीं सोचना पसंद करते थे; उन्हें चिंता थी कि वे एक भ्रामक समस्या का पीछा करते हुए अपने करियर के वर्षों को खो देंगे जिसे हल करना असंभव था। गिल्मर को 2013 का एक दिन याद है जब वह सक्स के कार्यालय गए और संघ-बंद अनुमान लगाया। उनके सलाहकार - जिन्होंने अतीत में स्वयं समस्या से संघर्ष किया था - ने उन्हें लगभग कमरे से बाहर निकाल दिया।

"माइक ने कहा, 'जस्टिन, आप मुझे इस समस्या के बारे में फिर से सोचने पर मजबूर कर देंगे और मैं ऐसा नहीं करना चाहता," गिल्मर ने कहा।

अनिश्चितता की एक अंतर्दृष्टि

रटगर्स की अपनी यात्रा के बाद, गिल्मर ने समस्या को अपने दिमाग में घुमा लिया, यह समझने की कोशिश कर रहे थे कि यह इतना कठिन क्यों था। उन्होंने अपने आप को एक बुनियादी तथ्य से प्रेरित किया: यदि आपके पास 100 सेटों का परिवार है, तो दो को चुनने और उनका मिलन करने के 4,950 अलग-अलग तरीके हैं। फिर उन्होंने खुद से पूछा: यह कैसे संभव है कि 4,950 अलग-अलग यूनियनों का नक्शा सिर्फ 100 सेटों पर वापस आ जाए, अगर उन यूनियनों में कम से कम कुछ आवृत्ति के साथ कोई तत्व नहीं दिखाई देता है?

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

20वीं शताब्दी के पूर्वार्द्ध में सूचना सिद्धांत का विकास हुआ, जो क्लॉड शैनन के 1948 के पेपर के साथ सबसे प्रसिद्ध है, "संचार का एक गणितीय सिद्धांत।” पेपर ने संदेश भेजने के लिए आवश्यक जानकारी की मात्रा की गणना करने का एक सटीक तरीका प्रदान किया, जो संदेश के बारे में अनिश्चितता की मात्रा के आधार पर होगा। यह लिंक - सूचना और अनिश्चितता के बीच - शैनन की उल्लेखनीय, मौलिक अंतर्दृष्टि थी।

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

संख्याओं के समुच्चय में निहित जानकारी पर भी यही सोच लागू होती है। यदि मेरे पास संघ-बंद सेटों का परिवार है - 1,024 से 1 की संख्या से बने 10 सेट कहें - मैं यादृच्छिक रूप से दो सेट चुन सकता हूं। तब मैं आपको प्रत्येक सेट के तत्वों के बारे में बता सकता था। उस संदेश को भेजने में लगने वाली जानकारी की मात्रा उन तत्वों के बारे में अनिश्चितता की मात्रा को दर्शाती है: उदाहरण के लिए, 50% संभावना है कि पहले सेट में पहला तत्व 1 है (क्योंकि 1 आधे सेट में दिखाई देता है) परिवार), जैसे कि 50% संभावना है कि उचित सिक्के के फ़्लिप के क्रम में पहला परिणाम हेड है।

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

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

नहीं की तुलना में अधिक होने की संभावना

Google पर अपना काम खत्म करने के बाद, गिल्मर ने रात में समस्या पर काम किया, और सप्ताहांत पर अक्टूबर के दूसरे छमाही और नवंबर की शुरुआत में काम किया। उन्हें उन विचारों से प्रोत्साहन मिला जो गणितज्ञों के एक समूह ने वर्षों पहले खोजे थे खुला सहयोग टिम गोवर्स नामक एक प्रमुख गणितज्ञ के ब्लॉग पर। उन्होंने अपनी ओर से एक पाठ्यपुस्तक के साथ भी काम किया ताकि वे उन सूत्रों को देख सकें जिन्हें वे भूल गए थे।

"आपको लगता है कि कोई व्यक्ति जो एक महान परिणाम के साथ आता है, उसे अध्याय 2 से परामर्श नहीं करना चाहिए सूचना सिद्धांत के तत्व, लेकिन मैंने किया," गिल्मर ने कहा।

गिल्मर की रणनीति एक संघ-बंद परिवार की कल्पना करना थी जिसमें सभी सेटों के 1% में भी कोई तत्व दिखाई नहीं देता था - एक प्रति उदाहरण, जो वास्तव में अस्तित्व में था, फ्रेंकल के अनुमान को गलत साबित करेगा।

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

अगला, इस संभावना के बारे में सोचें कि ए और बी के मिलन में 1 है। यह अभी भी असंभव है, लेकिन यह व्यक्तिगत सेटों में से किसी एक में दिखाई देने वाली बाधाओं से अधिक संभावना है। यह ए में दिखाई देने वाली संभावना का योग है और बी में दिखाई देने वाली संभावना दोनों में दिखाई देने वाली संभावना को घटाती है। तो, शायद सिर्फ 2% से कम।

यह अभी भी कम है, लेकिन यह 50-50 प्रस्ताव के करीब है। यानी रिजल्ट शेयर करने के लिए ज्यादा जानकारी की जरूरत होती है। दूसरे शब्दों में, यदि कोई संघ-बंद परिवार है जिसमें सभी सेटों के कम से कम 1% में कोई तत्व नहीं दिखाई देता है, तो दो सेटों के संघ में स्वयं सेटों की तुलना में अधिक जानकारी है।

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

इस बिंदु पर फ्रैंकल के अनुमान पर गिल्मर बंद होने लगा था। ऐसा इसलिए है क्योंकि यह प्रदर्शित करना आसान है कि संघ-बंद परिवार में, दो सेटों के संघ में आवश्यक रूप से स्वयं सेटों की तुलना में कम जानकारी होती है - अधिक नहीं।

यह देखने के लिए, उस संघ-बंद परिवार के बारे में सोचें जिसमें 1,024 अलग-अलग सेट हैं जिन्हें आप 1 से 10 तक की संख्या से बना सकते हैं। यदि आप उन दो सेटों को यादृच्छिक रूप से चुनते हैं, तो औसतन आप पांच तत्वों वाले सेट के साथ समाप्त हो जाएंगे। (उन 1,024 सेटों में से, 252 में पांच तत्व शामिल हैं, जो कि सबसे सामान्य सेट आकार है।) आप लगभग सात तत्वों वाले संघ के साथ भी समाप्त होने की संभावना रखते हैं। लेकिन सात तत्वों वाले सेट बनाने के केवल 120 अलग-अलग तरीके हैं।

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

इसके साथ ही गिल्मर के पास एक सबूत था। वह जानता था कि अगर सेट के 1% में भी कोई तत्व नहीं दिखाई देता है, तो संघ को अधिक जानकारी रखने के लिए मजबूर होना पड़ता है। लेकिन संघ में कम जानकारी होनी चाहिए। इसलिए कम से कम एक तत्व होना चाहिए जो कम से कम 1% सेट में दिखाई दे।

पुश टू 50

जब गिल्मर ने 16 नवंबर को अपना प्रमाण पोस्ट किया, तो उन्होंने एक नोट शामिल किया कि उन्होंने सोचा कि पूर्ण अनुमान के प्रमाण के और भी करीब पहुंचने के लिए अपनी पद्धति का उपयोग करना संभव है, संभावित रूप से दहलीज को 38% तक बढ़ाना।

पांच दिन बाद, तीन विभिन्न समूहों गणितज्ञों ने ऐसा करने के लिए गिल्मर के काम पर बने एक-दूसरे के घंटों के भीतर कागजात पोस्ट किए। अतिरिक्त कागजात पीछा किया, लेकिन ऐसा लगता है कि आरंभिक प्रस्फुटन ने गिल्मर के तरीकों को जहाँ तक ले जाया है; 50% तक पहुंचने की संभावना अतिरिक्त नए विचार लेगी।

फिर भी, फॉलो-अप पेपर के कुछ लेखकों के लिए, 38% प्राप्त करना अपेक्षाकृत सीधा था, और उन्होंने सोचा कि गिल्मर ने इसे स्वयं क्यों नहीं किया। सबसे सरल व्याख्या सही निकली: गणित के आधे दशक से अधिक समय के बाद, गिल्मर को यह नहीं पता था कि इसे खींचने के लिए आवश्यक कुछ तकनीकी विश्लेषणात्मक कार्य कैसे करें।

"मैं थोड़ा कठोर था, और ईमानदार होने के लिए, मैं फंस गया था," गिल्मर ने कहा। "लेकिन मैं यह देखने के लिए उत्सुक था कि समुदाय इसे कहाँ ले जाएगा।"

फिर भी गिल्मर को लगता है कि जिन परिस्थितियों ने उन्हें अभ्यास से बाहर कर दिया था, शायद उन्हीं परिस्थितियों ने उनके प्रमाण को संभव बनाया।

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

भूल सुधार: जनवरी ७,२०२१
मूल शीर्षक में गिल्मर को "Google इंजीनियर" कहा गया था। दरअसल, वह एक शोधकर्ता हैं।