Anatoly Karatsuba - Anatoly Karatsuba

Anatolij Alexejevič Karatsuba
narozený	(1937-01-31)31. ledna 1937 Groznyj, Sovětský svaz
Zemřel	28. září 2008(2008-09-28) (ve věku 71) Moskva, Rusko
Národnost	ruština
Alma mater	Moskevská státní univerzita
Vědecká kariéra
Pole	Matematik

Anatolij Alexejevič Karatsuba (jeho křestní jméno bylo často hláskováno Anatolii) (ruština: Анато́лий Алексе́евич Карацу́ба; Groznyj, Sovětský svaz 31. ledna 1937 - Moskva, Rusko, 28. září 2008^[1]) byl ruština matematik pracující v oboru analytická teorie čísel, str-adická čísla a Dirichletova řada.

Po většinu svého studentského a profesního života byl spojován s Fakulta mechaniky a matematiky z Moskevská státní univerzita, bránící a D.Sc. tam s názvem „Metoda trigonometrických součtů a teorémů střední hodnoty“ v roce 1966.^[2] Později zastával pozici u Steklovův matematický ústav z Akademie věd.^[2]

Jeho učebnice Základy Teorie analytického čísla šel do dvou vydání, 1975 a 1983.^[2]

The Algoritmus Karatsuba je nejdříve známá algoritmus rozděl a panuj pro násobení a žije dál jako speciální případ jeho přímé generalizace, Algoritmus Toom – Cook.^[3]

Hlavní výzkumné práce Anatolije Karatsuby byly publikovány ve více než 160 výzkumných pracích a monografiích.^[4]

Jeho dcera, Yekaterina Karatsuba, také matematik, zkonstruoval FEE metoda.

Ocenění a tituly

• 1981: Cena P.L.Tchebysheva Sovětské akademie věd
• 1999: Významný vědec Ruska
• 2001: I.M. Vinogradovova cena Ruské akademie věd

Rané práce na informatice

Jako student Moskevské státní univerzity v Lomonosově se Karatsuba zúčastnil semináře Andrey Kolmogorov a našel řešení dvou problémů, které nastolil Kolmogorov. To bylo zásadní pro vývoj teorie automatů a začalo nové odvětví v matematice, teorie rychlých algoritmů.

Automaty

V novinách Edward F. Moore,^[5] ${displaystyle (n; m; p)}$, automat (nebo stroj) ${displaystyle S}$, je definováno jako zařízení s ${displaystyle n}$ státy, ${displaystyle m}$ vstupní symboly a ${displaystyle p}$ výstupní symboly. Devět vět o struktuře ${displaystyle S}$ a experimenty s ${displaystyle S}$ jsou prokázány. Později takové ${displaystyle S}$ stroje dostal jméno Stroje Moore. Na konci příspěvku v kapitole «Nové problémy» Moore formuluje problém zlepšení odhadů, které získal ve větách 8 a 9:

Věta 8 (Moore). Dáno svévolně ${displaystyle (n; m; p)}$ stroj ${displaystyle S}$, takže každé dva stavy lze navzájem odlišit, existuje experiment délky ${displaystyle n (n-1) / 2}$ který identifikuje stav ${displaystyle S}$ na konci tohoto experimentu.

V roce 1957 Karatsuba prokázal dvě věty, které zcela vyřešily Mooreův problém při zlepšování odhadu délky experimentu v jeho Věta 8.

Teorém A (Karatsuba). Li ${displaystyle S}$ je ${displaystyle (n; m; p)}$ stroj tak, že každé dva jeho stavy lze od sebe odlišit, pak existuje nanejvýš rozvětvený experiment délky ${displaystyle (n-1) (n-2) / 2 + 1}$, pomocí kterého lze najít stát ${displaystyle S}$ na konci experimentu.

Teorém B (Karatsuba). Existuje a ${displaystyle (n; m; p)}$ stroj, jehož každý stav lze od sebe odlišit, takže délka nejkratšího experimentu, který na konci experimentu zjistí stav stroje, se rovná ${displaystyle (n-1) (n-2) / 2 + 1}$.

Tyto dvě věty dokázal Karatsuba ve svém 4. ročníku jako základ svého projektu ve 4. ročníku; odpovídající příspěvek byl předložen do časopisu "Uspekhi Mat. Nauk" dne 17. prosince 1958 a publikován v červnu 1960.^[6] Dodnes (2011) tento výsledek Karatsuba, který později získal titul „Moore-Karatsuba teorém“, zůstává jediným přesným (jediným přesným nelineárním řádem odhadu) nelineárním výsledkem jak v teorii automatů, tak v v podobných problémech teorie složitosti výpočtů.

Pracuje v teorii čísel

Hlavní výzkumné práce A.A.Karatsuba byly publikovány ve více než 160 výzkumných pracích a monografiích.^{[7][8][9][10]}

The str- adická metoda

A.A.Karatsuba postavil nový ${displaystyle p}$-adická metoda v teorii trigonometrických součtů.^[11] Odhady tzv ${displaystyle L}$- součty formuláře

${displaystyle S = součet _ {x = 1} ^ {P} e ^ {2pi i (a_ {1} x / p ^ {n} + tečky a_ {n} x ^ {n} / p)}, kvadrant ( a_ {s}, p) = 1, quad 1leq sleq n,}$

vedený^[12] do nových mezí pro nuly Dirichlet ${displaystyle L}$-series modulo mocninu prvočísla, k asymptotickému vzorci pro počet Waringovy kongruence tvaru

${displaystyle x_ {1} ^ {n} + tečky + x_ {t} ^ {n} ekviv N {pmod {p ^ {k}}}, quad 1leq x_ {s} leq P, quad 1leq sleq n, quad P$

k řešení problému distribuce zlomkových částí polynomu s celočíselnými koeficienty modulo ${displaystyle p ^ {k}}$. A.A. Karatsuba si to uvědomil jako první^[13] v ${displaystyle p}$-adická forma «principu vkládání» Eulera-Vinogradova a vypočítat a ${displaystyle p}$-adický analog Vinogradova ${displaystyle u}$-čísla při odhadu počtu řešení kongruence typu Waring.

Předpokládat, že : ${displaystyle x_ {1} ^ {n} + tečky + x_ {t} ^ {n} ekviv N {pmod {Q}}, quad 1leq x_ {s} leq P, quad 1leq sleq t, quad (1)}$ a navíc: ${displaystyle P ^ {r} leq Q$

kde ${displaystyle p}$ je prvočíslo. Karatsuba to v tom případě dokázal pro jakékoli přirozené číslo ${displaystyle ngeq 144}$ existuje a ${displaystyle p_ {0} = p_ {0} (n)}$ takový, že pro každého ${displaystyle p_ {0}> p_ {0} (n)}$ každé přirozené číslo ${displaystyle N}$ mohou být zastoupeny ve formě (1) pro ${displaystyle tgeq 20r + 1}$, a pro ${displaystyle t$ existují ${displaystyle N}$ taková, že kongruence (1) nemá žádná řešení.

Tento nový přístup, který našel Karatsuba, vedl k novému ${displaystyle p}$-adic důkaz o Vinogradov věta o střední hodnotě, která hraje ústřední roli ve Vinogradovově metodě trigonometrických součtů.

Další složka ${displaystyle p}$- adická metoda A.A. Karatsuba je přechod od neúplných systémů rovnic k úplným na úkor místních ${displaystyle p}$-adická změna neznámých.^[14]

Nechat ${displaystyle r}$ být libovolné přirozené číslo, ${displaystyle 1leq rleq n}$. Určete celé číslo ${displaystyle t}$ nerovnostmi ${displaystyle m_ {t} leq rleq m_ {t + 1}}$. Uvažujme soustavu rovnic

${displaystyle {egin {cases} x_ {1} ^ {m_ {1}} + tečky + x_ {k} ^ {m_ {1}} = y_ {1} ^ {m_ {1}} + tečky + y_ {k } ^ {m_ {1}} tečky tečky tečky tečky tečky tečky tečky tečky tečky x_ {1} ^ {m_ {s}} + tečky + x_ {k} ^ {m_ {s}} = y_ {1} ^ { m_ {s}} + tečky + y_ {k} ^ {m_ {s}} x_ {1} ^ {n} + tečky + x_ {k} ^ {n} = y_ {1} ^ {n} + tečky + y_ {k} ^ {n} konec {případů}}}$

${displaystyle 1leq x_ {1}, tečky, x_ {k}, y_ {1}, tečky, y_ {k} leq P, quad 1leq m_ {1}$

Karatsuba prokázal, že počet řešení ${displaystyle I_ {k}}$ tohoto systému rovnic pro ${displaystyle kgeq 6rnlog n}$ vyhovuje odhadu

${displaystyle I_ {k} ll P ^ {2k-delta}, quad delta = m_ {1} + dots + m_ {t} + (s-t + 1) r.}$

U neúplných systémů rovnic, ve kterých proměnné procházejí čísly s malými prvočíslnými děliteli, použil Karatsuba multiplikativní překlad proměnných. To vedlo k v podstatě novému odhadu trigonometrických součtů a nové větě o střední hodnotě pro takové systémy rovnic.

Problém Hua Luogenga na exponenciálním konvergenci singulárního integrálu v Terryho problému

${displaystyle p}$-adická metoda AAKaratsuba zahrnuje techniky odhadu míry množiny bodů s malými hodnotami funkcí z hlediska hodnot jejich parametrů (koeficientů atd.) a naopak techniky odhadu těchto parametrů z hlediska míra této množiny v reálném a ${displaystyle p}$-adické metriky. Tato stránka Karatsubovy metody se projevila obzvláště jasně v odhadu trigonometrických integrálů, což vedlo k řešení problému Hua Luogeng. V roce 1979 Karatsuba spolu se svými studenty G.I. Arkhipov a V.N. Chubarikov získal kompletní řešení^[15] problému Hua Luogeng najít exponent konvergence integrálu:

${displaystyle vartheta _ {0} = int limity _ {- infty} ^ {+ infty} cdots int limity _ {- infty} ^ {+ infty} {iggl |} int limity _ {0} ^ {1} e ^ { 2pi i (alpha _ {n} x ^ {n} + cdots + alpha _ {1} x)} dx {iggr |} ^ {2k} dalpha _ {n} ldots dalpha _ {1},}$

kde ${displaystyle ngeq 2}$ je pevné číslo.

V tomto případě exponent konvergence znamená hodnotu ${displaystyle gamma}$, takový, že ${displaystyle vartheta _ {0}}$ konverguje pro ${displaystyle 2k> gamma + varepsilon}$ a rozcházejí se ${displaystyle 2k$, kde ${displaystyle varepsilon> 0}$ je libovolně malý. Ukázalo se, že integrál ${displaystyle vartheta _ {0}}$ konverguje pro ${displaystyle 2k> {frac {1} {2}} (n ^ {2} + n) +1}$ a rozcházejí se ${displaystyle 2kleq {frac {1} {2}} (n ^ {2} + n) +1}$.

Současně byl vyřešen podobný problém integrálu: ${displaystyle vartheta _ {1} = int _ {- infty} ^ {+ infty} cdots int _ {- infty} ^ {+ infty} {iggl |} int _ {0} ^ {1} e ^ {2pi i ( alpha _ {n} x ^ {n} + alpha _ {m} x ^ {m} + cdots + alpha _ {r} x ^ {r})} dx {iggr |} ^ {2k} dalpha _ {n} dalpha _ {m} ldots dalpha _ {r},}$ kde ${displaystyle n, m, ldots, r}$ jsou celá čísla, splňující podmínky: ${displaystyle 1leq r$

Karatsuba a jeho studenti dokázali, že integrál ${displaystyle vartheta _ {1}}$ konverguje, pokud ${displaystyle 2k> n + m + ldots + r}$ a liší se, pokud ${displaystyle 2kleq n + m + ldots + r}$.

Integrály ${displaystyle vartheta _ {0}}$ a ${displaystyle vartheta _ {1}}$ vznikají při studiu tzv Prouhet – Tarry – Escott problém. Karatsuba a jeho studenti získali řadu nových výsledků souvisejících s vícerozměrným analogem Tarryho problému. Zejména prokázali, že pokud ${displaystyle F}$ je polynom v ${displaystyle r}$ proměnné (${displaystyle rgeq 2}$) formuláře:${displaystyle F (x_ {1}, ldots, x_ {r}), =, limity součtu _ {u _ {1} = 0} ^ {n_ {1}} limity součtu cdots _ {u _ {r} = 0 } ^ {n_ {r}} alfa (u _ {1}, ldots, u _ {r}) x_ {1} ^ {u _ {1}} ldots x_ {r} ^ {u _ {r}}, }$ s nulovým volným termínem, ${displaystyle m = (n_ {1} +1) ldots (n_ {r} +1) -1}$, ${displaystyle {ar {alpha}}}$ je ${displaystyle m}$-dimenzionální vektor, skládající se z koeficientů ${displaystyle F}$, pak integrál: ${displaystyle vartheta _ {2} = int limity _ {- infty} ^ {+ infty} cdots int limity _ {- infty} ^ {+ infty} {iggl |} int limity _ {0} ^ {1} cdots int limity _ {0} ^ {1} e ^ {2pi iF (x_ {1}, ldots, x_ {r})} dx_ {1} ldots dx_ {r} {iggr |} ^ {2k} d {ar {alpha} }}$ konverguje pro ${displaystyle 2k> mn}$, kde ${displaystyle n}$ je nejvyšší z čísel ${displaystyle n_ {1}, ldots, n_ {r}}$. Tento výsledek, který není konečný, vygeneroval novou oblast v teorii trigonometrických integrálů, spojenou se zlepšením hranic exponentu konvergence ${displaystyle vartheta _ {2}}$ (I. A. Ikromov, M. A. Chahkiev a další).

Více trigonometrických součtů

V letech 1966—1980 se vyvinula Karatsuba^[16][17] (za účasti jeho studentů G.I. Arkhipova a V.N. Chubarikova) teorie násobku Hermann Weyl trigonometrické součty, tj. součty formuláře

${displaystyle S = S (A) = součet _ {x_ {1} = 1} ^ {P_ {1}} součet bodů _ {x_ {r} = 1} ^ {P_ {r}} e ^ {2pi iF ( x_ {1}, tečky, x_ {r})}}$ , kde ${displaystyle F (x_ {1}, tečky, x_ {r}) = součet _ {t_ {1} = 1} ^ {n_ {1}} součet bodů _ {t_ {r} = 1} ^ {n_ {r }} alfa (t_ {1}, tečky, t_ {r}) x_ {1} ^ {t_ {1}} tečky x_ {r} ^ {t_ {r}}}$ ,

${displaystyle A}$ je systém reálných koeficientů ${displaystyle alpha (t_ {1}, tečky, t_ {r})}$. Ústředním bodem této teorie, stejně jako v teorii vinogradovských trigonometrických součtů, je následující věta o střední hodnotě.

Nechat ${displaystyle n_ {1}, tečky, n_ {r}, P_ {1}, tečky, P_ {r}}$ být přirozená čísla, ${displaystyle P_ {1} = min (P_ {1}, tečky, P_ {r})}$,${displaystyle m = (n_ {1} +1) tečky (n_ {r} +1)}$. Kromě toho ${displaystyle Omega}$ být ${displaystyle m}$-rozměrná krychle formy :: ${displaystyle 0leq alpha (t_ {1}, tečky, t_ {r}) <1}$ , ${displaystyle 0leq t_ {1} leq n_ {1}, tečky, 0leq t_ {r} leq n_ {r}}$, v euklidovském prostoru: a :: ${displaystyle J = J (P_ {1}, tečky, P_ {r}; n_ {1}, tečky, n_ {r}; K, r) = {podmnožina {Omega} {int tečky int}} | S (A ) | ^ {2K} dA}$ . : Pak pro všechny ${displaystyle au geq 0}$ a ${displaystyle Kgeq K_ {au} = m au}$ hodnota ${displaystyle J}$ lze odhadnout následovně

${displaystyle Jleq K_ {au} ^ {2m au} varkappa ^ {4varkappa ^ {2} Delta (au)} 2 ^ {8mvarkappa au} (P_ {1} tečky P_ {r}) ^ {2K} P ^ {- varkappa Delta (au)}}$ , :

kde ${displaystyle varkappa = n_ {1} u _ {1} + tečky + n_ {r} u _ {r}}$ , ${displaystyle gamma varkappa = 1}$, ${displaystyle Delta (au) = {frac {m} {2}} (1- (1-gamma) ^ {au})}$ , ${displaystyle P = (P_ {1} ^ {n_ {1}} tečky P_ {r} ^ {n_ {r}}) ^ {gamma}}$a přirozená čísla ${displaystyle u _ {1}, tečky, u _ {r}}$ jsou takové, že: :: ${displaystyle -1 <{frac {P_ {s}} {P_ {1}}} - u _ {s} leq 0}$ , ${displaystyle s = 1, tečky, r}$ .

Věta o střední hodnotě a lemma o multiplicitě průniku vícerozměrných rovnoběžnostěn tvoří základ odhadu vícenásobného trigonometrického součtu, který získal Karatsuba (dvourozměrný případ odvodil G.I. Arkhipov^[18]). Označující ${displaystyle Q_ {0}}$ nejmenší společný násobek čísel ${displaystyle q (t_ {1}, tečky, t_ {r})}$ s podmínkou ${displaystyle t_ {1} + tečky t_ {r} geq 1}$, pro ${displaystyle Q_ {0} geq P ^ {1/6}}$ odhad platí

${displaystyle | S (A) | leq (5n ^ {2n}) ^ {ru (Q_ {0})} (au (Q_ {0})) ^ {r-1} P_ {1} tečky P_ {r} Q ^ {- 0,1 mu} + 2 ^ {8r} (rmu ^ {- 1}) ^ {r-1} P_ {1} tečky P_ {r} P ^ {- 0,05mu}}$ ,

kde ${displaystyle au (Q)}$ je počet dělitelů celého čísla ${displaystyle Q}$, a ${displaystyle u (Q)}$ je počet zřetelných dělitelů čísla ${displaystyle Q}$.

Odhad Hardyho funkce v Waringově problému

Použití jeho ${displaystyle p}$-adická forma metody Hardy-Littlewood-Ramanujan-Vinogradov k odhadu trigonometrických součtů, ve kterých je součet převzat z čísel s malými prvočíslnými děliteli, získal Karatsuba^[19] nový odhad dobře známých Hardy funkce ${displaystyle G (n)}$ v Waringův problém (pro ${displaystyle ngeq 400}$):

${displaystyle! G (n) <2nlog n + 2nlog log n + 12n.}$

Vícerozměrný analog Waringova problému

Při svém následném vyšetřování Waringova problému získal Karatsuba^[20] následující dvourozměrné zobecnění tohoto problému:

Uvažujme soustavu rovnic

${displaystyle x_ {1} ^ {n-i} y_ {1} ^ {i} + tečky + x_ {k} ^ {n-i} y_ {k} ^ {i} = N_ {i}}$ , ${displaystyle i = 0,1, tečky, n}$ ,

kde ${displaystyle N_ {i}}$ jsou dána kladná celá čísla se stejným řádem nebo růstem, ${displaystyle N_ {0} o + infty}$, a ${displaystyle x_ {varkappa}, y_ {varkappa}}$ jsou neznámá, což jsou také kladná celá čísla. Tento systém má řešení, pokud ${displaystyle k> cn ^ {2} přihlásit se}$ , a pokud ${displaystyle k$, pak existují takové ${displaystyle N_ {i}}$, že systém nemá žádná řešení.

Artinův problém lokálního znázornění nuly formou

Emil Artin způsobil problém na ${displaystyle p}$-adické vyjádření nuly formou libovolného stupně d. Artin původně předpokládal výsledek, který by nyní byl popsán jako p-adické pole být C₂ pole; jinými slovy by došlo k netriviální reprezentaci nuly, pokud by byl počet proměnných alespoň d². Ukázalo se, že tomu tak není Guy Terjanian. Karatsuba ukázal, že aby měl netriviální zastoupení nuly formou, měl by počet proměnných růst v míře rychleji než polynomiálně d; toto číslo by ve skutečnosti mělo mít téměř exponenciální růst, v závislosti na stupni. Karatsuba a jeho student Arkhipov dokázali,^[21] že pro jakékoli přirozené číslo ${displaystyle r}$ tady existuje ${displaystyle n_ {0} = n_ {0} (r)}$, tak, že pro všechny ${displaystyle ngeq n_ {0}}$ existuje formulář s integrálními koeficienty ${displaystyle F (x_ {1}, tečky, x_ {k})}$ stupně menší než ${displaystyle n}$, jehož počet proměnných je ${displaystyle k}$, ${displaystyle kgeq 2 ^ {u}}$,

${displaystyle u = {frac {n} {(log _ {2} n) (log _ {2} log _ {2} n) tečky underbrace {(log _ {2} tečky log _ {2} n)} _ {r} underbrace {(log _ {2} tečky log _ {2} n) ^ {3}} _ {r + 1}}}}$

který má pouze triviální zastoupení nuly ve 2-adických číslech. Rovněž získali podobný výsledek pro jakýkoli lichý primární modul ${displaystyle p}$.

Odhady krátkých součtů Kloostermana

Karatsuba vyvinut^[22][23][24] (1993—1999) nová metoda odhadu krátkéhoKloosterman součty, tj. trigonometrické součty formuláře

${displaystyle sum limits _ {nin A} exp {{iggl (} 2pi i, {frac {an ^ {*} + bn} {m}} {iggr)}},}$

kde ${displaystyle n}$ proběhne sadou ${displaystyle A}$ čísel, coprime do ${displaystyle m}$, počet prvků ${displaystyle | A |}$ ve kterém je podstatně menší než ${displaystyle m}$a symbol ${displaystyle n ^ {*}}$ označuje třídu shody, inverzní k ${displaystyle n}$ modulo ${displaystyle m}$: ${displaystyle nn ^ {*} ekviv. 1 (mod m)}$.

Až do počátku 90. let byly odhady tohoto typu známé, zejména u součtů, ve kterých byl počet sčítanců vyšší než ${displaystyle {sqrt {m}}}$ (H. D. Kloosterman, I. M. Vinogradov, H. Salié, L. Carlitz, S.Uchiyama, A. Weil ). Jedinou výjimkou byly speciální moduly formuláře ${displaystyle m = p ^ {alpha}}$, kde ${displaystyle p}$ je pevné prvočíslo a exponent ${displaystyle alpha}$ zvyšuje se do nekonečna (tento případ studoval A. G. Postnikov metodou Vinogradova). Karatsubova metoda umožňuje odhadnout součty Kloostermana, kde počet sčítání nepřesahuje

${displaystyle m ^ {varepsilon},}$

a v některých případech dokonce

${displaystyle exp {{(ln m) ^ {2/3 + varepsilon}}},}$

kde ${displaystyle varepsilon> 0}$ je libovolně malé pevné číslo. Závěrečná práce Karatsuby na toto téma^[25] byla zveřejněna posmrtně.

Různé aspekty metody Karatsuba našly uplatnění v následujících problémech teorie analytických čísel:

• nalezení asymptotiky součtů dílčích částí formy: ${displaystyle {sum _ {nleq x}} '{iggl {} {frac {an ^ {*} + bn} {m}} {iggr}}, {sum _ {pleq x}}' {iggl {} {frac {ap ^ {*} + bp} {m}} {iggr}},}$ : kde ${displaystyle n}$ běží, jeden po druhém, přes celá čísla splňující podmínku ${displaystyle (n, m) = 1}$, a ${displaystyle p}$ proběhne prvočísly, která nerozdělují modul ${displaystyle m}$ (Karatsuba);

• nalezení dolní meze počtu řešení nerovností tvaru: ${displaystyle alpha <{iggl {} {frac {an ^ {*} + bn} {m}} {iggr}} leq eta}$ : v celých číslech ${displaystyle n}$, ${displaystyle 1leq nleq x}$, coprime do ${displaystyle m}$, ${displaystyle x <{sqrt {m}}}$ (Karatsuba);

• přesnost aproximace libovolného reálného čísla v segmentu ${displaystyle [0,1]}$ dílčími částmi formuláře:

${displaystyle {iggl {} {frac {an ^ {*} + bn} {m}} {iggr}},}$ : kde ${displaystyle 1leq nleq x}$, ${displaystyle (n, m) = 1}$, ${displaystyle x <{sqrt {m}}}$ (Karatsuba);

• přesnější konstanta ${displaystyle c}$ v Brun – Titchmarshova věta  :

${displaystyle pi (x; q, l) <{frac {cx} {varphi (q) ln {frac {2x} {q}}}}}}$ : kde ${displaystyle pi (x; q, l)}$ je počet prvočísel ${displaystyle p}$, nepřesahující ${displaystyle x}$ a patřící do aritmetické progrese ${displaystyle pequiv l {pmod {q}}}$ (J. Friedlander, H. Iwaniec );

• dolní mez pro největšího prvotního dělitele součinu čísel ve tvaru:

${displaystyle n ^ {3} +2}$, ${displaystyle N$ (D. R. Heath-Brown );

• což dokazuje, že existuje nekonečně mnoho prvočísel této formy:

${displaystyle a ^ {2} + b ^ {4}}$ (J. Friedlander, H. Iwaniec );

• kombinatorické vlastnosti množiny čísel:

${displaystyle n ^ {*} {pmod {m}}}$${displaystyle 1leq nleq m ^ {varepsilon}}$ (A. A. Glibichuk).

Riemannova zeta funkce

Selbergovy nuly

V roce 1984 Karatsuba dokázal,^[26][27] že za pevnou ${displaystyle varepsilon}$ splnění podmínky${displaystyle 0$, dostatečně velká ${displaystyle T}$ a ${displaystyle H = T ^ {a + varepsilon}}$, ${displaystyle a = {frac {27} {82}} = {frac {1} {3}} - {frac {1} {246}}}$, interval ${displaystyle (T, T + H)}$ obsahuje alespoň ${displaystyle cHln T}$ skutečné nuly Funkce Riemann zeta ${displaystyle zeta {Bigl (} {frac {1} {2}} + it {Bigr)}}$.

Zvláštní případ ${displaystyle Hgeq T ^ {1/2 + varepsilon}}$ bylo prokázáno Atle Selberg dříve v roce 1942.^[28] Odhady Atle Selberg a Karatsuba nelze zlepšit, pokud jde o pořadí růstu jako ${displaystyle T o + infty}$.

Distribuce nul Riemannovy zeta funkce v krátkých intervalech kritické linie

Karatsuba také získal ^[29] řada výsledků o distribuci nul ${displaystyle zeta (s)}$ v «krátkých» intervalech kritické linie. Dokázal, že analogie Selbergova domněnka platí pro «téměř všechny» intervaly ${displaystyle (T, T + H]}$, ${displaystyle H = T ^ {varepsilon}}$, kde ${displaystyle varepsilon}$ je libovolně malé pevné kladné číslo. Karatsuba vyvinul (1992) nový přístup ke zkoumání nul Riemannovy zeta funkce na „supershort“ intervalech kritické linie, tj. Na intervalech ${displaystyle (T, T + H]}$, délka ${displaystyle H}$ z nichž roste pomaleji než kterýkoli jiný, i když libovolně malý ${displaystyle T}$. Zejména dokázal, že pro všechna daná čísla ${displaystyle varepsilon}$, ${displaystyle varepsilon _ {1}}$ splnění podmínek ${displaystyle 0$ téměř ve všech intervalech ${displaystyle (T, T + H]}$ pro ${displaystyle Hgeq exp {{(ln T) ^ {varepsilon}}}}$ obsahovat alespoň ${displaystyle H (ln T) ^ {1-varepsilon _ {1}}}$ nuly funkce ${displaystyle zeta {igl (} {frac {1} {2}} + it {igr)}}$. Tento odhad je velmi blízký odhadu, který vyplývá z Riemannova hypotéza.

Nuly lineárních kombinací Dirichletovy řady L.

Karatsuba vyvinula novou metodu ^[30][31] vyšetřování nul funkcí, které lze reprezentovat jako lineární kombinace Dirichlet ${displaystyle L}$-série. Nejjednodušším příkladem funkce tohoto typu je funkce Davenport-Heilbronn definovaná rovností

${displaystyle f (s) = {frac {1} {2}} (1-ikappa) L (s, chi) + {frac {1} {2}} (1, +, ikappa) L (s, {ar {chi}}),}$

kde ${displaystyle chi}$ je non-hlavní charakter modulo ${displaystyle 5}$ (${displaystyle chi (1) = 1}$, ${displaystyle chi (2) = i}$, ${displaystyle chi (3) = - i}$, ${displaystyle chi (4) = - 1}$, ${displaystyle chi (5) = 0}$, ${displaystyle chi (n + 5) = chi (n)}$ pro všechny ${displaystyle n}$),

${displaystyle kappa = {frac {{sqrt {10-2 {sqrt {5}}}} - 2} {{sqrt {5}} - 1}}.}$

Pro ${displaystyle f (s)}$ Riemannova hypotéza není pravda, nicméně, kritická linie ${displaystyle Re s = {frac {1} {2}}}$ obsahuje nicméně anormálně mnoho nul.

Karatsuba dokázal (1989), že interval ${displaystyle (T, T + H]}$, ${displaystyle H = T ^ {27/82 + varepsilon}}$, obsahuje alespoň

${displaystyle H (ln T) ^ {1/2} e ^ {- c {sqrt {ln ln T}}}}$

nuly funkce ${displaystyle f {igl (} {frac {1} {2}} + it {igr)}}$. Podobné výsledky získal Karatsuba také pro lineární kombinace obsahující libovolný (konečný) počet sčítání; exponent stupně ${displaystyle {frac {1} {2}}}$ je zde nahrazeno menším číslem ${displaystyle eta}$, to záleží pouze na formě lineární kombinace.

Hranice nul funkce zeta a vícerozměrný problém Dirichletových dělitelů

Karatsubě patří nový průlomový výsledek ^[32] ve vícerozměrném problému Dirichletových dělitelů, který souvisí s nalezením čísla ${displaystyle D_ {k} (x)}$ řešení nerovnosti ${displaystyle x_ {1} * ldots * x_ {k} leq x}$ v přirozených číslech ${displaystyle x_ {1}, ldots, x_ {k}}$ tak jako ${displaystyle x o + infty}$. Pro ${displaystyle D_ {k} (x)}$ existuje asymptotický vzorec formy

${displaystyle D_ {k} (x) = xP_ {k-1} (ln x) + R_ {k} (x)}$ ,

kde ${displaystyle P_ {k-1} (u)}$ je polynom stupně ${displaystyle (k-1)}$, jejichž koeficienty závisí na ${displaystyle k}$ a lze je najít výslovně a ${displaystyle R_ {k} (x)}$ je zbývající termín, jehož všechny známé odhady (do roku 1960) měly podobu

${displaystyle | R_ {k} (x) | leq x ^ {1-alfa (k)} (cln x) ^ {k}}$ ,

kde ${displaystyle alpha = {frac {1} {ak + b}}}$, ${displaystyle a, b, c}$ jsou některé absolutní kladné konstanty.

Karatsuba získal přesnější odhad ${displaystyle R_ {k} (x)}$, ve kterém je hodnota ${displaystyle alfa (k)}$ byl v pořádku ${displaystyle k ^ {- 2/3}}$ a klesal mnohem pomaleji než ${displaystyle alfa (k)}$ v předchozích odhadech. Karatsubův odhad je jednotný ${displaystyle x}$ a ${displaystyle k}$; zejména hodnota ${displaystyle k}$ může růst jako ${displaystyle x}$ roste (jak nějaká síla logaritmu o ${displaystyle x}$). (Podobně vypadající, ale slabší výsledek získal v roce 1960 německý matematik Richert, jehož práce zůstala neznámá sovětským matematikům alespoň do poloviny sedmdesátých let.)

Důkaz odhadu ${displaystyle R_ {k} (x)}$ je založen na řadě tvrzení, v podstatě ekvivalentních teorému na hranici nul funkce Riemannova zeta, získané metodou Vinogradova, tj. teorém, který tvrdí, že ${displaystyle zeta (s)}$ nemá v regionu žádné nuly

${displaystyle Re sgeq 1- {frac {c} {(ln | t |) ^ {2/3} (ln ln | t |) ^ {1/3}}}, čtyřkolka | t |> 10}$ .

Karatsuba nalezena ^[33](2000) zpětný vztah odhadů hodnot ${displaystyle R_ {k} (x)}$ s chováním${displaystyle zeta (s)}$ blízko linky ${displaystyle Re s = 1}$. Zejména prokázal, že pokud ${displaystyle alfa (y)}$ je libovolná nerostoucí funkce splňující podmínku ${displaystyle 1 / yleq alpha (y) leq 1/2}$, tak, že pro všechny ${displaystyle kgeq 2}$ odhad

${displaystyle | R_ {k} (x) | leq x ^ {1-alfa (k)} (cln x) ^ {k}}$

drží tedy ${displaystyle zeta (s)}$ nemá v regionu žádné nuly

${displaystyle Re sgeq 1-c_ {1}, {frac {alpha (ln | t |)} {ln ln | t |}}, quad | t | geq e ^ {2}}$

(${displaystyle c, c_ {1}}$ jsou některé absolutní konstanty).

Odhady maxima modulu zeta funkce zespodu v malých oblastech kritické oblasti a v malých intervalech kritické linie

Karatsuba představil a studoval ^[34] funkce ${displaystyle F (T; H)}$ a ${displaystyle G (s_ {0}; Delta)}$, definované rovností

${displaystyle F (T; H) = max _ {| tT | leq H} {igl |} zeta {igl (} {frac {1} {2}} + it {igr)} {igr |}, quad G ( s_ {0}; Delta) = max _ {| s-s_ {0} | leq Delta} | zeta (s) |.}$

Tady ${displaystyle T}$ je dostatečně velké kladné číslo, ${displaystyle 0$, ${displaystyle s_ {0} = sigma _ {0} + iT}$, ${displaystyle {frac {1} {2}} leq sigma _ {0} leq 1}$, ${displaystyle 0$. Odhad hodnot ${displaystyle F}$ a ${displaystyle G}$ zdola ukazuje, jak velké (v modulu) hodnoty ${displaystyle zeta (s)}$ může trvat krátké intervaly kritické linie nebo v malých sousedstvích bodů ležících v kritickém pruhu ${displaystyle 0leq Re sleq 1}$. Pouzdro ${displaystyle Hgg ln ln T}$ byl dříve studován Ramachandrou; pouzdro ${displaystyle Delta> c}$, kde ${displaystyle c}$ je dostatečně velká konstanta, je triviální.

Karatsuba zejména prokázal, že pokud hodnoty ${displaystyle H}$ a ${displaystyle Delta}$ překročit určité dostatečně malé konstanty, pak odhady

${displaystyle F (T; H) geq T ^ {- c_ {1}}, quad G (s_ {0}; Delta) geq T ^ {- c_ {2}},}$

držte, kde ${displaystyle c_ {1}, c_ {2}}$ jsou určité absolutní konstanty.

Chování argumentu funkce zeta na kritické linii

Karatsuba získal řadu nových výsledků^[35][36] související s chováním funkce ${displaystyle S (t) = {frac {1} {pi}} arg {zeta {igl (} {frac {1} {2}} + it {igr)}}}$, kterému se říká argument Funkce Riemann zeta na kritickém řádku (zde ${displaystyle arg {zeta {igl (} {frac {1} {2}} + it {igr)}}}$ je přírůstek libovolné spojité větve ${displaystyle arg zeta (s)}$ podél přerušované čáry spojující body ${displaystyle 2,2 + it}$ a ${displaystyle {frac {1} {2}} + it}$). Mezi těmito výsledky jsou věty o střední hodnotě pro funkci ${displaystyle S (t)}$ a jeho první integrál ${displaystyle S_ {1} (t) = int _ {0} ^ {t} S (u) du}$ na intervalech reálné přímky a také věta prohlašující, že každý interval ${displaystyle (T, T + H]}$ pro ${displaystyle Hgeq T ^ {27/82 + varepsilon}}$ obsahuje alespoň

${displaystyle H (ln T) ^ {1/3} e ^ {- c {sqrt {ln ln T}}}}$

body, kde je funkce ${displaystyle S (t)}$ znamení změny. Dříve podobné výsledky byly získány Atle Selberg pro případ${displaystyle Hgeq T ^ {1/2 + varepsilon}}$.

Dirichletovy postavy

Odhady krátkých součtů znaků v konečných polích

Na konci šedesátých let se Karatsuba odhaduje na krátké částky Dirichletovy postavy, vyvinutý ^[37] nová metoda umožňující získat netriviální odhady krátkých součtů znaků v konečná pole. Nechat${displaystyle ngeq 2}$ být pevné celé číslo, ${displaystyle F (x) = x ^ {n} + a_ {n-1} x ^ {n-1} + ldots + a_ {1} x + a_ {0}}$ polynom, neredukovatelný nad polem ${displaystyle mathbb {Q}}$ racionálních čísel, ${displaystyle heta}$ kořen rovnice ${displaystyle F (heta) = 0}$, ${displaystyle mathbb {Q} (heta)}$ odpovídající rozšíření pole ${displaystyle mathbb {Q}}$, ${displaystyle omega _ {1}, ldots, omega _ {n}}$ základ ${displaystyle mathbb {Q} (heta)}$, ${displaystyle omega _ {1} = 1}$, ${displaystyle omega _ {2} = heta}$, ${displaystyle omega _ {3} = heta ^ {2}, ldots, omega _ {n} = heta ^ {n-1}}$. Kromě toho ${displaystyle p}$ být dostatečně velký prime, takový ${displaystyle F (x)}$ je neredukovatelné modulo ${displaystyle p}$,${displaystyle mathrm {GF} (p ^ {n})}$ the Galoisovo pole se základem ${displaystyle omega _ {1}, omega _ {2}, ldots, omega _ {n}}$, ${displaystyle chi}$ non-jistina Dirichletova postava pole ${displaystyle mathrm {GF} (p ^ {n})}$. Nakonec nechte ${displaystyle u _ {1}, ldots, u _ {n}}$ být některá nezáporná celá čísla, ${displaystyle D (X)}$ sada prvků ${displaystyle {ar {x}}}$ pole Galois ${displaystyle mathrm {GF} (p ^ {n})}$,

${displaystyle {ar {x}} = x_ {1} omega _ {1} + ldots + x_ {n} omega _ {n}}$ ,

takový, že pro každého ${displaystyle i}$, ${displaystyle 1leq ileq n}$platí následující nerovnosti:

${displaystyle u _ {i}$ .

Karatsuba to dokázal u každého opraveného ${displaystyle k}$, ${displaystyle kgeq n + 1}$a libovolné ${displaystyle X}$ splnění podmínky

${displaystyle p ^ {{frac {1} {4}} + {frac {1} {4k}}} leq Xleq p ^ {{frac {1} {2}} + {frac {1} {4k}}} }$

platí následující odhad:

${displaystyle {iggl |} limity součtu _ {{ar {x}} v D (X)} chi ({ar {x}}) {iggr |} leq c {Bigl (} X ^ {1- {frac {1 } {k}}} p ^ {{frac {1} {4k}} + {frac {1} {4k ^ {2}}}} {Bigr)} ^ {!! n} (ln p) ^ {gamma },}$

kde ${displaystyle gamma = {frac {1} {k}} (2 ^ {n + 1} -1)}$a konstanta ${displaystyle c}$ záleží jen na ${displaystyle n}$ a základ ${displaystyle omega _ {1}, ldots, omega _ {n}}$.

Odhady lineárních součtů znaků nad posunutými prvočísly

Karatsuba vyvinul řadu nových nástrojů, které mu v kombinaci s Vinogradovovou metodou odhadu součtů s prvočísly umožnily získat v roce 1970 ^[38] odhad součtu hodnot nehlavního znaku modulo prime ${displaystyle q}$ na posloupnosti posunutých prvočísel, jmenovitě odhad formy

${displaystyle {iggl |} limity součtu _ {pleq N} chi (p + k) {iggr |} leq cNq ^ {- {frac {varepsilon ^ {2}} {1024}}},}$

kde ${displaystyle k}$ je celé číslo splňující podmínku ${displaystyle kot equiv 0 (mod q)}$, ${displaystyle varepsilon}$ libovolně malé pevné číslo, ${displaystyle Ngeq q ^ {1/2 + varepsilon}}$a konstanta ${displaystyle c}$ záleží na ${displaystyle varepsilon}$ pouze.

Toto tvrzení je podstatně silnější než odhad Vinogradova, pro který není triviální ${displaystyle Ngeq q ^ {3/4 + varepsilon}}$.

V roce 1971 vystoupil na mezinárodní konferenci o teorii čísel u příležitosti 80. Narozenin Ivan Matveyevich Vinogradov, Akademik Jurij Linnik zaznamenal následující:

«Velmi důležitá jsou vyšetřování prováděná Vinogradovem v oblasti asymptotiky z Dirichletova postava na posunutých prvočíslech ${limity součtu displaystyle _ {pleq N} chi (p + k)}$, které poskytují snížený výkon ve srovnání s ${displaystyle N}$ ve srovnání s ${displaystyle Ngeq q ^ {3/4 + varepsilon}}$,${displaystyle varepsilon> 0}$, kde ${displaystyle q}$ je modul znaku. Tento odhad má zásadní význam, protože je tak hluboký, že dává více než rozšířený Riemannova hypotéza Zdá se, že v tomto směru je hlubší skutečnost než domněnka (pokud je domněnka pravdivá). Nedávno tento odhad vylepšil A.A.Karatsuba ».

Tento výsledek byl rozšířen Karatsubou k případu, kdy ${displaystyle p}$ prochází prvočísla v aritmetickém postupu, jehož přírůstek roste s modulem${displaystyle q}$.

Odhady součtu znaků na polynomech s hlavním argumentem

Karatsuba nalezena ^[37][39] řada odhadů součtů Dirichletových znaků v polynomech stupně dva pro případ, kdy argument polynomu proběhne krátkou posloupností následujících prvočísel. Pojďme například ${displaystyle q}$ být dostatečně vysoký prime, ${displaystyle f (x) = (x-a) (x-b)}$, kde ${displaystyle a}$ a ${displaystyle b}$ jsou celá čísla, splňující podmínku ${displaystyle ab (a-b) ot equiv 0 (mod q)}$a nechte ${displaystyle left ({frac {n} {q}} ight)}$ označit Legendární symbol, pak pro všechny pevné ${displaystyle varepsilon}$ s podmínkou ${displaystyle 0$ a ${displaystyle N> q ^ {3/4 + varepsilon}}$ pro částku ${displaystyle S_ {N}}$,

${displaystyle S_ {N} = limity součtu _ {pleq N} {iggl (} {frac {f (p)} {q}} {iggr)},}$

platí následující odhad:

${displaystyle | S_ {N} | leq cpi (N) q ^ {- {frac {varepsilon ^ {2}} {100}}}}$

(tady ${displaystyle p}$ proběhne následujícími prvočísly, ${displaystyle pi (N)}$ je počet prvočísel nepřesahující ${displaystyle N}$, a ${displaystyle c}$ je konstanta, v závislosti na ${displaystyle varepsilon}$ pouze).

Obdobný odhad získal Karatsuba i pro případ, kdy ${displaystyle p}$ proběhne posloupností prvočísel v aritmetické posloupnosti, jejichž přírůstek může růst spolu s modulem ${displaystyle q}$.

Karatsuba se domníval, že netriviální odhad součtu ${displaystyle S_ {N}}$ pro ${displaystyle N}$, které jsou ve srovnání s ${displaystyle q}$, zůstává pravdou v případě, kdy ${displaystyle f (x)}$ je nahrazen libovolným polynomem stupně ${displaystyle n}$, což není čtvercové modulo ${displaystyle q}$. Tato domněnka je stále otevřená.

Dolní hranice pro součet znaků v polynomech

Karatsuba postavena ^[40] nekonečná posloupnost prvočísel ${displaystyle p}$ a posloupnost polynomů ${displaystyle f (x)}$ stupně ${displaystyle n}$ s celočíselnými koeficienty, takovými ${displaystyle f (x)}$ není plné čtvercové modulo ${displaystyle p}$,

${displaystyle {frac {4 (p-1)} {ln p}} leq nleq {frac {8 (p-1)} {ln p}},}$

a takhle

${limity součtu stylů zobrazení _ {x = 1} ^ {p} vlevo ({frac {f (x)} {p}} vpravo) = p.}$

Jinými slovy, pro všechny ${displaystyle x}$ hodnota ${displaystyle f (x)}$ se ukázalo být kvadratickým zbytkem modulo ${displaystyle p}$. Tento výsledek to ukazuje André Weil odhad

${displaystyle {iggl |} limity součtu _ {x = 1} ^ {p} vlevo ({frac {f (x)} {p}} vpravo) {iggr |} leq (n-1) {sqrt {p}} }$

nelze podstatně zlepšit a pravou stranu druhé nerovnosti nelze nahradit řekněme hodnotou ${displaystyle C {sqrt {n}} {sqrt {p}}}$, kde ${displaystyle C}$ je absolutní konstanta.

Součty znaků v aditivních sekvencích

Karatsuba našel novou metodu,^[41] umožňující získat poměrně přesné odhady součtu hodnot ne-hlavních Dirichletových znaků na aditivních sekvencích, tj. na sekvencích skládajících se z čísel tvaru ${displaystyle x + y}$, kde proměnné ${displaystyle x}$ a ${displaystyle y}$ prochází několika sadami${displaystyle A}$ a ${displaystyle B}$ nezávisle na sobě. Nejcharakterističtějším příkladem tohoto druhu je následující tvrzení, které se uplatňuje při řešení široké třídy problémů spojených se sčítáním hodnot Dirichletových znaků. Nechat ${displaystyle varepsilon}$ být libovolně malé pevné číslo, ${displaystyle 0$, ${displaystyle q}$ dostatečně velká prime, ${displaystyle chi}$ non-hlavní charakter modulo ${displaystyle q}$. Kromě toho ${displaystyle A}$ a ${displaystyle B}$ být libovolné podmnožiny úplného systému tříd kongruence modulo ${displaystyle q}$, splňující pouze podmínky ${displaystyle | A |> q ^ {varepsilon}}$, ${displaystyle | B |> q ^ {1/2 + varepsilon}}$. Pak platí následující odhad:

${displaystyle {iggl |} limity součtu _ {xin A} limity limitu _ {yin B} chi (x + y) {iggr |} leq c | A | cdot | B | q ^ {- {frac {varepsilon ^ {2 }} {20}}}, quad c = c (varepsilon)> 0.}$

Karatsuba's method makes it possible to obtain non-trivial estimates of that sort in certain other cases when the conditions for the sets ${displaystyle A}$ a ${displaystyle B}$, formulated above, are replaced by different ones, for example: ${displaystyle |A|>q^{varepsilon }}$, ${displaystyle {sqrt {|A|}}cdot |B|>q^{1/2+varepsilon }.}$

V případě, kdy ${displaystyle A}$ a ${displaystyle B}$ are the sets of primes in intervals ${displaystyle (1,X]}$, ${displaystyle (1,Y]}$ respektive kde ${displaystyle Xgeq q^{1/4+varepsilon }}$, ${displaystyle Ygeq q^{1/4+varepsilon }}$, an estimate of the form

${displaystyle { iggl |}sum limits _{pleq X}sum limits _{p'leq Y}chi (p+p'){ iggr |}leq cpi (X)pi (Y)q^{-c_{1}varepsilon ^{2}},}$