రంగుల చిక్కుముడిని విప్పిన AI

గీతలతో కలిపిన బిందువుల నెట్‌వర్క్‌ను తీసుకోండి — గణిత శాస్త్రవేత్తలు దీన్ని గ్రాఫ్ అంటారు. ఇప్పుడు గీతతో కలిసిన రెండు బిందువులకు ఎప్పుడూ ఒకే రంగు రాకుండా బిందువులకు రంగులు వేయండి. ఇది సాధ్యమయ్యే కనిష్ఠ రంగుల సంఖ్యే ఆ గ్రాఫ్ వర్ణ సంఖ్య (chromatic number). ఒక ప్రసిద్ధ ప్రత్యేక సందర్భం 1977లో నిరూపితమైన నాలుగు రంగుల సిద్ధాంతం, దాని శీర్షికే అంతా చెబుతుంది: “Every planar map is four colorable” (ప్రతి సమతల పటానికీ నాలుగు రంగులు సరిపోతాయి).

హాడ్విగర్ 1943 పందెం

1943లో, హాడ్విగర్ అన్ని గ్రాఫ్‌లకూ వర్తించే ఒక విస్తృత నియమాన్ని ప్రతిపాదించాడు. బిందువులను లేదా గీతలను తొలగించడం ద్వారా, కలిసిన రెండు బిందువులను ఒకటిగా విలీనం చేయడం ద్వారా ఒక గ్రాఫ్‌ను కుదించండి. ఫలితాన్ని మైనర్ (minor) అంటారు. ఈ విధంగా పొందగల అతి పెద్ద సంపూర్ణ గ్రాఫ్‌ను — ప్రతి బిందువూ మిగతా ప్రతి బిందువుతో కలిసిన సమూహం — హాడ్విగర్ పరిశీలించి, అవసరమైన రంగుల సంఖ్య ఆ సమూహ పరిమాణాన్ని ఎప్పుడూ మించదని ఊహించాడు.

పత్రం దీన్ని “గ్రాఫ్ సిద్ధాంతంలోని అత్యంత పురాతనమైన, అత్యంత మౌలికమైన సమస్యలలో ఒకటి” అంటుంది. ఇది చిన్న సందర్భాలకు మాత్రమే నిరూపితమైంది: ఐదు వరకు సమూహాలకు, అక్కడ అది నాలుగు రంగుల సిద్ధాంతానికి సమానమని లేదా దానికి కుదించవచ్చని తేలింది. ఆరు నుంచి ముందుకు, అది తెరిచే ఉంది.

ఒక్కో సంవర్గమానంతో దగ్గరవుతూ

ఖచ్చితమైన ప్రకటన లొంగకపోవడంతో, పరిశోధకులు రంగుల సంఖ్యను సమూహ పరిమాణానికి సంబంధించిన ఏదో ఒక ప్రమేయంతో, వీలైనంత నెమ్మదిగా పెరిగేదానితో, పరిమితం చేయడానికి ప్రయత్నించారు. పత్రం ఆ పురోగతిని వివరిస్తుంది. దశాబ్దాలుగా, అత్యుత్తమ పరిమితి అనుపాతం కంటే కాస్త వేగంగా పెరిగింది — ఒక సంవర్గమానం (logarithm) వర్గమూలం ఉన్న గుణకం మేర. కొన్నేళ్ల క్రితం, నోరిన్ (Norin), పోస్ట్ల్ (Postle), సాంగ్ (Song) ఆ అడ్డంకిని ఛేదించారు. ఆ తర్వాత డెల్‌కూర్ (Delcourt), పోస్ట్ల్ దాన్ని మరింత మెరుగుపరిచి, కీలకంగా, తగినంత చిన్న గ్రాఫ్‌లను పరిష్కరిస్తే చాలని చూపించారు. లియు (Liu), లువో (Luo) అదనపు గుణకాన్ని మూడంచెల సంవర్గమానానికి తగ్గించారు.

సహజమైన గమ్యం రేఖీయ హాడ్విగర్ ఊహ: సమూహ పరిమాణానికి ఒక స్థిరమైన గుణిజం ఎప్పుడూ సరిపోతుంది. మాంట్రియల్‌లోని మెక్‌గిల్ విశ్వవిద్యాలయానికి చెందిన సెర్గీ నోరిన్ (Sergey Norin), ETH జ్యూరిక్‌కు చెందిన రాఫాయెల్ స్టైనర్ (Raphael Steiner) ఇప్పుడు నిరూపించామని చెబుతున్నది ఇదే.

యంత్రం పోషించిన పాత్ర

రచయితలు స్పష్టంగా చెబుతారు: నిరూపణను వారి సూచనలను అనుసరించి OpenAI నమూనా GPT-6 Astra కనుగొంది. వారు మొదట దాన్ని చాలా దట్టమైన గ్రాఫ్‌ల సందర్భాన్ని నిరూపించమని అడిగారు, అదే తప్పిపోయిన ముక్క అని వారు నమ్మారు. అది విజయవంతమైంది, “కేవలం రెండు మూడు గంటలు, కొంత ప్రోత్సాహం తర్వాత” అని వారు రాస్తారు. ఒక ఆధారపడటాన్ని స్పష్టం చేయమని అడిగినప్పుడు, అది ఒక నిర్దిష్ట పరిమాణం వరకు గ్రాఫ్‌లను కవర్ చేసింది — కానీ అవసరమైన పరిధిని పూర్తిగా కాదు. అప్పుడు వారు ఆ ఖాళీని పూడ్చడానికి ఒక మౌలిక ఆలోచనను అడిగారు, దాని నుంచి తుది నిరూపణలోని “బూట్‌స్ట్రాప్” దశ పుట్టింది. సంకోచాల (contractions) గురించిన ఒక సూచన తప్ప, రచయితల సొంత నిర్దిష్ట నిరూపణ ఆలోచనలలో దాదాపు ఏదీ మిగల్లేదని వారు చెబుతారు.

రాత మనుషులది. మరో OpenAI నమూనా ప్రూఫ్‌రీడింగ్‌కు, గ్రంథసూచికకు సహాయపడింది. OpenAI Codex మొత్తం నిరూపణకు Lean నిరూపణ సహాయకంలో ఒక లాంఛనప్రాయమైన, యంత్రంతో తనిఖీ చేయగల రూపాన్ని తయారు చేసిందని రచయితలు నివేదిస్తారు, దాన్ని AI రాసిన తొలి ముసాయిదాతో పాటు ఆన్‌లైన్‌లో ఉంచారు. గణితానికి పూర్తి బాధ్యత తామే తీసుకుంటారు.

నిరూపణ లోపల

వాదనలో రెండు భాగాలు ఉన్నాయి:

1. చిన్న గ్రాఫ్‌లు, కొన్ని రంగులు. సమూహ పరిమితి కంటే మరీ పెద్దవి కాని గ్రాఫ్‌లకు, సమూహ పరిమాణానికి సుమారు నాలుగు రెట్లు సరిపోతుందని రచయితలు చూపిస్తారు. ప్రారంభ బిందువు రీడ్ (Reed), సేమూర్ (Seymour)ల 1998 ఫలితం: రంగులు వేయడంలో సడలించిన, “భిన్నాత్మక” (fractional) రూపం ఇప్పటికే గుణకం రెండుతో రేఖీయ నియమాన్ని పాటిస్తుంది. కొత్త పని గ్రాఫ్‌కు కొన్ని అదనపు గీతలు జోడించి, ఒక సహాయక నిర్మాణంలో భారీ జతకూర్పులను (matchings) కనుగొనడం ద్వారా భిన్నాత్మక రంగులను నిజమైన రంగులుగా మారుస్తుంది.
2. బూట్‌స్ట్రాప్. రెండో వాదన కవర్ అయ్యే గ్రాఫ్ పరిమాణాల పరిధిని ప్రతి దశలో ఘాతంలో నాలుగు-బై-మూడు గుణకంతో విస్తరిస్తుంది, పెద్ద స్థిరాంకం మూల్యంగా. పది దశలు పరిధిని మూడింట ఒకటి నుంచి సుమారు 5.92కి తీసుకెళ్తాయి, డెల్‌కూర్-పోస్ట్ల్ కుదింపుకు అవసరమైన 5 అనే పరిమితిని దాటి. ఈ భాగం గ్యార్ఫాష్ (Gyárfás) పాత ఉపాయాన్ని ఉపయోగిస్తుంది, దాన్ని ఈ సమస్యకు ఇంతకు ముందెన్నడూ వర్తింపజేయలేదని రచయితలు అంటారు.

రచయితలు నిరూపణను తెలిసిన సాధనాలతో నిర్మించినదిగా వర్ణిస్తారు — “ఇప్పటికే ఉన్న ఫలితాల కుంభాకార ఆవరణ (convex hull) లోపలే ఉన్నది”, అయినా దాని స్పష్టమైన అంచు మీద లేనిది.

తెరిచే ఉన్నవి

స్థిరాంకం అపారమైనది: స్థూల అంచనా సుమారు 10¹⁰⁰ ఇస్తుంది. దాన్ని 10¹⁰ కంటే తక్కువకు తీసుకురావడానికి అవకాశం ఉందని రచయితలు భావిస్తారు, కానీ, ఉదాహరణకు, 100కి చేరాలంటే కొత్త ఆలోచనలు అవసరమని అనుకుంటారు. హాడ్విగర్ ఖచ్చితమైన ఊహను ఎవరూ తాకలేదు: “మేము ఇంకా నిర్ణయించుకోలేదు,” అని వారు రాస్తారు. పత్రం ఒక ప్రీప్రింట్; 41 పేజీల కొత్త గణితం ఇప్పుడు ఇతర నిపుణుల నిశిత పరిశీలనను ఎదుర్కోవాలి.