పొద్దుతిరుగుడు ఊహ నిరూపితమైంది

1 నుంచి n వరకు ఉన్న సంఖ్యలను తీసుకుని, వాటిలో కొన్నింటిని ఎంచుకునే అన్ని మార్గాలను చూడండి: అలాంటి ఉపసమితులు 2ⁿ ఉన్నాయి. ఇప్పుడు సరిగ్గా ఒకే ఉమ్మడి భాగాన్ని పంచుకుని, మరేమీ పంచుకోని కొన్ని ఉపసమితులను ఎంచుకోండి. గణిత శాస్త్రవేత్తలు దీన్ని పొద్దుతిరుగుడు (sunflower) అంటారు: ఉమ్మడి భాగం కేంద్రం, ప్రతి సమితిలో మిగిలిన భాగం మరే రేకునూ తాకని ఒక రేకు.

పొద్దుతిరుగుడులు సంయోజన శాస్త్రం (combinatorics) యొక్క ప్రాథమిక సాధనం. కొన్ని తర్క వలయాల పరిమితులు, “cap set” సమస్య, వేగవంతమైన మాతృకా గుణకారం, సమాచార సిద్ధాంతంతో ఉన్న సంబంధాలను పత్రం పేర్కొంటుంది.

1970 నాటి ప్రశ్న

రచయితల ప్రకారం, వాటి గురించిన అత్యంత సహజమైన ప్రశ్న Paul Erdős 1970లో రాసిన ఒక పత్రం నాటిది. {1, …, n} యొక్క ఉపసమితుల సేకరణ, దానిలోని ఏ k సమితులూ పొద్దుతిరుగుడు ఏర్పరచకపోతే, ఎంత పెద్దదిగా ఉండగలదు?

1970లలో Erdős, Endre Szemerédi అలాంటి సేకరణ సాధ్యమయ్యే 2ⁿ ఉపసమితుల కంటే ఘాతాంకపరంగా చిన్నదిగా ఉండాలని ఊహించారు: 2 కంటే ఖచ్చితంగా తక్కువైన ఏదో ఒక సంఖ్య c కి, గరిష్ఠంగా cⁿ.

దశాబ్దాల పాటు అత్యుత్తమ హద్దులు కొంచెం మాత్రమే తగ్గించగలిగాయి, ఆధారాన్ని 2 కంటే కిందికి తీసుకురావడానికి ఎప్పుడూ సరిపోలేదు. మూడు రేకుల సందర్భం (k = 3) మాత్రమే పరిష్కారమైంది, 2016లో, cap set సమస్యపై వచ్చిన విప్లవాత్మక పురోగతి ద్వారా, Alon, Shpilka, Umans చేసిన ఒక సమస్యా-రూపాంతరం (reduction) ద్వారా.

హద్దు

Matija Bucić, Fankang He (వియన్నా విశ్వవిద్యాలయం), Hyunwoo Lee (KAIST, దక్షిణ కొరియాలోని Institute for Basic Science) ఈ ఊహను ప్రతి k ≥ 3 కి నిరూపించారు. వారి ప్రధాన సిద్ధాంతం: k రేకుల పొద్దుతిరుగుడు లేని సేకరణలో గరిష్ఠంగా

3 · (2 − 1/(16k³))ⁿ

సభ్యులు ఉంటారు. ఆధారం 2 కి కొంచెం కిందే ఉంది, కానీ అది 2 కంటే తక్కువైన ఒక స్థిర సంఖ్య, Erdős, Szemerédi సరిగ్గా అడిగింది అదే. పెద్ద k లకు నిజమైన విలువ దీని కంటే చాలా తక్కువగా ఉండలేదని 1997 నాటి ఒక నిర్మాణం చూపిస్తుంది.

సమితుల నుంచి సదిశలకు

నిరూపణ సమస్య యొక్క సదిశల (vectors) రూపాంతరం గుండా సాగుతుంది. సంఖ్యలను ఒక్కొక్కటి D మూలకాలు గల n బ్లాకులుగా విభజించి, ప్రతి బ్లాకు నుంచి ఒక మూలకాన్ని ఎంచుకోండి: ప్రతి ఎంపికా ఒక సదిశ. ప్రతి స్థానంలోనూ వాటి ఎంట్రీలు అన్నీ సమానంగా గానీ, అన్నీ వేర్వేరుగా గానీ ఉన్నప్పుడు కొన్ని సదిశలు పొద్దుతిరుగుడును ఏర్పరుస్తాయి.

తర్వాత రచయితలు ఒక “పొద్దుతిరుగుడు పరీక్షకి” ని నిర్మిస్తారు: పొద్దుతిరుగుడు లేని సేకరణపై, దాని ఇన్‌పుట్‌లన్నీ ఒకే సదిశ అయినప్పుడు మాత్రమే సున్నా కాని విలువనిచ్చే ఒక ప్రమేయం. కొత్త అంశం ఏమిటంటే, ఈ ప్రమేయాన్ని అడుగడుగునా తక్కువ డిగ్రీ గల అంతర్వేశన బహుపదులతో (interpolation polynomials) రాయడం. ఆ బహుపదులను లెక్కించడం సేకరణ పరిమాణానికి హద్దును ఇస్తుంది (వారి సిద్ధాంతం 2). ఒక సంభావ్యతా వాదం, అంటే అన్ని సమితి పరిమాణాలపై సగటు తీసిన యాదృచ్ఛిక బ్లాకులు, ఆ హద్దును సాధారణ సమితులకు తిరిగి తీసుకువస్తుంది.

ఒక యంత్రం కనుగొంది, మరొకటి తనిఖీ చేసింది

AI గురించి పత్రంలోని ప్రకటన అసాధారణంగా సూటిగా ఉంది. సిద్ధాంతం 2 యొక్క నిరూపణను ChatGPT 6 Astra Pro కనుగొంది, తెలిసిన మూడు రేకుల వాదాన్ని సాధారణీకరించమని అడగడంతో మొదలైన ఒక చిన్న చర్చ తర్వాత. రచయితలకు ఆ అడుగు మరో లక్ష్యం కోసం అవసరమైంది: Szemerédi ప్రతిపాదించిన ఒక గ్రాఫ్ సమస్య యొక్క ప్రేరిత (induced) రూపాంతరం, దాన్ని తర్వాతి ఒక నోట్‌లో ప్రకటిస్తామని వారు చెబుతున్నారు.

మోడల్ తన నిరూపణను “slice rank” భాషలో రాసింది. రచయితలు దాన్ని బహుపది పద్ధతి భాషలో తిరిగి రాశారు, అది పాఠకులకు సులభమని వారి అభిప్రాయం. ప్రతి ఫలితాన్నీ తాము ధృవీకరించామని, పూర్తి బాధ్యత తీసుకుంటామని వారు పేర్కొన్నారు, అలాగే నిరూపణ నిరూపణ-తనిఖీ సాఫ్ట్‌వేర్ అయిన Lean 4.35 లో ధృవీకరించబడిందని, ఆ ధృవీకరణను Palomar రిపోజిటరీలో పోస్ట్ చేస్తారని తెలిపారు.

ఇది పరిష్కరించనిది

రచయితలు ఆధారాన్ని ఇష్టతమం చేయడానికి ప్రయత్నించలేదు. మూడు రేకులకు, ఇది Naslund, Sawin 2017లో ఇచ్చిన సుమారు 1.89 హద్దును అధిగమించదు. ఇంకా బలమైన సోదర సమస్య, Erdős–Rado పొద్దుతిరుగుడు ఊహ, ఇంకా తెరిచే ఉంది: వారి హద్దులు ఇప్పటికీ బ్లాకు పరిమాణం D పై ఎక్కువగా ఆధారపడి ఉన్నాయి, ఆ సమస్య సరిగ్గా నిషేధించేది అదే.