Prime Number Theorem: Difference between revisions
imported>Michael Hardy (redirect) |
imported>Greg Martin (created page with material formerly from Prime number) |
||
| Line 1: | Line 1: | ||
The list of prime numbers suggests that they thin out the further you go: 44% of the one-digit numbers are prime, but only 23% of the two-digit numbers and 16% of the three-digit numbers. The trial division method explained above provides an intuitive explanation. To test whether a number <math>n</math> is prime, you have to try whether it can be divided by all numbers between 2 and <math>\sqrt n</math>. Large numbers have to undergo more tests, so fewer of them will be prime. | |||
The Prime Number Theorem explains how fast the prime numbers thin out. It says that if you are looking around the number <math>n</math>, about one in every <math>\log n</math> numbers is prime (here, <math>\log n</math> denotes the [[natural logarithm]] of <math>n</math>). The formal statement of the Prime Number Theorem is | |||
:<math>\lim_{x\to\infty} \frac{\pi(x) \log x}{x} = 1</math> | |||
where <math>\pi(x)</math> denotes the number of primes <math>\le x</math>. This result was demonstrated independently by [[Jacques Hadamard]] and [[Charles de la Vallée Poussin]] in 1896. An essential part of their proof is the function | |||
:<math>\zeta(s) = \sum_{n = 1}^{\infty} \frac{1}{n^s}. </math> | |||
This function was already considered by the 18th century Swiss mathematician [[Leonhard Euler]], who realized that | |||
:<math> \sum_{n = 1}^{\infty} \frac{1}{n^s} = \prod_{p \in \mathbb{P}} \frac{1}{1 - p^{-s}}, </math> | |||
where the product on the right goes over all prime numbers: | |||
:<math> \prod_{p \in \mathbb{P}} \frac{1}{1 - p^{-s}} = \frac{1}{1-2^{-s}} \, \frac{1}{1-3^{-s}} \, \frac{1}{1-5^{-s}} \, \frac{1}{1-7^{-s}} \cdots </math> | |||
To see why this is so, we use the formula for the sum of a [[geometric series]] to write the product as | |||
:<math> \left( 1 + \frac1{2^s} + \frac1{2^{2s}} + \frac1{2^{3s}} + \cdots \right) \left( 1 + \frac1{3^s} + \frac1{3^{2s}} + \frac1{3^{3s}} + \cdots \right) \left( 1 + \frac1{5^s} + \frac1{5^{2s}} + \frac1{5^{3s}} + \cdots \right) \cdots .</math> | |||
Multiplying out this product, we get a sum of terms of the form | |||
:<math> \frac{1}{(p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k})^s}, </math> | |||
where <math>p_1</math>, ..., <math>p_k</math> are prime numbers and <math>a_1</math>, ..., <math>a_k</math> are positive integers. Euler's formula equating the sum and the product now follows from the fact that every number has a [[unique factorization]] into primes. This also indicates the connection between the function <math>\zeta</math> and the prime numbers. | |||
Euler used his formula to give an alternative proof that there are infinitely many primes. If we take <math>s=1</math>, we get | |||
:<math> \sum_{n = 1}^{\infty} \frac{1}{n} = \prod_{p \in \mathbb{P}} \frac{1}{1 - \frac1p}. </math> | |||
The sum on the left is the [[harmonic series]], which diverges. If the number of primes were finite, then the product would evaluate to a finite number. This contradiction shows that there are infinitely many primes. | |||
The above definition for the function <math>\zeta</math> only works when <math>s > 1</math>, because the infinite sum diverges otherwise, but a technique called [[analytic continuation]] can be used to extend the definition to all values of <math>s</math>, including [[complex number]]s. The function with the extended domain is known as the [[Riemann zeta function]]. Hadamard and de la Vallée Poussin proved that this function cannot be zero in certain parts of the complex plane and used this to establish the prime number theorem. A proof not relying on [[complex analysis]] proved elusive, even though weaker results on the distribution of prime numbers have long been known<ref>Ribenboim, ''Introduction to Analytic Number theory''</ref><ref>Scharlau and Opolka, ''From Fermat to Minkowski''</ref>. It was only in 1949 that [[Atle Selberg]] and [[Paul Erdős]] were able to establish the theorem by elementary means. | |||
The location of the values <math>s</math> for which <math>\zeta</math>(<math>s</math>) is zero is one of the biggest mysteries in contemporary mathematics. The [[Riemann hypothesis]] states all the zeros of the Riemann zeta function lie on two lines in the complex plane. A proof of the Riemann hypothesis would lead immediately to more precise estimates on how fast the function <math>\pi(n)</math> grows. | |||
Revision as of 21:05, 29 April 2007
The list of prime numbers suggests that they thin out the further you go: 44% of the one-digit numbers are prime, but only 23% of the two-digit numbers and 16% of the three-digit numbers. The trial division method explained above provides an intuitive explanation. To test whether a number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is prime, you have to try whether it can be divided by all numbers between 2 and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt n} . Large numbers have to undergo more tests, so fewer of them will be prime.
The Prime Number Theorem explains how fast the prime numbers thin out. It says that if you are looking around the number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , about one in every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log n} numbers is prime (here, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log n} denotes the natural logarithm of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} ). The formal statement of the Prime Number Theorem is
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lim_{x\to\infty} \frac{\pi(x) \log x}{x} = 1}
where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi(x)} denotes the number of primes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \le x} . This result was demonstrated independently by Jacques Hadamard and Charles de la Vallée Poussin in 1896. An essential part of their proof is the function
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \zeta(s) = \sum_{n = 1}^{\infty} \frac{1}{n^s}. }
This function was already considered by the 18th century Swiss mathematician Leonhard Euler, who realized that
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{n = 1}^{\infty} \frac{1}{n^s} = \prod_{p \in \mathbb{P}} \frac{1}{1 - p^{-s}}, }
where the product on the right goes over all prime numbers:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \prod_{p \in \mathbb{P}} \frac{1}{1 - p^{-s}} = \frac{1}{1-2^{-s}} \, \frac{1}{1-3^{-s}} \, \frac{1}{1-5^{-s}} \, \frac{1}{1-7^{-s}} \cdots }
To see why this is so, we use the formula for the sum of a geometric series to write the product as
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( 1 + \frac1{2^s} + \frac1{2^{2s}} + \frac1{2^{3s}} + \cdots \right) \left( 1 + \frac1{3^s} + \frac1{3^{2s}} + \frac1{3^{3s}} + \cdots \right) \left( 1 + \frac1{5^s} + \frac1{5^{2s}} + \frac1{5^{3s}} + \cdots \right) \cdots .}
Multiplying out this product, we get a sum of terms of the form
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{(p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k})^s}, }
where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_1} , ..., Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_k} are prime numbers and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1} , ..., Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_k} are positive integers. Euler's formula equating the sum and the product now follows from the fact that every number has a unique factorization into primes. This also indicates the connection between the function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \zeta} and the prime numbers.
Euler used his formula to give an alternative proof that there are infinitely many primes. If we take Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s=1} , we get
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{n = 1}^{\infty} \frac{1}{n} = \prod_{p \in \mathbb{P}} \frac{1}{1 - \frac1p}. }
The sum on the left is the harmonic series, which diverges. If the number of primes were finite, then the product would evaluate to a finite number. This contradiction shows that there are infinitely many primes.
The above definition for the function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \zeta} only works when Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s > 1} , because the infinite sum diverges otherwise, but a technique called analytic continuation can be used to extend the definition to all values of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} , including complex numbers. The function with the extended domain is known as the Riemann zeta function. Hadamard and de la Vallée Poussin proved that this function cannot be zero in certain parts of the complex plane and used this to establish the prime number theorem. A proof not relying on complex analysis proved elusive, even though weaker results on the distribution of prime numbers have long been known[1][2]. It was only in 1949 that Atle Selberg and Paul Erdős were able to establish the theorem by elementary means.
The location of the values Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} for which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \zeta} (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} ) is zero is one of the biggest mysteries in contemporary mathematics. The Riemann hypothesis states all the zeros of the Riemann zeta function lie on two lines in the complex plane. A proof of the Riemann hypothesis would lead immediately to more precise estimates on how fast the function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi(n)} grows.