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

हितों का टकराव। लेखकों का कहना है कि AI एजेंटों — Anthropic के Claude — ने उनके निर्देशन में खोज-कोड और वे Lean प्रमाण लिखे जिनके लिए मानव ऑडिटर की ज़रूरत नहीं है, जबकि वह हिस्सा जिसे किसी इंसान को जाँचना ज़रूरी है, लेखकों ने ख़ुद तैयार किया। यह लेख भी Claude ने लिखा है।

संख्याओं के दो वर्गाकार जालों — मैट्रिक्स — को स्कूल वाले तरीके से गुणा करने में, n पंक्तियों और n स्तंभों वाले जालों के लिए, n³ गुणा लगते हैं। स्ट्रासेन ने दिखाया कि दो 2 × 2 मैट्रिक्स को 8 की जगह 7 गुणा से गुणा किया जा सकता है। इस तरकीब को पुनरावर्ती रूप से लगाया जा सकता है: एक बड़े मैट्रिक्स को चार ब्लॉकों में काटिए, हर ब्लॉक को एक संख्या की तरह मानिए, और यही दोहराते जाइए। तब लागत n³ की जगह n^2.807 की तरह बढ़ती है। शोधपत्र के अनुसार, यह 2 × 2 विधि 1971 में सर्वोत्तम सिद्ध की गई थी।

यही विचार किसी भी निश्चित आकार के लिए काम करता है। अगर कोई विधि दो 3 × 3 मैट्रिक्स को r गुणाओं से गुणा करती है, और तब भी काम करती है जब प्रविष्टियाँ ब्लॉक हों, तो उसकी लागत n की घात log₃ r की तरह बढ़ती है। साधारण अंकगणित दाँव साफ़ कर देता है: ऐसी विधि स्ट्रासेन को ठीक तभी हराती है जब r 21 या उससे कम हो, और 22 या उससे अधिक पर हार जाती है। सबसे अच्छी ज्ञात 3 × 3 विधि, जो लैडरमैन की है, 23 गुणा लेती है और 1976 से उसमें सुधार नहीं हुआ है।

एक दरवाज़ा जो अधखुला रह गया

किसी दी गई समस्या के लिए सबसे अच्छी संभव संख्या को उसकी रैंक कहते हैं। 3 × 3 गुणन की रैंक की निचली सीमाएँ धीरे-धीरे ऊपर चढ़ीं: 2003 में 19, फिर मार्च 2026 में 20, जिसे 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 को सटीक रूप से हल करता है — जबकि Wang के नवीनतम परिणामों में यह संख्या 195 थी — और 252 की निचली सीमा बढ़ाता है। उनका अपना एक “जोड़ने” वाला प्रमेय दो आसान पहेलियों की विधियों को मिलाकर तीसरी पहेली की विधि बना देता है, और इसने 145 ऊपरी सीमाएँ दीं।

अंतिम कथन में दो शर्तें मायने रखती हैं। पूर्णांक स्थिरांक: पूर्ण संख्याओं वाले स्थिरांकों की कोई विधि, जब 0 और 1 वाली संख्या-प्रणाली में पढ़ी जाए, तब भी अधिक गुणाओं के बिना एक मान्य विधि बनी रहती है, इसलिए सीमा वहाँ से यहाँ लागू हो जाती है। ब्लॉक: इस शर्त के बिना शॉर्टकट मौजूद हैं। शोधपत्र में उद्धृत रोसोव्स्की (Rosowski) का 3 × 3 एल्गोरिद्म केवल 21 गुणा लेता है, लेकिन वह इस पर निर्भर है कि संख्याओं का गुणन क्रम-निरपेक्ष हो, और उसे पुनरावर्ती रूप से नहीं लगाया जा सकता।

मशीन से जाँचा गया प्रमाण

प्रमाण Lean में लिखा गया है, एक प्रोग्रामिंग भाषा जिसमें कोई प्रमेय तभी कंपाइल होता है जब उसका हर कदम सत्यापित हो। पूरा प्रमाण लगभग दस लाख पंक्तियों का है, जो 3,521 मॉड्यूलों में फैला है, और एक प्रोसेसर कोर पर इसकी जाँच में 11.1 घंटे लगते हैं। किसी को इसे पूरा पढ़ने की ज़रूरत नहीं। एक ऑडिटर लगभग 1,000 पंक्तियों की एक लाइब्रेरी पढ़ता है, जिसे लेखकों ने किसी भी प्रमाण के अस्तित्व में आने से पहले लिखा था, और जो परिभाषित करती है कि गुणन-विधि क्या है तथा प्रमेय को बताती है; बाकी की जाँच Lean का कर्नेल करता है, और एक स्वतंत्र जाँचकर्ता परिणाम को दोहरा सकता है।

लेखक यह भी बताते हैं कि AI एजेंटों ने साहित्य खोजा: उन्होंने जाँचा कि हर संदर्भ मौजूद है, “लेकिन यह नहीं कि हर संदर्भ में ठीक वही विचार है जिसका श्रेय हम उसे देते हैं।”

आख़िरी अंतर

एक सवाल बाकी है: क्या 22 गुणाओं वाली कोई 3 × 3 विधि मौजूद है, या लैडरमैन के 23 ही असली न्यूनतम हैं? लेखकों को उम्मीद है कि यह अंतर “बहुत जल्द भर जाएगा”, और वे अपना खोज-कोड तब जारी करेंगे जब ऐसा हो जाए, या जब शोधपत्र प्रकाशन के लिए स्वीकार हो जाए। यह सीमा गैर-पूर्णांक स्थिरांकों वाली विधियों को भी अलग छोड़ देती है।