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

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?

• Well, I'd say the simplest lower bound (although a not very useful one) is $\pi(n)\ge 0$. This one can be proven without even making any reference to the properties of primes. ;-) – celtschk Aug 13 '16 at 9:42
• The very elegant argument here can be combined with this answer to get a lower bound $\pi(n) \geq (n-1) \log(2) / \log(n)$. – Watson Dec 27 '19 at 17:15

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\}$

• This is a nice answer! However, shouldn't it be "this is because $P_n + 1$ must itself..." and not $P_1 + 1$? Also, would it perhaps be clearer to let $q_{\pi(n)}$ be the largest prime less than $n$ to make the tie to the prime counting function $\pi(\cdot)$ more obvious (i.e. enumerate the primes as $q_1, \ldots, q_{\pi(n)}$)? :) – Erlend Graff Aug 14 '16 at 0:12
• Wow, nice answer sir! – Sandeep Silwal Aug 14 '16 at 16:08
• @ErlendGraff thanks for the P_n correction. The benefit of defining q_n as I have is to make comparison to n! very easy (as opposed to having to compare P_n to pi(n)!) – rikhavshah Aug 14 '16 at 21:09

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.

• For the unfamiliar reader: The square brackets denote the floor function in parts 2) and 3) above... – Benjamin Dickman Aug 13 '16 at 19:12
• @BenjaminDickman: You mean the integer part? Floor isn't denoted by brackets... – user541686 Aug 13 '16 at 20:42
• @Mehrdad it seems it does not really matter given that the quantities are positive. But actually it is a common notation for floor. – quid Aug 13 '16 at 22:36

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.$$

According to Bertrand's postulate (proofs of which may be found here), if $n\geq 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.

• This is a better bound than that in my answer, but the cost is that you must first prove Bertrand's postulate (still elementary but less "simple"). – Will R Aug 13 '16 at 23:27

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_i\in \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_k\leq n.$$ A stars and bars argument establishes that the number of tuples $(a_1,\ldots,a_k)$ satisfying this is ${n+k\choose 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{2\pi n}(n/e)^n$ on every factorial gives $${(\alpha+1)n \choose n}\sim \frac{1}{\sqrt{2\pi 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{2\pi 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 $\alpha\geq .2938\ldots$. 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.

• Hi, could you explain the jump from "since there are $\pi(n)$ total primes [...]" to $(\log_2(n) +1)^{\pi (n)}\geq n?$ Sorry, I'm sure it's simple I just can't see it right now. – Sonk Oct 23 '16 at 15:26