IYAKAR GUDUN WARWARE MA'AUNI DAGA 1974, AN TABBATAR DA ITA A ƘARSHE

Don gano inda wani aiki (function) f ke ketare sifili, kwamfuta kan gudanar da maimaitawa (iteration): fara da wani hasashe x, yi wa aikin ’yan tambayoyi, lissafa hasashe mafi kyau, sannan a maimaita. Tambayoyin su ne ƙididdigar ƙima (evaluations): ƙimar f a wani maki, ko ta gangarensa (wato derivative), ko ta wani derivative mafi girma.

Lambobi da ke ninkuwa

Ana auna gudun irin wannan hanya da darajar saurinta (order). Idan kuskuren yanzu shi ne ε, maimaitawa mai darajar sauri p tana barin kuskure na kusan ε zuwa ƙarfin p. Darajar sauri 2 tana nufin cewa, kusa da amsar, adadin lambobin da suka yi daidai yana ninkuwa a kowane mataki; darajar sauri 4, cewa yana ninkuwa sau huɗu.

Hanyar Newton tana kashe ƙididdigar ƙima biyu a kowane mataki — f(x) da gangarensa f′(x) — kuma tana komawa zuwa x − f(x)/f′(x). Darajar saurinta 2 ce. Yin ƙarin tambayoyi a kowane mataki na iya sayen ƙarin gudu. Tambayar ita ce nawa.

Hasashe daga 1974

A 1974, H. T. Kung da J. F. Traub sun gabatar da amsa, a matsayin “Conjecture 8.1” na wata takarda a cikin Journal of the ACM: maimaitawa mara ƙwaƙwalwa (without memory) da ke amfani da ƙididdigar ƙima n a kowane mataki tana da darajar sauri 2ⁿ⁻¹ a mafi yawa. “Mara ƙwaƙwalwa” yana nufin cewa hanyar ba ta riƙe komai daga matakan baya sai hasashenta na yanzu.

Ba za a iya saukar da iyakar ba: Kung da Traub da kansu sun gina hanyoyin “maki da yawa” (multipoint) da suka kai 2ⁿ⁻¹ ga kowane n ≥ 2 — darajar sauri 4 da ƙididdigar ƙima uku, 8 da huɗu, 16 da biyar. Abin da ya rage shi ne ɗayan rabin: hujja cewa babu wata hanya da za ta iya yin fiye da haka. Sakamako na ɓangare sun zo tare da hasashen da kuma bayansa. An tabbatar da iyakar ga hanyoyin da suka dogara da interpolation, ga hanyoyin rational masu ƙididdigar ƙima biyu, da kuma ƙarƙashin wasu ƙarin sharuɗɗa daban-daban; ga hanyoyin da ke amfani da ƙimomin aikin kawai, an tabbatar da wata iyaka mafi rauni, 2ⁿ. Batun gaba ɗaya ya kasance a buɗe.

Yaudarar algorithm

Yanzu an tabbatar da shi gaba ɗaya, a aikin Matthew Colbrook, na Department of Applied Mathematics and Theoretical Physics ta University of Cambridge. Samfurin da gangan yana da karimci ga algorithm ɗin. Yana iya zaɓar inda zai yi ƙididdigar ƙima, da waɗanne derivatives zai ɗauka, yayin da yake tafiya. Yana iya sarrafa amsoshin ta kowace hanya tabbatacciya (deterministic) da yake so, ba tare da buƙatar santsi (smoothness) a ƙa’idodinsa ba.

Hujjar tana juya tabbataccen halin algorithm ɗin (determinism) a kansa. A gina ayyuka biyu da ke ba da amsoshi iri ɗaya sak ga dukkan tambayoyinsa amma suna da sifilai daban-daban. Dole ne algorithm ɗin ya mayar da hasashe ɗaya ga dukkansu, don haka a kan ɗaya daga cikinsu yana kuskure da aƙalla rabin nisan da ke tsakanin sifilai biyun.

Don nemo irin waɗannan nau’i-nau’i, Colbrook na ɗan tura wani aikin tunani (reference function) da ƙaramin polynomial mai digiri (degree) n a mafi yawa, wanda ke da lambobin ninkawa (coefficients) n + 1 da za a iya daidaitawa. Kowace ƙididdigar ƙima tana ƙayyade haɗi ɗaya kawai daga cikinsu a mafi yawa, don haka bayan tambayoyi n wasu turawa suna kasancewa ba a ganinsu ga algorithm ɗin. Wannan ƙidaya kaɗai ba ta isa ba: turawar da ba a gani na iya kusan rashin motsa sifilin.

Babban kayan aikin shi ne Wronskian — wani determinant da aka gina daga wani iyalin polynomials da derivatives ɗinsu. Wata sabuwar lemma ta ce idan wani polynomial na iyalin yana da sifilai da yawa da suka cunkushe cikin ƙaramin faifai (disc), dole ne Wronskian na iyalin ya zama sifili a kusa. Ta hanyar amsa wa algorithm ɗin kodayaushe da aikin da sifilinsa ke nesa da waɗannan ’yan maki, hujjar tana barin sifilin a ’yance ya motsa.

Lissafin bin diddigi ne ke samar da ƙarfin (exponent). Farawa daga nisa ε daga sifilin, sifilan da za su iya yiwuwa suna kasancewa a baje kan kewayon da ya kai aƙalla wani constant sau wani ƙarfin ε. A cewar Colbrook, “ƙarfin yana kasancewa ɗaya bayan lura ta farko sannan yana ninkuwa, yana ba da 2ⁿ⁻¹ bayan lura n.”

Aiki ɗaya ga kowane girma

Wata wahala ta rage. Ma’anar darajar sauri tana ba da damar constant ɗin da ke gaba ya dogara da aikin, don haka aiki mara kyau dabam a kowane girma ba ya tabbatar da komai. Saboda haka Colbrook na gina aiki guda ɗaya, ta hanyar ƙara gyare-gyare ɗaya bayan ɗaya, kowanne yana zama sifili a kowane maki da algorithm ɗin ya riga ya tambaya, ta yadda dukkan amsoshin baya su kasance daidai yadda suke.

Abin da ginin ke kaiwa a ƙarshe (limit) shi ne aiki cikakke (entire function) — mai santsi ko’ina, har ma a kan lambobin complex — wanda gangarensa ke tsakanin 3/4 da 5/4 a kan layin lambobi na gaske (real line): lanƙwasa da ke tashi a hankali tare da sifili ɗaya mai kyakkyawan hali. Ga kowane p sama da 2ⁿ⁻¹, hanyar ta kasa kai darajar sauri p a kansa. Saboda haka mafi kyawun darajar sauri ba tare da ƙwaƙwalwa ba daidai 2ⁿ⁻¹ ce ga n ≥ 2. Takardar ta tabbatar da wannan iyaka ɗaya lokacin da ƙididdigar ƙima lambobin complex ne.

Farashin tambaya duka lokaci ɗaya

Wata magana mafi kaifi ta shafi ƙididdigar ƙima da aka yi a rukuni-rukuni, inda ake zaɓar kowace tambaya ta rukuni kafin kowace amsarsa ta iso — yanayin hanyoyin da ke aiki a layi ɗaya (parallel methods). Da rukunoni masu girma ℓ₁, …, ℓₖ, darajar sauri ita ce ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1) a mafi yawa. Yin dukkan tambayoyi n lokaci ɗaya yana iyakance darajar sauri a n; yin su ɗaya bayan ɗaya yana ba da damar 2ⁿ⁻¹. Da ƙididdigar ƙima biyar, wannan 5 ne idan aka kwatanta da 16.

Na’ura ta duba

An tabbatar da sakamakon a tsari na hukuma (formally verified) a cikin Lean, mataimakin hujja (proof assistant) da ke duba kowane mataki na hankali. Lambar (code) a buɗe take ga jama’a kuma an yi mata rajista a rajistar Palomar. Takardar ta bayyana cewa an aiwatar da tsara hujjar a Lean (Lean formalisation) da taimakon ChatGPT 6, sannan aka duba ta da Lean 4 Comparator a kan theorems na takardar, cewa an sake duba kowace hujja ta hannun Colbrook, kuma Colbrook ne ke ɗaukar cikakken alhakin abin da ke ciki.

Iyakar ta shafi hanyoyin da ke mantawa. Hanyoyin da aka bar su su sake amfani da matakansu na baya suna bin wasu iyakoki dabam, waɗanda wannan takarda ta bar su a gefe.