DHANIA YA ALIZETI YAANGUKA

Chukua namba kutoka 1 hadi n na uangalie njia zote za kuchagua baadhi yake: kuna seti ndogo 2ⁿ za aina hiyo. Sasa chagua seti ndogo chache zinazoshiriki sehemu ileile ya pamoja hasa, na hakuna kingine. Wanahisabati huita hii alizeti (sunflower): sehemu ya pamoja ni kiini, na kinachobaki katika kila seti ni petali isiyogusa petali nyingine yoyote.

Alizeti ni chombo cha msingi cha kombinatoria. Makala inaorodhesha uhusiano na mipaka ya baadhi ya saketi za mantiki, na tatizo la “cap set”, na uzidishaji wa haraka wa matriki na nadharia ya taarifa.

Swali kutoka mwaka 1970

Swali la asili zaidi kuzihusu linarudi, kwa mujibu wa waandishi, kwenye makala ya mwaka 1970 ya Paul Erdős. Mkusanyiko wa seti ndogo za {1, …, n} unaweza kuwa mkubwa kiasi gani ikiwa hakuna k kati ya seti zake zinazounda alizeti?

Katika miaka ya 1970, Erdős na Endre Szemerédi walidhania kwamba mkusanyiko kama huo lazima uwe mdogo zaidi kwa kipeo kuliko seti ndogo 2ⁿ zinazowezekana: zisizozidi cⁿ, kwa namba fulani c iliyo chini kabisa ya 2.

Kwa miongo kadhaa, mipaka bora ilipunguza kidogo tu, kamwe haikutosha kushusha msingi chini ya 2. Ni hali ya petali tatu pekee (k = 3) iliyotatuliwa, mwaka 2016, kupitia mafanikio makubwa kuhusu tatizo la cap set na upunguzaji uliofanywa na Alon, Shpilka na Umans.

Kikomo

Matija Bucić na Fankang He (Chuo Kikuu cha Vienna) na Hyunwoo Lee (KAIST na Taasisi ya Sayansi ya Msingi, Korea Kusini) wanathibitisha dhania hiyo kwa kila k ≥ 3. Nadharia yao kuu: mkusanyiko usio na alizeti yenye petali k una wanachama wasiozidi

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

Msingi uko chini kidogo tu ya 2, lakini ni namba isiyobadilika iliyo chini ya 2, na hicho ndicho hasa Erdős na Szemerédi walichoomba. Muundo mmoja wa mwaka 1997 unaonyesha kwamba, kwa k kubwa, thamani halisi haiwezi kuwa chini zaidi sana.

Kutoka seti hadi vekta

Uthibitisho unapitia toleo la tatizo linalotumia vekta. Gawanya namba katika vitalu n vyenye elementi D kila kimoja na uchague elementi moja katika kila kitalu: kila chaguo ni vekta. Vekta kadhaa huunda alizeti pale ambapo, katika kila nafasi, viingizo vyake ama vyote ni sawa ama vyote ni tofauti.

Kisha waandishi wanaunda “kipimaji cha alizeti”: kitendakazi ambacho, juu ya mkusanyiko usio na alizeti, si sifuri isipokuwa tu pale ambapo viingizo vyake vyote ni vekta ileile. Kiungo kipya ni kuandika kitendakazi hiki, hatua kwa hatua, kwa polinomia za uchopekaji (interpolation) za daraja la chini. Kuhesabu polinomia hizo kunaweka kikomo kwa ukubwa wa mkusanyiko (Nadharia yao ya 2). Hoja ya kiuwezekano, ya vitalu nasibu vilivyowekewa wastani juu ya ukubwa wote wa seti, inarudisha kikomo hicho kwa seti za kawaida.

Kimegunduliwa na mashine, kimehakikiwa na nyingine

Kauli ya makala kuhusu AI ni ya wazi kwa namna isiyo ya kawaida. Uthibitisho wa Nadharia ya 2 uligunduliwa na ChatGPT 6 Astra Pro, baada ya mazungumzo mafupi yaliyoanza kwa kuiomba ijumlishe hoja inayojulikana ya petali tatu. Waandishi walihitaji hatua hiyo kwa lengo jingine: toleo lililochochewa (induced) la tatizo la grafu lililoulizwa na Szemerédi, ambalo wanatangaza kwa ajili ya makala fupi ya baadaye.

Modeli iliandika uthibitisho wake kwa lugha ya “slice rank”. Waandishi waliuandika upya kwa lugha ya mbinu ya polinomia, ambayo wanaiona rahisi zaidi kwa wasomaji. Wanasema walihakiki kila tokeo na wanabeba jukumu kamili, na kwamba uthibitisho umehakikiwa katika Lean 4.35, programu ya kukagua uthibitisho, huku uhakiki huo ukitarajiwa kuwekwa kwenye hazina ya Palomar.

Kisichotatuliwa

Waandishi hawakujaribu kuboresha msingi. Kwa petali tatu, haupiti kikomo cha mwaka 2017 cha Naslund na Sawin, takriban 1.89. Na tatizo dada lenye nguvu zaidi, dhania ya alizeti ya Erdős–Rado, bado liko wazi: mipaka yao bado inategemea sana ukubwa wa kitalu D, ambacho ndicho hasa tatizo hilo linakataza.