Automata

In the paper of Edward F. Moore,^[5] ${\displaystyle (n;m;p)}$, an automaton (or a machine) ${\displaystyle S}$, is defined as a device with ${\displaystyle n}$ states, ${\displaystyle m}$ input symbols and ${\displaystyle p}$ output symbols. Nine theorems on the structure of ${\displaystyle S}$ and experiments with ${\displaystyle S}$ are proved. Later such ${\displaystyle 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:

Theorem 8 (Moore). Given an arbitrary ${\displaystyle (n;m;p)}$ machine ${\displaystyle S}$, such that every two states can be distinguished from each other, there exists an experiment of length ${\displaystyle n(n-1)/2}$ that identifies the state of ${\displaystyle S}$ at the end of this experiment.

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.

Theorem A (Karatsuba). If ${\displaystyle S}$ is a ${\displaystyle (n;m;p)}$ machine such that each two its states can be distinguished from each other then there exists a ramified experiment of length at most ${\displaystyle (n-1)(n-2)/2+1}$, by means of which one can find the state ${\displaystyle S}$ at the end of the experiment.

Theorem B (Karatsuba). There exists a ${\displaystyle (n;m;p)}$ machine, every states of which can be distinguished from each other, such that the length of the shortest experiment finding the state of the machine at the end of the experiment, is equal to ${\displaystyle (n-1)(n-2)/2+1}$.

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.^[6] 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 p-adic method

A.A.Karatsuba constructed a new ${\displaystyle p}$-adic method in the theory of trigonometric sums.^[11] The estimates of so-called ${\displaystyle L}$-sums of the form

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

led^[12] to the new bounds for zeros of the Dirichlet ${\displaystyle L}$-series modulo a power of a prime number, to the asymptotic formula for the number of Waring congruence of the form

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

to a solution of the problem of distribution of fractional parts of a polynomial with integer coefficients modulo ${\displaystyle p^{k}}$. A.A. Karatsuba was the first to realize^[13] in the ${\displaystyle p}$-adic form the «embedding principle» of Euler-Vinogradov and to compute a ${\displaystyle p}$-adic analog of Vinogradov ${\displaystyle u}$-numbers when estimating the number of solutions of a congruence of the Waring type.

Assume that : ${\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)}$ and moreover : ${\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,}$ where ${\displaystyle p}$ is a prime number. Karatsuba proved that in that case for any natural number ${\displaystyle n\geq 144}$ there exists a ${\displaystyle p_{0}=p_{0}(n)}$ such that for any ${\displaystyle p_{0}>p_{0}(n)}$ every natural number ${\displaystyle N}$ can be represented in the form (1) for ${\displaystyle t\geq 20r+1}$, and for ${\displaystyle t<r}$ there exist ${\displaystyle N}$ such that the congruence (1) has no solutions.

This new approach, found by Karatsuba, led to a new ${\displaystyle 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 ${\displaystyle p}$-adic method of A.A. Karatsuba is the transition from incomplete systems of equations to complete ones at the expense of the local ${\displaystyle p}$-adic change of unknowns.^[14]

Let ${\displaystyle r}$ be an arbitrary natural number, ${\displaystyle 1\leq r\leq n}$. Determine an integer ${\displaystyle t}$ by the inequalities ${\displaystyle m_{t}\leq r\leq m_{t+1}}$. Consider the system of equations

${\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 proved that the number of solutions ${\displaystyle I_{k}}$ of this system of equations for ${\displaystyle k\geq 6rn\log n}$ satisfies the estimate

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

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.

The Hua Luogeng problem on the convergency exponent of the singular integral in the Terry problem

${\displaystyle 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 ${\displaystyle 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. In 1979 Karatsuba, together with his students G.I. Arkhipov and V.N. Chubarikov obtained a complete solution^[15] of the Hua Luogeng problem of finding the exponent of convergency of the 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},}$

where ${\displaystyle n\geq 2}$ is a fixed number.

In this case, the exponent of convergency means the value ${\displaystyle \gamma }$, such that ${\displaystyle \vartheta _{0}}$ converges for ${\displaystyle 2k>\gamma +\varepsilon }$ and diverges for ${\displaystyle 2k<\gamma -\varepsilon }$, where ${\displaystyle \varepsilon >0}$ is arbitrarily small. It was shown that the integral ${\displaystyle \vartheta _{0}}$ converges for ${\displaystyle 2k>{\tfrac {1}{2}}(n^{2}+n)+1}$ and diverges for ${\displaystyle 2k\leq {\tfrac {1}{2}}(n^{2}+n)+1}$.

At the same time, the similar problem for the integral was solved: ${\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},}$ where ${\displaystyle n,m,\ldots ,r}$ are integers, satisfying the conditions : ${\displaystyle 1\leq r<\ldots <m<n,\quad r+\ldots +m+n<{\tfrac {1}{2}}(n^{2}+n).}$

Karatsuba and his students proved that the integral ${\displaystyle \vartheta _{1}}$ converges, if ${\displaystyle 2k>n+m+\ldots +r}$ and diverges, if ${\displaystyle 2k\leq n+m+\ldots +r}$.

The integrals ${\displaystyle \vartheta _{0}}$ and ${\displaystyle \vartheta _{1}}$ arise in the studying of the so-called Prouhet–Tarry–Escott problem. Karatsuba and his students obtained a series of new results connected with the multi-dimensional analog of the Tarry problem. In particular, they proved that if ${\displaystyle F}$ is a polynomial in ${\displaystyle r}$ variables (${\displaystyle r\geq 2}$) of the form : ${\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}},}$ with the zero free term, ${\displaystyle m=(n_{1}+1)\ldots (n_{r}+1)-1}$, ${\displaystyle {\bar {\alpha }}}$ is the ${\displaystyle m}$-dimensional vector, consisting of the coefficients of ${\displaystyle F}$, then the 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 }}}$ converges for ${\displaystyle 2k>mn}$, where ${\displaystyle n}$ is the highest of the numbers ${\displaystyle n_{1},\ldots ,n_{r}}$. This result, being not a final one, generated a new area in the theory of trigonometric integrals, connected with improving the bounds of the exponent of convergency ${\displaystyle \vartheta _{2}}$ (I. A. Ikromov, M. A. Chahkiev and others).

Multiple trigonometric sums

In 1966–1980, Karatsuba developed^[16][17] (with participation of his students G.I. Arkhipov and V.N. Chubarikov) the theory of multiple Hermann Weyl trigonometric sums, that is, the sums of the form

${\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})}}$ , where ${\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}$ is a system of real coefficients ${\displaystyle \alpha (t_{1},\dots ,t_{r})}$. The central point of that theory, as in the theory of the Vinogradov trigonometric sums, is the following mean value theorem.

Let ${\displaystyle n_{1},\dots ,n_{r},P_{1},\dots ,P_{r}}$ be natural numbers, ${\displaystyle P_{1}=\min(P_{1},\dots ,P_{r})}$,${\displaystyle m=(n_{1}+1)\dots (n_{r}+1)}$. Furthermore, let ${\displaystyle \Omega }$ be the ${\displaystyle m}$-dimensional cube of the form :: ${\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}}$, in the euclidean space : and :: ${\displaystyle J=J(P_{1},\dots ,P_{r};n_{1},\dots ,n_{r};K,r)={\underset {\Omega }{\int \dots \int }}|S(A)|^{2K}dA}$ . : Then for any ${\displaystyle \tau \geq 0}$ and ${\displaystyle K\geq K_{\tau }=m\tau }$ the value ${\displaystyle J}$ can be estimated as follows

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

where ${\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 }}$, and the natural numbers ${\displaystyle \nu _{1},\dots ,\nu _{r}}$ are such that: :: ${\displaystyle -1<{\frac {P_{s}}{P_{1}}}-\nu _{s}\leq 0}$ , ${\displaystyle s=1,\dots ,r}$ .

The mean value theorem and the lemma on the multiplicity of intersection of multi-dimensional parallelepipeds form the basis of the estimate of a multiple trigonometric sum, that was obtained by Karatsuba (two-dimensional case was derived by G.I. Arkhipov^[18]). Denoting by ${\displaystyle Q_{0}}$ the least common multiple of the numbers ${\displaystyle q(t_{1},\dots ,t_{r})}$ with the condition ${\displaystyle t_{1}+\dots t_{r}\geq 1}$, for ${\displaystyle Q_{0}\geq P^{1/6}}$ the estimate holds

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

where ${\displaystyle \tau (Q)}$ is the number of divisors of the integer ${\displaystyle Q}$, and ${\displaystyle \nu (Q)}$ is the number of distinct prime divisors of the number ${\displaystyle Q}$.

The estimate of the Hardy function in the Waring problem

Applying his ${\displaystyle p}$-adic form of the Hardy-Littlewood-Ramanujan-Vinogradov method to estimating trigonometric sums, in which the summation is taken over numbers with small prime divisors, Karatsuba obtained^[19] a new estimate of the well known Hardy function ${\displaystyle G(n)}$ in the Waring's problem (for ${\displaystyle n\geq 400}$):

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

Multi-dimensional analog of the Waring problem

In his subsequent investigation of the Waring problem Karatsuba obtained^[20] the following two-dimensional generalization of that problem:

Consider the system of equations

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

where ${\displaystyle N_{i}}$ are given positive integers with the same order or growth, ${\displaystyle N_{0}\to +\infty }$, and ${\displaystyle x_{\varkappa },y_{\varkappa }}$ are unknowns, which are also positive integers. This system has solutions, if ${\displaystyle k>cn^{2}\log n}$ , and if ${\displaystyle k<c_{1}n^{2}}$, then there exist such ${\displaystyle N_{i}}$, that the system has no solutions.

The Artin problem of local representation of zero by a form

Emil Artin had posed the problem on the ${\displaystyle p}$-adic representation of zero by a form of arbitrary degree d. Artin initially conjectured a result, which would now be described as the p-adic field being a C₂ field; in other words non-trivial representation of zero would occur if the number of variables was at least d². This was shown not to be the case by an example of Guy Terjanian. Karatsuba showed that, in order to have a non-trivial representation of zero by a form, the number of variables should grow faster than polynomially in the degree d; this number in fact should have an almost exponential growth, depending on the degree. Karatsuba and his student Arkhipov proved,^[21] that for any natural number ${\displaystyle r}$ there exists ${\displaystyle n_{0}=n_{0}(r)}$, such that for any ${\displaystyle n\geq n_{0}}$ there is a form with integral coefficients ${\displaystyle F(x_{1},\dots ,x_{k})}$ of degree smaller than ${\displaystyle n}$, the number of variables of which is ${\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}}}}$

which has only trivial representation of zero in the 2-adic numbers. They also obtained a similar result for any odd prime modulus ${\displaystyle p}$.

Estimates of short Kloosterman sums

Karatsuba developed^[22][23][24] (1993—1999) a new method of estimating short Kloosterman sums, that is, trigonometric sums of the form

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

where ${\displaystyle n}$ runs through a set ${\displaystyle A}$ of numbers, coprime to ${\displaystyle m}$, the number of elements ${\displaystyle \|A\|}$ in which is essentially smaller than ${\displaystyle m}$, and the symbol ${\displaystyle n^{*}}$ denotes the congruence class, inverse to ${\displaystyle n}$ modulo ${\displaystyle m}$: ${\displaystyle nn^{*}\equiv 1(\mod m)}$.

Up to the early 1990s, the estimates of this type were known, mainly, for sums in which the number of summands was higher than ${\displaystyle {\sqrt {m}}}$ (H. D. Kloosterman, I. M. Vinogradov, H. Salié, L. Carlitz, S. Uchiyama, A. Weil). The only exception was the special moduli of the form ${\displaystyle m=p^{\alpha }}$, where ${\displaystyle p}$ is a fixed prime and the exponent ${\displaystyle \alpha }$ increases to infinity (this case was studied by A. G. Postnikov by means of the method of Vinogradov). Karatsuba's method makes it possible to estimate Kloosterman sums where the number of summands does not exceed

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

and in some cases even

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

where ${\displaystyle \varepsilon >0}$ is an arbitrarily small fixed number. The final paper of Karatsuba on this subject^[25] was published posthumously.

Various aspects of the method of Karatsuba have found applications in the following problems of analytic number theory:

• finding asymptotics of the sums of fractional parts of the form : ${\displaystyle {\sum _{n\leq x}}'{\biggl \{}{\frac {an^{*}+bn}{m}}{\biggr \}},{\sum _{p\leq x}}'{\biggl \{}{\frac {ap^{*}+bp}{m}}{\biggr \}},}$ : where ${\displaystyle n}$ runs, one after another, through the integers satisfying the condition ${\displaystyle (n,m)=1}$, and ${\displaystyle p}$ runs through the primes that do not divide the module ${\displaystyle m}$ (Karatsuba);

• finding a lower bound for the number of solutions of inequalities of the form : ${\displaystyle \alpha <{\biggl \{}{\frac {an^{*}+bn}{m}}{\biggr \}}\leq \beta }$ : in the integers ${\displaystyle n}$, ${\displaystyle 1\leq n\leq x}$, coprime to ${\displaystyle m}$, ${\displaystyle x<{\sqrt {m}}}$ (Karatsuba);
• the precision of approximation of an arbitrary real number in the segment ${\displaystyle [0,1]}$ by fractional parts of the form :

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

• a more precise constant ${\displaystyle c}$ in the Brun–Titchmarsh theorem :

${\displaystyle \pi (x;q,l)<{\frac {cx}{\varphi (q)\ln {\frac {2x}{q}}}},}$ : where ${\displaystyle \pi (x;q,l)}$ is the number of primes ${\displaystyle p}$, not exceeding ${\displaystyle x}$ and belonging to the arithmetic progression ${\displaystyle p\equiv l{\pmod {q}}}$ (J. Friedlander, H. Iwaniec);

• a lower bound for the greatest prime divisor of the product of numbers of the form :

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

• proving that there are infinitely many primes of the form:

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

• combinatorial properties of the set of numbers :

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

The Riemann zeta function

The boundary of zeros of the zeta function and the multi-dimensional problem of Dirichlet divisors

To Karatsuba belongs a new breakthrough result ^[32] in the multi-dimensional problem of Dirichlet divisors, which is connected with finding the number ${\displaystyle D_{k}(x)}$ of solutions of the inequality ${\displaystyle x_{1}*\ldots *x_{k}\leq x}$ in the natural numbers ${\displaystyle x_{1},\ldots ,x_{k}}$ as ${\displaystyle x\to +\infty }$. For ${\displaystyle D_{k}(x)}$ there is an asymptotic formula of the form

${\displaystyle D_{k}(x)=xP_{k-1}(\ln x)+R_{k}(x)}$ ,

where ${\displaystyle P_{k-1}(u)}$ is a polynomial of degree ${\displaystyle (k-1)}$, the coefficients of which depend on ${\displaystyle k}$ and can be found explicitly and ${\displaystyle R_{k}(x)}$ is the remainder term, all known estimates of which (up to 1960) were of the form

${\displaystyle |R_{k}(x)|\leq x^{1-\alpha (k)}(c\ln x)^{k}}$ ,

where ${\displaystyle \alpha ={\frac {1}{ak+b}}}$, ${\displaystyle a,b,c}$ are some absolute positive constants.

Karatsuba obtained a more precise estimate of ${\displaystyle R_{k}(x)}$, in which the value ${\displaystyle \alpha (k)}$ was of order ${\displaystyle k^{-2/3}}$ and was decreasing much slower than ${\displaystyle \alpha (k)}$ in the previous estimates. Karatsuba's estimate is uniform in ${\displaystyle x}$ and ${\displaystyle k}$; in particular, the value ${\displaystyle k}$ may grow as ${\displaystyle x}$ grows (as some power of the logarithm of ${\displaystyle x}$). (A similar looking, but weaker result was obtained in 1960 by a German mathematician Richert, whose paper remained unknown to Soviet mathematicians at least until the mid-seventies.)

Proof of the estimate of ${\displaystyle R_{k}(x)}$ is based on a series of claims, essentially equivalent to the theorem on the boundary of zeros of the Riemann zeta function, obtained by the method of Vinogradov, that is, the theorem claiming that ${\displaystyle \zeta (s)}$ has no zeros in the region

${\displaystyle Re\ s\geq 1-{\frac {c}{(\ln |t|)^{2/3}(\ln \ln |t|)^{1/3}}},\quad |t|>10}$ .

Karatsuba found ^[33](2000) the backward relation of estimates of the values ${\displaystyle R_{k}(x)}$ with the behaviour of ${\displaystyle \zeta (s)}$ near the line ${\displaystyle Re\ s=1}$. In particular, he proved that if ${\displaystyle \alpha (y)}$ is an arbitrary non-increasing function satisfying the condition ${\displaystyle 1/y\leq \alpha (y)\leq 1/2}$, such that for all ${\displaystyle k\geq 2}$ the estimate

${\displaystyle |R_{k}(x)|\leq x^{1-\alpha (k)}(c\ln x)^{k}}$

holds, then ${\displaystyle \zeta (s)}$ has no zeros in the region

${\displaystyle Re\ s\geq 1-c_{1}\,{\frac {\alpha (\ln |t|)}{\ln \ln |t|}},\quad |t|\geq e^{2}}$

(${\displaystyle c,c_{1}}$ are some absolute constants).

The Dirichlet characters