समीकरणे सोडवण्याची 1974 मधील वेगमर्यादा, अखेर सिद्ध

एखादे फलन f शून्य कुठे ओलांडते ते शोधण्यासाठी, संगणक अनेकदा एक पुनरावृत्ती (iteration) चालवतो: एखाद्या अंदाज x पासून सुरुवात करा, फलनाला काही प्रश्न विचारा, अधिक चांगला अंदाज काढा, आणि पुन्हा तेच करा. हे प्रश्न म्हणजे मूल्यांकने (evaluations): एखाद्या बिंदूवरील f चे मूल्य, किंवा त्याच्या उताराचे (अवकलज, derivative), किंवा एखाद्या उच्च अवकलजाचे.

दुप्पट होणारे अंक

अशा पद्धतीचा वेग तिच्या क्रमाने (order) मोजला जातो. सध्याची त्रुटी ε असेल, तर p क्रमाची पुनरावृत्ती साधारण ε चा घात p इतकी त्रुटी शिल्लक ठेवते. क्रम 2 म्हणजे, उत्तराजवळ, अचूक अंकांची संख्या प्रत्येक पायरीत दुप्पट होते; क्रम 4 म्हणजे ती चौपट होते.

न्यूटनची पद्धत प्रत्येक पायरीत दोन मूल्यांकने खर्च करते — f(x) आणि त्याचा उतार f′(x) — आणि x − f(x)/f′(x) कडे सरकते. तिचा क्रम 2 आहे. प्रत्येक पायरीत अधिक प्रश्न विचारल्याने अधिक वेग विकत घेता येतो. प्रश्न असा आहे की किती.

1974 मधील एक अनुमान

1974 मध्ये, H. T. Kung आणि J. F. Traub यांनी Journal of the ACM मधील एका शोधनिबंधात “Conjecture 8.1” म्हणून एक उत्तर सुचवले: प्रत्येक पायरीत n मूल्यांकने वापरणाऱ्या स्मृतिविरहित (without memory) पुनरावृत्तीचा क्रम जास्तीत जास्त 2ⁿ⁻¹ असतो. “स्मृतिविरहित” म्हणजे पद्धत आपल्या सध्याच्या अंदाजाखेरीज मागील पायऱ्यांमधील काहीही जपून ठेवत नाही.

ही मर्यादा यापेक्षा खाली आणता येणे शक्य नव्हते: Kung आणि Traub यांनी स्वतःच प्रत्येक n ≥ 2 साठी 2ⁿ⁻¹ गाठणाऱ्या “बहुबिंदू” (multipoint) पद्धती बनवल्या होत्या — तीन मूल्यांकनांसह क्रम 4, चारसह 8, पाचसह 16. उरलेला होता दुसरा अर्धा भाग: कोणतीही पद्धत यापेक्षा चांगले करू शकत नाही याचा पुरावा. अनुमानासोबतच आणि त्यानंतरही आंशिक निष्कर्ष आले. ही मर्यादा अंतर्वेशन-आधारित (interpolation-based) पद्धतींसाठी, दोन मूल्यांकने वापरणाऱ्या परिमेय पद्धतींसाठी, आणि विविध अतिरिक्त अटींखाली सिद्ध झाली; केवळ फलन-मूल्ये वापरणाऱ्या पद्धतींसाठी, 2ⁿ ही दुर्बल मर्यादा प्रस्थापित झाली. सर्वसाधारण स्थिती मात्र अनुत्तरितच राहिली.

अल्गोरिदमला फसवणे

केंब्रिज विद्यापीठाच्या Department of Applied Mathematics and Theoretical Physics मधील Matthew Colbrook आता ते पूर्णपणे सिद्ध करतात. हे प्रारूप जाणूनबुजून अल्गोरिदमच्या बाजूने उदार ठेवलेले आहे. कुठे मूल्यांकन करायचे आणि कोणते अवकलज घ्यायचे, हे अल्गोरिदम पुढे जाता जाता निवडू शकतो. उत्तरांवर तो आपल्याला हव्या त्या कोणत्याही निर्धारित (deterministic) पद्धतीने प्रक्रिया करू शकतो, आणि त्याच्या नियमांकडून कोणत्याही सुरळीतपणाची (smoothness) अपेक्षा नसते.

पुरावा अल्गोरिदमच्या स्वतःच्या निर्धारिततेलाच त्याच्याविरुद्ध वापरतो. अशी दोन फलने बनवा जी त्याच्या सर्व प्रश्नांना अगदी तीच उत्तरे देतात, पण ज्यांचे शून्यबिंदू वेगवेगळे आहेत. अल्गोरिदमला दोन्हींसाठी तोच अंदाज परत द्यावा लागतो, त्यामुळे त्यांपैकी एकावर तो दोन शून्यबिंदूंमधील अंतराच्या किमान निम्म्याने चुकतो.

अशा जोड्या शोधण्यासाठी, Colbrook एका संदर्भ-फलनात जास्तीत जास्त n घाताच्या एका लहान बहुपदीची भर घालून किंचित बदल करतात; या बहुपदीत n + 1 समायोज्य सहगुणक असतात. प्रत्येक मूल्यांकन त्यांच्या जास्तीत जास्त एका संयोगाला निश्चित करते, त्यामुळे n प्रश्नांनंतर काही बदल अल्गोरिदमला अदृश्य राहतात. केवळ ही मोजणी पुरेशी नाही: एखाद्या अदृश्य बदलामुळे शून्यबिंदू जेमतेमच हलू शकतो.

मुख्य साधन म्हणजे व्रॉन्स्कियन (Wronskian) — बहुपदींच्या एका कुटुंबापासून आणि त्यांच्या अवकलजांपासून बनवलेला एक निर्धारक (determinant). एक नवे उपप्रमेय (lemma) सांगते की, कुटुंबातील एखाद्या बहुपदीचे अनेक शून्यबिंदू एका लहान चकतीत (disc) दाटीवाटीने असतील, तर कुटुंबाचा व्रॉन्स्कियन जवळपास कुठेतरी शून्य व्हायलाच हवा. ज्याचा शून्यबिंदू या थोड्याशा बिंदूंपासून दूर राहतो अशा फलनानेच अल्गोरिदमला नेहमी उत्तर देऊन, पुरावा शून्यबिंदूला हलण्यास मोकळा ठेवतो.

हिशेबातून घातांक मिळतो. शून्यबिंदूपासून ε अंतरावरून सुरुवात केल्यास, संभाव्य शून्यबिंदू किमान एक स्थिरांक गुणिले ε चा एखादा घात इतक्या कक्षेत पसरलेले राहतात. Colbrook यांच्या शब्दांत, “पहिल्या निरीक्षणानंतर घातांक एक राहतो आणि मग दुप्पट होतो, ज्यामुळे n निरीक्षणांनंतर 2ⁿ⁻¹ मिळतो.”

प्रत्येक पातळीसाठी एकच फलन

एक अडचण उरली होती. क्रमाच्या व्याख्येत पुढे येणारा स्थिरांक फलनावर अवलंबून असू शकतो, त्यामुळे प्रत्येक पातळीवर (scale) वेगळे वाईट फलन घेतल्याने काहीच सिद्ध होत नाही. म्हणून Colbrook एकामागून एक दुरुस्त्या जोडत एकच फलन बनवतात; प्रत्येक दुरुस्ती अल्गोरिदमने आधीच प्रश्न विचारलेल्या प्रत्येक बिंदूवर शून्य होते, जेणेकरून मागील सर्व उत्तरे अगदी तीच राहतात.

या बांधणीचे सीमा-फलन (limit) म्हणजे एक संपूर्ण फलन (entire function) — सर्वत्र सुरळीत, अगदी संमिश्र संख्यांवरही — ज्याचा उतार वास्तव रेषेवर 3/4 आणि 5/4 यांच्या दरम्यान राहतो: एकच सुस्वभावी शून्यबिंदू असलेला, सातत्याने चढणारा वक्र. 2ⁿ⁻¹ पेक्षा मोठ्या कोणत्याही p साठी, या फलनावर पद्धत p क्रम गाठू शकत नाही. म्हणून n ≥ 2 साठी स्मृतिविरहित इष्टतम क्रम नेमका 2ⁿ⁻¹ आहे. मूल्यांकने संमिश्र संख्या असतानाही हीच मर्यादा शोधनिबंधात सिद्ध केली आहे.

सगळे एकदम विचारण्याची किंमत

अधिक नेमके एक विधान गटांमध्ये केलेल्या मूल्यांकनांना लागू होते, जिथे गटातील प्रत्येक प्रश्न त्या गटाचे कोणतेही उत्तर येण्यापूर्वीच निवडलेला असतो — समांतर (parallel) पद्धतींची हीच स्थिती असते. ℓ₁, …, ℓₖ आकारांच्या गटांसह, क्रम जास्तीत जास्त ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1) असतो. सर्व n प्रश्न एकदम विचारल्याने क्रम n वर मर्यादित होतो; ते एकेक करून विचारल्याने 2ⁿ⁻¹ शक्य होतो. पाच मूल्यांकनांसह, हे 5 विरुद्ध 16 आहे.

यंत्राने तपासलेले

हे निष्कर्ष Lean मध्ये औपचारिकपणे पडताळले गेले आहेत — Lean हा प्रत्येक तार्किक पायरी तपासणारा एक प्रूफ असिस्टंट (proof assistant) आहे. कोड सार्वजनिक आहे आणि Palomar नोंदवहीत नोंदवलेला आहे. Colbrook यांनी नमूद केले आहे की Lean मधील औपचारिकीकरण ChatGPT 6 च्या मदतीने करण्यात आले, मग Lean 4 Comparator द्वारे शोधनिबंधातील प्रमेयांशी ताडून तपासले गेले, आणि प्रत्येक युक्तिवादाचे पुनरावलोकन Colbrook यांनी केले असून आशयाची संपूर्ण जबाबदारी त्यांनी स्वीकारली आहे.

ही मर्यादा विसरणाऱ्या पद्धतींबाबत आहे. आपल्या आधीच्या पायऱ्या पुन्हा वापरण्याची मुभा असलेल्या पद्धती इतर मर्यादांचे पालन करतात, ज्यांचा विचार हा शोधनिबंध करत नाही.