সমীকরণ সমাধানের 1974 সালের এক গতিসীমা, অবশেষে প্রমাণিত

একটি ফাংশন f কোথায় শূন্য অতিক্রম করে তা খুঁজতে কম্পিউটার প্রায়ই একটি পুনরাবৃত্তি (iteration) চালায়: একটি অনুমান x থেকে শুরু করে, ফাংশনটিকে কয়েকটি প্রশ্ন করে, আরও ভালো একটি অনুমান হিসাব করে, এবং আবার একই কাজ করে। প্রশ্নগুলো হলো মূল্যায়ন (evaluations): কোনো বিন্দুতে f-এর মান, বা তার ঢালের (অবকলজ) মান, বা কোনো উচ্চতর অবকলজের মান।

যে অঙ্কগুলো দ্বিগুণ হয়

এমন একটি পদ্ধতির গতি মাপা হয় তার ক্রম (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-এর একটি গবেষণাপত্রের “অনুমান 8.1” (Conjecture 8.1) হিসেবে একটি উত্তর প্রস্তাব করেন: প্রতি ধাপে n টি মূল্যায়ন ব্যবহারকারী স্মৃতিহীন (without memory) একটি পুনরাবৃত্তির ক্রম সর্বোচ্চ 2ⁿ⁻¹। “স্মৃতিহীন” মানে, পদ্ধতিটি তার বর্তমান অনুমান ছাড়া আগের ধাপগুলো থেকে কিছুই রাখে না।

সীমাটি নামানো সম্ভব ছিল না: কুং ও ট্রাউব নিজেরাই প্রতিটি n ≥ 2-এর জন্য 2ⁿ⁻¹-এ পৌঁছানো “বহুবিন্দু” (multipoint) পদ্ধতি বানিয়েছিলেন — তিনটি মূল্যায়নে ক্রম 4, চারটিতে 8, পাঁচটিতে 16। যা অনুপস্থিত ছিল তা হলো অন্য অর্ধেক: এই প্রমাণ যে কোনো পদ্ধতিই এর চেয়ে ভালো করতে পারে না। আংশিক ফলাফল এসেছিল অনুমানটির সঙ্গেই এবং তার পরেও। সীমাটি প্রমাণিত হয়েছিল অন্তর্বেশন-ভিত্তিক (interpolation-based) পদ্ধতির জন্য, দুটি মূল্যায়নসহ মূলদ পদ্ধতির জন্য, এবং নানা অতিরিক্ত শর্তের অধীনে; কেবল ফাংশনের মান ব্যবহারকারী পদ্ধতির জন্য একটি দুর্বলতর সীমা, 2ⁿ, প্রতিষ্ঠিত হয়েছিল। সাধারণ ক্ষেত্রটি খোলাই থেকে গিয়েছিল।

অ্যালগরিদমকে ধোঁকা দেওয়া

ইউনিভার্সিটি অব কেমব্রিজের ডিপার্টমেন্ট অব অ্যাপ্লায়েড ম্যাথমেটিক্স অ্যান্ড থিওরেটিক্যাল ফিজিক্সের (Department of Applied Mathematics and Theoretical Physics) ম্যাথিউ কলব্রুক (Matthew Colbrook) এখন এটি পুরোপুরি প্রমাণ করেছেন। মডেলটি ইচ্ছাকৃতভাবে অ্যালগরিদমের প্রতি উদার। চলতে চলতে সে বেছে নিতে পারে কোথায় মূল্যায়ন করবে এবং কোন অবকলজ নেবে। উত্তরগুলোকে সে নিজের পছন্দমতো যেকোনো নির্ধারিত (deterministic) উপায়ে প্রক্রিয়া করতে পারে, তার নিয়মগুলোর কোনো মসৃণতার শর্ত ছাড়াই।

প্রমাণটি অ্যালগরিদমের নিজের নির্ধারণবাদকেই তার বিরুদ্ধে কাজে লাগায়। এমন দুটি ফাংশন বানান যারা তার সব প্রশ্নের হুবহু একই উত্তর দেয় কিন্তু যাদের শূন্যবিন্দু ভিন্ন। অ্যালগরিদমকে দুটোর জন্যই একই অনুমান ফেরত দিতে হবে, তাই এদের একটিতে সে অন্তত দুই শূন্যবিন্দুর মধ্যকার দূরত্বের অর্ধেক ব্যবধানে লক্ষ্যভ্রষ্ট হয়।

এমন জোড়া খুঁজতে কলব্রুক একটি প্রসঙ্গ-ফাংশনকে সর্বোচ্চ n ঘাতের একটি ছোট বহুপদী দিয়ে সামান্য ঠেলে দেন, যার n + 1টি সমন্বয়যোগ্য সহগ আছে। প্রতিটি মূল্যায়ন এদের সর্বোচ্চ একটি সমাবেশকে স্থির করে দেয়, তাই n টি প্রশ্নের পরেও কিছু ঠেলা অ্যালগরিদমের কাছে অদৃশ্য থেকে যায়। শুধু এই গণনাই যথেষ্ট নয়: একটি অদৃশ্য ঠেলা হয়তো শূন্যবিন্দুকে প্রায় নড়াবেই না।

মূল হাতিয়ার হলো রনস্কিয়ান (Wronskian) — বহুপদীর একটি পরিবার ও তাদের অবকলজ থেকে গড়া একটি নির্ণায়ক। একটি নতুন লেমা বলে, পরিবারের কোনো বহুপদীর যদি একটি ছোট চাকতির মধ্যে অনেকগুলো শূন্যবিন্দু ঠাসা থাকে, তাহলে কাছেই পরিবারটির রনস্কিয়ানকে শূন্য হতে হবে। অ্যালগরিদমকে সবসময় এমন একটি ফাংশন দিয়ে উত্তর দিয়ে, যার শূন্যবিন্দু এই অল্প কয়েকটি বিন্দু থেকে দূরে থাকে, প্রমাণটি শূন্যবিন্দুকে নড়াচড়ার জন্য মুক্ত রাখে।

হিসাবনিকাশ থেকেই সূচকটি বেরিয়ে আসে। শূন্যবিন্দু থেকে ε দূরত্বে শুরু করলে, সম্ভাব্য শূন্যবিন্দুগুলো অন্তত ε-এর একটি ঘাতের একটি ধ্রুবক গুণিতকের সমান পরিসর জুড়ে ছড়িয়ে থাকে। লেখকের ভাষায়, “প্রথম পর্যবেক্ষণের পর সূচকটি এক থাকে এবং তারপর দ্বিগুণ হয়, 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 দিয়ে গবেষণাপত্রের উপপাদ্যগুলোর সঙ্গে মিলিয়ে যাচাই করা হয়েছে, এবং প্রতিটি যুক্তি লেখক নিজে পর্যালোচনা করেছেন, যিনি বিষয়বস্তুর পূর্ণ দায়িত্ব নিচ্ছেন।

সীমাটি সেই পদ্ধতিগুলো নিয়ে যারা ভুলে যায়। যেসব পদ্ধতি তাদের আগের ধাপগুলো আবার ব্যবহার করতে পারে, তারা অন্য সীমা মেনে চলে, যা এই গবেষণাপত্র পাশে সরিয়ে রেখেছে।