showing that $\log(N) \leq \prod_{n \leq N} {(1-p^{-1})^{-1}}$

Question

i can't see that $H_n \leq \prod_{n \leq N}{(1-p^{-1})^{-1}}$

and i can't see that $\log(N) \leq \prod_{n \leq N} {(1-p^{-1})^{-1}}$

p is prime and $H_n$ is harmonic series

Answer 1

First of all, since $1/(1-x) = \sum_{k=0}^{\infty} x^k$ if $0 < x < 1$, for any prime $p$ $1/(1-1/p) = \sum_{k=0}^{\infty} 1/p^k$.

Therefore $\prod_{p \le n} 1/(1-1/p) =\prod_{p \le n} \sum_{k=0}^{\infty} 1/p^k $.

Consider what that last product of sums means: By unique factorization, every number with all its prime factors $\le n$ is represented. Written out, $\prod_{p \le n} \sum_{k=0}^{\infty} 1/p^k = \sum_{p|m => p\le n} 1/m $. This is probably the hardest step to understand, but it is a well-known number theoretic argument dating at least back to Euler.

But certainly all integers $\le n$ have all their prime factors $\le n$. (Of course a lot more do also.) Therefore $\sum_{p|m => p\le n} 1/m > \sum_{m=1}^n 1/m = H_n $.

(Added a little later.)

To show that $H_n > \ln n$, use $\int_1^n dx/x = \ln n$ and $1/k > \int_k^{k+1} dx/x$.

Answer 2

Take any integer $k\le n$. Then $k$ can be written as a product of primes $p\le n$. $$\sum_{k\le n}\frac{1}{k}\le\prod_{p\le n}\left(1+\frac{1}{p}+ \frac{1}{p^2}+\cdots\right)$$The above is a "$\le$" and not a "$=$" because there are many numbers greater than $n$ which can be factored by primes $p\le n$.

Hence the Right side weighs more than the left. For the next part proving $\log(n)<H_n$, as above, suffices.