ஒவ்வொரு புள்ளியையும் மற்ற ஒவ்வொன்றுடனும் இணையுங்கள்: மிகக் குறைந்த குறுக்கீடுகள், நிரூபிக்கப்பட்டன

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

கணிதவியலாளர்கள் இத்தகைய படத்தை முழு வரைபடம் (complete graph) Kₙ-இன் ஒரு வரைதல் என்று அழைக்கின்றனர் — n புள்ளிகள், ஒவ்வோர் இணையும் இணைக்கப்பட்டது — மேலும் எந்த வரைதலும் எட்டக்கூடிய மிகக் குறைந்த குறுக்கீடுகளை அதன் குறுக்கீட்டு எண் (crossing number) என்கின்றனர். செக் குடியரசின் சார்லஸ் பல்கலைக்கழகத்தைச் (Charles University) சேர்ந்த Martin Balko, இந்தக் கேள்வியை “இடவியல் வரைபடக் கோட்பாட்டின் (topological graph theory) மிகப் புகழ்பெற்ற சிக்கல்களில் ஒன்று” என்கிறார்.

ஓர் ஓவியரின் எண்ணிக்கை

1950களின் இறுதியில், பிரிட்டிஷ் ஓவியர் Anthony Hill, சரியாக

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

குறுக்கீடுகள் கொண்ட Kₙ வரைதல்களை உருவாக்கினார்; இங்கே ⌊ ⌋ என்பது கீழ்நோக்கி முழுமையாக்குதலைக் குறிக்கிறது. எந்த வரைதலும் இதைவிடச் சிறப்பாகச் செய்ய முடியாது என்ற ஊகத்தை முதலில் வெளியிட்டவர் Guy; பின்னர் Harary-யும் Hill-உம் அதை விவாதித்தனர்; Erdős-உம் Guy-யும் அதைப் பிரபலப்படுத்தினர். அது Harary–Hill கருதுகோள் (conjecture) அல்லது Guy-இன் கருதுகோள் என்று அழைக்கப்படுகிறது.

சூத்திரம் வேகமாக ஏறுகிறது:

4 அல்லது அதற்குக் குறைவான புள்ளிகள்: 0 குறுக்கீடுகள்
5 புள்ளிகள்: 1
7 புள்ளிகள்: 9
10 புள்ளிகள்: 60
14 புள்ளிகள்: 315

ஆறு பத்தாண்டுகளின் பகுதி விடைகள்

சரியாக Z(n) குறுக்கீடுகள் கொண்ட வரைதல்கள், எத்தனை புள்ளிகளுக்கும் இருந்தன; கடினமான பகுதி, எந்த வரைதலும் இதைவிடச் சிறப்பாகச் செய்யாது என்று காட்டுவதுதான்.

அறுபது ஆண்டுகளுக்கும் மேலாக, அது சிறப்பு வகை வரைதல்களுக்கு மட்டுமே நிரூபிக்கப்பட்டது — எடுத்துக்காட்டாக, எல்லாப் புள்ளிகளும் ஒரே கோட்டின் மீது இருந்து, ஒவ்வொரு வளைகோடும் அதன் ஒரே பக்கத்தில் வைக்கப்படும் வரைதல்கள், அல்லது புள்ளிகள் ஒரு கோளத்தின் மீது இருந்து, ஒவ்வொரு வளைகோடும் மிகக் குறுகிய வழியை எடுக்கும் வரைதல்கள். Balko தாமே, Fulek, Kynčl ஆகியோருடன் சேர்ந்து, அத்தகைய ஒரு வகைக்குத் தீர்வு கண்டிருந்தார். 2021-க்குள், கணினிகள் இந்தச் சூத்திரத்தை 14 புள்ளிகள் வரை உறுதிப்படுத்தியிருந்தன. மிகப் பெரிய எண்ணிக்கையிலான புள்ளிகளுக்கு, மிகச் சிறந்த பொது முடிவுகள் Z(n)-இன் குறைந்தது 98.5%-ஐயும், பின்னர் 98.99%-ஐயும் உறுதி செய்தன.

ஒரு நிரூபணம், பின்னர் இன்னும் தெளிவான ஒன்று

2026-இல், எத்தனை புள்ளிகளுக்கும் பொருந்தும் ஒரு நிரூபணத்தை OpenAI அறிவித்தது; Balko-வின் கட்டுரை அதை ஓர் “OpenAI Math Release preprint” என்று பட்டியலிட்டு, தேற்றத்தின் பெருமையை அதற்கே அளிக்கிறது. அந்த நிரூபணம் எப்படிக் கண்டறியப்பட்டது என்பதைக் கட்டுரை கூறவில்லை. Balko-வின் சொற்களில், மூல நிரூபணம் “ஒப்பீட்டளவில் சுருக்கமானது”, ஆனால் “பின்தொடர்வதற்கு மிகவும் கடினமானது”. அவரது முன்அச்சு (preprint), “நேரியல் இயற்கணிதம், வரைபடக் கோட்பாடு ஆகியவற்றின் அடிப்படை அறிவு மட்டுமே தேவைப்படும்” என்று அவர் எழுதும், நெறிப்படுத்தப்பட்ட ஒரு மாற்று வடிவத்தை முன்வைக்கிறது. மற்றொரு கணிதவியலாளரான Gelasio Salazar, தனியான, விரிவான ஒரு விளக்கவுரையைத் தயாரித்து வருகிறார்.

குறுக்கீடுகளுக்குப் பதிலாகக் குணகங்களை எண்ணுதல்

அறியப்பட்ட வரைதல்கள் ஏற்கெனவே Z(n)-ஐ எட்டுவதால், கீழ் வரம்புக்கு மட்டுமே நிரூபணம் தேவை. அதற்கு நான்கு படிகள் ஆகின்றன.

ஒற்றை எண்களே போதும். ஒரு மிகச் சிறந்த வரைதலை, ஒரு புள்ளியைப் பகிர்ந்துகொள்ளும் வளைகோடுகள் ஒருபோதும் குறுக்கிடாதவாறு மீண்டும் வரையலாம்; அப்போது ஒவ்வொரு குறுக்கீடும் 4 வெவ்வேறு புள்ளிகளை உள்ளடக்குகிறது. 6 புள்ளிகளில் ஒவ்வொன்றையும் ஒவ்வொன்றாக நீக்குங்கள்: எஞ்சும் ஒவ்வொரு 5-புள்ளிப் படத்திலும் குறைந்தது 1 குறுக்கீடு உள்ளது; ஒவ்வொரு குறுக்கீடும் 6 நீக்கங்களில் சரியாக 2-இல் தப்பிப் பிழைக்கிறது (அதன் சொந்த 4 புள்ளிகளில் ஒன்று நீக்கப்படும்போதெல்லாம் அது மறைகிறது; மற்ற 2-இல் தப்பிப் பிழைக்கிறது). எனவே குறுக்கீடுகளின் இருமடங்கு குறைந்தது 6: அதாவது குறைந்தது 3, இதுவே Z(6). அதே எண்ணிக்கை முறை ஒவ்வோர் இரட்டை எண்ணுக்கும் பொருந்துகிறது.
பல்லுறுப்புக்கோவைகளின் ஒரு குடும்பம். ஒவ்வொரு புள்ளிக்கும் அதற்கே உரிய ஓர் எண்ணைக் கொடுங்கள். ஒரு குறுக்கீடு இரண்டு வளைகோடுகளை, அதாவது நான்கு புள்ளிகளை, அதாவது நான்கு எண்களை உள்ளடக்குகிறது. Balko நான்கு மாறிகளில் அமைந்த பல்லுறுப்புக்கோவைகளைப் (polynomials) பயன்படுத்துகிறார்; n ஒற்றையாக இருக்கும்போது அந்தக் குடும்பத்துக்குச் சரியாக Z(n) சார்பற்ற குணகங்கள் இருக்கும்படி அவை தேர்ந்தெடுக்கப்படுகின்றன — 7 புள்ளிகளுக்கு, 3 × 3 = 9.
மிகக் குறைவான குறுக்கீடுகள் இடம் விட்டுச் செல்கின்றன. ஒரு குறுக்கீட்டில் ஒரு பல்லுறுப்புக்கோவை பூஜ்ஜியமாக வேண்டும் என்று கேட்பது ஒரு சமன்பாடு. கட்டற்ற குணகங்களை விடக் குறைவான சமன்பாடுகள் இருந்தால், நேரியல் இயற்கணிதம் எப்போதும் பூஜ்ஜியமல்லாத ஒரு தீர்வை விட்டுச் செல்கிறது. எனவே Z(n)-ஐ விடக் குறைவான குறுக்கீடுகள் கொண்ட ஒரு வரைதலுடன், அதன் எல்லாக் குறுக்கீடுகளிலும் பூஜ்ஜியமாகும் பூஜ்ஜியமல்லாத ஒரு பல்லுறுப்புக்கோவையும் வரும்; அவற்றில் மிகக் குறைந்த படி (degree) கொண்டதை எடுத்துக்கொள்ளுங்கள்.
தளம் எதிர்த்துத் தள்ளுகிறது. வடிவியல் ஒரே ஒரு பாரம்பரிய உண்மையின் வழியே நுழைகிறது: தளத்தில் உள்ள ஒரு மூடிய வளையம், மற்றொன்றை வலமிருந்து இடமாகக் கடக்கும் அதே எண்ணிக்கையில்தான் இடமிருந்து வலமாகவும் கடக்கிறது. நன்கு தேர்ந்தெடுக்கப்பட்ட எடைகளுடன், இது பல்லுறுப்புக்கோவையின் மதிப்புகளின் வர்க்கங்களின் ஒரு கூட்டுத்தொகையைத் தருகிறது; அவற்றில் சில நேர்மறையாகவும் சில எதிர்மறையாகவும் எண்ணப்படுகின்றன, மொத்தம் பூஜ்ஜியம். நேர்மறை உறுப்புகள் அனைத்தும் குறுக்கீடுகளில் அமைகின்றன, அங்கே பல்லுறுப்புக்கோவை பூஜ்ஜியம்; எனவே எதிர்மறை உறுப்புகளும் மறைய வேண்டும். வளைய உண்மையின் இரண்டாவது பயன்பாடு, அதை ஒரு நிலையான காரணியால் வகுபடச் செய்கிறது; வகுத்தால், அதே பண்பு கொண்ட, குறைந்த படியுடைய, பூஜ்ஜியமல்லாத ஒரு பல்லுறுப்புக்கோவை கிடைக்கிறது; இது சாத்தியமற்றது, ஏனெனில் நாம் மிகக் குறைந்த படி கொண்டதையே எடுத்தோம்.

அந்தக் குறிகள் சார்ந்த வாதமே Balko-வின் முக்கிய மாற்றம்: அது “ஒரு சிதைவற்ற இருநேரியல் வடிவம் (nondegenerate bilinear form), செங்குத்து நிரப்பிகள் (orthogonal complements) ஆகியவற்றை உள்ளடக்கிய” மூல வாதத்தை மாற்றீடு செய்கிறது. அவர் வளைய உண்மையை வேறு விதமாகவும் நிரூபிக்கிறார்; ஒவ்வொரு புள்ளியையும் இன்னும் நேரடியாகத் தனிமைப்படுத்துகிறார்.

ஒரே அடியில் தீர்வு கண்ட பிற வலையமைப்புகள்

குறுக்கீடுகளுக்குப் பதிலாக, குறைந்தது ஒருமுறையாவது குறுக்கிடும் வளைகோட்டு இணைகளையோ, ஒற்றை எண்ணிக்கையில் குறுக்கிடும் இணைகளையோ எண்ணினாலும், விடை Z(n)-ஆகவே இருக்கிறது — ஒரு புள்ளியைப் பகிர்ந்துகொள்ளும் வளைகோடுகள் வேறெங்கும் சந்திக்காத வரை. முந்தைய குறைப்புகளுடன் (reductions) இணைந்து, இந்தத் தேற்றம், சில இணைப்புகள் நீக்கப்பட்ட முழு வரைபடங்களுக்கும், ஒரு பாதையின் வழியே அல்லது ஓர் இரட்டைச் சுழற்சியைச் (even cycle) சுற்றிச் சங்கிலியாக இணைக்கப்பட்ட முழு வரைபட நகல்களுக்கும், விரிவாக்கப்பட்ட சியர்பின்ஸ்கி வரைபடங்கள் (extended Sierpiński graphs) எனப்படும் பின்னவடிவம் (fractal) போன்ற வலையமைப்புகளின் ஒரு குடும்பத்துக்கும் துல்லியமான குறுக்கீட்டு எண்களைத் தருகிறது.

6 புள்ளிகள் கொண்ட முழு வரைபடத்திலிருந்து ஒரே ஒரு வளைகோட்டை நீக்கினால், அதன் குறைந்தபட்சம் 3 குறுக்கீடுகளிலிருந்து 2-ஆகக் குறைகிறது; 8 புள்ளிகளில், 18-இலிருந்து 15-ஆக.