11
$\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$
  • 10
    $\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
14
$\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\}$

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

$\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$ – Mehrdad 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
9
$\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.$$

$\endgroup$
8
$\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.

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

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

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

protected by Saad Dec 13 '18 at 16:27

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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