0
$\begingroup$

What is the largest constant $c$ such that $ \frac{c\,x}{\ln x} < \pi(x)$ for all integers $x$? Also, if no one knows, do you think expecting an answer is unreasonable?

  • 0
    @WillJagy Coming up with a lower bound as above is actually not hard, and lhf has the correct answer (though without a proof). I have detailed a proof of this bound in my answer, below.2012-11-15

1 Answers 1

3

We begin with Dusart's lower bound, $\pi(x) > \frac{x}{\log x}+\frac{x}{(\log x)^2},$ valid for $x \geq 599$. In particular, $\pi(x)> c \cdot x/\log x$ for $x \geq 599$ with $c=1$. This result actually holds for $x \notin S:=\{2,3,4,5,6,9,10\}$, as some (finite) computation shows. Thus our maximal $c$ equals $\min\{\pi(k) \log k/k : k = S\},$ and this is attained for $k=2$. In other words, $\pi(n) \geq \frac{\log 2}{2} n/\log n$ for $n \geq 2$.

Along these lines, we have moreover that:

  1. $c$ can be taken minimally as $\log 2 \approx 0.693$ for all integers $n \geq 3$.
  2. $c$ can be taken minimally as $\frac{\log 6}{2} \approx 0.896$ for all integers $n \geq 5$.
  3. $c$ can be taken minimally as $\frac{2 \log 10}{5} \approx 0.921$ for all integers $n \geq 7$.
  4. $c$ can be taken minimally as $1$ for all integers $n \geq 11$.

(Here, I have replaced your $<$ with $\leq$.) The prime number theorem implies that result $4$ is the final word on the subject.

In my opinion, a better question concerns the constants in the pair of inequalities $c_1 \mathrm{Li}(n) \leq \pi(n) \leq c_2 \mathrm{Li}(n),$ as $\pi$ and $\mathrm{Li}$ overtake each other infinitely often.

Edit: Another fun question is the following: what is the minimal $c$ such that $\pi(n) \leq c n/\log n$ for all integers $n \geq 2$? Once again, Dusart's bounds (now the upper bound) implies that $\pi(n) < c n/\log n$ for $n \geq 355991$ and $ c= 1+\frac{1}{\log 355991} + \frac{2.51}{(\log 355991)^2} \approx 1.094.$ Computation then implies that $\pi(n) \leq \frac{30 \log 113}{113} \cdot\frac{n}{\log n} \approx 1.255 \frac{n}{\log n},$ and that this is the best $c$ value that holds for all $n \geq 2$. To contrast between this and the lower bounds on $c$, the progress in reducing $c$ to $1$ as $n \to \infty$ is quite incremental. Further improvements take the form $ \pi(n) \leq \frac{\pi(k) \log k_i}{k_i} \cdot \frac{n}{\log n} \text{ for } n > k_{i-1},$ in which $\{k_i\}$ is given by the following sequence: $[113,116],199,200,[283,287],293,317,[467,471],[661,663],683,684,[691,693],773,887,888,1129,[1327,1331],[1627,1629],[1637,1639],[1669,1676],1699,1759,[1789,1793],1801,1802,1811,2143,2144,2153,[2803,2805],[2861,2868],[2971,2983],[3023,3025],3041,3049,3089,[3947,3951],[4297,4313],4363,4364,4373,[4523,4526],\ldots$

For instance, we have $\pi(n) \leq 1.1438 n/\log n$ for $n \geq 4526$ by our final approximation. Note: there is no reason to stop here in particular. In fact, the sequence $\{k_i\}$ is infinite.