State/Chebyshev estimates for the prime number function

From SlugmathWiki

Theorem
Proof

Theorem: (Chebyshev estimates for the prime number function) For all $\epsilon > 0$, there exists $x_0 > 0$, such that for all $x \in \NN$ satisfying $x > x_0$, $$(\log(2) - \epsilon) \frac{x}{log(x)} \leq \pi(x) < (\log(4) + \epsilon) \frac{x}{\log(x)},$$ where $\pi(x)$ denotes the prime counting function, and $log(x)$ denotes the natural logarithm of $x$.

Logical Connections

This statement logically relies on the following definitions and statements: Def/Prime counting function, Def/Natural logarithm, State/Estimate for the product of primes

The following statements and definitions rely on the material of this page:

To visualize the logical connections between this statements and other items of mathematical knowledge, you can visit the following cluster(s), and click the "Visualize" tab: Clust/Analytic number theory

Our proof is based on that in the book of Erdos and Suranyi. We begin by proving a lower bound for $\pi(x)$:

	Suppose that $x \in \NN$, and $x > 1$. Consider the binomial coefficient: $$C_x = \left( {2x \atop x} \right).$$
	Consider the exponents $e_p$ in the canonical decomposition of $C_x$. We have seen that $0 \leq e_p \leq log_{p}(2x)$ for all prime numbers $p$. It follows that: $$C_x = \prod_{p \in P} p^{e_p} \leq \prod_{p \in P, p \leq 2x} 2x = (2x)^{\pi(2x)}.$$ We can also estimate $C_x$ as follows: $$C_x = \left( {2x \atop x} \right) = \frac{(2x)!}{x!x!} = 2^x \frac{1 \cdot 3 \cdot \cdots \cdot 2x-1}{x!}.$$ The last equality follows from separating $(2x)!$ into even and odd factors, factoring out $2^x$, and cancelling. Since $3 > 2, 5 > 4, \ldots, 2x - 1 > 2x-2$, we find that: $$C_x > 2^x \frac{2 \cdot 4 \cdots \cdot 2x-2}{x!} = 2^x 2^{x-1}\frac{(x-1)!}{x!} = \frac{2^{2x-1} }{x} = \frac{2^{2x} }{2x}.$$ Putting these identities together, we find that: $$(2x)^{\pi(2x)} \geq C_x > \frac{2^{2x} }{2x}.$$ Therefore, we find that: $$\pi(2x) log(2x) > 2x log(2) - log(2x).$$ Hence, we find that: $$\pi(2x) > log(2) \frac{2x}{log(2x)} - 1.$$ Since $\pi(2x+1) \geq \pi(2x)$, we find that: $$\pi(2x+1) > log(2) \frac{2x+1 - 1}{log(2x)} - 1.$$ $$\pi(2x+1) > log(2) \frac{2x+1}{log(2x+1)} - log(2)\frac{1}{log(2x+1)} - 1.$$ $$\pi(2x+1) > log(2) \frac{2x+1}{log(2x+1)} - 2.$$ Since every natural number has the form $2x$, or the form $2x+1$, for some natural number $x$, it follows that for all $y \in \NN$, $$\pi(y) > log(2) \frac{y}{log(y)} - 2.$$
	Hence, if the limit below exists, then: $$\lim_{x \rightarrow \infty} \frac{\pi(x) \log(x)}{x} \geq \log(2).$$

Next, we prove an upper bound for $\pi(x)$.

	Suppose that $x \in \NN$, and $x > 1$.
	Recall that one has the following estimate for the product of primes: $$\prod_{p \leq x} p < 4^x.$$ Now, choose a real number $\delta$, such that $0 < \delta < 1$. Let $y = x^\delta$. Then, one has: $$\prod_{y < p \leq x} p \geq y^{\pi(x) - \pi(y)} > y^{\pi(x) - y} = x^{\delta(\pi(x) - x^\delta)}.$$ It follows that: $$ x^{\delta(\pi(x) - x^\delta)} < 4^x.$$ Taking the logarithm of both sides yields: $$(\delta \pi(x) - x^\delta) \log(x) < x \log(4).$$ Hence, $$\pi(x) < \frac{x \log(4)}{\delta \log(x)} + x^\delta.$$ Therefore, $$\pi(x) < \left( \frac{\log(4)}{\delta} + x^{\delta - 1} \log(x) \right) \frac{x}{\log(x)}.$$ As $\delta$ approaches $1$ (from the left), the quantity in parentheses approaches $\log(4)$.
	It follows that, if the limit below exists, then: $$\lim_{x \rightarrow \infty} \frac{\pi(x) \log(x)}{x} \leq \log(4).$$

State/Chebyshev estimates for the prime number function

From SlugmathWiki

Logical Connections

Views

Personal tools

Navigation

Mathematics

Pegagogy

Search

Toolbox