संख्यांच्या जाळ्यांच्या गुणाकारात नवा विक्रम

दोन मॅट्रिक्सांचा — संख्यांच्या जाळ्यांचा — गुणाकार ही संगणनातील सर्वांत मूलभूत क्रियांपैकी एक आहे. पाठ्यपुस्तकी पद्धतीने केल्यास, दोन n-बाय-n जाळ्यांच्या गुणाकाराचा खर्च n³ प्रमाणे वाढतो. फोल्कर श्ट्रासेन (Volker Strassen) यांचा 1969 चा अल्गोरिदम याहून चांगली कामगिरी करणारा पहिला होता — शोधनिबंधाच्या शब्दांत “उप-घनीय” (subcubic) — आणि तेव्हापासून गणितज्ञ प्रगती एकाच संख्येने मोजतात: घातांक ω (ओमेगा), म्हणजे जाळी मोठी होत जातात तेव्हा पुरेसा ठरणारा n चा सर्वांत लहान घात.

श्ट्रासेन यांनी तो 2.81 च्या खाली आणला. शोधनिबंधात सूचीबद्ध केलेल्या अनेक दशकांच्या कामाने, अधिकाधिक लहान पावलांनी, तो सुमारे 2.37 पर्यंत खाली आणला आहे. 2026 मध्ये एमिलियन ड्युपॉन (Emilien Dupont) आणि सहकारी 2.371177 पर्यंत पोहोचले. आता Matroid, Inc. या कंपनीचे रेझा झादेह (Reza Zadeh) ω < 2.37115924 सिद्ध करतात.

1969 मधील श्ट्रासेनपासून या शोधनिबंधापर्यंत, ω च्या वरच्या मर्यादेतील निवडक सुधारणा. — तालिका 1, Zadeh (2026), arXiv:2610.10593, CC BY 4.0.

2,12,820 सेटिंग्ज असलेली कृती

हे विक्रम लहान जाळ्यांसाठीच्या एखाद्या अधिक हुशार युक्तीतून येत नाहीत. ते येतात कॉपरस्मिथ–विनोग्राड टेन्सर नावाच्या एका बैजिक वस्तूतून, जिचे तुकडे करून ते पुन्हा जोडता येतात — पुनरावर्ती पद्धतीने — आणि अनेक स्वतंत्र मॅट्रिक्स-गुणाकारांत रूपांतरित करता येतात. ते कसे कापायचे हे निवडींच्या एका प्रचंड संचावरून ठरते: संभाव्यता-वितरणे, एन्ट्रॉपी-दंड, आणि पातळी-दर-पातळी ठरवलेले मॅट्रिक्स-आकार. निवडींचा कोणताही वैध संच वैध मर्यादा देतो; कौशल्य आहे ते चांगला संच शोधण्यात.

जॉश आल्मन (Josh Alman) आणि सहकाऱ्यांच्या चौकटीवर आणि ड्युपॉन व सहकाऱ्यांच्या मांडणीवर आधारित, झादेह यांनी तीन सुधारणांसह 2,12,820 संख्या एकाच वेळी जुळवल्या:

• महत्त्वानुसार पुनर्मापन. रचनेतील काही घटक क्वचितच दिसतात, त्यामुळे निकालावर त्यांचा परिणाम अत्यल्प असतो आणि इष्टतमीकरण करणारी पद्धत त्यांना फारशी हलवत नाही. प्रत्येक संख्या, तिचा घटक किती भार वाहतो त्यानुसार पुनर्मापित केली गेली.
• अडथळ्यांसाठी सहा कळा. अंतिम घातांक तीन टप्प्यांवरील तीन स्पर्धक राशींपैकी सर्वांत दुर्बल राशीवरून ठरतो. एका स्वतंत्र दुरुस्तीने फक्त सहा नियंत्रकांचा वापर करून त्यांचा समतोल राखला.
• अचूक निर्यात. अंतिम कृती 2⁹⁶ छेद असलेल्या अचूक अपूर्णांकांत रूपांतरित केली गेली.

तपासणीद्वारे सिद्धता

ही मर्यादा संगणक-सहाय्यित सिद्धता आहे. फक्त Python ची मानक लायब्ररी वापरणारा एक छोटा प्रोग्राम — नेटवर्क नाही, मॉडेल नाही, अतिरिक्त पॅकेज नाही — अचूक अपूर्णांकांपासून प्रत्येक वितरण पुन्हा रचतो आणि हमीयुक्त पूर्णांकनाने निकालाचे मूल्यमापन करतो. मुख्य राशी धन आहे, सुमारे 8.5 अब्जांश इतकी, असे त्याला आढळते, आणि यातून मर्यादा सिद्ध होते. हे काय समाविष्ट करत नाही यावर लेखक भर देतात: हा प्रोग्राम लेखापरीक्षण करता येण्याजोगा कोड आहे, सिद्धता-सहाय्यकातील संपूर्ण सिद्धांताचे औपचारिकीकरण नव्हे, आणि शोध स्थानिक होता — ही कृती शक्य तितकी सर्वोत्तम असल्याचा कोणताही दावा नाही.

लेखक असेही लिहितात की नावे न दिलेल्या जनरेटिव्ह AI साधनांनी संख्यात्मक शोध, सॉफ्टवेअर आणि हस्तलिखित यांत मदत केली, आणि सुरुवातीचा कोड एरिक नासलुंड (Eric Naslund) यांनी सार्वजनिकरीत्या सामायिक केलेल्या संगणकीय टिपणांवर आधारलेला होता. 5 ऑक्टोबर 2026 रोजी प्रसिद्ध झालेले एक स्वतंत्र सार्वजनिक संगणक-प्रमाणपत्र 2.371169353 पर्यंत पोहोचले होते; नवे मूल्य त्याहूनही कमी आहे.

सैद्धांतिकदृष्ट्या, अधिक वेगवान

ड्युपॉन आणि सहकाऱ्यांच्या तुलनेत घातांकातील लाभ 0.00001776 आहे. या पद्धतीने मिळवलेल्या सर्व मर्यादांप्रमाणे, ही हमी अनंतस्पर्शी आहे: नवा अल्गोरिदम कोणत्या मॅट्रिक्स-आकारापासून प्रत्यक्षात विद्यमान अल्गोरिदमना मागे टाकेल, हे एकटा घातांक सांगत नाही. तो बदलतो ते 1969 पासून चालत आलेल्या एका प्रश्नाचे सर्वोत्तम ज्ञात उत्तर — तत्त्वतः, संख्यांच्या जाळ्यांचा गुणाकार किती वेगाने करता येतो?