I post here the my first lecture in Leiden about analytic number theory. The main lecture is here
http://www.math.leidenuniv.nl/~evertse/ant16-1.pdf
In this, he introduces a very nice introduction about prime number theory, its relations to the theory of Riemann zeta function and L-functions. Latter, he proved a main theorem of the lecture due to Erdos.
Theorem 1 (Erdos). For all real $x\ge 3$, we have $\frac{1}{2}\frac{x}{\log x}\le \pi(x) \le 2\frac{x}{\log x}$, where $\pi(x)$ is the number of prime numbers that does not exceed to $x$.
The key idea here is to look at the properties of ${2k+1 \choose k}$ for all $k\ge 1$. In addition, to prove this, we will prove some lemmas
Lemma 2. $\prod_{k+2\le p\le 2k+1} p | {2k+1\choose k}$.
Proof. Obvious.
Lemma 3. Let $n\in \mathbb{Z}_{n\ge 1}$ and $p$ is a prime number, then
$$ord_p(n!) = \sum_{j=1}^\infty \big[\frac{n}{p^j}\big]$$.
Proof. Easy.
Lemma 4. Let $k\in \mathbb{Z}_{n\ge 1}$ and $p$ is a prime. Suppose $p^a | {2k+1\choose k}$, then $p^a\le 2k+1$.
Proof. We have ${2k+1\choose k}=\frac{(2k+1)!}{k!(k+1)!}$, and $p|{2k+1\choose k}$ means
$$ord_p{2k+1\choose k}=\sum_{j=1}^\infty\big[\frac{2k+1}{p^j}\big]-\big[\frac{k+1}{p^j}\big]-\big[\frac{k}{p^j}\big]$$
For any real numbers $a,b$, it is obvious to see that $[a+b]-[a]-[b]\in\{0,1\}$, and $\big[\frac{2k+1}{p^j}\big]-\big[\frac{k+1}{p^j}\big]-\big[\frac{k}{p^j}\big]$ is 0 if $p^j>2k+1$. Hence, $ord_p{2k+1\choose k}\le \alpha$, where $\alpha$ is the largest integer with $p^\alpha \le 2k+1$. This impiles $a\le\alpha$, and $p^a\le 2k+1$. (Q.E.D)
Via these lemmas, we obtain a
Corollary 5. ${2k+1\choose k}\le (2k+1)^{\pi(2k+1)}$, where $\pi(x)$ is defined above.
Proof. Let ${2k+1\choose k} = p_1^{\alpha_1}...p_n^{\alpha_n}$, then by Lemma 4, $p_i^{\alpha_i}\le 2k+1$, and $n\le \pi(2k+1)$. This concludes our corollary. (Q.E.D)
We are away from the proof of the theorem one more lemma.
Lemma 5. Let $k\in \mathbb{Z}_{n\ge 1}$, then
$$\frac{2^{2k+1}}{2k+2}\le {2k+1\choose k}\le 2^{2k}$$
Proof. We use the identity, and inequality
$$2^{2k+1}=\sum_{i=0}^{2k+1}\frac{2k+1}{i} \le (2k+1){2k+1\choose k}$$
Because ${2k+1\choose k}$ is the largest in the sum of left hand side. It implies $\frac{2^{2k+1}}{2k+2}\le {2k+1\choose k}$.
Further, ${2k+1\choose k}=\frac{1}{2}({2k+1\choose k}+{2k+1\choose k+1})\le \frac{1}{2} \sum_{i=0}^{2k+1}\frac{2k+1}{i} = \frac{1}{2}2^{2k+1}=2^{2k}$
(Q.E.D)
We are now ready for the proof of our main theorem. First is the upper bound, we have $\pi(x)\ge \frac{1}{2}\frac{x}{\log x}$ for $x\ge 3$.
Let $k$ be the integer with $2k+1\le x< 2k+3$. That means, $\pi(x) = \pi(2k+1)$. We use Lemma 5 to btain
$$\frac{2^{2k+1}}{2k+2}\le {2k+1 \choose k}\le (2k+1)^{\pi(2k+1)}$$
Taking the logarithms for the left and right hand side, we have
$$(2k+1)\log 2 - log(2k+2)\le \pi(2k+1)\log(2k+1)$$
So,
$$\pi(x) \ge \frac{2k+1\log 2-\log(2k+2)}{\log(2k+1)}\ge \frac{(x-2)\log 2-\log(x+1)}{\log x}>\frac{1}{2}\frac{x}{\log x}$$
The final inequality is true for $x>1000$. For $x<1000$, we can check by hand.
For the upper bound, let $n=[x]$, then $\frac{n}{\log n}\le \frac{x}{\log x}$ (it does make sense, because $x>>\log x$), and $\pi(x)=\pi(n)$. We will prove this by induction.
For $3\le n\le 1000$, we can check it by hand. For larger $n$, if $n$ is even, then $\pi(n)=\pi(n-1)\le \frac{2(n-1)}{\log(n-1)}\le \frac{2n}{\log n}$. Let $n=2k+1$, by Lemma 1, we have
$${2k+1\choose k}\ge (k+2)^{\pi(2k+1)-\pi(k+1)}$$
Using the inequality in Lemma 5, we have $2^{2k}\le (k+2)^{\pi(2k+1)-\pi(k+1)}$. Taking the logarithm of both sides, we have
$$\pi(2k+1)-\pi(k+1)\le\frac{2k\log 2}{\log(k+1)}$$
Hence, by the induction hypothesis,
$$\pi(2k+1)\le \frac{2k\log 2}{\log(k+2)}+\frac{2(k+1)}{\log(k+1)}$$
So,
$$\pi(n)\le \frac{(n-1)\log 2}{\log \frac{n}{2}}+\frac{n+1}{\log\frac{n}{2}} = \frac{n(\log 2+1)+1-\log 2}{\log \frac{n}{2}}<\frac{2n}{\log n}$$
It can be easily obtained when we compare two highest terms $2n\log \frac{n}{2}$ VS $n\log n (\log 2 + 1)$, with the note that $\log 2 + 1 \cong 1.3$.
No comments:
Post a Comment