Prime number theorem

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.

This 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.

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 estimated 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 always been curious about how often prime numbers appear as numbers get larger. In the late 1700s, mathematicians like Adrien-Marie Legendre and Carl Friedrich Gauss made guesses about counting primes. In the 1800s, Pafnuty Chebyshev took important steps to prove these guesses, showing that primes appear fairly regularly.

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 bigger, and they found exactly how much less common. Their work used ideas from another famous mathematician, Bernhard Riemann, who linked 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 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.

Newman's proof of the prime number theorem

D.J. Newman found a simple way to prove the prime number theorem. His proof uses ideas from complex numbers, such as Cauchy's integral formula and Cauchy's integral theorem, but it stays close to basic math.

The proof looks at a special math idea called the Chebyshev function ϑ(x). By studying this function, Newman showed that certain math parts fit together to prove the prime number theorem. This helps us 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. It suggests 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. Mathematicians are still working to make these guesses even better and more exact.

Elementary proofs

In the middle of the 1900s, some mathematicians thought 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, mathematicians used a computer tool called Isabelle to check a proof of the prime number theorem. This was the first time a computer checked this math idea.

In 2009, another mathematician used a tool called HOL Light to check the proof in a different way. He worked 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.

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.

Non-asymptotic bounds on the prime-counting function

Main article: Prime-counting function § Inequalities

The prime number theorem helps us understand how primes are spread out among larger numbers. It is an asymptotic result, meaning it talks about what happens when numbers get really big. This theorem gives us a way to estimate how many primes there are up to a certain number, but it doesn’t give an 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.

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, but it has since been checked in other ways.

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 helps us understand how common or rare these polynomials are, just like the prime number theorem helps us understand prime numbers.