5
$\begingroup$

It seems to be the case that for any integer $x > 1 $, we have $ x \leq 2^{\pi(x)} $

I'm not sure whether this is obviously true, annoyingly false or difficult to prove. I'm hoping it's the former, and that I'm just being dim. I'm thinking along the lines of prime factorisation of $x$, but I can't see it. Any help would be greatly appreciated.

Thanks

$\endgroup$
  • $\begingroup$ Can you use the prime number theorem? $\endgroup$ – Unreasonable Sin Oct 21 '11 at 21:12
  • $\begingroup$ No. This has arisen as part of a question I'm trying to do. If it's not something elementary, then I must be approaching my original problem the wrong way. $\endgroup$ – MartinP Oct 21 '11 at 21:13
  • $\begingroup$ From Bertrand's postulate we have $\pi(2^n) \ge n$ (by induction on $n$). $\endgroup$ – Joel Cohen Oct 21 '11 at 21:27
  • $\begingroup$ You don't need the full prime number theorem; Bertrand's postulate will suffice. Of course that is not quite elementary either. $\endgroup$ – Henning Makholm Oct 21 '11 at 21:28
3
$\begingroup$

Suppose that $x$ is minimal such that $x>2^{\pi(x)}$. Let $y=\lceil x/2 \rceil$; then $2y\ge x>2y-2$. Bertrand’s postulate in its stronger form ensures that there is a prime between $y$ and $2y-2$ and hence between $y$ and $x$, so $\pi(x)\ge\pi(y)+1$, and therefore $2^{\pi(x)}\ge 2\cdot 2^{\pi(y)}\ge 2y = x$, which is a contradiction.

$\endgroup$
  • $\begingroup$ I like this and appreciate your help, but my question is from the introductory section of a course in number theory - I'm not sure if Bertrand's postulate is even included later in the course. If anyone's interested, the question wants me to prove that $ x \leq (1 + \frac{\log{x}}{\log{2}})^{\pi(x)} $, and I widdled it down to my question above. I'd really rather not see a full solution - any subtle hints would be greatly appreciated though. I haven't yet grasped the relevance of "log" when it comes to number theory - if anyone could shed any light, that too would be greatly appreciated. $\endgroup$ – MartinP Oct 21 '11 at 23:50
0
$\begingroup$

In "A Classical Introduction to Modern Number Theory" by Ireland and Rosen, a very close bound is obtained by completely elementary means.

Assum $p_n \le x < p_{n+1}$, where $p_i$ denotes the $i$'th prime. By definition, $\pi(x) = n$.

Considers the numbers up to $x$: $\{1,2,\cdots, x \}$. They are divisible only by primes among $\{ p_1, p_2, \cdots, p_{n} \}$. If you decompose those numbers into a square part and square-free part, i.e. write $a = rs^2$ where $r$ is a product of distinct primes and $s$ is a square, we see that there are 2 constraints on $r,s$:

  1. Since $r$ is square-free, it must be a product of distinct primes among the first $n$ primes. There are only $2^{n}$ options for $r$.

  2. Since $s^2 \le a$, we must have $s \le \sqrt{a} \le \sqrt{x}$, so there are at most $\sqrt{x}$ options for $s$.

All in all, there are at most $2^n \times \sqrt{x}$ options for those numbers between $1$ and $x$: $$ x \le 2^{n} \sqrt{x} = 2^{\pi(x)} \sqrt{x}$$

This shows that $\pi(x) \ge \log_{2} \sqrt{x} = \frac{\log_{2} x}{2}$. $\blacksquare$

Similarly, if we decompose those numbers into an $n$'th-power and an $n$-powerfree number, we find: $$\pi(x) \ge \frac{\ln x (1-\frac{1}{n}) }{\ln n} $$ But $n=2$ already gives the best bound. I will think later about improving this to $\pi(x) \ge \log_2 x$ - I believe it is possible with a similar method.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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