Преглед на кода на Анатолий Карацуба

{{Личност
| име              = Анатолий Карацуба
| име-оригинал     = 
| категория        = математик
| описание         = руски математик
| портрет          = A.A.Karatsuba.jpg
| портрет-описание = 
| роден-място      = [[Грозни]], [[Русия]]
| починал-място    = [[Москва]], Русия
| националност     = 
| вложки           = {{Личност/Учен | категория = математик
| област           = [[математика]]
| образование      = [[Московски държавен университет]]
| учил-при         = 
| работил-в        = [[Математически институт „Стеклов“|МИ „Стеклов“]], [[Московски държавен университет|МДУ]]
| студенти         = 
| публикации       = 
| известен-с       = 
| повлиян          = 
| повлиял          = }}
}}
'''Анатолий Алексеевич Карацуба''' е [[Руснаци|руски]] [[математик]], създател на първия бърз изчислителен метод – [[алгоритъм на Карацуба]] за умножаване на големи числа.

== Образование и работа ==
[[Файл:A.A.Karatsuba graduate.jpg|мини|А. А. Карацуба като ученик]]
През 1944 – 1954 г. Анатолий Карацуба учи в мъжка гимназия No6 в гр. Грозни и я завършва със сребърен медал. Още в ранните си години той изявява изключителния си талант в математиката: още в началните класове той решава задачи, които представляват трудност дори и за най-големите ученици.

През 1959 г. завършва факултета по математика и механика на [[Московски държавен университет|Московския държавен университет „Ломоносов“]]. През 1962 г. получава степен [[Кандидат на науките|„кандидат на физико-математическите науки“]] с дисертацията „Рационални тригонометрични суми от специален тип и техни приложения“ (с научен ръководител Н. М. Коробов), и започва да работи във факултета по математика и механика на същия университет. През 1966 г. се хабилитира и придобива научната степен „доктор на математическите научки“ с дисертацията „Методът на тригонометричните суми и теоремите за средните стойности“. Същата година става член на [[Математически институт „Стелков“|Института по математика „Стеклов“]].

От 1983 г. е водещ специалист по [[теория на числата]] в [[СССР]]. Бил е ръководител на отдела по теория на числата в Института „Стеклов“, професор в катедрата по теория на числата на Московския държавен университет от 1970 г. и професор в катедрата по [[математически анализ]] на [[Московски държавен университет|Московския държавен университет]] от 1980 г. Неговите интереси включват [[Ред на Фурие|тригонометрични редове]] и тригонометрични интеграли, [[дзета-функция на Риман]], [[Краен автомат|крайни автомати]], ефективни [[Алгоритъм|алгоритми]].

Карацуба е ръководил докторантурите на 15 докторанта, получили степени „кандидат на науките“ (7 от тях по-късно са получили степен „доктор на науките“). Той е награден с държавни награди и почетни титли.

== Награди и титли ==
* 1981 – награда „П. Л. Чебишев“ на Съветската Академията на науките на СССР
* 1999 – [[заслужил деятел на науката на Руската федерация]]
* 2001 – награда „И. М. Виноградов“ на Руската академия на науките

== Ранни изследвания в информатиката ==
Като студент в Московския държавен университет „Ломоносов“ Карацуба посещава семинар на [[Андрей Колмогоров]] и намира решения на 2 проблема, поставени от Колмогоров. Това е съществено за развитието на теория на автоматите и поражда нов клон в математиката – теорията на бързите алгоритми.

=== Автомати ===
В статията на [[Едуард Ф. Мур]]<ref>{{cite journal| last=Moore| first= E. F.| title= Gedanken-experiments on Sequential Machines.| pages=129 – 153| journal= Automata Studies, Annals of Mathematical Studies, Princeton University Press, Princeton, N.J.,| issue=34| year=1956}}</ref><math>(n; m; p)</math> автомат (или машина) <math>S</math> е дефиниран като устройство с <math>n</math> състояния, <math>m</math> входни символа и <math>p</math> изходни символа. Доказани са девет теореми за структурата на <math>S</math>. По-късно такива „<math>S</math> машини“ получават името [[Автомат на Мур]]. В края на статията в раздела „Нови проблеми“ Мур формулира проблема за подобряване на оценките, които той е получил в Теореми 8 и 9:

: '''Теорема 8 (Мур).''' Нека е дадена произволна <math>(n; m; p)</math> машина <math>S</math>, такава че всеки 2 състояния могат да бъдат различени едно от друго. Тогава съществува експеримент с дължина <math>n(n-1)/2</math>, който различава състоянието на <math>S</math> в края на експеримента.

През 1957 г. Карацуба доказва 2 теореми, които напълно решават проблема на Мур по подобряване на оценката за дължината на експеримента в '''Теорема 8'''.

: '''Теорема ''A'' (Карацуба).''' Ако <math>S</math> е <math>(n; m; p)</math> машина, такава, че всеки 2 нейни състояния могат да бъдат различени едно от друго, то съществува разклоняващ се експеримент с дължина най-много {{nobr|<math>(n-1)(n-2)/2 + 1</math>}}, посредством който може да се определи състоянието на <math>S</math> в крайния момент.

: '''Теорема ''B'' (Карацуба).''' Съществува такава <math>(n; m; p)</math> машина, всеки 2 състояния на която могат да бъдат различени едно от друго, такава че дължината на най-краткия експеримент, откриващ състоянието на машината в края на ескперимента, е равен на {{nobr|<math>(n-1)(n-2)/2 + 1</math>}}.

Тези 2 теореми са доказани от Карацуба в курсова работа през четвъртата година от обучението му. Последващата публикация е изпратена в списанието „Успехи математических наук“ на 17 декември 1958 г. и е публикувана през юни 1960 г.<ref>{{cite journal| last=Карацуба| first=А. А.| title=Решение одной задачи из теории конечных автоматов | pages=157 – 159| journal=УМН| issue=15:3| year=1960}}</ref>. До днес (12 април 2010) този резултат на Карацуба, който по-късно получава названието „Теорема на Мур-Карацуба“, остава единственият точен нелинеен резултат в автоматната теория и в подобните проблеми от теорията на сложността на изчисленията.

=== Бързи алгоритми ===
[[Бързи алгоритми|Бързите алгоритми]] са област от изчислителната математика, която изучава алгоритмите за изчисление на дадена функция с определена точност, използвайки най-малкия възможен брой операции. Приемаме, че числата са записани в двоична система, като знаците 0 и 1 наричаме „битове“. Една „бит операция“ е дефинирана като записване на един от знаците 0, 1, плюс, минус, скоба; групиране, изваждане или умножаване на два бита. [[Андрей Колмогоров]] е един от първите, които поставят проблеми за бит-сложността на изчисленията. Сложността на умножението <math>M(n)</math> е дефинирано като броя на бит операциите, достатъчни за изчисляването на произведението на две n-цифрени числа по начин, зададен от даден алгоритъм.

Умножавайки две n-цифрени цели числа по стандартния училищен метод „в колонка“, ние получаваме горна граница <math>M(n) = O(n^2)</math>. През 1956 [[Андрей Колмогоров|А.Н.Колмогоров]] предполага, че долната граница за <math>M(n)</math> при всеки метод за умножение също е от порядък <math>n^2</math>, т.е. е невъзможно да се пресметне произведението на две <math>n</math>-цифрени цели числа с по-малко от <math>n^2</math> операции (така наречената „Хипотеза n^2“ на Колмогоров). Хипотезата <math>n^2</math> е изглеждала реалистична, защото през човешка история хората са умножавали числа чрез алгоритми със сложност от порядък <math>O(n^2)</math> и ако е съществувал по-бърз метод за умножение, то вероятно той е щял да бъде открит.

През 1960 г. Анатолий Карацуба открива нов метод за умножаване на 2 <math>n</math>-цифрени числа, който сега е познат като [[„Алгоритъм на Карацуба“]], при който сложността е от порядък
: <math>M(n) = O(n^{\log_23}) = O(n^{1,58496\ldots}),</math> с което опровергава <math>n^2</math> хипотезата. Този резултат е обяснен от Карацуба на семинара на Колмогоров в Московския държавен университет през 1960 г., след което семинарът на Колмогоров приключва своята дейност. Първата статия, описваща метода, е подготвена от самия Колмогоров<ref>{{cite journal|last=Карацуба А., Офман Ю.|title=Умножение многозначных чисел на автоматах|year=1962|journal=Доклады Академии Наук СССР|issue=145.2}}</ref>, където той представя 2 различни и несвързани един с друг резултати на 2 от своите студенти. В статията Колмогоров ясно уточнява, че теорема (несвързана с бързото умножаване) принадлежи на Ю. Офман и друга (с първия бърз алгоритъм за умножение) принадлежи на А. Карацуба. Методът на Карацуба по-късно е наречен „[[Алгоритъм#Според дизайна|Алгоритъм разделяй и владей]]“. Другите имена на този метод, в зависимост от областта, в която се прилага той, са „Бинарно разделяне“, „Принцип на дихотомията“ и т.н.

По-късно въз основа на идеята на Карацуба<ref>{{cite journal|last=Karacuba A.|title=Berechnungen und die Kompliziertheit von Beziehungen|year=1975|journal=Elektronische Informationsverarbeitung und Kybernetik|issue=11}}</ref><ref>{{cite journal|last=Карацуба А. А.|title=Сложность вычислений|year=1995|journal=Труды Математического института им. Стеклова|issue=211}}</ref><ref>{{cite book|last=[[Кнут Д.]]|title=Искусство программирования| issue= 3-то изд. – М.: Вильямс, 2007. – Т. 2. Получисленные алгоритмы.|year=2007|pages=832, isbn=0-201-89684-2}}.</ref> са конструирани хиляди бързи алгоритми, много от които са негови директни обобщения, като [[Алгоритъм на Шонхейдж-Щрасен|алгоритъма на Шонхейдж-Щрасен]]<ref>{{cite journal|last=Schcnhage A., Strassen V.|title=Schnelle Multiplikation großer Zahlen|yeae=1971|journal=Computing|номер=7|pages=281 – 292}}</ref> и [[Алгоритъм на Щрасен|алгоритъма на Щрасен за умножение на матрици]]<ref>Strassen, Volker, ''Gaussian Elimination is not Optimal'', Numer. Math. 13, p. 354 – 356, 1969</ref>. През последните години терминът „Разделяй и владей“ е използван за операции, които разбиват даден проблем на части, което вече не е свързано с бързите изчислителни алгоритми.

Френският математик и философ [[Жан-Пол Делаайе]] описва<ref>{{cite journal|last=Jean-Paul Delahaye.|title=Mathematiques et philosophie|year=2000|journal=Pour la Science|issue=277|pages=100 – 104}}</ref> метода за умножение на Карацуба като „един от най-полезните резултати в математиката“.

Алгоритъмът на Анатолий Карацуба е внедрен в практически всички модерни компютри, не само софтуерно, но също така и хардуерно.

== Основни изследвания ==
В статията „Върху математическите работи на проф. А. А. Карацуба“ <ref>{{cite book
| last         = Г. И. Архипов; В. Н. Чубариков.
| title      = О математических работах профессора А. А. Карацубы
| ссылка        = http://www.mi.ras.ru/~karatsuba/download/intro.ps
| year          = 1997
| issue           = 218
| pages      = 7 – 19
}}</ref>, публикувана по случай 60-ата годишнина на А. А. Карацуба, неговите бивши студенти Г. И. Аркипов и [[Владимир Чубариков]] характеризират специалните черти на изследванията на Карацуба по следния начин:

{{цитат|Когато се описват изследванията на изтъкнати учени, е нормално да се наблегне на някои характеристики и специални черти от техните креативни разработки. Такива отличаващи черти на научните изследвания на проф. Карацуба са комбинаторната изобретателност, фундаменталната значимост и завършеността на резултатите.}}

Главните разработки на А. А. Карацуба са публикувани в повече от 160 статии и монографии.<ref>{{cite journal|author=Карацуба А. А.| title= Основы аналитической теории чисел.| journal= М.: Наука| year= 1975}}</ref><ref>{{cite journal|author=Архипов Г. И., Карацуба А. А., Чубариков В. Н.| title= Теория кратных тригонометрических сумм.| journal= М.: Наука| year= 1987}}</ref><ref>{{cite journal|author=Воронин С. М., Карацуба А. А.| title= Дзета-функция Римана.| journal=М.: Физматлит| year= 1994}}</ref><ref>{{cite journal|author=Karatsuba A. A. | title= Complex analysis in number theory.| journal= London, Tokyo: C.R.C.| year= 1995}}</ref>

=== Тригонометрични суми и тригонометрични интеграли ===
==== ''p''-адичен метод ====
Карацуба създава <math>p</math>-адичния метод в теорията на тригонометричните суми. Оценките на така наречените <math>L</math>-суми от типа

: <math>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,</math>

получени в <ref>{{cite journal| last=Карацуба| first=А. А.| title= Оценки тригонометрических сумм особого вида и их приложения| pages=513 – 514| journal= Докл. АН СССР| issue=137:3| year= 1961}}</ref>, довеждат до

* нови ограничения за нулите на <math>L</math>-редовете на Дирихле по модул степен на просто число.

* асимптотична формула за броя на решенията на сравнението от Варингов тип

: <math>x_1^{n} + \dots + x_t^{n} \equiv N \pmod{p^k}, \quad 1 \le x_s \le P, \quad 1 \le s \le n, \quad P < p^k</math>

* решение на задачата за разпределението на дробните части на полиномиални редици.

Карацуба е първият, който осъзнава<ref>{{cite journal| last=Карацуба| first=А. А.| title= Проблема Варинга для сравнения по модулю, равному степени простого числа| pages=28 – 38| journal= Вестн. МГУ| issue=1:4| year= 1962}}</ref>, че съществува <math>p</math>–адичен аналог на така наречения „принцип на включването“ на Ойлер-Виноградов. Карацуба също пресмята <math>p</math>-адичния аналог на <math>u</math>-числата на Виноградов, при оценката на броя на решенията на сравнението от Варингов тип.

Нека имаме:

: <math>x_1^{n} + \dots + x_t^{n} \equiv N \pmod{Q}, \quad 1 \le x_s \le P, \quad 1 \le s \le t, \quad (1)</math>

така че

: <math>P^r \le Q < P^{r+1}, \quad 1 \le r \le \frac{1}{12}\sqrt{n}, \quad Q = p^k, \quad k \ge 4(r+1)n,</math>

където <math>p</math> е просто число. Карацуба доказва, че за всяко естествено число <math>n \ge 144</math> съществува <math>p_0 = p_0(n)</math>, такова че за всяко <math>p_0 > p_0(n)</math> всяко естествено число <math>N</math> може да бъде представено във вида (1) при <math>t \ge 20r + 1</math>. А при <math>t < r</math> съществува <math>N</math>, такова че сравнението (1) няма решения.

Този нов подход, открит от Карацуба, довежда до ново <math>p</math>-адично доказателство на теоремата на Виноградов за средните стойности, която играе централна роля в метода на Виноградов в теорията на тригонометричните суми.

Друг компонент от <math>p</math>-адичния метод на Карацуба е преходът от непълни системи от уравнения до пълни системи от такива за сметка на локална <math>p</math>-адична смяна на неизвестните. <ref>{{cite journal| last=Карацуба| first=А. А.| title= Об оценке числа решений некоторых уравнений| pages=31 – 32| journal= Докл. АН СССР| issue=165:1| year=1965}}</ref>
<ref>{{cite journal| last=Карацуба| first=А. А.| title= Системы сравнений и уравнения Варинговского типа| pages=274 – 276| journal= Докл. АН СССР| issue=1:4| year=1965}}</ref>

Нека <math>r</math> е произволно естествено число, <math>1 \le r \le n</math>. Определяме цялото число <math>t</math> чрез неравенствата <math>m_t \le r \le m_{t+1}</math>. Разглеждаме системата от уравнения

: <math>
\begin{cases}
x_1^{m_1} + \dots + x_k^{m_1} = y_1^{m_1} + \dots + y_k^{m_1}\\
\dots\dots\dots\dots\dots\dots\dots\dots \\
x_1^{m_s} + \dots + x_k^{m_s} = y_1^{m_s} + \dots + y_k^{m_s}\\
x_1^{n} + \dots + x_k^{n} = y_1^{n} + \dots + y_k^{n}
\end{cases}
</math>

: <math>1 \le x_1,\dots,x_k,y_1,\dots,y_k \le P, \quad 1 \le m_1 < m_2 < \dots < m_s < m_{s+1} = n.</math>

Карацуаба доказва, че броят на решенията <math>I_k</math> на тази система от уравнения при <math>k \ge 6rn\log n</math> изпълнява оценката

: <math>I_k \ll P^{2k-\delta}, \quad \delta = m_1 + \dots + m_t + (s-t+1)r.</math>

За непълни системи от уравнения, при които променливите пробягват числа с малки прости делители, Карацуба прилага специален метод, което довежда до съществено нова оценка на тригонометрични суми и нова теорема за средните стойности за такива системи от уравнения.

==== Задачата на Хуа-ло-Кен за експонентата на сходимост на интеграла от проблема на Тери ====
<math>p</math>-адичният метод на Карацуба включва оценки на мярката на множеството от точки с малки значения на функции посредством техните параметри (коефициенти и т.н.) и, обратно, оценки на тези параметри посредством мярката на множества в реалната и <math>p</math>-адичната метрики. Тази страна на метода се проявява особено ярко при оценки на тригонометрични интеграли, което довежда до решението на задачата на [[Хуа – Ло – кен]]. През 1979 г. Карацуба заедно със своите ученици Архипов и Чубариков решават напълно<ref>{{cite journal| author=Архипов Г. И., Карацуба А. А., Чубариков В. Н.|title= Тригонометрические интегралы| pages=971 – 1003| journal= Изв. РАН. Сер. матем.| issue=43:5| year=1979}}</ref> задачата на Хуа – Ло – кен, поставена през 1937, която се състои в определянето на показателя на [[сходимост]] на интеграла

: <math>\vartheta_0=\int\limits_{-\infty}^{+\infty}\cdots
\int\limits_{-\infty}^{+\infty}\biggl|\int\limits_{0}^{1}e^{2\pi
i(\alpha_{n}x^{n}+\cdots
+\alpha_{1}x)}dx\biggr|^{2k}d\alpha_{n}\ldots d\alpha_{1},</math>
где <math>n \ge 2</math> – фиксированное число.

==== Кратни тригонометрични суми ====
В периода 1966 – 1980 Карацуба създава<ref>{{cite journal| last=Карацуба| first=А. А.| title= Теоремы о среднем и полные тригонометрические суммы | pages=183 – 206| journal= Изв. АН СССР. Сер. матем.| issue=30:1| year=1966}}</ref><ref>{{cite journal|author= Виноградов И. М., Карацуба А. А.| title= Метод тригонометрических сумм в теории чисел| pages=4 – 30| journal= Труды МИАН| issue=168| year=1984}}</ref><ref>{{cite journal|author= Архипов Г. И., Карацуба А. А., Чубариков В. Н.| title= Теория кратных тригонометрических сумм| journal= М.: Наука| year=1987}}</ref> (с участие на своите ученици Архипов и Чубариков) теорията на кратните тригонометрични суми на [[Херман Вайл]], т.е сума от вида

: <math>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)}</math>,
где <math>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}</math>,
където <math>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}</math>,

<math>A</math> – набор от реални коефициенти <math>\alpha(t_1,\dots,t_r)</math>. Централният момент в тази теория, както и в теорията на тригонометричните суми на И.М.Виноградов, се състои в следващата теорема за '''средната стойност'''.

: Нека <math>n_1,\dots,n_r,P_1,\dots,P_r</math> са естествени числа, <math>P_1 = \min(P_1,\dots,P_r)</math>,<math>m = (n_1+1)\dots(n_r+1)</math>. Нека <math>\Omega</math> е <math>m</math>-мерен куб в [[евклидово пространство]] от вида

:: <math>0 \le \alpha(t_1,\dots,t_r) < 1</math>, <math>0 \le t_1 \le n_1, \dots,0 \le t_r \le n_r</math>,
: и
:: <math>J = J(P_1,\dots,P_r;n_1,\dots,n_r;K,r) = \underset{\Omega}{\int\dots\int}|S(A)|^{2K} dA</math>.

: Тогава при произволни <math>\tau \ge 0</math> и <math>K \ge K_{\tau} = m\tau</math>, за величината <math>J</math> имаме оценката

:: <math>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)}</math>,

: където <math>\varkappa = n_1\nu_1+ \dots + n_r\nu_r</math>, <math>\gamma\varkappa = 1</math>, <math>\Delta(\tau) = \frac{m}{2}(1-(1-\gamma)^{\tau})</math>, <math>P = (P_1^{n_1}\dots P_r^{n_r})^{\gamma}</math>, и естествените числа <math>\nu_1, \dots, \nu_r</math> са такива, че:
:: <math>-1 < \frac{P_s}{P_1} - \nu_s \le 0</math>, <math>s= 1,\dots, r</math>.

Теоремата за средната стойност и лемата за кратностите на пресичанията на многомерни паралелепипеди лежат в основата на оценката за кратните тригонометрични суми, получени от Карацуба. Ако означим с <math>Q_0</math> най-малкото общо кратно на числата <math>q(t_1,\dots,t_r)</math> с условието <math>t_1 + \dots t_r \ge 1</math>, то при <math>Q_0 \ge P^{1/6}</math> е изпълнена оценката

: <math>|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}</math>,

където <math>\tau(Q)</math> е броят на делителите на числото <math>Q</math>, а <math>\nu(Q)</math> е броят на различните прости делители на числото <math>Q</math>.

==== Оценка на функцията на Харди в проблема на Уоринг ====
Прилагайки конструираната <math>p</math>-адична форма на кръговия метод на Харди-Литлууд-Рамануджан-Виноградов към оценките на тригонометричните суми, в които сумирането се извършва по числа с малки прости делители, Карацуба получава<ref>{{cite journal| last=Карацуба| first=А. А.| title= О функции G(n) в проблеме Варинга | pages=935 – 947| journal= Изв. РАН. Сер. матем.| issue=49:5| year=1985}}</ref> нова оценка за известната функция на [[Годфри Харолд Харди|Харди]] <math>G(n)</math> в [[Проблем на Уоринг|проблема на Уоринг]] (при <math>n \ge 400</math>):

: <math>\! G(n) < 2 n\log n + 2 n\log\log n + 12 n.</math>

==== Многомерен аналог на проблема на Уоринг ====
В своите по-нататъшни изследвания по проблема на Варинг, Карацуба получава <ref>{{cite journal| author=Архипов Г. И., Карацуба А. А.|title= Многомерный аналог проблемы Варинга | pages=521 – 523| journal= Докл. АН СССР| issue=295:3| year=1987}}</ref><ref>{{cite journal| author=Karatsuba A. A.|title= Waring's problem in several dimension| pages=5 – 6| journal= Mathem. Forschungs, Oberwolfach, Tagungsbericht| issue=42| year=1988}}</ref> следващото двумерно обобщение:

Разглеждаме системата от уравнения

: <math>x_1^{n-i}y_1^i + \dots + x_k^{n-i}y_k^i = N_i</math>, <math>i = 0,1,\dots, n</math>,

където <math>N_i</math> са зададени положителни цели числа, които имат еднакъв порядък на нарастване, <math>N_0 \to +\infty</math>, а <math>x_{\varkappa},y_{\varkappa}</math> са неизвестни, но също положителни числа. Тази система е разрешима, ако <math>k > cn^2\log n</math>,
а ако
<math>k < c_1n^2</math>,
то съществуват такива <math>N_i</math>, че системата няма решение.

==== Проблем на Артин за локалното представяне на нулата от дадена форма ====
В изследванията по проблема на [[Емил Артин]] за <math>p</math>-адичното представяне на нула чрез зададена форма от произволна степен, резултатите на Карацуба показват, че вместо по-ранно предполаганото степенно нарастване на броя на променливите за нетривиалното представяне на нулата чрез формата, това число променливи трябва да расте почти експоненциално спрямо степента. Карацуба заедно със своя ученик Архипов доказват,<ref>{{cite journal| author=Архипов Г. И., Карацуба А. А.|title= О локальном представлении нуля формой | pages=948 – 961| journal= Изв. АН СССР. Сер. матем.| issue=45:5| year=1981}}</ref>, че за всяко естествено число <math>r</math> съществува такова <math>n_0 = n_0(r)</math> че за всяко <math>n \ge n_0</math>, съществува форма <math>F(x_1,\dots,x_k)</math> със степен, по-малка от <math>n</math>, с цели коефициента, броят на променливите на която е <math>k</math>,
<math>k \ge 2^u</math>,

: <math>u = \frac{n}{(\log_2n)(\log_2\log_2n)\dots\underbrace{(\log_2\dots\log_2n)}_r\underbrace{(\log_2\dots\log_2n)^3}_{r+1}}</math>

и имаща само тривиално представяне на нулата в двоичните числа. Също така са получили аналогичен резултат за произволен нечетен прост модул <math>p</math>.

==== Оценки на кратки суми на Клостерман ====
Карацуба създава<ref>{{cite journal| last=Карацуба| first=А. А.| title= Аналоги сумм Клоостермана | pages=93 – 102| journal= Изв. РАН. Сер. матем.| issue=59:5| year=1995}}</ref><ref>{{cite journal| last=Карацуба| first=А. А.| title= Аналоги неполных сумм Клоостермана и их приложения | pages=89 – 120| journal= Tatra Mountains Math. Publ.| issue=11| year=1997}}</ref><ref>{{cite journal| last=Карацуба| first=А. А.| title= Двойные суммы Клоостермана | pages= 682 – 687| journal= Матем. заметки| issue=66:5| year=1999}}</ref> (1993 – 1999) нов метод за оценка на кратки [[суми на Клостерман]], т.е. тригонометрична сума от вида

: <math>\sum\limits_{n\in A}\exp{\biggl(2\pi i\,\frac{an^{*}+bn}{m}\biggr)},</math>

където <math>n</math> пробягва някакво множеството <math>A</math> от числа, взаимно-прости с <math>m</math>, броят <math>\|A\|</math> на елементите на което е значително по-малък от <math>m</math>, а символът <math>n^{*}</math> означава обратния елемент на <math>n</math> по модул <math>m</math>:
<math>nn^{*}\equiv 1\pmod m</math>.

До началото на 1990-те оценки за суми от такъв тип били известни, ако броят на събираемите в тях не надминава <math>\sqrt{m}</math> ([[Хендрик Клостерман]], [[Иван Виноградов]], Г. Сале, [[Леонард Карлиц]] (''Leonard Carlitz''), С. Учияма, [[Андре Вейл]]). Изключение са специални суми от вида <math>m = p^{\alpha}</math>, където <math>p</math> е фиксирано просто число, а експонентата <math>\alpha</math> расте неограничено (този случай е бил изследван от Постниковим по метода на Виноградов). Методът на Карацуба позволява да се оцени сумата на Клостерман, броят на събираемите на която не превъзхожда <math>m^{\varepsilon}</math>, а в някои случаи – дори <math>\exp{\{(\ln m)^{2/3+\varepsilon}\}}</math>, където <math>\varepsilon > 0</math> е произволно малко фиксирано число.

Различни аспекти на метода на Карацуба са намерили приложение в решението на следващите задачи от аналитичната теория на числата:

* намиране на асимптотични формули за суми от дробни части от вида
*: <math>{\sum_{n\le x}}'\biggl\{\frac{an^{*}+bn}{m}\biggr\}, {\sum_{p\le x}}'\biggl\{\frac{ap^{*}+bp}{m}\biggr\},</math>
: където <math>n</math> пробягва последователни цели числа, удовлетворяващи <math>(n,m)=1</math>, а <math>p</math> пробягва прости числа, не делящи модула <math>m</math> (Карацуба);

* намиране на долни граници за броя на решенията на неравенства от вида
*: <math>\alpha<\biggl\{\frac{an^{*}+bn}{m}\biggr\}\le\beta</math>
: в цели числа <math>n</math>, <math>1\le n\le x</math>, взаимно прости с <math>m</math>, <math>x<\sqrt{m}</math> (Карацуба);

* изследване на точността на приближението на произволно реално число от интирвала <math>[0,1]</math> с дробни части от вида
*: <math>\biggl\{\frac{an^{*}+bn}{m}\biggr\},</math>
: където <math>1\le n\le x</math>, <math>(n,m)=1</math>, <math>x<\sqrt{m}</math> (Карацуба);

* комбинаторни свойства множеството от числата <math>n^{*} \pmod{m}</math>, <math>1 \le n \le m^{\varepsilon}</math> (А. А. Глибичук).

=== Дзета-функция на Риман ===
==== Хипотеза на А. Селберг ====
През 1984 година Карацуба установява,<ref>{{cite journal| last=Карацуба| first=А. А.| title= О нулях функции ζ(s) на коротких промежутках критической прямой | pages=569 – 584| journal= Изв. РАН. Сер. матем.| issue=48:3| year=1984}}</ref><ref>{{cite journal| last=Карацуба| first=А. А.| title= Ра''с''пределение нулей функции ζ(1/2 + it) | pages=1214 – 1224 | journal= Изв. РАН. Сер. матем.| issue=48:6| year=1984}}</ref><ref>{{cite journal| last=Карацуба| first=А. А.| title= О нулях дзета-функции Римана на критической прямой | pages=167 – 178| journal= Труды МИАН| issue=167| year=1985}}</ref> че при фиксирано <math>\varepsilon</math>, изпълняващо условието <math>0<\varepsilon < 0.001</math>, достатъчно голямо <math>T</math> и <math>H = T^{a+\varepsilon}</math>, <math>a = \tfrac{27}{82} = \tfrac{1}{3} -\tfrac{1}{246}</math>, интервалът <math>(T,T+H)</math> съдържа не по-малко от <math>cH\ln T</math> реални нули на [[Дзета-функция на Риман|дзета-функцията на Риман]] <math>\zeta\Bigl(\tfrac{1}{2}+it\Bigr)</math>.

Това твърдение през 1942 е изложено като хипотеза на А. Селберг, който е доказал неговата вярност за случая <math>H\ge T^{1/2+\varepsilon}</math>. Оценките на Селберг и Карацуба са неподобряеми по отношение на порядък на нарастване при <math>\zeta\Bigl(\tfrac{1}{2}+it\Bigr)</math>.

==== Разпределение на нулите на дзета-функцията на Риман в кратки отрязъци от критическата права ====
На Карацуба принадлежат<ref>{{cite journal| last=Карацуба| first=А. А.| title= О количестве нулей дзета-функции Римана, лежащих на почти всех коротких промежутках критической прямой | pages=372 – 397| journal= Изв. РАН. Сер. матем.| issue=56:2| year=1992}}</ref> редица резултати за разпределението на нулите на <math>\zeta(s)</math> в „кратки“ отрязъци от критическата права. Той е доказал, че аналог на '''хипотезата на Селберг''' е валидна за „почти всички“ отрязъци <math>(T,T+H]</math>, <math>H = T^{\varepsilon}</math>, където <math>\varepsilon</math> е производно малко фиксирано положително число. Карацуба разработва (1992) нов подход за изследване на нулите на дзета-функцията на Риман върху „свръхкратки“ интервали на критическата права, т.е. интервали от типа <math>(T, T+H]</math>, където дължината <math>H</math> расте по-бавно от произволно малка степен на <math>T</math>. В частност, той е доказал, че за всеки две зададени числа <math>\varepsilon</math>, <math>\varepsilon_{1}</math> с условието <math>0<\varepsilon, \varepsilon_{1}<1</math> почти всички интервали <math>(T,T+H]</math> при <math>H\ge\exp{\{(\ln T)^{\varepsilon}\}}</math> съдържат не по-малко от <math>H(\ln T)^{1-\varepsilon_{1}}</math> нули на функцията <math>\zeta\bigl(\tfrac{1}{2}+it\bigr)</math>. Тази оценка е твърде близко до това, което би следвало от [[Хипотеза на Риман|Хипотезата на Риман]].

==== Нули на линейни комбинации от L-редове на Дирихле ====
Карацуба създава нов метод<ref>{{cite journal| last=Карацуба| first=А. А.| title= О нулях функции Дэвенпорта–Хейльбронна, лежащих на критической прямой | pages=303 – 315| journal= Изв. РАН. Сер. матем.| issue=54:2| year=1990}}</ref><ref>{{cite journal| last=Karatsuba | first=A. A. | title= On Zeros of the Davenport–Heilbronn Function | pages=271 – 293| journal= Proc. Amalfi Conf. Analytic Number Theory| year=1992}}</ref><ref>{{cite journal| last=Карацуба| first=А. А.| title= О нулях арифметических рядов Дирихле, не имеющих эйлерова произведения | pages=3 – 14| journal= Изв. РАН. Сер. матем.| issue=57:5| year=1993}}</ref> за изследване на нулите на функции, представими като линейни комбинации от [[<math>L</math> -функции на Дирихле]]. Като прост пример на функция от такъв род служи функцията на [[Харолд Дейвънпорт|Дейвънпорт]]-[[Хейлброн]], която се определя чрез равенството

: <math>
f(s)=\tfrac{1}{2}(1-i\kappa)L(s,\chi)+\tfrac{1}{2}(1
\,+\,i\kappa)L(s,\bar{\chi}),
</math>

където <math>\chi</math> е неглавен характер по модул <math>5</math> (<math>\chi(1) = 1</math>,
<math>\chi(2) = i</math>, <math>\chi(3) = -i</math>, <math>\chi(4) = -1</math>, <math>\chi(5) = 0</math>,
<math>\chi(n+5) = \chi(n)</math> за всяко <math>n</math>),

: <math>
\kappa=\frac{\sqrt{10-2\sqrt{5}}-2}{\sqrt{5}-1}.
</math>

За <math>f(s)</math> [[Хипотеза на Риман|хипотезата на Риман]] не е вярна, но критичната права <math>Re \ s = \tfrac{1}{2}</math> съдържа, аномално много нули на тази функция.

Карацуба установява (1989), че интервалът <math>(T, T+H]</math>, <math>H = T^{27/82+\varepsilon}</math> съдържа не по-малко от

: <math>
H(\ln T)^{1/2}e^{-c\sqrt{\ln\ln T}}
</math>

нули на функцията <math>f\bigl(\tfrac{1}{2}+it\bigr)</math>. Подобни резултати са получени от Карацуба и за линейни комбинации, съдържащи произволен (краен) брой събираеми; като при това показателят на степента <math>\tfrac{1}{2}</math> се заменя с малко число <math>\beta</math>, зависещо само от вида на линейната комбинация.

==== Граница на нулите на дзета-функцията и многомерния проблем за делителите на Дирихле ====
[[Файл:A.A.Karatsuba on lecture.jpg|мини|Лекция в Математическия институт на името на В.А. Стеклов]]
На Карацуба принадлежи принципно нов резултат<ref>{{cite journal| last=Карацуба| first=А. А.| title= Равномерная оценка остаточного члена в проблеме делителей Дирихле | pages=475 – 483| journal= Изв. АН СССР. Сер. матем.| issue=36:3| year=1972}}</ref> в многомерния проблем за делителите на Дирихле, който е свързан с намирането при <math>x\to +\infty</math> на броя <math>D_{k}(x)</math> на решенията на неравенството <math>x_{1}*\ldots *x_{k}\le x</math> в естествени числа <math>x_{1}, \ldots, x_{k}</math>. За <math>D_{k}(x)</math> има асимптотична формула от вида

: <math>
D_{k}(x) = xP_{k-1}(\ln x)+R_{k}(x)
</math>,

в която <math>P_{k-1}(u)</math> е многочлен от степен <math>(k-1)</math>, коефициентите на който зависят от <math>k</math> и могат да бъдат намерени явно, а <math>R_{k}(x)</math> е остатъчен член, всички известни (до 1960 г.) оценки за който са имали вида

: <math>
|R_{k}(x)| \le x^{1-\alpha(k)}(c\ln x)^{k}
</math>,

където <math>\alpha = \frac{1}{ak+b}</math>, а <math>a,b,c</math> са абсолютни положителни константи.

Карацуба получава по-точна оценка за <math>R_{k}(x)</math>, в която величината <math>\alpha(k)</math> има порядък <math>k^{-2/3}</math> и намалява значително по-бавно, отколкото <math>\alpha(k)</math> в предишните оценки. Оценката на Карацуба е равномерна по <math>x</math> и <math>k</math>; в частност величината <math>k</math> може да расте с нарастването на <math>x</math> (като някоя степен на логаритъм от <math>x</math>). (Подобен, но по-слаб резултат бил получен през 1960 г. от немския математик Рихтер, работата на който е останала неизвестна на съветските математици поне до средата на 70-те години).

Извеждането на оценки за <math>R_{k}(x)</math> се опира на ред твърдения, еквивалентни на теоремата за границата на нулите на дзета-функцията на Риман, получаеми по методи на И.М.Виноградов, т.е. теорема за това, че <math>\zeta(s)</math> няма нули в областта

: <math>
Re \ s \ge 1 - \frac{c}{(\ln |t|)^{2/3}(\ln\ln
|t|)^{1/3}},\quad |t|> 10
</math>.

Карацуба установява<ref>{{cite journal| last=Karatsuba| first=A. A.| title= The multidimensional Dirichlet divisor problem and zero free regions for the Riemann zeta function| pages=131 – 140| journal= Functiones et Approximatio| issue= XXVIII| year=2000}}</ref><ref>{{cite journal| last=Карацуба| first=А. А.| title= О связи многомерной проблемы делителей Дирихле с границей нулей ζ(s) | pages=477 – 480| journal= Матем. заметки| issue=70:3| year=2001}}</ref> (2000) обратна връзка между оценката на величината <math>R_{k}(x)</math> с поведението на <math>\zeta(s)</math> в близост до правата <math>Re \ s = 1</math>. В частност, той доказал, че ако <math>\alpha(y)</math> е произволна ненарастваща функция, удовлетворяваща условието <math>1/y \le \alpha(y)\le 1/2</math>, такава, че при всички <math>k\ge 2</math> е изпълнена оценката

: <math>
|R_{k}(x)| \le x^{1-\alpha(k)}(c\ln x)^{k}
</math>,

то <math>\zeta(s)</math> няма нули в областта

: <math>
Re \ s \ge 1 - c_{1}\,\frac{\alpha(\ln |t|)}{\ln\ln |t|},\quad |t|\ge e^{2}
</math>

(<math>c, c_{1}</math> – абсолютни константи).

==== Оценки отдолу за максимума на модула на дзета-функцията в малки области от критичната ивица и в къси интервали от критичната права ====
От Карацуба са въведени и изследвани<ref>{{cite journal| last=Карацуба| first=А. А.| title= О нижних оценках максимума модуля ζ(s) в малых областях критической полосы | pages=796 – 798| journal= Матем. заметки| issue=70:5| year=2001}}</ref>
<ref>{{cite journal| last=Карацуба| first=А. А.| title= О нижних оценках максимума модуля дзета-функции Римана на коротких промежутках критической прямой | pages=99 – 104| journal= Изв. РАН. Сер. матем.| issue=68:8| year=2004}}</ref> функциите <math>F(T;H)</math> и <math>G(s_{0};\Delta)</math>, определени с равенствата

: <math>
F(T;H) = \max_{|t-T|\le H}\bigl|\zeta\bigl(\tfrac{1}{2}+it\bigr)\bigr|,\quad
G(s_{0};\Delta) = \max_{|s-s_{0}|\le\Delta}|\zeta(s)|.
</math>

Тук <math>T</math> е достатъчно голямо положително число, <math>0<H\ll \ln\ln T</math>, <math>s_{0} = \sigma_{0}+iT</math>, <math>\tfrac{1}{2}\le\sigma_{0}\le 1</math>, <math>0<\Delta < \tfrac{1}{3}</math>. Оценки отдолу за величините <math>F</math> и <math>G</math> показват колко големи (по абсолютна стойност) значения може да приема <math>\zeta(s)</math> на къси отрязъци от критичната права или в малки околности на точки от критичната ивица <math>0\le Re \ s\le 1</math>. Случаят <math>H\gg \ln\ln T</math> е бил изследван по-рано от Рамачандра; случай <math>\Delta > c</math>, където <math>c</math> е достатъчно голяма константа е тривиален.

Карацуба доказва в частност, че ако величините <math>H</math> и <math>\Delta</math> превъзхождат някои достатъчно малки константи, то са изпълнени оценките

: <math>
F(T;H) \ge T^{- c_{1}},\quad G(s_{0};
\Delta) \ge T^{- c_{2}},
</math>

където <math>c_{1}, c_{2}</math> са някои абсолютни константи.

==== Поведение на аргумента на дзета-функцията върху критичната права ====
Карацуба получава редица нови резултати <ref>{{cite journal| last=Карацуба| first=А. А.| title= Плотностная теорема и поведение аргумента дзета-функции Римана | pages=448 – 449| journal= Матем. заметки| issue=60:3| year=1996}}</ref>
<ref>{{cite journal| last=Карацуба| first=А. А.| title= О функции S(t) | pages=27 – 56 | journal= Изв. РАН. Сер. матем.| issue=60:5| year=1996}}</ref>, касаещи поведението на функцията <math>S(t) = \frac{1}{\pi}\arg{\zeta\bigl(\tfrac{1}{2}+it\bigr)}</math>, наричана аргумент на [[Дзета-функция на Риман|дзета-функцията на Риман]] върху критичната права (тук <math>\arg{\zeta\bigl(\tfrac{1}{2}+it\bigr)}</math> означава нарастването на произволен непрекъснат клон на <math>\arg\zeta(s)</math> по начупена линия, съединяваща точките <math>2, 2+it</math> и <math>\tfrac{1}{2}+it</math>. В това число – теоремата за средната стойност на функцията <math>S(t)</math> и нейната примитивна <math>S_{1}(t) = \int_{0}^{t}S(u)du</math> върху интервали от реалната права, а също така теорема за това, че всеки интервал <math>(T,T+H]</math> при <math>H \ge T^{27/82+\varepsilon}</math> съдържа не по-малко от

: <math>
H(\ln T)^{1/3}e^{-c\sqrt{\ln\ln T}}
</math>

точки на смяна на знака на функцията <math>S(t)</math>. По-рано подобни резултати били установени от [[Атле Селберг|А.Селберг]] за случая <math>H\ge T^{1/2+\varepsilon}</math>.

=== Характери на Дирихле ===
==== Оценки на кратки суми от характери в крайни полета ====
В края на 60-те години Карацуба, занимавайки се с оценки на кратки суми от [[характери]], създава <ref>{{cite journal| last=Карацуба| first=А. А.| title= Суммы характеров и первообразные корни в конечных полях | pages=1287 – 1289 | journal= Докл. АН СССР| issue=180:6| year=1968}}</ref> нов метод, който позволява да се получат нетривиални оценки на кратки суми от характери в [[крайни полета]]. Нека <math>n\ge 2</math> е фиксирано цяло число,
<math>F(x) = x^{n}+a_{n-1}x^{n-1}+\ldots + a_{1}x + a_{0}</math> – неразложим над полето <math>\mathbb{Q}</math> на рационалните числа полином, <math>\theta</math> – корен на уравнението <math>F(\theta) = 0</math>, <math>\mathbb{Q}(\theta)</math> – разширение на полето <math>\mathbb{Q}</math>, <math>\omega_{1},\ldots, \omega_{n}</math> – базис за <math>\mathbb{Q}(\theta)</math>, <math>\omega_{1} = 1</math>, <math>\omega_{2} = \theta</math>,
<math>\omega_{3} = \theta^{2}, \ldots, \omega_{n} = \theta^{n-1}</math>. Нека по-нататък <math>p</math> е достатъчно голямо просто число, такова че <math>F(x)</math> е неразложим по модул <math>p</math>, <math>\mathrm{GF}(p^{n})</math> – [[полето на Галоа]] с базис <math>\omega_{1}, \omega_{2}, \ldots, \omega_{n}</math>, <math>\chi</math> – неглавен [[характер на Дирихле]] за полето <math>\mathrm{GF}(p^{n})</math>. Нека накрая <math>\nu_{1},\ldots, \nu_{n}</math> са някои неотрицателни цели числа, <math>D(X)</math> е множеството от елементи <math>\bar{x}</math> на полето на Галоа <math>\mathrm{GF}(p^{n})</math>,

: <math>
\bar{x} = x_{1}\omega_{1} + \ldots + x_{n}\omega_{n}
</math>,

такива че за всяко <math>i</math>, <math>1\le i\le n</math>, са изпълнени неравенставта:

: <math>
\nu_{i}< x_{i}< \nu_{i} + X
</math>.

Карацуба доказва, че при произволно фиксирано <math>k</math>, <math>k\ge n+1</math>, и произволно <math>X</math> с условието

: <math>
p^{\frac{1}{4}+\frac{1}{4k}} \le X \le p^{\frac{1}{2}+\frac{1}{4k}}
</math>

е изпълнена оценката:

: <math>
\biggl|\sum\limits_{\bar{x}\in D(X)}\chi(\bar{x})\biggr| \le c\Bigl(X^{1-\frac{1}{k}}p^{\frac{1}{4k}+\frac{1}{
4k^{2}}}\Bigr)^{\!\!n}(\ln p)^{\gamma},
</math>

където <math>\gamma = \frac{1}{k}(2^{n+1}-1)</math>, а константата <math>c</math> зависи от <math>n</math> и базиса <math>\omega_{1},\ldots, \omega_{n}</math>.

==== Оценки на линейни суми от характери по изместени прости числа ====
Карацуба разработва ред нови прийоми, приложението на които наред с метода на Виноградов за оценка на суми с прости числа, му позволяват през 1970 г. да получи<ref>{{cite journal| last=Карацуба| first=А. А.| title= Об оценках сумм характеров | pages=20 – 30 | journal= Изв. АН СССР. Сер. матем.| issue=34:1| year=1970}}</ref><ref>{{cite journal| last=Карацуба| first=А. А.| title= Суммы характеров с простыми числами | pages=299 – 321 | journal= Изв. АН СССР. Сер. матем.| issue=34:2| year=1970}}</ref> оценка за сумата на стойностите на неглавния характер по прост модул <math>q</math> върху редици от изместени прости числа, а именно оценка от вида

: <math>\biggl|\sum\limits_{p\le N}\chi(p+k)\biggr|\le cNq^{-\frac{\varepsilon^{2}}{1024}},</math>

където <math>k</math> е цяло число, изпълняващо условието <math>k\not\equiv 0 \pmod q</math>, <math>\varepsilon</math> – произволно малко фиксирано число, <math>N\ge q^{1/2+\varepsilon}</math>, а константата <math>c</math> зависи само от <math>\varepsilon</math>.

Това твърдение представлява значително усилване на оценката на Виноградов, която е нетривиална при <math>N\ge q^{3/4+\varepsilon}</math>.

През 1971 г. по време на Международната конференция по теория на числата, посветена на 80-ата годишнина на Виноградов, академикът [[Юрий Линник]] отбелязва следното:

{{цитат|Твърди важни са изследванията на И.М.Виноградов върху асимптотичната формула за сума от [[характери на Дирихле]] върху изместени прости числа <math>\sum\limits_{p\le N}\chi(p+k)</math>, която дава степенно понижение в сравнение с <math>N</math> вече при <math>N\ge q^{3/4+\varepsilon}</math>, <math>\varepsilon > 0</math>, където <math>q</math> е модул на характера. Тази оценка има принципно значение, тъй като по дълбочина превъзхожда това, което дава непосредственото прилагане на разширената [[хипотеза на Риман]] и, по всяка вероятност, е истина, по-дълбока от тази хипотеза (ако тя е вярна). Неодавна тази оценка е подобрена от Карацуба.}}

Този резултат е бил пренесен от Карацуба и за случая, когато <math>p</math> пробягва прости числа от аритметична прогресия, разликата на която расте заедно с нарастването на модула <math>q</math>.

==== Оценки за суми от характери от полином с прости аргументи ====
На Карацуба принадлежат<ref>{{cite journal| last=Карацуба| first=А. А.| title= Суммы характеров и первообразные корни в конечных полях | pages=1287 – 1289 | journal= Докл. АН СССР| issue=180:6| year=1968}}</ref><ref>{{cite journal| last=Карацуба| first=А. А.| title= Суммы характеров по последовательности сдвинутых простых чисел и их применения | pages=155 – 159| journal= Матем. заметки| issue=17:1| year=1975}}</ref> редица оценки за суми на характери на Дирихле от полиноми от втора степен за случая, когато аргументът им пробягва някаква кратка редица от поредни прости числа. Нека например <math>q</math> е достатъчно голямо просто число, <math>f(x) = (x-a)(x-b)</math>, където <math>a</math> и <math>b</math> са цели числа, удовлетворяващи условието <math>ab(a-b)\not\equiv 0 \pmod q</math>, и нека <math>\left(\frac{n}{q}\right)</math> означава [[Символ на Льожандър|символа на Льожандър]]. Тогава при всяко фиксирано <math>\varepsilon</math> с условието <math>0<\varepsilon<\tfrac{1}{2}</math> и <math>N>q^{3/4+\varepsilon}</math> за сумите <math>S_{N}</math>,

: <math>
S_{N} = \sum\limits_{p\le N}\biggl(\frac{f(p)}{q}\biggr),
</math>

е изпълнена оценката

: <math>
|S_{N}| \le c\pi(N)q^{-\frac{\varepsilon^{2}}{100}}
</math>

(Тук <math>p</math> пробягва поредни прости числа, <math>\pi(N)</math> е броят на простите числа, ненадминаващи <math>N</math>, а <math>c</math> е константа, зависеща само от <math>\varepsilon</math>).

Подобна оценка е била получена от Карацуба и за случая, когато <math>p</math> пробягва редица от прости числа, принадлежащи на аритметична прогресия, разликата на които може да расте заедно с модула <math>q</math>.

От Карацуба е била изказана хипотеза, според която нетривиалната оценка за сумите <math>S_{N}</math> при <math>N</math>, „малки“ в сравнение с <math>q</math>, остава вярна и ако заменим <math>f(x)</math> с произовлен полином от <math>n</math>-та степен, който не е квадрат по модул <math>q</math>. Тази хипотеза до момента не е доказана.

==== Оценки отдолу за суми от характери от полиноми ====
Карацуба е построил <ref>{{cite journal| last=Карацуба| first=А. А.| title= Об оценках снизу сумм характеров от многочленов| pages=67 – 72|journal= Матем. заметки| issue=14:1| year=1973}}</ref> безкрайна редица от прости числа <math>p</math> и редица от многочлени <math>f(x)</math> от степен <math>n</math> с цели коефициенти, такива че <math>f(x)</math> не е точен квадрат по модул <math>p</math>,

: <math>\frac{4(p-1)}{\ln p} \le n \le \frac{8(p-1)}{\ln p},</math>

и такива, че

: <math>\sum\limits_{x =1}^{p}\left(\frac{f(x)}{p}\right) = p. </math>

С други думи за всяко <math>x</math> стойността <math>f(x)</math> се оказва квадратичен остатък по модул <math>p</math>.

Този резултат показва, че оценката на [[Андре Вейл|А.Вейл]]

: <math>\biggl|\sum\limits_{x=1}^{p}\left(\frac{f(x)}{p}\right)\biggr| \le (n-1)\sqrt{p}</math>

не може да бъде подобрена съществено, като дясната част на последното неравенство
се замени например с величината <math>C\sqrt{n}\sqrt{p}</math>, където <math>C</math> е абсолютна константа.

==== Суми на характери на адитивни редици ====
Карацуба е открил нов метод <ref>{{cite journal| last=Карацуба| first=А. А.| title= Ра''с''пределение степенных вычетов и невычетов в аддитивных последовательностях| pages=759 – 760|journal= Докл. АН СССР| issue=196:4| year=1971}}</ref><ref>{{cite journal| last=Карацуба| first=А. А.| title= Ра''с''пределение значений характеров Дирихле на аддитивных последовательностях| pages=543 – 545|journal= Докл. АН СССР| issue=319:3| year=1991}}</ref>, позволяващ да се намира твърде точни оценки за сумите от стойностите на неглавните характери на Дирихле върху адитивни редици, т.е. редици, състоящи се от числа от вида {{nobr|<math>x+y</math>}}, където променливите <math>x</math> и <math>y</math> независимо едно от друго пробягват, съответно някакви множества <math>A</math> и <math>B</math>.

Най-яркият примерен резултат от такъв вид е следното твърдение, намиращо приложение при решенията на широк клас задачи, свързани със сумирането на стойностите на характерите на Дирихле. Нека <math>\varepsilon</math> – произволно малко фиксирано число, <math>0<\varepsilon<\tfrac{1}{2}</math>, <math>q</math> – достатъчно голямо просто число, <math>\chi</math> – неглавен характер по модул <math>q</math>. Нека, също, <math>A</math> и <math>B</math> – произволни подмодмножества на пълната система от остатъци по модул <math>q</math>, удовлетворяващи единствено условията <math>\|A\|>q^{\varepsilon}</math>, <math>\|B\|>q^{1/2+\varepsilon}</math>. Тогава е изпълнена оценката:

: <math>
\biggl|\sum\limits_{x\in A}\sum\limits_{y\in B}\chi(x+y)\biggr|\le c\|A\|\cdot\|B\| q^{-\frac{\varepsilon^{2}}{20}},\quad c = c(\varepsilon)>0.
</math>

Методът на Карацуба позволява получаването на нетривиални оценки за суми от такъв род и в някои случаи, когато указаните горе условия за множествата <math>A</math> и <math>B</math> се заменят с други, например: <math>\|A\|>q^{\varepsilon}</math>,
<math>\sqrt{\|A\|}\cdot\|B\|> q^{1/2+\varepsilon}.</math>

В случая, когато <math>A</math> и <math>B</math> представляват множества от прости числа от интервалите <math>(1,X]</math>, <math>(1,Y]</math> съответно, така че <math>X\ge q^{1/4+\varepsilon}</math>, <math>Y\ge q^{1/4+\varepsilon}</math>, е изпълнена оценка от вида:

: <math>
\biggl|\sum\limits_{p\le X}\sum\limits_{p'\le
Y}\chi(p+p')\biggr|\le c\pi(X)\pi(Y)q^{-c_{1}\varepsilon^{2}},
</math>

където <math>\pi(Z)</math> – броят на простите числа, ненадминаващи <math>Z</math>, <math>c = c(\varepsilon)>0</math>, а <math>c_{1}</math> е абсолютна константа.

==== Разпределение на степенни остатъци и първообразни корени в редки редици ====
От Карацуба са получени <ref>{{cite journal| last=Karatsuba| first=A. A.| title= Sums of characters with prime numbers and their applications | pages=155 – 162| journal= Tatra Mountains Math. Publ.| issue=20| year=2000}}</ref>
<ref>{{cite journal| last=Карацуба| first=А. А.| title= Суммы характеров с весами | pages=29 – 42 | journal= Изв. РАН. Сер. матем.| issue=64:2| year=2000}}</ref> (2000) нетривиални оценкки за суми от стойности на характери на Дирихле „с тегла“, т.е. суми от събираеми от вида <math>\chi(n)f(n)</math>, където <math>f(n)</math> – функция на естествен аргумент. Оценки от такъв вид намират приложение при решенията на широк кръг задачи в теорията на числата, свързани с разпределението на степенни остатъци (неостатъци), а също така първообразни корени в едни или други редици.

Нека <math>k\ge 2</math> – цяло число, <math>q</math> – достатъчно голямо просто число, <math>(a,q) = 1</math>, <math>|a|\le \sqrt{q}</math>, <math>N\ge q^{\frac{1}{2} - \frac{1}{2(k+1)}+\varepsilon}</math>, където <math>0<\varepsilon<\min{\{0.01, \tfrac{2}{3(k+1)}\}}</math>, и нека накрая

: <math>
D_{k}(x) = \sum\limits_{x_{1}*\ldots *x_{k}\le x}1 = \sum\limits_{n\le
x}\tau_{k}(n)
</math>

(за асимптотично изразяване за <math>D_{k}(x)</math> погледни по-горе, в раздела, посветен на многомерния проблем за делители на Дирихле). За сумите <math>V_{1}(x)</math> и <math>V_{2}(x)</math> от величините <math>\tau_{k}(n)</math>, разпрострени върху стойностите <math>n \le x</math>, за които числата <math>(n+a)</math> са квадратични остатъци (съответно неостатъци) по модул <math>q</math>, Карацуба е получил асимптотични формули от вида

: <math>
V_{1}(x) = \tfrac{1}{2}D_{k}(x) + O\bigl(xq^{-0.01\varepsilon^{2}}\bigr),\quad
V_{2}(x) = \tfrac{1}{2}D_{k}(x) + O\bigl(xq^{-0.01\varepsilon^{2}}\bigr)
</math>.

Аналогично за сумата <math>V(x)</math> от величините <math>\tau_{k}(n)</math>, взета по всички <math>n\le x</math>, за които <math>(n+a)</math> е първообразен корен по модул <math>q</math>, се получава асимптотично изразяване от вида

: <math>
V(x) = \left(1 - \frac{1}{p_{1}}\right)\ldots \left(1 -
\frac{1}{p_{s}}\right)D_{k}(x) + O\bigl(xq^{-0.01\varepsilon^{2}}\bigr)
</math>,

където <math>p_{1},\ldots, p_{s}</math> – всички прости делители на <math>q-1</math>.

Методът, развит от Карацуба, е приложен от него и към задачи за разпределение на степенните остатъци (неостатъци) в последователност от изместени прости числа от вида <math>p+a</math>, числа от вида <math>x^{2}+y^{2}+a</math> и т.н.

== Работа в късните му години ==
[[Файл:A.A.Karatsuba_Pamir.jpg|мини|На памирско възвишение]]

В късните си години, освен с изследвания в теорията на числата, Карацуба изучава някои проблеми от [[Теоретична физика|теоретичната физика]]<ref>{{cite journal| author = Anatolii A. Karatsuba and Ekatherina A. Karatsuba| title= Physical mathematics in number theory | journal= Functional Analysis and Other Mathematics| issue= 3:2| year= 2010}}</ref>, по-конкретно в сферата на [[Квантова теория на полето|квантовата теория на полето]]. Прилагайки една от неговите теореми и други подходи от теорията на числата, той извежда нови резултати <ref>{{cite journal| author = Karatsuba A. A., Karatsuba E. A.| title= Application of ATS in a quantum-optical model| pages=211 – 232| journal= Analysis and Mathematical Physics: Trends in Mathematics| Birkhäuser Verlag, Basel| year= 2009}}</ref>
<ref>{{cite journal| author = Karatsuba A. A., Karatsuba E. A.| title= A resummation formula for collapse and revival in the Jaynes–Cummings model| pages=195304, 16| journal= J. Phys. A: Math. Theor.| issue= 42| year= 2009| doi= 10.1088/1751 – 8113/42/19/195304}}</ref> в модела на Джейнс-Къмингс в [[Квантова оптика|квантовите оптики]].

== Личен живот ==
Карацуба е женен за Диана Василиевна Сенченко, негова бивша съкурсничка в [[Московски държавен университет|Московския държавен университет „Ломоносов“]], [[факултет по математика и механика]], и настоящ университетски преподавател. Тяхната дъщеря Екатерина Анатолиевна Карацуба е водещ изследовател в [[Изчислителен център „Дородницин“|изчислителния център „Дородницин“]], доктор на физико-математическите науки.

[[Файл:A.A.Karatsuba in Crimea.jpg|мини|В Крим]]
През целия си живот Карацуба практикува множество спортове: в младите си години, атлетика, по-късно спелеология и планински туризъм. 11 пъти е изкачвал върхове над 7000 м:
* [[Исмаил Самани (връх)|Връх Исмаил Самани]] (най-високият в СССР) през 1977 и 1985;
* [[Ленин (връх)|Връх Ленин]] през 1968 и 1979;
* [[Корженевская (връх)|Връх Корженевская]] през 1980, 1982, 1983, 1985, 1986, 1988 и 1991.

Четири пъти е изкачвал връх [[Елбрус]]. Качвал се е в планините на [[Кавказ]], [[Памир|Памирските планини]] и, особено през последните години от живота си, [[Тян Шан]] в [[Залиски Алатау]] и [[Тески Ала-ту]].

Карацуба е трастен любител и познавач на класическата музика, особено на творчеството на [[Йохан Себастиан Бах]] и [[Антонио Вивалди]]. Той редовно посещава концерти на [[Консерватория|Московската Консерватория]], обича концертите на [[Святослав Рихтер]], [[Леонид Коган]], [[Мстислав Ростропович]], [[Виктор Третяков]], [[Андрей Корсаков]] и неговата група „Концертино“, [[Владимир Овчинников]], [[Николай Лугански]].

== Вижте също ==
* [[АТС теорема]]
* [[Диаграма на Мур]]
* [[Умножение на Карацуба]]

== Бележки ==
<references/>

== Външни препратки ==
* {{икона|ru}} [http://www.mi.ras.ru/~karatsuba/list.html Списък с научни трудове] на сайта на МИАН
* {{икона|ru}} [http://www.mi.ras.ru/~karatsuba/ Данни за научните интереси, образованието и професионалната кариера] на сайта на МИАН

{{Нормативен контрол}}
{{СОРТКАТ:Карацуба, Анатолий}}
[[Категория:Руски математици]]
[[Категория:Математици (анализ)]]
[[Категория:Математици (теория на числата)]]
[[Категория:Възпитаници на Московския университет]]
[[Категория:Преподаватели в Московския университет]]
[[Категория:Руски спортисти]]
[[Категория:Съветски алпинисти]]
[[Категория:Родени в Грозни]]
[[Категория:Починали в Москва]]