素数计数函数$\pi(x)\sim \Theta(\frac{x}{\log{x}})$的一个初等方法——素数定理的估计
$\DeclareMathOperator{\lcm}{lcm}$
本文的方法来源于GTM 190:"Problems in Algebraic Number Theory",给出了$\pi(x)\sim \Theta(\frac{x}{\log{x}})$的证明。以下使用的$p$隐含了$p$是素数的条件。
1. $\pi(x)\ge \frac{x\log{2}}{2\log{x}}$在$x\ge 6$成立
证明：(1)定义$\psi(x)=\sum_{p^\alpha \le x}\log{p}$,也就是说，小于$x$最大素数的幂乘积再取$\log$.那么我们可以知道
$$e^{\psi(n)}=\lcm(1,2,\cdots,n)$$
同时，利用二次函数性质，我们知道在$0\le x\le 1$时候，$x(1-x)\le \frac{1}4$,那么有$$\int_0^1 x^n(1-x)^ndx\le \frac{1}{4}$$
但是我们同样知道$\int_0^1 x^n(1-x)^ndx>0$,且展开多项式，最大的次数为$2n$,不定积分就产生了$1/1,1/2,\cdots,1/(2n+1)$这些分母。也就是$$ e^{\psi(2n+1)}\int_0^1 x^n(1-x)^ndx\ge 1 \ge 4^n\int_0^1 x^n(1-x)^ndx$$
从而很容易就知道$\psi(2n+1)\ge 2n\log{2}$。
(2)由于$\psi(2n)\ge \psi(2n-1) \ge (2n-2)\log{2}\ge \frac{x}{2} \log{2}$对于任意$2n\ge 6$成立，与此同时，$2n+1 \ge n/2$，那么我们知道
$$\pi(x)\ge \sum_{p\le x}= \sum_{p^{\alpha}\le x}\log_x(p)=\frac{\psi(x)}{\log{x}}\ge \frac{x\log{2}}{2\log{x}}$$
2.$\pi(x)\le \frac{9x\log{2}}{\log{x}}$在$x\ge 2$成立
证明：注意到$\prod_{n<p\le 2n}p|\binom{2n}{n}$,这是由于当$p>n$的时候，$(p,n!)=1$,那么我们就知道
$$\prod_{k=1}^{2n} k\le \prod_{k=1}^n (2k)(2k+0)=2^{2n}(n!)^2 \Rightarrow\sum_{n<p\le 2n}\log{p}\le 2n\log{2}$$
定义$\theta(n)=\sum_{p\le n}\log{p}$,那么$\theta(2n)-\theta(n)\le 2n\log{2}$,利用数学归纳法知道$\theta(2^r)\le 2^{r+1}\log{2}$
对于任意$x$,选择$r$,使得$2^r<x\le 2^{r+1}$,所以$\theta(x)\le 2^{r+1} \log{2} \le 4x\log{2}$,特别地，就有$\theta(x)-\theta(\sqrt{x})\le 4x\log{2}$.我们考虑
$$\pi(x)-\pi(\sqrt{x})\le \sum_{\sqrt{x}< p \le}\log_{\sqrt{x}}{p}=\frac{1}{\log{\sqrt{x}}}(\theta(x)-\theta(\sqrt{x}))\le\frac{8x\log{2}}{\log{x}}$$
那么根据这个结论就知道，$$\pi(x)\le \frac{8x\log{2}}{\log{x}}+\pi(\sqrt{x})\le \frac{8x\log{2}}{\log{x}}+\sqrt{x} \le\frac{9x\log{2}}{\log{x}}$$
小结
1.我们可以看出，主要是通过$\pi(x)$与$\log_x{p}$或者$\log_{\sqrt{x}}{p}$和的对比进行估计的，这样的函数可以很松地估计$\pi(x)$,我们可以把这个证明变得更紧一些。
2.但是这样的证明太技巧性了，我们对素数定理更深刻的理解并没有得到体现，陶哲轩曾在他的讲座“Structure And Randomness in the Prime Numbers”（附上报告的slide）曾说过这样的话：
"There are more elementary ways to prove the prime number theorem, but those proofs are longer and also not so intuitive. In fact, the elementary proof are not considered anyway as elegant and informative as the much more modern proof..."
翻译过来是“尽管素数定理有更加初等的证明方法，但是这些证明都很长，而且没有（如同前面他讲过的一个傅立叶分析的证明一样）那么直观。事实上，初等的证明完全没有和现代证明相提并论的优美性与知识性”。这里是陶哲轩提到的证明
这个证明我也许会在以后提到。言归正传，我们现在初等证明只是一个比较tricky的东西，利用现代的观点进行理解才是我们的目标。
优质内容筛选与推荐>>1、移动端根据dpr适配
2、第四天
3、Ray Lighting Creating realistic shadows for terrain
4、【Windows】关于shift和空格同时按无反应的解决方案
5、redis对string进行的相关操作