14
$\begingroup$

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?

$\endgroup$
  • 11
    $\begingroup$ 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. ;-) $\endgroup$ – celtschk Aug 13 '16 at 9:42
  • $\begingroup$ 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)$. $\endgroup$ – Watson Dec 27 '19 at 17:15
15
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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)}$)? :) $\endgroup$ – Erlend Graff Aug 14 '16 at 0:12
  • 1
    $\begingroup$ Wow, nice answer sir! $\endgroup$ – Sandeep Silwal Aug 14 '16 at 16:08
  • 1
    $\begingroup$ @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)!) $\endgroup$ – rikhavshah Aug 14 '16 at 21:09
35
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$
10
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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"). $\endgroup$ – Will R Aug 13 '16 at 23:27
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sonk Oct 23 '16 at 15:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.