Анато́лий Алексе́евич Карацу́ба (31 января 1937, Грозный — 28 сентября 2008, Москва) — советский и российский .

Наиболее известен как создатель так называемого умножения Карацубы — быстрого алгоритма умножения больших чисел.

Учёба и работа

Анатолий Карацуба учился в 1944—1954 годах в средней мужской школе № 6 города Грозного и окончил её с серебряной медалью. Уже в ранние годы проявлял исключительные способности к математике, решая в младших классах задачи, которые давали в математическом кружке старшеклассникам.

В 1959 году окончил механико-математический факультет МГУ им. Ломоносова. В 1962 году он стал кандидатом физико-математических наук с диссертацией «Рациональные тригонометрические суммы специального вида и их приложения» (научный руководитель — Н. М. Коробов), и начал работать на факультете в МГУ. В 1966 году он защитил докторскую диссертацию «Метод тригонометрических сумм и теоремы о среднем» и стал научным сотрудником Математического института АН СССР (МИАН).

С 1983 года он являлся ведущим специалистом в области теории чисел в СССР и России, и заведующим отдела теории чисел (образован в 1983 году) в МИАНе, профессором кафедры теории чисел МГУ с 1970 года и профессором кафедры математического анализа МГУ (образована в 1962 году) с 1980 года. Его исследовательские интересы включали тригонометрические суммы и интегралы, дзета-функцию Римана, характеры Дирихле, конечный автомат, эффективные алгоритмы.

А. А. Карацуба был научным руководителем 15 аспирантов, получивших степень кандидата наук; семеро из них стали впоследствии докторами наук. Имел государственные премии и звания.

Премии и звания 1981: Премия имени П. Л. Чебышёва АН СССР 4 июня 1999: Заслуженный деятель науки Российской Федерации 2001: Премия имени И. М. Виноградова РАН

Ранние работы по информатике Будучи студентом МГУ им. Ломоносова, А. А. Карацуба принимал участие в работе семинара А. Н. Колмогорова и нашёл решения двух поставленных Колмогоровым проблем, что дало импульс развитию теории автоматов и положило начало новому направлению в математике — теории быстрых алгоритмов.

Автоматы В статье Эдварда Мура «Умозрительные эксперименты на последовательных машинах» автомат (или машина) определяется как имеющее состояний, входных символов и выходных символов устройство. Доказывается девять теорем о структуре и экспериментах с . Позднее такие машины стали называть автоматами Мура. В конце статьи, в главе «Новые проблемы» Мур формулирует задачу об улучшении оценок полученных им в теоремах 8 и 9:

Теорема 8 (Мур). Пусть задана произвольная машина , такая, что каждые два её состояния различимы одно от другого, тогда существует эксперимент длины который устанавливает (находит) состояние в конце этого эксперимента.В 1957 году Карацуба доказал две теоремы, которые полностью решили проблему Мура по улучшению оценки длины эксперимента в его Теореме 8.

Теорема A (Карацуба). Если есть машина, каждые два состояния которой различимы между собой, то существует разветвлённый эксперимент длины не более чем , посредством которого можно установить (найти) состояние в конце эксперимента.

Теорема B (Карацуба). Существует машина, каждые два состояния которой взаиморазличимы, такая, что длина наикратчайшего эксперимента, устанавливающего состояние машины в конце эксперимента, равна .

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

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

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

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

и тем самым опровергнув гипотезу , о чём сообщил Колмогорову после очередного заседания семинара. На следующем заседании семинара этот метод был рассказан самим Колмогоровым, и семинар прекратил свою работу. Первая статья с описанием умножения Карацубы была подготовлена самим Колмогоровым, где он представил два разных и несвязанных друг с другом результата двух своих учеников. Хотя в статье Колмогоров чётко отметил, что одна теорема (не связанная с быстрым умножением) принадлежит Ю. Офману, а другая теорема (с первым в истории быстрым умножением) — А. Карацубе, эта публикация двух авторов надолго сбила с толку читателей, которые полагали, что оба автора внесли вклад в создание метода быстрого умножения, и даже называли этот метод двумя именами. Метод Карацубы впоследствии был обобщён до парадигмы «разделяй и властвуй», другими важными примерами которой являются , двоичный поиск, метод бисекции и др.

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

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

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

Основные исследования В своей статье «О математических работах профессора Карацубы», посвящённой 60-летнему юбилею А. А. Карацубы, его ученики Г. И. Архипов и В. Н. Чубариков так описывают особенности научных работ А. А. Карацубы:

Основные исследования А. А. Карацубы опубликованы более чем в 160 научных статьях и монографиях.

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

p-адический метод А. А. Карацуба построил новый -адический метод в теории тригонометрических сумм. Полученные им оценки так называемых -сумм вида

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

решению проблемы распределения дробных долей многочлена с целыми коэффициентами по модулю . А. А. Карацуба первый реализует

в -адической форме «принцип вложения» Эйлера-Виноградова и строит -адический аналог - чисел Виноградова при оценке числа решений сравнения варинговского типа.

Пусть

причём

где  — простое число. А. А. Карацуба доказал, что в этом случае для всякого натурального числа существует такое, что для любого всякое натуральное число представимо в виде (1) при , а при существуют такие, что сравнение (1) неразрешимо.

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

Ещё одним элементом -адического метода А. А. Карацубы является переход от неполных систем уравнений к полным за счёт локального -адического изменения неизвестных.

Пусть  — произвольное натуральное число, , и целое число определяется неравенствами . Рассмотрим систему уравнений

А. А. Карацуба доказал, что для числа решений этой системы уравнений при справедлива оценка

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

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

где  — фиксированное число.

В данном случае показателем сходимости называется такое значение , что сходится при и расходится при , где сколь угодно мало. Было установлено, что интеграл сходится при и расходится при .

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

где  — целые числа, удовлетворяющие условиям

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

Интегралы и возникают при решении так называемой проблемы Терри (проблемы Терри-Эскотта). А. А. Карацубой и его учениками был получен ряд новых результатов, связанных с многомерным аналогом проблемы Терри. В частности, ими было установлено, что если  — полином от переменных () вида

с нулевым свободным коэффициентом, ,  — -мерный вектор, составленный из коэффициентов , то интеграл

сходится при , где  — наибольшее из чисел . Этот результат, не являясь окончательным, породил новое направление в теории тригонометрических интегралов, связанное с уточнением границ для показателя сходимости (И. А. Икромов, М. А. Чахкиев и другие).

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

, где ,

 — набор вещественных коэффициентов . Центральным моментом этой теории, как и теории тригонометрических сумм И. М. Виноградова, является следующая теорема о среднем.

Пусть  — натуральные числа, ,. Пусть далее  — -мерный куб в евклидовом пространстве вида , , и . Тогда при любом и для величины имеет место оценка , где , , , , и натуральные числа таковы, что: , .

Теорема о среднем и лемма о кратности пересечения многомерных параллелепипедов лежат в основе оценки кратной тригонометрической суммы, полученной А. А. Карацубой (двумерный случай был получен Г. И. Архиповым). Если обозначить через наименьшее общее кратное чисел с условием , то при справедлива оценка

,

где  — количество делителей числа , а  — количество различных простых делителей числа .