Анатолий Карацуба

Анатолий Карацуба Анатолий Алексеевич Карацуба
руски математик
Роден	31 януари 1937 г. Грозни, Русия
Починал	28 септември 2008 г. Москва, Русия
Учил в	Московски държавен университет
Научна дейност
Област	математика
Работил в	МИ „Стеклов“, МДУ
Анатолий Карацуба в Общомедия

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

Образование и работа

А. А. Карацуба като ученик

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

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

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

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

Награди и титли

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

Ранни изследвания в информатиката

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

Автомати

В статията на Едуард Ф. Мур$(n;m;p)$ автомат (или машина) $S$ е дефиниран като устройство с $n$ състояния, $m$ входни символа и $p$ изходни символа. Доказани са девет теореми за структурата на $S$. По-късно такива „$S$ машини“ получават името Автомат на Мур. В края на статията в раздела „Нови проблеми“ Мур формулира проблема за подобряване на оценките, които той е получил в Теореми 8 и 9:

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

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

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

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

Тези 2 теореми са доказани от Карацуба в курсова работа през четвъртата година от обучението му. Последващата публикация е изпратена в списанието „Успехи математических наук“ на 17 декември 1958 г. и е публикувана през юни 1960 г.. До днес (12 април 2010) този резултат на Карацуба, който по-късно получава названието „Теорема на Мур-Карацуба“, остава единственият точен нелинеен резултат в автоматната теория и в подобните проблеми от теорията на сложността на изчисленията.

Бързи алгоритми

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

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

През 1960 г. Анатолий Карацуба открива нов метод за умножаване на 2 $n$-цифрени числа, който сега е познат като „Алгоритъм на Карацуба“, при който сложността е от порядък

$M(n)=O(n^{\log _{2}3})=O(n^{1,58496\ldots }),$ с което опровергава $n^{2}$ хипотезата. Този резултат е обяснен от Карацуба на семинара на Колмогоров в Московския държавен университет през 1960 г., след което семинарът на Колмогоров приключва своята дейност. Първата статия, описваща метода, е подготвена от самия Колмогоров, където той представя 2 различни и несвързани един с друг резултати на 2 от своите студенти. В статията Колмогоров ясно уточнява, че теорема (несвързана с бързото умножаване) принадлежи на Ю. Офман и друга (с първия бърз алгоритъм за умножение) принадлежи на А. Карацуба. Методът на Карацуба по-късно е наречен „Алгоритъм разделяй и владей“. Другите имена на този метод, в зависимост от областта, в която се прилага той, са „Бинарно разделяне“, „Принцип на дихотомията“ и т.н.

По-късно въз основа на идеята на Карацуба са конструирани хиляди бързи алгоритми, много от които са негови директни обобщения, като алгоритъма на Шонхейдж-Щрасен и алгоритъма на Щрасен за умножение на матрици. През последните години терминът „Разделяй и владей“ е използван за операции, които разбиват даден проблем на части, което вече не е свързано с бързите изчислителни алгоритми.

Френският математик и философ Жан-Пол Делаайе описва метода за умножение на Карацуба като „един от най-полезните резултати в математиката“.

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

Основни изследвания

В статията „Върху математическите работи на проф. А. А. Карацуба“ , публикувана по случай 60-ата годишнина на А. А. Карацуба, неговите бивши студенти Г. И. Аркипов и Владимир Чубариков характеризират специалните черти на изследванията на Карацуба по следния начин:

„

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

“

Главните разработки на А. А. Карацуба са публикувани в повече от 160 статии и монографии.

Тригонометрични суми и тригонометрични интеграли

p-адичен метод

Карацуба създава $p$-адичния метод в теорията на тригонометричните суми. Оценките на така наречените $L$-суми от типа

$S=\sum _{x=1}^{P}e^{2\pi i(a_{1}x/p^{n}+\dots a_{n}x^{n}/p)},\quad (a_{s},p)=1,\quad 1\leq s\leq n,$

получени в , довеждат до

• нови ограничения за нулите на $L$-редовете на Дирихле по модул степен на просто число.

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

$x_{1}^{n}+\dots +x_{t}^{n}\equiv N{\pmod {p^{k}}},\quad 1\leq x_{s}\leq P,\quad 1\leq s\leq n,\quad P<p^{k}$

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

Карацуба е първият, който осъзнава, че съществува $p$–адичен аналог на така наречения „принцип на включването“ на Ойлер-Виноградов. Карацуба също пресмята $p$-адичния аналог на $u$-числата на Виноградов, при оценката на броя на решенията на сравнението от Варингов тип.

Нека имаме:

$x_{1}^{n}+\dots +x_{t}^{n}\equiv N{\pmod {Q}},\quad 1\leq x_{s}\leq P,\quad 1\leq s\leq t,\quad (1)$

така че

$P^{r}\leq Q<P^{r+1},\quad 1\leq r\leq {\frac {1}{12}}{\sqrt {n}},\quad Q=p^{k},\quad k\geq 4(r+1)n,$

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

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

Друг компонент от $p$-адичния метод на Карацуба е преходът от непълни системи от уравнения до пълни системи от такива за сметка на локална $p$-адична смяна на неизвестните.

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

${\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}}$

$1\leq x_{1},\dots ,x_{k},y_{1},\dots ,y_{k}\leq P,\quad 1\leq m_{1}<m_{2}<\dots <m_{s}<m_{s+1}=n.$

Карацуаба доказва, че броят на решенията $I_{k}$ на тази система от уравнения при $k\geq 6rn\log n$ изпълнява оценката

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

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

Задачата на Хуа-ло-Кен за експонентата на сходимост на интеграла от проблема на Тери

$p$-адичният метод на Карацуба включва оценки на мярката на множеството от точки с малки значения на функции посредством техните параметри (коефициенти и т.н.) и, обратно, оценки на тези параметри посредством мярката на множества в реалната и $p$-адичната метрики. Тази страна на метода се проявява особено ярко при оценки на тригонометрични интеграли, което довежда до решението на задачата на Хуа – Ло – кен. През 1979 г. Карацуба заедно със своите ученици Архипов и Чубариков решават напълно задачата на Хуа – Ло – кен, поставена през 1937, която се състои в определянето на показателя на сходимост на интеграла

$\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},$

где $n\geq 2$ – фиксированное число.

Кратни тригонометрични суми

В периода 1966 – 1980 Карацуба създава (с участие на своите ученици Архипов и Чубариков) теорията на кратните тригонометрични суми на Херман Вайл, т.е сума от вида

$S=S(A)=\sum _{x_{1}=1}^{P_{1}}\dots \sum _{x_{r}=1}^{P_{r}}e^{2\pi iF(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}}$, където $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}}$,

$A$ – набор от реални коефициенти $\alpha (t_{1},\dots ,t_{r})$. Централният момент в тази теория, както и в теорията на тригонометричните суми на И.М.Виноградов, се състои в следващата теорема за средната стойност.

Нека $n_{1},\dots ,n_{r},P_{1},\dots ,P_{r}$ са естествени числа, $P_{1}=\min(P_{1},\dots ,P_{r})$,$m=(n_{1}+1)\dots (n_{r}+1)$. Нека $\Omega$ е $m$-мерен куб в евклидово пространство от вида

$0\leq \alpha (t_{1},\dots ,t_{r})<1$, $0\leq t_{1}\leq n_{1},\dots ,0\leq t_{r}\leq n_{r}$,

и

$J=J(P_{1},\dots ,P_{r};n_{1},\dots ,n_{r};K,r)={\underset {\Omega }{\int \dots \int }}|S(A)|^{2K}dA$.

Тогава при произволни $\tau \geq 0$ и $K\geq K_{\tau }=m\tau$, за величината $J$ имаме оценката

$J\leq K_{\tau }^{2m\tau }\varkappa ^{4\varkappa ^{2}\Delta (\tau )}2^{8m\varkappa \tau }(P_{1}\dots P_{r})^{2K}P^{-\varkappa \Delta (\tau )}$,

където $\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 }$, и естествените числа $\nu _{1},\dots ,\nu _{r}$ са такива, че:

$-1<{\frac {P_{s}}{P_{1}}}-\nu _{s}\leq 0$, $s=1,\dots ,r$.

Теоремата за средната стойност и лемата за кратностите на пресичанията на многомерни паралелепипеди лежат в основата на оценката за кратните тригонометрични суми, получени от Карацуба. Ако означим с $Q_{0}$ най-малкото общо кратно на числата $q(t_{1},\dots ,t_{r})$ с условието $t_{1}+\dots t_{r}\geq 1$, то при $Q_{0}\geq P^{1/6}$ е изпълнена оценката

$|S(A)|\leq (5n^{2n})^{r\nu (Q_{0})}(\tau (Q_{0}))^{r-1}P_{1}\dots P_{r}Q^{-0.1\mu }+2^{8r}(r\mu ^{-1})^{r-1}P_{1}\dots P_{r}P^{-0.05\mu }$,

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

Оценка на функцията на Харди в проблема на Уоринг

Прилагайки конструираната $p$-адична форма на кръговия метод на Харди-Литлууд-Рамануджан-Виноградов към оценките на тригонометричните суми, в които сумирането се извършва по числа с малки прости делители, Карацуба получава нова оценка за известната функция на Харди $G(n)$ в проблема на Уоринг (при $n\geq 400$):

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

Многомерен аналог на проблема на Уоринг

В своите по-нататъшни изследвания по проблема на Варинг, Карацуба получава следващото двумерно обобщение:

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

$x_{1}^{n-i}y_{1}^{i}+\dots +x_{k}^{n-i}y_{k}^{i}=N_{i}$, $i=0,1,\dots ,n$,

където $N_{i}$ са зададени положителни цели числа, които имат еднакъв порядък на нарастване, $N_{0}\to +\infty$, а $x_{\varkappa },y_{\varkappa }$ са неизвестни, но също положителни числа. Тази система е разрешима, ако $k>cn^{2}\log n$, а ако $k<c_{1}n^{2}$, то съществуват такива $N_{i}$, че системата няма решение.

Проблем на Артин за локалното представяне на нулата от дадена форма

В изследванията по проблема на Емил Артин за $p$-адичното представяне на нула чрез зададена форма от произволна степен, резултатите на Карацуба показват, че вместо по-ранно предполаганото степенно нарастване на броя на променливите за нетривиалното представяне на нулата чрез формата, това число променливи трябва да расте почти експоненциално спрямо степента. Карацуба заедно със своя ученик Архипов доказват,, че за всяко естествено число $r$ съществува такова $n_{0}=n_{0}(r)$ че за всяко $n\geq n_{0}$, съществува форма $F(x_{1},\dots ,x_{k})$ със степен, по-малка от $n$, с цели коефициента, броят на променливите на която е $k$, $k\geq 2^{u}$,

$u={\frac {n}{(\log _{2}n)(\log _{2}\log _{2}n)\dots \underbrace {(\log _{2}\dots \log _{2}n)} _{r}\underbrace {(\log _{2}\dots \log _{2}n)^{3}} _{r+1}}}$

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

Оценки на кратки суми на Клостерман

Карацуба създава (1993 – 1999) нов метод за оценка на кратки суми на Клостерман, т.е. тригонометрична сума от вида

$\sum \limits _{n\in A}\exp {{\biggl (}2\pi i\,{\frac {an^{*}+bn}{m}}{\biggr )}},$

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

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

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

• намиране на асимптотични формули за суми от дробни части от вида

  ${\sum _{n\leq x}}'{\biggl \{}{\frac {an^{*}+bn}{m}}{\biggr \}},{\sum _{p\leq x}}'{\biggl \{}{\frac {ap^{*}+bp}{m}}{\biggr \}},$

където $n$ пробягва последователни цели числа, удовлетворяващи $(n,m)=1$, а $p$ пробягва прости числа, не делящи модула $m$ (Карацуба);

• намиране на долни граници за броя на решенията на неравенства от вида

  $\alpha <{\biggl \{}{\frac {an^{*}+bn}{m}}{\biggr \}}\leq \beta$

в цели числа $n$, $1\leq n\leq x$, взаимно прости с $m$, $x<{\sqrt {m}}$ (Карацуба);

• изследване на точността на приближението на произволно реално число от интирвала $[0,1]$ с дробни части от вида

  ${\biggl \{}{\frac {an^{*}+bn}{m}}{\biggr \}},$

където $1\leq n\leq x$, $(n,m)=1$, $x<{\sqrt {m}}$ (Карацуба);

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

Дзета-функция на Риман

Хипотеза на А. Селберг

През 1984 година Карацуба установява, че при фиксирано $\varepsilon$, изпълняващо условието $0<\varepsilon <0.001$, достатъчно голямо $T$ и $H=T^{a+\varepsilon }$, $a={\tfrac {27}{82}}={\tfrac {1}{3}}-{\tfrac {1}{246}}$, интервалът $(T,T+H)$ съдържа не по-малко от $cH\ln T$ реални нули на дзета-функцията на Риман $\zeta {\Bigl (}{\tfrac {1}{2}}+it{\Bigr )}$.

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

Разпределение на нулите на дзета-функцията на Риман в кратки отрязъци от критическата права

На Карацуба принадлежат редица резултати за разпределението на нулите на $\zeta (s)$ в „кратки“ отрязъци от критическата права. Той е доказал, че аналог на хипотезата на Селберг е валидна за „почти всички“ отрязъци $(T,T+H]$, $H=T^{\varepsilon }$, където $\varepsilon$ е производно малко фиксирано положително число. Карацуба разработва (1992) нов подход за изследване на нулите на дзета-функцията на Риман върху „свръхкратки“ интервали на критическата права, т.е. интервали от типа $(T,T+H]$, където дължината $H$ расте по-бавно от произволно малка степен на $T$. В частност, той е доказал, че за всеки две зададени числа $\varepsilon$, $\varepsilon _{1}$ с условието $0<\varepsilon ,\varepsilon _{1}<1$ почти всички интервали $(T,T+H]$ при $H\geq \exp {\{(\ln T)^{\varepsilon }\}}$ съдържат не по-малко от $H(\ln T)^{1-\varepsilon _{1}}$ нули на функцията $\zeta {\bigl (}{\tfrac {1}{2}}+it{\bigr )}$. Тази оценка е твърде близко до това, което би следвало от Хипотезата на Риман.

Нули на линейни комбинации от L-редове на Дирихле

Карацуба създава нов метод за изследване на нулите на функции, представими като линейни комбинации от [[$L$ -функции на Дирихле]]. Като прост пример на функция от такъв род служи функцията на Дейвънпорт-Хейлброн, която се определя чрез равенството

$f(s)={\tfrac {1}{2}}(1-i\kappa )L(s,\chi )+{\tfrac {1}{2}}(1\,+\,i\kappa )L(s,{\bar {\chi }}),$

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

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

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

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

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

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

Граница на нулите на дзета-функцията и многомерния проблем за делителите на Дирихле

Лекция в Математическия институт на името на В.А. Стеклов

На Карацуба принадлежи принципно нов резултат в многомерния проблем за делителите на Дирихле, който е свързан с намирането при $x\to +\infty$ на броя $D_{k}(x)$ на решенията на неравенството $x_{1}*\ldots *x_{k}\leq x$ в естествени числа $x_{1},\ldots ,x_{k}$. За $D_{k}(x)$ има асимптотична формула от вида

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

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

$|R_{k}(x)|\leq x^{1-\alpha (k)}(c\ln x)^{k}$,

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

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

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

$Re\ s\geq 1-{\frac {c}{(\ln |t|)^{2/3}(\ln \ln |t|)^{1/3}}},\quad |t|>10$.

Карацуба установява (2000) обратна връзка между оценката на величината $R_{k}(x)$ с поведението на $\zeta (s)$ в близост до правата $Re\ s=1$. В частност, той доказал, че ако $\alpha (y)$ е произволна ненарастваща функция, удовлетворяваща условието $1/y\leq \alpha (y)\leq 1/2$, такава, че при всички $k\geq 2$ е изпълнена оценката

$|R_{k}(x)|\leq x^{1-\alpha (k)}(c\ln x)^{k}$,

то $\zeta (s)$ няма нули в областта

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

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

Оценки отдолу за максимума на модула на дзета-функцията в малки области от критичната ивица и в къси интервали от критичната права

От Карацуба са въведени и изследвани функциите $F(T;H)$ и $G(s_{0};\Delta )$, определени с равенствата

$F(T;H)=\max _{|t-T|\leq H}{\bigl |}\zeta {\bigl (}{\tfrac {1}{2}}+it{\bigr )}{\bigr |},\quad G(s_{0};\Delta )=\max _{|s-s_{0}|\leq \Delta }|\zeta (s)|.$

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

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

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

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

Поведение на аргумента на дзета-функцията върху критичната права

Карацуба получава редица нови резултати , касаещи поведението на функцията $S(t)={\frac {1}{\pi }}\arg {\zeta {\bigl (}{\tfrac {1}{2}}+it{\bigr )}}$, наричана аргумент на дзета-функцията на Риман върху критичната права (тук $\arg {\zeta {\bigl (}{\tfrac {1}{2}}+it{\bigr )}}$ означава нарастването на произволен непрекъснат клон на $\arg \zeta (s)$ по начупена линия, съединяваща точките $2,2+it$ и ${\tfrac {1}{2}}+it$. В това число – теоремата за средната стойност на функцията $S(t)$ и нейната примитивна $S_{1}(t)=\int _{0}^{t}S(u)du$ върху интервали от реалната права, а също така теорема за това, че всеки интервал $(T,T+H]$ при $H\geq T^{27/82+\varepsilon }$ съдържа не по-малко от

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

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

Характери на Дирихле

Оценки на кратки суми от характери в крайни полета

В края на 60-те години Карацуба, занимавайки се с оценки на кратки суми от характери, създава нов метод, който позволява да се получат нетривиални оценки на кратки суми от характери в крайни полета. Нека $n\geq 2$ е фиксирано цяло число, $F(x)=x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}$ – неразложим над полето $\mathbb {Q}$ на рационалните числа полином, $\theta$ – корен на уравнението $F(\theta )=0$, $\mathbb {Q} (\theta )$ – разширение на полето $\mathbb {Q}$, $\omega _{1},\ldots ,\omega _{n}$ – базис за $\mathbb {Q} (\theta )$, $\omega _{1}=1$, $\omega _{2}=\theta$, $\omega _{3}=\theta ^{2},\ldots ,\omega _{n}=\theta ^{n-1}$. Нека по-нататък $p$ е достатъчно голямо просто число, такова че $F(x)$ е неразложим по модул $p$, $\mathrm {GF} (p^{n})$ – полето на Галоа с базис $\omega _{1},\omega _{2},\ldots ,\omega _{n}$, $\chi$ – неглавен характер на Дирихле за полето $\mathrm {GF} (p^{n})$. Нека накрая $\nu _{1},\ldots ,\nu _{n}$ са някои неотрицателни цели числа, $D(X)$ е множеството от елементи ${\bar {x}}$ на полето на Галоа $\mathrm {GF} (p^{n})$,

${\bar {x}}=x_{1}\omega _{1}+\ldots +x_{n}\omega _{n}$,

такива че за всяко $i$, $1\leq i\leq n$, са изпълнени неравенставта:

$\nu _{i}<x_{i}<\nu _{i}+X$.

Карацуба доказва, че при произволно фиксирано $k$, $k\geq n+1$, и произволно $X$ с условието

$p^{{\frac {1}{4}}+{\frac {1}{4k}}}\leq X\leq p^{{\frac {1}{2}}+{\frac {1}{4k}}}$

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

${\biggl |}\sum \limits _{{\bar {x}}\in D(X)}\chi ({\bar {x}}){\biggr |}\leq c{\Bigl (}X^{1-{\frac {1}{k}}}p^{{\frac {1}{4k}}+{\frac {1}{4k^{2}}}}{\Bigr )}^{\!\!n}(\ln p)^{\gamma },$

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

Оценки на линейни суми от характери по изместени прости числа

Карацуба разработва ред нови прийоми, приложението на които наред с метода на Виноградов за оценка на суми с прости числа, му позволяват през 1970 г. да получи оценка за сумата на стойностите на неглавния характер по прост модул $q$ върху редици от изместени прости числа, а именно оценка от вида

${\biggl |}\sum \limits _{p\leq N}\chi (p+k){\biggr |}\leq cNq^{-{\frac {\varepsilon ^{2}}{1024}}},$

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

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

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

„

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

“

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

Оценки за суми от характери от полином с прости аргументи

На Карацуба принадлежат редица оценки за суми на характери на Дирихле от полиноми от втора степен за случая, когато аргументът им пробягва някаква кратка редица от поредни прости числа. Нека например $q$ е достатъчно голямо просто число, $f(x)=(x-a)(x-b)$, където $a$ и $b$ са цели числа, удовлетворяващи условието $ab(a-b)\not \equiv 0{\pmod {q}}$, и нека $\left({\frac {n}{q}}\right)$ означава символа на Льожандър. Тогава при всяко фиксирано $\varepsilon$ с условието $0<\varepsilon <{\tfrac {1}{2}}$ и $N>q^{3/4+\varepsilon }$ за сумите $S_{N}$,

$S_{N}=\sum \limits _{p\leq N}{\biggl (}{\frac {f(p)}{q}}{\biggr )},$

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

$|S_{N}|\leq c\pi (N)q^{-{\frac {\varepsilon ^{2}}{100}}}$

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

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

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

Оценки отдолу за суми от характери от полиноми

Карацуба е построил безкрайна редица от прости числа $p$ и редица от многочлени $f(x)$ от степен $n$ с цели коефициенти, такива че $f(x)$ не е точен квадрат по модул $p$,

${\frac {4(p-1)}{\ln p}}\leq n\leq {\frac {8(p-1)}{\ln p}},$

и такива, че

$\sum \limits _{x=1}^{p}\left({\frac {f(x)}{p}}\right)=p.$

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

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

${\biggl |}\sum \limits _{x=1}^{p}\left({\frac {f(x)}{p}}\right){\biggr |}\leq (n-1){\sqrt {p}}$

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

Суми на характери на адитивни редици

Карацуба е открил нов метод , позволяващ да се намира твърде точни оценки за сумите от стойностите на неглавните характери на Дирихле върху адитивни редици, т.е. редици, състоящи се от числа от вида $x+y$, където променливите $x$ и $y$ независимо едно от друго пробягват, съответно някакви множества $A$ и $B$.

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

${\biggl |}\sum \limits _{x\in A}\sum \limits _{y\in B}\chi (x+y){\biggr |}\leq c\|A\|\cdot \|B\|q^{-{\frac {\varepsilon ^{2}}{20}}},\quad c=c(\varepsilon )>0.$

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

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

${\biggl |}\sum \limits _{p\leq X}\sum \limits _{p'\leq Y}\chi (p+p'){\biggr |}\leq c\pi (X)\pi (Y)q^{-c_{1}\varepsilon ^{2}},$

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

Разпределение на степенни остатъци и първообразни корени в редки редици

От Карацуба са получени (2000) нетривиални оценкки за суми от стойности на характери на Дирихле „с тегла“, т.е. суми от събираеми от вида $\chi (n)f(n)$, където $f(n)$ – функция на естествен аргумент. Оценки от такъв вид намират приложение при решенията на широк кръг задачи в теорията на числата, свързани с разпределението на степенни остатъци (неостатъци), а също така първообразни корени в едни или други редици.

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

$D_{k}(x)=\sum \limits _{x_{1}*\ldots *x_{k}\leq x}1=\sum \limits _{n\leq x}\tau _{k}(n)$

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

$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 )}$.

Аналогично за сумата $V(x)$ от величините $\tau _{k}(n)$, взета по всички $n\leq x$, за които $(n+a)$ е първообразен корен по модул $q$, се получава асимптотично изразяване от вида

$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 )}$,

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

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

Работа в късните му години

На памирско възвишение

В късните си години, освен с изследвания в теорията на числата, Карацуба изучава някои проблеми от теоретичната физика, по-конкретно в сферата на квантовата теория на полето. Прилагайки една от неговите теореми и други подходи от теорията на числата, той извежда нови резултати в модела на Джейнс-Къмингс в квантовите оптики.

Личен живот

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

В Крим

През целия си живот Карацуба практикува множество спортове: в младите си години, атлетика, по-късно спелеология и планински туризъм. 11 пъти е изкачвал върхове над 7000 м:

• Връх Исмаил Самани (най-високият в СССР) през 1977 и 1985;
• Връх Ленин през 1968 и 1979;
• Връх Корженевская през 1980, 1982, 1983, 1985, 1986, 1988 и 1991.

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

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

Вижте също

• АТС теорема
• Диаграма на Мур
• Умножение на Карацуба

Външни препратки

• ((ru)) Списък с научни трудове на сайта на МИАН
• ((ru)) Данни за научните интереси, образованието и професионалната кариера на сайта на МИАН