Namespaces
Variants
Actions

Analytic number theory

From Encyclopedia of Mathematics
Revision as of 10:21, 22 April 2012 by TBloom (talk | contribs) (Finished TeX!)
Jump to: navigation, search

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

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-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}'"`UNIQ-MathJax26-QINU`"' f(s)=\frac{-\zeta'(s)}{\zeta(s)}=\sum_{n=1}^\infty\Lambda(n)n^{-s},'"`UNIQ-MathJax27-QINU`"' \sum_{n\leq x}\Lambda(n)=\frac{1}{2\pi i}\int_{\Re s=2}\frac{x^sf(s)}{s}\,\mathrm{d}s.'"`UNIQ-MathJax28-QINU`"'\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}'"`UNIQ-MathJax29-QINU`"' 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},'"`UNIQ-MathJax30-QINU`"'\left\lvert \alpha-\frac{a}{q}\right\rvert<\frac{1}{q^\tau},'"`UNIQ-MathJax31-QINU`"'\lvert S\rvert\leq\Delta P,'"`UNIQ-MathJax32-QINU`"' f(x,y)=(y-\alpha)f_1(x,y)+(x-\alpha)^nf_2(x,\alpha)'"`UNIQ-MathJax33-QINU`"' 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|Algebraic number]]; [[Transcendental number|Transcendental number]]. ===='"`UNIQ--h-5--QINU`"'References==== <table><tr><td valign="top">[1]</td> <td valign="top"> I.M. Vinogradov, , ''Selected works'' , Springer (1985) (Translated from Russian)</td></tr><tr><td valign="top">[2]</td> <td valign="top"> I.M. Vinogradov, "Elements of number theory" , Dover, reprint (1954) (Translated from Russian)</td></tr><tr><td valign="top">[3]</td> <td valign="top"> I.M. Vinogradov, "The method of trigonometric sums in the theory of numbers" , Interscience (1954) (Translated from Russian)</td></tr><tr><td valign="top">[4]</td> <td valign="top"> A.O. Gel'fond, "Transcendental and algebraic numbers" , Dover, reprint (1960) (Translated from Russian)</td></tr><tr><td valign="top">[5]</td> <td valign="top"> B.N. Delone, "The Peterburg school of number theory" , Moscow-Leningrad (1947) (In Russian)</td></tr><tr><td valign="top">[6]</td> <td valign="top"> A.A. Karatsuba, "Fundamentals of analytic number theory" , Moscow (1975) (In Russian)</td></tr><tr><td valign="top">[7]</td> <td valign="top"> Yu.V. Linnik, "The dispersion method in binary additive problems" , Amer. Math. Soc. (1963) (Translated from Russian)</td></tr><tr><td valign="top">[8]</td> <td valign="top"> N.G. Chudakov, "Introductions to the theory of Dirichlet $L$-functions" , Moscow-Leningrad (1947) (In Russian)</td></tr><tr><td valign="top">[9]</td> <td valign="top"> K. Prachar, "Primzahlverteilung" , Springer (1957)</td></tr><tr><td valign="top">[10]</td> <td valign="top"> H. Davenport, "Multiplicative number theory" , Springer (1980)</td></tr><tr><td valign="top">[11]</td> <td valign="top"> E.C. Titchmarsh, "The theory of the Riemann zeta-function" , Clarendon Press (1951)</td></tr><tr><td valign="top">[12]</td> <td valign="top"> L.-K. Hua, "Abschätzungen von Exponentialsummen und ihre Anwendung in der Zahlentheorie" , ''Enzyklopaedie der Mathematischen Wissenschaften mit Einschluss ihrer Anwendungen'' , '''1''' : 2 (1959) (Heft 13, Teil 1)</td></tr><tr><td valign="top">[13]</td> <td valign="top"> A. Baker, "Linear forms in the logarithms of algebraic numbers (II)" ''Mathematika'' , '''14''' (1967) pp. 102–107</td></tr><tr><td valign="top">[14]</td> <td valign="top"> A.I. Vinogradov, "The density hypothesis for Dirichlet $L$-series" Izv. Akad. Nauk SSSR Ser. Mat. , 29 : 4 (1965) pp. 903–924 (In Russian)[15] E. Bombieri, "On the large sieve" Mathematika , 12 (1965) pp. 201–225


Comments

Liouville's theorem is closely related with the theory of continued fractions (cf. Continued fraction).

For a description of various results obtained on additive problems and the distribution of prime numbers in arithmetic progressions see Large sieve; Distribution of prime numbers; Sieve method.

References

[a1] R.C. Vaughan, "The Hardy–Littlewood method" , Cambridge Univ. Press (1981)
[a2] H.E. Richert, "Sieve methods" , Acad. Press (1974)
[a3] A. Ivić, "The Riemann zeta-function" , Wiley (1985)
How to Cite This Entry:
Analytic number theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Analytic_number_theory&oldid=25030
This article was adapted from an original article by A.A. Karatsuba (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article