Anatolij Alexejevič Karacuba

Anatolij Alexejevič Karacuba (; 31. január 1937, Groznyj, Rusko, vtedy Ruská SSR, ZSSR — 28. september 2008, Moskva, Rusko) bol ruský matematik, autor prvého efektívneho algoritmu na násobenie veľkých čísiel.
Štúdium a práca.
Anatolij Karacuba študoval v rokoch 1944 - 1954 na chlapčenskej strednej škole v Groznom, ktorú ukončil s vyznamenaním. Už v mladých rokoch preukázal neobyčajný matematický talent. Ako žiak prvých ročníkov riešil úlohy zadávané študentom posledných ročníkov. 
V roku 1959 dokončil úspešne štúdium na Lomonosovovej Moskovskej štátnej univerzite, na Katedre matematiky a mechaniky. Titul kandidát vied získal v roku 1962 vypracovaním dizertácie na tému "Špeciálne racionálne trigonometrické sumy a ich aplikácie". Vedúcim jeho práce bol N. M. Korobov. Po jej obhájení začal Karacuba pracovať na Katedre matematiky a mechaniky Moskovskej štátnej univerzity. V roku 1966 získal titul doktor vied v odbore matematika s prácou "Metóda trigonometrických súm a vety o stredných hodnotách" a stal sa členom matematického ústavu V. A. Steklova AV ZSSR. 
Po roku 1983 bol Anatolij Karacuba považovaný za jedného z popredných sovietskych odborníkov a výskumníkov v oblasti teórie čísiel. Bol vedúcim oddelenia teórie čísiel Steklovovho inštitútu, profesorom na oddelení teórie čísiel Moskovskej štátnej univerzity (od roku 1970) a profesorom na oddelení matematickej analýzy Moskovskej štátnej univerzity (od roku 1980). Jeho výskum bol zameraný na trigonometrické rady a integrály, Riemannovu zeta funkciu, konečné automaty a efektívne algoritmy. 
A. Karacuba vyškolil 15 doktorandov, sedem z nich neskôr získalo titul doktor vied.
Prvé práce z informatiky.
Ako študent Moskovskej štátnej univerzity navštevoval Anatolij Karacuba seminár vedený Andrejom Nikolajevičom Kolmogorovom a vyriešil dva problémy, ktoré Kolmogorov formuloval. Tieto problémy boli podstatné pre rozvoj teórie automatov a ich vyriešenie odštartovalo nový smer v matematike, teóriu efektívnych algoritmov. 
Automaty.
Edward F. Moore definuje vo svojom článku „Gedanken-experiments on Sequential Machines“ automat formula_1 typu formula_2 ako zariadenie, ktoré má formula_3 stavov, reaguje na formula_4 vstupných symbolov a dáva na výstupe formula_5 symbolov. V spomínanej práci je vyslovených a dokázaných 9 viet o štruktúre formula_1. Takéto automaty dostali neskôr meno Moorove automaty. V závere svojho článku formuluje problém týkajúci sa zlepšenia odhadov zo svojich viet 8 a 9: 
Karacuba dokázal v roku 1957 dve vety, ktoré dávajú úplnú odpoveď na Moorov problém týkajúci sa zlepšenia odhadu v jeho Vete 8. 
Tieto dve vety dokázal Karacuba v štvrtom ročníku univerzity v rámci ročníkového projektu. Príslušný článok bol publikovaný v júni 1960. Až do dnes (12.04.2010) táto tzv. Moore-Karacubova veta ostáva jediným presným nelineárnym odhadom v teórii automatov a podobných problémoch teórie výpočtovej zložitosti.
Efektívne algoritmy.
Efektívne algoritmy predstavujú časť výpočtovej matematiky, ktorá študuje algoritmy vyčísľovania danej funkcie s danou presnosťou za podmienky použitia čo najmenšieho počtu bitových operácií. Za predpokladu, že je číslo zadané v dvojkovej sústave, sa znaky 0 a 1 nazývajú bity (analógia cifier v desiatkovej sústave). Jedna bitová operácia je definovaná ako zapísanie niektorého zo znakov 0, 1, plus, mínus alebo zátvorka, ďalej zreťazenie, odčítanie a súčet dvoch bitov. Andrej Nikolajevič Kolmogorov ako prvý sformuloval problém o bitovej zložitosti vyčíslenia. "Zložitosť násobenia formula_17 je definovaná ako počet bitových operácií postačujúcich na vyčíslenie súčinu dvoch formula_3-ciferných čísiel podľa zadaného algoritmu."
Ak uvažujeme násobenie dvoch formula_3-ciferných celých čísiel bežnou školskou metódou "pod seba" dostaneme horný odhad formula_20. Andrej Kolmogorov vyslovil v roku 1956 hypotézu, že dolný odhad zložitosti formula_17 je pre každý algoritmus násobenia tiež rádu formula_22. Čiže, že nie je možné vyčísliť súčin dvoch formula_3-ciferných celých čísiel rýchlejšie ako s pomocou formula_22 operácií. 
Táto "formula_22 hypotéza" sa zdala byť prijateľnou, nakoľko v celej histórii nebol známy žiadny rýchlejší algoritmus násobenia a zdalo sa, že ak by nejaký rýchlejší algoritmus existoval, už by ho niekto objavil. 
A. Karacuba však našiel v roku 1960 novú metódu násobenia dvoch formula_3-ciferných čísiel dnes známu ako Karacubov algoritmus. Jeho zložitosť je formula_27 čo vyvracia "formula_22 hypotézu". Tento svoj výsledok prezentoval Karacuba na Kolmogorovom seminári na Moskovskej štátnej univerzite, čím sa aj zavŕšila činnosť tohoto semináru. Prvú prácu, ktorá vysvetľovala nový algoritmus pripravil sám Kolmogorov, kde prezentoval dva medzi sebou nesúvisiace výsledky dvoch svojich študentov. Kolmogorov presne uvádza, že jedna z viet (nezaoberajúca sa rýchlym násobením) patrí J. Ofmanovi a druhá veta (opisujúca prvý rýchly algoritmus násobenia) patrí A. Karacubovi. Karacubov algoritmus sa zvykne nazývať aj "metóda rozdeľuj a panuj", "binárne rozštiepenie", či "princíp dichotómie". 
Na základe Karacubovej myšlienky bolo neskôr nájdené množstvo ďalších rýchlych algoritmov. Z nich najznámejšie sú priame zovšeobecnenia Karacubovho algoritmu, ako sú Schönhage–Strassenov algoritmus 
 a Strassenov algoritmus násobenia matíc. V posledných rokoch sa termín "rozdeľuj a panuj" používa pre algoritmy, pri ktorých sa problém rozdelí na časti; nemusí nutne ísť o priame spojenie s algoritmom rýchleho násobenia. 
Francúzsky matematik a filozof Jean-Paul Delahaye sa odvoláva na Karacubov algoritmus ako na "«jeden z najužitočnejších výsledkov matematiky»." 
Karacubov algoritmus je implementovaný v každom modernom počítači a to nielen ako softvér ale aj ako hardvér. 
Práce v teórii čísiel.
A. Karacuba publikoval výsledky svojej vedeckej práce vo viac ako 160 odborných článkoch a napísal 5 monografií. 
Trigonometrické sumy a integrály.
"p"-adická metóda v odhade trigonometrických súm.
A. Karacuba objavil tzv. formula_5-adickú metódu pre odhad istých trigonometrických súčtov, tzv. formula_30-súm 
Význam jeho odhadov spočíva najmä v tom, že umožňujú presnejšiu lokalizáciu núl tzv. Dirichletových "L"-radov.
Viacnásobné trigonometrické sumy.
V rokoch 1960 - 1980 sa A. Karacuba venoval teórii viacnásobných trigonometrických súm, teda súm tvaru 
Kľúčovým výsledkom Karacubovej teórie je istá veta o strednej hodnote, podobne ako je to aj vo Vinogradovovej teórii trigonometrických súm. Tvrdenie vety je nasledovné 
Táto veta o strednej hodnote spolu s lemmou o počte priesekov s mnohorozmerným rovnobežnostenom sú základom pre Karacubov odhad veľkosti násobnej trigonometrickej sumy. Označme znakom formula_53 najmenší spoločný násobok čísiel formula_54 s podmienkou formula_55, pre formula_56. Potom platí odhad 
kde formula_58 je počet deliteľov čísla formula_59 a formula_60 je počet rôznych prvočíselných deliteľov čísla formula_59. 
Odhad Hardyho funkcie vo Waringovom probléme.
Na základe formula_5-adickej modifikácie Hardy-Littlewood-Ramanujan-Vinogradovovej metódy odhadu trigonometrických súm získal Karacuba nový odhad známej Hardyho funkcie z tzv. Waringovho problému: 
Viacrozmerná verzia Waringovho problému.
A Karacuba získal aj nasledovný výsledok vo viacrozmernom analógu Waringovho problému: 
Uvažujme systém rovníc 
formula_65, 
kde formula_66 sú dané celé kladné čísla rovnakého rádu formula_67. Nech ďalej formula_68 sú neznáme, taktiež však kladné celé čísla. Potom uvedená sústava rovníc má riešenie ak formula_69 a, z druhej strany, ak formula_70, tak existujú čísla formula_66, že sústava riešenie nemá.
Riemannova zeta-funkcia.
Selbergova hypotéza.
V roku 1984 A. Karacuba dokázal, že pre každé pevné formula_72, spĺňajúce podmienku formula_73 a pre dostatočne veľké formula_74 a formula_75, formula_76 je pravda, že interval formula_77 obsahuje najmenej formula_78 núl funkcie formula_79, kde formula_80 je Riemannova zeta-funkcia. 
Uvedené tvrdenie vyslovil ako hypotézu A. Selberg v roku 1942 a sám ho aj dokázal pre prípad formula_81. Vie sa, že Selbergov a Karacubov odhad sa už nedajú zlepšiť, čo sa týka rádu rastu pri formula_82. 
Rozloženie núl Riemannovej zeta-funkcii na krátkych úsekoch na kritickej priamke.
A. Karacuba získal viaceré výsledky týkajúce sa početnosti núl Riemannovej zeta-funkcie na krátkych intervaloch ležiacich na kritickej priamke. Dokázal, že analóg Selbergovej hypotézy platí pre takmer všetky intervaly formula_83, formula_84, kde formula_72 je ľubovoľné malé kladné číslo. V roku 1992 objavil novú metódu skúmania núl Riemannovej zeta-funkcie na "superkrátkych" intervaloch na kritickej priamke, formula_86, ktorých dĺžka formula_87 rastie s formula_74 pomalšie ako akákoľvek kladná mocnina formula_74. Špeciálne dokázal, že pre každé čísla formula_72, formula_91 spĺňajúce podmienky formula_92 platí, že takmer všetky intervaly formula_83 s formula_94 obsahujú aspoň formula_95 núl Riemannovej zeta-funkcie. Tento odhad je blízky dôležitého odhadu plynúceho z Riemannovej hypotézy.