గణితంప్రీప్రింట్సిద్ధాంతంచదవడానికి 3 నిమిషాలు

అంతరిక్షానికి రంగు వేయడానికి ఎన్ని రంగులు? ఒక సాధారణ కొలబద్దకు 2d కి మించి అవసరం లేదు

ఒక చదునైన సమతలంలోని ప్రతి బిందువునూ తీసుకుని, ప్రతిదానికీ ఒక రంగు ఇవ్వండి. ఒకే నియమం: సరిగ్గా ఒక యూనిట్ దూరంలో ఉన్న రెండు బిందువులకు ఎప్పుడూ ఒకే రంగు ఉండకూడదు. పని చేసే కనీస రంగుల సంఖ్య ఎంత?

ఇదే హాడ్విగర్–నెల్సన్ సమస్య (Hadwiger–Nelson problem). ఇది 1950 నాటిది, రచయితల మాటల్లో విచ్ఛిన్న జ్యామితి (discrete geometry)లో అత్యంత ప్రసిద్ధి చెందిన అపరిష్కృత సమస్యల్లో ఒకటి. చాలా కాలం పాటు సమాధానం 4 నుంచి 7 మధ్య ఉంటుందని మాత్రమే తెలుసు. ఇటీవలి ఒక పెద్ద ముందడుగు కింది పరిమితిని 5 కి పెంచింది. కచ్చితమైన సమాధానం ఇప్పటికీ తెలియదు.

కొలబద్దను మార్చడం

దూరాన్ని సాధారణ కొలబద్దతోనే కొలవాల్సిన అవసరం లేదు. గణిత శాస్త్రవేత్తలు అనేక ఇతర నార్మ్‌లను (norms) — పొడవును కొలిచే పద్ధతులను — నిర్వచిస్తారు. ప్రతిదాన్నీ దాని “యూనిట్ బంతి” (unit ball) వర్ణిస్తుంది, అంటే కేంద్రం నుంచి గరిష్ఠంగా 1 దూరంలో ఉన్న బిందువుల సమితి. సాధారణ దూరానికి అది ఒక గుండ్రని బంతి; ఇతర నార్మ్‌లకు అది తన కేంద్రం చుట్టూ సౌష్ఠవంగా ఉండే ఏ కుంభాకార (convex) ఆకారమైనా కావచ్చు.

సమతలంపై ఉండే ప్రతి నార్మ్‌కూ, రంగుల చిక్కుప్రశ్నకు సమాధానం 4 నుంచి 7 మధ్య ఉంటుంది. d డైమెన్షన్లలో, ఏ నార్మ్‌కైనా అది గరిష్ఠంగా d లో ఘాతాంకీయంగా (exponential) ఉంటుంది. సాధారణ యూక్లిడియన్ నార్మ్‌తో సహా అనేక సహజమైన నార్మ్‌లకు అది కనీసం ఘాతాంకీయంగా కూడా ఉంటుంది: డైమెన్షన్ పెరిగే కొద్దీ రంగుల సంఖ్య విపరీతంగా పెరిగిపోతుంది.

ఆ విస్ఫోటనమే నియమమా? నోగా అలోన్ (ప్రిన్స్‌టన్ విశ్వవిద్యాలయం, టెల్ అవీవ్ విశ్వవిద్యాలయం), మాటియా బుచిచ్ (వియన్నా విశ్వవిద్యాలయం), జేమ్స్ డేవిస్ (లైప్‌జిగ్ విశ్వవిద్యాలయం) ఒక సాధారణ (typical) నార్మ్‌ను పరిశీలించారు. ఒక నార్మ్‌ను “యాదృచ్ఛికంగా” ఎంచుకోవడానికి సహజమైన మార్గం లేదు, కాబట్టి వారు ఒక టోపాలజీ భావనను వాడతారు: మినహాయింపులు ఉపేక్షించదగిన (“meagre”) సమితిని ఏర్పరిస్తే, ఆ గుణం సాధారణ నార్మ్‌కు వర్తిస్తుంది. అలోన్, బుచిచ్, లీసా సౌర్‌మాన్ గతంలో చేసిన పరిశోధన, ఒక సాధారణ నార్మ్‌కు గరిష్ఠంగా 2ᵈ రంగులు అవసరమని చూపి, అది నిజానికి ఎంత దగ్గరగా ఉందని ప్రశ్నించింది.

ఘాతాంకీయం కాదు, రేఖీయం

సమాధానం: చాలా దూరంగా ఉంది. కొత్త పత్రం ఇలా నిరూపిస్తుంది:

  • d-డైమెన్షనల్ అంతరాళంలోని ఒక సాధారణ నార్మ్‌కు, 2d రంగులు ఎప్పుడూ సరిపోతాయి;
  • ఇది అత్యుత్తమం: నార్మ్‌ల ఒక వివృత సమితి (open set)కి కనీసం 2d రంగులు అవసరం. కాబట్టి కొన్ని నార్మ్‌లకు సరిగ్గా 2d అవసరం.

పది డైమెన్షన్లలో, ఒక సాధారణ నార్మ్‌కు గరిష్ఠంగా ఇరవై రంగులు అవసరం, కాగా సాధారణ దూరానికి ఘాతాంకీయంగా పెరిగే సంఖ్య అవసరం. రచయితల ప్రకారం, ఏ డైమెన్షన్ d లోనైనా ఒక “కచ్చితంగా కుంభాకార” (strictly convex) నార్మ్‌కు రంగుల సంఖ్యను కచ్చితంగా నిర్ధారించడం కూడా ఇదే మొదటిసారి.

కింది పరిమితి ఒక చక్కని ఉచ్చును వాడుతుంది. 2d బిందువులను కనుగొనండి, అవన్నీ ఒకదానికొకటి సరిగ్గా ఒక యూనిట్ దూరంలో ఉండాలి, a, b అనే రెండు తప్ప — అవి అర యూనిట్ దూరంలో ఉంటాయి. మొత్తం అమరికకు a గుండా దర్పణ ప్రతిబింబాన్ని జోడించండి. 2d కంటే తక్కువ రంగులు ఉంటే, b కీ దాని దర్పణ ప్రతిబింబానికీ రెండింటికీ a రంగే తప్పనిసరిగా రావాలి — కానీ అవి సరిగ్గా ఒక యూనిట్ దూరంలో ఉన్నాయి. వైరుధ్యం. నార్మ్‌లో ఏ చిన్న మార్పు వచ్చినా ఈ అమరిక నిలిచి ఉంటుందని ఒక స్థిరత్వ లెమ్మా (stability lemma) చూపుతుంది.

అధిక డైమెన్షన్లలో ఒంటరి పరుగుదారు

పై పరిమితి ప్రతి బిందువుకూ, దాని ఒక చక్కగా ఎంచుకున్న ప్రక్షేపం (projection) 1/(2d) వెడల్పు గల ముక్కల్లో ఎక్కడ పడుతుందో దాన్ని బట్టి రంగు వేస్తుంది. ఇది పని చేయాలంటే ఒక కీలక అంశం అవసరం. దాన్ని రచయితలు ప్రసిద్ధ ఒంటరి పరుగుదారు ఊహ (lonely runner conjecture) యొక్క అధిక-డైమెన్షనల్, మాత్రికా రూపంగా వర్ణిస్తారు:

sup over x of minᵢ ‖aᵢ · x − bᵢ‖ ≥ k / (2n)

ఇక్కడ ‖t‖ అంటే t నుంచి దగ్గరి పూర్ణాంకానికి దూరం; k డైమెన్షన్లలో ఉండే ఏ n సదిశలు aᵢ కైనా, వాటిలో ఏ k అయినా స్వతంత్రంగా ఉంటే ఇది వర్తిస్తుంది. ఈ ప్రకటన “దృష్టి అవరోధం” (view obstruction) మీద I. J. షోన్‌బర్గ్ 1978 నాటి ఊహను కూడా పరిష్కరిస్తుంది — అనంతం వైపు ప్రతి దృష్టినీ అడ్డుకోవడానికి ఆవర్తన పలకలు (periodic slabs) ఎంత మందంగా ఉండాలనే ప్రశ్న అది. రచయితలు దీన్ని ఈ రంగంలో అత్యంత సంప్రదాయ అపరిష్కృత సమస్యల్లో ఒకటిగా పేర్కొంటారు. దీనికి సంబంధించిన హెంజే, మాలికియోసిస్ ఊహను కూడా ఇది పరిష్కరిస్తుంది.

కృతజ్ఞతల్లో యంత్రం

రచయితలు స్పష్టంగా చెబుతారు: “సిద్ధాంతం 1 నిరూపణలో మాకు అవసరమైన చివరి అంశం, అంటే లెమ్మా 7 నిరూపణను, సుదీర్ఘ చర్చ తర్వాత ChatGPT 6 Pro మాకు అందించింది”. ఆ చర్చలో వారు తమ సొంత పరిశీలనలను — ఇండక్షన్ ఆలోచన, సాధారణ వ్యూహంతో సహా — పంచుకున్నారు. “కింది పరిమితి వాదన కూడా ChatGPT 6 Pro సహాయంతోనే కనుగొనబడింది.”

ప్రశ్నలు మిగిలే ఉన్నాయి. కచ్చితమైన విలువ 2d నార్మ్‌ల ఒక వివృత సమితికి నిరూపితమైంది, అన్ని సాధారణ నార్మ్‌లకూ కాదు. సాధారణ యూక్లిడియన్ దూరానికి, ప్రతి డైమెన్షన్‌లోనూ 2d కంటే కచ్చితంగా ఎక్కువ రంగులు అవసరమవుతాయని రచయితలు ఆశిస్తున్నారు — ఇది 2, 4, 7, 8 డైమెన్షన్లలో, 9 నుంచి పైన ఇప్పటికే తెలుసు, కానీ 3, 5, 6 డైమెన్షన్లలో ఇంకా అపరిష్కృతంగానే ఉంది.