Prove that $\pi(x) > \log x - 1$.


Based on a hint and very elementary methods, I got that $$ \prod_{p \leq x} (1-p^{-1})^{-1} \leq \prod_{k=2}^{\pi(x)+1} (1-k^{-1})^{-1}. $$ The second product telescopes to $\pi(x)+1$, and based on numerical calculations, I should be able to show that $\log x$ is less than this product. In fact, using this trivial bound $$ \log x = \int_1^x {dt \over t} < \sum_{k=1}^{[x]+1} {1 \over k}, $$ seems to hold for $x \geq 5$. The remaining cases could be checked separately. So is there a simple way to show that $$ \sum_{k=1}^{[x]+1} {1 \over k} < \prod_{p \leq x} (1-p^{-1})^{-1} $$ for $x \geq 5$? It only needs to be verified for positive integers, so I thought induction might work, but I'm not seeing how to deal with a sum and a product together. I also thought about expanding $\log x$ into a series another way, but its power series doesn't converge where we would need it to. In fact, I'm fairly confident this is the right approach, because of the close comparison between $\log x$ and these partial sums of the harmonic series. One approach from here is to do something like this, but with a finite number of terms, it seems to get really messy really fast.

Notes: $\log$ is natural, $[x]$ is the floor function, and $p$ ranges over primes.

  • 3
    $\begingroup$ Expand $(1-p^{-1})^{-1}$ into a geometric series. Cut that off at $p^{-k}$ when $p^k > x$. Multiply the finite sums. Every $k^{-1}$ for $k \leqslant x$ (and some more) occurs in the sum. $\endgroup$ – Daniel Fischer Nov 21 '13 at 17:00
  • $\begingroup$ Similar post: math.stackexchange.com/questions/567350/… $\endgroup$ – A l'Maeaux Nov 22 '13 at 10:11

Expand the factors into geometric series,

$$\left(1 - \frac{1}{p}\right)^{-1} = \sum_{\mu=0}^\infty \frac{1}{p^\mu}.$$

If you are comfortable with multiplying infinite series, you will note that thus

$$\prod_{p\leqslant x}\left(1 - \frac{1}{p}\right)^{-1} = \sum_{k \in A(x)} \frac{1}{k},\tag{1}$$

where $A(x) = \{ n \in \mathbb{N}^+ : \text{ all prime factors of $n$ are } \leqslant x\}$. Since a number $\leqslant x$ cannot have a prime factor $> x$, we have $\{1,\, 2,\, \dotsc,\, \lfloor x\rfloor\} \subset A(x)$, so the inequality

$$\sum_{k = 1}^{\lfloor x\rfloor} \frac{1}{k} \leqslant \prod_{p\leqslant x}\left(1 - \frac{1}{p}\right)^{-1}$$ follows. (You had the upper limit of the sum as $\lfloor x\rfloor+1$, which is more than needed, since $\sum_{k=1}^n \frac1k > \log (n+1)$. Nevertheless, for $x \geqslant 2$, the product is also greater than the larger sum. If $\lfloor x\rfloor +1$ is composite, $\frac{1}{\lfloor x\rfloor+1}$ is included in the sum, and if $\lfloor x\rfloor+1$ is prime, the sum includes $\frac{1}{\lfloor x\rfloor + 2} + \frac{1}{\lfloor x\rfloor+4} > \frac{1}{\lfloor x\rfloor+1}$ [if $x \geqslant 3$] or $\frac{1}{4}+\frac{1}{8} > \frac{1}{3}$ [if $2\leqslant x < 3$]. If $1\leqslant x < 2$, the inequality only holds for the smaller sum, since then the product is $1$, as an empty product.)

If you are not yet sure how to justify $(1)$, estimate each geometric series by a partial sum,

$$\left(1 - \frac{1}{p}\right)^{-1} > \sum_{\mu = 0}^{\left\lfloor \frac{\log x}{\log p}\right\rfloor} \frac{1}{p^\mu},$$

and multiply these finite sums,

$$\prod_{p\leqslant x}\left(1 - \frac{1}{p}\right)^{-1} > \prod_{p\leqslant x} \sum_{\mu_p = 0}^{m_p} \frac{1}{p^{\mu_p}} = \sum_{k\in B(x)} \frac{1}{k},$$

where $B(x) = \{ n \in \mathbb{N}^+ : n \text{ is a product of prime powers }\leqslant x\}$, and $m_p = \left\lfloor \frac{\log x}{\log p}\right\rfloor$. Again, we have $\{1,\,2,\,\dotsc,\,\lfloor x\rfloor\} \subset B(x)$ and thus the product is seen to be greater than $\log (\lfloor x\rfloor+1)$. To be certain that the product of the partial sums is already greater than the sum to $\lfloor x\rfloor +1$ - which is, as indicated, more than necessary - you can take a larger partial sum, summing to $m_p+2$ suffices (for $x \geqslant 2$).

  • $\begingroup$ Thanks! This is probably more detail than is warranted though, considering this is homework. $\endgroup$ – A l'Maeaux Nov 21 '13 at 20:35
  • $\begingroup$ Oops. I completely missed that. Don't tell anyone. $\endgroup$ – Daniel Fischer Nov 21 '13 at 20:35

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.