HUJJAR AI, AN SAKE ZANA TA DOMIN MUTANE

Zana wasu ɗigo sannan ka haɗa wasu daga cikinsu da layuka. Masana lissafi suna kiran wannan graph; ɗigon su ne vertices (ƙulli), layukan su ne edges (gefe), kuma yawan layukan da ke taɓa ɗigo shi ne degree ɗinsa (mataki). Bishiya (tree) graph ce mara zobe wadda ke haɗe a guntu ɗaya, kamar ɗan reshe mai rassa; bishiya mai ɗigo t koyaushe tana da layuka t − 1.

A farkon shekarun 1960, Paul Erdős da Vera T. Sós sun yi wata tambaya mai sauƙi: layuka nawa ne ke tilasta wa graph ta ƙunshi kowace bishiya ta wani girma? Amsarsu, hasashen Erdős–Sós (Erdős–Sós conjecture), ita ce:

Idan graph tana da matsakaicin degree fiye da t − 2, tana ƙunshe da kowace bishiya mai vertices t.

Iyakar tana da kaifi. Ɗauki kwafe daban-daban na cikakkiyar graph mai ɗigo t − 1, kowane biyu a haɗe: kowane ɗigo yana da maƙwabta daidai t − 2, amma babu guntu da ya isa girma don ɗaukar bishiya mai ɗigo t. Wahalar tana cikin kalmar matsakaici. Idan kowane ɗigo ɗaya-ɗaya yana da aƙalla maƙwabta t − 1, mutum zai iya ɗora bishiya reshe bayan reshe ba tare da wata matsala ba. Amma matsakaici ba ya faɗin komai game da kowane ɗigo ɗaya: wasu na iya samun ɗaruruwan maƙwabta, wasu kuma kusan babu.

Shekaru sittin na amsoshi rabi-rabi

A cewar tarihin da aka bayar a takardar, matsalar ta samo asali ne daga 1962–1964 kuma ta zama babba a reshen lissafi da ke nazarin yawan edges da ke tilasta wani tsari. An warware wasu lamura na musamman: taurari, hanyoyi, taurari biyu-biyu, bishiyoyi masu ƙananan rassa. A farkon shekarun 1990, masana lissafi huɗu — Ajtai, Komlós, Simonovits da Szemerédi — sun sanar da hujja ga manyan bishiyoyi sosai, amma takardun baya-bayan nan sun lura cewa ba a taɓa wallafa cikakken rubutu ba. Ƙarin sakamako na rabi-rabi sun iso a 2021, 2024 da 2026. A ranar 4 ga Satumba 2026, Reed da Stein sun wallafa hujja ga manyan graph masu yawan haɗi, wadda suka ce an samar da ita ba tare da AI ba.

Sannan wani rahoto ya zo. A watan Satumba 2026, Tom Adamczewski da Thomas Bloom, a wani takarda da ake kira FrontierMath Erdős, sun danganta hujjar dukan hasashen ga wani nau’in samfurin AI da ba a fitar ba tukuna, GPT-6 Astra. Asalin hujjar ƙidayar a fili take, kuma wani ma’ajiyar bayanai da ke tare da ita yana rubuta binciken hujjar da AI ɗin ya yi da kansa da kuma tabbatarwa ta tsari a harshen duba hujjoji na Lean. Marubutan rahoton sun kuma yi kira ga ƙwararrun mutane su rubuta cikakkun bayanai na gargajiya.

Bayyana graph ɗigo ɗaya bayan ɗaya

Jay Cummings, na Jami’ar Jihar California, Sacramento, ya amsa wannan kira. Labarinsa mai shafi 27 ya riƙe babbar hujjar ƙidaya ta AI ɗin amma ya canza yadda ake ba da labarinta:

1. Bayyana graph a hankali. Jera vertices a wani tsari sannan ka bayyana su ɗaya bayan ɗaya, tare da edges da ke tsakanin waɗanda aka riga aka nuna.
2. Nemi fiye da haka. Maimakon kowace kwafin bishiyar, nemi wadda “tushenta” da aka zaɓa ke kan vertex na farko daidai. Neman fiye da haka yana sauƙaƙa hujjar.
3. Ƙidaya maƙwabta na farko. Waɗannan su ne maƙwabtan vertex na farko da suka bayyana kafin irin wannan kwafi ta bayyana. Tara su a kowane tsari mai yiwuwa.
4. Ƙayyade jimillar. Ta hanyar musanyar vertices ko dukan ɓangarorin tsarin — motsin da kullum za a iya mayar da su — Cummings ya nuna cewa, a matsakaici a kan dukan tsare-tsare, maƙwabta na farko ba sa wuce t − 2.

Mataki na ƙarshe gajere ne. Idan graph ba ta ƙunshi kwafin bishiyar ba, kowane maƙwabcin vertex na farko zai zama na farko, a kowane tsari. A matsakaici a kan dukan tsare-tsare, wannan daidai yake da matsakaicin degree — wanda bisa zato ya wuce t − 2. Saɓani: dole bishiyar ta kasance a ciki.

Hujjar tana amfani ne kawai da jimillar degrees, ba yadda aka rarraba su ba. Cummings kuma ya ba da nau’in hujja na yiwuwa (probabilistic), kuma ya warware misalan bishiyoyi masu vertices huɗu da biyar a kan graph na zahiri.

Littafin hotuna na hujja

Labarin yana ɗauke da hotuna 32. Yana ƙarewa da wani sakamako na gargajiya: yi wa dukan layukan cikakkiyar graph launi da launuka q, kuma launi ɗaya koyaushe zai ƙunshi wata bishiya da aka bayar da zarar graph ta kai vertices q(t − 2) + 2. A wata sanarwa ta ƙarshe, Cummings ya bayyana cewa ya samar da rubutun ne a cikin doguwar tattaunawa da ChatGPT, cewa sababbin ra’ayoyin gabatarwa — maƙwabta na farko, rarrabuwa a fili, zane-zane — nasa ne, kuma ya duba komai kuma ya ɗauki cikakken alhaki.

Ya kwatanta bayaninsa da wasu na baya-bayan nan na Riordan da Scott, Wood da Frederickson, kuma ya lura cewa an riga an faɗaɗa hanyar zuwa hanyoyin sadarwa masu alkibla da kuma “hypergraphs”, wasu daga cikin waɗannan faɗaɗawa ma an danganta su ga GPT-6 Astra. Gudummawarsa, kamar yadda ya rubuta, ita ce “bayani na gani na hujjar da aka mayar da hankali kan mai karatu, ba sabon warware hasashen ba.”