ఒక AI నిరూపణ, మనుషుల కోసం మళ్లీ గీసినది
కొన్ని చుక్కలు గీసి, వాటిలో కొన్నింటిని గీతలతో కలపండి. గణిత శాస్త్రవేత్తలు దీన్ని గ్రాఫ్ అంటారు; చుక్కలు శీర్షాలు, గీతలు అంచులు, ఒక చుక్కను తాకే గీతల సంఖ్య దాని డిగ్రీ. వృక్షం అంటే ఎలాంటి లూప్లూ లేకుండా, కొమ్మలున్న రెమ్మలా ఒకే ముక్కగా కలిసి ఉండే గ్రాఫ్; t చుక్కలున్న వృక్షానికి ఎల్లప్పుడూ t − 1 గీతలు ఉంటాయి.
1960ల ప్రారంభంలో, పాల్ ఎర్డోస్, వెరా టి. షోష్ ఒక సరళమైన ప్రశ్న అడిగారు: ఎన్ని గీతలు ఉంటే ఒక గ్రాఫ్లో ఇచ్చిన పరిమాణంలోని ప్రతి వృక్షమూ తప్పనిసరిగా ఉంటుంది? వారి సమాధానం, ఎర్డోస్–షోష్ ఊహ (Erdős–Sós conjecture), ఇది:
ఒక గ్రాఫ్ సగటు డిగ్రీ t − 2 కంటే ఎక్కువ అయితే, అందులో t శీర్షాలున్న ప్రతి వృక్షమూ ఉంటుంది.
ఈ పరిమితి ఖచ్చితమైనది. ప్రతి జంటా కలపబడిన, t − 1 చుక్కలున్న సంపూర్ణ గ్రాఫ్ యొక్క వేర్వేరు ప్రతులను తీసుకోండి: ప్రతి చుక్కకు సరిగ్గా t − 2 పొరుగువి ఉంటాయి, అయినా ఏ ముక్కా t చుక్కల వృక్షాన్ని పట్టేంత పెద్దది కాదు. కష్టమంతా సగటు అనే పదంలోనే ఉంది. ప్రతి ఒక్క చుక్కకూ కనీసం t − 1 పొరుగువి ఉంటే, వృక్షాన్ని కొమ్మ కొమ్మగా ఏ ఇబ్బందీ లేకుండా అమర్చవచ్చు. కానీ సగటు ఏ ఒక్క చుక్క గురించీ ఏమీ చెప్పదు: కొన్నింటికి వందల పొరుగువి ఉండవచ్చు, మరికొన్నింటికి దాదాపు ఏవీ ఉండకపోవచ్చు.
అరవై ఏళ్ల పాక్షిక సమాధానాలు
పత్రంలో వివరించిన చరిత్ర ప్రకారం, ఈ సమస్య 1962–1964 నాటిది, ఒక నిర్దిష్ట నమూనా ఏర్పడటానికి ఎన్ని అంచులు అవసరమో అధ్యయనం చేసే గణిత శాఖకు కేంద్రంగా మారింది. ప్రత్యేక సందర్భాలు ఒక్కొక్కటిగా పరిష్కారమయ్యాయి: నక్షత్రాలు, మార్గాలు, జంట నక్షత్రాలు, తక్కువ కొమ్మలున్న వృక్షాలు. 1990ల ప్రారంభంలో నలుగురు గణిత శాస్త్రవేత్తలు — అయ్తాయ్, కోమ్లోష్, సిమోనోవిచ్, సెమెరెడి — చాలా పెద్ద వృక్షాలకు ఒక నిరూపణను ప్రకటించారు, కానీ దాని పూర్తి రాతప్రతి ఎప్పుడూ ప్రచురితం కాలేదని ఇటీవలి పత్రాలు పేర్కొంటున్నాయి. మరిన్ని పాక్షిక ఫలితాలు 2021, 2024, 2026లలో వచ్చాయి. 2026 సెప్టెంబర్ 4న, రీడ్, స్టైన్ పెద్ద, దట్టమైన గ్రాఫ్లకు ఒక నిరూపణను పోస్ట్ చేశారు, దాన్ని AI లేకుండా రూపొందించామని వారు చెబుతున్నారు.
తర్వాత ఒక నివేదిక వచ్చింది. 2026 సెప్టెంబర్లో, టామ్ ఆడమ్చెవ్స్కీ, థామస్ బ్లూమ్ FrontierMath Erdős అనే పత్రంలో పూర్తి ఊహ నిరూపణను GPT-6 Astra అనే AI నమూనా విడుదలకు ముందు రూపానికి ఆపాదించారు. అసలు లెక్కింపు వాదన బహిరంగంగా అందుబాటులో ఉంది, దానితో పాటు ఉన్న ఒక రిపాజిటరీ నిరూపణ కోసం AI స్వతంత్రంగా సాగించిన అన్వేషణను, Lean అనే నిరూపణ-తనిఖీ భాషలో లాంఛనప్రాయ ధ్రువీకరణను నమోదు చేస్తుంది. నివేదిక రచయితలు మానవ నిపుణులను మరింత పూర్తిస్థాయి, సంప్రదాయ వివరణలు రాయమని కూడా కోరారు.
ఒక్కో చుక్కగా గ్రాఫ్ను బయటపెట్టడం
కాలిఫోర్నియా స్టేట్ యూనివర్సిటీ, శాక్రమెంటోకు చెందిన జే కమింగ్స్ ఆ పిలుపుకు స్పందిస్తున్నారు. ఆయన 27 పేజీల వ్యాసం AI కేంద్ర లెక్కింపు వాదనను అలాగే ఉంచుతుంది, కానీ దాన్ని చెప్పే తీరును మారుస్తుంది:
- గ్రాఫ్ను క్రమంగా బయటపెట్టండి. శీర్షాలను ఏదో ఒక క్రమంలో జాబితా చేసి, వాటిని ఒక్కొక్కటిగా బయటపెట్టండి, ఇప్పటికే చూపిన వాటి మధ్య అంచులతో సహా.
- ఇంకా ఎక్కువ అడగండి. వృక్షపు ఏదైనా ప్రతికి బదులు, ఎంచుకున్న “మూలం” (root) సరిగ్గా మొట్టమొదటి శీర్షంపై ఉండే ప్రతి కోసం వెతకండి. ఎక్కువ అడగడం నిరూపణను సులభతరం చేస్తుంది.
- ముందుగా వచ్చే పొరుగువాటిని లెక్కించండి. అలాంటి ప్రతి కనిపించడానికి ముందే వచ్చే మొదటి శీర్షపు పొరుగువి ఇవి. సాధ్యమైన ప్రతి క్రమంపైనా వాటిని కూడండి.
- మొత్తానికి హద్దు విధించండి. శీర్షాలను లేదా క్రమంలోని మొత్తం భాగాలను తారుమారు చేయడం ద్వారా — ఎల్లప్పుడూ వెనక్కి తిప్పగలిగే కదలికలు — అన్ని క్రమాలపై సగటున, ముందుగా వచ్చే పొరుగువి గరిష్ఠంగా t − 2 మాత్రమే ఉంటాయని కమింగ్స్ చూపిస్తారు.
చివరి అడుగు చిన్నది. గ్రాఫ్లో వృక్షపు ప్రతి ఒక్కటి కూడా లేకపోతే, మొదటి శీర్షపు ప్రతి పొరుగూ, ప్రతి క్రమంలోనూ, ముందుగా వచ్చినదే అవుతుంది. అన్ని క్రమాలపై సగటు తీసుకుంటే, అది సరిగ్గా సగటు డిగ్రీ — ఊహ ప్రకారం అది t − 2 కంటే ఎక్కువ. వైరుధ్యం: వృక్షం అక్కడ ఉండి తీరాలి.
ఈ నిరూపణ డిగ్రీల మొత్తాన్ని మాత్రమే వాడుతుంది, అవి ఎలా విస్తరించి ఉన్నాయో కాదు. కమింగ్స్ ఒక సంభావ్యతా రూపాన్ని కూడా ఇస్తారు, నాలుగు, ఐదు శీర్షాలున్న వృక్షాలను నిర్దిష్ట గ్రాఫ్లపై సాధించి చూపిస్తారు.
ఒక నిరూపణ బొమ్మల పుస్తకం
వ్యాసంలో 32 చిత్రాలు ఉన్నాయి. అది ఒక సాంప్రదాయ పర్యవసానంతో ముగుస్తుంది: ఒక సంపూర్ణ గ్రాఫ్ గీతలన్నింటికీ q రంగులు వేయండి, గ్రాఫ్కు q(t − 2) + 2 శీర్షాలు ఉన్నప్పుడు ఏదో ఒక రంగులో ఇచ్చిన వృక్షం ఎల్లప్పుడూ ఉంటుంది. ఒక చివరి ప్రకటనలో, కమింగ్స్ ఈ పాఠాన్ని ChatGPT తో సుదీర్ఘ సంభాషణలో రూపొందించానని, కొత్త ప్రదర్శన ఆలోచనలు — ముందుగా వచ్చే పొరుగువి, స్పష్టమైన విభజనలు, బొమ్మలు — తనవేనని, అన్నింటినీ తాను తనిఖీ చేసి పూర్తి బాధ్యత తీసుకుంటానని వివరిస్తారు.
ఆయన తన వివరణను రియోర్డన్, స్కాట్, వుడ్, ఫ్రెడరిక్సన్ల ఇతర ఇటీవలి వివరణలతో పోలుస్తారు, ఈ పద్ధతి ఇప్పటికే దిశలున్న జాలాలకు, “హైపర్గ్రాఫ్ల” (hypergraphs) కు విస్తరించబడిందని, ఆ విస్తరణల్లో కొన్ని కూడా GPT-6 Astra కు ఆపాదించబడ్డాయని పేర్కొంటారు. తన రచన “వాదనకు పాఠక-కేంద్రిత, దృశ్య వివరణ, ఊహకు కొత్త పరిష్కారం కాదు” అని ఆయన రాస్తారు.
