KIASI KIKUBWA ZAIDI USICHOWEZA KULIPA, SASA KIMEWEKEWA KIKOMO KINACHOBANA

Fikiria mashine ya malipo inayokubali aina chache tu za sarafu, zinazopatikana bila kikomo, na ambayo kamwe hairudishi chenji. Baadhi ya viasi vinaweza kulipwa kamili; vingine haviwezi kamwe. Wanahisabati huziita thamani za sarafu vizalishi (generators), na huuliza swali linaloonekana rahisi kwa udanganyifu: ni kiasi gani kikubwa zaidi kisichoweza kulipwa?

Viasi visivyoweza kulipwa kamwe

Chukua namba kamili a₁ < a₂ < … < aₙ zisizo na kigawo kinachoshirikiwa na zote. Jumla inayopatikana kwa kujumlisha namba hizi, kila moja mara nyingi kadiri unavyotaka, ni “inayowakilishika”. Namba kamili zisizowakilishika ni chache, zenye idadi yenye kikomo; kubwa zaidi kati yake ni namba ya Frobenius, F. (Ikiwa mojawapo ya thamani ni 1, kila kiasi kinaweza kulipwa na F huwekwa kuwa −1.)

Mfano mdogo: kwa sarafu za 3, 4 na 6, unaweza kulipa 3, 4, 6, 7, 8 na kila kiasi baada ya hapo, lakini kamwe si 1, 2 au 5. Kwa hiyo F = 5. Kumbuka kwamba 3 na 6 zinashiriki kigawo; kinachojalisha ni kwamba hakuna kigawo kinachoshirikiwa na zote tatu.

Kwa sarafu mbili kuna jibu kamili, fomula ya Sylvester: F(a₁, a₂) = a₁a₂ − a₁ − a₂. Kwa tatu au zaidi, kazi ni kuweka kikomo kwa F: kuthibitisha kwamba haiwezi kuzidi thamani fulani inayokokotolewa kutoka kwenye sarafu.

Kizidishi 2 kisichotaka kuondoka

Paul Erdős na Ronald Graham walithibitisha, kwa vizalishi vitatu au zaidi:

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

Hapa aₙ ni thamani kubwa zaidi, aₙ₋₁ ni ya pili kwa ukubwa, n ni idadi ya thamani, na ⌊ ⌋ inamaanisha kukadiria kuelekea chini. Kama fomula ya Sylvester, inahusisha sarafu mbili kubwa zaidi.

Pia walikadiria hali mbaya zaidi, yaani F kubwa zaidi inayowezekana wakati thamani zote n hazizidi t. Pengo kati ya makadirio yao, takriban kizidishi 2, liliongoza kwenye dhana (conjecture) iliyorekodiwa kama Tatizo la Erdős #433 (Erdős Problem #433). Jacques Dixmier aliitatua, na pia akathibitisha kikomo rahisi zaidi kinachofaa kwa kila seti: F ≤ aₙ²/(n − 1). Kizidishi 2 kimetoweka, lakini pia sarafu ya pili kwa ukubwa imetoweka.

Kubakiza sarafu zote mbili kubwa zaidi

Lin Chen, Tingwei Hu, Yuchen Mao na Guochuan Zhang, wa Kitivo cha Sayansi na Teknolojia ya Kompyuta katika Chuo Kikuu cha Zhejiang, walitaka vyote viwili: bila kizidishi 2, na sarafu ya pili kwa ukubwa ikibakizwa. Jibu lao, linalofaa kwa seti yoyote ya thamani mbili au zaidi:

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

Hapa ⌈ ⌉ inamaanisha kukadiria kuelekea juu. Ukilinganisha na Erdős na Graham, kizidishi 2 kimetoweka, kwa gharama ya kugawanya kwa n − 1 badala ya n na kukadiria kuelekea juu. Ukilinganisha na Dixmier, kikomo kipya kinaweza kuwa kidogo zaidi kwa kiasi kikubwa wakati sarafu ya pili kwa ukubwa ni ndogo ikilinganishwa na ile kubwa zaidi.

Kwa mfano wa 3, 4, 6, kikomo cha Erdős na Graham kinatoa 10, cha Dixmier kinatoa 18, na kile kipya kinatoa 4 × 3 − 6 − 1 = 5, sawasawa na thamani halisi. Si jambo la kushangaza: seti hii ni ya familia ya visa vya ukingoni vilivyoelezwa hapa chini, vilivyojengwa ili kufikia kikomo hicho sawasawa; makala haitoi ulinganisho wowote kwa seti za kawaida.

Kupanga viasi kwa baki

Uthibitisho unafuata njia ya Erdős na Graham. Panga kila kiasi kulingana na baki yake baada ya kugawanya kwa sarafu kubwa zaidi, aₙ. Mara jumla ya sarafu ndogo zaidi inapofikia baki fulani, kuongeza nakala za aₙ hufikia kila kiasi kikubwa zaidi chenye baki hiyo. Kazi ni kuonyesha kwamba kila baki inaweza kufikiwa kwa gharama nafuu.

Chombo kikuu ni nadharia ya Kneser, kuhusu jinsi seti ya jumla inavyopaswa kuwa kubwa. Erdős na Graham waliitumia kuonyesha kwamba jumla za takriban sarafu aₙ/n hufunika zaidi ya nusu ya baki, kisha wakaongeza maradufu ili kuzifunika zote. Kila sarafu katika jumla hizi ina thamani isiyozidi aₙ₋₁, kwa hiyo kuongeza maradufu idadi ya sarafu huongeza maradufu gharama: ndiyo chanzo cha kizidishi 2.

Uthibitisho mpya unatumia jumla za sarafu ⌈aₙ/(n − 1)⌉. Jumla hizi zinapokosa baadhi ya baki, nadharia ya Kneser inasema kwamba baki zinazokosekana hazijatawanyika ovyo: zinaunda familia nzima za baki zilizopangwa kwa nafasi sawa. Kadiri familia nyingi zaidi zinavyokosekana, ndivyo sarafu ndogo zaidi zinavyopaswa kujazana katika kila familia inayofikiwa, kwa hiyo kila moja ya familia hizo ina baadhi ya sarafu ndogo, na sarafu chache za ziada zinazohitajika kufikia familia zinazokosekana ni nafuu. Jumla haizidi kamwe ⌈aₙ/(n − 1)⌉ × aₙ₋₁.

Hatua hiyo ya kwanza inatoa kikomo bila “− 1” yake ya mwisho. Moja hiyo ya mwisho inatokana na hoja tofauti, inayotegemea nadharia ya Scherk na Kemperman kuhusu jumla zinazoweza kuundwa kwa njia moja tu: inaonyesha kwamba kiasi cha mpakani aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ chenyewe kinaweza kulipwa kila mara. Kwa mujibu wa sehemu ya shukrani, waandishi kwanza walithibitisha kikomo dhaifu zaidi; kisha GPT-6 ilisaidia kupata hoja inayokishusha kwa moja, na pia ilisaidia katika uthibitisho kwamba kikomo hicho hakiwezi kushushwa na katika kuhariri Kiingereza. Waandishi wanaeleza kwamba wanabeba jukumu la mswada wa mwisho.

Visa vinavyogusa kikomo sawasawa

Kikomo hiki hakiwezi kushushwa: kwa kila n ≥ 3, waandishi wanajenga seti zisizo na idadi ambapo F ni sawa nacho kabisa. Chukua q yoyote ≥ 2 na thamani q, 2q, …, (n − 1)q, pamoja na (n − 2)q + 1. Zote isipokuwa moja ni vigawe vya q, kwa hiyo hazilipi chochote ambacho q peke yake haiwezi kulipa. Seti hiyo hutenda kama sarafu mbili, q na (n − 2)q + 1, na fomula ya Sylvester inatoa F inayolingana sawasawa na kikomo kipya. Kwa n = 3 na q = 3, mbinu hii inatoa hasa mfano wa 3, 4, 6 ulio hapo juu.

Sarafu chache, dari la chini zaidi

Kikomo hicho kinaweza pia kusomwa kwa mtazamo wa msongamano. Kinatumika kwa seti yoyote iliyopunguzwa inayoundwa na thamani i ndogo zaidi pamoja na ile kubwa zaidi, ilimradi bado hazina kigawo cha pamoja. Kuondoa sarafu kunaweza tu kufanya malipo kuwa magumu zaidi, kwa hiyo dari lililothibitishwa kwa seti iliyopunguzwa linatumika pia kwa seti kamili. Kinachodhibiti matokeo ni takriban aᵢ/i, kinyume cha jinsi thamani i za kwanza zinavyojaza kwa msongamano namba kutoka 1 hadi aᵢ: kundi lenye msongamano mkubwa zaidi ndilo hushinda. Hasa, waandishi wanabainisha, sarafu ya pili kwa ukubwa inaweza kuwekwa kando tu kila mara sarafu zilizobaki bado hazina kigawo kinachoshirikiwa na zote.

Makala inabaki ya kinadharia tu: haitoi namba yoyote ya jinsi kikomo kipya kilivyo kidogo zaidi kwa seti za kawaida za sarafu, na ukali wake unathibitishwa tu kwa thamani tatu za sarafu au zaidi.