I came across this proof in Proofs From the Book by Aigner and Ziegler. It uses the inequality $logx \leq \pi(x)+1$. (Here, we use natural logarithm)

The proof starts with the inequality

$log$ $x \leq 1+ \frac{1}{2} +\frac{1}{3} + \dots \frac{1}{n-1} + \frac{1}{n} \leq \sum{\frac{1}{m}},$ where the sum extends over all $m\in \mathbb{N}$ which have only prime divisors $p \leq x$

My first question is how do we define this sum, do these $m$'s consist of all possible products $p_1.p_2 \dots p_k$ where $p_1,p_2, \dots ,p_k$ are the all primes less or equal to $x$?

Now, the rest of the proof goes as: "Since every such $m$ can be written in a unique way as a product of the form $ \displaystyle \prod_{\substack{ p \leq x}} p^{k_p}$,

we see that the last sum is equal to $\displaystyle \prod_{\substack{ p \in \mathbb{P} \\ p \leq x}}(\sum_{k \geq0} \frac{1}{p^k})$. "

and after some steps the proof ends with the inequality $logx \leq \pi(x)+1$.

My second question is how do we write this sum-product $\displaystyle \prod_{\substack{ p \in \mathbb{P} \\ p \leq x}}(\sum_{k \geq0} \frac{1}{p^k})$?

  • $\begingroup$ First question: yes, exactly. Second question: We write this as the Euler product $\prod_{k=1}^r\left( 1-\frac{1}{p_k}\right)^{-1}$. $\endgroup$ – Dietrich Burde May 17 '16 at 14:21
  • $\begingroup$ You do not need the logarithm, the product is equivalent to the harmonic series, which diverges, so the product must also diverge, which is not possible if the number of primes is finite. $\endgroup$ – Peter May 17 '16 at 14:47
  • $\begingroup$ First question: note that all these factors can be repeated at will so that the products are unbounded. $\endgroup$ – Yves Daoust May 17 '16 at 15:03
  • $\begingroup$ For the first question: So $m=p_1^{\alpha_1}.p_2^{\alpha_2} \dots p_k^{\alpha_k}$ where $p_1,p_2,\dots,p_k$ are the primes less or equal to x. These $\alpha$ s can be zero. Do they have a maximum? If so, then we would have $\leq 1+ \frac{1}{2} +\frac{1}{3} + \dots \frac{1}{n-1} + \frac{1}{n} = \sum{\frac{1}{m}}$, right ? $\endgroup$ – Ninja May 17 '16 at 15:27
  • $\begingroup$ I realized that they do not have a maximum, that's why we use power series. Thank you all for enlightening me. $\endgroup$ – Ninja May 17 '16 at 17:44

Your Answer

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

Browse other questions tagged or ask your own question.