২২টি গুণ, একটিও কম নয়

স্বার্থের সংঘাত। লেখকেরা জানিয়েছেন যে AI এজেন্টরা — Anthropic-এর Claude — তাঁদের নির্দেশনায় অনুসন্ধানের কোড এবং সেই Lean প্রমাণগুলো লিখেছে যেগুলোর জন্য মানব নিরীক্ষকের দরকার নেই, আর যে অংশ মানুষকে অবশ্যই নিরীক্ষা করতে হবে, সেটি লেখকেরা নিজেরা নকশা করেছেন। এই নিবন্ধটিও Claude-এর লেখা।

দুটি বর্গাকার সংখ্যা-ছক — ম্যাট্রিক্স — স্কুলের পদ্ধতিতে গুণ করতে n সারি ও n কলামের ছকের জন্য n³টি গুণ লাগে। স্ট্রাসেন দেখিয়েছিলেন যে দুটি ২ × ২ ম্যাট্রিক্স ৮টির বদলে ৭টি গুণে গুণ করা যায়। কৌশলটি পুনরাবৃত্তভাবে প্রয়োগ করা যায়: একটি বড় ম্যাট্রিক্সকে চারটি ব্লকে কাটুন, প্রতিটি ব্লককে একটি সংখ্যা হিসেবে ধরুন, এবং আবার একই কাজ করুন। তখন খরচ n³-এর বদলে n^2.807-এর মতো বাড়ে। গবেষণাপত্র অনুযায়ী, এই ২ × ২ পদ্ধতিটি ১৯৭১ সালে সর্বোত্তম বলে প্রমাণিত হয়েছিল।

একই ধারণা যেকোনো নির্দিষ্ট আকারের জন্য কাজ করে। কোনো পদ্ধতি যদি দুটি ৩ × ৩ ম্যাট্রিক্স r-টি গুণে গুণ করে, এবং উপাদানগুলো ব্লক হলেও কাজ করে, তবে তার খরচ বাড়ে n-এর log₃ r ঘাতের মতো। সাধারণ পাটিগণিতেই বাজি স্পষ্ট হয়: এমন পদ্ধতি স্ট্রাসেনকে হারায় ঠিক তখনই, যখন r হয় ২১ বা তার কম, আর ২২ বা তার বেশি হলে হেরে যায়। সবচেয়ে ভালো জানা ৩ × ৩ পদ্ধতি, যা লাডারম্যানের, ২৩টি গুণ ব্যবহার করে এবং ১৯৭৬ সাল থেকে এর উন্নতি হয়নি।

যে দরজা আধখোলা ছিল

কোনো সমস্যার জন্য সম্ভাব্য সবচেয়ে ভালো সংখ্যাকে বলা হয় তার র‍্যাঙ্ক। ৩ × ৩ গুণের র‍্যাঙ্কের নিম্নসীমা ধীরে ধীরে ওপরে উঠেছে: ২০০৩ সালে ১৯, তারপর ২০২৬ সালের মার্চে ২০, যা Wang হিসাব করেছিলেন শুধু ০ ও ১ নিয়ে গঠিত একটি ক্ষুদ্র সংখ্যা-পদ্ধতিতে, যেখানে ১ + ১ = ০। ২০২৬ সালের সেপ্টেম্বরে Wang এবং Yang-এর নেতৃত্বাধীন একটি দল দশ দিনের ব্যবধানে স্বাধীনভাবে ২১-এ পৌঁছান। কিন্তু ২১-এও স্ট্রাসেনের চেয়ে দ্রুত কোনো ৩ × ৩ পদ্ধতির জায়গা থেকে গিয়েছিল।

পলিটেকনিক মন্ট্রিয়ল ও কার্নেগি মেলন বিশ্ববিদ্যালয়ের আইজ্যাক রুডিচ (Isaac Rudich) এবং পলিটেকনিক মন্ট্রিয়লের লুই-মার্তাঁ রুসো (Louis-Martin Rousseau) এখন সীমাটিকে ২২-এ ঠেলে দিয়েছেন।

উপপাদ্য ১। যে অ্যালগরিদম পূর্ণসংখ্যা ধ্রুবক দিয়ে দুটি ৩ × ৩ ম্যাট্রিক্স গুণ করে, এবং যেকোনো আকারের ব্লকে পুনরাবৃত্তভাবে প্রয়োগ করা যায়, তা অন্তত ২২টি গুণ ব্যবহার করে।

তাই এমন কোনো অ্যালগরিদম মোটামুটি n^2.814-এর চেয়ে ভালো করতে পারে না — এবং কোনোটিই স্ট্রাসেনের ২ × ২ পদ্ধতিকে হারাতে পারে না।

৪৯৬টি ছোট ধাঁধা

প্রমাণটি Wang-এর তৈরি একটি সারণির ওপর দাঁড়িয়ে, যা কঠিন সমস্যাটিকে ৪৯৬টি সহজতর সমস্যায় ভাগ করে। প্রতিটি সমস্যা প্রথম ম্যাট্রিক্সের ওপর কিছু “শর্ত” যোগ করে — যেমন, তার কিছু উপাদানের যোগফল শূন্য। শর্ত যত বেশি, সমস্যা তত সহজ, শেষে সেই তুচ্ছ ক্ষেত্র যেখানে ম্যাট্রিক্সটি পুরোপুরি শূন্য।

লেখকেরা প্রথমে একটি নির্ভুল অনুসন্ধান-প্রোগ্রাম বানান, যা প্রতিটি ধাঁধার আসল উত্তর তাঁদের জানিয়ে দেয় তা প্রমাণের চেষ্টা করার আগেই। এই উত্তরগুলো মানচিত্রের কাজ করেছে: কোন নিম্নসীমাগুলোর পেছনে ছোটা সার্থক, তা দেখিয়েছে। শেষ পর্যন্ত তাঁদের প্রমাণ ৪৯৬টি ধাঁধারই সীমা নির্ধারণ করে, তার ৩৫৯টির সঠিক মীমাংসা করে — যেখানে Wang-এর সর্বশেষ ফলাফলে সংখ্যাটি ছিল ১৯৫ — এবং ২৫২টির নিম্নসীমা বাড়ায়। তাঁদের নিজস্ব একটি “জোড়া লাগানোর” উপপাদ্য দুটি সহজতর ধাঁধার পদ্ধতি মিলিয়ে তৃতীয় একটি ধাঁধার পদ্ধতি তৈরি করে, এবং এটি ১৪৫টি ঊর্ধ্বসীমা দিয়েছে।

চূড়ান্ত বিবৃতিতে দুটি শর্ত গুরুত্বপূর্ণ। পূর্ণসংখ্যা ধ্রুবক: পূর্ণ সংখ্যার ধ্রুবকওয়ালা কোনো পদ্ধতিকে ০ ও ১-এর সংখ্যা-পদ্ধতিতে পড়লে তা বাড়তি কোনো গুণ ছাড়াই বৈধ পদ্ধতি থাকে, তাই সীমাটি সেখানেও খাটে। ব্লক: এই শর্ত ছাড়া শর্টকাট আছে। গবেষণাপত্রে উদ্ধৃত রোসোভস্কির (Rosowski) ৩ × ৩ অ্যালগরিদমে মাত্র ২১টি গুণ লাগে, কিন্তু এটি সংখ্যার গুণের বিনিময়যোগ্যতার ওপর নির্ভর করে এবং পুনরাবৃত্তভাবে প্রয়োগ করা যায় না।

যন্ত্রে যাচাই করা প্রমাণ

প্রমাণটি লেখা হয়েছে Lean-এ, এমন একটি প্রোগ্রামিং ভাষা যেখানে কোনো উপপাদ্য কেবল তখনই কম্পাইল হয় যখন তার প্রতিটি ধাপ যাচাই করা হয়। পূর্ণ প্রমাণটি প্রায় দশ লক্ষ লাইনের, ৩,৫২১টি মডিউলে ছড়ানো, এবং একটি প্রসেসর কোরে যাচাই করতে ১১.১ ঘণ্টা লাগে। কাউকে পুরোটা পড়তে হবে না। একজন নিরীক্ষক প্রায় ১,০০০ লাইনের একটি লাইব্রেরি পড়েন, যা লেখকেরা কোনো প্রমাণ তৈরি হওয়ার আগেই লিখেছিলেন, এবং যা সংজ্ঞায়িত করে গুণ-পদ্ধতি কী এবং উপপাদ্যটি বিবৃত করে; বাকিটা যাচাই করে Lean-এর কার্নেল, আর একটি স্বাধীন যাচাইকারী ফলাফলটি পুনরায় চালিয়ে দেখতে পারে।

লেখকেরা আরও জানান যে AI এজেন্টরা গবেষণা-সাহিত্য খুঁজেছে: তারা যাচাই করেছে যে প্রতিটি তথ্যসূত্রের অস্তিত্ব আছে, “কিন্তু এটা নয় যে প্রতিটিতে ঠিক সেই ধারণাটিই আছে যার কৃতিত্ব আমরা তাকে দিই।”

শেষ ফাঁক

একটি প্রশ্ন বাকি: ২২টি গুণের কোনো ৩ × ৩ পদ্ধতি কি আছে, নাকি লাডারম্যানের ২৩-ই আসল সর্বনিম্ন? লেখকেরা আশা করেন ফাঁকটি “খুব শিগগিরই বন্ধ হবে”, এবং তা হলে বা গবেষণাপত্রটি প্রকাশের জন্য গৃহীত হলে তাঁরা তাঁদের অনুসন্ধানের কোড প্রকাশ করবেন। সীমাটি অপূর্ণসংখ্যা ধ্রুবকের পদ্ধতিগুলোকেও বাইরে রাখে।