Prime number theorem

In mathematics, the prime number theorem (PNT) helps us understand how prime numbers are spread out among all the whole numbers. It tells us that as numbers get bigger, prime numbers become rarer, and it shows exactly how much rarer they get. This important idea was proven in 1896 by two mathematicians, Jacques Hadamard and Charles Jean de la Vallée Poussin, using work started by Bernhard Riemann.

The theorem says that for very large numbers, the chance that a random number is prime is about one divided by the natural logarithm of that number. This means the space between prime numbers grows slowly as numbers get bigger. For example, among numbers with up to 1000 digits, about one in 2300 is prime, while among numbers with up to 2000 digits, about one in 4600 is prime. This helps mathematicians predict where prime numbers might be found, even for very large numbers.

Statement

Imagine you are counting how many prime numbers there are up to a certain number. For example, up to the number 10, there are 4 prime numbers: 2, 3, 5, and 7. The prime number theorem tells us that as numbers get really big, the number of primes up to that point can be approximated by dividing the number by its natural logarithm.

This means that for very large numbers, the number of primes is roughly the number itself divided by how many times you need to multiply it by e (about 2.718) to reach it. The theorem was proven in 1896 by two mathematicians, using ideas from another mathematician about a special math function.

History of the proof of the asymptotic law of prime numbers

People have long wondered how often prime numbers appear as numbers get bigger. In the late 1700s, mathematicians like Adrien-Marie Legendre and Carl Friedrich Gauss made guesses about how to count primes. In the 1800s, Pafnuty Chebyshev made important steps toward proving these guesses, showing that primes are fairly regular in how often they show up.

Finally, in 1896, Jacques Hadamard and Charles Jean de la Vallée Poussin proved the Prime Number Theorem together. They showed that primes become less common as numbers grow, and they found exactly how much less common. Their work built on ideas from another famous mathematician, Bernhard Riemann, who connected primes to complex numbers. Since then, many other mathematicians have found new ways to prove this important theorem.

Proof sketch

Here is a simple idea behind one way to understand why primes get rarer as numbers grow bigger. We start by counting primes in a special way, using a tool called the Chebyshev function, written as ψ(x). This function helps us see patterns more clearly.

The big idea is that if we look at ψ(x) compared to x, we find they grow in the same way. This means the number of primes up to x grows roughly like x divided by log x, which is the main point of the prime number theorem.

To understand ψ(x), we use another important math tool called the Riemann zeta function. By studying its patterns, we can show that ψ(x) behaves nicely, and this helps prove the theorem. While the full proof is very detailed, this gives a glimpse into why the theorem works.

Newman's proof of the prime number theorem

D.J. Newman created a clear way to show the prime number theorem. This proof uses ideas from complex numbers, like Cauchy's integral formula and Cauchy's integral theorem, but stays close to basic math ideas.

The proof looks at a special math idea called the Chebyshev function ϑ(x). By studying how this function behaves, Newman showed that certain math parts fit together in a way that proves the prime number theorem. This means we can understand how prime numbers are spread out among all whole numbers.

Prime-counting function in terms of the logarithmic integral

In 1838, a mathematician named Dirichlet suggested a better way to guess how many prime numbers there are up to a certain number. He used a special math tool called the offset logarithmic integral, written as Li(x).

This idea connects to how often primes appear, suggesting that the "density" of primes around a number t is about 1 divided by the logarithm of t.

Later, in 1899, another mathematician showed that the prime number theorem could also be expressed using this logarithmic integral. Even today, mathematicians are working to make these guesses even better and more exact.

Elementary proofs

In the middle of the 1900s, some mathematicians thought that proving the prime number theorem needed very complex math. But in 1948, Atle Selberg found a way to prove it using simpler tools. Soon after, Paul Erdős also found a simple proof. These proofs showed that the prime number theorem wasn’t as complex as people thought.

Later, Florian Richter used a different area of math called ergodic theory to prove the theorem in another way. These different proofs helped mathematicians understand the theorem better and showed that simple methods could be very powerful.

Computer verifications

In 2005, some mathematicians used a special computer tool called Isabelle to check a proof of the prime number theorem. This was the first time a computer had checked this important math idea. They chose this method because the tool could handle some math ideas but not others.

In 2009, another mathematician used a different tool called HOL Light to check the proof in another way. He built up the needed math skills to make the proof clear and neat.

Prime number theorem for arithmetic progressions

This part of the prime number theorem looks at how prime numbers are spread out in special number patterns called arithmetic progressions. It says that if two numbers have no common factors other than 1, the primes will appear evenly in certain patterns. This was proven using clever mathematical methods.

There is something interesting called a "prime number race." For example, when looking at primes that end in certain digits, one group often has more primes than another for a while, but then they switch places many times. This back-and-forth happens infinitely often, which is a curious pattern in numbers.

Non-asymptotic bounds on the prime-counting function

Main article: Prime-counting function § Inequalities

The prime number theorem tells us about how primes are spread out among bigger numbers. It is an asymptotic result, meaning it talks about what happens when numbers get really large. This theorem gives us a way to estimate how many primes there are up to a certain number, but it doesn’t give a exact count. Instead, it says that for any small number ε greater than 0, there is a point S so that for all numbers x bigger than S, the number of primes up to x is between (1 − ε) times x divided by the natural logarithm of x and (1 + ε) times x divided by the natural logarithm of x.

Similarly, there are also bounds for how far the actual count of primes can be below this estimate. For any ε between 0 and 1, there is a number S so that for all x bigger than S, the number of primes up to x is at least (1 − ε) times x divided by the natural logarithm of x.

Approximations for the _n_th prime number

The prime number theorem helps us guess where the _n_th prime number will be. A simple way to think about it is that the _n_th prime, written as p_n, is about n times the natural logarithm of n.

Better ways to guess this use more detailed math, like the Cesàro method from 1894. Even very big prime numbers can be guessed pretty closely this way. For example, for the 2×10¹⁷th prime, the guess was off by only a tiny amount.

Table of π(x), x / log x, and li(x)

This table shows how many prime numbers there are up to a certain number, called π(x), and compares it to two ways of guessing this number: x / log x and li(x). The table also shows how close these guesses are to the real number of primes.

The number of primes up to 10²⁴ was first found using a special idea called the Riemann hypothesis, but it has since been checked without needing that idea.

x	π(x)	π(x) − ⁠x/log(x)⁠	li(x) − π(x)	% error		⁠x/π(x)⁠
x	π(x)	π(x) − ⁠x/log(x)⁠	li(x) − π(x)	⁠x/log(x)⁠	li(x)	⁠x/π(x)⁠
10	4	0	2	8.22%	42.606%	2.500
10²	25	3	5	14.06%	18.597%	4.000
10³	168	23	10	14.85%	5.561%	5.952
10⁴	1,229	143	17	12.37%	1.384%	8.137
10⁵	9,592	906	38	9.91%	0.393%	10.425
10⁶	78,498	6,116	130	8.11%	0.164%	12.739
10⁷	664,579	44,158	339	6.87%	0.051%	15.047
10⁸	5,761,455	332,774	754	5.94%	0.013%	17.357
10⁹	50,847,534	2,592,592	1,701	5.23%	3.34×10⁻³ %	19.667
10¹⁰	455,052,511	20,758,029	3,104	4.66%	6.82×10⁻⁴ %	21.975
10¹¹	4,118,054,813	169,923,159	11,588	4.21%	2.81×10⁻⁴ %	24.283
10¹²	37,607,912,018	1,416,705,193	38,263	3.83%	1.02×10⁻⁴ %	26.590
10¹³	346,065,536,839	11,992,858,452	108,971	3.52%	3.14×10⁻⁵ %	28.896
10¹⁴	3,204,941,750,802	102,838,308,636	314,890	3.26%	9.82×10⁻⁶ %	31.202
10¹⁵	29,844,570,422,669	891,604,962,452	1,052,619	3.03%	3.52×10⁻⁶ %	33.507
10¹⁶	279,238,341,033,925	7,804,289,844,393	3,214,632	2.83%	1.15×10⁻⁶ %	35.812
10¹⁷	2,623,557,157,654,233	68,883,734,693,928	7,956,589	2.66%	3.03×10⁻⁷ %	38.116
10¹⁸	24,739,954,287,740,860	612,483,070,893,536	21,949,555	2.51%	8.87×10⁻⁸ %	40.420
10¹⁹	234,057,667,276,344,607	5,481,624,169,369,961	99,877,775	2.36%	4.26×10⁻⁸ %	42.725
10²⁰	2,220,819,602,560,918,840	49,347,193,044,659,702	222,744,644	2.24%	1.01×10⁻⁸ %	45.028
10²¹	21,127,269,486,018,731,928	446,579,871,578,168,707	597,394,254	2.13%	2.82×10⁻⁹ %	47.332
10²²	201,467,286,689,315,906,290	4,060,704,006,019,620,994	1,932,355,208	2.03%	9.59×10⁻¹⁰ %	49.636
10²³	1,925,320,391,606,803,968,923	37,083,513,766,578,631,309	7,250,186,216	1.94%	3.76×10⁻¹⁰ %	51.939
10²⁴	18,435,599,767,349,200,867,866	339,996,354,713,708,049,069	17,146,907,278	1.86%	9.31×10⁻¹¹ %	54.243
10²⁵	176,846,309,399,143,769,411,680	3,128,516,637,843,038,351,228	55,160,980,939	1.78%	3.21×10⁻¹¹ %	56.546
10²⁶	1,699,246,750,872,437,141,327,603	28,883,358,936,853,188,823,261	155,891,678,121	1.71%	9.17×10⁻¹² %	58.850
10²⁷	16,352,460,426,841,680,446,427,399	267,479,615,610,131,274,163,365	508,666,658,006	1.64%	3.11×10⁻¹² %	61.153
10²⁸	157,589,269,275,973,410,412,739,598	2,484,097,167,669,186,251,622,127	1,427,745,660,374	1.58%	9.05×10⁻¹³ %	63.456
10²⁹	1,520,698,109,714,272,166,094,258,063	23,130,930,737,541,725,917,951,446	4,551,193,622,464	1.53%	2.99×10⁻¹³ %	65.759

Analogue for irreducible polynomials over a finite field

There is a version of the prime number theorem that talks about special kinds of equations called "irreducible polynomials" over a finite field. These polynomials act like prime numbers because all other polynomials can be built from them.

When we count these special polynomials of a certain size, we find that their number relates to the size in a clear way. This makes it easier to understand how common or rare these polynomials are, much like how the prime number theorem tells us about the distribution of prime numbers.