சமன்பாடுகளைத் தீர்ப்பதற்கான 1974-ஆம் ஆண்டின் வேக வரம்பு, இறுதியாக நிரூபிக்கப்பட்டது

ஒரு சார்பு f எங்கே பூஜ்ஜியத்தைக் கடக்கிறது என்று கண்டறிய, ஒரு கணினி பெரும்பாலும் ஒரு மறுசெய்கையை (iteration) இயக்குகிறது: x என்ற ஒரு தோராய மதிப்பிலிருந்து தொடங்கி, சார்பிடம் சில கேள்விகளைக் கேட்டு, மேம்பட்ட ஒரு தோராய மதிப்பைக் கணக்கிட்டு, மீண்டும் அதையே செய்கிறது. அந்தக் கேள்விகள் மதிப்பீடுகள் (evaluations): ஏதோ ஒரு புள்ளியில் f-இன் மதிப்பு, அல்லது அதன் சாய்வின் (வகைக்கெழு, derivative) மதிப்பு, அல்லது ஓர் உயர் வகைக்கெழுவின் மதிப்பு.

இரட்டிப்பாகும் இலக்கங்கள்

அத்தகைய ஒரு முறையின் வேகம் அதன் வரிசையால் (order) அளக்கப்படுகிறது. தற்போதைய பிழை ε என்றால், p வரிசை கொண்ட ஒரு மறுசெய்கை ஏறக்குறைய ε-இன் p அடுக்கு அளவுப் பிழையை விட்டுச் செல்கிறது. வரிசை 2 என்றால், விடைக்கு அருகில், சரியான இலக்கங்களின் எண்ணிக்கை ஒவ்வொரு படியிலும் இரட்டிப்பாகிறது என்று பொருள்; வரிசை 4 என்றால், அது நான்கு மடங்காகிறது.

நியூட்டனின் முறை (Newton’s method) ஒவ்வொரு படிக்கும் இரண்டு மதிப்பீடுகளைச் செலவிடுகிறது — f(x), அதன் சாய்வு f′(x) — பிறகு x − f(x)/f′(x)-க்கு நகர்கிறது. அதன் வரிசை 2. ஒவ்வொரு படியிலும் கூடுதல் கேள்விகள் கேட்பது கூடுதல் வேகத்தை வாங்கித் தரக்கூடும். கேள்வி: எவ்வளவு?

1974-ஆம் ஆண்டின் ஓர் ஊகம்

1974-இல், H. T. Kung, J. F. Traub இருவரும், Journal of the ACM இதழில் வெளியான ஒரு கட்டுரையில் “Conjecture 8.1” என்ற பெயரில் ஒரு விடையை முன்வைத்தனர்: ஒவ்வொரு படிக்கும் n மதிப்பீடுகளைப் பயன்படுத்தும், நினைவற்ற (without memory) ஒரு மறுசெய்கையின் வரிசை அதிகபட்சம் 2ⁿ⁻¹. “நினைவற்ற” என்றால், அந்த முறை தன் தற்போதைய தோராய மதிப்பைத் தவிர முந்தைய படிகளிலிருந்து எதையும் வைத்துக்கொள்வதில்லை என்று பொருள்.

இந்த வரம்பை மேலும் குறைக்க முடியாது: n ≥ 2 என்ற ஒவ்வொரு n-க்கும் 2ⁿ⁻¹-ஐ எட்டும் “பல்புள்ளி” (multipoint) முறைகளை Kung, Traub இருவருமே உருவாக்கியிருந்தனர் — மூன்று மதிப்பீடுகளுடன் வரிசை 4, நான்குடன் 8, ஐந்துடன் 16. விடுபட்டிருந்தது மறுபாதி: எந்த முறையாலும் இதை விடச் சிறப்பாகச் செய்ய முடியாது என்பதற்கான நிரூபணம். ஊகத்துடனும் அதற்குப் பிறகும் பகுதி முடிவுகள் வந்தன. இடைச்செருகல் (interpolation) அடிப்படையிலான முறைகளுக்கும், இரண்டு மதிப்பீடுகள் கொண்ட விகிதமுறு (rational) முறைகளுக்கும், பல்வேறு கூடுதல் நிபந்தனைகளின் கீழும் இந்த வரம்பு நிரூபிக்கப்பட்டது; சார்பின் மதிப்புகளை மட்டுமே பயன்படுத்தும் முறைகளுக்கு, பலவீனமான ஒரு வரம்பு — 2ⁿ — நிறுவப்பட்டது. பொது நிலை திறந்தே இருந்தது.

வழிமுறையை ஏமாற்றுதல்

University of Cambridge-இன் பயன்முறைக் கணிதம் மற்றும் கோட்பாட்டு இயற்பியல் துறையைச் (Department of Applied Mathematics and Theoretical Physics) சேர்ந்த Matthew Colbrook, இப்போது அதை முழுமையாக நிரூபிக்கிறார். மாதிரி வேண்டுமென்றே வழிமுறைக்குத் தாராளமாக இருக்கிறது. எங்கே மதிப்பிட வேண்டும், எந்த வகைக்கெழுக்களை எடுக்க வேண்டும் என்பதை அது செல்லும் போக்கிலேயே தேர்வு செய்யலாம். விடைகளைத் தான் விரும்பும் எந்தத் தீர்மானமான (deterministic) வழியிலும் அது செயலாக்கலாம்; அதன் விதிகளுக்கு எந்த மென்மைத்தன்மையும் (smoothness) தேவையில்லை.

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

அத்தகைய இணைகளைக் கண்டறிய, Colbrook ஒரு குறிப்புச் சார்பை (reference function), அதிகபட்சம் n படி கொண்ட ஒரு சிறிய பல்லுறுப்புக்கோவையால் சற்றே தள்ளுகிறார்; அந்தப் பல்லுறுப்புக்கோவைக்கு n + 1 சரிசெய்யக்கூடிய கெழுக்கள் உள்ளன. ஒவ்வொரு மதிப்பீடும் அவற்றின் அதிகபட்சம் ஒரு சேர்க்கையை (combination) மட்டுமே நிர்ணயிக்கிறது; எனவே n கேள்விகளுக்குப் பிறகு, சில தள்ளல்கள் வழிமுறையின் கண்ணுக்குத் தெரியாமலேயே இருக்கின்றன. அந்த எண்ணிக்கை மட்டும் போதாது: கண்ணுக்குத் தெரியாத ஒரு தள்ளல் பூஜ்ஜியத்தை மிகச் சொற்பமாகவே நகர்த்தக்கூடும்.

முக்கியக் கருவி ரான்ஸ்கியன் (Wronskian) — பல்லுறுப்புக்கோவைகளின் ஒரு குடும்பத்திலிருந்தும் அவற்றின் வகைக்கெழுக்களிலிருந்தும் கட்டப்படும் ஓர் அணிக்கோவை (determinant). ஒரு புதிய துணைத்தேற்றம் (lemma) சொல்கிறது: குடும்பத்தின் ஒரு பல்லுறுப்புக்கோவைக்கு, ஒரு சிறிய வட்டத்துக்குள் (disc) நெருக்கமாக அடைக்கப்பட்ட பல பூஜ்ஜியங்கள் இருந்தால், குடும்பத்தின் ரான்ஸ்கியன் அருகிலேயே பூஜ்ஜியமாக வேண்டும். ஒரு ரான்ஸ்கியனுக்கு வரையறுக்கப்பட்ட எண்ணிக்கையிலான பூஜ்ஜியங்களே உள்ளன. அவற்றிலிருந்து விலகியே இருக்கும் பூஜ்ஜியம் கொண்ட ஒரு சார்பைக் கொண்டு எப்போதும் வழிமுறைக்கு விடையளிப்பதன் மூலம், நிரூபணம் பூஜ்ஜியத்தை நகரும் சுதந்திரத்துடன் வைத்திருக்கிறது.

கணக்கு வைப்பே அடுக்கைத் தருகிறது. பூஜ்ஜியத்திலிருந்து ε தொலைவில் தொடங்கினால், சாத்தியமான பூஜ்ஜியங்கள், ஒரு மாறிலியை ε-இன் ஓர் அடுக்கால் பெருக்கிய அளவுக்குக் குறையாத ஒரு வரம்பில் பரவியே இருக்கின்றன. ஆசிரியரின் சொற்களில், “முதல் அவதானிப்புக்குப் பிறகு அடுக்கு ஒன்றாகவே இருக்கிறது, பிறகு இரட்டிப்பாகிறது; n அவதானிப்புகளுக்குப் பிறகு 2ⁿ⁻¹ கிடைக்கிறது.” இந்தப் பூஜ்ஜியங்களை வழிமுறையால் வேறுபடுத்த முடியாததால், அதன் பிழை எப்போதும் ஒரு மாறிலியை ε-இன் 2ⁿ⁻¹ அடுக்கால் பெருக்கியதற்குக் கீழே விழ முடியாது: 2ⁿ⁻¹-க்கு மேல் எந்த வரிசையும் இல்லை.

எல்லா அளவுகோல்களுக்கும் ஒரே சார்பு

ஒரு சிரமம் மீதமிருந்தது. வரிசையின் வரையறை, பிழை ஏதோ ஒரு மாறிலியை ε-இன் p அடுக்கால் பெருக்கியதற்குக் கீழே இருக்க வேண்டும் என்று மட்டுமே கேட்கிறது; அந்த மாறிலி சார்பைப் பொறுத்து மாறலாம்; எனவே ஒவ்வோர் அளவுகோலிலும் (scale) வேறு வேறு மோசமான சார்பு இருப்பது எதையும் நிரூபிக்காது. ஆகவே Colbrook ஒரு ஒற்றைச் சார்பை உருவாக்குகிறார்: திருத்தங்களை ஒன்றன்பின் ஒன்றாகச் சேர்க்கிறார்; ஒவ்வொரு திருத்தமும், வழிமுறை ஏற்கெனவே கேள்வி கேட்ட ஒவ்வொரு புள்ளியிலும் பூஜ்ஜியமாகிறது; இதனால் கடந்த எல்லா விடைகளும் முற்றிலும் மாறாமல் இருக்கின்றன.

இதன் எல்லை ஒரு முழுச் சார்பு (entire function) — எல்லா இடங்களிலும் மென்மையானது, சிக்கலெண்களின் மீதும் கூட — அதன் சாய்வு மெய்க்கோட்டில் 3/4-க்கும் 5/4-க்கும் இடையே இருக்கிறது: நன்னடத்தை கொண்ட ஒரே ஒரு பூஜ்ஜியத்துடன், சீராக ஏறும் ஒரு வளைகோடு. 2ⁿ⁻¹-க்கு மேலான எந்த p-க்கும், அந்தச் சார்பின் மீது அந்த முறை p வரிசையை எட்டத் தவறுகிறது. ஆகவே, n ≥ 2-க்கு, நினைவற்ற முறைகளின் உகந்த வரிசை சரியாக 2ⁿ⁻¹. மதிப்பீடுகள் சிக்கலெண்களாக இருக்கும்போதும் இதே வரம்பைக் கட்டுரை நிரூபிக்கிறது.

எல்லாவற்றையும் ஒரே நேரத்தில் கேட்பதன் விலை

மேலும் கூர்மையான ஒரு கூற்று, குழுக்களாகச் செய்யப்படும் மதிப்பீடுகளை உள்ளடக்குகிறது: ஒரு குழுவின் ஒவ்வொரு கேள்வியும், அதன் எந்த விடையும் வருவதற்கு முன்பே தேர்வு செய்யப்படுகிறது — இணையான (parallel) முறைகளின் நிலை இதுதான். ℓ₁, …, ℓₖ அளவுகள் கொண்ட குழுக்களுடன், வரிசை அதிகபட்சம் ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1). n கேள்விகளையும் ஒரே நேரத்தில் கேட்டால், வரிசை n-இல் கட்டுப்படுகிறது; அவற்றை ஒவ்வொன்றாகக் கேட்டால், 2ⁿ⁻¹ வரை அனுமதிக்கப்படுகிறது. ஐந்து மதிப்பீடுகளுடன், இது 5, அதற்கு எதிராக 16.

இயந்திரத்தால் சரிபார்க்கப்பட்டது

முடிவுகள் Lean-இல் முறைப்படி சரிபார்க்கப்பட்டுள்ளன — ஒவ்வொரு தர்க்கப் படியையும் சரிபார்க்கும் ஒரு நிரூபண உதவியாளர் அது. குறியீடு பொதுவில் உள்ளது; முறைசார் நிரூபணங்களின் ஒரு பொதுப் பதிவேட்டில் (Palomar) அது பதிவு செய்யப்பட்டுள்ளது. Lean முறைப்படுத்தல் ChatGPT 6-இன் உதவியுடன் மேற்கொள்ளப்பட்டது என்றும், பிறகு Lean 4 Comparator மூலம் கட்டுரையின் தேற்றங்களுக்கு எதிராகச் சரிபார்க்கப்பட்டது என்றும், ஒவ்வொரு வாதமும் ஆசிரியரால் மறுஆய்வு செய்யப்பட்டது என்றும் ஆசிரியர் கூறுகிறார்; உள்ளடக்கத்துக்கான முழுப் பொறுப்பையும் ஆசிரியரே ஏற்கிறார்.

இந்த வரம்பு, மறக்கும் முறைகளைப் பற்றியது. தம் முந்தைய படிகளை மீண்டும் பயன்படுத்த அனுமதிக்கப்பட்ட முறைகள் வேறு வரம்புகளுக்குக் கட்டுப்படுகின்றன; இந்தக் கட்டுரை அவற்றை ஒதுக்கி வைக்கிறது. மேலும், இந்த வரம்பு ஒரு மோசமான நிலைக்கானது (worst case): குறிப்பிட்ட சில சார்புகளின் மீது, ஒரு முறை இன்னும் வேகமாகச் செல்ல முடியும்.