Anatolij Alexejevič Karacuba

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie
Anatolij Alexejevič Karacuba
Anatolij Alexejevič Karacuba
ruský matematik

Narodenie 31. január 1937
Groznyj, Rusko, vtedy Ruská SSR, ZSSR
Úmrtie 28. september 2008 (71 rokov)
Moskva, Rusko

Anatolij Alexejevič Karacuba (rus. Анатолий Алексеевич Карацуба; 31. január 1937, Groznyj, Rusko, vtedy Ruská SSR, ZSSR28. 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.[upraviť | upraviť zdroj]

Karacuba za mlada.

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 nevídaný 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 obhájení dizertácie 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.

Ocenenia[upraviť | upraviť zdroj]

Prvé práce z informatiky[upraviť | upraviť zdroj]

Ako študent Moskovskej štátnej univerzity navštevoval Anatolij Karacuba seminár vedený Andrejom Nikolajevičom Kolmogorovom a vyriešil dva problémy formulované Kolmogorovom. 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[upraviť | upraviť zdroj]

Edward F. Moore definuje vo svojom článku [1] automat S typu (n; m;p) ako zariadenie, ktoré má

n stavov, reaguje na m vstupných symbolov a dáva na výstupe p symbolov. V spomínanej práci je vyslovených a dokázaných 9 viet o štruktúre S. Takéto automaty dostali neskôr meno Moorove automaty. V závere svojho článku Moore formuluje problém týkajúci sa zlepšenia odhadov zo svojich viet 8 a 9:

Veta 8 (Moore). Majme ľubovoľný (n; m; p) automat S, ktorého každé dva stavy sú rozlíšiteľné, potom existuje experiment dĺžky n(n-1)/2, ktorý určí stav automatu S.

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.

Veta A (Karacuba). Ak S je (n; m; p) - automat ktorého každé dva stavy sú rozlíšiteľné, tak existuje experiment dĺžky nanajvýš (n-1)(n-2)/2 + 1, ktorý identifikuje stav automatu S.
Veta B (Karacuba). Existuje (n; m; p) automat, ktorého každé dva stavy sú rozlíšiteľné, taký, že dĺžka najkratšieho experimentu, ktorým je možné zistiť jeho stav je rovná (n-1)(n-2)/2 + 1.

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[2]. 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[upraviť | upraviť zdroj]

Efektívne algoritmy predstavujú časť výpočtovej matematiky, ktorá študuje algoritmy vyčíslovania 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 M(n) je definovaná ako počet bitových operácií postačujúcich na vyčíslenie súčinu dvoch n-ciferných čísiel podľa zadaného algoritmu."

Ak uvažujeme násobenie dvoch n-ciferných celých čísiel bežnou školskou metódou "pod seba" dostaneme horný odhad M(n) = O(n^2). Andrej Kolmogorov vyslovil v roku 1956 hypotézu, že dolný odhad zložitosti M(n) je pre každý algoritmus násobenia tiež rádu n^2. Čiže, že nie je možné vyčísliť súčin dvoch n-ciferných celých čísiel rýchlejšie ako s pomocou n^2 operácií. Táto n^2 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 n-ciferných čísiel dnes známu ako Karacubov algoritmus. Jeho zložitosť je M(n) = O(n^{\log_23}) = O(n^{1,58496\ldots}), čo vyvracia n^2 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, ,[3], kde Kolmogorov prezentoval dva medzi sebou nesúvisiace výsledky dvoch svojich študentov. Kolmogorov presne uvádza, že jedna z viet (nezaoberajúca sa rýchlim 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 [4] a Strassenov algoritmus násobenia matíc. .[5] V posledných rokoch sa termín rozdeľuj a panuj používa pre algoritmy pri ktorých sa problém rozdelí na časti, a nemusí nutne ísť o priame spojenie s algoritmom rýchleho násobenia.

Francúzsky matematik a filozof Jean-Paul Delahaye[6] 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 nie len ako software ale aj ako hardware.

Práce v teórii čísiel[upraviť | upraviť zdroj]

A. Karacuba publikoval výsledky svojej vedeckej práce vo viac ako 160 odborných článkoch a napísal 5 monografií.[7][8][9][10][11]

Trigonometrické sumy a integrály[upraviť | upraviť zdroj]

p-adická metóda v odhade trigonometrických súm[upraviť | upraviť zdroj]

A. Karacuba objavil tzv. p-adickú metódu pre odhad istých trigonometrických súčtov, tzv. L-súm[12]

S = \sum_{x=1}^P e^{2\pi i (a_1x/p^n+ \dots a_nx^n/p)},
\quad (a_s,p) = 1, \quad 1 \le s \le n,

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[upraviť | upraviť zdroj]

V rokoch 1960 - 1980 sa A. Karacuba venoval teórii viacnásobných trigonometrických súm[13][14][15], teda súm tvaru

S = S(A) =
\sum_{x_1=1}^{P_1}\dots\sum_{x_r=1}^{P_r}e^{2\pi i
F(x_1,\dots,x_r)} , ãäå F(x_1,\dots,x_r) =
\sum_{t_1=1}^{n_1}\dots\sum_{t_r=1}^{n_r}\alpha(t_1,\dots,t_r)x_1^{t_1}\dots
x_r^{t_r} ,

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é

Nech n_1,\dots,n_r,P_1,\dots,P_r sú prirodzené čísla, P_1 = \min(P_1,\dots,P_r),m =
(n_1+1)\dots(n_r+1). Nech ďalej \Omega

je m-rozmerná kocka :: 0 \le
\alpha(t_1,\dots,t_r) < 1 , 0 \le t_1 \le n_1, \dots
,0 \le t_r \le n_r, v n-rozmernom Euklidovom priestore : and :: J
= J(P_1,\dots,P_r;n_1,\dots,n_r;K,r) =
\underset{\Omega}{\int\dots\int}|S(A)|^{2K} dA . : Potom pre každé \tau \ge 0 and K \ge K_{\tau} =
m\tau platí pre strednú hodnotu J nasledovný odhad

J \le
K_{\tau}^{2m\tau}\varkappa^{4\varkappa^2\Delta(\tau)}2^{8m\varkappa\tau}(P_1\dots
P_r)^{2K}P^{-\varkappa\Delta(\tau)} , : kde

\varkappa = n_1\nu_1+ \dots + n_r\nu_r , \gamma\varkappa = 1, \Delta(\tau) =
\frac{m}{2}(1-(1-\gamma)^{\tau}) , P =
(P_1^{n_1}\dots P_r^{n_r})^{\gamma}, a prirodzené čísla \nu_1, \dots , \nu_r sú takéto: :: -1 < \frac{P_s}{P_1} - \nu_s \le 0 , s=
1,\dots , r .

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 Q_0 najmenší spoločný násobok čísiel q(t_1,\dots,t_r) s podmienkou t_1 + \dots t_r \ge 1, pre Q_0
\ge P^{1/6}. Potom platí odhad

|S(A)| \le (5n^{2n})^{r\nu(Q_0)}(\tau(Q_0))^{r-1}P_1\dots
P_rQ^{-0.1\mu} + 2^{8r}(r\mu^{-1})^{r-1}P_1\dots
P_rP^{-0.05\mu} ,

kde \tau(Q) je počet deliteľov čísla Q a \nu(Q) je počet rôznych prvočíselných deliteľov čísla Q.

Odhad Hardyho funkcie vo Waringovom probléme[upraviť | upraviť zdroj]

Na základe p-adickej modifikácie Hardy-Littlewood-Ramanujan-Vinogradovovej metódy odhadu trigonometrických súm získal Karacuba[16] nový odhad známej Hardyho funkcie z tzv. Waringovho problému

\! G(n) < 2 n\log n + 2 n\log\log n + 12 n.

Viacrozmerná verzia Waringovho problému[upraviť | upraviť zdroj]

A Karacuba získal aj nasledovný výsledok vo viacrozmernom analógu Waringovho problému[17][18]

Uvažujme systém rovníc

x_1^{n-i}y_1^i + \dots + x_k^{n-i}y_k^i = N_i ,

i = 0,1,\dots, n ,

kde N_i sú dané celé kladné čísla rovnakého rádu N_0 \to +\infty. Nech ďalej x_{\varkappa},y_{\varkappa} sú neznáme, taktiež však kladné celé čísla. Potom uvedená sústava rovníc má riešenie ak k >
cn^2\log n a, z druhej strany, ak k < c_1n^2, tak existujú čísla N_i, že sústava riešenie nemá.

Riemannova zeta-funkcia[upraviť | upraviť zdroj]

Selbergova hypotéza[upraviť | upraviť zdroj]

V roku 1984 A. Karacuba dokázal[19][20][21], že pre každé pevné \varepsilon, spĺňajúce podmienku 0<\varepsilon < 0.001 a pre dostatočne veľké T a H = T^{a+\varepsilon}, a =
\tfrac{27}{82} = \tfrac{1}{3} -\tfrac{1}{246} je pravda, že interval (T,T+H) obsahuje najmenej cH\ln T núl funkcie \zeta\Bigl(\tfrac{1}{2}+it\Bigr), kde z\mapsto \zeta(z) 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 H\ge T^{1/2+\varepsilon}. Vie sa, že Selbergov a Karacubov odhad sa už nedajú zlepšiť, čo sa týka rádu rastu pri T\to +\infty.

Rozloženie núl Riemannovej zeta-funkcii na krátkych úsekoch na kritickej priamke[upraviť | upraviť zdroj]

A. Karacuba získal viaceré výsledky [22] 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 (T,T+H], H = T^{\varepsilon}, kde \varepsilon je ľubovoľné malé kladné číslo. V roku 1992 objavil A. Karacuba novú metódu skúmania núl Riemannovej zeta-funkcie na superkrátkych intervaloch na kritickej priamke, (T,
T+H], ktorých dĺžka H rastie s T pomalšie ako akákoľvek kladná mocnina T. Špeciálne A. Karacuba dokázal, že pre každé čísla \varepsilon, \varepsilon_{1} spĺňajúce podmienky 0<\varepsilon, \varepsilon_{1}<1 platí, že takmer všetky intervaly (T,T+H] s H\ge\exp{\{(\ln
T)^{\varepsilon}\}} obsahujú aspoň H(\ln
T)^{1-\varepsilon_{1}} núl Riemannovej zeta-funkcie. Tento odhad je blízky dôležitého odhadu plynúceho z Riemannovej hypotézy.

Referencie[upraviť | upraviť zdroj]

  1. Moore, E. F. (1956). "Gedanken-experiments on Sequential Machines.". Automata Studies, Annals of Mathematical Studies, Princeton University Press, Princeton, N.J., (34): 129–153.
  2. Karatsuba, A. A. (1960). "Solution of one problem from the theory of finite automata". Usp. Mat. Nauk (15:3): 157– 59.
  3. Karatsuba A., Ofman Yu.: Multiplication of multidigit numbers on automata. Soviet Physics-Doklady, 7, 595–596 (1963); translation from Dokl. Akad. Nauk SSSR, 145:2, 293–294, (1962).
  4. Schonhage A., Strassen V.: Schnelle Multiplikation grosser Zahlen, 1971, Computing, Vol. 7,pages=281–292
  5. Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354—356, 1969
  6. Delahaye, Jean-Paul (2000). "Mathematiquest philosophie". Pour la Science (277): 100–104.
  7. KARATSUBA, A. A. (1975). Principles of analytic number theory.. Moscow: Nauka.
  8. G. I. Archipov, A. A. Karatsuba, V. N. Chubarikov (1987). Theory of multiple trigonometric sums.. Moscow: Nauka.
  9. A. A. Karatsuba, S. M. Voronin (1994). The Riemann Zeta Function.. Moscow: Fiz.Mat.Lit..
  10. {{cite book|first= A. A. |last=Karatsuba| title= Complex analysis in number theory.|location= London, Tokyo: C.R.C.| year= 1995}}
  11. A. A. Karatsuba, M. A. Korolev (...). Encyclopedia of Number Theory.. Moscow: Nauka.
  12. Karatsuba, A. A. (1961). "Estimates of trigonometric sums of a special form and their applications". Dokl. Akad. Nauk SSSR (137:3): 513–514.
  13. Karatsuba, A. A. (1966). "The mean value theorems and complete trigonometric sums". Izv. Akad. Nauk SSSR, Ser. Mat. (30:1): 183–206.
  14. {{cite journal|author= I. M. Vinogradov, A. A. Karatsuba| title= The method of trigonometric sums in number theory| pages=4–30| journal= Proc. Steklov Inst. Math.| issue=168| year=1984}}
  15. G. I. Archipov, A. A. Karatsuba, V. N. Chubarikov (1987). "Theory of multiple trigonometric sums". M.: Nauka.
  16. Karatsuba, A. A. (1985). "On the function G(n) in Waring's problem". Izv. Akad. Nauk SSSR, Ser. Math. (49:5): 935–947.
  17. G. I. Archipov, A. A. Karatsuba (1987). "A multidimensional analogue of Waring's problem". Dokl. Akad. Nauk SSSR (295:3): 521–523.
  18. Karatsuba, A. A. (1988). "Waring's problem in several dimension". Mathem. Forschungs, Oberwolfach, Tagungsbericht (42): 5–6.
  19. Karatsuba, A. A. (1984). "On the zeros of the function ?(s) on short intervals of the critical line". Izv. Akad. Nauk SSSR, Ser. Mat. (48:3): 569–584.
  20. {{cite journal| first=A. A.| last=Karatsuba|title= The distribution of zeros of the function ?(1/2+it)| pages=1214–1224 | journal= Izv. Akad. Nauk SSSR, Ser. Mat.| issue=48:6| year=1984}}
  21. Karatsuba, A. A. (1985). "On the zeros of the Riemann zeta-function on the critical line". Proc. Steklov Inst. Math. (167): 167–178.
  22. Karatsuba, A. A. (1992). "On the number of zeros of the Riemann zeta-function lying in almost all short intervals of the critical line". Izv. Ross. Akad. Nauk, Ser. Mat. (56:2): 372–397.

Iné projekty[upraviť | upraviť zdroj]