ADADI MAFI GIRMA DA BA ZA KA IYA BIYA BA, YANZU AN SA MASA IYAKA MAI MATSEWA

Ka yi tunanin wani akwatin kuɗi da ke karɓar ’yan nau’ikan tsabar kuɗi kaɗan kawai, ba tare da iyaka a yawansu ba, kuma ba ya taɓa ba da canji. Wasu adadi ana iya biyan su daidai; wasu kuma ba za a taɓa iya ba. Masana lissafi suna kiran ƙimomin tsabar kuɗin generators, kuma suna yin wata tambaya mai kama da sauƙi: menene adadi mafi girma da ba za a iya biya ba?

Adadin da ba za a taɓa iya biya ba

Ɗauki lambobi cikakku a₁ < a₂ < … < aₙ da babu wani abin raba (factor) da dukansu suke da shi. Jimillar da aka samu ta hanyar haɗa waɗannan lambobi, kowanne sau nawa ka ga dama, ana kiranta “mai yiwuwar wakilci” (representable). Lambobi cikakku kaɗan ne kawai (finitely many) ba haka suke ba; mafi girma cikinsu shi ne lambar Frobenius (Frobenius number), F. (Idan ɗaya daga cikin ƙimomin 1 ne, ana iya biyan komai kuma ana sa F ya zama −1.)

Ƙaramin misali: da tsabar kuɗi na 3, 4 da 6, za ka iya biyan 3, 4, 6, 7, 8 da kowane adadi bayan haka, amma ba za ka taɓa iya biyan 1, 2 ko 5 ba. Don haka F = 5. Lura cewa 3 da 6 suna da abin raba ɗaya; abin da ke da muhimmanci shi ne babu abin raba da ke tsakanin dukansu uku.

Ga tsabar kuɗi biyu akwai amsa ta ainihi, dabarar Sylvester: F(a₁, a₂) = a₁a₂ − a₁ − a₂. Ga uku ko fiye, aikin shi ne sa wa F iyaka: tabbatar da cewa ba zai iya wuce wata ƙima da aka lissafa daga tsabar kuɗin ba.

Ninki 2 mai taurin kai

Paul Erdős da Ronald Graham sun tabbatar, ga generators uku ko fiye:

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

A nan aₙ ita ce ƙima mafi girma, aₙ₋₁ ta biyu mafi girma, n yawan ƙimomin, kuma ⌊ ⌋ tana nufin zagaye zuwa ƙasa. Kamar dabarar Sylvester, ta ƙunshi tsabar kuɗi biyu mafiya girma.

Sun kuma yi ƙiyasin mafi munin yanayi, F mafi girma da zai yiwu idan dukan ƙimomin n ba su wuce t ba. Giɓin da ke tsakanin ƙiyasinsu, kusan ninki 2, ya kai ga wani hasashe (conjecture) da aka rubuta a matsayin Erdős Problem #433. Jacques Dixmier ya warware shi, kuma ya tabbatar da wata iyaka mafi sauƙi da ke aiki ga kowane rukuni: F ≤ aₙ²/(n − 1). Ninki 2 ya tafi, amma tsabar kuɗi ta biyu mafi girma ma ta tafi.

Riƙe tsabar kuɗi biyu mafiya girma

Lin Chen, Tingwei Hu, Yuchen Mao da Guochuan Zhang, na College of Computer Science and Technology a Zhejiang University, sun so duka biyun: babu ninki 2, kuma a riƙe tsabar kuɗi ta biyu mafi girma. Amsarsu, mai aiki ga kowane rukuni na ƙimomi biyu ko fiye:

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

A nan ⌈ ⌉ tana nufin zagaye zuwa sama. Idan aka kwatanta da ta Erdős da Graham, ninki 2 ya ɓace, a kan farashin raba da n − 1 maimakon n da kuma zagaye zuwa sama. Idan aka kwatanta da ta Dixmier, sabuwar iyakar za ta iya zama ƙarama sosai idan tsabar kuɗi ta biyu mafi girma ƙarama ce idan aka kwatanta da mafi girma.

A misalin 3, 4, 6, iyakar Erdős da Graham tana ba da 10, ta Dixmier tana ba da 18, sabuwar kuma tana ba da 4 × 3 − 6 − 1 = 5, daidai ainihin ƙimar. Ba abin mamaki ba ne: wannan rukuni yana cikin dangin misalan ƙarshen gaɓa da aka bayyana a ƙasa, waɗanda aka gina don su kai iyakar daidai; takardar ba ta ba da kwatanci a kan rukunoni na yau da kullum ba.

Rarraba adadi bisa ragowa

Hujjar tana bin hanyar Erdős da Graham. Ka rarraba kowane adadi bisa ragowarsa (remainder) bayan raba shi da tsabar kuɗi mafi girma, aₙ. Da zarar jimillar ƙananan tsabar kuɗi ta kai wata ragowa, ƙara kwafin aₙ yana kaiwa ga kowane adadi mafi girma mai wannan ragowa. Aikin shi ne nuna cewa ana iya kaiwa ga kowace ragowa da arha.

Babban kayan aiki shi ne theorem na Kneser, kan girman da rukunin jimloli dole ne ya kasance da shi. Erdős da Graham sun yi amfani da shi don nuna cewa jimlolin kusan tsabar kuɗi aₙ/n suna rufe fiye da rabin ragowoyin, sannan suka ninka don rufe su duka. Kowace tsabar kuɗi a cikin waɗannan jimloli ba ta wuce aₙ₋₁ ba, don haka ninka yawan tsabar kuɗi yana ninka farashi: daga nan ninki 2 ya fito.

Sabuwar hujjar tana amfani da jimloli na tsabar kuɗi ⌈aₙ/(n − 1)⌉. Lokacin da waɗannan jimloli suka rasa wasu ragowoyi, theorem na Kneser ya ce ragowoyin da suka ɓace ba a warwatse suke ba kara-zube: suna kafa cikakkun iyalai na ragowoyi masu tazara daidai-wa-daida. Gwargwadon yawan iyalan da suka ɓace, gwargwadon yawan ƙananan tsabar kuɗi da dole ne su cunkushe cikin kowane iyali da aka kai, don haka kowane ɗaya daga cikin waɗannan iyalai yana ɗauke da wasu ƙananan tsabar kuɗi, kuma ’yan ƙarin tsabar kuɗin da ake buƙata don kaiwa ga iyalan da suka ɓace suna da arha. Jimillar ba ta taɓa wuce ⌈aₙ/(n − 1)⌉ × aₙ₋₁ ba.

Wannan mataki na farko yana ba da iyakar ba tare da “− 1” na ƙarshe ba. Raka’a ta ƙarshe ta fito ne daga wata hujja daban, bisa wani theorem na Scherk da Kemperman kan jimlolin da za a iya samarwa ta hanya ɗaya kawai: tana nuna cewa adadin kan iyaka aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ kansa ana iya biyan sa koyaushe. Bisa ga sashen godiya, marubutan sun fara tabbatar da iyakar mafi rauni; sai GPT-6 ya taimaka wajen gano hujjar da ke rage ta da ɗaya, kuma ya taimaka a hujjar cewa ba za a iya rage iyakar ba da kuma gyaran Turancin. Marubutan sun bayyana cewa su ne ke da alhakin rubutun ƙarshe.

Misalan da suka kai iyakar daidai

Ba za a iya rage wannan iyaka ba: ga kowane n ≥ 3, marubutan sun gina rukunoni marasa iyaka inda F ya yi daidai da ita. Ɗauki kowane q ≥ 2 da ƙimomin q, 2q, …, (n − 1)q, tare da (n − 2)q + 1. Duka sai ɗaya ninkin q ne, don haka ba sa biyan wani abu da q kaɗai ba zai iya biya ba. Rukunin yana aiki kamar tsabar kuɗi biyu, q da (n − 2)q + 1, kuma dabarar Sylvester tana ba da F da ya yi daidai da sabuwar iyakar. Da n = 3 da q = 3, wannan girke-girke yana samar da daidai misalin 3, 4, 6 da ke sama.

Ƙarancin tsabar kuɗi, ƙasan rufi

Ana kuma iya karanta iyakar ta fuskar cunkoso (density). Tana aiki ga kowane rukuni da aka rage wanda aka yi daga ƙimomi i mafiya ƙanƙanta tare da mafi girma, muddin waɗannan har yanzu ba su da abin raba na bai ɗaya. Cire tsabar kuɗi zai iya sa biya ya ƙara wahala ne kawai, don haka rufin da aka tabbatar ga rukunin da aka rage yana aiki ga cikakken rukunin ma. Abin da ke sarrafa sakamakon kusan aᵢ/i ne, juzu’in yadda ƙimomin i na farko ke cika lambobi daga 1 zuwa aᵢ da yawa: rukuni mafi cunkoso ne ke yin nasara. Musamman, marubutan sun lura, ana iya ajiye tsabar kuɗi ta biyu mafi girma a gefe a duk lokacin da sauran tsabar kuɗin har yanzu ba su da abin raba da ke tsakanin dukansu.

Takardar tana nan a fagen ka’ida kawai: ba ta ba da adadi kan girman yadda sabuwar iyakar ta fi ƙanƙanta a kan rukunonin tsabar kuɗi na yau da kullum ba, kuma an tabbatar da cewa ba za a iya inganta ta ba ne kawai ga ƙimomin tsabar kuɗi uku ko fiye.