Ytukyg

I am trying to understand how a lower bound can exist on the prime counting function, and to begin this process of educating myself I am trying to find a simple complete proof, that does not hinge on another more complex theory?

Here's a very easy to prove lower bound:

Consider the product of all primes less than $n$, call it $P_n$. Let the largest prime less than $n$ be $q_n$. There must be a prime on $[q_n+1, P_n+1]$ (this is because $P_n+1$ must itself be prime or be divisible by some other prime, but isn't divisible by any prime less than or equal to $q_n$). Clearly, $P_n+1leq n!$ for $n>2,ninmathbb{N}$

Given that $pi(3)=2$, we see that $pi(3!)=pi(6)geq2+1=3$, then $pi(6!)geq4$

In general $pi(3underbrace{!!...!!}_{n})geq n+1$

Interpolation is easy, let $pi(n)=pi(k)$ for $k=sup{3underbrace{!!...!!}_{m}|3underbrace{!!...!!}_{m}leq n}$

Actually, I absolutely fail to understand why the classical Chebyshev bound is considered to be so difficult. The proof consists of four elementary steps:

1) $A_n={2n choose n}=frac{(2n)!}{n!^2}$ is an integer whose factorization includes only primes $ple 2n$. In addition, this number is fairly large: since $frac{n+k}{k}ge 2$ for all $1le kle n$, we have $A_nge 2^n$.

2) The power of a prime $p$ in $m!$ equals $left[frac mpright]+left[frac m{p^2}right]+dots+left[frac m{p^k}right]$ where $p^kle m< p^{k+1}$.

3) Hence the power of any prime $p$ in $A_n$ equals $sum_{j=1}^{k_p}left(left[frac {2n}{p^j}right]-2left[frac n{p^j}right]right)le k_p$,
where $p^{k_p}le 2n< p^{k_p+1}$ (we used here the trivial observation that $[2x]-2[x]le 1$ for all $x$).

4) Thus, $2^nle A_nle prod_{ple 2n}p^{k_p}le (2n)^{pi(2n)}$ whence
$$
pi(2n)ge frac{nlog 2}{log(2n)}
$$
giving you the right order of magnitude at the expense of at most half an hour of studies.

There's a simple lower bound due to Erdős which I detailed over in another answer. For completeness, I'll repost the argument as an answer here.

Let $ninmathbb{N}={1,2,3,ldots}.$ Consider the set $$S(n) = {(k,l)inmathbb{N}^{2}:ltext{ is square-free and }k^{2}lleq n}.$$ It is a standard fact that every natural number has a unique representation in the form $k^{2}l,$ where $k$ and $l$ are natural numbers and $l$ is square-free. This gives $lvert S(n)rvert = n.$

Now if we have a pair $(k,l)$ with $k^{2}lleq n,$ then we must have $k^{2}leq n$ and $lleq n$, since $k$ and $l$ are positive. Note that this gives $kleqsqrt{n}.$ Since $l$ is square-free, $l$ can be expressed as a product of distinct primes, each of which must be not-greater-than $n$ since $lleq n$. That is, $l$ can be expressed as a product of the primes $p_{1},p_{2},ldots,p_{pi(n)}.$ There are $2^{pi(n)}$ such products.

Therefore, if we know $(k,l)in S(n)$ then there are at most $sqrt{n}$ possibilities for what $k$ might be and at most $2^{pi(n)}$ possibilities for what $l$ might be (independent of $k$, of course). It follows that $lvert S(n)rvert leq 2^{pi(n)}sqrt{n},$ so $nleq2^{pi(n)}sqrt{n}.$

Taking $log$s and rearranging gives the following result: $$pi(n)geqfrac{log{n}}{2log{2}}quadtext{for }n=1,2,ldots.$$

According to Bertrand's postulate (proofs of which may be found here), if $ngeq 2$, then there is a prime between $n$ and $2n$ (not including $n$). Therefore, in general, $pi(2x) geq pi(x)+1$. Since $pi(2)=1$, we have $pi(4)geq 1+1=2, pi(8)geq 2+1=3$, and in general, $pi(2^n)geq n implies pi(x) geq log_2(x)$ (since $pi$ is increasing). This lower bound is by no means optimal, but it is simple and admits a relatively simple proof.

Given $k$ primes $p_1,ldots,p_k$, let us calculate the number of products of these primes below some threshold $2^n$. That is, ask how many choices of exponents $a_iin mathbb N$ satisfy:
$$p_1^{a_1}p_2^{a_2}ldots p_k^{a_k}leq 2^n.$$
Since every prime is at least $2$, we get that this statement implies
$$2^{a_1+a_2+ldots+a_k}leq 2^n$$
$$a_1+a_2+ldots+a_kleq n.$$
A stars and bars argument establishes that the number of tuples $(a_1,ldots,a_k)$ satisfying this is ${n+kchoose n}$. There are $2^n$ integers in the interval $[1,2^n]$ and each can be written as a product of primes less than $2^n$. Thus, we must have, setting $k=pi(2^n)$:
$${n+pi(2^n)choose n}geq 2^n.$$
That's a pretty painless proof.

Okay, let's do the painful bit of showing that this is a logarithmic bound. This is, unfortunately, using harder tools than were required to derive the bound in the first place. It basically reduces to figuring out that there is some $alpha$ such that the minimal $pi(2^n)geq alpha n$ for large enough $n$. To do so, consider the value $${(alpha+1)n choose n}=frac{((alpha+1)n)!}{n!(alpha n)!}$$ where we slightly abuse notation in assuming the relevant terms are integers. Since we're going to use an asymptotic approximation, this does not really matter. Using Stirling's approximation that $n!sim sqrt{2pi n}(n/e)^n$ on every factorial gives
$${(alpha+1)n choose n}sim frac{1}{sqrt{2pi n}}cdot frac{sqrt{alpha+1}}{sqrt{alpha}}cdot frac{((alpha+1)n/e)^{(alpha+1)n}}{(n/e)^n(alpha n/e)^{alpha n}}=frac{1}{sqrt{2pi n}}cdot frac{sqrt{alpha+1}}{sqrt{alpha}}cdot left(frac{(alpha+1)^{alpha+1}}{alpha^{alpha}}right)^n$$
What should be clear is that this function is eventually bounded by $frac{(alpha+1)^{alpha+1}}{alpha^{alpha}}$, meaning that expression must be at least two. Numerically, this gives $alphageq .2938ldots$. For the minimal possible $alpha$ given by this inequality, we would get
$$pi(2^n)geq alpha n$$
for big enough $n$. This suffices to establish a logarithmic lower bound on the prime counting function.

Here is an answer that uses the Fundamental Theorem of Arithmetic. Let $pi(n)$ be the number of primes less than or equal to $n$. For each natural $k$ less than $n$, the exponent of the primes in the prime factorization of $k$ can be at most $log_2(n)$.

Since there are $pi(n)$ total primes that can be used in the prime factorization of $k$, we have

$$(log_2(n) + 1)^{pi(n)} ge n implies pi(n) ge frac{log(n)}{log(log_2(n) + 1)} approx frac{log(n)}{log log(n)}.$$

Interestingly, exponentiating this bound gives you the PNT.