सूरजमुखी अनुमान आख़िरकार सुलझा

1 से n तक की संख्याएँ लीजिए और उनमें से कुछ को चुनने के सभी तरीक़ों को देखिए: ऐसे 2ⁿ उपसमुच्चय होते हैं। अब कुछ ऐसे उपसमुच्चय चुनिए जो ठीक एक ही साझा हिस्सा रखते हैं, और कुछ नहीं। गणितज्ञ इसे सूरजमुखी कहते हैं: साझा हिस्सा केंद्र है, और हर समुच्चय का बचा हुआ हिस्सा एक पंखुड़ी है जो किसी दूसरी पंखुड़ी को नहीं छूती।

सूरजमुखी संयोजन-विज्ञान (कॉम्बिनेटोरिक्स) का एक बुनियादी औज़ार हैं। शोधपत्र इनके संबंध कुछ तार्किक परिपथों की सीमाओं, “कैप सेट” समस्या, तेज़ मैट्रिक्स गुणन और सूचना सिद्धांत से गिनाता है।

1970 का एक सवाल

लेखकों के अनुसार, इनके बारे में सबसे स्वाभाविक सवाल Paul Erdős के 1970 के एक शोधपत्र तक जाता है। {1, …, n} के उपसमुच्चयों का एक संग्रह कितना बड़ा हो सकता है अगर उसके कोई भी k समुच्चय सूरजमुखी न बनाएँ?

1970 के दशक में Erdős और Endre Szemerédi ने अनुमान लगाया कि ऐसा संग्रह 2ⁿ संभव उपसमुच्चयों से घातांकीय रूप से छोटा होना चाहिए: अधिकतम cⁿ, किसी ऐसी संख्या c के लिए जो 2 से सख़्ती से कम हो।

दशकों तक सबसे अच्छी सीमाएँ थोड़ा-सा ही घटा पाईं, कभी इतना नहीं कि आधार 2 से नीचे आ जाए। केवल तीन-पंखुड़ी वाला मामला (k = 3) 2016 में सुलझा, कैप सेट समस्या पर हुई सफलता और Alon, Shpilka और Umans के एक अपचयन (रिडक्शन) के ज़रिए।

सीमा

Matija Bucić और Fankang He (वियना विश्वविद्यालय) और Hyunwoo Lee (KAIST और इंस्टीट्यूट फ़ॉर बेसिक साइंस, दक्षिण कोरिया) इस अनुमान को हर k ≥ 3 के लिए सिद्ध करते हैं। उनका मुख्य प्रमेय: जिस संग्रह में k-पंखुड़ी वाला कोई सूरजमुखी नहीं है, उसमें अधिकतम

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

सदस्य होते हैं। आधार 2 से ठीक नीचे है, लेकिन यह 2 से नीचे की एक नियत संख्या है, और ठीक यही Erdős और Szemerédi ने माँगा था। 1997 का एक निर्माण दिखाता है कि बड़े k के लिए असली मान इससे बहुत कम नहीं हो सकता।

समुच्चयों से सदिशों तक

प्रमाण समस्या के सदिशों वाले एक संस्करण से होकर जाता है। संख्याओं को D तत्वों वाले n खंडों में बाँटिए और हर खंड से एक तत्व चुनिए: हर चुनाव एक सदिश है। कई सदिश सूरजमुखी बनाते हैं जब हर स्थान पर उनकी प्रविष्टियाँ या तो सब बराबर हों या सब अलग-अलग।

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

एक मशीन ने खोजा, दूसरी ने जाँचा

AI के बारे में शोधपत्र का कथन असामान्य रूप से सीधा है। प्रमेय 2 का प्रमाण ChatGPT 6 Astra Pro ने खोजा, एक छोटी बातचीत के बाद जो उससे ज्ञात तीन-पंखुड़ी तर्क का सामान्यीकरण करने के अनुरोध से शुरू हुई थी। लेखकों को यह क़दम एक दूसरे लक्ष्य के लिए चाहिए था: Szemerédi द्वारा रखी गई एक ग्राफ़ समस्या का एक प्रेरित (induced) संस्करण, जिसकी घोषणा वे एक बाद के नोट के लिए करते हैं।

मॉडल ने अपना प्रमाण “स्लाइस रैंक” की भाषा में लिखा। लेखकों ने इसे बहुपद विधि की भाषा में दोबारा लिखा, जिसे वे पाठकों के लिए आसान मानते हैं। वे कहते हैं कि उन्होंने हर नतीजे को सत्यापित किया है और पूरी ज़िम्मेदारी लेते हैं, और यह कि प्रमाण Lean 4.35 में सत्यापित किया जा चुका है, जो एक प्रमाण-जाँच सॉफ़्टवेयर है, और यह सत्यापन Palomar रिपॉज़िटरी पर डाला जाएगा।

यह क्या नहीं सुलझाता

लेखकों ने आधार को अनुकूलित करने की कोशिश नहीं की। तीन पंखुड़ियों के लिए यह Naslund और Sawin की 2017 की लगभग 1.89 वाली सीमा को नहीं हराता। और उससे मज़बूत बहन-समस्या, Erdős–Rado सूरजमुखी अनुमान, अभी खुली है: उनकी सीमाएँ अब भी खंड-आकार D पर बहुत निर्भर करती हैं, और ठीक यही वह समस्या मना करती है।