HASASHEN FURE MAI KAMA DA RANA (SUNFLOWER) YA RUSHE

Ka ɗauki lambobi daga 1 zuwa n kuma ka duba dukkan hanyoyin zaɓar wasu daga cikinsu: akwai 2ⁿ irin waɗannan ƙananan tarin (subsets). Yanzu ka zaɓi wasu ƙananan tarin da ke raba ɓangare ɗaya na gama-gari daidai, ba komai kuma. Masana lissafi suna kiran wannan sunflower: ɓangaren da aka raba shi ne tsakiya (core), kuma abin da ya rage daga kowane tarin ganyen fure ne da ba ya taɓa wani ganye.

Sunflowers kayan aiki ne na asali na combinatorics. Takardar ta lissafa alaƙa da iyakokin wasu da’irorin logic, da matsalar “cap set”, da ninka matrices mai sauri da kuma ka’idar bayanai (information theory).

Tambaya daga 1970

Tambayar da ta fi dacewa game da su ta samo asali, a cewar marubutan, daga wata takarda ta 1970 ta Paul Erdős. Yaya girman tarin ƙananan tarin {1, …, n} zai iya kasancewa idan babu k daga cikin tarinsa da suka zama sunflower?

A shekarun 1970, Erdős da Endre Szemerédi sun yi hasashen cewa irin wannan tarin dole ya kasance ƙarami ta hanyar exponential fiye da ƙananan tarin 2ⁿ da za a iya samu: cⁿ a mafi yawa, ga wata lamba c da ke ƙasa da 2 ba tare da shakka ba.

Shekaru da dama, mafi kyawun iyakoki sun ɗan rage kaɗan ne kawai, ba su taɓa isa su kawo tushen ƙasa da 2 ba. Yanayin ganye uku (k = 3) kawai aka warware, a 2016, ta hanyar babban ci gaban da aka samu a matsalar cap set da kuma wata ragewa ta Alon, Shpilka da Umans.

Iyakar

Matija Bucić da Fankang He (Jami’ar Vienna) da Hyunwoo Lee (KAIST da Institute for Basic Science, Koriya ta Kudu) sun tabbatar da hasashen ga kowane k ≥ 3. Babban theorem ɗinsu: tarin da ba shi da sunflower mai ganye k yana da a mafi yawa

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

mambobi. Tushen yana ɗan ƙasa da 2, amma lamba ce tsayayya ƙasa da 2, kuma wannan shi ne daidai abin da Erdős da Szemerédi suka nema. Wani gini na 1997 ya nuna cewa, ga babban k, gaskiyar ba za ta iya yin ƙasa sosai da haka ba.

Daga tarin zuwa vectors

Hujjar tana bi ta wata sigar matsalar da vectors. A raba lambobin zuwa tubala n na abubuwa D kuma a zaɓi abu ɗaya a kowane tubali: kowane zaɓi vector ne. Vectors da yawa suna zama sunflower lokacin da, a kowane matsayi, abubuwan da ke cikinsu ko dai duka daidai suke ko duka daban suke.

Daga nan marubutan suka gina wani “mai gwajin sunflower”: wani function da, a kan tarin da babu sunflower a ciki, ba sifili ba ne sai lokacin da dukkan abubuwan da aka shigar vector ɗaya ne. Sabon sinadarin shi ne rubuta wannan function, mataki-mataki, da interpolation polynomials masu ƙaramin degree. Ƙirga waɗannan polynomials yana iyakance girman tarin (Theorem 2 ɗinsu). Wata hujja ta yiwuwa (probabilistic), tubala na bazuwar da aka yi matsakaicinsu a kan dukkan girman tarin, tana mayar da iyakar zuwa tarin na yau da kullum.

Na’ura ce ta same shi, wata ta duba shi

Bayanin takardar game da AI a bayyane yake fiye da yadda aka saba. ChatGPT 6 Astra Pro ne ya sami hujjar Theorem 2, bayan wata gajeriyar tattaunawa da ta fara da roƙon sa ya faɗaɗa sananniyar hujjar ganye uku. Marubutan sun buƙaci wannan matakin don wata manufa daban: wata sigar induced ta wata matsalar graph da Szemerédi ya gabatar, wadda suka sanar za su wallafa a wata takarda ta gaba.

Samfurin ya rubuta hujjarsa a harshen “slice rank”. Marubutan sun sake rubuta ta a harshen hanyar polynomial (polynomial method), wadda suke ganin ta fi sauƙi ga masu karatu. Sun bayyana cewa sun tabbatar da kowane sakamako kuma suna ɗaukar cikakken alhaki, kuma an tabbatar da hujjar a Lean 4.35, wata manhajar duba hujja, kuma za a wallafa tabbatarwar a rumbun Palomar.

Abin da ba ta warware ba

Marubutan ba su yi ƙoƙarin inganta tushen ba. Ga ganye uku, ba ta doke iyakar 2017 ta Naslund da Sawin ba, kusan 1.89. Kuma matsalar ’yar’uwa mafi ƙarfi, hasashen sunflower na Erdős–Rado, har yanzu a buɗe take: iyakokinsu har yanzu sun dogara sosai ga girman tubali D, wanda shi ne daidai abin da wannan matsalar ta hana.