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

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

А. О. Карацуба побудував новий ${\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.}$

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