7.3: Getting Closer to the Proof of the Prime Number Theorem
( \newcommand{\kernel}{\mathrm{null}\,}\)
We know prove a theorem that is related to the defined functions above. Keep in mind that the prime number theorem is given as follows: limx→∞π(x)logxx=1. We now state equivalent forms of the prime number theorem.
The following relations are equivalent limx→∞π(x)logxx=1 limx→∞θ(x)x=1 limx→∞ψ(x)x=1.
We have proved in Theorem 86 that (???) and (???) are equivalent, so if we show that (???) and (???) are equivalent, the proof will follow. Notice that using the integral representations of the functions in Theorem 85, we obtain θ(x)x=π(x)logxx−1x∫x2π(t)tdt and π(x)logxx=θ(x)x+logxx∫x2θ(t)tlog2tdt. Now to prove that ([3]) implies (???), we need to prove that limx→∞1x∫x2π(t)tdt=0. Notice also that (???) implies that π(t)t=O(1logt) for t≥2 and thus we have 1x∫x2π(t)tdt=O(1x∫x2dtlogt) Now once you show that (Exercise 1) ∫x2dtlogt≤√xlog2+x−√xlog√x, then (???) implies (???) will follow. We still need to show that (???) implies (???) and thus we have to show that limx→∞logxx∫x2θ(t)dttlog2t=0. Notice that θ(x)=O(x) and hence logxx∫x2θ(t)dttlog2t=O(logxx∫x2dtlog2t). Now once again we show that (Exercise 2) ∫x2dtlog2t≤√xlog22+x−√xlog2√x then (???) implies (???) will follow.
Define l1=lim infx→∞π(x)x/logx, L1=lim supx→∞π(x)x/logx, l2=lim infx→∞θ(x)x, L2=lim supx→∞θ(x)x, and l3=lim infx→∞ψ(x)x, L3=lim supx→∞ψ(x)x, then l1=l2=l3 and L1=L2=L3.
Notice that ψ(x)=θ(x)+θ(x1/2)+θ(x1/3)+...θ(x1/m)≥θ(x) where m≤log2x
Also, ψ(x)=∑p≤x[logxlogp]logp≤∑p≤xlogxlogplogp=logxπ(x). Thus we have θ(x)≤ψ(x)≤π(x)logx As a result, we have θ(x)x≤ψ(x)x≤π(x)x/logx and we get that L2≤L3≤L1. We still need to prove that L1≤L2.
Let α be a real number where 0<α<1, we have θ(x)=∑p≤xlogp≥∑xα≤p≤xlogp>∑xα≤p≤xαlogx (logp>αlogx)=αlogx{π(x)−π(xα)} However, π(xα)≤xα. Hence θ(x)>αlogx{π(x)−xα} As a result, θ(x)x>απ(x)x/logx−αxα−1logx Since limx→∞αlogx/x1−α=0, then L2≥αlim supx→∞π(x)x/logx As a result, we get that L2≥αL1 As α→1, we get L2≥L1.
Proving that l1=l2=l3 is left as an exercise.
We now present an inequality due to Chebyshev about π(x).
There exist constants a<A such that axlogx<π(x)<Axlogx for sufficiently large x.
Put l=lim infx→∞π(x)x/logx, L=lim supx→∞π(x)x/logx, It will be sufficient to prove that L≤4log2 and l≥log2. Thus by Theorem 2, we have to prove that lim supx→∞θ(x)x≤4log2 and lim infx→∞ψ(x)x≥log2 To prove (???), notice that N=C(2n,n)=(n+1)(n+2)...(n+n)n!<22n<(2n+1)N Suppose now that p is a prime such that n<p<2n and hence p∣N. As a result, we have N≥∏n<p<2np. We get N≥θ(2n)−θ(n). Since N<22n, we get that θ(2n)−θ(n)<2nlog2. Put n=1,2,22,...,2m−1 where m is a positive integer. We get that θ(2m)<2m−1log2. Let x>1 and choose m such that 2m−1≤x≤2m, we get that θ(x)≤θ(2m)≤2m+1log2≤4xlog2 and we get (???) for all x.
We now prove (???). Notice that by Lemma 9, we have that the highest power of a prime p dividing N=(2n)!(n!)2 is given by sp=μp∑i=11{[2npi]−2[npi]}. where μp=[log2nlogp]. Thus we have N=∏p≤2npsp. If x is a positive integer then [2x]−2[x]<2, It means that [2x]−2[x] is 0 or 1. Thus sp≤μp and we get N≤∏p≤e2npμp. Notice as well that ψ(2n)=∑p≤2n[log2nlogp]logp=∑p≤2nμplogp. Hence we get logN≤ψ(2n). Using the fact that 22n<(2n+1)N, we can see that ψ(2n)>2nlog2−log(2n+1). Let x>2 and put n=[x2]≥1. Thus x2−1<n<x2 and we get 2n≤x. So we get ψ(x)≥ψ(2n)>2nlog2−log(2n+1)>(x−2)log2−log(x+1). As a result, we get lim infx→∞ψ(x)x≥log2.
Exercises
- Show that l1=l2=l3 in Theorem 88.
- Show that ∫x2dtlogt≤√xlog2+x−√xlog√x,
- Show that ∫x2dtlog2t≤√xlog22+x−√xlog2√x
- Show that N=C(2n,n)=(n+1)(n+2)...(n+n)n!<22n<(2n+1)N
- Show that 22n2√n<N=C(2n,n)<22n√2n.
Hint: For one side of the inequality, write N2n=(2n)!22n(n!)2=1.3.5....(2n−1)2.4.6....(2n).2.4.6.....(2n)2.4.6...(2n), then show that 1>(2n+1).N224n>2n.N224n. The other side of the inequality will follow with similar arithmetic techniques as the first inequality.
Contributors and Attributions
Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.