सूर्यफूल अटकळ अखेर सिद्ध

1 ते n पर्यंतच्या संख्या घ्या आणि त्यांपैकी काही निवडण्याचे सर्व मार्ग पाहा: असे 2ⁿ उपसंच आहेत. आता असे काही उपसंच निवडा ज्यांचा समाईक भाग अगदी तोच आहे, आणि बाकी काहीही समाईक नाही. गणितज्ञ याला सूर्यफूल (sunflower) म्हणतात: समाईक भाग हा गाभा, आणि प्रत्येक संचाचा उरलेला भाग ही अशी पाकळी जी इतर कोणत्याही पाकळीला स्पर्श करत नाही.

सूर्यफुले हे संयोजनशास्त्राचे (combinatorics) एक मूलभूत साधन आहे. शोधनिबंधात काही तर्क-परिपथांच्या मर्यादा, “cap set” समस्या, जलद मॅट्रिक्स गुणाकार आणि माहिती सिद्धांत यांच्याशी असलेले संबंध नमूद केले आहेत.

1970 मधील एक प्रश्न

लेखकांच्या मते, त्यांच्याविषयीचा सर्वात नैसर्गिक प्रश्न Paul Erdős यांच्या 1970 मधील एका शोधनिबंधापर्यंत मागे जातो. {1, …, n} च्या उपसंचांचा संग्रह किती मोठा असू शकतो, जर त्याचे कोणतेही k संच सूर्यफूल बनवत नसतील?

1970 च्या दशकात Erdős आणि Endre Szemerédi यांनी अटकळ मांडली की असा संग्रह 2ⁿ शक्य उपसंचांपेक्षा घातांकीय प्रमाणात लहान असलाच पाहिजे: जास्तीत जास्त cⁿ, 2 पेक्षा काटेकोरपणे कमी असलेल्या एखाद्या संख्येसाठी c.

अनेक दशके सर्वोत्तम सीमांनी थोडेसेच कमी केले, आधार 2 च्या खाली आणण्याइतके कधीच नाही. फक्त तीन पाकळ्यांचे प्रकरण (k = 3) सुटले होते, 2016 मध्ये, cap set समस्येवरील मोठ्या प्रगतीमुळे आणि Alon, Shpilka आणि Umans यांनी केलेल्या एका रूपांतरणामुळे (reduction).

सीमा

Matija Bucić आणि Fankang He (व्हिएन्ना विद्यापीठ) आणि Hyunwoo Lee (KAIST आणि Institute for Basic Science, दक्षिण कोरिया) ही अटकळ प्रत्येक k ≥ 3 साठी सिद्ध करतात. त्यांचे मुख्य प्रमेय: k पाकळ्यांचे सूर्यफूल नसलेल्या संग्रहात जास्तीत जास्त

3 · (2 − 1/(16k³))ⁿ

सदस्य असतात. आधार 2 च्या अगदी थोडा खाली आहे, पण तो 2 च्या खाली असलेला एक निश्चित आकडा आहे, आणि Erdős आणि Szemerédi यांनी नेमके तेच मागितले होते. 1997 मधील एक रचना दाखवते की मोठ्या k साठी खरे मूल्य यापेक्षा फार कमी असू शकत नाही.

संचांकडून सदिशांकडे

सिद्धता सदिशांच्या (vectors) स्वरूपातील समस्येच्या एका आवृत्तीतून जाते. संख्यांना प्रत्येकी D घटकांच्या n खंडांमध्ये विभाजित करा आणि प्रत्येक खंडातून एक घटक निवडा: प्रत्येक निवड म्हणजे एक सदिश. काही सदिश तेव्हा सूर्यफूल बनवतात जेव्हा प्रत्येक स्थानावर त्यांच्या नोंदी एकतर सगळ्या समान किंवा सगळ्या वेगवेगळ्या असतात.

मग लेखक एक “सूर्यफूल परीक्षक” तयार करतात: असे फलन जे सूर्यफूलरहित संग्रहावर, त्याचे सर्व आदान एकच सदिश असतील तेव्हाच शून्येतर असते. नवा घटक म्हणजे हे फलन, पायरीपायरीने, कमी घाताच्या आंतरवेशन बहुपदींनी (interpolation polynomials) लिहिणे. त्या बहुपदी मोजल्याने संग्रहाच्या आकाराला सीमा मिळते (त्यांचे प्रमेय 2). एक संभाव्यतावादी युक्तिवाद, म्हणजे सर्व संच-आकारांवर सरासरी काढलेले यादृच्छिक खंड, ही सीमा सामान्य संचांकडे परत आणतो.

एका यंत्राने शोधले, दुसऱ्याने तपासले

AI बद्दल शोधनिबंधातील विधान असामान्यपणे थेट आहे. प्रमेय 2 ची सिद्धता ChatGPT 6 Astra Pro ने शोधली, एका छोट्या चर्चेनंतर, जी तीन पाकळ्यांसाठीच्या ज्ञात युक्तिवादाचे सामान्यीकरण करायला सांगून सुरू झाली होती. लेखकांना ती पायरी दुसऱ्या एका उद्दिष्टासाठी हवी होती: Szemerédi यांनी मांडलेल्या आलेख-समस्येची प्रवर्तित (induced) आवृत्ती, जी ते पुढील एका टिपणात जाहीर करणार असल्याचे सांगतात.

मॉडेलने आपली सिद्धता “slice rank” च्या भाषेत लिहिली. लेखकांनी ती बहुपदी पद्धतीच्या भाषेत पुन्हा लिहिली, जी त्यांच्या मते वाचकांसाठी सोपी आहे. त्यांनी प्रत्येक निष्कर्ष पडताळल्याचे आणि पूर्ण जबाबदारी घेत असल्याचे ते सांगतात, आणि ही सिद्धता सिद्धता-तपासणी सॉफ्टवेअर Lean 4.35 मध्ये पडताळली गेली आहे, ती पडताळणी Palomar संग्रहावर प्रसिद्ध केली जाणार आहे.

काय सुटलेले नाही

लेखकांनी आधार इष्टतम करण्याचा प्रयत्न केला नाही. तीन पाकळ्यांसाठी तो Naslund आणि Sawin यांच्या 2017 मधील सुमारे 1.89 या सीमेपेक्षा सरस ठरत नाही. आणि त्याहून बळकट भगिनी-समस्या, Erdős–Rado सूर्यफूल अटकळ, अजूनही खुली आहे: त्यांच्या सीमा अजूनही खंडाच्या आकार D वर मोठ्या प्रमाणात अवलंबून आहेत, आणि नेमके तेच त्या समस्येत निषिद्ध आहे.