समीकरण हल करने की 1974 की एक गति-सीमा, आख़िरकार सिद्ध

यह पता लगाने के लिए कि कोई फ़ंक्शन f कहाँ शून्य को काटता है, कंप्यूटर अक्सर एक पुनरावृत्ति (iteration) चलाता है: एक अनुमान x से शुरू करो, फ़ंक्शन से कुछ प्रश्न पूछो, एक बेहतर अनुमान निकालो, और दोहराओ। ये प्रश्न मूल्यांकन (evaluations) होते हैं: किसी बिंदु पर f का मान, या उसकी ढलान (अवकलज, derivative) का, या किसी उच्चतर अवकलज का।

दोगुने होते अंक

ऐसी विधि की गति उसकी कोटि (order) से मापी जाती है। अगर वर्तमान त्रुटि ε है, तो कोटि p की एक पुनरावृत्ति मोटे तौर पर ε की घात p जितनी त्रुटि छोड़ती है। कोटि 2 का अर्थ है कि उत्तर के पास, हर क़दम पर सही अंकों की संख्या दोगुनी हो जाती है; कोटि 4 का, कि वह चौगुनी हो जाती है।

न्यूटन की विधि (Newton’s method) हर क़दम पर दो मूल्यांकन ख़र्च करती है — 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 मूल्यांकन इस्तेमाल करती है, की कोटि अधिकतम 2ⁿ⁻¹ होती है। “बिना स्मृति” का अर्थ है कि विधि अपने वर्तमान अनुमान के अलावा पिछले क़दमों से कुछ भी नहीं रखती।

इस सीमा को नीचे नहीं लाया जा सकता था: कुंग और ट्राउब ने ख़ुद हर n ≥ 2 के लिए 2ⁿ⁻¹ तक पहुँचने वाली “बहुबिंदु” (multipoint) विधियाँ बनाई थीं — तीन मूल्यांकनों से कोटि 4, चार से 8, पाँच से 16। जो कमी थी वह दूसरा आधा था: यह प्रमाण कि कोई भी विधि इससे बेहतर नहीं कर सकती। आंशिक परिणाम अनुमान के साथ भी आए और उसके बाद भी। यह सीमा अंतर्वेशन-आधारित (interpolation-based) विधियों के लिए, दो मूल्यांकनों वाली परिमेय विधियों के लिए, और विभिन्न अतिरिक्त शर्तों के तहत सिद्ध हुई; केवल फ़ंक्शन के मानों का उपयोग करने वाली विधियों के लिए, एक कमज़ोर सीमा, 2ⁿ, स्थापित हुई। सामान्य मामला खुला रहा।

एल्गोरिद्म को चकमा देना

कैंब्रिज विश्वविद्यालय के अनुप्रयुक्त गणित और सैद्धांतिक भौतिकी विभाग (Department of Applied Mathematics and Theoretical Physics) में कार्यरत मैथ्यू कोलब्रुक ने अब इसे पूरी तरह सिद्ध कर दिया है। मॉडल जानबूझकर एल्गोरिद्म के प्रति उदार है। वह चलते-चलते चुन सकता है कि कहाँ मूल्यांकन करे, और कौन-से अवकलज ले। वह उत्तरों को अपनी पसंद के किसी भी नियतात्मक (deterministic) तरीक़े से संसाधित कर सकता है, उसके नियमों से किसी सुचारुता (smoothness) की अपेक्षा किए बिना।

प्रमाण एल्गोरिद्म की अपनी नियतात्मकता को उसी के ख़िलाफ़ मोड़ देता है। ऐसे दो फ़ंक्शन बनाइए जो उसके सभी प्रश्नों के बिल्कुल एक जैसे उत्तर दें लेकिन जिनके शून्य अलग हों। एल्गोरिद्म को दोनों के लिए एक ही अनुमान लौटाना होगा, इसलिए उनमें से किसी एक पर वह दोनों शून्यों के बीच की दूरी के कम से कम आधे से चूकता है।

ऐसे जोड़े खोजने के लिए, प्रमाण एक संदर्भ फ़ंक्शन को अधिकतम n घात वाले एक छोटे बहुपद से थोड़ा खिसकाता है, जिसके n + 1 समायोज्य गुणांक होते हैं। हर मूल्यांकन उनके अधिकतम एक संयोजन को तय करता है, इसलिए n प्रश्नों के बाद कुछ खिसकाव एल्गोरिद्म के लिए अदृश्य रह जाते हैं। अकेली यह गिनती काफ़ी नहीं है: कोई अदृश्य खिसकाव शून्य को मुश्किल से हिला सकता है।

मुख्य औज़ार रॉन्स्कियन (Wronskian) है — बहुपदों के एक परिवार और उनके अवकलजों से बना एक सारणिक (determinant)। एक नई लेम्मा कहती है कि अगर परिवार के किसी बहुपद के कई शून्य एक छोटी चकती में ठसाठस भरे हों, तो परिवार का रॉन्स्कियन पास ही कहीं शून्य होना चाहिए। एल्गोरिद्म को हमेशा ऐसे फ़ंक्शन से उत्तर देकर जिसका शून्य इन गिने-चुने बिंदुओं से दूर रहे, प्रमाण शून्य को हिलने के लिए आज़ाद रखता है।

हिसाब-किताब से घातांक निकलता है। शून्य से ε की दूरी पर शुरू करने पर, संभावित शून्य कम से कम एक स्थिरांक गुणा ε की किसी घात जितने दायरे में फैले रहते हैं। लेखक के शब्दों में, “घातांक पहले प्रेक्षण के बाद एक रहता है और फिर दोगुना होता है, जिससे n प्रेक्षणों के बाद 2ⁿ⁻¹ मिलता है।”

हर पैमाने के लिए एक फ़ंक्शन

एक कठिनाई बाक़ी थी। कोटि की परिभाषा आगे वाले स्थिरांक को फ़ंक्शन पर निर्भर होने देती है, इसलिए हर पैमाने पर एक अलग बुरा फ़ंक्शन कुछ भी सिद्ध नहीं करता। इसलिए प्रमाण एक अकेला फ़ंक्शन बनाता है, एक के बाद एक सुधार जोड़कर, जिनमें से हर एक उन सभी बिंदुओं पर शून्य होता है जिनसे एल्गोरिद्म पहले ही प्रश्न पूछ चुका है, ताकि पिछले सभी उत्तर बिल्कुल वही रहें।

सीमा पर मिलने वाला फ़ंक्शन एक संपूर्ण फ़ंक्शन (entire function) है — हर जगह सुचारु, सम्मिश्र संख्याओं पर भी — जिसकी ढलान वास्तविक रेखा पर 3/4 और 5/4 के बीच रहती है: एक लगातार चढ़ता वक्र जिसका एक सुव्यवस्थित शून्य है। 2ⁿ⁻¹ से ऊपर के किसी भी p के लिए, विधि इस पर कोटि p तक पहुँचने में विफल रहती है। इसलिए n ≥ 2 के लिए बिना स्मृति वाली इष्टतम कोटि ठीक 2ⁿ⁻¹ है। शोधपत्र यही सीमा तब भी सिद्ध करता है जब मूल्यांकन सम्मिश्र संख्याएँ हों।

सब कुछ एक साथ पूछने की क़ीमत

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

मशीन द्वारा जाँचा गया

परिणामों को Lean में औपचारिक रूप से सत्यापित किया गया है, जो एक प्रूफ़ असिस्टेंट है और हर तार्किक क़दम की जाँच करता है। कोड सार्वजनिक है और Palomar रजिस्ट्री में दर्ज है। लेखक के कथन के अनुसार, Lean औपचारिकीकरण ChatGPT 6 की मदद से किया गया, फिर Lean 4 Comparator से शोधपत्र के प्रमेयों के विरुद्ध जाँचा गया, और हर तर्क की समीक्षा लेखक ने की, जिन पर सामग्री की पूरी ज़िम्मेदारी है।

यह सीमा उन विधियों से संबंधित है जो भूल जाती हैं। जिन विधियों को अपने पिछले क़दमों का दोबारा उपयोग करने की अनुमति है, वे दूसरी सीमाओं का पालन करती हैं, जिन्हें यह शोधपत्र अलग छोड़ देता है।