సమీకరణాలను సాధించడానికి 1974 నాటి వేగ పరిమితి, చివరికి నిరూపితమైంది

ఒక ఫంక్షన్ f ఎక్కడ సున్నాను దాటుతుందో కనుగొనడానికి, కంప్యూటర్ తరచూ ఒక పునరావృతిని (iteration) నడుపుతుంది: ఒక ఊహ x నుంచి మొదలుపెట్టి, ఫంక్షన్‌ను కొన్ని ప్రశ్నలు అడిగి, మెరుగైన ఊహను లెక్కించి, మళ్లీ అదే చేస్తుంది. ఆ ప్రశ్నలు మూల్యాంకనాలు (evaluations): ఏదో ఒక బిందువు వద్ద f విలువ, లేదా దాని వాలు (అవకలజం, derivative) విలువ, లేదా ఉన్నత అవకలజం విలువ.

రెట్టింపయ్యే అంకెలు

అలాంటి పద్ధతి వేగాన్ని దాని క్రమం (order) ద్వారా కొలుస్తారు. ప్రస్తుత దోషం ε అయితే, p క్రమం ఉన్న పునరావృతి సుమారు ε యొక్క p ఘాతం అంత దోషాన్ని మిగులుస్తుంది. క్రమం 2 అంటే, సమాధానానికి దగ్గరగా, ప్రతి దశలో సరైన అంకెల సంఖ్య రెట్టింపవుతుంది; క్రమం 4 అంటే, అది నాలుగు రెట్లవుతుంది.

న్యూటన్ పద్ధతి ప్రతి దశకు రెండు మూల్యాంకనాలు ఖర్చు చేస్తుంది — f(x), దాని వాలు f′(x) — x − f(x)/f′(x)కు కదులుతుంది. దాని క్రమం 2. ప్రతి దశలో మరిన్ని ప్రశ్నలు అడగడం ద్వారా ఎక్కువ వేగం పొందవచ్చు. ఎంత అనేదే ప్రశ్న.

1974 నాటి ఒక ఊహ

1974లో, H. T. కుంగ్, J. F. ట్రాబ్ Journal of the ACMలోని ఒక పత్రంలో “Conjecture 8.1”గా ఒక సమాధానాన్ని ప్రతిపాదించారు: ప్రతి దశలో n మూల్యాంకనాలను వాడే జ్ఞాపకశక్తి లేని పునరావృతికి క్రమం గరిష్ఠంగా 2ⁿ⁻¹. “జ్ఞాపకశక్తి లేని” అంటే, ఆ పద్ధతి తన ప్రస్తుత ఊహ తప్ప మునుపటి దశల నుంచి ఏదీ నిలుపుకోదు.

ఆ హద్దును తగ్గించడం సాధ్యం కాదు: ప్రతి n ≥ 2కు 2ⁿ⁻¹ను చేరుకునే “బహుబిందు” (multipoint) పద్ధతులను కుంగ్, ట్రాబ్ స్వయంగా నిర్మించారు — మూడు మూల్యాంకనాలతో క్రమం 4, నాలుగుతో 8, ఐదుతో 16. లోపించింది మిగతా సగం: ఏ పద్ధతీ ఇంతకంటే మెరుగ్గా చేయలేదనే నిరూపణ. పాక్షిక ఫలితాలు ఆ ఊహతో పాటే, దాని తర్వాతా వచ్చాయి. అంతర్వేశనం (interpolation) ఆధారిత పద్ధతులకు, రెండు మూల్యాంకనాలతో పనిచేసే అకరణీయ (rational) పద్ధతులకు, వివిధ అదనపు షరతుల కింద ఈ హద్దు నిరూపితమైంది; ఫంక్షన్ విలువలను మాత్రమే వాడే పద్ధతులకు, బలహీనమైన 2ⁿ హద్దు స్థాపించబడింది. సాధారణ సందర్భం తెరిచే ఉండిపోయింది.

అల్గారిథమ్‌ను మోసం చేయడం

కేంబ్రిడ్జ్ విశ్వవిద్యాలయపు అనువర్తిత గణితం, సైద్ధాంతిక భౌతికశాస్త్ర విభాగానికి చెందిన మాథ్యూ కాల్‌బ్రూక్ ఇప్పుడు దాన్ని పూర్తిగా నిరూపించారు. ఈ నమూనా ఉద్దేశపూర్వకంగా అల్గారిథమ్‌కు ఉదారంగా ఉంటుంది. అది ముందుకు సాగుతూ ఎక్కడ మూల్యాంకనం చేయాలో, ఏ అవకలజాలను తీసుకోవాలో ఎంచుకోవచ్చు. తనకు నచ్చిన ఏ నిర్ధారిత (deterministic) పద్ధతిలోనైనా సమాధానాలను ప్రాసెస్ చేయవచ్చు, దాని నియమాలకు ఎలాంటి నునుపుదనమూ (smoothness) అవసరం లేదు.

నిరూపణ అల్గారిథమ్ సొంత నిర్ధారితత్వాన్నే దానికి వ్యతిరేకంగా తిప్పుతుంది. దాని అన్ని ప్రశ్నలకూ సరిగ్గా అవే సమాధానాలు ఇచ్చే, కానీ వేర్వేరు సున్నాలు ఉన్న రెండు ఫంక్షన్లను నిర్మించండి. అల్గారిథమ్ రెండింటికీ ఒకే ఊహను ఇవ్వాలి, కాబట్టి వాటిలో ఒకదానిపై అది రెండు సున్నాల మధ్య దూరంలో కనీసం సగం తప్పుతుంది.

అలాంటి జంటలను కనుగొనడానికి, కాల్‌బ్రూక్ ఒక సూచన ఫంక్షన్‌ను గరిష్ఠంగా n పరిమాణం (degree) ఉన్న ఒక చిన్న బహుపదితో (polynomial) కొద్దిగా కదిలిస్తారు; దానికి n + 1 సర్దుబాటు చేయగల గుణకాలు ఉంటాయి. ప్రతి మూల్యాంకనం వాటిలో గరిష్ఠంగా ఒక సంయోజనాన్ని మాత్రమే స్థిరపరుస్తుంది, కాబట్టి n ప్రశ్నల తర్వాత కొన్ని కదలికలు అల్గారిథమ్‌కు కనిపించకుండా మిగులుతాయి. ఆ లెక్క ఒక్కటే చాలదు: కనిపించని ఒక కదలిక సున్నాను అతి కొద్దిగా మాత్రమే కదిలించవచ్చు.

కీలక సాధనం వ్రాన్‌స్కియన్ (Wronskian) — బహుపదుల ఒక కుటుంబం, వాటి అవకలజాల నుంచి నిర్మించే ఒక నిర్ధారకం (determinant). ఒక కొత్త లెమ్మా ఇలా చెబుతుంది: కుటుంబంలోని ఒక బహుపదికి ఒక చిన్న వృత్తంలో అనేక సున్నాలు కిక్కిరిసి ఉంటే, ఆ కుటుంబపు వ్రాన్‌స్కియన్ దగ్గరలో ఎక్కడో సున్నా కావాలి. ఈ కొన్ని బిందువులకు దూరంగా సున్నా ఉండే ఫంక్షన్‌తోనే ఎప్పుడూ అల్గారిథమ్‌కు సమాధానం ఇవ్వడం ద్వారా, నిరూపణ సున్నా స్వేచ్ఛగా కదిలేలా ఉంచుతుంది.

లెక్కల పద్దు ఘాతాంకాన్ని ఇస్తుంది. సున్నా నుంచి ε దూరంలో మొదలుపెడితే, సాధ్యమైన సున్నాలు కనీసం ε యొక్క ఒక ఘాతానికి ఒక స్థిరాంకం రెట్లు ఉన్న పరిధిలో విస్తరించి ఉంటాయి. రచయిత మాటల్లో, “మొదటి పరిశీలన తర్వాత ఘాతాంకం ఒకటిగానే ఉండి, ఆ తర్వాత రెట్టింపవుతుంది, n పరిశీలనల తర్వాత 2ⁿ⁻¹ ఇస్తుంది.”

ప్రతి స్థాయికీ ఒకే ఫంక్షన్

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

ఆ పరిమితి ఒక సంపూర్ణ ఫంక్షన్ (entire function) — సంకీర్ణ సంఖ్యలపై (complex numbers) కూడా అన్నిచోట్లా నునుపుగా ఉండేది — వాస్తవ రేఖపై దాని వాలు 3/4, 5/4 మధ్య ఉంటుంది: ఒకే ఒక చక్కగా ప్రవర్తించే సున్నా ఉన్న, స్థిరంగా పైకి లేచే వక్రరేఖ. 2ⁿ⁻¹ కంటే ఎక్కువైన ఏ pకైనా, పద్ధతి దానిపై p క్రమాన్ని చేరుకోలేదు. కాబట్టి n ≥ 2కు జ్ఞాపకశక్తి లేని ఉత్తమ క్రమం సరిగ్గా 2ⁿ⁻¹. మూల్యాంకనాలు సంకీర్ణ సంఖ్యలైనప్పుడు కూడా పత్రం ఇదే హద్దును నిరూపిస్తుంది.

అన్నీ ఒకేసారి అడిగే మూల్యం

మరింత పదునైన ఒక ప్రకటన సమూహాలుగా చేసే మూల్యాంకనాలను వర్తిస్తుంది; ఇక్కడ ఒక సమూహంలోని ప్రతి ప్రశ్నా, దాని సమాధానాల్లో ఏదీ రాకముందే ఎంచుకోబడుతుంది — సమాంతర పద్ధతుల పరిస్థితి ఇది. ℓ₁, …, ℓₖ పరిమాణాల సమూహాలతో, క్రమం గరిష్ఠంగా ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1). n ప్రశ్నలన్నీ ఒకేసారి అడిగితే క్రమం nకు పరిమితమవుతుంది; వాటిని ఒక్కొక్కటిగా అడిగితే 2ⁿ⁻¹ సాధ్యమవుతుంది. ఐదు మూల్యాంకనాలతో, అది 16తో పోలిస్తే 5.

యంత్రం తనిఖీ చేసింది

ఫలితాలు ప్రతి తార్కిక దశనూ తనిఖీ చేసే నిరూపణ సహాయకమైన లీన్‌లో (Lean) లాంఛనంగా ధ్రువీకరించబడ్డాయి. కోడ్ బహిరంగంగా అందుబాటులో ఉంది, పాలోమార్ రిజిస్ట్రీలో నమోదైంది. లీన్ లాంఛనీకరణ ChatGPT 6 సహాయంతో జరిగిందని, ఆ తర్వాత Lean 4 Comparatorతో పత్రంలోని సిద్ధాంతాలకు వ్యతిరేకంగా తనిఖీ చేయబడిందని, ప్రతి వాదనను రచయిత స్వయంగా సమీక్షించారని, విషయానికి పూర్తి బాధ్యత రచయితదేనని రచయిత పేర్కొన్నారు.

ఈ పరిమితి మరచిపోయే పద్ధతులకు సంబంధించినది. తమ మునుపటి దశలను తిరిగి వాడుకోగల పద్ధతులు వేరే హద్దులకు లోబడి ఉంటాయి; ఈ పత్రం వాటిని పక్కన పెడుతుంది.