Prime number theorem
The prime number theorem allows the distribution of prime numbers to be estimated using logarithms . The connection between prime numbers and logarithms was already suspected by the 15-year-old Carl Friedrich Gauß in 1793 and independently of him by Adrien-Marie Legendre in 1798, but it was not proven until 1896 independently by Jacques Salomon Hadamard and Charles-Jean de La Vallée Poussin .
The prime number function
In the following, let the prime number function, which is defined for any real numbers , as the number of prime numbers that are not greater than . Formally one can write:
The symbol denotes the set of prime numbers, the notation stands for the number of elements in the set
The prime number theorem
The prime number theorem says:
If we call two real functions and are asymptotically equivalent , if the quotient for converges to 1, the prime number theorem can also be formulated as follows: The functions and are asymptotically equivalent.
The prime rate is substantially equivalent to the Riemann zeta function has no zeros with has.
There is a variety of analytical evidence. A simple proof that avoids estimating the zeta function at infinity according to Hadamard and La Vallée Poussin was given by Donald Newman . A third way within the analytic number theory uses the Taubers theorems of Wiener-Ikehara , also avoids the estimation in infinity, but uses deeper results from the theory of the Fourier transformation . There is also evidence without the use of complex function theory (“elementary” evidence according to Paul Erdős and Atle Selberg ).
Stronger forms of the prime number theorem
Better approximations than the integral logarithm delivers
The integral representation for is chosen because the antiderivatives of are not elementary .
The logarithm of integral is asymptotically equivalent to therefore also to
One can show:
with a positive constant . There is a Landau symbol , i. i.e., there is a constant such that
applies to all . The improvement in the error term depends on showing that the zeta function is zero-point free in ever larger areas in the critical strip. Assuming the Riemann Hypothesis (according to which all non-trivial zeros lie on the straight line ), and only below this, one can estimate the error
improve ( Helge von Koch 1901). Lowell Schoenfeld found a non-asymptotic limit assuming the Riemann conjecture:
- .
history
Adrien-Marie Legendre was the first to publish in his Théorie des nombres ( Treatise on Number Theory ) in 1798, independently of Gauss, the assumed relationship between prime numbers and logarithms. In the second edition of this work in 1808 he improved the estimate from about the same
(where this value 1.08366 is responsible for the problem of the existence of the Legendre constant ). A first step towards a proof was taken by Pafnuti Lwowitsch Chebyshev , who in 1851 showed the following weaker form of the prime number theorem:
for all sufficiently large . This means that the number of prime numbers under a given size does not deviate from the logarithmic function by more than approximately 10% upwards or downwards .
The English mathematician James Joseph Sylvester , then a professor at the American Johns Hopkins University in Baltimore , refined Chebyshev's method in 1892 and showed that for the inequality if the inequality was sufficiently large, the lower limit 0.95695 and the upper limit 1.04423, i.e. the deviation a maximum of only about 5%.
In his famous work on the number of prime numbers below a given quantity (1859), Bernhard Riemann showed the relationship between the distribution of prime numbers and the properties of the Riemann zeta function . In 1895, the German mathematician Hans von Mangoldt proved the main result of Riemann's work that the prime number theorem is equivalent to the theorem that the Riemann zeta function has no zeros with real part 1. Both Hadamard and de la Vallée Poussin proved the non-existence of such zeros in 1896. Your proofs of the prime number theorem are therefore not "elementary", but use methods of function theory . For many years an elementary proof of the prime number theorem was considered impossible, which was refuted in 1949 by the proofs found by Atle Selberg and Paul Erdős (whereby “elementary” here by no means means “simple”). Numerous variants and simplifications of this proof were found later.
Numerical examples
The following table shows concrete values of the prime number function in comparison with the logarithms, Legendre's formula and the integral logarithm.
10 | 4th | 0.400000 | 4th | 0 | 0.921034 | 8th | 6th | 2 |
10 2 | 25th | 0.250000 | 22nd | 3 | 1.151293 | 28 | 30th | 5 |
10 3 | 168 | 0.168000 | 145 | 23 | 1.160503 | 172 | 178 | 10 |
10 4 | 1,229 | 0.122900 | 1,086 | 143 | 1.131951 | 1,231 | 1,246 | 17th |
10 5 | 9,592 | 0.095920 | 8,686 | 906 | 1.104320 | 9,588 | 9,630 | 38 |
10 6 | 78,498 | 0.078498 | 72,382 | 6.116 | 1.084490 | 78,543 | 78,628 | 130 |
10 7 | 664.579 | 0.066458 | 620.421 | 44,158 | 1.071175 | 665.140 | 664.918 | 339 |
10 8 | 5,761,455 | 0.057615 | 5,428,681 | 332,774 | 1.061299 | 5,768,004 | 5,762,209 | 754 |
10 9 | 50,847,534 | 0.050848 | 48.254.942 | 2,592,592 | 1.053727 | 50,917,519 | 50.849.235 | 1,701 |
10 10 | 455.052.511 | 0.045505 | 434.294.482 | 20,758,029 | 1.047797 | 455.743.004 | 455.055.615 | 3,104 |
10 11 | 4,118,054,813 | 0.041181 | 3,948,131,654 | 169.923.159 | 1.043039 | 4,124,599,869 | 4,118,066,401 | 11,588 |
10 12 | 37.607.912.018 | 0.037608 | 36.191.206.825 | 1.416.705.193 | 1.039145 | 37,668,527,415 | 37.607.950.281 | 38,263 |
10 13 | 346.065.536.839 | 0.034607 | 334.072.678.387 | 11,992,858,452 | 1.035899 | 346,621,096,885 | 346.065.645.810 | 108,971 |
10 14 | 3,204,941,750,802 | 0.032049 | 3.102.103.442.166 | 102.838.308.636 | 1.033151 | 3.210.012.022.164 | 3,204,942,065,692 | 314,890 |
10 15 | 29,844,570,422,669 | 0.029845 | 28,952,965,460,217 | 891,604,962,452 | 1.030795 | 29,890,794,226,982 | 29,844,571,475,288 | 1,052,619 |
10 16 | 279.238.341.033.925 | 0.027924 | 271.434.051.189.532 | 7,804,289,844,393 | 1.028752 | 279.660.033.612.131 | 279.238.344.248.557 | 3,214,632 |
10 17 | 2,623,557,157,654,233 | 0.026236 | 2,554,673,422,960,305 | 68,883,734,693,281 | 1.026964 | 2,627,410,589,445,923 | 2,623,557,165,610,822 | 7,956,589 |
10 18 | 24,739,954,287,740,860 | 0.024740 | 24,127,471,216,847,324 | 612,483,070,893,536 | 1.025385 | 24,775,244,142,175,635 | 24,739,954,309,690,415 | 21,949,555 |
10 19 | 234.057.667.276.344.607 | 0.023406 | 228.576.043.106.974.646 | 5,481,624,169,369,960 | 1.023982 | 234,381,646,366,460,804 | 234.057.667.376.222.382 | 99.877.775 |
10 20 | 2,220,819,602,560,918,840 | 0.022208 | 2,171,472,409,516,259,138 | 49.347.193.044.659.701 | 1.022725 | 2,223,801,523,570,829,204 | 2,220,819,602,783,663,484 | 222,744,644 |
10 21 | 21,127,269,486,018,731,928 | 0.021127 | 20,680,689,614,440,563,221 | 446.579.871.578.168.707 | 1.021594 | 21,154,786,057,670,023,133 | 21,127,269,486,616,126,182 | 597.394.254 |
10 22 | 201,467,286,689,315,906,290 | 0.020147 | 197,406,582,683,296,285,296 | 4.060.704.006.019.620.994 | 1.020570 | 201,721,849,105,666,574,218 | 201,467,286,691,248,261,498 | 1,932,355,208 |
10 23 | 1,925,320,391,606,803,968,923 | 0.019253 | 1,888,236,877,840,225,337,614 | 37,083,513,766,578,631,309 | 1.019639 | 1,927,681,221,597,738,628,080 | 1,925,320,391,614,054,155,139 | 7.250.186.216 |
10 24 | 18,435,599,767,349,200,867,866 | 0.018436 | 18,095,603,412,635,492,818,797 | 339.996.354.713.708.049.069 | 1.018789 | 18,457,546,327,619,878,007,916 | 18,435,599,767,366,347,775,144 | 17.146.907.278 |
10 25 | 176.846.309.399.143.769.411.680 | 0.017685 | 173.717.792.761.300.731.060.452 | 3,128,516,637,843,038,351,228 | 1.018009 | 177.050.792.039.110.236.839.710 | 176.846.309.399.198.930.392.619 | 55.160.980.939 |
10 26 | 1,699,246,750,872,437,141,327,603 | 0.016992 | 1,670,363,391,935,583,952,504,342 | 28,883,358,936,853,188,823,261 | 1.017292 | 1.701.156.120.834.278.630.173.694 | 1,699,246,750,872,593,033,005,724 | 155.891.678.121 |
10 27 | 16,352,460,426,841,680,446,427,399 | 0.016352 | 16,084,980,811,231,549,172,264,034 | 267,479,615,610,131,274,163,365 | 1.016629 | 16,370,326,243,373,272,895,062,280 | 16,352,460,426,842,189,113,085,405 | 508.666.658.006 |
OEIS | Follow A006880 in OEIS | Follow A057834 in OEIS | Follow A057835 in OEIS | Follow A058289 in OEIS | Follow A057754 in OEIS | Follow A057752 in OEIS |
The size is called the prime number density.
If you compare with the values of in the table, it seems as if it always applies. In fact, the difference changes in becomes greater the sign infinitely many times as JE Littlewood showed 1914th The Gaussian formula underestimates the number of prime numbers in a sufficiently large number range, which Stanley Skewes was able to estimate upwards in 1933 with the Skewes number named after him . Russell Sherman Lehman made an important sentence about the upper limit in 1966 and was able to push it down to a "manageable" size of 1.165 · 10 1165 . Using Lehman's theorem, the Dutch mathematician Herman te Riele was able to show in 1986 that between 6.627 · 10 370 and 6.687 · 10 370 there are more than 10 180 consecutive numbers for which applies. The currently best lowest value, also based on Lehman's results, was determined in 2000 by the mathematicians Carter Bays and Richard Hudson, who showed that such a change, as proven by Littlewood, occurs before 1.398244 · 10 316 . Although they couldn't prove it, their calculations suggest that they actually found the first sign change. More specifically, it suggests that the inequality for true always.
Explicit formulas for the prime number function
Formulas for prime functions come in two types: arithmetic formulas and analytic formulas. Analytical formulas for prime counting were the first to be used to prove the prime number theorem. They come from the work of Bernhard Riemann and Hans von Mangoldt and are generally known as explicit formulas.
We have the following expression for :
in which
and the second Chebyshev function . Here the zeros of the Riemann zeta function are in the critical strip where the real part of lies between zero and one. The formula applies to values greater than one, i.e. H. the region of interest. The sum over the roots is conditionally convergent and should be taken in the order of increasing absolute values of the imaginary part. It should be noted that the same sum over the trivial roots results in the last subtrahend in the formula.
Similar to for , an averaging at the jump points can also be introduced for the function that counts prime numbers, introduced by Riemann . For we have the more complicated formula
Here, too, the formula applies again for , while the non-trivial zeros of the Riemann zeta function are ordered according to their absolute value, and the latter integral, again taken with a minus sign, is exactly the same sum, but above the trivial zeros. The first term is the usual logarithmic integral function; the expression in the second term should be viewed as being the analytic continuation of the exponential integral function from the positive real to the complex plane with the branch cut along the negative real axis.
Thus, if one introduces an averaging function at the jump points as above with the Möbius inversion formula
valid for , where
is the so-called Riemann R-function. The latter series for this is known as the Gram series and converges for all positives .
The sum over nontrivial zeros of the zeta function in the formula for describes the fluctuations of , while the remaining terms make up the "smooth" part of the prime number function.
So you can
describe as the best fit for .
The amplitude of the "noisy" part is heuristically approx. , With which the fluctuations in the prime number distribution can be represented with the function:
A comprehensive table with the values of is available.
Statement about the sequence of prime numbers
The prime number theorem also provides information about the ascending order of the prime numbers. So it is equivalent to the statement
and it even applies to everyone
Prime number theorem for arithmetic progressions, Siegel-Walfisz theorem
Let the number of prime numbers be less than or equal in the arithmetic progression , where are coprim ( ). Peter Gustav Lejeune Dirichlet (see Dirichletscher Prime Number Theorem ) and Adrien-Marie Legendre suspected that asymptotic
with the Euler Phi function (the number to be relatively prime numbers less than ). This was proved by Charles-Jean de La Vallée Poussin using methods similar to those used for proving the prime number theorem.
As an example, this can be applied to the distribution of prime numbers to their final digits in the decimal system (this applies analogously to every base). Only the digits 1, 3, 7, 9 come into consideration (except for the prime numbers 5 and 2 themselves) and from the prime number theorem for arithmetic progressions it follows that the prime numbers are evenly distributed among their final digits. There are, however, some imbalances that are the subject of research. In numerical terms there are usually more prime numbers of the form than below a certain limit, although the prime numbers are asymptotically distributed equally across both classes ( Chebyshev's bias , also prime number race , after Pafnuti Lwowitsch Chebyshev ). According to John Edensor Littlewood , the sign changes infinitely often. Similar phenomena exist when considering other congruences than such mod . As K. Soundararajan and Oliver found in 2016, there are also deviations from the uniform distribution when looking at the distribution of the end digits for consecutive prime numbers.
The distribution in arithmetic progressions was examined more precisely by Arnold Walfisz in Siegel and Walfisz's theorem (based on a result by Carl Ludwig Siegel ). The theorem provides an asymptotic error term for the above formula. There is a constant and any number with .
Originally the phrase used by Siegel and Walfisz for the function
formulated with the Mangoldt function . With the notations already introduced (as well as as above , ) the theorem then says that there is a constant for every N such that:
The theorem is not effective because it says nothing about the size of the constant . The theorem of Bombieri and Winogradow (and the conjecture of Elliott and Halberstam ) give more precise statements about the error term in Dirichlet's prime number theorem for arithmetic progressions .
literature
- E. Freitag, R. Busam: Function theory. 3. Edition. Springer-Verlag, Berlin 2000. ISBN 3-540-67641-4 .
- GH Hardy , EM Wright: An Introduction to the Theory of Numbers. 5th edition, Oxford University Press, Oxford 1979. ISBN 0-19-853171-0 .
- Peter Bundschuh : Introduction to Number Theory , Springer 2008 (with proof from Newman)
Web links
- Chris K. Caldwell: How many primes are there? (English)
- Eric W. Weisstein : Prime Number Theorem . In: MathWorld (English).
Individual evidence
- ^ Donald J. Newman: Analytic Number Theory . Springer, 1998. Newman: Simple Analytic Proof of the Prime Number Theorem . In: American Mathematical Monthly , Volume 87, 1980, pp. 693-696
- ↑ On Newman's proof also: J. Korevaar: On Newman's quick way to the prime number theorem . In: Mathematical Intelligencer , Volume 4, 1982, No. 3. Don Zagier: Newman's Short Proof of the Prime Number Theorem . In: American Mathematical Monthly , Volume 104, 1997, pp. 705-708. The proof is also presented in Bundschuh: Introduction to Number Theory . Springer, 2008. Newman: Analytic Number Theory . Springer, 1998.
- ^ Arnold Walfisz , Weylsche exponential sums in the newer number theory, VEB Deutscher Verlag der Wissenschaften 1963, p. 187. The proof in Walfisz comes from Hans-Egon Richert . Derbyshire, Prime Obsession, Joseph Henry Press 2003, p. 244, calls this the best known estimate of the error term.
- ↑ L. Schoenfeld, Sharper Bounds for the Chebyshev Functions θ (x) and ψ (x). II, Mathematics of Computation, Volume 30, 1976, pp. 337-360
- ↑ He had dealt with the subject in 1792 or 1793, see the letter from 1849 to Johann Franz Encke , Textarchiv - Internet Archive . There he also discusses the Legendre constant and the integral logarithm.
- ^ Adrien-Marie Legendre: D'une loi très-remarquable observée dans l'énumération des nombres premiers . In: Théorie des nombres . 3. Edition. Didot, Paris 1830, Volume 2, pp. 65–70, Textarchiv - Internet Archive
- ↑ Pafnuti Lwowitsch Tschebyshev: Sur la fonction qui détermine la totalité des nombres premiers inférieurs à une limite donnée. In: Mémoires présentés à l'Académie Impériale des sciences de St.-Pétersbourg par divers savants , 6, 1851, pp. 141–157. Also in: Journal de mathématiques pures et appliquées , 1. F., 17, 1852, pp. 341–365. Reprinted in Andrej Andrejewitsch Markoff, Nikolai Jakowlewitsch Sonin (ed.): Œuvres de PL Tchebychef . Volume 1. Academy, St. Petersburg 1898, pp. 27-48, Textarchiv - Internet Archive .
- ↑ Don Zagier , The first 50 million prime numbers , elements of mathematics (supplements to the journal), Volume 15 (1977), pp. 15 f., Doi: 10.5169 / seals-10209 (freely accessible .) Gives a significantly simplified proof of a weaker estimate )
- ↑ James Joseph Sylvester: On arithmetical series. In: Messenger of Mathematics , 21, 1892, pp. 1-19, 87-120. Reprinted in Henry Frederick Baker (Ed.): The Collected Mathematical Papers of James Joseph Sylvester . 4 volumes. University Press, Cambridge 1904-1912, Volume 4. 1912, pp. 687-731, archive.org .
- ↑ Bernhard Riemann: About the number of prime numbers under a given size. In: Monthly reports of the Royal Prussian Academy of Sciences in Berlin , 1859, pp. 671–680. See also Wilhelm Scheibner: About the number of prime numbers under any limit. In: Archive of Mathematics and Physics , 5, 1860, pp. 233-252.
- ↑ Hans von Mangoldt: On Riemann's treatise "About the number of prime numbers under a given size" . In: Journal for pure and applied mathematics , 114, 1895, pp. 255–305.
- ^ Jacques Hadamard: Sur la distribution des zéros de la fonction ζ (s) et ses conséquences arithmétiques. (PDF; 1.3 MB). In: Bulletin de la Société Mathématique de France , 24, 1896, pp. 199-220.
- ^ Charles de La Vallée Poussin: Recherches analytiques de la théorie des nombres premiers. In: Annales de la Société Scientifique de Bruxelles 20 B (1896), pp. 183-256, 281-352, 363-397; 21 B (1897), pp. 351-368.
- ↑ Shorter versions of the evidence by Hadamard, De la Vallée-Poussin are in EC Titchmarsh: The Theory of the Riemann Zeta-Function . Clarendon Press, 1951, 1986, Chapter 3
- ^ Atle Selberg: An elementary proof of the prime-number theorem. In: Annals of Mathematics , 50, 1949, No. 2, pp. 305-313.
- ↑ Paul Erdős: On a new method in elementary number theory which leads to an elementary proof of the prime number theorem. (PDF; 687 kB). In: Proceedings of the National Academy of Sciences of the United States of America , 35, 1949, pp. 374-384.
- ↑ The elementary proof according to Erdös and Selberg is also presented in a modified form in Hardy, Wright, Introduction to the theory of numbers, Oxford 1975
- ↑ The values for π (x) are from Chris K. Caldwell: How Many Primes Are There? Prime Pages, accessed December 12, 2015 .
- ↑ The value for π (10 26 ) is from DB Staple: The combinatorial algorithm for computing pi (x). Dalhousie University, accessed December 12, 2015 .
- ↑ The value for π (10 27 ) is from Kim Walisch: New confirmed pi (10 ^ 27) prime counting function record. mersenneforum.org, accessed on December 1, 2016 (English).
- ^ John E. Littlewood: Sur la distribution des nombres premiers. In: Comptes Rendus de l ' Académie des Sciences 158 (1914), pp. 1869-1872.
- ^ Stanley Skewes: On the difference . In: Journal of the London Mathematical Society 8 (1933), pp. 277-283; On the difference (II). In: Proceedings of the London Mathematical Society 5 (1955), pp. 48-70.
- ^ Russell Sherman Lehman: On the difference π (x) - li (x). (PDF; 2.6 MB). In: Acta Arithmetica 11 (1966), pp. 397-410.
- ^ Herman JJ te Riele: On the Sign of the Difference π (x) - li (x). (PDF; 550 kB). In: Mathematics of Computation , 48, 1987, pp. 323-328. See Chris K. Caldwell: How many primes are there? Cape. 3, History of the Prime Number Theorem.
- ↑ Carter Bays, Richard H. Hudson: A new bound for the smallest x with π (x)> li (x). (PDF; 422 kB). In: Mathematics of Computation , 69, 2000, No. 231, pp. 1285-1296.
- ^ EC Titchmarsh: The Theory of Functions, 2nd ed . Oxford University Press, 1960.
- ↑ See Riemann Hypothesis or Riemann Prime Counting Function , Mathworld
- ↑ Hans Riesel , Gunnar Göhl: Some calculations related to Riemann's prime number formula . In: American Mathematical Society (Ed.): Mathematics of Computation . 24, No. 112, 1970, ISSN 0025-5718 , pp. 969-983. doi : 10.2307 / 2004630 .
- ↑ Eric W. Weisstein : Riemann Prime Counting Function . In: MathWorld (English).
- ↑ Eric W. Weisstein : Gram Series . In: MathWorld (English).
- ^ The encoding of the prime distribution by the zeta zeros . Matthew Watkins. Retrieved September 14, 2008.
- ↑ Values of π ( x ) and Δ ( x ) for various values of x . . Andrey V. Kulsha. Retrieved September 14, 2008.
- ^ Pierre Dusart: The k-th prime is greater than for . In: Mathematics of Computation . 68, No. 225, 1999, pp. 411-415. doi : 10.1090 / S0025-5718-99-01037-6 .
- ↑ Chebyshev's Bias, mathworld
- ^ Walfisz, On additive number theory II, Mathematische Zeitschrift, Volume 40, 1936, pp. 592–607
- ↑ On the Siegel-Walfisz theorem, see also Harold Davenport : Multiplicative Number Theory . 2nd Edition. Springer, 1980, p. 133, Terry Tao, Notes Complex Analytic Multiplicative Number Theory (exercise 64)
- ↑ Seal: About the class number of square number fields . In: Acta Arithmetica , Volume 1, 1935, pp. 83-86