What is the simplest lower bound on prime counting functions proof wise?

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 $p\le 2n$. In addition, this number is fairly large: since $\frac{n+k}{k}\ge 2$ for all $1\le k\le n$, we have $A_n\ge 2^n$.

2) The power of a prime $p$ in $m!$ equals $\left[\frac mp\right]+\left[\frac m{p^2}\right]+\dots+\left[\frac m{p^k}\right]$ where $p^k\le 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]-2\left[\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^n\le A_n\le \prod_{p\le 2n}p^{k_p}\le (2n)^{\pi(2n)}$ whence $$ \pi(2n)\ge \frac{n\log 2}{\log(2n)} $$ giving you the right order of magnitude at the expense of at most half an hour of studies.


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+1\leq n!$ for $n>2,n\in\mathbb{N}$

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

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

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


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 $n\in\mathbb{N}=\{1,2,3,\ldots\}.$ Consider the set $$S(n) = \{(k,l)\in\mathbb{N}^{2}:l\text{ is square-free and }k^{2}l\leq 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}l\leq n,$ then we must have $k^{2}\leq n$ and $l\leq n$, since $k$ and $l$ are positive. Note that this gives $k\leq\sqrt{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 $l\leq 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 $n\leq2^{\pi(n)}\sqrt{n}.$

Taking $\log$s and rearranging gives the following result: $$\pi(n)\geq\frac{\log{n}}{2\log{2}}\quad\text{for }n=1,2,\ldots.$$