Карацуба Анатолій Олексійович
рос. Анатолий Алексеевич Карацуба
Народився	31 січня 1937(1937-01-31)[1]  Грозний, РРФСР, СРСР[1]
Помер	28 вересня 2008(2008-09-28)[1] (71 рік)  Москва, Росія
Країна	Росія  СРСР
Діяльність	математик, викладач університету
Alma mater	Механіко-математичний факультет МДУd МДУ[2]
Галузь	математичний аналіз, теорія чисел, фізика, теорія алгоритмів і математика[3]
Заклад	Математичний інститут імені Стєклова МДУ
Науковий ступінь	доктор фізико-математичних наук
Науковий керівник	Nikolay Korobovd
Відомі учні	Sergei Voronind
Аспіранти, докторанти	Sergei Voronind Vladimir Chubarikovd Gennadiy Arhipovd Alla Aleksandrovna Lavrikd[2] Gavkhar Dehkhanovna Negmatovad[2] Doychin Ivanov Tolevd[2] Mikhail Mikhailovich Petechuckd[2] Vladimir Aleksandrovich Plaksind[2] Ilgar Shikar oglu Jabbarovd[2] Irina Rezvyakovad[2] Zarullo Khusenovich Rakhmonovd[2] Sergei Aleksandrovich Gritsenkod[2] Grigori Abramovich Kolesnikd[2] Maksim Korolevd[2] Maris Evgenievich Changad[2]
Діти	Yekaterina Karatsubad
Нагороди
Карацуба Анатолій Олексійович у Вікісховищі

Анатолій Олексійович Карацу́ба (31 січня 1937, Грозний — 28 вересня 2008, Москва) — радянський і російський математик. Творець першого швидкого методу в історії математики — методу множення великих чисел^[4][5] (множення Карацуби).

Анатолій Карацуба навчався в 1944—1954 роках у середній чоловічій школі № 6 міста Грозного і закінчив її зі срібною медаллю. Вже в ранні роки він виявив виняткові здібності до математики, розв'язуючи в молодших класах завдання, які давали в математичному гуртку старшокласникам.

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

Від 1983 року був провідним фахівцем у галузі теорії чисел в СРСР і Росії, і завідувачем відділу теорії чисел в МІАН, професором кафедри теорії чисел МДУ від 1970 року і професором кафедри математичного аналізу МДУ (створена 1962 року) від 1980 року. Його дослідницькі інтереси включали тригонометричні суми і тригонометричні інтеграли, дзета-функцію Рімана, характери Діріхле, скінченні автомати, ефективні алгоритми.

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

• 1981: Премія імені П. Л. Чебишова АН СРСР^[ru]
• 1999: Заслужений діяч науки РФ
• 2001: Премія імені І. М. Виноградова^[ru] РАН

Студентом МДУ ім. Ломоносова, А. О. Карацуба брав участь у роботі семінару А. М. Колмогорова і розв'язав дві поставлені Колмогоровим задачі, що дало імпульс розвитку теорії автоматів і поклало початок новому напрямку в математиці — теорії швидких алгоритмів.

У статті Едварда Мура «Умоглядні експерименти на послідовних машинах»^[6] ${\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}$.

Швидкі алгоритми — галузь обчислювальної математики, яка вивчає алгоритми обчислення заданої функції з заданою точністю з застосуванням якомога меншої кількості бітових операцій. Вважається, що числа записано в двійковій системі числення, знаки якої 0 і 1 називають бітами. Одна бітова операція визначається як запис знаків 0, 1, плюс, мінус, дужка; додавання, віднімання і множення двох бітів. Перші постановки задач про бітову складність обчислення належать А. М. Колмогорову. Складність алгоритму множення ${\displaystyle n}$ визначається як кількість бітових операцій, достатня для обчислення добутку двох 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}}$, про що повідомив Колмогорову після чергового засідання семінару. На наступному засіданні семінару цей метод розказав сам Колмогоров, і семінар припинив свою роботу^[7]. Першу статтю з описом множення Карацуби підготував Колмогоров, подавши в ній два різних, не пов'язаних між собою результати двох своїх учнів^[8].

Хоча в статті Колмогоров чітко зазначив, що одна теорема (не пов'язана зі швидким множенням) належить Ю. Офману, а інша теорема (з першим в історії швидким множенням) належить А. Карацубі, однак, ця публікація двох авторів надовго збила з пантелику читачів, які вважали, що обидва автори відкрили метод швидкого множення разом, і навіть називали цей метод іменами обох дослідників. Метод Карацуби згодом узагальнено за допомогою парадигми «розділяй та володарюй», іншими важливими прикладами якої є метод двійкового розбиття^[en], двійковий пошук, метод бісекції та інші.

Згодом на основі цієї ідеї А. Карацуби^[7][9][5] побудовано багато швидких алгоритмів, найвідомішими з яких є його безпосередні узагальнення, такі як метод множення Шьонгаґе — Штрассена, метод матричного множення Штрассена^[10], метод швидкого перетворення Фур'є. Французький математик і філософ Жан-Поль Делає^[en] назвав метод множення Карацуби «одним з найкорисніших результатів математики»^[11]. Алгоритм Анатолія Карацуби впроваджено практично в усіх сучасних комп'ютерах не лише на програмному, а й на апаратному рівні^{[джерело?]}.

У своїй статті «Про математичні роботи професора Карацуби»^[12], присвяченій 60-річному ювілею А. О. Карацуби, його учні Г. І. Архипов і В. М. Чубариков^[ru] так описують особливості наукових робіт А. О. Карацуби :

«При викладі праць чудових учених природно виділити якісь характерні і яскраві риси їхньої творчості. Такими визначальними рисами в науковій діяльності професора Карацуби є комбінаторна винахідливість, ґрунтовність і певна завершеність результатів.»

Основні дослідження А. О. Карацуби опубліковані більш ніж у 160 наукових статтях і монографіях.^{[13][14][15][16]}

А. О. Карацуба побудував новий ${\displaystyle p}$-адичний метод у теорії тригонометричних сум. Отримані ним оцінки^[17] привели до нових меж нулів ${\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.}$

Для неповних систем рівнянь, у яких змінні пробігають числа з малими простими дільниками, А. О. Карацуба застосував мультиплікативний зсув змінних. Це призвело до якісно нової оцінки тригонометричних сум і нової теореми про середнє для таких систем рівнянь.

• Список наукових праць [Архівовано 28 лютого 2018 у Wayback Machine.] на сайті МІАНу
• Данні про наукові інтереса, освіту і професійну діяльність [Архівовано 4 березня 2016 у Wayback Machine.]
• Архипов Г. И., Чубариков В. Н. Анатолий Алексеевич Карацуба [Архівовано 20 серпня 2021 у Wayback Machine.]