प्रत्येक बिंदू प्रत्येक दुसऱ्याशी जोडा: सर्वात कमी छेद, आता सिद्ध

कागदावर पाच बिंदू काढा आणि प्रत्येक जोडी एका वक्राने जोडा: एकूण दहा वक्र. ते हवे तसे वाकू शकतात, पण कोणताही वक्र तिसऱ्या बिंदूतून जाऊ नये. प्रत्येक छेद टाळण्याचा प्रयत्न करा, आणि तुम्ही अपयशी ठराल. पाच बिंदूंसह किमान 1 छेद अटळ आहे; सहासह किमान 3; दहासह किमान 60.

गणितज्ञ अशा चित्राला पूर्ण आलेखाचे (complete graph) Kₙ चे रेखाटन म्हणतात — n बिंदू, प्रत्येक जोडी जोडलेली — आणि कोणतेही रेखाटन गाठू शकणाऱ्या सर्वात कमी छेदांना त्याची छेदसंख्या (crossing number) म्हणतात. चेक प्रजासत्ताकातील चार्ल्स विद्यापीठाचे Martin Balko या प्रश्नाला “सांस्थितिक आलेख सिद्धांतातील (topological graph theory) सर्वात प्रसिद्ध समस्यांपैकी एक” म्हणतात.

एका कलाकाराची गणना

1950 च्या दशकाच्या अखेरीस ब्रिटिश कलाकार Anthony Hill यांनी Kₙ ची अशी रेखाटने तयार केली ज्यांत नेमके

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

छेद होते, जिथे ⌊ ⌋ म्हणजे खालच्या पूर्णांकाकडे पूर्णांकन. कोणतेही रेखाटन याहून चांगले करू शकत नाही हा अंदाज सर्वप्रथम Guy यांनी प्रकाशित केला, नंतर Harary आणि Hill यांनी त्याची चर्चा केली, आणि Erdős व Guy यांनी तो लोकप्रिय केला. तो हॅरारी–हिल अटकळ (Harary–Hill conjecture), किंवा Guy यांची अटकळ, म्हणून ओळखला जातो.

हे सूत्र झपाट्याने वाढते:

• 4 किंवा कमी बिंदू: 0 छेद
• 5 बिंदू: 1
• 7 बिंदू: 9
• 10 बिंदू: 60
• 14 बिंदू: 315

सहा दशकांची अर्धवट उत्तरे

नेमके Z(n) छेद असलेली रेखाटने प्रत्येक बिंदूसंख्येसाठी अस्तित्वात होती; कठीण भाग होता हे दाखवणे की कोणतेही रेखाटन याहून चांगले करत नाही.

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

एक सिद्धता, मग एक अधिक स्पष्ट

2026 मध्ये OpenAI ने प्रत्येक बिंदूसंख्येसाठी एक सिद्धता जाहीर केली; Balko यांचा शोधनिबंध तिची नोंद “OpenAI Math Release preprint” म्हणून करतो आणि प्रमेयाचे श्रेय तिला देतो. ती सिद्धता कशी सापडली हे शोधनिबंध सांगत नाही. Balko यांच्या शब्दांत, मूळ सिद्धता “तुलनेने लहान आहे”, पण “अनुसरायला बरीच कठीण” आहे. त्यांची प्रीप्रिंट एक सुटसुटीत रूपांतर मांडते, ज्याला, ते लिहितात, “रेषीय बीजगणित आणि आलेख सिद्धांताचे फक्त प्राथमिक ज्ञान लागते”. आणखी एक गणितज्ञ, Gelasio Salazar, एक स्वतंत्र, सविस्तर विवेचन तयार करत आहेत.

छेदांऐवजी सहगुणक मोजणे

ज्ञात रेखाटने आधीच Z(n) गाठत असल्याने, फक्त खालची मर्यादा सिद्ध करायची उरते. त्यासाठी चार पायऱ्या लागतात.

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

चिन्हांचा हा युक्तिवाद हा Balko यांचा मुख्य बदल आहे: तो “एक अपभ्रष्ट नसलेले द्विरेषीय रूप (nondegenerate bilinear form) आणि लंब पूरक (orthogonal complements) यांचा समावेश असलेल्या” मूळ युक्तिवादाची जागा घेतो. ते वळशाचे तथ्यही वेगळ्या प्रकारे सिद्ध करतात आणि प्रत्येक बिंदू अधिक थेटपणे वेगळा काढतात.

इतर जाळीही एकाच वेळी सुटली

छेदांऐवजी, जर एकमेकांना मुळात छेदणाऱ्या वक्रांच्या जोड्या मोजल्या, किंवा विषम संख्येने छेदणाऱ्या जोड्या मोजल्या, तरी उत्तर Z(n) च राहते — जोपर्यंत एक बिंदू सामायिक असलेले वक्र इतरत्र कधीच भेटत नाहीत. आधीच्या घटीकरणांसोबत (reductions) जोडल्यावर, हे प्रमेय काही दुवे काढून टाकलेल्या पूर्ण आलेखांसाठी, एका मार्गावर किंवा सम चक्राभोवती साखळीसारख्या जोडलेल्या पूर्ण आलेखाच्या प्रतींसाठी, आणि विस्तारित सिअरपिन्स्की आलेख (extended Sierpiński graphs) नावाच्या भग्नसदृश (fractal) जाळ्यांच्या एका कुटुंबासाठीही अचूक छेदसंख्या देते.

6 बिंदूंवरील पूर्ण आलेखातून फक्त एक वक्र काढून टाका, आणि त्याची किमान संख्या 3 छेदांवरून 2 वर येते; 8 बिंदूंवर, 18 वरून 15 वर.