अवकाश रंगवण्यासाठी किती रंग? एका सामान्य मापपट्टीसाठी 2d पेक्षा जास्त नाहीत

एका सपाट समतलातील प्रत्येक बिंदू घ्या आणि प्रत्येकाला एक रंग द्या. एकच नियम: अगदी एक एकक अंतरावर असलेल्या दोन बिंदूंना कधीही एकच रंग असता कामा नये. हे साध्य करणारी रंगांची किमान संख्या किती?

ही आहे हॅडविगर–नेल्सन समस्या, 1950 पासूनची, आणि लेखकांच्या शब्दांत विविक्त भूमितीतील (discrete geometry) सर्वांत प्रसिद्ध अनुत्तरित समस्यांपैकी एक. बराच काळ उत्तर 4 ते 7 दरम्यान असल्याचे माहीत होते. अलीकडच्या एका मोठ्या यशाने खालची सीमा 5 पर्यंत वाढवली. अचूक उत्तर अजूनही अज्ञात आहे.

मापपट्टी बदलणे

अंतर नेहमीच्या मापपट्टीनेच मोजले पाहिजे असे नाही. गणितज्ञ इतर अनेक नॉर्म्स — लांबी मोजण्याच्या पद्धती — परिभाषित करतात. प्रत्येक नॉर्मचे वर्णन त्याच्या “एकक गोल” (unit ball) द्वारे होते, म्हणजे केंद्रापासून जास्तीत जास्त 1 अंतरावरील बिंदूंचा संच. नेहमीच्या अंतरासाठी तो गोल चेंडू असतो; इतर नॉर्म्ससाठी तो केंद्राभोवती सममित असलेला कोणताही बहिर्वक्र (convex) आकार असू शकतो.

समतलावरील प्रत्येक नॉर्मसाठी, रंगवण्याच्या कोड्याचे उत्तर 4 ते 7 दरम्यान असते. d मितींमध्ये, कोणत्याही नॉर्मसाठी ते d मध्ये जास्तीत जास्त घातांकी (exponential) असते, आणि अनेक नैसर्गिक नॉर्म्ससाठी — नेहमीच्या युक्लिडीय नॉर्मसह — ते किमान घातांकीही असते: मिती वाढतात तसा रंगांचा आकडा प्रचंड वाढतो.

हा प्रचंड वाढीचा प्रकार हाच नियम आहे का? नोगा अलोन (प्रिन्स्टन विद्यापीठ आणि तेल अविव विद्यापीठ), मातिया बुचिच (व्हिएन्ना विद्यापीठ) आणि जेम्स डेव्हीस (लाइपझिग विद्यापीठ) यांनी एका सामान्य (typical) नॉर्मचा विचार केला. नॉर्म “यादृच्छिकपणे” निवडण्याची कोणतीही नैसर्गिक पद्धत नाही, म्हणून ते एक संस्थिती-शास्त्रीय (topological) संकल्पना वापरतात: अपवादांचा संच नगण्य (“meagre”) असेल तर तो गुणधर्म सामान्य नॉर्मसाठी लागू होतो. अलोन, बुचिच आणि लिसा सॉअरमन यांच्या आधीच्या कामाने दाखवले होते की सामान्य नॉर्मला जास्तीत जास्त 2ᵈ रंग लागतात, आणि हे सत्याच्या किती जवळ आहे असा प्रश्न विचारला होता.

रेषीय, घातांकी नव्हे

उत्तर: अजिबात जवळ नाही. नवा शोधनिबंध सिद्ध करतो की

• d-मितीय अवकाशावरील सामान्य नॉर्मसाठी, 2d रंग नेहमीच पुरेसे असतात;
• हे सर्वोत्तम शक्य आहे: नॉर्म्सच्या एका विवृत (open) संचाला किमान 2d रंग लागतात. त्यामुळे काही नॉर्म्सना अगदी 2d रंग लागतात.

दहा मितींमध्ये, सामान्य नॉर्मला जास्तीत जास्त वीस रंग लागतात, तर नेहमीच्या अंतराला घातांकी वेगाने वाढणारी संख्या लागते. लेखकांच्या मते, कोणत्याही मिती d मध्ये एखाद्या “काटेकोरपणे बहिर्वक्र” (strictly convex) नॉर्मसाठी रंगसंख्या अचूकपणे निश्चित होण्याची ही पहिलीच वेळ आहे.

खालची सीमा एक नेटका सापळा वापरते. असे 2d बिंदू शोधा जे सर्व एकमेकांपासून अगदी एक एकक अंतरावर आहेत, फक्त a आणि b हे दोन सोडून, जे अर्धा एकक अंतरावर आहेत. संपूर्ण रचनेची a मधून आरशातील प्रतिमा जोडा. 2d पेक्षा कमी रंग असल्यास, b आणि त्याची आरशातील प्रतिमा दोघांनाही a चाच रंग घ्यावा लागेल — पण ते एकमेकांपासून अगदी एक एकक अंतरावर आहेत. विरोधाभास. एक स्थिरता लेमा दाखवतो की नॉर्ममध्ये कोणताही लहान बदल केला तरी ही रचना टिकून राहते.

उच्च मितींमधील एकटा धावपटू

वरची सीमा प्रत्येक बिंदूला, त्याचा एक योग्य निवडलेला प्रक्षेप (projection) 1/(2d) रुंदीच्या कोणत्या पट्टीत पडतो त्यानुसार रंग देते. हे काम करण्यासाठी एक कळीचा घटक लागतो, ज्याचे वर्णन लेखक प्रसिद्ध एकट्या धावपटूच्या अनुमानाची (lonely runner conjecture) उच्च-मितीय, मॅट्रिक्स आवृत्ती असे करतात:

sup over x of minᵢ ‖aᵢ · x − bᵢ‖ ≥ k / (2n)

येथे ‖t‖ म्हणजे t पासून जवळच्या पूर्णांकापर्यंतचे अंतर, k मितींमधील कोणत्याही n सदिशांसाठी aᵢ, ज्यांपैकी कोणतेही k स्वतंत्र आहेत. हे विधान “दृष्टी-अडथळा” (view obstruction) विषयीचे आय. जे. शोनबर्ग यांचे 1978 मधील एक अनुमानही सोडवते — अनंताकडे जाणारी प्रत्येक दृष्टी अडवण्यासाठी आवर्ती पट्ट्या किती जाड असाव्यात हा प्रश्न — ज्याला लेखक या क्षेत्रातील सर्वांत अभिजात अनुत्तरित समस्यांपैकी एक म्हणतात, तसेच हेन्झे आणि मालिकिओसिस यांचे एक संबंधित अनुमानही.

ऋणनिर्देशातील यंत्र

लेखक स्पष्ट आहेत: “ChatGPT 6 Pro ने आम्हाला प्रमेय 1 च्या पुराव्यात लागणाऱ्या अंतिम घटकाचा, म्हणजे लेमा 7 चा, पुरावा एका प्रदीर्घ चर्चेनंतर दिला”, ज्या चर्चेत त्यांनी स्वतःची निरीक्षणे — प्रवर्तनाची (induction) कल्पना आणि सर्वसाधारण रणनीतीसह — सामायिक केली होती. “खालच्या सीमेचा युक्तिवादही ChatGPT 6 Pro च्या साहाय्याने सापडला.”

प्रश्न शिल्लक आहेत. 2d हे अचूक मूल्य नॉर्म्सच्या एका विवृत संचावर सिद्ध झाले आहे, सर्व सामान्य नॉर्म्ससाठी नव्हे. आणि नेहमीच्या युक्लिडीय अंतरासाठी लेखकांना प्रत्येक मितीत 2d पेक्षा काटेकोरपणे अधिक रंग अपेक्षित आहेत — हे मिती 2, 4, 7, 8 आणि 9 व त्यापुढील मितींमध्ये आधीच माहीत आहे, पण मिती 3, 5 आणि 6 मध्ये अजूनही अनुत्तरित आहे.