« first day (3317 days earlier)      last day (755 days later) » 

Koro
Koro
09:59
I know that $\pi(n) \ge \frac{\ln n} {2\ln 2} $.
How do I replace n by any x>1?
Because apparently this inequality is true even when x is not an integer.
2
Proof: Let $p_i$ denote ith prime. Fix k. Define N(x) = no. of elements in {n<=x: n is not divisible by p_j for any j>k}
We can write such n as n= n'^2s. Clearly, $n'\le \sqrt x$. And s can be chosen in 2j ways so we have $N(x) \le 2^j \sqrt x$.
Taking $ j=\pi(x) $, we have $N(x) =[x] $, where [.] represents greatest integer function.
We can even get a tighter inequality : $N(x) \le 2^j \sqrt{[x]} $. With this, it follows that $[x] \le 2^j \sqrt{[x]} $. The result follows.
But I don't understand how to prove it for any x (i.e. without involving any [.]).
Martin Sleziak
Martin Sleziak
10:31
@Koro Did you check whether this isn't answered on the main site. For example, this post: $\pi(x)\geqslant\frac{\log x}{2\log2}$ for all $x\geqslant2.$
The answer gives a proof and a reference. (Although I have checked neither the proof given here nor the reference.)
4
Q: $\pi(x)\geqslant\frac{\log x}{2\log2}$ for all $x\geqslant2.$

CIJLet $\pi$ be the prime counting function. Then $\pi(x)\geqslant\log x/(2\log2)$ for all $x\geqslant2.$ Maybe I am missing something pretty evident, but, so far, I have proved that $\pi(x)\geqslant\log{\lfloor x\rfloor}/(2\log2)$ using a method Paul Erdős used to prove that there are infinit...

number-theory elementary-number-theory prime-numbers
3
A: $\pi(x)\geqslant\frac{\log x}{2\log2}$ for all $x\geqslant2.$

Marco CantariniTake the first $j$ primes $2,3,\dots,p_{j}$ and define $N\left(x\right)=\left|\left\{ n\leq x:\, p\nmid n\,\forall p>p_{j}\right\} \right|$. If we write an $n$ in the form $$n=n_{1}^{2}m$$ with $m$ a squarefree number, we have $$m=2^{a_{1}}3^{a_{2}}\cdots p_{j}^{a_{j}}$$ where $a_{i}\in\left\{ 0,...

 
1 hour later…
Koro
Koro
11:53
@MartinSleziak I had checked this one before posting here. But the answer there did not seem to address this issue. There was however a discussion about in the comments below the answer but it seems unanswered still (or probably I didn't understand it). About the reference: the proof I wrote above is inspired from the same reference.
My doubt is the blue colored part in the following extract of the comment taken from below the above linked answer: "I understand what do yo mean, but this is not really a problem. Using this technique, you can show that the sum of the reciprocal of primes diverges and this imply that $π(x)$ is greater than, for example $x^\frac 12$. $\color{blue}{\text{So this imply that the passage from $⌊x⌋$ to x doesn't create problems.} }$"
Martin Sleziak
Martin Sleziak
12:45
The answer mentions Hardy-Wright - this is what's written in the book:
user image
 
1 hour later…
Koro
Koro
13:52
Indeed. N(x) was defined as an integer but in the proof $N(x)=x$ is taken which should be true only if x is an integer.
Martin Sleziak
Martin Sleziak
The above argument basically shows $n\le 2^{\pi(n)}\sqrt n$, i.e., $\sqrt n\le 2^{\pi(n)}$.
We would like to have
\begin{align*}
\sqrt{n+1} &\le 2^{\pi(n)}\\
\sqrt{n(n+1)} &\le 2^{\pi(n)}\sqrt{n}
\end{align*}
so it suffices to show $$n+1\le 2^{\pi(n)}\sqrt{n}.$$
I.e., we would like to see that the estimate $2^{\pi(n)}\sqrt{n}$ actually counts at least one number greater than $n$.
If we know from Bertrand's postulate that there is a prime $p>\frac n2$, then we have $2p>n$. But it would definitely be better to have a more straightforward argument - without relying on Bertand.
Koro
Koro
There is a proof of the same statement in Ireland and Rosen as well. (I have not yet studied Bertrand's postulate). That proof also uses N(x)=x (in different symbols of course).
This is proposition 2.4.2 in the book.
Martin Sleziak
Martin Sleziak
Yes, Proposition 2.4.2. I was just checking the book.
user image
Koro
Koro
the set $f_S(x)$ there is just N(x) in Hardy's except one difference: S can be any set of primes whereas to define N(x) we consider first j primes (so we have the natural order of numbers here).
Martin Sleziak
Martin Sleziak
14:10
Sorry, I do not see an immediate way to fix this.
Although it feels like squeezing one more element should not be that difficult....
Koro
Koro
np, thanks. Have a great day!
Martin Sleziak
Martin Sleziak
14:39
It seems that the same proof appears on many posts on Mathematics - without addressing this specific issue.
2
A: Lower bound for prime number function $\pi(x)$

luluWell, here's a way to get a cheap lower bound. Note that any $n≤x$ can be written uniquely as $m\times k^2$ where $m$ is square free. It follows that $$x≤ 2^{\pi(x)}\sqrt x\implies \sqrt x ≤ 2^{\pi(x)}\implies \frac {\log_2(x)}2≤\pi(x)$$ This seems better than your desired bound.

0
A: Prime counting function inequality

OfirIn "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 ...

 
4 hours later…
Martin Sleziak
Martin Sleziak
19:05
@C.I.J. I understand what do yo mean, but this is not really a problem. Using this technique, you can show that the sum of the reciprocal of primes diverges and this imply that $\pi(x)$ is greater than, for example $x^{1/2}$. So this imply that the passage from $\left\lfloor x\right\rfloor $ to $x$ doesn't create problems. Nice observation, however ;) — Marco Cantarini Oct 30, 2015 at 8:15
On thing that seems unusual to me concerning the above comment is the suggestion to use $\pi(x)\ge\sqrt{x}$. Once I have this, then it is an immediate consequence that $$2^{\pi(x)}\ge 2^{\sqrt x} \ge \sqrt x.$$
So I do not need the previous estimate with square-free at all to arrive at $2^{\pi(x)}\ge\sqrt{x}$ if I am allowed to use $\pi(x)\ge\sqrt{x}$.

« first day (3317 days earlier)      last day (755 days later) »