Asympototic estimation of log log function

Question

Let $N>0$ be an integer and consider the sum $\sum_{n=3}^N(\log \log N-\log \log n)$. It is not hard to see that this sum has the complexity $O(N^2)$ since $\log \log x <\log x<x$, so that the sum is smaller than $\sum_{n=3}^N N-n$. But can we find a better upper bound for this sum so that it has at most complexity $O(1)$? And what could be the best estimation of this sum?

Answer 1

I get that the sum is bounded by $N \ln(\ln(N))/\ln(N) $.

What follows is not always rigorous, but I think it has a good chance of being correst.

$0 < a < 1, a=e^{-1/c}$ so $1/c=-\ln(a), c=-1/\ln(a) $.

$\begin{array}\\ f(n) &=\sum_{k=3}^n (\ln(\ln(n))-\ln(\ln(k)))\\ &=\sum_{k=3}^{n^a} (\ln(\ln(n))-\ln(\ln(k)))+\sum_{k=n^a+1}^n (\ln(\ln(n))-\ln(\ln(k)))\\ &<n^a \ln(\ln(n))+\sum_{k=n^a+1}^n (\ln(\ln(n))-\ln(\ln(n^a)))\\ &<n^a \ln(\ln(n))+n(\ln(\ln(n))-\ln(\ln(n^a)))\\ &=n^a \ln(\ln(n))+n(\ln(\dfrac{\ln(n)}{\ln(n^a)}))\\ &=n^a \ln(\ln(n))+n(\ln(\dfrac{\ln(n)}{a\ln(n)}))\\ &=n^a \ln(\ln(n))+n(\ln(\dfrac{1}{a}))\\ &=n^a \ln(\ln(n))+n(-\ln(a))\\ &=n^{e^{-1/c}} \ln(\ln(n))+n/c \qquad 1/c=-\ln(a), a=e^{-1/c}, \ln(a)=1/c \\ &\approx n^{1-1/c} \ln(\ln(n))+n/c \qquad \text{if } c \text{ is large} \\ \end{array} $

If $c=n^{1/c}$, so the terms are approximately equal (aside from the $\ln(\ln(n))$) $c^c=n, c \ln(c)=\ln(n)$ so $c \approx \ln(n)/\ln(\ln(n)), n/c \approx n \ln(\ln(n))/\ln(n)$

Answer 2

By the Euler–Maclaurin formula, we have \begin{align} \sum\limits_{n = 3}^N {\log \log n} & = \int_3^N {\log \log t\,\mathrm{d}t} + \mathcal{O}(\log \log N)\\ & = N\log \log N - \int_3^N {\frac{{\mathrm{d}t}}{{\log t}}} + \mathcal{O}(\log \log N) \end{align} as $N\to+\infty$. Consequently, $$ \sum\limits_{n = 3}^N {(\log \log N - \log \log n)} = \int_3^N {\frac{{\mathrm{d}t}}{{\log t}}} + \mathcal{O}(\log \log N) $$ as $N\to+\infty$. Finally, using the asymptotic expansion of the logarithmic integral, we have $$ \sum\limits_{n = 3}^N {(\log \log N - \log \log n)} \sim \frac{N}{{\log N}}\left( {1 + \frac{{1!}}{{\log N}} + \frac{{2!}}{{\log ^2 N}} + \ldots } \right) $$ as $N\to+\infty$.