गणितज्ञों ने 'गोलाकार घन' बनाने की खोज पूरी की

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

या इसलिए पप्पू और अन्य ने परिकल्पना की। सहस्राब्दी के लिए, कोई भी साबित नहीं कर सका कि हेक्सागोन इष्टतम थे - अंत में, 1999 में, गणितज्ञ थॉमस हेल्स ने दिखाया कि कोई अन्य आकार बेहतर नहीं कर सकता। आज, गणितज्ञ अभी भी यह नहीं जानते हैं कि कौन से आकार न्यूनतम संभव सतह क्षेत्र के साथ तीन या अधिक आयामों को टाइल कर सकते हैं।

यह "फोम" समस्या व्यापक अनुप्रयोगों में बदल गई है - साबुन के बुलबुले (या फोम) के व्यवहार का अध्ययन करने वाले भौतिकविदों और क्रिस्टल की संरचना का विश्लेषण करने वाले रसायनज्ञों के लिए, गणितज्ञों के लिए स्फेयर-पैकिंग व्यवस्था की खोज और सांख्यिकीविदों के लिए प्रभावी डेटा-प्रोसेसिंग तकनीक विकसित करना .

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

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

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

"यह कहानी का बहुत अच्छा अंत है," रेगेव ने कहा।

घनाकार फोम

गणितज्ञों ने फोम समस्या के अन्य संस्करणों पर विचार किया है - इसमें क्या होता है यदि आपको केवल पूर्णांक जाली कहे जाने वाले स्थान के अनुसार विभाजन करने की अनुमति है। समस्या के उस संस्करण में, आप समान दूरी वाले बिंदुओं (प्रत्येक 1 इकाई के अलावा) का एक वर्ग सरणी लेते हैं और उन बिंदुओं में से प्रत्येक को एक आकृति का केंद्र बनाते हैं। "क्यूबिकल" फोम की समस्या पूछती है कि जब आपको इस तरह से टाइल लगाने की आवश्यकता होगी तो न्यूनतम सतह क्षेत्र क्या होगा।

कई गुना कहे जाने वाले टोपोलॉजिकल स्पेस के गुणों को समझने के लिए शोधकर्ता शुरू में इस प्रतिबंध को लागू करने में रुचि रखते थे। लेकिन डेटा विश्लेषण और अन्य अनुप्रयोगों में प्रासंगिक होते हुए, प्रश्न ने स्वयं का जीवन लिया।

यह ज्यामितीय रूप से भी दिलचस्प है, क्योंकि यह "इष्टतम" का अर्थ बदल सकता है। उदाहरण के लिए, दो आयामों में, नियमित हेक्सागोन अब विमान को टाइल नहीं कर सकते हैं यदि उन्हें केवल क्षैतिज और ऊर्ध्वाधर दिशाओं में पूर्णांक राशियों द्वारा स्थानांतरित किया जा सकता है। (आपको उन्हें दो दिशाओं में से एक में अपरिमेय राशियों से स्थानांतरित करना होगा।)

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

ये अंतर तुच्छ लग सकते हैं, लेकिन वे उच्च आयामों में बहुत बड़े हो जाते हैं।

किसी दिए गए आयतन के सभी आकारों में, जो सतह क्षेत्र को कम करता है वह गोला है। जैसा n, आयामों की संख्या, बढ़ती है, गोले की सतह का क्षेत्रफल के वर्गमूल के अनुपात में बढ़ता है n.

लेकिन गोले खाली जगह छोड़े बिना टाइल नहीं लगा सकते। दूसरी ओर, ए nवॉल्यूम 1 कैन का डायमेंशनल क्यूब। पकड़ यह है कि इसका सतह क्षेत्र 2 हैn, इसके आयाम के सीधे अनुपात में बढ़ रहा है। वॉल्यूम 10,000 के 1-आयामी घन का सतह क्षेत्र 20,000 है - 400 से बहुत बड़ा, 10,000-आयामी क्षेत्र का अनुमानित सतह क्षेत्र।

और इसलिए शोधकर्ताओं ने सोचा कि क्या वे "गोलाकार घन" पा सकते हैं - एक आकार जो टाइल करता है nआयामी स्थान, एक घन की तरह, लेकिन जिसका सतह क्षेत्र धीरे-धीरे बढ़ता है, एक गोले की तरह।

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

अब हम जानते हैं कि ऐसा नहीं है।

कठिन समस्याओं की कठोरता

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

द्वारा 2002 में प्रस्तावित सुभाष खोट, उस समय एक स्नातक छात्र, अनुमान यह बताता है कि यदि कोई विशेष समस्या - एक जिसमें नेटवर्क के नोड्स को रंग निर्दिष्ट करना शामिल है - को ठीक से हल नहीं किया जा सकता है, तो एक अनुमानित समाधान भी खोजना बहुत कठिन है। यदि सही है, तो अनुमान शोधकर्ताओं को एक झटके में अन्य कम्प्यूटेशनल कार्यों के विशाल वर्गीकरण की जटिलता को समझने की अनुमति देगा।

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

यह पता चला है कि इनमें से कई कार्यों का अनुमानित समाधान खोजना एनपी-कठिन है। मान लें कि आप ग्राफ़ के कोने को अलग-अलग रंगों के साथ लेबल करना चाहते हैं जो बाधाओं की कुछ सूची को संतुष्ट करता है। यदि उन सभी बाधाओं को पूरा करना एनपी-मुश्किल है, तो उनमें से सिर्फ 90%, या 75%, या 50% को पूरा करने की कोशिश करने के बारे में क्या? कुछ दहलीज के नीचे, एक कुशल एल्गोरिदम के साथ आना संभव हो सकता है, लेकिन उस दहलीज से ऊपर, समस्या एनपी-हार्ड हो जाती है।

दशकों से, कंप्यूटर वैज्ञानिकों ने रुचि की विभिन्न अनुकूलन समस्याओं के लिए थ्रेसहोल्ड को कम करने का काम किया है। लेकिन कुछ सवाल इस तरह के विवरण से बचते हैं। जबकि एक एल्गोरिदम 80% सर्वोत्तम समाधान की गारंटी दे सकता है, यह 95% सर्वोत्तम समाधान प्राप्त करने के लिए एनपी-कठिन हो सकता है, जिससे 80% और 95% के बीच समस्या का समाधान एनपी-हार्ड क्षेत्र में हो जाता है।

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

लेकिन 2002 में यूजीसी के प्रस्तावित होने के तुरंत बाद, शोधकर्ताओं ने दिखाया कि यदि अनुमान सत्य है, तो आप किसी भी बाधा संतुष्टि समस्या के लिए कठोरता सीमा की आसानी से गणना कर सकते हैं। (ऐसा इसलिए है क्योंकि यूजीसी का यह भी अर्थ है कि एक ज्ञात एल्गोरिथ्म इन सभी समस्याओं के लिए सर्वोत्तम संभव सन्निकटन प्राप्त करता है।) "यह इन सभी अनुकूलन समस्याओं के लिए सटीक रूप से लिंचपिन था," ओ'डोनेल ने कहा।

और इसलिए सैद्धांतिक कंप्यूटर वैज्ञानिक यूजीसी को साबित करने के लिए तैयार हो गए - एक ऐसा कार्य जिसने अंततः उनमें से कुछ को गोलाकार घनों की खोज करने के लिए प्रेरित किया।

कठिन समस्याओं को कठिन बनाना

2005 में ओ'डॉनेल माइक्रोसॉफ्ट रिसर्च में काम कर रहे थे। वह और दो सहयोगी - उरीएल फीज, अब वीज़मैन इंस्टीट्यूट ऑफ साइंस में, और गाइ किंडलर, अब जेरूसलम के हिब्रू विश्वविद्यालय में - यूजीसी से निपटने के लिए मिलकर काम किया।

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

यदि यूजीसी सत्य है, तो इसका अर्थ यह होगा कि, कुछ यादृच्छिक ग्राफ दिए जाने पर, एक कुशल सन्निकटन एल्गोरिथम उस ग्राफ के वास्तविक अधिकतम कट के लगभग 87% के भीतर ही प्राप्त कर सकता है। कोई बेहतर करना एनपी-कठिन होगा।

Feige, Kindler और O'Donnell इसके बजाय विपरीत दिशा में जाना चाहते थे: उन्होंने यह दिखाने की आशा की कि अधिकतम कटौती का अनुमान लगाना कठिन है, और फिर इसका उपयोग UGC को साबित करने के लिए करें। उनकी योजना समानांतर दोहराव नामक तकनीक की ताकत पर निर्भर थी - एक चतुर रणनीति जो कठिन समस्याओं को कठिन बना देती है।

कहते हैं कि आप जानते हैं कि एक समस्या जिसे आप हल कर सकते हैं और जिसे आप अधिकतर हल कर सकते हैं, के बीच अंतर करना एनपी-मुश्किल है। समानांतर दोहराव आपको अधिक मजबूत कठोरता परिणाम दिखाने के लिए उस पर निर्माण करने में सक्षम बनाता है: यह उस समस्या के बीच अंतर करने के लिए एनपी-कठिन है जिसे आप हल कर सकते हैं और जिसे आप मुश्किल से हल कर सकते हैं। नोर ने कहा, "यह गैर-सहज, गहरी घटना ... आज बहुत सारे कंप्यूटर विज्ञान के दायरे में है।"

लेकिन एक पेंच है। समानांतर दोहराव हमेशा किसी समस्या की कठोरता को उतना नहीं बढ़ाता जितना कंप्यूटर वैज्ञानिक चाहते हैं। विशेष रूप से, अधिकतम कटौती की समस्या के पहलू हैं जो "समानांतर पुनरावृत्ति के लिए एक बड़ा सिरदर्द पैदा करते हैं," रेगेव ने कहा।

फीज, किंडलर और ओ'डॉनेल ने यह दिखाने पर ध्यान केंद्रित किया कि सिरदर्द के बावजूद समानांतर दोहराव काम कर सकता है। "यह वास्तव में विश्लेषण करने के लिए एक जटिल बात है," कहा डाना मोशकोविट्ज़, टेक्सास विश्वविद्यालय, ऑस्टिन में एक सैद्धांतिक कंप्यूटर वैज्ञानिक। "लेकिन यह tantalizingly करीब लग रहा था। समानांतर दोहराव ऐसा लग रहा था कि यह [मदद] इस कनेक्शन को अधिकतम कट से अनूठे गेम तक ले जाएगा।

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

समानांतर दोहराव आपको इस समस्या के एक उच्च-आयामी संस्करण पर विचार करने की अनुमति देता है - एक जिसमें आपको दिखाई देने वाले सभी विषम चक्रों को तोड़ना पड़ता है। Feige, Kindler और O'Donnell को यह दिखाने की जरूरत है कि जैसे-जैसे आयामों की संख्या बहुत बड़ी हो जाती है, आपको सभी विषम चक्रों को तोड़ने के लिए किनारों के एक बहुत बड़े अंश को हटाना होगा। अगर यह सच था, तो इसका मतलब यह होगा कि समानांतर पुनरावृत्ति इस "बेवकूफ अधिकतम-कट" समस्या की कठोरता को प्रभावी ढंग से बढ़ा सकती है।

तभी टीम ने एक जिज्ञासु संयोग की खोज की: यह व्याख्या करने का एक ज्यामितीय तरीका था कि क्या समानांतर पुनरावृत्ति उस तरह से काम करेगी जिस तरह से उन्हें उम्मीद थी। रहस्य क्यूबिकल फोम के सतह क्षेत्र में है।

नींबू से लेकर नींबू पानी तक

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

"हम ऐसे थे, ओह, क्या अजीब ज्यामिति समस्या है, लेकिन यह शायद सच है, है ना?" ओ'डॉनेल ने कहा। "हमें वास्तव में सही उत्तर होने की आवश्यकता थी।" लेकिन वह, फीज और किंडलर इसे साबित नहीं कर सके। तो 2007 में, वे एक पत्र में प्रकाशित यूजीसी पर हमला करने में मदद करने के लिए उन्होंने इस समस्या का उपयोग करने की योजना कैसे बनाई, इसकी रूपरेखा।

जल्द ही, उनकी उम्मीदें धराशायी हो गईं।

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

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

ओ'डॉनेल ने कहा, "अद्वितीय खेलों की कठोरता दिखाने के लिए समानांतर दोहराव का उपयोग करने की हमारी योजना सबसे सरल मामले में भी काम नहीं आई।" "इस तरह पूरी योजना को तोड़ दिया।"

हालांकि निराशाजनक, रज़ का परिणाम गोलाकार क्यूब्स के अस्तित्व पर भी संकेत देता है: टाइलिंग करने में सक्षम आकार nएक सतह क्षेत्र के साथ आयामी स्थान जो के वर्गमूल के अनुपात में बढ़ाया गया है n. ओ'डॉनेल ने कहा, "हम पसंद कर रहे थे, ठीक है, चलो नींबू से नींबू पानी बनाते हैं और समानांतर दोहराव और असतत ग्राफ के बारे में इस निराशाजनक तकनीकी परिणाम को लेते हैं, और इसे एक स्वच्छ, रोचक परिणाम में बदल देते हैं।"

वह और किंडलर, कंप्यूटर वैज्ञानिकों के सहयोग से अनूप राव और एवी विगडरसन, रज के प्रमाण पर ध्यान दिया जब तक कि वे इसकी तकनीकों को अच्छी तरह से सीख नहीं लेते थे ताकि उन्हें फोम की समस्या में अनुवाद किया जा सके। 2008 में, उन्होंने दिखाया गोलाकार घन वास्तव में संभव हैं.

"यह समस्या के बारे में तर्क करने का एक अच्छा तरीका है," कहा मार्क ब्रेवरमैन प्रिंसटन का। "यह खूबसूरत है।"

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

"उनके निर्माण के बारे में कुछ बहुत ही असंतोषजनक है," रेगेव ने कहा। "यह एक अमीबा जैसा दिखता है। यह वैसा नहीं दिखता जैसा आप उम्मीद करते हैं, एक अच्छी टाइलिंग बॉडी।

यही वह और नोर खोजने के लिए निकल पड़े।

पिंजरे से आज़ाद होना

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

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

लेकिन पिछले महीने नोर और रेगेव ने साबित कर दिया कि आप विभाजन कर सकते हैं nपूर्णांक के साथ आयामी स्थान एक उत्तल आकृति के साथ समन्वय करता है जिसका सतह क्षेत्र गोले के काफी करीब है। और उन्होंने इसे पूरी तरह से ज्यामितीय रूप से किया - समस्या को उसकी गणितीय जड़ों की ओर लौटाते हुए।

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

द्वि-आयामी ग्रिड में एक बिंदु पर विचार करें। यह क्षैतिज और ऊर्ध्वाधर दिशाओं में अपने निकटतम बिंदुओं से 1 इकाई की दूरी पर स्थित है। लेकिन विकर्ण दिशा में, निकटतम बिंदु $latex sqrt{2}$ इकाई दूर है — एक विसंगति जो बड़े स्थानों में बदतर हो जाती है। में nआयामी पूर्णांक जाली, निकटतम बिंदु अभी भी 1 इकाई दूर हैं, लेकिन वे "विकर्ण" बिंदु अब $latex sqrt{n}$ इकाइयां दूर हैं। कहें, 10,000 आयामों में, इसका मतलब है कि किसी भी बिंदु का निकटतम "विकर्ण" पड़ोसी 100 यूनिट दूर है, भले ही 10,000 अन्य बिंदु (प्रत्येक दिशा में एक) हैं जो केवल 1 यूनिट दूर हैं।

दूसरे जालों में, वे दो प्रकार की दूरियाँ एक दूसरे के अनुपात में बढ़ती हैं। गणितज्ञ दशकों से जानते हैं कि न्यूनतम सतह क्षेत्र के उत्तल आकृतियों के साथ ऐसी जाली को कैसे टाइल करना है।

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

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

दूसरे शब्दों में, वे जिस उप-स्थान के साथ समाप्त हुए, ठीक वही प्रकार था जो गणितज्ञ पहले से ही जानते थे कि कैसे बेहतर ढंग से टाइल करना है।

लेकिन यह केवल आधा काम था। नोर और रेगेव को पूरे स्थान को विभाजित करने की आवश्यकता थी, न कि केवल इसका एक टुकड़ा। एक पाने के लिए n-आयामी गोलाकार घन, उन्हें अपनी कुशल टाइल को शेष स्थान से टाइल के साथ गुणा करना था (जिस तरह आप एक त्रि-आयामी घन प्राप्त करने के लिए एक-आयामी रेखा खंड के साथ द्वि-आयामी वर्ग को गुणा कर सकते हैं)। ऐसा करने से उनका निर्माण वापस मूल स्थान में आ जाएगा, लेकिन इससे इसकी सतह का क्षेत्रफल भी बढ़ जाएगा।

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

गणितज्ञ ने कहा, गोलाकार घनों पर पिछले काम से "उनका प्रमाण पूरी तरह से अलग है" नोगा अलोन. "और पूर्व-निरीक्षण में, यह शायद अधिक प्राकृतिक प्रमाण है। किसी को शायद इसी से शुरुआत करने की कोशिश करनी चाहिए थी।”

"जब चीजें अलग तरह से की जाती हैं," रज़ ने कहा, "कभी-कभी आपको दिलचस्प अतिरिक्त निहितार्थ मिलते हैं।"

आशा फिर से जगी

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

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

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

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

"ज्यामिति में बहुत संभावनाएं हैं," मिंजर ने कहा। "यह सिर्फ इतना है कि हम इसे अच्छी तरह से नहीं समझते हैं।"