22 பெருக்கல்கள், ஒன்று கூடக் குறையாது

நலன் முரண். தேடல் நிரலையும், மனிதத் தணிக்கையாளர் தேவைப்படாத Lean நிரூபணங்களையும் தங்கள் வழிகாட்டுதலின் கீழ் AI முகவர்கள் — Anthropic உருவாக்கிய Claude — எழுதியதாகவும், மனிதர் தணிக்கை செய்ய வேண்டிய பகுதியைத் தாங்களே வடிவமைத்ததாகவும் ஆசிரியர்கள் குறிப்பிடுகின்றனர். இந்தக் கட்டுரையையும் Claude எழுதியுள்ளது.

இரண்டு சதுர எண் அட்டவணைகளை — அணிகளை — பள்ளியில் கற்பிக்கும் முறையில் பெருக்க, n நிரைகளும் n நிரல்களும் கொண்ட அட்டவணைகளுக்கு n³ பெருக்கல்கள் ஆகின்றன. இரண்டு 2 × 2 அணிகளை 8-க்குப் பதில் 7 பெருக்கல்களில் பெருக்க முடியும் என்று ஸ்ட்ராசன் காட்டினார். இந்த உத்தியைச் சுழல்முறையில் (recursively) பயன்படுத்தலாம்: ஒரு பெரிய அணியை நான்கு தொகுதிகளாக வெட்டி, ஒவ்வொரு தொகுதியையும் ஒரே எண்ணாகக் கருதி, மீண்டும் செய்யுங்கள். அப்போது செலவு n³-க்குப் பதில் n^2.807 போல வளர்கிறது. ஆய்வுக் கட்டுரையின்படி, இந்த 2 × 2 செய்முறை உகந்தது என்பது 1971-இல் நிறுவப்பட்டது.

இதே யோசனை எந்த நிலையான அளவுக்கும் பொருந்தும். இரண்டு 3 × 3 அணிகளை r பெருக்கல்களில் பெருக்கி, உறுப்புகள் தொகுதிகளாக இருக்கும்போதும் இயங்கும் ஒரு செய்முறை, n-இன் log₃ r அடுக்கு போல வளரும் செலவைத் தருகிறது. எளிய கணக்கு பணயத்தில் இருப்பதைக் காட்டுகிறது: அத்தகைய செய்முறை r 21 அல்லது அதற்குக் குறைவாக இருக்கும்போது மட்டுமே ஸ்ட்ராசனை மிஞ்சும்; 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 அணிகளை முழு எண் மாறிலிகளுடன் பெருக்கி, எந்த அளவுத் தொகுதிகளுக்கும் சுழல்முறையில் பயன்படுத்தக்கூடிய எந்த வழிமுறையும் (algorithm) குறைந்தது 22 பெருக்கல்களைப் பயன்படுத்துகிறது.

எனவே அத்தகைய எந்த வழிமுறையும் சுமார் n^2.814-ஐவிடச் சிறப்பாகச் செய்ய முடியாது — எதுவும் ஸ்ட்ராசனின் 2 × 2 முறையை மிஞ்ச முடியாது.

496 சிறிய புதிர்கள்

நிரூபணம், கடினமான சிக்கலை 496 எளிய சிக்கல்களாகப் பிரிக்கும், வாங் உருவாக்கிய ஒரு அட்டவணையின் மீது கட்டப்பட்டுள்ளது. ஒவ்வொன்றும் முதல் அணியின் மீது “நிபந்தனைகளைச்” சேர்க்கிறது — எடுத்துக்காட்டாக, அதன் சில உறுப்புகளின் கூட்டுத்தொகை பூஜ்ஜியம் என்பது போல. நிபந்தனைகள் அதிகமானால் சிக்கல் எளிதாகிறது; இறுதியில் அணி முழுவதும் பூஜ்ஜியமாக இருக்கும் அற்ப நிலை வரை.

ஒவ்வொரு புதிருக்குமான உண்மையான விடையை, அதை நிரூபிக்க முயல்வதற்கு முன்பே தெரிவிக்கும் ஒரு துல்லியமான தேடல் நிரலை ஆசிரியர்கள் முதலில் உருவாக்கினர். அந்த விடைகள் ஒரு வரைபடம் போலச் செயல்பட்டன: எந்தக் கீழ் வரம்புகளைத் துரத்துவது பயனுள்ளது என்பதைக் காட்டின. இறுதியில், அவர்களின் நிரூபணம் 496 புதிர்களுக்கும் வரம்பு விதிக்கிறது, அவற்றில் 359-ஐத் துல்லியமாகத் தீர்க்கிறது — வாங்கின் சமீபத்திய முடிவுகளில் இது 195 — மேலும் 252-க்குக் கீழ் வரம்பை உயர்த்துகிறது. அவர்களுடைய சொந்த “ஒட்டுதல்” (gluing) தேற்றம், இரண்டு எளிய புதிர்களின் செய்முறைகளை இணைத்து மூன்றாவது புதிருக்கான செய்முறையை உருவாக்குகிறது; மேல் வரம்புகளில் 145-ஐ அதுவே வழங்கியது.

இறுதிக் கூற்றில் இரண்டு நிபந்தனைகள் முக்கியம். முழு எண் மாறிலிகள்: முழு எண் மாறிலிகள் கொண்ட செய்முறையை 0-1 எண் அமைப்பில் படித்தாலும், அது கூடுதல் பெருக்கல்கள் இல்லாத செல்லுபடியான செய்முறையாகவே இருக்கிறது; எனவே வரம்பு அங்கும் பொருந்துகிறது. தொகுதிகள்: இந்தத் தேவை இல்லையென்றால் குறுக்குவழிகள் உள்ளன. கட்டுரை மேற்கோள் காட்டும் ரோசோவ்ஸ்கியின் 3 × 3 வழிமுறைக்கு 21 பெருக்கல்களே போதும்; ஆனால் அது எண்களின் பரிமாற்றுத் தன்மையை (commuting) சார்ந்துள்ளது, சுழல்முறையில் பயன்படுத்த முடியாது.

இயந்திரம் சரிபார்த்த நிரூபணம்

நிரூபணம் Lean-இல் எழுதப்பட்டுள்ளது; இது ஒவ்வொரு அடியும் சரிபார்க்கப்பட்டால் மட்டுமே தேற்றம் தொகுக்கப்படும் (compile) ஒரு நிரலாக்க மொழி. முழு நிரூபணம் 3,521 தொகுதிக் கோப்புகளில் (modules) பரவிய சுமார் பத்து லட்சம் வரிகள்; ஒரே செயலிக் கருவில் அதைச் சரிபார்க்க 11.1 மணி நேரம் ஆகிறது. யாரும் அதை முழுமையாகப் படிக்க வேண்டியதில்லை. ஒரு தணிக்கையாளர், எந்த நிரூபணமும் இருப்பதற்கு முன்பே ஆசிரியர்கள் எழுதிய, பெருக்கல் செய்முறை என்றால் என்ன என்பதை வரையறுத்துத் தேற்றத்தைக் கூறும் சுமார் 1,000 வரி நூலகத்தைப் படிக்கிறார்; மீதியை Lean-இன் கருவம் (kernel) சரிபார்க்கிறது; ஒரு சாராத சரிபார்ப்பான் முடிவை மீண்டும் இயக்க முடியும்.

AI முகவர்கள் ஆய்வு இலக்கியத்தைத் தேடியதாகவும் ஆசிரியர்கள் குறிப்பிடுகின்றனர்: ஒவ்வொரு மேற்கோளும் உள்ளதா என்று அவர்கள் சரிபார்த்தனர், “ஆனால் ஒவ்வொன்றும் நாம் அதற்குச் சேர்க்கும் யோசனையைத் துல்லியமாகக் கொண்டுள்ளதா என்று அல்ல.”

கடைசி இடைவெளி

ஒரு கேள்வி எஞ்சியுள்ளது: 22 பெருக்கல்கள் கொண்ட 3 × 3 செய்முறை உள்ளதா, அல்லது லேடர்மேனின் 23-தான் உண்மையான குறைந்தபட்சமா? இந்த இடைவெளி “மிக விரைவில் மூடப்படும்” என்று ஆசிரியர்கள் எதிர்பார்க்கின்றனர்; அது மூடப்பட்டதும், அல்லது கட்டுரை வெளியீட்டுக்கு ஏற்கப்பட்டதும், தங்கள் தேடல் நிரலை வெளியிடுவார்கள். முழு எண் அல்லாத மாறிலிகள் கொண்ட செய்முறைகளையும் இந்த வரம்பு ஒதுக்கிவைக்கிறது.