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.

$\endgroup$
6
  • $\begingroup$ Just so we're clear: are you using the version of the logarithmic integral where the lower limit is $2$? $\endgroup$ Dec 5, 2011 at 17:15
  • $\begingroup$ @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. $\endgroup$ Dec 5, 2011 at 17:54
  • 2
    $\begingroup$ 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$. $\endgroup$ Dec 5, 2011 at 17:59
  • $\begingroup$ 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. $\endgroup$ Dec 5, 2011 at 18:26
  • 1
    $\begingroup$ @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. $\endgroup$ Dec 5, 2011 at 22:50

1 Answer 1

2
$\begingroup$

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}<p\leq x}\frac{1}{p}+O\left(\frac{x}{\log x}\right)=x\left(\log\log x-\log\log\sqrt{x}\right)+O\left(\frac{x}{\log x}\right)$$ $$=x\log2+O\left(\frac{x}{\log x}\right).$$

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..$

$\endgroup$
3
  • $\begingroup$ Thank you so much for this answer. Very helpful and informative! $\endgroup$ Dec 5, 2011 at 18:09
  • $\begingroup$ 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)). $\endgroup$ Dec 5, 2011 at 18:19
  • $\begingroup$ @GeoffreyCaveney: Take a look at my comments just below your question. $\endgroup$ Dec 5, 2011 at 18:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .