Карацуба, Анатолий Алексеевич

В статье Эдварда Мура «Умозрительные эксперименты на последовательных машинах»[3] ${\displaystyle (n;m;p)}$ автомат (или машина) ${\displaystyle S}$ определяется как имеющее ${\displaystyle n}$ состояний, ${\displaystyle m}$ входных символов и ${\displaystyle p}$ выходных символов устройство. Доказывается девять теорем о структуре ${\displaystyle S}$ и экспериментах с ${\displaystyle S}$. Позднее такие ${\displaystyle S}$ машины стали называть автоматами Мура. В конце статьи, в главе «Новые проблемы» Мур формулирует задачу об улучшении оценок полученных им в теоремах 8 и 9:

Теорема 8 (Мур). Пусть задана произвольная ${\displaystyle (n;m;p)}$ машина ${\displaystyle S}$, такая что каждые два её состояния различимы одно от другого, тогда существует эксперимент длины ${\displaystyle n(n-1)/2}$ который устанавливает (находит) состояние ${\displaystyle S}$ в конце этого эксперимента.

В 1957 году Карацуба доказал две теоремы, которые полностью решили проблему Мура по улучшению оценки длины эксперимента в его Теореме 8.

Теорема A (Карацуба). Если ${\displaystyle S}$ есть ${\displaystyle (n;m;p)}$ машина, каждые два состояния которой различимы между собой, то существует разветвлённый эксперимент длины не более чем ${\displaystyle (n-1)(n-2)/2+1}$, посредством которого можно установить (найти) состояние ${\displaystyle S}$ в конце эксперимента.

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

Эти две теоремы явились основой курсовой работы Карацубы 4-го курса «Об одной проблеме из теории автоматов» которая была отмечена похвальным отзывом (то есть не очень высоко) на конкурсе студенческих работ механико-математического факультета МГУ им. Ломоносова в 1958 году. Статья была подана Карацубой в журнал Успехи математических наук в декабре 1958 года, а опубликована лишь в июне 1960 года[4]. Однако до настоящего времени этот результат Карацубы, который впоследствии стал называться теоремой Мура – Карацубы, является единственным точным (единственно точный нелинейный порядок оценки) нелинейным результатом как в теории автоматов, так и в аналогичных задачах теории сложности вычислений.[1]

Быстрые алгоритмы — область вычислительной математики, которая изучает алгоритмы вычисления заданной функции с заданной точностью с использованием как можно меньшего числа битовых операций. Будем считать, что числа записаны в двоичной системе счисления, знаки которой 0 и 1 называются битами. Одна битовая операция определяется как запись знаков 0, 1, плюс, минус, скобка; сложение, вычитание и умножение двух битов. Первые постановки задач о битовой сложности вычисления принадлежат А. Н. Колмогорову. Сложность умножения ${\displaystyle M(n)}$ определяется как количество битовых операций, достаточное для вычисления произведения двух ${\displaystyle n}$-значных чисел посредством данного алгоритма.

Перемножая два n-значных числа обычным школьным способом «в столбик», мы имеем оценку сверху ${\displaystyle M(n)=O(n^{2})}$. В 1956 году А. Н. Колмогоров высказал гипотезу, что нижняя оценка ${\displaystyle M(n)}$ при любом методе умножения есть также величина порядка ${\displaystyle n^{2}}$, то есть нельзя вычислить произведение двух n-значных чисел быстрее, чем за ${\displaystyle n^{2}}$ операций (так называемая «гипотеза ${\displaystyle n^{2}}$»). На правдоподобность гипотезы ${\displaystyle n^{2}}$ указывал тот факт, что за всё время существования математики к тому моменту люди производили умножение со сложностью порядка ${\displaystyle O(n^{2})}$, и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден.

В 1960 году на механико-математическом факультете МГУ начал работать семинар по математическим вопросам кибернетики под руководством А. Н. Колмогорова, где была сформулирована «гипотеза ${\displaystyle n^{2}}$» и поставлен ряд задач об оценке сложности других подобных вычислений. Анатолий Карацуба, надеясь получить нижнюю оценку величины ${\displaystyle M(n)}$, нашёл новый метод умножения двух n-значных чисел, известный теперь как умножение Карацубы, с оценкой сложности

${\displaystyle M(n)=O(n^{\log _{2}3})=O(n^{1,58496\ldots }),}$

и тем самым опровергнув гипотезу ${\displaystyle n^{2}}$, о чём сообщил Колмогорову после очередного заседания семинара. На следующем заседании семинара этот метод был рассказан самим Колмогоровым, и семинар прекратил свою работу.[5] Первая статья с описанием умножения Карацубы была подготовлена самим Колмогоровым, где он представил два разных и несвязанных друг с другом результата двух своих учеников.[6] Хотя в статье Колмогоров чётко отметил, что одна теорема (не связанная с быстрым умножением) принадлежит Ю. Офману, а другая теорема (с первым в истории быстрым умножением) — А. Карацубе, эта публикация двух авторов надолго сбила с толку читателей, которые полагали, что оба автора внесли вклад в создание метода быстрого умножения, и даже называли этот метод двумя именами. Метод Карацубы впоследствии был обобщён до парадигмы «разделяй и властвуй», другими важными примерами которой являются метод двоичного разбиения, двоичный поиск, метод бисекции и др.

Впоследствии на основе этой идеи А. Карацубы[5][7][8] было построено множество быстрых алгоритмов, самыми известными из которых являются его непосредственные обобщения, такие как метод умножения Шёнхаге-Штрассена[9], метод матричного умножения Штрассена[10] и быстрое преобразование Фурье.

Французский математик и философ Жан-Поль Делайе назвал[11] метод умножения Карацубы «одним из самых полезных результатов математики».

Алгоритм Анатолия Карацубы внедрён практически во все современные компьютеры не только на программном, но и на аппаратном уровне.

А. А. Карацуба построил новый ${\displaystyle p}$-адический метод в теории тригонометрических сумм. Полученные [17] им оценки так называемых ${\displaystyle L}$-сумм вида

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

привели к новым границам нулей ${\displaystyle L}$-рядов Дирихле по модулю, равному степени простого числа, к выводу асимптотической формулы для числа варинговского сравнения вида

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

решению проблемы распределения дробных долей многочлена с целыми коэффициентами по модулю ${\displaystyle p^{k}}$. А. А. Карацуба первый реализует [18] в ${\displaystyle p}$-адической форме «принцип вложения» Эйлера-Виноградова и строит ${\displaystyle p}$-адический аналог ${\displaystyle u}$- чисел Виноградова при оценке числа решений сравнения варинговского типа.

Пусть

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

причём

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

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

Этот новый подход, найденный А. А. Карацубой, привёл к новому ${\displaystyle p}$-адическому доказательству теоремы о среднем И. М. Виноградова, играющей центральную роль в методе тригонометрических сумм Виноградова.

Ещё одним элементом ${\displaystyle p}$-адического метода А. А. Карацубы является переход от неполных систем уравнений к полным за счёт локального ${\displaystyle p}$-адического изменения неизвестных. [19] [20]

Пусть ${\displaystyle r}$ — произвольное натуральное число, ${\displaystyle 1\leq r\leq n}$, и целое число ${\displaystyle t}$ определяется неравенствами ${\displaystyle m_{t}\leq r\leq m_{t+1}}$. Рассмотрим систему уравнений

${\displaystyle {\begin{cases}x_{1}^{m_{1}}+\dots +x_{k}^{m_{1}}=y_{1}^{m_{1}}+\dots +y_{k}^{m_{1}},\\\qquad \qquad \qquad \qquad \vdots \\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}}}$

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

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

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

Для неполных систем уравнений, в которых переменные пробегают числа с малыми простыми делителями, А. А. Карацуба применил мультипликативный сдвиг переменных. Это привело к качественно новой оценке тригонометрических сумм и новой теореме о среднем для таких систем уравнений.

${\displaystyle p}$-адический метод А. А. Карацубы включает в себя способы оценок меры множества точек с малыми значениями функций через значения их параметров (коэффициенты и т. п.) и, обратно, оценок этих параметров через меру множества в вещественной и ${\displaystyle p}$-адической метриках. Особенно ярко эта сторона метода А. А. Карацубы проявилась при оценках тригонометрических интегралов, что привело к решению проблемы Хуа Ло-кена. В 1979 году А. А. Карацуба вместе со своими учениками Г. И. Архиповым и В. Н. Чубариковым полностью решили[21] проблему Хуа Ло-кена, поставленную в 1937 году, которая заключалась в определении показателя сходимости интеграла:

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

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

В данном случае показателем сходимости называется такое значение ${\displaystyle \gamma }$, что ${\displaystyle \vartheta _{0}}$ сходится при ${\displaystyle 2k>\gamma +\varepsilon }$ и расходится при ${\displaystyle 2k<\gamma -\varepsilon }$, где ${\displaystyle \varepsilon >0}$ сколь угодно мало. Было установлено, что интеграл ${\displaystyle \vartheta _{0}}$ сходится при ${\displaystyle 2k>{\tfrac {1}{2}}(n^{2}+n)+1}$ и расходится при ${\displaystyle 2k\leq {\tfrac {1}{2}}(n^{2}+n)+1}$.

Тогда же была решена и аналогичная проблема для интеграла

${\displaystyle \vartheta _{1}=\int _{-\infty }^{+\infty }\cdots \int _{-\infty }^{+\infty }{\biggl |}\int _{0}^{1}e^{2\pi i(\alpha _{n}x^{n}+\alpha _{m}x^{m}+\cdots +\alpha _{r}x^{r})}dx{\biggr |}^{2k}d\alpha _{n}d\alpha _{m}\ldots d\alpha _{r},}$

где ${\displaystyle n,m,\ldots ,r}$ — целые числа, удовлетворяющие условиям

${\displaystyle 1\leq r<\ldots <m<n,\quad r+\ldots +m+n<{\tfrac {1}{2}}(n^{2}+n).}$

А. А. Карацубой и его учениками было установлено, что интеграл ${\displaystyle \vartheta _{1}}$ сходится, если ${\displaystyle 2k>n+m+\ldots +r}$ и расходится, если ${\displaystyle 2k\leq n+m+\ldots +r}$.

Интегралы ${\displaystyle \vartheta _{0}}$ и ${\displaystyle \vartheta _{1}}$ возникают при решении так называемой проблемы Терри (проблемы Терри-Эскотта). А. А. Карацубой и его учениками был получен ряд новых результатов, связанных с многомерным аналогом проблемы Терри. В частности, ими было установлено, что если ${\displaystyle F}$ — полином от ${\displaystyle r}$ переменных (${\displaystyle r\geq 2}$) вида

${\displaystyle F(x_{1},\ldots ,x_{r})\,=\,\sum \limits _{\nu _{1}=0}^{n_{1}}\cdots \sum \limits _{\nu _{r}=0}^{n_{r}}\alpha (\nu _{1},\ldots ,\nu _{r})x_{1}^{\nu _{1}}\ldots x_{r}^{\nu _{r}},}$

с нулевым свободным коэффициентом, ${\displaystyle m=(n_{1}+1)\ldots (n_{r}+1)-1}$, ${\displaystyle {\bar {\alpha }}}$ — ${\displaystyle m}$-мерный вектор, составленный из коэффициентов ${\displaystyle F}$, то интеграл

${\displaystyle \vartheta _{2}=\int \limits _{-\infty }^{+\infty }\cdots \int \limits _{-\infty }^{+\infty }{\biggl |}\int \limits _{0}^{1}\cdots \int \limits _{0}^{1}e^{2\pi iF(x_{1},\ldots ,x_{r})}dx_{1}\ldots dx_{r}{\biggr |}^{2k}d{\bar {\alpha }}}$

сходится при ${\displaystyle 2k>mn}$ , где ${\displaystyle n}$ — наибольшее из чисел ${\displaystyle n_{1},\ldots ,n_{r}}$. Этот результат, не являясь окончательным, породил новое направление в теории тригонометрических интегралов, связанное с уточнением границ для показателя сходимости ${\displaystyle \vartheta _{2}}$ (И. А. Икромов, М. А. Чахкиев и другие).

В 1966—1980 годах А. А. Карацуба создал[22][23][14] (при участии своих учеников Г. И. Архипова и В. Н. Чубарикова) теорию кратных тригонометрических сумм Г. Вейля, то есть сумм вида

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

где ${\displaystyle 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}}}$ ,

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

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

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

и

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

Тогда при любом ${\displaystyle \tau \geq 0}$ и ${\displaystyle K\geq K_{\tau }=m\tau }$ для величины ${\displaystyle J}$ имеет место оценка

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

где ${\displaystyle \varkappa =n_{1}\nu _{1}+\dots +n_{r}\nu _{r}}$ , ${\displaystyle \gamma \varkappa =1}$, ${\displaystyle \Delta (\tau )={\frac {m}{2}}(1-(1-\gamma )^{\tau })}$ , ${\displaystyle P=(P_{1}^{n_{1}}\dots P_{r}^{n_{r}})^{\gamma }}$, и натуральные числа ${\displaystyle \nu _{1},\dots ,\nu _{r}}$ таковы, что:

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

Теорема о среднем и лемма о кратности пересечения многомерных параллелепипедов лежат в основе оценки кратной тригонометрической суммы, полученной А. А. Карацубой (двумерный случай был получен Г. И. Архиповым[24]). Если обозначить через ${\displaystyle Q_{0}}$ наименьшее общее кратное чисел ${\displaystyle q(t_{1},\dots ,t_{r})}$ с условием ${\displaystyle t_{1}+\dots t_{r}\geq 1}$, то при ${\displaystyle Q_{0}\geq P^{1/6}}$ справедлива оценка

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

где ${\displaystyle \tau (Q)}$ — количество делителей числа ${\displaystyle Q}$, а ${\displaystyle \nu (Q)}$ — количество различных простых делителей числа ${\displaystyle Q}$.

Применяя сконструированную им ${\displaystyle p}$-адическую форму кругового метода Харди-Литтлвуда-Рамануджана-Виноградова к оценкам тригонометрических сумм, в которых суммирование ведётся по числам с малыми простыми делителями, А. А. Карацуба получил[25] новую оценку известной функции Харди ${\displaystyle G(n)}$ в проблеме Варинга (при ${\displaystyle n\geq 400}$):

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

В своих дальнейших исследованиях по проблеме Варинга А. А. Карацуба получил [26][27] следующее двумерное обобщение этой проблемы:

Рассмотрим систему уравнений

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

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

В исследованиях по проблеме Артина о ${\displaystyle p}$-адическом представлении нуля формой произвольной степени результаты А. А. Карацубы показали, что вместо ранее предполагавшегося степенного роста числа переменных для нетривиального представления нуля формой, это число переменных должно расти почти экспоненциально в зависимости от степени. А. А. Карацуба вместе со своим учеником Г. И. Архиповым доказали[28], что для любого натурального числа ${\displaystyle r}$ существует такое ${\displaystyle n_{0}=n_{0}(r)}$, что для любого ${\displaystyle n\geq n_{0}}$ существует форма ${\displaystyle F(x_{1},\dots ,x_{k})}$ степени, меньшей ${\displaystyle n}$, с целыми коэффициентами, число переменных которой ${\displaystyle k}$, ${\displaystyle k\geq 2^{u}}$ ,

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

и имеющая только тривиальное представление нуля в 2-адических числах, а также получили аналогичный результат для произвольного нечётного простого модуля ${\displaystyle p}$.

А. А. Карацуба создал[29][30][31](1993—1999) новый метод оценок коротких сумм Клоостермана, то есть тригонометрических сумм вида

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

где ${\displaystyle n}$ пробегает некоторое множество ${\displaystyle A}$ чисел, взаимно простых с ${\displaystyle m}$, число ${\displaystyle \|A\|}$ элементов в котором существенно меньше ${\displaystyle m}$, а символ ${\displaystyle n^{*}}$ обозначает вычет, обратный к ${\displaystyle n}$ по модулю ${\displaystyle m}$: ${\displaystyle nn^{*}\equiv 1(\mod m)}$.

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

Различные аспекты метода А. А. Карацубы нашли применение в решении следующих задач аналитической теории чисел:

• нахождение асимптотик сумм дробных долей вида

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

где ${\displaystyle n}$ пробегает подряд идущие целые числа с условием ${\displaystyle (n,m)=1}$, а ${\displaystyle p}$ пробегает простые числа, не делящие модуль ${\displaystyle m}$ (А. А. Карацуба);

• нахождение нижней границы для числа решений неравенств вида

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

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

• точность приближения произвольного вещественного числа из отрезка ${\displaystyle [0,1]}$ дробными долями вида

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

где ${\displaystyle 1\leq n\leq x}$, ${\displaystyle (n,m)=1}$, ${\displaystyle x<{\sqrt {m}}}$ (А. А. Карацуба);

• уточнение постоянной ${\displaystyle c}$ в неравенстве Бруна-Титчмарша

  ${\displaystyle \pi (x;q,l)<{\frac {cx}{\varphi (q)\ln {\frac {2x}{q}}}},}$

где ${\displaystyle \pi (x;q,l)}$ — число простых чисел ${\displaystyle p}$, не превосходящих ${\displaystyle x}$ и принадлежащих арифметической прогрессии ${\displaystyle p\equiv l{\pmod {q}}}$ (Дж. Фридлендер, Г. Иванец);

• нижняя оценка наибольшего простого делителя произведения чисел вида:

  ${\displaystyle n^{3}+2}$, ${\displaystyle N<n\leq 2N}$ (Д. Р. Хиз-Браун);

• доказательство бесконечности простых чисел вида ${\displaystyle a^{2}+b^{4}}$ (Дж. Фридлендер, Г. Иванец);

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

В 1984 году А. А. Карацуба установил,[33][34][35] что при фиксированном ${\displaystyle \varepsilon }$ с условием ${\displaystyle 0<\varepsilon <0.001}$, достаточно большом ${\displaystyle T}$ и ${\displaystyle H=T^{a+\varepsilon }}$, ${\displaystyle a={\tfrac {27}{82}}={\tfrac {1}{3}}-{\tfrac {1}{246}}}$, промежуток ${\displaystyle (T,T+H)}$ содержит не менее ${\displaystyle cH\ln T}$ вещественных нулей дзета-функции Римана ${\displaystyle \zeta {\Bigl (}{\tfrac {1}{2}}+it{\Bigr )}}$.

Это утверждение в 1942 году было высказано в качестве гипотезы А. Сельбергом[36], который сам доказал его справедливость для случая ${\displaystyle H\geq T^{1/2+\varepsilon }}$. Оценки А. Сельберга и А. А. Карацубы являются неулучшаемыми по порядку роста при ${\displaystyle T\to +\infty }$.

А. А. Карацубе принадлежит[37] также ряд результатов о распределении нулей ${\displaystyle \zeta (s)}$ на «коротких» промежутках критической прямой. Он доказал, что аналог гипотезы Сельберга справедлив для «почти всех» промежутков ${\displaystyle (T,T+H]}$, ${\displaystyle H=T^{\varepsilon }}$, где ${\displaystyle \varepsilon }$ — сколь угодно малое фиксированное положительное число. А. А. Карацуба разработал (1992) новый подход к исследованию нулей дзета-функции Римана на «сверхкоротких» промежутках критической прямой, то есть на промежутках ${\displaystyle (T,T+H]}$, длина ${\displaystyle H}$ которых растёт медленнее любой, даже сколь угодно малой, степени ${\displaystyle T}$. В частности, он доказал, что для любых заданных чисел ${\displaystyle \varepsilon }$, ${\displaystyle \varepsilon _{1}}$ с условием ${\displaystyle 0<\varepsilon ,\varepsilon _{1}<1}$ почти все промежутки ${\displaystyle (T,T+H]}$ при ${\displaystyle H\geq \exp {\{(\ln T)^{\varepsilon }\}}}$ содержат не менее ${\displaystyle H(\ln T)^{1-\varepsilon _{1}}}$ нулей функции ${\displaystyle \zeta {\bigl (}{\tfrac {1}{2}}+it{\bigr )}}$. Эта оценка весьма близка к той, что следует из гипотезы Римана.

А. А. Карацубой создан новый метод[38][39][40] исследования нулей функций, представимых в виде линейных комбинаций ${\displaystyle L}$ -рядов Дирихле. Простейшим примером функции такого рода служит функция Дэвенпорта-Хейльбронна, определяемая равенством

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

где ${\displaystyle \chi }$ — неглавный характер по модулю ${\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)}$ для любого ${\displaystyle n}$),

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

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

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

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

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

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

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

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

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

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

где ${\displaystyle \alpha ={\frac {1}{ak+b}}}$, ${\displaystyle a,b,c}$ — абсолютные положительные постоянные.

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

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

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

А. А. Карацуба установил[42] [43] (2000) обратную связь оценок величин ${\displaystyle R_{k}(x)}$ с поведением ${\displaystyle \zeta (s)}$ вблизи прямой ${\displaystyle Re\ s=1}$. В частности, он доказал, что если ${\displaystyle \alpha (y)}$ — произвольная невозрастающая функция с условием ${\displaystyle 1/y\leq \alpha (y)\leq 1/2}$, такая, что при всех ${\displaystyle k\geq 2}$ выполняется оценка

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

то ${\displaystyle \zeta (s)}$ не имеет нулей в области

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

(${\displaystyle c,c_{1}}$ — абсолютные постоянные).

А. А. Карацубой введены и исследованы [44] [45] функции ${\displaystyle F(T;H)}$ и ${\displaystyle G(s_{0};\Delta )}$, определяемые равенствами

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

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

А. А. Карацуба доказал, в частности, что если величины ${\displaystyle H}$ и ${\displaystyle \Delta }$ превосходят некоторые достаточно малые константы, то справедливы оценки

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

где ${\displaystyle c_{1},c_{2}}$ — некоторые абсолютные постоянные.

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

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

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

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

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

таких, что при любом ${\displaystyle i}$, ${\displaystyle 1\leq i\leq n}$, выполняются неравенства:

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

А. А. Карацуба доказал, что при любом фиксированном ${\displaystyle k}$, ${\displaystyle k\geq n+1}$, и произвольном ${\displaystyle X}$ с условием

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

справедлива оценка:

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

где ${\displaystyle \gamma ={\frac {1}{k}}(2^{n+1}-1)}$, а постоянная ${\displaystyle c}$ зависит лишь от ${\displaystyle n}$ и базиса ${\displaystyle \omega _{1},\ldots ,\omega _{n}}$.

А. А. Карацуба разработал ряд новых приёмов, применение которых наряду с методом И. М. Виноградова оценок сумм с простыми числами позволило ему в 1970 году получить[49][50] оценку суммы значений неглавного характера по простому модулю ${\displaystyle q}$ на последовательности сдвинутых простых чисел, а именно оценку вида

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

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

Это утверждение представляет собой значительное усиление оценки И. М. Виноградова, нетривиальной при ${\displaystyle N\geq q^{3/4+\varepsilon }}$.

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

Этот результат был перенесен А. А. Карацубой и на случай, когда ${\displaystyle p}$ пробегает простые числа арифметической прогрессии, разность которой растет вместе с модулем ${\displaystyle q}$.

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

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

справедлива оценка:

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

(здесь ${\displaystyle p}$ пробегает подряд идущие простые числа, ${\displaystyle \pi (N)}$ — количество простых чисел, не превосходящих ${\displaystyle N}$, а ${\displaystyle c}$ — постоянная, зависящая лишь от ${\displaystyle \varepsilon }$).

Подобная оценка была получена А. А. Карацубой и для случая, когда ${\displaystyle p}$ пробегает последовательность простых чисел, принадлежащих арифметической прогрессии, разность которой может расти вместе с модулем ${\displaystyle q}$.

А. А. Карацубой высказана гипотеза, согласно которой нетривиальная оценка суммы ${\displaystyle S_{N}}$ при ${\displaystyle N}$, «маленьких» по сравнению с ${\displaystyle q}$, остаётся справедливой и в случае, если заменить ${\displaystyle f(x)}$ произвольным многочленом ${\displaystyle n}$-й степени, который не является квадратом по модулю ${\displaystyle q}$. Эта гипотеза в настоящее время не доказана.

А. А. Карацуба построил[52] бесконечную последовательность простых чисел ${\displaystyle p}$ и последовательность многочленов ${\displaystyle f(x)}$ степени ${\displaystyle n}$ с целыми коэффициентами, таких, что ${\displaystyle f(x)}$ не является полным квадратом по модулю ${\displaystyle p}$,

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

и таких, что

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

Иными словами, при любом ${\displaystyle x}$ значение ${\displaystyle f(x)}$ оказывается квадратичным вычетом по модулю ${\displaystyle p}$. Этот результат показывает, что оценку А. Вейля

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