0
$\begingroup$

Consider the following sum, where $\operatorname{li}((x)$ is the logarithmic integral function:

$$\operatorname{lisum}(x) = \sum_{k=1} ^{\lfloor\sqrt x\rfloor} \operatorname{li}((x/k)$$

For small $x$, $\operatorname{lisum}(x)>x$, but at about $x=\exp(\exp(2))$ and above, $\operatorname{lisum}(x)< x$.

The curious thing about this sum is the difference $\log(\log(x)) - \log(\log(\operatorname{lisum}(x)))$. Of course it becomes positive when $x>\operatorname{lisum}(x)$, but the behavior beyond that point is interesting. It reaches a small positive maximum but then decreases again, and the behavior as $x\rightarrow\infty$ is not clear to me.

As far as I can determine, the positive maximum of this difference occurs at $x=4028048.999\ldots$, just less than $2007^2$, where $\log(\log(x)) - \log(\log(\operatorname{lisum}(x))) = 0.0131248248\ldots$.

Curiously, at this value $\log(\log(x))=2.72187372\ldots$, $\log(\log(\operatorname{lisum}(x)))=2.708748902\ldots$, and $\exp(\exp(0.0131248248\ldots))=2.754432227\ldots$. All of these values are beguilingly close to $e$, but I cannot find a direct relationship to $e$ or a reason why the maximum occurs here.

Question 1: Why does this maximum occur so close to $e$ but not precisely at $e$?

Question 2: How does $\log(\log(x)) - \log(\log(\operatorname{lisum}(x)))$ behave as $x\rightarrow\infty$?

Up to about $x=\exp(\exp(3.4))$, the rate of growth of $\log(\log(\operatorname{lisum}(x)))$ accelerates, but then it begins to decelerate. (For example, $\log(\log(\operatorname{lisum}(\exp(\exp(3.4)))))-\log(\log(\operatorname{lisum}(\exp(\exp(3.3)))))=0.10069\ldots$, but $\log(\log(\operatorname{lisum}(\exp(\exp(3.5)))))-\log(\log(\operatorname{lisum}(\exp(\exp(3.4)))))=0.10068\ldots$.) It is not clear to me how $\log(\log(x)) - \log(\log(\operatorname{lisum}(x)))$ behaves beyond this point.

  • 0
    Just so we're clear: are you using the version of the logarithmic integral where the lower limit is $2$?2011-12-05
  • 0
    @geoffrey: Looking at the double logarithm is almost never the right thing to do for numerical computation. Even wildly different numbers seem close; notice $$\log\log (1000 000)-\log\log(500 000)\approx 0.0514.$$Since $\text{lisum}(x)\sim x\log 2$ (see my answer), $$\log \log x-\log \log \text{lisum}(x)=\log \frac{\log x}{\log \text{lisum}(x)}=\log \left(\frac{1}{1+\frac{\log\log 2+o(1)}{\log x}}+\right).$$Using the Taylor expansion, this goes to zero as $x\rightarrow \infty$. What this means is that even though they have different asymptotics, when you take $\log \log$ the limit is zero.2011-12-05
  • 2
    To add to this, I remember something a professor told me when I was working on a numerical project: "All functions look the same when you take $\log \log $." There are even many famous quotes in number theory such as "$\log \log x$ goes to infinity, but has never been observed to do so." To emphasize, $\log \log$ of a trillion is still less then $4$. In fact, the double logarithm of a billion trillions is still less then $4$.2011-12-05
  • 0
    No, I am using the plain logarithmic integral where the lower limit is 0. I checked the offset logarithmic integral that you mention, and the difference it makes is negligible for this sum. It decreases the sum by only about sqrt(x), which is negligible since, as Eric Naslund explains below, the sum itself is on the order of x.2011-12-05
  • 0
    @eric: Thank you for showing that the limit is 0. I think log log x is relevant here since, as you explain, it is related to omega(n), the number of distinct prime factors of n, and the Hardy-Ramanujan theorem shows that the normal order of omega(n) is log log n. Let me state the curious behavior of the function in another way: The derivative of log log x - log log (x log 2) is negative. But the derivative of log log x - log log lisum(x) is positive up to x=10^13 ! When the values up to 10 trillion do not reflect the asymptotic behavior, I think that is a phenomenon worthy of attention.2011-12-05
  • 1
    @GeoffreyCaveney: Yes, the asymptotic for $\sum_{n\leq x}\omega(n)$ is $x\log\log x$. But what I am trying to get as is that you should not then be taking the log log of this sum. Essentially you are looking at $\log\log$ of a modified version of the above sum, and there is no reason to do that, why not just look at the above sum by itself? We can saw so much, and they then imply all the results about the $\log \log$. The other way around is not true.2011-12-05

1 Answers 1

2

This is a very different way to look at this sum using number theory and the prime number theorem. I hope his approach explains some context where such sums may appear, it is not meant to be the shortest solution (for that just evaluate the sum), but it is motivated by looking at the average of $\omega(n)$, the number of distinct prime factors of $n$.

Consider $\omega(n)=\sum_{p|n}1$, and look at $\sum_{n\leq x}\omega(n).$ Then $$\sum_{n\leq x}\omega(n)=\sum_{n\leq x}\sum_{p|n}1=\sum_{p\leq x}\sum_{k\leq\frac{x}{p}}1=\sum_{p\leq x}\left[\frac{x}{p}\right].$$ Using the hyperbola method, the middle term also is $$\sum_{p\leq x}\sum_{k\leq\frac{x}{p}}1=\sum_{pk\leq x}1=\sum_{k\leq\sqrt{x}}\sum_{p\leq\frac{x}{k}}1+\sum_{k>\sqrt{x}}\sum_{p\leq\frac{x}{k}}1$$ $$=\sum_{k\leq\sqrt{x}}\pi\left(\frac{x}{k}\right)+\sum_{p\leq\sqrt{x}}\left(\left[\frac{x}{p}\right]-\left[\sqrt{x}\right]\right).$$ Now, by the prime number theorem, $\pi\left(\frac{x}{k}\right)=\text{li}\left(\frac{x}{k}\right)+O\left(\frac{x}{k}e^{-c\sqrt{\log\frac{x}{k}}}\right).$ Rewriting again, and taking into account that $\left[x\right]=x+O(1)$ this is $$\sum_{k\leq\sqrt{x}}\text{li}\left(\frac{x}{k}\right)+x\sum_{p\leq\sqrt{x}}\frac{1}{p}+O\left(\frac{x}{\log x}+\sum_{k\leq\sqrt{x}}\frac{x}{k}e^{-c\sqrt{\log\frac{x}{k}}}\right).$$ Hence $$\sum_{n\leq x}\omega(n)=\sum_{p\leq x}\left[\frac{x}{p}\right]=\sum_{k\leq\sqrt{x}}\text{li}\left(\frac{x}{k}\right)+x\sum_{p\leq\sqrt{x}}\frac{1}{p}+O\left(\frac{x}{\log x}\right).$$ The middle sum is $$\sum_{p\leq x}\left[\frac{x}{p}\right]=x\sum_{p\leq x}\frac{1}{p}+O\left(\frac{x}{\log x}\right)$$ so we conclude $$\sum_{k\leq\sqrt{x}}\text{li}\left(\frac{x}{k}\right)=x\sum_{\sqrt{x}

Remark: Also, why are you looking at the double logarithm? $\log \log x$ will be extremely close to $\log \log y$ for almost all small $x$ and $y$. For example, $\log \log(110 000) -\log \log (100 000)=0.0082..$

  • 0
    Thank you so much for this answer. Very helpful and informative!2011-12-05
  • 0
    About looking at log log x: I know the difference is always small, but my interest is in how the difference increases up to x=4028049 and then decreases, first at an accelerating rate but then at a decelerating rate at about x=10^13. This behavior is curious and I would like to understand it. I do not see behavior like this, for example, in the difference of the single logarithm, log x - log(lisum(x)).2011-12-05
  • 0
    @GeoffreyCaveney: Take a look at my comments just below your question.2011-12-05