حدّ سرعة لحلّ المعادلات يعود إلى عام 1974، أُثبت أخيرًا

لإيجاد النقطة التي تقطع فيها دالةٌ f الصفر، كثيرًا ما يُجري الحاسوب تكرارًا (iteration): يبدأ من تخمين x، ويطرح على الدالة بضعة أسئلة، ويحسب تخمينًا أفضل، ثم يكرّر. والأسئلة هي تقييمات (evaluations): قيمة 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) تبلغ 2ⁿ⁻¹ لكل n ≥ 2، أي الرتبة 4 بثلاثة تقييمات، و8 بأربعة، و16 بخمسة. وما كان ينقص هو النصف الآخر: برهان على أن لا طريقة تستطيع أن تفعل أفضل. وجاءت نتائج جزئية مع التخمين وبعده. فقد أُثبت الحدّ للطرق القائمة على الاستيفاء (interpolation)، وللطرق الكسرية (rational) ذات التقييمين، وفي ظل شروط إضافية متنوعة؛ وللطرق التي لا تستخدم إلا قيم الدالة، أُثبت حدّ أضعف هو 2ⁿ. وبقيت الحالة العامة مفتوحة.

خداع الخوارزمية

ويُثبته الآن ماثيو كولبروك، من قسم الرياضيات التطبيقية والفيزياء النظرية في جامعة كامبريدج، بصورة كاملة. والنموذج سخيّ عمدًا مع الخوارزمية. فلها أن تختار أين تُجري التقييم، وأي المشتقات تأخذ، أثناء سيرها. ولها أن تعالج الأجوبة بأي طريقة حتمية تشاء، من دون أي اشتراط للنعومة (smoothness) في قواعدها.

يقلب البرهان حتميةَ الخوارزمية نفسها ضدها. ابنِ دالتين تعطيان الأجوبة نفسها تمامًا عن كل أسئلتها لكن لهما صفران مختلفان. فيجب على الخوارزمية أن تُرجع التخمين نفسه لكلتيهما، لذا فإنها تخطئ في إحداهما بما لا يقل عن نصف المسافة بين الصفرين.

ولإيجاد أزواج كهذه، يُزيح كولبروك دالةً مرجعية إزاحة طفيفة بإضافة كثيرة حدود صغيرة درجتها n على الأكثر، لها n + 1 معاملًا قابلًا للضبط. وكل تقييم يثبّت تركيبة واحدة منها على الأكثر، لذا تبقى بعد n سؤالًا بعضُ الإزاحات غير مرئية للخوارزمية. لكن هذا العدّ وحده لا يكفي: فقد لا تحرّك إزاحةٌ غير مرئية الصفرَ إلا بالكاد.

والأداة الأساسية هي الرونسكيان (Wronskian)، وهو محدِّدة تُبنى من عائلة من كثيرات الحدود ومشتقاتها. وتنص مُبرهنة مساعدة (lemma) جديدة على أنه إذا كان لكثيرة حدود من العائلة أصفار كثيرة متراصّة في قرص صغير، فلا بد أن ينعدم رونسكيان العائلة في جوارها. وبالإجابة دائمًا على الخوارزمية بدالة يبقى صفرها بعيدًا عن هذه النقاط القليلة، يُبقي البرهانُ الصفرَ حرًّا في الحركة.

والحساب الدقيق هو ما يُنتج الأُس. فبدءًا من مسافة ε من الصفر، تبقى الأصفار الممكنة موزّعة على مدى لا يقل عن ثابتٍ مضروبٍ في قوة من قوى ε. وبعبارة المؤلف، «يبقى الأُس واحدًا بعد الملاحظة الأولى ثم يتضاعف، فيعطي 2ⁿ⁻¹ بعد n ملاحظة».

دالة واحدة لكل المقاييس

بقيت صعوبة واحدة. فتعريف الرتبة يسمح للثابت في المقدمة بأن يعتمد على الدالة، لذا فإن دالة سيئة مختلفة عند كل مقياس لا تُثبت شيئًا. ولذلك يبني كولبروك دالةً واحدة، بإضافة تصحيحات واحدًا تلو الآخر، كلٌّ منها ينعدم عند كل نقطة سبق أن استعلمت عنها الخوارزمية، بحيث تبقى كل الأجوبة السابقة كما هي تمامًا.

والنهاية دالة تامّة (entire function)، أي ملساء في كل مكان، حتى على الأعداد المركّبة، ويبقى ميلها بين 3/4 و5/4 على المستقيم الحقيقي: منحنى صاعد بانتظام له صفر واحد حسن السلوك. ولكل p أكبر من 2ⁿ⁻¹، تفشل الطريقة في بلوغ الرتبة p على هذه الدالة. لذا فإن الرتبة المثلى بلا ذاكرة هي 2ⁿ⁻¹ تمامًا لـn ≥ 2. وتُثبت الورقة الحدّ نفسه حين تكون التقييمات أعدادًا مركّبة.

ثمن السؤال دفعة واحدة

وتغطي عبارةٌ أدقّ التقييماتِ التي تُجرى في مجموعات، حيث يُختار كل سؤال في المجموعة قبل وصول أيٍّ من أجوبتها، وهي حالة الطرق المتوازية. فمع مجموعات أحجامها ℓ₁, …, ℓₖ، تكون الرتبة على الأكثر ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1). وطرح الأسئلة الـn كلها دفعة واحدة يحدّ الرتبة عند n؛ وطرحها واحدًا تلو الآخر يسمح بـ2ⁿ⁻¹. ومع خمسة تقييمات، هذا 5 مقابل 16.

تحقّق آلي

النتائج مُتحقَّق منها صوريًا في Lean، وهو مساعد براهين يتحقق من كل خطوة منطقية. والرمز البرمجي علني ومسجّل في سجلّ Palomar. ويذكر المؤلف أن الصياغة الصورية في Lean أُنجزت بمساعدة ChatGPT 6، ثم تُحقّق منها باستخدام Lean 4 Comparator في مقابل مبرهنات الورقة، وأن المؤلف راجع كل حجة، ويتحمّل المسؤولية الكاملة عن المحتوى.

ويتعلق هذا الحدّ بالطرق التي تنسى. أما الطرق المسموح لها بإعادة استخدام خطواتها السابقة فتخضع لحدود أخرى، تتركها هذه الورقة جانبًا.