حد سرعتی از سال 1974 برای حل معادله‌ها، سرانجام اثبات شد

رایانه برای یافتن نقطه‌ای که تابع f در آن از صفر می‌گذرد، اغلب یک تکرار (iteration) را اجرا می‌کند: از یک حدس x آغاز می‌کند، چند پرسش از تابع می‌پرسد، حدسی بهتر محاسبه می‌کند و همین کار را تکرار می‌کند. این پرسش‌ها ارزیابی (evaluation) نام دارند: مقدار f در یک نقطه، یا مقدار شیب آن (مشتق)، یا مقدار مشتقی از مرتبهٔ بالاتر.

رقم‌هایی که دو برابر می‌شوند

سرعت چنین روشی با مرتبه (order) آن سنجیده می‌شود. اگر خطای کنونی ε باشد، تکراری از مرتبهٔ p خطایی تقریباً برابر با ε به توان p برجا می‌گذارد. مرتبهٔ 2 یعنی در نزدیکی پاسخ، شمار رقم‌های درست در هر گام دو برابر می‌شود؛ مرتبهٔ 4 یعنی چهار برابر می‌شود.

روش نیوتن در هر گام دو ارزیابی صرف می‌کند — f(x) و شیب آن، f′(x) — و به x − f(x)/f′(x) می‌رود. مرتبهٔ آن 2 است. پرسیدن پرسش‌های بیشتر در هر گام می‌تواند سرعت بیشتری به همراه بیاورد. پرسش این است که چه اندازه.

حدسی از سال 1974

در سال 1974، اچ. تی. کونگ (H. T. Kung) و جی. اف. تراب (J. F. Traub) پاسخی پیشنهاد کردند، با عنوان «حدس 8.1» (Conjecture 8.1) در مقاله‌ای در Journal of the ACM: تکراری بدون حافظه که در هر گام n ارزیابی به کار می‌برد، مرتبه‌ای حداکثر برابر با 2ⁿ⁻¹ دارد. «بدون حافظه» یعنی روش از گام‌های پیشین چیزی جز حدس کنونی‌اش نگه نمی‌دارد.

این کران را نمی‌شد پایین‌تر آورد: خودِ کونگ و تراب روش‌هایی «چندنقطه‌ای» (multipoint) ساخته بودند که برای هر n ≥ 2 به 2ⁿ⁻¹ می‌رسیدند — مرتبهٔ 4 با سه ارزیابی، 8 با چهار، 16 با پنج. آنچه کم بود نیمهٔ دیگر بود: اثباتی که نشان دهد هیچ روشی نمی‌تواند بهتر عمل کند. نتایجی جزئی همراه با این حدس و پس از آن به دست آمد. این کران برای روش‌های مبتنی بر درون‌یابی، برای روش‌های گویا با دو ارزیابی، و با شرط‌های اضافی گوناگون اثبات شد؛ برای روش‌هایی که فقط از مقادیر تابع بهره می‌برند، کرانی ضعیف‌تر، یعنی 2ⁿ، ثابت شد. حالت کلی همچنان باز ماند.

فریب دادن الگوریتم

متیو کولبروک (Matthew Colbrook)، از دپارتمان ریاضیات کاربردی و فیزیک نظری دانشگاه کمبریج، اکنون آن را به‌طور کامل اثبات می‌کند. مدلِ او عامدانه با الگوریتم سخاوتمند است. الگوریتم می‌تواند در حین کار انتخاب کند که کجا ارزیابی کند و کدام مشتق‌ها را بگیرد. می‌تواند پاسخ‌ها را به هر شیوهٔ قطعی (deterministic) که بخواهد پردازش کند، بی‌آنکه هیچ همواری‌ای از قواعدش خواسته شود.

اثبات، قطعی بودنِ خودِ الگوریتم را علیه آن به کار می‌گیرد. دو تابع بسازید که به همهٔ پرسش‌های الگوریتم دقیقاً پاسخ‌های یکسان بدهند اما صفرهای متفاوت داشته باشند. الگوریتم ناچار است برای هر دو یک حدس یکسان برگرداند، پس روی یکی از آن دو دست‌کم به اندازهٔ نیمی از فاصلهٔ میان دو صفر خطا می‌کند.

برای یافتن چنین جفت‌هایی، کولبروک یک تابع مرجع را با افزودن چندجمله‌ای کوچکی از درجهٔ حداکثر n اندکی تغییر می‌دهد؛ این چندجمله‌ای n + 1 ضریب قابل‌تنظیم دارد. هر ارزیابی حداکثر یک ترکیب از این ضریب‌ها را تثبیت می‌کند، پس پس از n پرسش، برخی از این تغییرهای کوچک برای الگوریتم نامرئی می‌مانند. این شمارش به‌تنهایی کافی نیست: یک تغییر نامرئی ممکن است صفر را تنها به‌زحمت جابه‌جا کند.

ابزار کلیدی رونسکین (Wronskian) است — دترمینانی که از خانواده‌ای از چندجمله‌ای‌ها و مشتق‌هایشان ساخته می‌شود. یک لم تازه می‌گوید که اگر یکی از چندجمله‌ای‌های این خانواده صفرهای بسیاری داشته باشد که در قرصی کوچک فشرده شده‌اند، رونسکینِ خانواده باید در همان نزدیکی صفر شود. یک رونسکین تنها شمار محدودی صفر دارد. اثبات با پاسخ دادن همیشگی به الگوریتم از طریق تابعی که صفرش از این صفرها دور می‌ماند، صفر را آزاد نگه می‌دارد تا جابه‌جا شود.

حساب‌وکتاب، نما را به دست می‌دهد. با آغاز از فاصلهٔ ε از صفر، صفرهای ممکن بر بازه‌ای پراکنده می‌مانند که دست‌کم برابر با یک ثابت ضرب در توانی از ε است. به گفتهٔ نویسنده، «نما پس از نخستین مشاهده یک می‌ماند و سپس دو برابر می‌شود، و پس از n مشاهده 2ⁿ⁻¹ به دست می‌دهد.» از آنجا که الگوریتم نمی‌تواند این صفرها را از هم تشخیص دهد، خطایش نمی‌تواند همیشه به زیر یک ثابت ضرب در ε به توان 2ⁿ⁻¹ برسد: هیچ مرتبه‌ای بالاتر از 2ⁿ⁻¹ ممکن نیست.

یک تابع برای همهٔ مقیاس‌ها

یک دشواری باقی ماند. تعریف مرتبه تنها می‌خواهد که خطا زیر یک ثابت ضرب در ε به توان p بماند، و این ثابت ممکن است به تابع بستگی داشته باشد؛ پس اگر در هر مقیاس یک تابع بدِ متفاوت داشته باشیم، چیزی اثبات نمی‌شود. از این رو کولبروک یک تابع واحد می‌سازد و اصلاح‌ها را یکی پس از دیگری به آن می‌افزاید؛ هر اصلاح در همهٔ نقطه‌هایی که الگوریتم پیش‌تر پرسیده صفر می‌شود، تا همهٔ پاسخ‌های گذشته دقیقاً همان بمانند.

تابع حدی یک تابع تام (entire function) است — همه‌جا هموار، حتی روی اعداد مختلط — که شیبش روی خط حقیقی میان 3/4 و 5/4 می‌ماند: منحنی‌ای که پیوسته بالا می‌رود و یک صفرِ خوش‌رفتار دارد. برای هر p بالاتر از 2ⁿ⁻¹، روش روی این تابع به مرتبهٔ p نمی‌رسد. بنابراین مرتبهٔ بهینهٔ بدون حافظه برای n ≥ 2 دقیقاً 2ⁿ⁻¹ است. مقاله همین کران را برای حالتی که ارزیابی‌ها اعداد مختلط باشند نیز اثبات می‌کند.

بهای پرسیدن همه با هم

گزاره‌ای دقیق‌تر ارزیابی‌هایی را در بر می‌گیرد که به صورت گروهی انجام می‌شوند، یعنی هر پرسشِ یک گروه پیش از رسیدن هر یک از پاسخ‌های آن گروه انتخاب می‌شود — وضعیت روش‌های موازی. با گروه‌هایی به اندازه‌های ℓ₁, …, ℓₖ، مرتبه حداکثر ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1) است. پرسیدن همهٔ n پرسش با هم، مرتبه را به n محدود می‌کند؛ پرسیدن آن‌ها یکی‌یکی 2ⁿ⁻¹ را ممکن می‌سازد. با پنج ارزیابی، این یعنی 5 در برابر 16.

وارسی‌شده به دست ماشین

نتایج به‌طور صوری در لین (Lean) راستی‌آزمایی شده‌اند، دستیار اثباتی که تک‌تک گام‌های منطقی را وارسی می‌کند. کد عمومی است و در یک فهرست عمومی از اثبات‌های صوری (Palomar) ثبت شده است. نویسنده اعلام می‌کند که صوری‌سازی در لین با کمک ChatGPT 6 انجام شد، سپس با Lean 4 Comparator در برابر قضیه‌های مقاله وارسی شد، و همهٔ استدلال‌ها را خودِ نویسنده بازبینی کرد که مسئولیت کامل محتوا را بر عهده می‌گیرد.

این حد به روش‌هایی مربوط است که فراموش می‌کنند. روش‌هایی که اجازه دارند گام‌های پیشین خود را دوباره به کار گیرند از کران‌های دیگری پیروی می‌کنند که این مقاله به آن‌ها نمی‌پردازد. و این کران مربوط به بدترین حالت است: روی برخی تابع‌های خاص، یک روش همچنان می‌تواند سریع‌تر پیش برود.