# Analytic number theory

A branch of number theory. Analytic number theory deals with the problems of distribution of primes, studies the behaviour of number-theoretic functions, and the theory of algebraic and transcendental numbers.

## Distribution of prime numbers

a) The problem of the distribution of prime numbers (primes) is one of the most interesting and most difficult problems in analytic number theory. The first result on the problem of the distribution of primes was obtained by Euclid: There are infinitely many primes. Let $\pi(x)$ be the number of primes not exceeding $x$. Euclid's theorem can then be formulated as follows: $\pi(x)\to +\infty$ as $x\to\infty$. The next step was due to P.L. Chebyshev (1850), who proved that:

1) The quantity $\pi(x)$ satisfies the inequalities

$$\frac{ax}{\ln x}<\pi(x)<\frac{bx}{\ln x},$$

where $a\geq(\ln 2)/2$; $b\leq 2\ln 2$.

2) If there exists a limit of $\pi(x)\ln(x)/x$ as $x\to+\infty$, this limit is one.

The problem of the existence of this limit was solved in 1896 by J. Hadamard and by Ch.J. de la Vallée-Poussin, who established thereby that

$$\pi(x)=\frac{x}{\ln x}(1+o(1)).$$

De la Vallée-Poussin demonstrated a much more general assertion, viz. if

$$\pi(x)=\int_2^x\frac{\mbox{d}t}{\ln t}+R(x),$$

then

$$R(x)=O(xe^{-\alpha\sqrt{\ln x}}),$$

where $\alpha>0$ is an absolute constant (cf. de la Vallée-Poussin theorem). This problem was solved by methods of the theory of functions of a complex variable. The problem of estimating $R(x)$ is closely connected with the problem on the behaviour of a certain function of a complex variable, which was first (1859) studied by B. Riemann and which is now known as Riemann's zeta-function. This function is defined by

$$\zeta(s)=1^{-s}+2^{-s}+\cdots+n^{-s}+\cdots,\,\,\,s=\sigma+it,\,\,\,\sigma>1.$$

Even earlier (1737, 1749) the zeta-function with real $s$-values was studied by L. Euler, who demonstrated the identity specifying the connection between $\zeta(s)$ and prime numbers:

$$\zeta(s)=(1-2^{-s})^{-1}(1-3^{-s})^{-1}\cdots(1-p^{-s})^{-1}\cdots,\,\,\,\sigma>1,$$

where the product is taken over all prime numbers. The function $\zeta(s)$, which is given in the form of a series for $\sigma>1$, can be analytically extended to the entire plane of the complex variable; the resulting function is analytic in the entire complex plane except at the point $s=1$, where it has a simple pole with residue one. The problem of estimating the remainder $R(x)$ in the asymptotic formula for the distribution of primes is closely connected with the problem of the distribution of the zeros of $\zeta(s)$ in the "critical" strip $0\leq\sigma\leq1$. According to the Riemann hypothesis, all the zeros of $\zeta(s)$ in the critical strip lie on the straight line $\sigma=1/2$. It follows from this hypothesis that $R(x)=O(\sqrt{x}\ln x)$. Conversely, the Riemann hypothesis on the zeros of $\zeta(s)$ follows from the relation $R(x)=O(x^{1/2+\epsilon})$, where $\epsilon>0$ may be as small as one pleases (cf. Riemann hypotheses). Hadamard and de la Vallée-Poussin obtained the asymptotic law for the distribution of primes by proving that $\zeta(s)$ cannot have any zeros if $\sigma\geq 1$. So-called $\Omega$-theorems were proved for $R(x)$: There exist two sequences $X\to+\infty$, $Y\to+\infty$ such that

$$R(X)<-X^{1/2}\frac{\ln\ln\ln X}{\ln\ln X},$$ $$R(Y)>Y^{1/2}\frac{\ln\ln\ln Y}{\ln\ln Y}.$$

b) A second problem on the distribution of primes is to estimate the difference between two successive primes, i.e. the number $\Delta_n=p_{n+1}-p_n$, where $p_n$ is the $n$-th prime. Here too, the first general result is due to Chebyshev, who showed that at least one prime number is contained between $N$ and $2N$, where $N\geq 1$ (the Bertrand postulate). The estimate of $\Delta_n$ is closely connected with the function $N(\alpha,T)$, which is the number of zeros of $\zeta(s)$ in the rectangle $1/2\leq\alpha\leq\sigma\leq1$, $\lvert t\rvert\leq T$. The function $N(\alpha,T)$ is in turn closely connected with the function $\zeta(1/2+it)$. The existing hypotheses are: $N(\alpha,T)=O(T^{2(1-\alpha)+\epsilon})$ (the density hypothesis) and $\zeta(1/2+it)=O(t^{\epsilon})$ (the Lindelöf hypothesis), where $\epsilon>0$ may be as small as one pleases. Lindelöf's hypothesis follows from the Riemann hypothesis on $\zeta(s)$; the density hypothesis follows from Lindelöf's hypothesis, and it follows from the density hypothesis that $\Delta_n=O(n^{1/2+\epsilon})$. It was proved that $\Delta_n=O(n^{\gamma})$, where $\gamma<1$.

c) The problem of the distribution of primes in arithmetical progressions $nk_l$, $(k,l)=1$, $n=0,1,\ldots,$ leads to the problem on the zeros of special zeta-functions — the so-called Dirichlet $L$-series, of the form

$$a_11^{-s}+a_22^{-s}+\cdots+a_nn^{-s}+\cdots$$

for $\sigma>1$, where $a_n$ depends on $n$ and on the difference $k$ of the series (Dirichlet characters modulo $k$).

The problem on the distribution of zeros of Dirichlet $L$-series and the distribution of primes in arithmetical progressions have their own specific features. One of the principal achievements in this field, due to C.L. Siegel (1935), is as follows: Let $\pi(x,k,l)$ be the number of primes not exceeding $x$ in the series $nk+l$, $n=0,1,\ldots,$. Then

$$\pi(x,k,l)=\frac{1}{\phi(k)}\int_2^x\frac{\mathrm{d}t}{\ln t}+O(x\ln^{-A}x),$$

where $\phi(k)$ is the Euler function and $1\leq k\leq \ln^Bx$, where $A$ and $B$ are arbitrary fixed numbers. Information about the distribution of prime numbers in arithmetical progressions is extensively used in solving additive problems involving prime numbers. See also Distribution of prime numbers.

Additive problems in analytic number theory include problems involving a special type of integer equations. The main problems of this kind are: To prove the solvability of a given equation and to find an asymptotic formula for the number of solutions of a given equation. The latter problem is much more difficult and, in a certain sense, its positive solution constitutes an answer to the first problem. Classical examples of additive problems are the Waring problem, the Goldbach problem and the Hardy–Littlewood problem.

Waring's problem (1770) can be formulated as follows: Let $J_{k,n}(N)$ be the number of solutions in positive integers $x_1,\ldots,x_n$ of the equation

\begin{equation}\label{war}x_1^n+\cdots+x_k^n=N,\end{equation}

where $N\geq 1$ is an integer. It is required to prove that there exists a number $k_0=k_0(n)$, where $k_0$ depends only on $n$, such that $J_{k,n}(N)\geq1$ if $k\geq k_0$. In other words, it is required to prove that any number $N\geq1$ can be represented by a sum of $n$-th powers of positive integers, the number of terms in this representation depending only on $n$. J.L. Lagrange (1770) solved this problem for $n=2$ by showing that any positive integer is the sum of four squares of integers. D. Hilbert (1909) was the first to give a general solution to Waring's problem. G.H. Hardy and J.E. Littlewood (1924) used their circle method to prove that for $J_{k,n}(N)$, if $k\geq n2^n+1$, an asymptotic formula of the form

\begin{equation}\label{hl} J_{k,n}(N)=AN^{k/n-1}+O(N^{k/n-1-\gamma})\end{equation}

is true, where $\gamma>0$ and $A=A(N)\geq c>0$; $c$ is an absolute constant. And since there are infinitely many numbers $N$ which, for $k=n$, are not the sum of $n$-th powers, i.e. $J_{k,n}(N)=0$, there arose the problem of establishing the true order of $k$, as a function of $n$, for which equation \ref{war} is solvable and formula \ref{hl} is valid. The strongest results on this problem were obtained by I.M. Vinogradov (1934) who showed that:

a) $J_{k,n}(N)\geq1$ for $N\geq N_0$ if $k\geq 3n\ln n+11n$;

b) formula \ref{hl} is true for $k\geq 4n^2\ln n$.

A second classical additive problem — the Goldbach–Euler problem (1742) — is as follows: Let $J(N)$ be the number of solutions in primes $p_1,p_2,p_3$ of the equation $p_1+p_2+p_3=N$; prove that for odd $N\geq7$, $J(N)\geq 1$. It was shown in 1937 by Vinogradov that (an asymptotic formula for $J(N)$):

$$J(N)=BN^2\ln^{-3}N+O(N^2\ln^{-3.5+\epsilon}N),$$

where $B=B(N)\geq0.6$. It follows, in particular, that $J(N)\geq1$ for $N\geq N_0$, i.e. a solution of the Goldbach–Euler problem for sufficiently large $N$.

Additive problems also include the Hardy–Littlewood problem (1923): Each $N\geq 2$ can be represented in the form $N=p+x^2+y^2$, where $p$ is a prime number and $x$ and $y$ are positive integers. Yu.V. Linnik proved in 1958 that if $W(N)$ is the number of solutions of this equation, the asymptotic formula

$$W(N)=\frac{\sigma N}{\ln N}+O(N\ln^{-1.028}N),$$

where $\sigma=\sigma(N)\geq c_1>0$ and $c_1$ is an absolute constant, is true. It follows that $W(N)\geq1$ if $N\geq N_0$, which is the solution of the Hardy–Littlewood problem for sufficiently large $N$. There are many additive problems which have remained unsolved for hundreds or even thousands of years. These include, for example, the problem on the infinite number of twin primes, i.e. pairs of primes $p$ and $q$ such that $\lvert p-q\rvert=2$, the binary problem of Goldbach–Euler, viz. that any even number $\geq 4$ is a sum of two primes; and the problem on the existence of an infinite number of primes in the sequence of the form $n^2+1$. See also Additive problems.

## Behaviour of number-theoretic functions

The theory of numbers comprises several classical functions: $\phi(n)$ — the number of numbers not exceeding $n$ and mutually prime with $n$ (the Euler function); $\tau(n)$ — the number of divisors of $n$; $\mu(n)$ — the Möbius function; $\Lambda(n)$ — the Mangoldt function, etc. Even though all these functions behave fairly "irregularly" , their average values can properly be studied. The average value of a function $f(n)$ is understood to mean the value of $\sum_{n\leq x}f(n)/x$. The problem of estimating the average value of $\mu(n)$ is equivalent to the problem of bounds on the zeros of the Riemann zeta-function. The problem of the asymptotic behaviour of the average value of $\Lambda(n)$ is equivalent to the problem of the asymptotic formula for $\pi(x)$, i.e. again to the problem of bounds on the zeros of the Riemann zeta-function. The results obtained on all these problems are the same as those obtained in the problem of the distribution of prime numbers. This does not apply to the problem of the asymptotic behaviour of the average value of $\tau(n)$ or, to put it in a somewhat different manner, the problem of the asymptotic formula for the sum of the values of $\tau(n)$. Let

$$\Phi(N)=\tau(1)+\cdots+\tau(N).$$

$\Phi(N)$ is then the number of integer points below the hyperbola $y=N/x$. Thus, to find the asymptotic behaviour of $\Phi(N)$ amounts to finding the asymptotic behaviour of the number of integer points in expanding domains. This class of problems also includes the problem of the integer points in a disc, i.e. the problem of determining the number

$$G(N)=\sum_{x^2+y^2\leq N}1,$$

where $x$ and $y$ are integers, and of extending these problems to arbitrary domains, both in a plane and in space. It was shown by P. Dirichlet in 1849 that

$$\Phi(N)=N\ln N+(2\gamma+1)N+R_1(N),$$

where $R_1(N)=O(\sqrt{N})$; it was also shown by C.F. Gauss in 1863 that

$$G(N)=\pi N+R_2(N),$$

where $R_2(N)=O(\sqrt{N})$. The problems of finding the best possible estimates for $R_1(N)$ and $R_2(N)$ are known as divisor problems and the circle problem, respectively. G.F. Voronoi (1903) obtained the formula

$$R_1(N)=O(N^{1/3}\ln N),$$

while the formula found by W. Sierpiński (1906) was

$$R_2(N)=O(N^{1/3}).$$

In addition, the $\Omega$-theorems:

$$R_1(N)=\Omega(N^{1/4})\quad\textrm{ and }\quad R_2(N)=\Omega(N^{1/4})$$

have also been demonstrated. The estimates of $R_1(N)$ and $R_2(N)$ obtained in our own days (1976) are somewhat better than those of Voronoi and Sierpiński.

A problem related to those just discussed is the asymptotic behaviour of the sum of the fractional parts of various types of functions or an equivalent problem, viz. the problem of the distribution of the fractional parts of various types of functions. Let $\{\alpha\}$ be the fractional part of the number $\alpha$. Then, if $F(x)$ is a real function, the problem concerns the asymptotic behaviour of the two functions

$$T_1(N)=\sum_{n\leq N}\{ F(n)\},$$

$$T_2(\gamma;N)=\sum_{\substack{0\leq \{F(n)\}\leq \gamma\\ n\leq N}}1.$$

If for any $0<\gamma\leq 1$

$$T_2(\gamma; N)=\gamma N+o(N),$$

one says that the fractional parts of $F(x)$ are uniformly distributed. The uniform distribution of the fractional parts of $F(n)$ can also be expressed in terms of the asymptotic behaviour of $T_1(N)$. The first results on the uniform distribution of the fractional parts of polynomials, and criteria for uniform distribution, were found by H. Weyl in 1916. The most accurate results in this field were obtained by Vinogradov, who also found asymptotic formulas for $T_1(N)$ and $T_2(N)$ in cases in which $n$ runs through a part of the set of integers not larger than $N$, in particular through the set of prime numbers. Not much is known about the distribution of the fractional parts of functions which grow faster than polynomials. For instance, nothing is known about the distribution of the fractional parts of the function $(3/2)^x$.

## Algebraic and transcendental numbers.

The theory of algebraic and transcendental numbers includes problems connected with the arithmetical nature of given numbers or classes of numbers. Consider polynomials with integer coefficients and with leading coefficient one; if $\alpha$ is a root of such a polynomial of degree $n$ and is not a root of a polynomial of a lower degree, it is said to be an algebraic number of degree $n$; if $n=1$, the number $\alpha$ is said to be rational. If, on the other hand, $\alpha$ is not an algebraic number, it is said to be transcendental. There are "much fewer" algebraic than transcendental numbers; "almost any" number is transcendental, but determining whether a specific number is transcendental or algebraic is very difficult. The principal "characteristic" of algebraic numbers is the fact that they are very "poorly" approximated to by rational numbers. This assertion (Liouville's theorem, cf. Liouville theorems, 1844) is formulated as follows: If $\alpha$ is an algebraic number of degree $n$, then

$$\left\lvert \alpha-\frac{p}{q}\right\rvert> cq^{-\kappa},$$

where $\kappa=n$, $c=c(\alpha)>0$ is a constant which depends only on $\alpha$, while $p$ and $q$ are arbitrary integers. The next decisive step in this problem was made by A. Thue (1909) whose ideas exerted a major influence on the theory of transcendental numbers. He showed that $\kappa=n/2+\epsilon$, $\epsilon>0$. Subsequently, the value of $\kappa$ was reduced by several workers, and it was shown by K.F. Roth in 1955 that $\kappa=2+\epsilon$ (it is known that $\kappa\geq 2$). A drawback of all these theorems (except for Liouville's theorem) consists in the fact that they are ineffective, i.e. $c$ cannot be computed from known $\alpha$ and $\epsilon$.

Approximation problems are connected with a certain class of problems in the theory of indefinite equations. E.g., Thue employed his approximation theorem to prove that the number of integral solutions of the equation $F_n(x,y)=a$, where $F_n(x,y)$ is a form with integral coefficients of degree $n\geq 3$ and $a$ is a non-zero integer, is finite (this theorem is also ineffective, i.e. no bound on the number of solutions of the equation can be given).

Another approach employed in this theory are transcendence proofs of numbers. The first results on this subject were obtained towards the end of the 19th century by Ch. Hermite (1873), who proved that the number $e$ is transcendental, and by F. Lindemann (1882), who proved that the number $\pi$ is transcendental and thus gave a negative solution to the problem of squaring the circle. According to the theorem of Gel'fond–Schneider (1934), $\alpha^\beta$ is a transcendental number if $\alpha$ is an algebraic number, $\alpha\neq0,1$ and $\beta$ is an algebraic number of degree $\geq 2$ (Hilbert's seventh problem). Beginning in 1967, A. Baker obtained a number of effective theorems on the estimation of linear forms in logarithms of algebraic numbers. As a result, Thue's theorem on the number of representations of an integer by a form was effectively demonstrated. There are still many unsolved problems in the theory of transcendental numbers; these include the transcendental nature of Euler's constant

$$\gamma=\lim_{n\to\infty}\left( \ln n-1-\frac{1}{2}-\cdots-\frac{1}{n}\right),$$

the problem of algebraic independence of the numbers $e$ and $\pi$, etc.

## Some methods used in analytic number theory

a) The method of complex integration. This method grew out of Euler's method of generating functions which is often used for the solution of problems in elementary mathematics. The method is based on the following formula (a discontinuous multiplier):

$$\frac{1}{2\pi i}\int_{\Re s=\sigma>0}\frac{x^s}{s}\,\mathrm{d}s=\begin{cases}1&\textrm{if }x>1,\\\frac{1}{2}&\textrm{if }x=1,\\0&\textrm{if }0<x<1,\end{cases}$$

where the integral is taken over the straight line $\Re s=\sigma>0$, $s=\sigma+it$. E.g., for $\Re s>1$,

$$f(s)=\frac{-\zeta'(s)}{\zeta(s)}=\sum_{n=1}^\infty\Lambda(n)n^{-s},$$

and for $x=N+1/2$ one obtains

$$\sum_{n\leq x}\Lambda(n)=\frac{1}{2\pi i}\int_{\Re s=2}\frac{x^sf(s)}{s}\,\mathrm{d}s.$$

The left-hand side of this equation is the Chebyshev function, finding the asymptotic behaviour of which is equivalent to the problem of prime numbers. The right-hand side, after the separation of the main factor, will be the smaller, the farther to the left the integration contour can be shifted. (Cf. Complex integration, method of.)

b) The circle method (of Hardy–Littlewood–Ramanujan). This method is used mostly in additive problems. Below the application and the nature of the circle method is considered in the example of applying Vinogradov's trigonometric sums to the ternary problem of Goldbach–Euler. Let $m$ be an integer. One then has (a discontinuous multiplier):

$$\int_0^1 e^{2\pi i\alpha m}\,\mathrm{d}\alpha=\begin{cases}1&\textrm{if }m=0,\\0&\textrm{if }m\neq 0.\end{cases}$$

Therefore

$$I(N)=\int_0^1 S^3(\alpha)e^{2\pi i\alpha N}\,\mathrm{d}\alpha,\quad S(\alpha)=\sum_{p\leq N}e^{\pi ixp},$$

and $I(N)$ is the number of solutions in primes of the equation $p_1+p_2+p_3=N$. The integration interval is then subdivided into two parts — the principal and the complementary interval; the principal interval contains all the intervals of the form

$$\left\lvert \alpha-\frac{a}{q}\right\rvert<\frac{1}{q^\tau},$$

where $(a,q)=1$, $0\leq a\leq q$, $q\leq \ln^{10}N$, $\tau=N\ln ^{-20}N$; all other intervals are within the complementary interval. The principal intervals do not intersect. Moreover, for $\alpha$ in the principal interval, the sum $S(\alpha)$ is "close" to the rational sum $S(a/q)$. However, for "small" $q$, $q\leq \ln N$, the distribution law of the prime numbers in a series with difference $q$ is known (e.g. Siegel's theorem), i.e. the asymptotic behaviour of the sums $S(a/q)$ is known. In this way the principal term of the problem is separated, which is the fundamental idea of the circle method. If one now makes a non-trivial estimate of $\lvert S(\alpha)\rvert$ on the complementary intervals (cf. Vinogradov method), the asymptotic formula in the Goldbach–Euler problem is obtained. (See also Circle method.)

c) The method of trigonometric sums. Most problems in analytic number theory can be expressed by trigonometric sums, i.e. finite sums of the form

\begin{equation}\label{exp} S=\sum_{x_1,\ldots,x_n}e^{2\pi i F(x_1,\ldots,x_n)},\end{equation}

where $F(x_1,\ldots,x_n)$ is a real function, while $x_1,\ldots,x_n$ run through a set of $P$ integers. Thus, the essence of many problems is the study of such sums, in particular the problem of finding the most accurate possible estimate of the modulus of such a sum. A trivial estimate of the sum (3) is $P$. The problem is to obtain an estimate of the form

$$\lvert S\rvert\leq\Delta P,$$

where $0\leq \Delta\leq 1$ is called the reducing factor. The first non-trivial estimates of trigonometric sums for the case when $F=F(x)$ is a polynomial, while $x=1,\ldots,P$, were obtained in 1919 by Weyl, who at the same time deduced a criterion for the uniform distribution of the fractional parts of functions in terms of trigonometric sums. The method of trigonometric sums was created by Vinogradov who, by utilizing intrinsic arithmetical properties of such sums, obtained very strong estimates of the modulus for a broad class of these sums. He was able to obtain in this way several fundamental results, close to the limit of the possible, in several problems of number theory (the Waring problem, the Hilbert–Kamke problem, and Weyl sums, cf. Weyl sum). Another consequence of Vinogradov's method (1937) was the solution of several additive problems on prime numbers, in particular the Euler–Goldbach problem. The fundamental idea in Vinogradov's method was "smoothing" (exponentiation of the trigonometric sum and reduction of the estimate to the theorem of averages for the estimation of Weyl sums, the introduction of double trigonometric sums for the estimation of sums of primes, etc.). (See also Trigonometric sums, method of.)

d) The dispersion method and the method of the large sieve. Linnik in 1958–1960 proposed a dispersion method for the solution of several additive problems in number theory. He solved the Hardy–Littlewood problem, the Titchmarsh problem on divisors and the additive divisor problem. The basic concept in the method is the dispersion of the number of solutions of a given auxiliary equation related to the principal equation (see also Dispersion method). Fundamental results were recently obtained by the method of the large sieve proposed by Linnik in 1940 for the solution of the problem of the smallest quadratic residue.

e) Methods in algebraic and transcendental number theory. In order to prove his theorem on the approximation of an algebraic number by a rational fraction, Thue (cf. Thue method) constructed the polynomial

$$f(x,y)=(y-\alpha)f_1(x,y)+(x-\alpha)^nf_2(x,\alpha)$$

with integer coefficients, where $f_1$ and $f_2$ are also polynomials. On the assumption that $\alpha$ is "well" approximated by fractions $p_1/q_1$ and $p_2/q_2$ with sufficiently large $q_1$ and $q_2$, putting $m\approx \ln q_1/\ln q_2$, and proving that $f(x,y)$ does not vanish if $x=p_1/q_1$, $y=p_2/q_2$, a contradiction is obtained.

A.O. Gel'fond's proof of the transcendental nature of numbers involves the function

$$f(z)=\sum_{k=0}^{q_0}\sum_{l=0}^q c_{k,l}e^{(\lambda k+l)z},\quad \lambda=\frac{\ln \alpha}{\ln \beta}.$$

On the assumption that $\alpha$ is an algebraic number and using Dirichlet's box principle, non-zero integers $c_{k,l}$ are chosen so that $f(z)$ and "many" of its derivatives have "many" zeros. A "large" number of zeros will yield "good" estimates from above for a "large" number of derivatives and points, whence, using the estimates from below obtained by Liouville's theorem, it follows that $f(z)$ and "many" of its derivatives have more zeros than before. A repetition of this process results either in $\lambda$ being a rational number or in zero values for $c_{k,l}$, which is in contradiction with their choice. See also Algebraic number; Transcendental number.

How to Cite This Entry:
Analytic number theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Analytic_number_theory&oldid=33836
This article was adapted from an original article by A.A. Karatsuba (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article