0
$\begingroup$

Is $$f(n)= \sum_{1\leq i \leq n}\log(i) - \sum_{\text{p is prime},\ p\leq n} \log(p)^2$$ a function of $\operatorname{O}(n^{\frac{1}{2}+\epsilon})$? if no, what do we know about its asymptotic growth?

I ploted it with matlab:

enter image description here

$\endgroup$
0
0
$\begingroup$

On other parts of math.SE, we learn how to estimate the second term. Question about Selberg's formula

$$ \sum_{p\le x}\log(p)^2 = x \log x - x + O \left( \frac{x}{\log x}\right)$$

and yet, by derivation of Stirling formula, we get the same order of magnitude.

$$ \log n! = n \log n - n + O(\log n)$$

By the triangle inequality we can conclude a trivial bound:

$$ \sum_{p\le n}\log(p)^2 - \log n! = O \left( \frac{n}{\log n}\right) $$


The first Chebyshev function looks similar but doesn't use a square. There are lots of these estimates if you poke around math.SE

I am going to re-write your summation using the prime counting function:

$$ \sum_{n \leq x} \bigg[ \log^2 n \big(\pi(n) - \pi(n-1)\big) - \log n \bigg] $$

By the prime number theorem we know how to estimate $\pi(n) - \pi(n-1)$:

$$ \pi(x) \approx \int_0^x \frac{dt}{\log t} \quad\text{ and }\quad \pi(n) - \pi(n-1)\approx \int_n^{n+1} \frac{dt}{\log t} \approx \frac{1}{\log n}$$

This leads to us writing summation of $\log n - \log n = 0$.

$\endgroup$

Your Answer

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