LissafiKafin bugawaNazariyyaKaratun minti 3

WANI HASASHE NA 1969 GAME DA JIMILLOLIN DA KE SOKE JUNA YA ZAMA BA GASKIYA BA

Ɗauki agogo mai awa shida, da jerin motsi: “juya allurar gaba da awa 1”, “gaba da awa 4”, da sauransu. Da motsi biyar na awa ɗaya kowanne, babu wani rukuni daga cikinsu da zai taɓa mayar da allurar daidai farkon wurinta. Da motsi shida, ko yaya suke, kullum wani rukuni zai yi hakan. Masana lissafi suna rubuta wannan lissafin agogo da C₆, kuma lamba shida a nan ita ce tsayayyen adadin Davenport (Davenport constant) na agogon.

Yanzu sanya irin waɗannan agogo r gefe da gefe, kuma bari kowane motsi ya juya kowace allura da nata adadin. Tsayayyen adadin Davenport na wannan rukunin agogo, wanda ake rubutawa D(C₆^r), shi ne mafi ƙarancin adadin motsi da ke tabbatar da samun wani rukuni wanda jimillarsa ke mayar da kowace allura farkon wurinta a lokaci ɗaya — ƙaramin jeri (subsequence) mai jimillar sifili (zero-sum), a kalaman takardar. Wannan adadi yana da alaƙa da matsaloli a ka’idar jadawalai (graph theory), jometiri mai iyaka (finite geometry), kombinatorik (combinatorics) da ka’idar rarrabuwa zuwa abubuwan ninkawa (factorization theory).

Wata dabara daga 1969

Akwai wata iyakar ƙasa (lower bound) mai sauƙi. A kan kowane agogo, ɗauki motsi biyar na awa ɗaya waɗanda suke shafar wannan agogon kaɗai: da agogo r, hakan yana ba da motsi 5r waɗanda babu wani rukuni daga cikinsu da ke soke juna. Don haka ana buƙatar akalla motsi 5r + 1. Gaba ɗaya, ga agogo masu awa n, akalla r(n − 1) + 1.

A 1969, van Emde Boas da Kruyswijk sun yi hasashen (conjecture) cewa wannan iyaka mai sauƙi ita ce ainihin amsar kullum:

D(C_n^r) = r(n − 1) + 1.

An tabbatar da shi a shekarun 1960 ga wasu yanayi, kamar agogo waɗanda adadin awoyinsu ƙarfi (power) ne na lambar firamare, ko kuma agogo biyu a mafi yawa. Bayan haka, ainihin ƙimar ta kasance ba a iya kaiwa gare ta ba: har zuwa 2018, ko da yanayin agogo huɗu masu awa shida ba a san shi ba. Duk da haka, hasashen ya zama “wata fitacciyar matsala da ta daɗe” a fannin, kuma ana sa ran zai tabbata.

Motsi 116 da ba sa taɓa soke juna

Weidong Gao (Jami’ar Tianjin, Tianjin University), Alfred Geroldinger (Jami’ar Graz, University of Graz), Guoqing Wang (Jami’ar Tiangong, Tiangong University) da Xiangneng Zeng (Jami’ar Sun Yat-Sen, Sun Yat-Sen University) yanzu sun nuna cewa ya kasa.

Ƙungiyar tana haɗa motsin kamar tubalan gini:

  • jerin motsi 24 a kan agogo biyar masu awa shida, wanda aka gina daga wani ƙaramin tebur: duk wani rukuni daga cikinsu da jimillarsa ta faɗa cikin wani ƙaramin tarin wurare uku, kullum yana sauka a kan wuri ɗaya wanda ba sifili ba;
  • jeri biyu irin wannan da suke raba waɗannan wurare uku, abin da ke ba da motsi 48 da babu wani rukuni daga cikinsu da ke soke juna;
  • wani jerin motsi 20 daban wanda shi ma babu wani rukuni daga cikinsu da ke soke juna.

Idan aka sanya su gefe da gefe, suna ba da motsi 2 × 48 + 20 = 116 a kan agogo 23 masu awa shida, kuma babu wani rukuni daga cikinsu da ke mayar da kowace allura farkon wurinta. Hasashen ya ce 23 × 5 = 115 ne jeri mafi tsawo da zai yiwu irin wannan. Don haka ga agogo 23, tsayayyen adadin Davenport akalla 117 ne, ba 116 ba.

Ana iya tara kwafin wannan gunduwa a kan juna: sakamakon gaba ɗaya shi ne D(C₆^r) ≥ 5r + ⌊r/23⌋ + 1, inda ⌊r/23⌋ ke ƙirga cikakkun gunduwoyi na 23 nawa ne ke shiga cikin r. Saboda haka hasashen ba gaskiya ba ne ga agogo masu awa shida da zarar r ta kai 23, da kuma kowace r mafi girma. Marubutan sun lura cewa wannan ka’ida (theorem) ɗaya kuma tana ƙaryata wani sakamako da aka yi hasashe game da rufe-rufe (coverings).

Abin da ya rage a buɗe

Hujjar ba ta ba da ainihin ƙimar D(C₆^r) ba, sai dai wata iyaka da hasashen ya hana. Ba ta faɗi wani sabon abu ga agogo ƙasa da 23 ba, inda sabuwar iyakar ta yi daidai da tsohuwar dabarar, ko kuma ga agogo masu adadin awoyi ban da shida. Takardar tana da shafuka biyar, kuma har yanzu ana jiran bitar takwarorin masana (peer review).