22 عملية ضرب، ولا واحدة أقل

تضارب مصالح. يذكر المؤلفان أن وكلاء ذكاء اصطناعي — Claude من شركة Anthropic — كتبوا، بتوجيه منهما، شيفرة البحث وبراهين Lean التي لا تحتاج إلى مدقق بشري، أما الجزء الذي يجب أن يدققه إنسان فقد صمّمه المؤلفان. وهذا المقال أيضًا من كتابة Claude.

يتطلب ضرب شبكتين مربعتين من الأعداد — مصفوفتين — بالطريقة المدرسية n³ عملية ضرب لشبكات من n صفًا وn عمودًا. وقد بيّن شتراسن أن مصفوفتين من 2 × 2 يمكن ضربهما بـسبع عمليات ضرب بدلًا من ثماني. ويمكن تطبيق الحيلة تكراريًا: تُقطَّع مصفوفة كبيرة إلى أربع كتل، وتُعامَل كل كتلة كأنها عدد واحد، ثم يُكرَّر ذلك. فتنمو الكلفة حينئذ مثل n^2.807 بدلًا من n³. ووفقًا للورقة، ثبت في 1971 أن وصفة 2 × 2 هذه هي المثلى.

والفكرة نفسها تصلح لأي حجم ثابت. فالوصفة التي تضرب مصفوفتين من 3 × 3 بـr عملية ضرب، وتظل صالحة حين تكون المُدخلات كتلًا، تعطي كلفة تنمو مثل n مرفوعًا إلى القوة log₃ r. وحساب بسيط يحدد ما على المحك: مثل هذه الوصفة تتفوق على شتراسن تمامًا حين تكون r تساوي 21 أو أقل، وتخسر عند 22 أو أكثر. أفضل وصفة 3 × 3 معروفة، وهي من وضع لادرمان، تستخدم 23 عملية ضرب ولم تُحسَّن منذ 1976.

باب ظل مواربًا

يُسمّى أفضل عدد ممكن لمسألة ما رتبتها. وقد ارتفعت الحدود الدنيا لرتبة ضرب 3 × 3 ببطء: 19 في 2003، ثم 20 في مارس 2026، حسبها Wang على نظام عددي صغير جدًا لا يضم إلا 0 و1، حيث 1 + 1 = 0. وفي سبتمبر 2026، بلغ Wang وفريق بقيادة Yang الرقم 21 كلٌّ على حدة، بفارق عشرة أيام. لكن 21 كان لا يزال يترك مجالًا لوصفة 3 × 3 أسرع من وصفة شتراسن.

وقد دفع إسحاق روديتش (Isaac Rudich)، من بوليتكنيك مونتريال وجامعة كارنيغي ميلون، ولويس-مارتان روسو (Louis-Martin Rousseau)، من بوليتكنيك مونتريال، هذا الحد الآن إلى 22.

المبرهنة 1. كل خوارزمية تضرب مصفوفتين من 3 × 3 بثوابت صحيحة، ويمكن تطبيقها تكراريًا على كتل بأي حجم، تستخدم 22 عملية ضرب على الأقل.

لذلك لا يمكن لأي خوارزمية من هذا النوع أن تفعل أفضل من نحو n^2.814 — ولا يمكن لأي منها أن تتفوق على طريقة شتراسن 2 × 2.

496 أحجية أصغر

يستند البرهان إلى جدول ابتكره Wang، يقسم المسألة الصعبة إلى 496 مسألة أسهل. كل واحدة منها تضيف «شروطًا» على المصفوفة الأولى — مثلًا، أن يكون مجموع بعض مُدخلاتها صفرًا. وكلما زادت الشروط سهلت المسألة، وصولًا إلى الحالة البديهية التي تكون فيها المصفوفة كلها أصفارًا.

بنى المؤلفان أولًا برنامج بحث دقيق أعطاهما الجواب الحقيقي لكل أحجية قبل أن يحاولا برهنته. وكانت هذه الأجوبة بمثابة خريطة: بيّنت أي الحدود الدنيا يستحق السعي وراءه. وفي النهاية، يضع برهانهما حدودًا لكل الأحجيات الـ496، ويحسم 359 منها بدقة — مقابل 195 في أحدث نتائج Wang — ويرفع الحد الأدنى لـ252 منها. ومبرهنة «لصق» خاصة بهما تجمع وصفتين لأحجيتين أسهل في وصفة لأحجية ثالثة، وقد وفّرت 145 من الحدود العليا.

شرطان مهمان في الصياغة النهائية. الثوابت الصحيحة: الوصفة ذات الثوابت الصحيحة، إذا قُرئت في النظام العددي المكوّن من 0 و1، تبقى وصفة صالحة بلا عمليات ضرب إضافية، فينتقل الحد إليها. الكتل: من دون هذا الشرط توجد طرق مختصرة. فخوارزمية روزوفسكي (Rosowski) للمصفوفات 3 × 3، المذكورة في الورقة، تحتاج إلى 21 عملية ضرب فقط، لكنها تعتمد على تبديلية ضرب الأعداد ولا يمكن تطبيقها تكراريًا.

برهان تتحقق منه آلة

البرهان مكتوب بلغة Lean، وهي لغة برمجة لا تُترجَم فيها المبرهنة إلا إذا جرى التحقق من كل خطوة. ويمتد البرهان الكامل على نحو مليون سطر موزعة على 3,521 وحدة، ويستغرق التحقق منه 11.1 ساعة على نواة معالج واحدة. ولا أحد يحتاج إلى قراءته كله. فالمدقق يقرأ مكتبة من نحو 1,000 سطر، كتبها المؤلفان قبل وجود أي برهان، تُعرّف ما هي وصفة الضرب وتنص على المبرهنة؛ ونواة Lean تتحقق من الباقي، ويمكن لمدقق مستقل أن يعيد إنتاج النتيجة.

ويشير المؤلفان أيضًا إلى أن وكلاء الذكاء الاصطناعي بحثوا في الأدبيات: تحققوا من وجود كل مرجع، «لكن ليس من أن كل مرجع يتضمن بالضبط الفكرة التي ننسبها إليه».

الفجوة الأخيرة

يبقى سؤال واحد: هل توجد وصفة 3 × 3 بـ22 عملية ضرب، أم أن رقم لادرمان 23 هو الحد الأدنى الحقيقي؟ يتوقع المؤلفان أن تُسدّ الفجوة «قريبًا جدًا»، وسينشران شيفرة البحث حين يحدث ذلك، أو حين تُقبل الورقة للنشر. كما يترك الحد جانبًا الوصفات ذات الثوابت غير الصحيحة.