Anatoly Karatsuba

En el artículo de Edward F. Moore , ^{[ 5 ]}${\displaystyle (n;m;p)}$, un autómata (o una máquina)${\displaystyle S}$, se define como un dispositivo con${\displaystyle n}$estados,${\displaystyle m}$símbolos de entrada y${\displaystyle p}$símbolos de salida. Nueve teoremas sobre la estructura de${\displaystyle S}$y experimentos con${\displaystyle S}$Se demuestran. Más tarde tales${\displaystyle S}$Las máquinas recibieron el nombre de máquinas de Moore . Al final del artículo, en el capítulo «Nuevos problemas», Moore formula el problema de mejorar las estimaciones que obtuvo en los Teoremas 8 y 9:

Teorema 8 (Moore)

Dado un arbitrario${\displaystyle (n;m;p)}$máquina${\displaystyle S}$, de tal manera que cada par de estados se puede distinguir entre sí, existe un experimento de longitud${\displaystyle n(n-1)/2}$que identifica el estado de${\displaystyle S}$al final de este experimento.

En 1957, Karatsuba demostró dos teoremas que resolvieron completamente el problema de Moore sobre la mejora de la estimación de la duración del experimento en su Teorema 8 .

Teorema A (Karatsuba)

Si${\displaystyle S}$es un${\displaystyle (n;m;p)}$máquina tal que cada dos de sus estados se pueden distinguir entre sí entonces existe un experimento ramificado de longitud como máximo${\displaystyle (n-1)(n-2)/2+1}$, mediante el cual se puede encontrar el estado${\displaystyle S}$al final del experimento.

Teorema B (Karatsuba)

Existe un${\displaystyle (n;m;p)}$máquina, cuyos estados pueden distinguirse entre sí, de tal manera que la duración del experimento más corto para encontrar el estado de la máquina al final del experimento sea igual a${\displaystyle (n-1)(n-2)/2+1}$.

Estos dos teoremas fueron demostrados por Karatsuba en su cuarto año como base de su proyecto de cuarto año; el artículo correspondiente fue enviado a la revista "Uspekhi Mat. Nauk" el 17 de diciembre de 1958 y publicado en junio de 1960. ^{[ 6 ]} Hasta el día de hoy (2011), este resultado de Karatsuba, que más tarde adquirió el título de "el teorema de Moore-Karatsuba", sigue siendo el único resultado no lineal preciso (el único orden no lineal preciso de la estimación) tanto en la teoría de autómatas como en problemas similares de la teoría de la complejidad de los cálculos.

AAKaratsuba construyó un nuevo${\displaystyle p}$Método -ádico en la teoría de sumas trigonométricas. ^{[ 11 ]} Las estimaciones de los llamados${\displaystyle L}$-sumas de la forma

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

condujo ^{[ 12 ]} a los nuevos límites para los ceros de la ecuación de Dirichlet${\displaystyle L}$-serie módulo una potencia de un número primo , a la fórmula asintótica para el número de congruencia de Waring de la forma

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

a una solución del problema de distribución de partes fraccionarias de un polinomio con coeficientes enteros módulo${\displaystyle p^{k}}$. AA Karatsuba fue el primero en darse cuenta ^{[ 13 ]} en el${\displaystyle p}$-forma ádica el «principio de incrustación» de Euler-Vinogradov y para calcular un${\displaystyle p}$-anádico análogo de Vinogradov${\displaystyle u}$-números al estimar el número de soluciones de una congruencia del tipo Waring.

Supongamos que  :${\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)}$y además  :${\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,}$dónde${\displaystyle p}$es un número primo. Karatsuba demostró que en ese caso para cualquier número natural${\displaystyle n\geq 144}$existe un${\displaystyle p_{0}=p_{0}(n)}$de tal manera que para cualquier${\displaystyle p_{0}>p_{0}(n)}$cada número natural${\displaystyle N}$puede representarse en la forma (1) para${\displaystyle t\geq 20r+1}$y para${\displaystyle t<r}$existen${\displaystyle N}$de tal manera que la congruencia (1) no tenga soluciones.

Este nuevo enfoque, hallado por Karatsuba, condujo a una nueva${\displaystyle p}$Demostración ádica del teorema del valor medio de Vinogradov , que desempeña un papel central en el método de sumas trigonométricas de Vinogradov.

Otro componente del${\displaystyle p}$El método -ádico de AA Karatsuba es la transición de sistemas de ecuaciones incompletos a completos a expensas de la local${\displaystyle p}$Cambio -ádico de incógnitas. ^{[ 14 ]}

Dejar${\displaystyle r}$sea ​​un número natural arbitrario ,${\displaystyle 1\leq r\leq n}$Determinar un número entero${\displaystyle t}$por las desigualdades${\displaystyle m_{t}\leq r\leq m_{t+1}}$Consideremos el sistema de ecuaciones

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

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

Karatsuba demostró que el número de soluciones${\displaystyle I_{k}}$de este sistema de ecuaciones para${\displaystyle k\geq 6rn\log n}$satisface la estimación

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

Para sistemas de ecuaciones incompletos, en los que las variables toman valores que incluyen números con divisores primos pequeños, Karatsuba aplicó la traslación multiplicativa de variables. Esto condujo a una estimación prácticamente nueva de las sumas trigonométricas y a un nuevo teorema del valor medio para dichos sistemas de ecuaciones.

${\displaystyle p}$El método -ádico de AAKaratsuba incluye las técnicas de estimar la medida del conjunto de puntos con valores pequeños de funciones en términos de los valores de sus parámetros (coeficientes, etc.) y, a la inversa, las técnicas de estimar esos parámetros en términos de la medida de este conjunto en el real y${\displaystyle p}$Métricas -ádicas. Este aspecto del método de Karatsuba se manifestó especialmente claro en la estimación de integrales trigonométricas, lo que condujo a la solución del problema de Hua Luogeng . En 1979, Karatsuba, junto con sus estudiantes GI Arkhipov y VN Chubarikov, obtuvieron una solución completa ^{[ 15 ]} del problema de Hua Luogeng de hallar el exponente de convergencia de la integral:

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

dónde${\displaystyle n\geq 2}$es un número fijo.

En este caso, el exponente de convergencia significa el valor${\displaystyle \gamma }$, de tal manera que${\displaystyle \vartheta _{0}}$converge para${\displaystyle 2k>\gamma +\varepsilon }$y diverge para${\displaystyle 2k<\gamma -\varepsilon }$, dónde${\displaystyle \varepsilon >0}$es arbitrariamente pequeño. Se demostró que la integral${\displaystyle \vartheta _{0}}$converge para${\displaystyle 2k>{\tfrac {1}{2}}(n^{2}+n)+1}$y diverge para ${\displaystyle 2k\leq {\tfrac {1}{2}}(n^{2}+n)+1}$.

Al mismo tiempo, se resolvió un problema similar para la integral: ${\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},}$ dónde${\displaystyle n,m,\ldots ,r}$son números enteros que satisfacen las condiciones  :${\displaystyle 1\leq r<\ldots <m<n,\quad r+\ldots +m+n<{\tfrac {1}{2}}(n^{2}+n).}$

Karatsuba y sus alumnos demostraron que la integral${\displaystyle \vartheta _{1}}$converge, si${\displaystyle 2k>n+m+\ldots +r}$y diverge, si${\displaystyle 2k\leq n+m+\ldots +r}$.

Las integrales${\displaystyle \vartheta _{0}}$y${\displaystyle \vartheta _{1}}$Surgen en el estudio del llamado problema de Prouhet-Tarry-Escott . Karatsuba y sus estudiantes obtuvieron una serie de nuevos resultados relacionados con el análogo multidimensional del problema de Tarry. En particular, demostraron que si${\displaystyle F}$es un polinomio en${\displaystyle r}$variables (${\displaystyle r\geq 2}$) de la forma  : ${\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}},}$ con el plazo gratuito cero, ${\displaystyle m=(n_{1}+1)\ldots (n_{r}+1)-1}$,${\displaystyle {\bar {\alpha }}}$es el${\displaystyle m}$vector de dimensión, que consta de los coeficientes de${\displaystyle F}$, entonces la integral  : ${\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 }}}$converge para${\displaystyle 2k>mn}$, dónde${\displaystyle n}$es el más alto de los números${\displaystyle n_{1},\ldots ,n_{r}}$Este resultado, al no ser definitivo, generó una nueva área en la teoría de las integrales trigonométricas, relacionada con la mejora de los límites del exponente de convergencia.${\displaystyle \vartheta _{2}}$(IA Ikromov, MA Chahkiev y otros).

En 1966–1980, Karatsuba desarrolló ^{[ 16 ] [ 17 ]} (con la participación de sus estudiantes GI Arkhipov y VN Chubarikov) la teoría de las sumas trigonométricas múltiples de Hermann Weyl , es decir, las sumas de la forma

${\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})}}$, dónde${\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}$es un sistema de coeficientes reales${\displaystyle \alpha (t_{1},\dots ,t_{r})}$. El punto central de esa teoría, como en la teoría de las sumas trigonométricas de Vinogradov, es el siguiente teorema del valor medio .

Dejar${\displaystyle n_{1},\dots ,n_{r},P_{1},\dots ,P_{r}}$sean números naturales,${\displaystyle P_{1}=\min(P_{1},\dots ,P_{r})}$,${\displaystyle m=(n_{1}+1)\dots (n_{r}+1)}$Además, dejemos${\displaystyle \Omega }$ser el${\displaystyle m}$Cubo dimensional de la forma  ::${\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}}$, en el espacio euclidiano  : y  ::${\displaystyle J=J(P_{1},\dots ,P_{r};n_{1},\dots ,n_{r};K,r)={\underset {\Omega }{\int \dots \int }}|S(A)|^{2K}dA}$.  : Entonces, para cualquier${\displaystyle \tau \geq 0}$y${\displaystyle K\geq K_{\tau }=m\tau }$el valor${\displaystyle J}$se puede estimar de la siguiente manera

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

dónde${\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 }}$y los números naturales${\displaystyle \nu _{1},\dots ,\nu _{r}}$son tales que:  ::${\displaystyle -1<{\frac {P_{s}}{P_{1}}}-\nu _{s}\leq 0}$,${\displaystyle s=1,\dots ,r}$.

El teorema del valor medio y el lema sobre la multiplicidad de intersección de paralelepípedos multidimensionales forman la base de la estimación de una suma trigonométrica múltiple, que fue obtenida por Karatsuba (el caso bidimensional fue derivado por GI Arkhipov ^{[ 18 ]} ). Denotando por${\displaystyle Q_{0}}$el mínimo común múltiplo de los números${\displaystyle q(t_{1},\dots ,t_{r})}$con la condición${\displaystyle t_{1}+\dots t_{r}\geq 1}$, para${\displaystyle Q_{0}\geq P^{1/6}}$La estimación se mantiene

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

dónde${\displaystyle \tau (Q)}$es el número de divisores del entero${\displaystyle Q}$, y${\displaystyle \nu (Q)}$es el número de divisores primos distintos del número${\displaystyle Q}$.

Aplicando su${\displaystyle p}$Forma -ádica del método de Hardy-Littlewood-Ramanujan-Vinogradov para estimar sumas trigonométricas, en la que la suma se toma sobre números con pequeños divisores primos, Karatsuba obtuvo ^{[ 19 ]} una nueva estimación de la conocida función de Hardy${\displaystyle G(n)}$en el problema de Waring (para${\displaystyle n\geq 400}$):

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

En su posterior investigación del problema de Waring, Karatsuba obtuvo ^{[ 20 ]} la siguiente generalización bidimensional de dicho problema:

Consideremos el sistema de ecuaciones

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

dónde${\displaystyle N_{i}}$se dan enteros positivos con el mismo orden o crecimiento,${\displaystyle N_{0}\to +\infty }$, y${\displaystyle x_{\varkappa },y_{\varkappa }}$son incógnitas, que también son enteros positivos. Este sistema tiene soluciones, si${\displaystyle k>cn^{2}\log n}$y si${\displaystyle k<c_{1}n^{2}}$, entonces existen tales${\displaystyle N_{i}}$que el sistema no tiene soluciones.

Emil Artin había planteado el problema en el${\displaystyle p}$Representación p-ádica del cero mediante una forma de grado arbitrario d . Artin conjeturó inicialmente un resultado, que ahora se describiría como que el campo p-ádico es un campo C2 ; en otras palabras _, una representación no trivial del cero ocurriría si el número de variables fuera al menos ^d2 . Esto se demostró que no era el caso mediante un ejemplo de Guy Terjanian . Karatsuba demostró que, para tener una representación no trivial del cero mediante una forma, el número de variables debería crecer más rápido que polinómicamente en el grado d ; este número, de hecho, debería tener un crecimiento casi exponencial, dependiendo del grado. Karatsuba y su estudiante Arkhipov demostraron, ^{[ 21 ]} que para cualquier número natural${\displaystyle r}$existe${\displaystyle n_{0}=n_{0}(r)}$, de tal manera que para cualquier${\displaystyle n\geq n_{0}}$Hay una forma con coeficientes enteros.${\displaystyle F(x_{1},\dots ,x_{k})}$de grado menor que${\displaystyle n}$, cuyo número de variables es${\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}}}}$

que tiene solo una representación trivial de cero en los números 2-ádicos. También obtuvieron un resultado similar para cualquier módulo primo impar.${\displaystyle p}$.

Karatsuba desarrolló ^{[ 22 ] [ 23 ] [ 24 ]} (1993—1999) un nuevo método para estimar sumas cortas de Kloosterman , es decir, sumas trigonométricas de la forma

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

dónde${\displaystyle n}$recorre un conjunto${\displaystyle A}$de números, coprimos a${\displaystyle m}$, el número de elementos${\displaystyle \|A\|}$en el cual es esencialmente más pequeño que${\displaystyle m}$y el símbolo${\displaystyle n^{*}}$denota la clase de congruencia, inversa de${\displaystyle n}$módulo${\displaystyle m}$:${\displaystyle nn^{*}\equiv 1(\mod m)}$.

Hasta principios de la década de 1990, las estimaciones de este tipo se conocían principalmente para sumas en las que el número de sumandos era mayor que${\displaystyle {\sqrt {m}}}$( HD Kloosterman , IM Vinogradov , H. Salié, L. Carlitz , S. Uchiyama, A. Weil ). La única excepción fueron los módulos especiales de la forma${\displaystyle m=p^{\alpha }}$, dónde${\displaystyle p}$es un número primo fijo y el exponente${\displaystyle \alpha }$aumenta hasta el infinito (este caso fue estudiado por AG Postnikov mediante el método de Vinogradov). El método de Karatsuba permite estimar sumas de Kloosterman donde el número de sumandos no excede

${\displaystyle m^{\varepsilon },}$

y en algunos casos incluso

${\displaystyle \exp {\{(\ln m)^{2/3+\varepsilon }\}},}$

dónde${\displaystyle \varepsilon >0}$es un número fijo arbitrariamente pequeño. El último artículo de Karatsuba sobre este tema ^{[ 25 ]} se publicó póstumamente.

Diversos aspectos del método de Karatsuba han encontrado aplicaciones en los siguientes problemas de la teoría analítica de números:

• hallar el comportamiento asintótico de las sumas de partes fraccionarias de la forma  :${\displaystyle {\sum _{n\leq x}}'{\biggl \{}{\frac {an^{*}+bn}{m}}{\biggr \}},{\sum _{p\leq x}}'{\biggl \{}{\frac {ap^{*}+bp}{m}}{\biggr \}},}$ : dónde${\displaystyle n}$recorre, uno tras otro, los números enteros que satisfacen la condición${\displaystyle (n,m)=1}$, y${\displaystyle p}$recorre los números primos que no dividen el módulo.${\displaystyle m}$(Karatsuba);

• hallar una cota inferior para el número de soluciones de desigualdades de la forma  :${\displaystyle \alpha <{\biggl \{}{\frac {an^{*}+bn}{m}}{\biggr \}}\leq \beta }$ : en los números enteros${\displaystyle n}$,${\displaystyle 1\leq n\leq x}$, coprimo a${\displaystyle m}$,${\displaystyle x<{\sqrt {m}}}$(Karatsuba);
• la precisión de aproximación de un número real arbitrario en el segmento${\displaystyle [0,1]}$por partes fraccionarias de la forma  :

${\displaystyle {\biggl \{}{\frac {an^{*}+bn}{m}}{\biggr \}},}$ : dónde${\displaystyle 1\leq n\leq x}$,${\displaystyle (n,m)=1}$,${\displaystyle x<{\sqrt {m}}}$ (Karatsuba);

• una constante más precisa${\displaystyle c}$en el teorema de Brun-Titchmarsh  :

${\displaystyle \pi (x;q,l)<{\frac {cx}{\varphi (q)\ln {\frac {2x}{q}}}},}$ : dónde${\displaystyle \pi (x;q,l)}$es el número de primos${\displaystyle p}$, sin exceder${\displaystyle x}$y perteneciente a la progresión aritmética${\displaystyle p\equiv l{\pmod {q}}}$ ( J. Friedlander , H. Iwaniec );

• un límite inferior para el mayor divisor primo del producto de números de la forma  :

${\displaystyle n^{3}+2}$,${\displaystyle N<n\leq 2N}$ ( Dr. Heath-Brown );

• demostrando que existen infinitos números primos de la forma:

${\displaystyle a^{2}+b^{4}}$ ( J. Friedlander , H. Iwaniec );

• Propiedades combinatorias del conjunto de números  :

${\displaystyle n^{*}{\pmod {m}}}$${\displaystyle 1\leq n\leq m^{\varepsilon }}$ (AA Glibichuk).