Transcript i ≤ n
Chebychev’s Theorem on the
Density of Prime
Numbers
Yaron Heger
and
Tal Kaminker
So far we only proved that there are ∞ primes.
But can we say more than this?
We will prove in this lecture a good estimation
on the density of primes
Density of primes
Let us define
= number of primes till x
Compare this with:
For large numbers…
x
pi(x)
x/ln x
x/(ln x -1)
1000
168
145
169
10000
1229
1086
1218
100000
9592
8686
9512
1000000
78498
72382
78030
10000000
664579
620420
661459
100000000
5761455
5428681
5740304
Basically it is possible to prove
that:
The numbers of primes till n is
asymptotically the same as n/ln(n)
Meaning:
This was proven in 1896 by Hadamard and de la Vallée Poussin
But we can’t prove it right now…
So we will prove less powerful but still good estimation
We will prove that:
π(x) = Θ(x/ log x)
This is a result of a work by Chebychev made in 1852.
Chebychev-type estimates
We will now prove that:
Lower bound
The heart of the proof is understanding some
facts of the binomial coefficient
2n (2n)! 2n (2n 1) (2n 2) (n 1)
n(n 1)( n 2) 2 1
n n!n!
Let us define:
100 3 4
2 3 1113 17 19 29 31 53 59 61 67 71 83 89 97
50
Overview
First we will prove that:
2n 2 2 n
n 2n
(1)
Then we will prove that:
For each
i
p 2n
ki
i
Thus, we get that:
( 2)
N
( n)
2
log( N )
Assuming (1) and (2) we conclude…
For N = 2n (N is even):
N
( n)
1
log( N )
For N = 2n+1 (N is odd):
N
( n)
2
log( N )
Proof:
(n 1) (n)
n
n 1 1
n 1
1
n 1
1
1
1
2
log n
log n
log n log n
log( n 1)
2n 2 2 n
n 2n
Proof of
Using the Newton's binomial:
1 1
2n
Thus
2n i 2 n i 2 n 2n
1 1
i 0 i
i 0 i
2n
2n
2
i 0 i
i 2n
2n
…
2n
n
So, if we manage to prove that
is the largest coefficient we will get that:
2n
2n
2
n 2n 1
Using simple arguments (for example that the
first and the last coefficients are 1) we can get
that:
2n 2 2 n
n 2n
Proof that
2n
n is
the largest coefficient
2n 2n (2n 1) (n 1) 2n (2n 1) (2n k 1) 2n
?
n (n 1) 2 1
k (k 1) 2 1
n
k
(2n k ) (2n k 1) (n 1) 1
?
n (n 1) (k 1)
1
Both the numerator and the denominator have n-k elements.
But any of the numerator’s elements is larger than any of the
denominator elements, thus:
2n 2n
n k 0
n k
This is enough since
2n 2n
n k n k
A graph:
Now we know that
2n
2
n
2
2n
2
n 2n
Now we will prove that:
For each
Where:
i
p 2n
ki
i
Proof that:
For each
i
p 2n
ki
i
First define:
For n N and prime p, define p (n) = the power to which p
appears in the factorization of n.
Thus, p (n) is the largest k≥0 such that
pk | n
And we also get:
np
p (n)
p| n
For example,
3 (162) 3 (3 2) 4
4
Proof that:
For each
i
p 2n
ki
i
Next, define the floor function:
a
b = a div b
For example: 16
5 3
Also, this equals to the number of multiplies
b,2b,3b,4b,…mb that do not exceed a
Proof that:
For each
i
p 2n
ki
i
Legendre’s lemma
n
p (n!) k
k 1 p
Proof:
First define:
Rp,n = {(i, k) | 1 ≤ i ≤ n and
p k divides i }.
Legendre’s lemma
Rp,n = {(i, k) | 1 ≤ i ≤ n and
k
pdivides
i }.
Example for p=2 and n=20:
i=1 2
k=1
2
3
●
3
4
●
●
5
6
●
7
8
●
9 10 11 12 13 14 15 16 17 18 19 20
●
●
●
4
For every ● the pair (i,k) is in Rp,n
●
●
●
●
●
●
●
●
●
●
Legendre’s lemma
According to what we have seen on the
blackboard, since both sums represents |Rp,n|
we have:
n
p (n!) k
k 1 p
And this proves the Legendre’s lemma.
So far we have seen…
We proved
●
2n 2 2 n
n 2n
n
p (n!) k
k 1 p
●
And we defined:
And now we will prove that:
for each i : piki 2n
Proof that:
For each
i
p 2n
ki
i
2n
If we denote, l p
n
According to the proof on the blackboard,
we get
2n n
l k 2 k
k 1 p
p
And since, y R 2 y 2 y {0,1}
We conclude that:
p l 2n
Summary :
We first proved that:
●
Then we proved:
●
2n 2 2 n
n 2n
n
p (n!) k
k 1 p
Finally we proved:
For each i
ki
i
p
2n
And from here we concluded the lower bound
theorem.