हर बिंदु को हर दूसरे बिंदु से जोड़िए: सबसे कम क्रॉसिंग, अब सिद्ध

काग़ज़ के एक पन्ने पर पाँच बिंदु बनाइए और हर जोड़े को एक वक्र से जोड़िए: कुल दस वक्र। वे आपकी इच्छा के अनुसार मुड़ सकते हैं, लेकिन कोई भी किसी तीसरे बिंदु से होकर नहीं गुज़र सकता। हर क्रॉसिंग से बचने की कोशिश कीजिए, और आप असफल रहेंगे। पाँच बिंदुओं के साथ कम से कम 1 क्रॉसिंग अपरिहार्य है; छह के साथ कम से कम 3; दस के साथ कम से कम 60।

गणितज्ञ ऐसे चित्र को पूर्ण ग्राफ़ (complete graph) Kₙ का आरेखण कहते हैं — n बिंदु, जिनका हर जोड़ा जुड़ा हो — और किसी भी आरेखण में संभव सबसे कम क्रॉसिंग को उसकी क्रॉसिंग संख्या (crossing number) कहते हैं। चेक गणराज्य के चार्ल्स विश्वविद्यालय के मार्टिन बाल्को (Martin Balko) इस प्रश्न को “टोपोलॉजिकल ग्राफ़ सिद्धांत की सबसे प्रसिद्ध समस्याओं में से एक” कहते हैं।

एक कलाकार की गिनती

1950 के दशक के अंत में ब्रिटिश कलाकार एंथनी हिल (Anthony Hill) ने Kₙ के ऐसे आरेखण बनाए जिनमें ठीक

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

क्रॉसिंग थे, जहाँ ⌊ ⌋ का अर्थ है नीचे की ओर पूर्णांकन। यह अनुमान कि कोई भी आरेखण इससे बेहतर नहीं कर सकता, सबसे पहले गाय (Guy) ने प्रकाशित किया, बाद में हैरारी (Harary) और हिल ने इस पर चर्चा की, और एर्डोश (Erdős) और गाय ने इसे लोकप्रिय बनाया। इसे हैरारी–हिल अनुमान (Harary–Hill conjecture), या गाय का अनुमान, कहा जाता है।

सूत्र तेज़ी से बढ़ता है:

4 या उससे कम बिंदु: 0 क्रॉसिंग
5 बिंदु: 1
7 बिंदु: 9
10 बिंदु: 60
14 बिंदु: 315

छह दशकों के आंशिक उत्तर

बिंदुओं की हर संख्या के लिए ठीक Z(n) क्रॉसिंग वाले आरेखण मौजूद थे; कठिन हिस्सा यह दिखाना था कि कोई भी आरेखण इससे बेहतर नहीं करता।

साठ से अधिक वर्षों तक यह केवल विशेष प्रकार के आरेखणों के लिए साबित हुआ था — उदाहरण के लिए, जब सभी बिंदु एक रेखा पर हों और हर वक्र उसके एक ही ओर रहे, या जब बिंदु एक गोले पर हों और हर वक्र सबसे छोटा रास्ता ले। स्वयं बाल्को ने फ़ुलेक (Fulek) और किन्चल (Kynčl) के साथ ऐसे एक वर्ग का निपटारा किया था। 2021 तक कंप्यूटरों ने 14 बिंदुओं तक सूत्र की पुष्टि कर दी थी। बिंदुओं की बहुत बड़ी संख्याओं के लिए, सबसे अच्छे सामान्य परिणाम Z(n) का कम से कम 98.5%, फिर 98.99%, सुनिश्चित करते थे।

एक प्रमाण, फिर एक अधिक स्पष्ट प्रमाण

2026 में OpenAI ने बिंदुओं की हर संख्या के लिए एक प्रमाण की घोषणा की, जिसे बाल्को का शोधपत्र “OpenAI Math Release preprint” के रूप में सूचीबद्ध करता है और प्रमेय का श्रेय उसे देता है। शोधपत्र यह नहीं बताता कि वह प्रमाण कैसे खोजा गया। बाल्को के शब्दों में, मूल प्रमाण “अपेक्षाकृत छोटा है”, लेकिन “इसे समझना काफ़ी कठिन है”। उनका प्रीप्रिंट एक सुव्यवस्थित रूपांतर प्रस्तुत करता है, जिसके लिए, वे लिखते हैं, “केवल रैखिक बीजगणित और ग्राफ़ सिद्धांत के प्रारंभिक ज्ञान की आवश्यकता है”। एक अन्य गणितज्ञ, गेलासियो सालाज़ार (Gelasio Salazar), एक अलग, विस्तृत व्याख्या तैयार कर रहे हैं।

क्रॉसिंग के बजाय गुणांक गिनना

चूँकि ज्ञात आरेखण पहले से ही Z(n) तक पहुँचते हैं, केवल निचली सीमा को साबित करना बाक़ी है। इसमें चार चालें लगती हैं।

विषम संख्याएँ काफ़ी हैं। किसी सर्वश्रेष्ठ आरेखण को इस तरह फिर से बनाया जा सकता है कि एक साझा बिंदु वाले वक्र कभी एक-दूसरे को न काटें; तब हर क्रॉसिंग में 4 अलग-अलग बिंदु शामिल होते हैं। 6 बिंदुओं में से हर एक को बारी-बारी से हटाइए: बची हुई हर 5-बिंदु वाली तस्वीर में कम से कम 1 क्रॉसिंग है, और हर क्रॉसिंग 6 में से ठीक 2 बार हटाने के बाद बचा रहता है (जब भी उसके अपने 4 बिंदुओं में से कोई हटाया जाता है, वह मिट जाता है, और बाक़ी 2 बार बचा रहता है)। इसलिए क्रॉसिंग की संख्या का दोगुना कम से कम 6 है: यानी कम से कम 3, जो Z(6) है। यही गिनती हर सम संख्या के लिए काम करती है।
बहुपदों का एक परिवार। हर बिंदु को उसकी अपनी संख्या दीजिए। एक क्रॉसिंग में दो वक्र शामिल होते हैं, यानी चार बिंदु, यानी चार संख्याएँ। बाल्को चार चरों वाले बहुपदों का उपयोग करते हैं, जिन्हें इस तरह चुना गया है कि n विषम होने पर परिवार में ठीक Z(n) स्वतंत्र गुणांक हों — 7 बिंदुओं के लिए 3 × 3 = 9।
बहुत कम क्रॉसिंग जगह छोड़ देते हैं। किसी बहुपद से किसी क्रॉसिंग पर शून्य होने की माँग करना एक समीकरण है। जब समीकरण स्वतंत्र गुणांकों से कम हों, तो रैखिक बीजगणित हमेशा एक शून्येतर हल छोड़ता है। इसलिए Z(n) से कम क्रॉसिंग वाले किसी आरेखण के साथ एक ऐसा शून्येतर बहुपद भी आता, जो उसके सभी क्रॉसिंग पर शून्य हो; इनमें से सबसे कम घात वाला लीजिए।
समतल पलटवार करता है। ज्यामिति एक क्लासिक तथ्य के ज़रिए आती है: समतल में एक बंद लूप किसी दूसरे लूप को दाएँ से बाएँ ठीक उतनी ही बार काटता है जितनी बार बाएँ से दाएँ। अच्छी तरह चुने गए भारों के साथ, इससे बहुपद के मानों के वर्गों का एक ऐसा योग मिलता है, जिसमें कुछ धनात्मक रूप से और कुछ ऋणात्मक रूप से गिने जाते हैं, और जिसका कुल शून्य होता है। सभी धनात्मक पद क्रॉसिंग पर पड़ते हैं, जहाँ बहुपद शून्य है, इसलिए ऋणात्मक पदों को भी शून्य होना होगा। लूप वाले तथ्य का दूसरा उपयोग उसे एक निश्चित गुणनखंड से विभाज्य बना देता है; भाग देने पर उसी गुण वाला कम घात का एक शून्येतर बहुपद मिलता है, जो असंभव है, क्योंकि हमने सबसे कम घात वाला लिया था।

चिह्न वाला यह तर्क बाल्को का मुख्य बदलाव है: यह मूल तर्क की जगह लेता है, जो “एक अपभ्रष्ट-रहित (nondegenerate) द्विरेखीय रूप और लांबिक पूरकों से जुड़ा” था। वे लूप वाले तथ्य को भी अलग ढंग से साबित करते हैं और हर बिंदु को अधिक सीधे ढंग से अलग करते हैं।

अन्य नेटवर्क भी एक साथ सुलझे

उत्तर Z(n) ही रहता है यदि क्रॉसिंग के बजाय वक्रों के उन जोड़ों को गिना जाए जो एक-दूसरे को काटते ही हैं, या जो विषम संख्या में बार काटते हैं — बशर्ते एक साझा बिंदु वाले वक्र कहीं और न मिलें। पहले के अपचयनों (reductions) के साथ मिलकर, यह प्रमेय उन पूर्ण ग्राफ़ों के लिए भी सटीक क्रॉसिंग संख्याएँ देता है जिनसे कुछ कड़ियाँ हटा दी गई हों, किसी पथ के साथ या किसी सम चक्र के चारों ओर शृंखला में जोड़ी गई पूर्ण ग्राफ़ की प्रतियों के लिए, और विस्तारित सिएरपिन्स्की ग्राफ़ (extended Sierpiński graphs) कहलाने वाले फ़्रैक्टल-जैसे नेटवर्कों के एक परिवार के लिए।

6 बिंदुओं वाले पूर्ण ग्राफ़ से केवल एक वक्र हटा दीजिए, और उसका न्यूनतम मान 3 क्रॉसिंग से घटकर 2 रह जाता है; 8 बिंदुओं पर, 18 से घटकर 15।