Anatoly Karatsuba

Anatoly Alexeyevich Karatsuba (his first name often spelled Anatolii) (Анато́лий Алексе́евич Карацу́ба; Grozny, Soviet Union, 31 January 1937 – Moscow, Russia, 28 September 2008 ) was a Russian mathematician working in the field of analytic number theory, p-adic numbers and Dirichlet series.

In 1957 Karatsuba proved two theorems which completely solved the Moore problem on improving the estimate of the length of experiment in his Theorem 8.

These two theorems were proved by Karatsuba in his 4th year as a basis of his 4th year project; the corresponding paper was submitted to the journal "Uspekhi Mat. Nauk" on December 17, 1958 and published in June 1960.

For most of his student and professional life he was associated with the Faculty of Mechanics and Mathematics of Moscow State University, defending a D.Sc. there entitled "The method of trigonometric sums and intermediate value theorems" in 1966.

He later held a position at the Steklov Institute of Mathematics of the Academy of Sciences.

His textbook Foundations of Analytic Number Theory went to two editions, 1975 and 1983.

The Karatsuba algorithm is the earliest known divide and conquer algorithm for multiplication and lives on as a special case of its direct generalization, the Toom–Cook algorithm.

The main research works of Anatoly Karatsuba were published in more than 160 research papers and monographs.

His daughter, Yekaterina Karatsuba, also a mathematician, constructed the FEE method.

As a student of Lomonosov Moscow State University, Karatsuba attended the seminar of Andrey Kolmogorov and found solutions to two problems set up by Kolmogorov.

This was essential for the development of automata theory and started a new branch in Mathematics, the theory of fast algorithms.

In the paper of Edward F. Moore, (n; m; p), an automaton (or a machine) S, is defined as a device with n states, m input symbols

and p output symbols.

Nine theorems on the structure of S and experiments with S are proved.

Later such S machines got the name of Moore machines.

At the end of the paper, in the chapter «New problems», Moore formulates the problem of improving the estimates which he obtained in Theorems 8 and 9:

In 1979 Karatsuba, together with his students G.I. Arkhipov and V.N. Chubarikov obtained a complete solution of the Hua Luogeng problem of finding the exponent of convergency of the integral:

where n \ge 2 is a fixed number.

In this case, the exponent of convergency means the value \gamma, such that \vartheta_0 converges for and diverges for, where is arbitrarily small.

It was shown that the integral converges for and diverges for

.

Up to this day (2011) this result of Karatsuba that later acquired the title "the Moore-Karatsuba theorem", remains the only precise (the only precise non-linear order of the estimate) non-linear result both in the automata theory and in the similar problems of the theory of complexity of computations.

The main research works of A. A. Karatsuba were published in more than 160 research papers and monographs.

A.A.Karatsuba constructed a new p-adic method in the theory of trigonometric sums.

The estimates of so-called L-sums of the form

led to the new bounds for zeros of the Dirichlet L-series modulo a power of a prime number, to the asymptotic formula for the number of Waring congruence of the form

to a solution of the problem of distribution of fractional parts of a polynomial with integer coefficients modulo p^k.

A.A. Karatsuba was the first to realize in the p-adic form the «embedding principle» of Euler-Vinogradov and to compute a p-adic analog of Vinogradov u-numbers when estimating the number of solutions of a congruence of the Waring type.

Assume that : and moreover : where p is a prime number.

Karatsuba proved that in that case for any natural number n \ge 144 there exists a such that for any every natural number N can be represented in the form (1) for, and for t < r there exist N such that the congruence (1) has no solutions.

This new approach, found by Karatsuba, led to a new p-adic proof of the Vinogradov mean value theorem, which plays the central part in the Vinogradov's method of trigonometric sums.

Another component of the p-adic method of A.A. Karatsuba is the transition from incomplete systems of equations to complete ones at the expense of the local p-adic change of unknowns.

Let r be an arbitrary natural number,.

Determine an integer t by the inequalities.

Consider the system of equations

Karatsuba proved that the number of solutions I_k of this system of equations for satisfies the estimate

For incomplete systems of equations, in which the variables run through numbers with small prime divisors, Karatsuba applied multiplicative translation of variables.

This led to an essentially new estimate of trigonometric sums and a new mean value theorem for such systems of equations.

p-adic method of A.A.Karatsuba includes the techniques of estimating the measure of the set of points with small values of functions in terms of the values of their parameters (coefficients etc.) and, conversely, the techniques of estimating those parameters in terms of the measure of this set in the real and p-adic metrics.

This side of Karatsuba's method manifested itself especially clear in estimating trigonometric integrals, which led to the solution of the problem of Hua Luogeng.