22 गुणाकार, एकही कमी नाही

हितसंबंधांचा संघर्ष. लेखक नमूद करतात की एआय एजंट्सनी — Anthropic चे Claude — त्यांच्या मार्गदर्शनाखाली शोध-कोड आणि ज्यांना मानवी परीक्षकाची गरज नाही अशा Lean सिद्धता लिहिल्या, तर मानवाने परीक्षण करणे आवश्यक असलेला भाग लेखकांनी आखला. हा लेखही Claude ने लिहिला आहे.

संख्यांच्या दोन चौरस जाळ्यांचा — मॅट्रिक्सचा — शाळेत शिकवलेल्या पद्धतीने गुणाकार करायचा तर n ओळी आणि n स्तंभ असलेल्या जाळ्यांसाठी n³ गुणाकार लागतात. स्ट्रासेन (Strassen) यांनी दाखवले की दोन 2 × 2 मॅट्रिक्सचा गुणाकार 8 ऐवजी 7 गुणाकारांत करता येतो. ही युक्ती आवर्ती पद्धतीने वापरता येते: मोठ्या मॅट्रिक्सचे चार खंड करा, प्रत्येक खंडाला एकाच संख्येसारखे वागवा, आणि पुनरावृत्ती करा. मग खर्च n³ ऐवजी n^2.807 प्रमाणे वाढतो. शोधनिबंधानुसार, ही 2 × 2 कृती 1971 मध्ये इष्टतम असल्याचे सिद्ध झाले.

हीच कल्पना कोणत्याही ठरावीक आकारासाठी चालते. दोन 3 × 3 मॅट्रिक्सचा r गुणाकारांत गुणाकार करणारी, आणि घटक खंड असले तरीही चालणारी कृती, n च्या log₃ r घाताप्रमाणे वाढणारा खर्च देते. साधे अंकगणित पणाला काय लागले आहे ते ठरवते: अशी कृती r 21 किंवा त्याहून कमी असेल तेव्हाच नेमकी स्ट्रासेनला मागे टाकते, आणि 22 किंवा त्याहून अधिक असल्यास हरते. ज्ञात सर्वोत्तम 3 × 3 कृती, लाडरमन (Laderman) यांची, 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 गुणाकार लागतात, पण तो संख्या क्रमनिरपेक्ष (commuting) असण्यावर अवलंबून आहे आणि आवर्ती पद्धतीने लागू करता येत नाही.

यंत्राने तपासलेली सिद्धता

सिद्धता Lean मध्ये लिहिली आहे, ही एक प्रोग्रामिंग भाषा आहे जिच्यात प्रत्येक पायरी पडताळली गेली तरच प्रमेय संकलित (compile) होतो. पूर्ण सिद्धता 3,521 मॉड्यूल्समध्ये पसरलेल्या सुमारे दहा लाख ओळींची आहे, आणि एकाच प्रोसेसर कोअरवर ती तपासायला 11.1 तास लागतात. ती सगळी कोणी वाचण्याची गरज नाही. परीक्षक सुमारे 1,000 ओळींचे एक ग्रंथालय वाचतो, जे कोणतीही सिद्धता अस्तित्वात येण्यापूर्वी लेखकांनी लिहिले होते, जे गुणाकाराची कृती म्हणजे काय याची व्याख्या करते आणि प्रमेय मांडते; बाकी Lean चा गाभा (kernel) तपासतो, आणि एक स्वतंत्र तपासक निकाल पुन्हा चालवून पाहू शकतो.

लेखक असेही नमूद करतात की एआय एजंट्सनी संदर्भ-साहित्याचा शोध घेतला: त्यांनी प्रत्येक संदर्भ अस्तित्वात असल्याचे तपासले, “पण आम्ही ज्या कल्पनेचे श्रेय प्रत्येकाला देतो ती नेमकी त्यात आहे की नाही हे नाही.”

शेवटची दरी

एक प्रश्न उरतो: 22 गुणाकारांची 3 × 3 कृती अस्तित्वात आहे का, की लाडरमन यांचे 23 हेच खरे किमान आहे? लेखकांना ही दरी “लवकरच भरून निघेल” अशी अपेक्षा आहे, आणि ती भरल्यावर किंवा शोधनिबंध प्रकाशनासाठी स्वीकारला गेल्यावर ते आपला शोध-कोड प्रसिद्ध करतील. ही मर्यादा अपूर्णांक स्थिरांक असलेल्या कृतींनाही बाजूला ठेवते.