22 గుణకారాలు, ఒక్కటి కూడా తక్కువ కాదు

ప్రయోజన సంఘర్షణ. ఏఐ ఏజెంట్లు — Anthropic కు చెందిన Claude — తమ మార్గదర్శకత్వంలో శోధన కోడ్‌ను, మానవ తనిఖీదారు అవసరం లేని Lean నిరూపణలను రాశాయని, మనిషి తప్పనిసరిగా తనిఖీ చేయాల్సిన భాగాన్ని తామే రూపొందించామని రచయితలు పేర్కొన్నారు. ఈ వ్యాసాన్ని కూడా Claude రాసింది.

రెండు చతురస్ర సంఖ్యల జాలకాలను — మాత్రికలను — బడిలో నేర్పే పద్ధతిలో గుణించాలంటే, n వరుసలు, n నిలువు వరుసలు ఉన్న జాలకాలకు n³ గుణకారాలు పడతాయి. స్ట్రాసెన్ (Strassen) రెండు 2 × 2 మాత్రికలను 8కి బదులు 7 గుణకారాలతో గుణించవచ్చని చూపించారు. ఈ చిట్కాను పునరావృతంగా వాడవచ్చు: పెద్ద మాత్రికను నాలుగు ఖండాలుగా కోసి, ప్రతి ఖండాన్ని ఒకే సంఖ్యలా పరిగణించి, మళ్లీ మళ్లీ చేయండి. అప్పుడు ఖర్చు n³కి బదులు n^2.807 లాగా పెరుగుతుంది. పరిశోధనా పత్రం ప్రకారం, ఈ 2 × 2 విధానం 1971లో సర్వోత్తమమని నిరూపించబడింది.

అదే ఆలోచన ఏ స్థిర పరిమాణానికైనా పనిచేస్తుంది. రెండు 3 × 3 మాత్రికలను r గుణకారాలతో గుణించే, అంశాలు ఖండాలైనా పనిచేసే విధానం, n యొక్క log₃ r ఘాతం లాగా పెరిగే ఖర్చును ఇస్తుంది. సరళమైన అంకగణితం పణంగా ఉన్నదేమిటో చెబుతుంది: అలాంటి విధానం r 21 లేదా అంతకంటే తక్కువ అయినప్పుడు మాత్రమే స్ట్రాసెన్‌ను అధిగమిస్తుంది, 22 లేదా అంతకంటే ఎక్కువ అయితే ఓడిపోతుంది. తెలిసిన అత్యుత్తమ 3 × 3 విధానం, లాడర్మన్ (Laderman)ది, 23 గుణకారాలను వాడుతుంది, 1976 నుంచి మెరుగుపడలేదు.

సగం తెరిచి ఉన్న తలుపు

ఇచ్చిన సమస్యకు సాధ్యమైన అత్యుత్తమ సంఖ్యను దాని ర్యాంక్ (rank) అంటారు. 3 × 3 గుణకారపు ర్యాంక్‌కు దిగువ హద్దులు నెమ్మదిగా పెరిగాయి: 2003లో 19, తర్వాత మార్చి 2026లో 20; దీనిని వాంగ్ కేవలం 0, 1 మాత్రమే ఉండి 1 + 1 = 0 అయ్యే ఒక చిన్న సంఖ్యా వ్యవస్థపై లెక్కించారు. సెప్టెంబర్ 2026లో, వాంగ్, యాంగ్ నేతృత్వంలోని ఒక బృందం స్వతంత్రంగా, ఒకదానికొకటి పది రోజుల వ్యవధిలో 21కి చేరాయి. కానీ 21 వద్ద కూడా స్ట్రాసెన్ కంటే వేగవంతమైన 3 × 3 విధానానికి చోటు మిగిలే ఉంది.

పాలిటెక్నిక్ మాంట్రియల్, కార్నెగీ మెలన్ యూనివర్సిటీకి చెందిన ఐజాక్ రుడిచ్, పాలిటెక్నిక్ మాంట్రియల్‌కు చెందిన లూయీ-మార్టిన్ రూసో ఇప్పుడు ఆ హద్దును 22కి నెట్టారు.

సిద్ధాంతం 1. పూర్ణాంక స్థిరాంకాలతో రెండు 3 × 3 మాత్రికలను గుణించే, ఏ పరిమాణం ఉన్న ఖండాలకైనా పునరావృతంగా వర్తింపజేయగల ఏ అల్గారిథమ్ అయినా కనీసం 22 గుణకారాలను వాడుతుంది.

కాబట్టి అలాంటి ఏ అల్గారిథమ్ కూడా సుమారు n^2.814 కంటే మెరుగ్గా చేయలేదు — ఏదీ స్ట్రాసెన్ 2 × 2 పద్ధతిని అధిగమించలేదు.

496 చిన్న పజిళ్లు

నిరూపణ వాంగ్ రూపొందించిన ఒక పట్టికపై ఆధారపడుతుంది, అది కఠినమైన సమస్యను 496 సులభమైన సమస్యలుగా విభజిస్తుంది. ప్రతి సమస్య మొదటి మాత్రికపై “షరతులు” జోడిస్తుంది — ఉదాహరణకు, దానిలోని కొన్ని అంశాల మొత్తం సున్నా. ఎన్ని ఎక్కువ షరతులు ఉంటే సమస్య అంత సులభం, మాత్రిక మొత్తం సున్నాలే అయిన అల్పమైన సందర్భం వరకు.

రచయితలు మొదట ఒక కచ్చితమైన శోధన ప్రోగ్రామ్‌ను నిర్మించారు, అది ప్రతి పజిల్ నిజమైన జవాబును, దానిని నిరూపించడానికి ప్రయత్నించడానికి ముందే వారికి చెప్పింది. ఆ జవాబులు ఒక పటంలా పనిచేశాయి: ఏ దిగువ హద్దుల వెంట పడటం విలువైనదో అవి చూపించాయి. చివరికి, వారి నిరూపణ మొత్తం 496 పజిళ్లకు హద్దులు ఇస్తుంది, వాటిలో 359ని కచ్చితంగా పరిష్కరిస్తుంది — వాంగ్ తాజా ఫలితాల్లోని 195తో పోలిస్తే — 252కి దిగువ హద్దును పెంచుతుంది. వారి సొంత “అతికింపు” సిద్ధాంతం రెండు సులభమైన పజిళ్ల విధానాలను కలిపి మూడో దానికి విధానాన్ని తయారుచేస్తుంది, ఎగువ హద్దుల్లో 145ని అది అందించింది.

తుది ప్రకటనలో రెండు షరతులు ముఖ్యం. పూర్ణాంక స్థిరాంకాలు: పూర్ణాంక స్థిరాంకాలు ఉన్న విధానాన్ని 0-1 సంఖ్యా వ్యవస్థలో చదివినా, అది అదనపు గుణకారాలు లేకుండానే చెల్లుబాటయ్యే విధానంగా ఉంటుంది, కాబట్టి హద్దు బదిలీ అవుతుంది. ఖండాలు: ఆ అవసరం లేకపోతే, అడ్డదారులు ఉన్నాయి. పత్రం ఉదహరించిన రోసోవ్స్కీ 3 × 3 అల్గారిథమ్‌కు కేవలం 21 గుణకారాలు చాలు, కానీ అది సంఖ్యలు స్థానమార్పిడి (commute) చేసుకోవడంపై ఆధారపడుతుంది, పునరావృతంగా వర్తింపజేయలేం.

యంత్రం తనిఖీ చేసిన నిరూపణ

నిరూపణ Leanలో రాయబడింది; ఇది ఒక ప్రోగ్రామింగ్ భాష, ఇందులో ప్రతి అడుగూ ధృవీకరించబడితేనే సిద్ధాంతం కంపైల్ అవుతుంది. పూర్తి నిరూపణ 3,521 మాడ్యూళ్లలో విస్తరించిన సుమారు పది లక్షల పంక్తులు, ఒకే ప్రాసెసర్ కోర్‌పై తనిఖీ చేయడానికి 11.1 గంటలు పడుతుంది. ఎవరూ దానినంతా చదవాల్సిన అవసరం లేదు. తనిఖీదారు సుమారు 1,000 పంక్తుల ఒక లైబ్రరీని చదువుతారు; ఏ నిరూపణా ఉనికిలోకి రాకముందే రచయితలు రాసిన ఇది, గుణకార విధానం అంటే ఏమిటో నిర్వచించి, సిద్ధాంతాన్ని పేర్కొంటుంది; మిగతాదంతా Lean కెర్నల్ తనిఖీ చేస్తుంది, ఒక స్వతంత్ర తనిఖీ సాధనం ఫలితాన్ని మళ్లీ నడిపి చూడగలదు.

ఏఐ ఏజెంట్లు సాహిత్యాన్ని శోధించాయని కూడా రచయితలు పేర్కొంటున్నారు: ప్రతి ఉల్లేఖనం ఉనికిలో ఉందని అవి తనిఖీ చేశాయి, “కానీ మేము దానికి ఆపాదించే ఆలోచన ప్రతిదానిలోనూ సరిగ్గా ఉందో లేదో కాదు.”

చివరి అంతరం

ఒక ప్రశ్న మిగిలి ఉంది: 22 గుణకారాలతో 3 × 3 విధానం ఉందా, లేక లాడర్మన్ 23యే నిజమైన కనిష్ఠమా? ఈ అంతరం “అతి త్వరలో మూసుకుపోతుందని” రచయితలు ఆశిస్తున్నారు; అది జరిగినప్పుడు, లేదా పత్రం ప్రచురణకు ఆమోదం పొందినప్పుడు, వారు తమ శోధన కోడ్‌ను విడుదల చేస్తారు. ఈ హద్దు పూర్ణాంకేతర స్థిరాంకాలు ఉన్న విధానాలను కూడా పక్కన పెడుతుంది.