22 ضربیں، ایک بھی کم نہیں

مفادات کا ٹکراؤ۔ مصنفین بتاتے ہیں کہ مصنوعی ذہانت کے ایجنٹوں — Anthropic کے Claude — نے ان کی ہدایت پر تلاش کا کوڈ اور وہ Lean ثبوت لکھے جنہیں کسی انسانی جانچ کار کی ضرورت نہیں، جبکہ وہ حصہ جسے انسان کو جانچنا ہوتا ہے، مصنفین نے خود وضع کیا۔ یہ مضمون بھی Claude نے لکھا ہے۔

اعداد کے دو مربع جالوں — میٹرکس — کو اسکول کی کتاب والے طریقے سے ضرب دینے میں n قطاروں اور n کالموں والے جالوں کے لیے n³ ضربیں لگتی ہیں۔ اسٹراسن نے دکھایا کہ دو 2 × 2 میٹرکس کو 8 کے بجائے 7 ضربوں سے ضرب دیا جا سکتا ہے۔ اس ترکیب کو بار بار (recursively) لاگو کیا جا سکتا ہے: ایک بڑے میٹرکس کو چار بلاکس میں کاٹیں، ہر بلاک کو ایک واحد عدد سمجھیں، اور دہرائیں۔ تب لاگت n³ کے بجائے n^2.807 کی طرح بڑھتی ہے۔ مقالے کے مطابق یہ 2 × 2 ترکیب 1971 میں بہترین ثابت کی گئی تھی۔

یہی خیال کسی بھی مقررہ جسامت کے لیے کام کرتا ہے۔ ایک ترکیب جو دو 3 × 3 میٹرکس کو r ضربوں سے ضرب دے، اور اس وقت بھی کام کرے جب اندراجات بلاکس ہوں، ایسی لاگت دیتی ہے جو n کی طاقت log₃ r کی طرح بڑھتی ہے۔ سادہ حساب بتاتا ہے کہ داؤ پر کیا ہے: ایسی ترکیب اسٹراسن کو ٹھیک اسی وقت مات دیتی ہے جب r اکیس یا اس سے کم ہو، اور 22 یا زیادہ پر ہار جاتی ہے۔ سب سے بہتر معلوم 3 × 3 ترکیب، جو لاڈرمین کی ہے، 23 ضربیں استعمال کرتی ہے اور 1976 سے اس میں بہتری نہیں ہوئی۔

ایک دروازہ جو ادھ کھلا رہا

کسی دیے گئے مسئلے کے لیے بہترین ممکنہ تعداد کو اس کا رینک (rank) کہا جاتا ہے۔ 3 × 3 ضرب کے رینک کی نچلی حدیں آہستہ آہستہ اوپر سرکیں: 2003 میں 19، پھر مارچ 2026 میں 20، جو وانگ نے صرف 0 اور 1 والے ایک ننھے سے عددی نظام پر نکالی، جہاں 1 + 1 = 0 ہوتا ہے۔ ستمبر 2026 میں وانگ اور یانگ کی قیادت میں ایک ٹیم نے آزادانہ طور پر، ایک دوسرے سے دس دن کے فرق سے، 21 تک رسائی حاصل کی۔ لیکن 21 اب بھی اسٹراسن سے تیز 3 × 3 ترکیب کی گنجائش چھوڑتا تھا۔

پولی ٹیکنیک مونٹریال اور کارنیگی میلن یونیورسٹی کے آئزک روڈچ اور پولی ٹیکنیک مونٹریال کے لوئی-مارتاں روسو نے اب یہ حد 22 تک پہنچا دی ہے۔

مسئلہ 1۔ ہر وہ الگورتھم جو صحیح عددی مستقلات کے ساتھ دو 3 × 3 میٹرکس کو ضرب دیتا ہے، اور کسی بھی جسامت کے بلاکس پر بار بار لاگو کیا جا سکتا ہے، کم از کم 22 ضربیں استعمال کرتا ہے۔

لہٰذا ایسا کوئی الگورتھم تقریباً n^2.814 سے بہتر نہیں ہو سکتا — اور کوئی بھی اسٹراسن کے 2 × 2 طریقے کو مات نہیں دے سکتا۔

496 چھوٹی پہیلیاں

ثبوت وانگ کی وضع کردہ ایک جدول پر مبنی ہے، جو مشکل مسئلے کو 496 آسان مسائل میں تقسیم کرتی ہے۔ ہر ایک پہلے میٹرکس پر “شرائط” کا اضافہ کرتا ہے — مثلاً یہ کہ اس کے کچھ اندراجات کا مجموعہ صفر ہو۔ جتنی زیادہ شرائط، مسئلہ اتنا ہی آسان، یہاں تک کہ وہ معمولی صورت آ جائے جس میں میٹرکس سارا صفر ہو۔

مصنفین نے پہلے تلاش کا ایک قطعی پروگرام بنایا جو انہیں ہر پہیلی کا اصل جواب اسے ثابت کرنے کی کوشش سے پہلے بتا دیتا تھا۔ ان جوابات نے نقشے کا کام دیا: انہوں نے دکھایا کہ کن نچلی حدوں کے پیچھے جانا فائدہ مند ہے۔ آخرکار ان کا ثبوت تمام 496 پہیلیوں کی حد مقرر کرتا ہے، ان میں سے 359 کو قطعی طور پر حل کرتا ہے — جبکہ وانگ کے تازہ ترین نتائج میں یہ تعداد 195 تھی — اور 252 کی نچلی حد بڑھا دیتا ہے۔ ان کا اپنا ایک “جوڑنے” والا مسئلہ دو آسان پہیلیوں کی ترکیبوں کو ملا کر تیسری کی ترکیب بناتا ہے، اور اس نے 145 بالائی حدیں فراہم کیں۔

حتمی بیان میں دو شرائط اہم ہیں۔ صحیح عددی مستقلات: صحیح عددی مستقلات والی ترکیب، جب 0 اور 1 والے عددی نظام میں پڑھی جائے، تو بغیر کسی اضافی ضرب کے ایک درست ترکیب رہتی ہے، اس لیے حد منتقل ہو جاتی ہے۔ بلاکس: اس شرط کے بغیر شارٹ کٹ موجود ہیں۔ روسووسکی کا 3 × 3 الگورتھم، جس کا مقالے میں حوالہ ہے، صرف 21 ضربیں مانگتا ہے، لیکن یہ اعداد کے قابلِ تبادلہ (commutative) ہونے پر منحصر ہے اور بار بار لاگو نہیں کیا جا سکتا۔

مشین سے جانچا گیا ثبوت

ثبوت Lean میں لکھا گیا ہے، ایک پروگرامنگ زبان جس میں کوئی مسئلہ تبھی کمپائل ہوتا ہے جب ہر قدم کی تصدیق ہو جائے۔ مکمل ثبوت 3,521 ماڈیولز میں پھیلی تقریباً دس لاکھ سطروں پر مشتمل ہے، اور ایک پروسیسر کور پر اس کی جانچ میں 11.1 گھنٹے لگتے ہیں۔ کسی کو یہ سب پڑھنے کی ضرورت نہیں۔ ایک جانچ کار تقریباً 1,000 سطروں کی ایک لائبریری پڑھتا ہے، جو مصنفین نے کسی بھی ثبوت کے وجود سے پہلے لکھی، جو بتاتی ہے کہ ضرب کی ترکیب کیا ہوتی ہے اور مسئلے کو بیان کرتی ہے؛ باقی کی جانچ Lean کا کرنل کرتا ہے، اور ایک آزاد جانچ کار نتیجے کو دوبارہ چلا سکتا ہے۔

مصنفین یہ بھی بتاتے ہیں کہ مصنوعی ذہانت کے ایجنٹوں نے علمی مواد کی تلاش کی: انہوں نے جانچا کہ ہر حوالہ موجود ہے، “لیکن یہ نہیں کہ ہر ایک میں بالکل وہی خیال ہے جو ہم اس سے منسوب کرتے ہیں”۔

آخری خلا

ایک سوال باقی ہے: کیا 22 ضربوں والی کوئی 3 × 3 ترکیب موجود ہے، یا لاڈرمین کی 23 ہی اصل کم ترین تعداد ہے؟ مصنفین توقع کرتے ہیں کہ یہ خلا “بہت جلد پُر ہو جائے گا”، اور جب ایسا ہوگا، یا جب مقالہ اشاعت کے لیے قبول ہو جائے گا، وہ اپنا تلاش کا کوڈ جاری کریں گے۔ یہ حد غیر صحیح عددی مستقلات والی ترکیبوں کو بھی شامل نہیں کرتی۔