# Asymptotic limit of truncated Legendre sieve

Consider the truncated sum

$$S(x):=\sum_{\substack{{d\mid P(\sqrt{x})}\\{d\leq x}}}\mu(d)/d,$$

where $P(z)$ is the product of all primes less than or equal to $z$, and $\mu(d)$ is the Möbius function.

My question is simply:

Does $S(x)$ have a provable asymptotic limit?

The question is motivated by the following plot:

It is well known from the prime number theorem and Merten's product theorem that $$\frac{x}{\log x \cdot \pi(x)} \sim 1 \quad \textrm{and} \quad \log x \cdot \sum_{\substack{{d\mid P(\sqrt{x})}}}\mu(d)/d \sim 2 \textrm{e}^{-\gamma}.$$ And in seeing the plot, I got curious of $$\log x \cdot S(x) \sim ?$$ It is not possible to state from the numerical example what the asymptotic limit of $\log x \cdot S(x)$ will be. But note that so is the case also of $x/(\log x \cdot \pi(x))$, which provable tends to 1. What I'm curious about therefore, is whether $\log x \cdot S(x)$ will go all the way to 1 or stagnate before that.

I did check out chapter 4 of Opera de Cribro by Friedlander and Iwaniec. There it appears that at least in terms of the elementary Legendre sieve, it is not possible to prove the asymptotic limit of $S(x)$. It might be that an affirmative answer lies other places in that book, with more powerful sieving methods. I would be glad if anyone could point me to the right place in that case, as it is a rather chunky piece of literature to just browse through.

ADDED 1: Numerically, it appears that the constant $\sum_{k=1}^{\infty} M(k) \log \Big(1+\frac 1k\Big)$ that was stated below in Lucia's answer should be 1, as according to Terry Tao's comment. This is evidenced in the following plot:

ADDED 2: One could also anticipate the asymptotic limit $$S(x)\sim \frac{1}{\log x}$$ from the following sloppy heuristic: $S(x)$ can in some sense be seen as the mean value of prime densities below $x$. If we take those densities to be $1/\log x$ around $x$, the average density is simply $\textrm{li}(x)/x$. We know of course that this expression satisfies $$\frac{\textrm{li}(x)}{x} \sim \frac{1}{\log x}.$$ We might therefore anticipate $S(x)\sim 1/ \log x$. I have added a new version below of the first plot, that also includes the term $\log x \cdot \textrm{li}(x)/x$, revealing that this lies above $\log x \cdot S(x)$. Naturally, we would not expect the two to coincide, as $S(x)$ must interpreted as the mean of a random model where the actual prime distribution is just one specific outcome.

One can prove that $(\log x)S(x)$ does tend to a limit, but I don't think the limit is necessarily a nice constant. [Edit The limit is in fact $1$ as noted by Terry Tao and user45947. ] Put $M(z) = \sum_{n\le z} \mu(n)/n$. Note that by the prime number theorem $M(z) \ll (\log z)^{-A}$ for any $A>0$ and $z$ large enough. I'll prove that $$S(x) \sim \frac{1}{\log x} \sum_{k=1}^{\infty} M(k) \log \Big(1+\frac 1k\Big),$$ and the bound on $M(k)$ guarantees that the sum above is convergent. This constant can of course be computed (and should be checked with your numerics) but I don't see why it should be anything nice. [ Edit In fact one can see that $$\sum_{k=1}^{K} M(k) \log \Big( 1+ \frac 1k \Big) = \sum_{n\le K} \frac{\mu(n)}{n}\sum_{k=n}^{K}\log (1+1/k) = \sum_{n\le K} \frac{\mu(n)}{n} \log \frac{K+1}{n}.$$ Since $\sum_{n=1}^{K} \mu(n)/n = O((\log K)^{-A})$ and $-\sum_{n=1}^{\infty} \mu(n)(\log n)/n=1$, it follows that the constant is in fact $1$. ]
To prove the asymptotic formula, note that $S(x)$ counts all $n\le x$ except for those $n$ having a prime factor $p$ larger than $\sqrt{x}$. Thus $$S(x) = M(x) - \sum_{p>\sqrt{x}} \sum_{\substack{n\le x \\ p|n }} \frac{\mu(n)}{n}.$$
The term $M(x) = O(1/(\log x)^2)$ and so we focus just on the second term above. Writing $n=mp$ this is $$\sum_{p>\sqrt{x}} \frac{1}{p } \sum_{m\le x/p} \frac{\mu(m)}{m}.$$ Now let $1\le k\le \sqrt{x}$ and group the primes $p$ above according to the ranges $x/(k+1) < p \le x/k$. Thus the sum above equals $$\sum_{1\le k\le \sqrt{x}} M(k) \sum_{x/(k+1) <p\le x/k} \frac{1}{p}.$$ Now use the asymptotics for the sum of the reciprocals of primes to see that the inner sum over $p$ above is $$\sim \log \frac{\log (x/k)}{\log (x/(k+1))} \sim \frac{\log (1+1/k)}{\log x}.$$ From this the desired asymptotic follows.
• Formally, one has $M(z) = - \sum_{n>z} \mu(n)/n$, so the sum $\sum_{k=1}^\infty M(k) \log(1+\frac{1}{k})$ appears to telescope formally to $\sum_n \frac{-\mu(n) \log n}{n} = 1$. One can presumably justify these formal computations by zeta regularization. – Terry Tao Apr 23 '15 at 3:26
• Excellent answer! It seems from numerical testing that @TerryTao is correct with respect to the sum $\sum_{k=1}^\infty M(k)\log(1+\frac{1}{k})=1$. A plot demonstrating this is added to the original question. I had sort of suspected $S(x)\sim 1/\log x$ from a rather hand waving heuristic (which I also have added to my posting), so it's nice to see that this actually seems to be the case. – user45947 Apr 23 '15 at 8:32
• @TerryTao: Yes indeed it is $1$. I should have thought an epsilon more! – Lucia Apr 23 '15 at 12:43