Elementary bounds on the primes

967 Views Asked by At

There are several loose yet elementary bounds on the prime numbers. Say for an example, an (very loose indeed...) upper bound on $p_n$, the $n^{th}$ prime number: $$p_n<2^{2^{n}}$$ can be easily achieved by induction (appendix 1). A much more tight one, $$p_n<4^n$$, could also be proved by using elementary combinatorics (appendix 2).

So, this post is to collect upper or lower bounds on $p_n$ which could also be attained by elementary approaches (by the way, there is a urban legend saying that the prime number theorem has an elementary proof, but not yet verified for me), which is (in an educator's view, maybe) indeed a very good way to inspire students who are studying elementary number theory to some beautiful method from an eye-catching result.

Thanks in advance.


Appendix 1

Induction: the proposition $p_n<2^{2^n}$ is obviously true for $n=1$. Now, assuming that it is true for some $k\in\mathbb N$, we have

$$p_{k+1}\le 1+p_1p_2\ldots p_k< 1+2^{2^1+2^2+\ldots +2^k}$$ $$=1+2^{2^{k+1}-2}<2^{2^{k+1}}$$ Which completed the proof with the principle of mathematical induction.

Appendix 2

Let $q$ be the $n^{th}$ prime number ($q=p_n$). Now, it's easy to show that every positive integer $k\le q$ could be written in the form $$k=m^2 p_1^{e_1}p_2^{e_2}\ldots p_n^{e_n}$$ Where $m<\sqrt q$ might be a composite number or a prime, and $e_i$ is either $1$ or $0$. So, since the strict upper bound of the number of naturals we could express by the above formula is $\sqrt q 2^n$, it gives $$q<\sqrt q2^n\implies q< 4^n$$ As desired.

1

There are 1 best solutions below

0
On BEST ANSWER

Let's begin with a variation of Erdős' argument that yields a tighter bound. Since every squarefree number $\leqslant x$ is the product of some set of distinct primes $\leqslant x$, we have

$$2^{\pi(x)} \geqslant Q(x).$$

Erdős' argument effectively uses a lower bound of $\sqrt{x}$, but we can easily show $Q(x) \geqslant \frac{x}{2}$, since

$$Q(x) \geqslant \lfloor x\rfloor - \sum_{p} \biggl\lfloor\frac{x}{p^2}\biggr\rfloor > x\Biggl(1 - \sum_p \frac{1}{p^2}\Biggr) - 1,$$

where the numbers divisible by the square of more than one prime are subtracted more than once (so the first inequality is strict for $x \geqslant 36$, compensating for the final $-1$). It's not hard to see $\sum_p \frac{1}{p^2} < \frac{1}{2}$, for

\begin{align} \sum_{p} \frac{1}{p^2} &= \frac{1}{4} + \frac{1}{9} + \frac{1}{25} + \sum_{p \geqslant 7} \frac{1}{p^2} \\ &< \frac{361}{900} + \sum_{k = 3}^{\infty} \frac{1}{(2k+1)^2} \\ &< \frac{361}{900} + \frac{1}{2}\sum_{k=3}^{\infty}\biggl(\frac{1}{2k(2k+1)} + \frac{1}{(2k+1)(2k+2)}\biggr) \\ &= \frac{361}{900} + \frac{1}{12} \\ &= \frac{109}{225}, \end{align}

and then one can verify $Q(x) \geqslant \frac{x}{2}$ for $x < 36$ by hand. Thus we have $2^{\pi(x)}\geqslant \frac{x}{2}$, which yields $\pi(x) \geqslant \frac{\log x}{\log 2} - 1$, and taking $x = p_n$ it yields $p_n \leqslant 2^{n+1}$. A more precise analysis of $Q(x)$ can only reduce the constant $\pm 1$, since we obviously have the upper bound $Q(x) \leqslant x$.

Unfortunately I don't know any elementary argument that shows $\pi(x) \geqslant x^{\alpha}$ for some $\alpha \in (0,1)$ [and doesn't yield the correct $x/\log x$ behaviour], so the next step is already giving the correct order of magnitude.

Chebyshev had the brilliant idea of using the central binomial coefficients to estimate $\pi(x)$. This works very well because they have a simple prime factorisation that we know exactly (for a suitable value of "know exactly"), and we know their magnitude.

Using $\lfloor 2y\rfloor - 2\lfloor y\rfloor \in \{0,1\}$ for all $y\in \mathbb{R}$ and Legendre's formula for the exponent of $p$ in the prime factorisation of factorials, we see that the exponent of $p\leqslant 2n$ in the factorisation of $\binom{2n}{n}$ is

$$e_p := \sum_{k : p^k \leqslant 2n} \Biggl(\biggl\lfloor \frac{2n}{p^k}\biggr\rfloor - 2\biggl\lfloor \frac{n}{p^k}\biggr\rfloor\Biggr) \leqslant \frac{\log (2n)}{\log p},$$

and hence

$$\binom{2n}{n} = \prod_{p \leqslant 2n} p^{e_p} \leqslant \prod_{p\leqslant 2n} p^{\log (2n)/\log p} = (2n)^{\pi(2n)}.$$

Using $\binom{2n}{n} \geqslant \frac{2^{2n}}{2n}$ this yields

$$\pi(2n) \geqslant \frac{2n\log 2}{\log (2n)} - 1,$$

and choosing $n = \bigl\lceil \frac{x}{2}\bigr\rceil$ we obtain

$$\pi(x) \geqslant \log 2\frac{x}{\log x} - 2$$

for $x \geqslant 2$. (Credit goes to fedja, whose excellent answer drove home the point that the proof is actually simple.)

To get an upper bound for $\pi(x)$, we note that every prime $n < p \leqslant 2n$ divides $\binom{2n}{n}$ with exponent $1$, whence

$$\prod_{n < p \leqslant 2n} p \leqslant \binom{2n}{n} \leqslant 2^{2n}.$$

Thus

$$\vartheta(2^k) - \vartheta(2^{k-1}) = \log \prod_{2^{k-1} < p \leqslant 2^k} p \leqslant 2^k\log 2,$$

and summing these estimates yields

$$\vartheta(2^k) < 2^{k+1}\log 2.$$

Choosing $k$ so that $x \leqslant 2^k < 2x$, we have

$$\vartheta(x) \leqslant \vartheta(2^k) < 2^{k+1}\log 2 \leqslant (4\log 2) x.$$

Now a summation by parts yields

\begin{align} \pi(x) &= \sum_{p \leqslant x} (\log p)\cdot \frac{1}{\log p} \\ &= \frac{\vartheta(x)}{\log x} + \int_2^x \frac{\vartheta(t)}{t(\log t)^2}\,dt \\ &\leqslant 4\log 2\Biggl(\frac{x}{\log x} + \int_2^x \frac{dt}{(\log t)^2}\Biggr) \\ &= 8 + 4\log 2\operatorname{Li}(x). \end{align}

With slightly more careful estimates, one can reduce the constant factor to $2\log 2$, and with some serious work one can get much closer to $1$, both for the upper and lower bounds.