Anatolijus Karacuba

Ankstyvieji darbai iš informatikos

Būdamas Maskvos valstybinio Lomonosovo universiteto studentu, Karacuba lankė Andrejaus Kolmogorovo seminarus ir išsprendė dvi Kolmogorovo iškeltas problemas, kurios buvo svarbios automatų teorijos vystymui ir davė pradžią naujai matematikos šakai – greitųjų algoritmų teorijai.

Automatai

Edvardo F. Muro (Edward F. Moore) straipsnyje  tipo  automatu arba mašina yra vadinamas įrenginys su  būsenų,  įėjimo simbolių ir  išėjimo simbolių. Straipsnyje buvo įrodytos devynios teoremos apie  struktūrą ir eksperimentus su . Vėliau  buvo pavadintos Muro mašinomis. Straipsnio pabaigoje skyrelyje "Naujos problemos" Muras suformulavo problemą apie įverčių, gautų 8 ir 9 teoremose patikslinimą.
8 teorema (Muro). Tarkime, jog  yra tokia tipo  mašina, kad bet kurios dvi būsenos yra skirtingos viena nuo kitos. Tuomet egzistuoja  ilgio algoritmas, savo pabaigoje identifikuojantis  būseną.
1957 m. Karacuba įrodė dvi teoremas, kurios pilnai išsprendė Muro problemą apie 8 teoremos algoritmo ilgio patikslinimą.
A teorema (Karacubos). Tarkime, jog  yra tipo  mašina, kurios bet kurios dvi būsenos yra skirtingos. Tuomet egzistuoja ne didesnio negu  išsišakojęs algoritmas, pagal kurį ekspermento pabaigoje gali būti surasta mašinos  būsena.
B teorema (Karacubos). Egzistuoja tokia  tipo mašina su skirtingomis būsenomis, kad būsenos radimo trumpiausio algoritmo ilgis yra 
Šias dvi teoremas Karacuba įrodė ketvirtame kurse, jos buvo jo kursinio darbo pagrindas. Atitinkamas straipsnis 1958 m. gruodžio 17 d. buvo įteiktas žurnalui "Uspechi Matem. Nauk" ir paskelbtas 1960 m. Iki šiol šis Karacubos rezultatas, vėliau pavadintas Muro-Karacubos teorema, lieka tiksliausias (tiksliausias ne tiesinis eilės įvertis) ne tiesinis rezultatas tiek automatų teorijoje, tiek ir analogiškose skaičiavimų sudėtingumo teorijos problemose.

Greitieji algoritmai

Greitieji algoritmai yra matematikos sritis, nagrinėjanti duotos funkcijos apskaičiavimo nurodytu tikslumu algoritmus naudojant kiek galima mažiau operacijos bitų. Tarkime, jog skaičiai yra užrašyti binarioje sistemoje, kurios ženklai  ir  yra vadinami "bitais". Vienos "operacijos bitas" apibrėžiamas rašant vieną iš ženklų , plius, minus, skliausteliai; rašant greta, atimant ir sudauginant du bitus. Andrejus Kolmogorovas pirmasis iškėlė problemas apie skaičiavimo sudėtigumo bitus. Daugybos sudėtigumas  yra skaičius operacijos bitų, reikalingas apskaičiuoti dviejų  skaitmenų skaičių sandaugą, naudojant duotą algoritmą.
Daugindami du -skaitmenų skaičius įprastu mokykliniu stulpelio metodu, gauname, kad . 1956 m. A. N. Kolmogorovas iškėlė hipotezę, jog bet kurio daugybos metodo apatinis  rėžis taip pat yra  eilės, t. y., negalima apskaičiuoti dviejų  skaitmenų skaičių sandaugą greičiau negu naudojant  operacijų (vadinamoji Kolmogorovo  hipotezė).  hipotezė atrodė realistinė, kadangi visa skaičių daugybos istorija naudojosi eilės  sedėtingumu, ir jei greitesnis metodas būtų egzistavęs, jis tikriausiai jau būtų surastas.
1960 m. Anatolijus Karacuba surado naują  ženklų skaičių daugybos būdą, dabar vadinamą Karacubos algoritmu, kurio sudėtingumo eilė . Taigi,  hipotezė buvo paneigta. Karacuba šį rezultatą 1960 m. pristatė Maskvos Valstybinio Universiteto Kolmogorovo seminare, kuris vėliau nustojo veikti. Pirmąjį straipsnį, kuriame buvo išdėstytas metodas, paruošė pats Kolmogorovas. Jame buvo pateikti du skirtingi, vienas su kitu nesusiję, jo dviejų studentų rezultatai. Straipsnyje Kolmogorovas aiškiai nurodė, jog viena teorema (nesusijusi su greita daugyba) priklauso J. Ofmanui, o kita (su pirmuoju greitosios daugybos algoritmu) yra įrodyta A. Karacubos. Vėliau Karacubos metodas buvo pavadintas "Dalyk ir nugalėk" algoritmu. Kiti šio metodo pavadinimai, priklausomai nuo taikymų srities, yra Binarusis skaidymas, Dichotomijos principas ir t. t.
Vėliau, remiantis Karacubos idėjomis buvo sukonstruoti tūkstančiai greitųjų algoritmų. Dauguma jų yra tiesioginiai Karacubos metodo apibendrinimai. Tokie yra Šonhagės-Štraseno (Schönhage-Strassen) ir Štraseno matricų daugybos algoritmai. Pastaraisiais metais "Dalyk ir nugalėk" vardas yra naudojamas operacijoms, kurios problemą skaldo į dalis, ir tai paprastai nėra susiję su greitais skaičiavimo algoritmais.
Prancūzų matematikas ir filosofas Žanas – Polis Delajė (Jean-Paul Delahaye) laikė Karacubos daugybos metodą "vienu iš naudingiausių matematikos rezultatų".
Anatolijaus Karacubos algoritmas praktiškai yra realizuotas šiuolaikiniuose kompiuteriuose, ne tik programinėje, bet ir techninėje įrangoje.

Darbai iš skaičių teorijos

Straipsnyje "Apie profesoriaus A. A. Karacubos matematikos darbus", paskelbtame A. A. Karacubos šešiasdešimtmečio proga, jo buvę mokiniai G. I. Archipovas ir V. N. Čiubarikovas išskiria tokius A. A. Karacubos mokslinių straipsnių charakteringus bruožus: "Aprašant garsių mokslininkų darbus, yra natūralu apibendrinti jųkūrybinio darbo kai kurias charakteristikas. Tokie išsiskiriantys profesoriaus Karacubos mokslinio darbo bruožai yra įvairiapusis genialumas, fundamentalus charakteris ir rezultatų išbaigtumas".
Svarbiausi A. A. Karacubos darbai yra paskelbti daugiau negu 160 mokslinių straipsnių ir monografijų.

$p$-adinis metodas

A. A. Karacuba pastatytas naujas - adinį metodą trigonometrinių sumų teorijoje. Taip vadinamų  sumų pavidalo
įverčiai, gauti darbe, sąlygojo naujus Dirichlė  funkcijų su pirminio skaičiaus laipsnio moduliu nulių įverčius, Varingo (Waring) lyginio
 sprendinių skaičiaus asimptotinę formulę, polinomo su sveikais keoficientais moduliu  trupmeninių dalių pasiskirstymo problemos sprendimą. A. A. Karacuba pirmasis realizavo Oilerio – Vinogradovo " įdėjimo principo" -adinį variantą ir suskaičiavo Vinogradovo -skaičiaus, įvertinančio Varingo tipo lyginio sprendinių skaičių, -adinį analogą. Tarkime, kad
ir, be to, , o  yra pirminis skaičius. Karacuba įrodė, kad tuomet su kiekvienu natūraliuoju  egzistuoja toks , kad, kai  kiekvienas natūralusis skaičius  gali būti išreikštas (1) forma su , o kai , egzistuoja tokie , kad (1) lyginys neturi prasmės.
Šis naujas Karacubos metodas atvedė prie naujo -adinio Vinogradovo vidurkių teoremos, sudarančios Vinogradovo trigonometrinių sumų metodo svarbiausią dalį, įrodymo.
Kitas A. A. Karacubos -adinio metodo privalumas yra perėjimas nuo nepilnos lygčių sistemos prie pilnos -adinio nežinomųjų pakeitimo dėka.
Tegul  yra bet koks natūralusis skaičius, , o sveikasis skaičius  yra apibrėžtas nelygybėmis  Nagrinėkime lygčių sistemą
kurioje  Karacuba parodė, kad šios sistemos sprendinių skaičiui  kai , yra teisingas įvertis
Nepilnoms lygčių sistemoms, kai kintamieji perbėga skaičius su mažais pirminiais dalikliais, Karacuba pritaikė multiplikatyvų kintamųjų pakeitimą. Tai leido gauti iš esmės naujus trigonometrinių sumų įverčius ir naują vidurkių teoremą tokio tipo lygčių sistemoms.

Hua-Luogeng'o problema apie Terio (Terry) problemos singuliariojo integralo rodiklių konvergavimą

-adinis A. A. Karacubos metodas leidžia įvertinti taškų aibių, sudarytų iš mažų funkcijų reikšmių, matą tų reikšmių ir jų parametrų (koeficientų ir t. t.) terminais, ir, priešingai, duoda būdą tų parametrų įvertinimui minėtos aibės mato terminais tiek realioje, tiek ir -adinėje metrikoje. Ši Karacubos metodo pusė labai ryškiai pasireiškia trigonometrinių integralų įvertinime, kuris atvedė prie Hua Luogengo problemos sprendimo. 1979 m. Karacuba kartu su savo mokiniais G. I. Archipovu ir V. N. Čiubarikovu gavo pilną Hua Lougengo problemos sprendimą, nurodydami integralo
konvergavimo rodiklį, kai  yra fiksuotas skaičius. Ši problema buvo iškelta 1937 m. Konvergavimo rodiklis yra reikšmė , su kuria integralas  konverguoja, kai  ir diverguoja, kai . Čia  yra kiek norima mažas skaičius. Buvo įrodyta, kad integralas  konverguoja, kai $2k > \frac{1}{2}(n^{2}+n)+1$, ir diverguoja, kai $2k \leq \frac{1}{2}(n^{2}+n)+1$. Tuo pa{\v c}iu metu pana{\v s}i problema buvo išspręsta ir integralui
 čia  yra sveikieji skaičiai, tenkinantys nelygybes . Karacuba ir jo mokiniai įrodė, jog integralas  konverguoja, kai , ir diverguoja, kai .
Integralai  ir  atsiranda nagrinėjant taip vadinamą Prušė-Terio-Eskoto (Prouchet-Tarry-Escott) problemą. Karacuba su savo mokiniais gavo eilę naujų rezultatų, liečiančių daugiamatį Terio problemos analogą. Be kita ko, jie įrodė, kad jei  yra , , kintamųjų polinomas
 polinomo  laisvasis narys lygus nuliui, , o  yra  – matis vektorius, sudarytas iš polinomo  koeficientų, tai tuomet integralas
konverguoja, kai , čia  yra didžiausias iš skaičių . Šis rezultatas, nors ir ne galutinis, inspiravo naują trigonometrinių integralų teorijos sritį, susijusią su integralo  konvergavimo rodiklio įverčio patikslinimu (I. A. Ikromovas, M. A. Čahkijevas ir kiti).

Kartotinės trigonometrinės sumos

1966–1980 Karacuba sukūrė kartotinių Hermano Veilio (Hermann Weyl) trigonometrinių sumų, t. y., sumų pavidalo
su
ir realių koeficientų  sistema , teoriją. Centrinė tos teorijos, kaip ir Vinogradovo trigonometrinių sumų teorijos, vieta yra tokia vidurkių teorema.
Tegul ,  yra natūralieji skaičiai, , . Be to, tegul  yra  -matis kubas , , , euklidinėje erdvėje ir
Tuomet su kiekvienu  ir  yra teisingas įvertis
čia , , , , o natūralieji skaičiai  tenkina nelygybes , .
Vidurkių teorema kartu su lema apie daugiamačių gretasienių susikirtimo kartotinumą sudaro Karacubos gauto kartotinių trigonometrinių sumų įvertinimo pagrindą. Tegul  yra skaičių , tenkinančių sąlygą  bendras mažiausias kartotinis. Tuomet, kai , galioja įvertis
čia  yra skaičiaus  daliklių skaičius, o  yra skaičiaus  skirtingų pirminių daliklių skaičius.

Hardžio funkcijos Varingo problemoje įvertis

Pritaikęs Hardžio-Litlvudo-Vinogradovo metodo -adinė formą trigonometrinių sumų, kuriose yra sumuojama pagal skaičius su mažais pirminiais dalikliais vertinimui, Karacuba gavo naują įvertį gerai žinomoms Hardžio funkcijoms  Varingo problemoje, kai

Varingo problemos daugiamatis analogas

Toliau nagrinėdamas Varingo problemą, Karacuba gavo tokį dvimatį jos apibendrinimą.
Imkime lygčių sistemą
kurioje  yra duoti sveikieji teigiami skaičiai su tuo pačiu augimo greičiu, ,  ir  yra nežinomieji, kurie taip pat yra sveikieji teigiami skaičiai. Ši sistema turi sprendinių, kai , o kai , tai egzistuoja tokie , kad sistema neturi sprendinių.

Artino (Artin) problema apie lokalią nulio išraišką duotąja forma

Nagrinėdamas Artino problemą apie -adinę nulio išraišką bet kokio laipsnio forma, Karacuba priešingai egzistuojančiai hipotezei, kad nulio išreiškimui netrivialia forma reikia, jog kintamųjų skaičius augtų polinomiškai, įrodė, kad iš tikrųjų šis skaičius turėtų augti beveik eksponentiškai priklausomai nuo formos laipsnio.
Karacuba kartu su savo mokiniu Archipovu įrodė , kad su kiekvienu natūraliuoju  egzistuoja toks , kad su visais  yra mažesnio negu  laipsnio   kintamųjų su sveikais koeficientais forma  turinti tik trivialią nulio išraišką -adiniais skaičiais. Panašius rezultatus jie gavo su bet kuriuo nelyginiu pirminiu moduliu .

Selbergo hipotezė

1984 m. Karacuba įrodė, kad su fiksuotu ,  , pakankamai dideliu  ir  su  intervale  yra bent  Rymano dzeta funkcijos  realių nulių.
Šis nulių skaičius yra 1942 m. Atlės Selbergo (Atle Selberg) iškelta hipotezė, kurią jis pats ir įrodė atveju 
Šie Selbergo ir Karacubos įverčiai negali būti patikslinti augimo eilės atžvilgiu, kai

Rymano dzeta funkcijos nulių pasiskirstymas trumpuose kritinės tiesės intervaluose

Karacuba gavo eilę rezultatų apie funkcijos  nulių pasiskirstymą kritinėje tiesėje. Jis įrodė, jog Selbergo hipotezės analogas yra teisingas "beveik visiems" intervalams  su , kai  yra kiek norint mažas fiksuotas teigiamas skaičius. 1992 m. Karacuba išvystė naują Rymano dzeta funkcijos nulių labai trumpuose kritinės tiesės intervaluose  tyrinėjimo metodą, kai intervalo ilgis  auga lėčiau už bet kurį, kad ir labai mažą,  laipsnį. Be kita ko, jis įrodė, kad su bet kuriais  ir ,  , beveik visuose intervaluose  su  yra bent  funkcijos  nulių. Pastarasis įvertis labai mažai skiriasi nuo įverčio, kuris išplaukia iš Rymano hipotezės.

Dzeta funkcijos elgesys kritinėje tiesėje

Karacuba gavo eilę naujų rezultatų apie funkcijos , vadinamos Rymano dzeta funkcijos argumentu kritinėje tiesėje, elgesį. Čia  yra bet kurios tolydžios  šakos pokytis išilgai laužt{\. e}s, jungian{\v c}ios taškus ,  ir  Tarp tų rezultatų yra funkcijos  ir jos pirmojo integralo  vidurkių teoremos realiosios ties{\. e}s intervaluose bei teorema, tvirtinanti, jog intervale  su  yra bent  taškų, kuriuose funkcija  keičia ženklą. Anksčiau panašius rezultatus atveju  buvo gavęs Selbergas.

Paskutiniųjų metų darbai

Paskutiniaisiais gyvenimo metais be skaičių teorijos tyrimų Karacuba nagrinėjo ir kai kurias teorinės fizikos problemas, ypač kvantinės kūnų teorijos srityje. Pritaikęs savo ATS teoremą ir kai kuriuos kitus skaičių teorijos metodus, jis gavo naujus rezultatus apie Džeinso-Kamingso (Jaynes-Cummings) modelį kvantinėje optikoje.