Why is $\sum_{p\leq x} \log p=O(x)$?

76 Views Asked by At

I know that $$2^{2n}=(1+1)^{2n}={2n\choose 0}+\cdots+{2n\choose n}+\cdots+{2n\choose 2n}\geq {2n\choose n}\geq \prod_{n < p \leq 2n} p$$

If we let $n=2^{k-1}$ this implies that $\prod_{2^{k-1} < p \leq 2^k}\leq 2^{2^k}$.

Hence, $\sum_{2^{k-1} < p \leq 2^k}\log p\leq 2^k \log 2$. It follows that $$\sum_{ p \leq 2^k}\log p\leq (2^k+2^{k-1}+\cdots+1)\log 2\leq 2^{k+1}\log 2.$$

My friend said that implies that there exists some constant $C$ and $x_0$ s.t for all $x\leq x_0$ $\sum_{ p \leq x}\log p\leq Cx$.

Can someone please explain to me why that should be the case?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $x>0$, and let $n_x=\lfloor \log_2 x\rfloor$ so that $2^{n_x}\leqslant x\leqslant 2^{1+n_x}$. Using what you said we have $$ \sum_{p\leqslant x}\log p\leqslant \sum_{p\leqslant 2^{1+n_x}} \log p\leqslant 4\log 2\times 2^{n_x}\leqslant (4\log 2) x $$ The constant $C=4\log 2$ works there.