కొన్ని చతుర్మితీయ ఆకారాలను ఏ అల్గోరిథమూ గుర్తించలేదు

కొన్ని ప్రశ్నలకు వంటకం (recipe) ఉండదు. ఎవరూ ఇంకా ఒకదాన్ని కనుగొనకపోవడం వల్ల కాదు, ఏ అల్గోరిథమూ — ఏ దశలవారీ పద్ధతీ, అది ఎంత పొడవైనదైనా, ఏ కంప్యూటర్‌పై నడిపినా — వాటికి ప్రతిసారీ సరిగ్గా జవాబు చెప్పలేదని నిరూపితమైనందువల్ల. ఆస్టిన్‌లోని యూనివర్సిటీ ఆఫ్ టెక్సాస్‌కు చెందిన కామెరాన్ మెక్‌ఎ. గోర్డన్ (Cameron McA. Gordon), చతుర్మితీయ ఆకారాల గురించి అలాంటి రెండు ప్రశ్నలను జోడిస్తున్నారు.

ఇది అదే ఆకారమా?

గణిత శాస్త్రవేత్తలు ఈ ఆకారాలను 4-మానిఫోల్డ్‌లు (4-manifolds) అంటారు: దగ్గరగా చూస్తే, ప్రతిచోటా సాధారణ చతుర్మితీయ అంతరాళంలా కనిపించే అంతరాళాలు. వాటిని కంప్యూటర్‌కు అందించడానికి, అవి కలిపి అతికించిన చదునైన ముక్కలతో నిర్మితమైనవని (“piecewise linear”, లేదా PL) పత్రం ఊహిస్తుంది, తద్వారా ప్రతిదాన్నీ ఒక పరిమిత దత్తాంశ జాబితాతో వర్ణించవచ్చు. అప్పుడు ప్రాథమిక ప్రశ్న ఇది: అలాంటి రెండు ఆకారాలు ఇస్తే, అవిచ్ఛిన్న రూపాంతరం (continuous deformation) వరకు, అవి ఒకటేనా?

1958లో, ఏ. ఏ. మార్కోవ్ (A. A. Markov) ఈ ప్రశ్నకు అల్గోరిథం లేదని చూపించారు. మార్కోవ్ నిరూపణ ఆకారాల సమస్యను సమూహాల (groups) గురించిన సమస్యగా మారుస్తుంది: పరిమిత సంఖ్యలో నియమాలతో నిర్వచించిన కొన్ని సమూహాలు — వరుసగా కలపగలిగే, రద్దు చేయగలిగే చర్యల సముదాయాలు — ఉన్నాయి, వాటి మూలకాల ఒక ఇచ్చిన కలయిక, “పదం” (word) అని పిలిచేది, తత్సమ మూలకానికి (identity), అంటే ఏమీ చేయని మూలకానికి, సమానమో కాదో ఏ అల్గోరిథమూ నిర్ణయించలేదు — ఇదే “పద సమస్య” (word problem). అలాంటి సమూహం నుంచి, ఆ అసాధ్యమైన సమస్యను పరిష్కరించడం ద్వారా మాత్రమే ఒక అల్గోరిథం వేరు చేయగలిగే ఆకారాలను నిర్మించవచ్చు.

ఏడు వరకు కౌంట్‌డౌన్

మార్కోవ్ వాదన ఆ కష్టాన్ని నిర్దిష్ట ఆకారాలకు కూడా కట్టివేస్తుంది. ఒక సాధారణ బంతి ఉపరితలమైన S² ను తీసుకుని, S² × S² లబ్ధాన్ని ఏర్పరచండి; అది ఒక చతుర్మితీయ ఆకారం. దాని k నకళ్లను కలిపి అతికించండి (ఒక “సంధానిత మొత్తం”, connected sum, #k అని రాస్తారు). కొన్ని k విలువలకు, ఇచ్చిన ఒక ఆకారం #k(S² × S²) అవునో కాదో ఏ అల్గోరిథమూ నిర్ణయించలేదు. ఏ k?

పత్రం ఈ కౌంట్‌డౌన్‌ను వివరిస్తుంది. 1969లో బొరిసోవ్ (Borisov) కనుగొన్న, పరిష్కరించలేని పద సమస్య, 12 నియమాలు ఉన్న ఒక సమూహం 14 నకళ్లను ఇచ్చింది. గోర్డన్ 2022లో దాన్ని 12 కు తెచ్చారు. ఎం. టాన్సర్ (M. Tancer), ఫ్రీడ్‌మన్ (Freedman) చేసిన చతుర్మితీయ ఆకారాల వర్గీకరణ గుండా ఒక కొత్త మార్గాన్ని కనుగొని, “టోపోలాజికల్” (topological) రూపంలో 9 కి చేరారు; ఆ రూపంలో ఆకారాలు చదునైన ముక్కలతో నిర్మితమై ఉండాల్సిన అవసరం లేదు. ఈ పని యొక్క ఒక పూర్వ రూపం 8కి చేరింది. తర్వాత కెగెల్ (Kegel), లి (Li), రెన్ (Ren) చాలా చిన్నదైన ఒక పరిష్కరించలేని సమూహాన్ని — 3 జనకాలు (generators), 9 నియమాలు — నిర్మించి, టోపోలాజికల్ రూపంలో 7 కి, చదునైన ముక్కల రూపంలో 9కి చేరారు.

గోర్డన్ టాన్సర్ మార్గాన్ని చదునైన ముక్కలతో నిర్మించిన ఆకారాలకు కూడా పనిచేసేలా చేసి, ఇలా నిరూపించారు:

ఇచ్చిన ఒక 4-మానిఫోల్డ్, S² × S² యొక్క 7 నకళ్ల సంధానిత మొత్తంతో ముక్క ముక్కగా అదేనా అని నిర్ణయించే అల్గోరిథం ఏదీ లేదు.

నిరూపణకు మూలం ఒక నిఘంటువు. కెగెల్, లి, రెన్ సమూహంలోని ప్రతి పదం wకూ, గోర్డన్ ఒక చతుర్మితీయ ఆకారాన్ని నిర్మిస్తారు. w తత్సమ మూలకానికి సమానమైతే, నియమాలపై అనుమతించిన కదలికల వరుస — ఆకారాన్ని మార్చకుండా వర్ణనను తిరగరాసే ఆండ్రూస్-కర్టిస్ కదలికలు (Andrews-Curtis moves) — ఆ ఆకారం సరిగ్గా S² × S² యొక్క ఏడు నకళ్లని చూపిస్తుంది. సమానం కాకపోతే, ఆ ఆకారంలో ఒక బిందువుకు బిగించలేని లూప్‌లు (loops) ఉంటాయి — S² × S² యొక్క ఏడు నకళ్లలో అది ఎప్పుడూ జరగదు — కాబట్టి అది ఆ ఏడు నకళ్లు కాజాలదు. అందువల్ల #7(S² × S²)ను గుర్తించే అల్గోరిథం పద సమస్యను పరిష్కరిస్తుంది, అది అసాధ్యం.

ముడిపడిన గోళాలు

రెండో ప్రశ్న ముడుల గురించి. ఒక సాధారణ ముడి అంటే త్రిమితీయ అంతరాళంలో ముడి వేసిన ఒక వృత్తం, ఒక ముడిని విప్పగలమో లేదో నిర్ణయించడం సాధ్యమే: హాకెన్ (Haken) కనుగొన్న ఒక అల్గోరిథం ఉంది. ఒక కొలత పైకి వెళ్తే, ఒక ద్విమితీయ గోళం చతుర్మితీయ అంతరాళంలో ముడిపడి ఉండగలదు. ఎక్కువ కొలతల్లో, సంబంధిత సమస్యకు అల్గోరిథం లేదని తెలుసు. చతుర్మితీయ గోళం S⁴లోని ద్విమితీయ గోళాల విషయంలో, ఎవరికీ తెలియదు.

#7(S² × S²) లోపల, ఒక ద్విమితీయ గోళం — లేదా ఏ ఉపరితలమైనా, రెండు వైపులది గానీ ఒకే వైపుది గానీ — ముడిలేనిదో (unknotted) కాదో నిర్ణయించే అల్గోరిథం లేదని గోర్డన్ నిరూపించారు. ఈ క్రమంలో, పత్రం ఆ ఆకారంలో ఒక గోళాన్ని నిర్మిస్తుంది, దాని చుట్టూ ఉన్న అంతరాళపు సమూహానికి పరిష్కరించలేని పద సమస్య ఉంటుంది; అలాగే S² × S² యొక్క 12 నకళ్లలో, ఒక కంప్యూటర్ వర్ణించగలిగే ప్రతి సమూహపు నకలునూ కలిగి ఉండే సమూహం గల ఒక గోళాన్ని కూడా నిర్మిస్తుంది.

బహుమతి: సున్నా నకళ్లు

పత్రం లక్ష్యాన్ని స్పష్టంగా చెబుతుంది: నకళ్ల సంఖ్యను సున్నాకు తీసుకురావడం. సున్నా నకళ్లు అంటే చతుర్మితీయ గోళం S⁴ స్వయంగా. ఐదు, అంతకంటే ఎక్కువ కొలతల్లో, ఏ అల్గోరిథమూ గోళాన్ని గుర్తించలేదు; రెండు, మూడు కొలతల్లో, ఒక అల్గోరిథం గుర్తించగలదు. నాలుగు కొలతల ప్రశ్న ఇంకా అపరిష్కృతంగానే ఉంది — S⁴లో ముడిపడిన గోళాలను కనిపెట్టగలమా అనే ప్రశ్న కూడా. తొలగించిన ప్రతి నకలూ రెండు ప్రశ్నలకూ మరింత దగ్గర చేస్తుంది.