# Sharp bounding of a sum involving Möbius function

I am trying to bound as sharply as possible the partial sum $$S(n)=\sum_{k=1}^{\frac{n}{p_{\pi\left(\sqrt{n}\right)}}} \mu(k) \left(\pi\left(\frac{n}{k}\right) + f(n,k)\right)$$

Where $$\pi(x)$$ is the prime counting function, $$p_{\pi\left(\sqrt{n}\right)}$$ is the greatest prime number less than $$\sqrt{n}$$, $$\mu(x)$$ is the Möbius function, and where $$\frac{2}{\log(\sqrt{n})}\cdot \pi\left(\frac{n}{k}\right)>f(n,k)>0$$.

I would like to have your feedback on the possible bounding I have sketched, which I do not know if it is correct, and hear your proposals to perform alternative boundings or improve the one I have derived.

What I have tried

1. As $$n$$ grows to infinity, $$\frac{f(n,k)}{\pi\left(\frac{n}{k}\right)}$$ approaches $$0$$, and thus we could state that, as $$n$$ grows to infinity, $$S(n)\sim\sum_{k=1}^{\frac{n}{p_{\pi\left(\sqrt{n}\right)}}} \mu(k) \pi\left(\frac{n}{k}\right)$$.

2. As $$n$$ grows to infinity, $$\frac{\frac{n}{p_{\pi\left(\sqrt{n}\right)}}}{\sqrt{n}}$$ approaches $$1$$, and thus we could state that, as $$n$$ grows to infinity, $$S(n)\sim\sum_{k=1}^{\sqrt{n}} \mu(k) \pi\left(\frac{n}{k}\right)$$.

3. An application of the Prime Number Theorem yields that, as $$n$$ grows to infinity, $$\frac{\pi\left(\frac{n}{k}\right)}{\sqrt{n}\space \cdot \space\pi\left(\frac{\sqrt{n}}{k}\right)}$$ approaches $$1$$, and thus we could state that, as $$n$$ grows to infinity, $$S(n)\sim\sqrt{n} \cdot \sum_{k=1}^{\sqrt{n}} \mu(k) \pi\left(\frac{\sqrt{n}}{k}\right)$$

4. Applying the explicit bounds for $$\pi(x)$$, we have that $$\pi(x)=C \cdot \frac{x}{\log(x)}$$, where $$1 is some real number that approaches $$1$$ as $$x$$ grows to infinity.

5. Applying Stirling approximation, we have that, as $$n$$ grows to infinity, $$\frac{\frac{n}{\log(n)}}{\sum_{k=1}^{n} \left(\frac{\log\left(\frac{n}{k}\right)}{\log\log\left(\frac{n}{k}\right)}\right)}$$ approaches $$1$$, and thus we have that $$\pi(n)=K \space \cdot \space \sum_{k=1}^{n} \left(\frac{\log\left(\frac{n}{k}\right)}{\log\log\left(\frac{n}{k}\right)}\right)$$, where $$K$$ is some real number that approaches $$1$$ as $$n$$ grows to infinity.

6. An application of the generalization of Möbius inversion formula yields then that, as $$n$$ grows to infinity, $$\sum_{k=1}^{\sqrt{n}} \mu(k) \pi\left(\frac{\sqrt{n}}{k}\right)= K_{\sqrt{n}} \space \cdot \space \frac{\log \sqrt{n}}{\log\log \sqrt{n}}$$, where $$K_{\sqrt{n}}$$ is some real number that approaches $$1$$ as $$n$$ grows to infinity.

7. Wrapping all up, we finally have that $$S(n)\sim K_{\sqrt{n}} \space \cdot \space \sqrt{n} \cdot \frac{\log \sqrt{n}}{\log\log \sqrt{n}}$$, where $$K_{\sqrt{n}}$$ is some real number that approaches $$1$$ as $$n$$ grows to infinity.

EDIT

After some external feedback relating this post, and @Greg Martin feedback, I realize that the bounding proposed in the OP needs to be amended, due to the oscilatory behaviour of S(n). Here is my alternative proposal:

1. As $$f(n,k)<\frac{2}{\log(\sqrt{n})}\cdot \pi\left(\frac{n}{k}\right)$$, then we have that $$\left |\sum_{k=1}^{\frac{n}{p_{\pi\left(\sqrt{n}\right)}}} \mu(k) f(n,k) \right |<\left |\frac{2}{\log(\sqrt{n})}\cdot \sum_{k=1}^{\frac{n}{p_{\pi\left(\sqrt{n}\right)}}} \mu(k) \pi\left(\frac{n}{k}\right)\right |$$

Therefore, we can state that $$\sum_{k=1}^{\frac{n}{p_{\pi\left(\sqrt{n}\right)}}} \mu(k) \pi\left(\frac{n}{k}\right)-\left |\frac{2}{\log(\sqrt{n})}\cdot \sum_{k=1}^{\frac{n}{p_{\pi\left(\sqrt{n}\right)}}} \mu(k) \pi\left(\frac{n}{k}\right)\right |

1. Applying the explicit bounds for $$\pi(x)$$, we have that $$\pi(x)=C \cdot \frac{x}{\log(x)}$$, where $$1 is some real number that approaches $$1$$ as $$x$$ grows to infinity.

2. Applying Stirling approximation, we have that, as $$n$$ grows to infinity, $$\frac{\frac{n}{\log(n)}}{\sum_{k=1}^{n} \left(\frac{\log\left(\frac{n}{k}\right)}{\log\log\left(\frac{n}{k}\right)}\right)}$$ approaches $$1$$, and thus we have that $$\pi(n)=K \space \cdot \space \sum_{k=1}^{n} \left(\frac{\log\left(\frac{n}{k}\right)}{\log\log\left(\frac{n}{k}\right)}\right)$$, where $$K$$ is some real number that approaches $$1$$ as $$n$$ grows to infinity.

3. An application of the generalization of Möbius inversion formula yields then that, as $$n$$ grows to infinity, $$\sum_{k=1}^{\sqrt{n}} \mu(k) \pi\left(\frac{\sqrt{n}}{k}\right)= K_{\sqrt{n}} \space \cdot \space \frac{\log \sqrt{n}}{\log\log \sqrt{n}}$$, where $$K_{\sqrt{n}}$$ is some real number that approaches $$1$$ as $$n$$ grows to infinity.

At this point, I doubt that the steps establishing that $$\sum_{k=1}^{\frac{n}{p_{\pi\left(\sqrt{n}\right)}}} \mu(k) \pi\left(\frac{n}{k}\right)\sim \sqrt{n} \cdot \sum_{k=1}^{\sqrt{n}} \mu(k) \pi\left(\frac{\sqrt{n}}{k}\right)$$ are correct (for the same reason that step 1 of the OP was not correct), but I believe that a bounding of $$\sum_{k=1}^{\frac{n}{p_{\pi\left(\sqrt{n}\right)}}} \mu(k) \pi\left(\frac{n}{k}\right)$$ in terms of $$\sqrt{n} \cdot \sum_{k=1}^{\sqrt{n}} \mu(k) \pi\left(\frac{\sqrt{n}}{k}\right)$$ is possible. Any suggestion? Do you validate steps 1 to 4 of this alternative proposal?

EDIT 2

I add what I believe could be a correct way to continue the bounding process (please comment and add feedback if it is right, wrong, or whatever you like):

From now on, for readability purposes, $$\alpha = \lfloor\frac{n}{p_{\pi(\sqrt{n})}}\rfloor$$.

We start replacing step 4:

1. An application of the generalization of Möbius inversion formula yields then that, as $$n$$ grows to infinity, $$\sum_{k=1}^{\alpha} \mu(k) \pi\left(\frac{\alpha}{k}\right)= K_{\alpha} \space \cdot \space \frac{\log \alpha}{\log\log \alpha}$$, where $$K_{\alpha}$$ is some real number that approaches $$1$$ as $$n$$ grows to infinity.

2. Applying the explicit bounds for $$\pi(x)$$, we have that $$\pi\left(\frac{\alpha}{k}\right)=C \cdot \frac{n}{k \cdot p_{\pi(\sqrt{n})}\log\left(\frac{n}{k \cdot p_{\pi(\sqrt{n})}}\right)}$$, where $$1 is some real number that approaches $$1$$ as $$x$$ grows to infinity. As we have that $$2 \cdot \log\left(\frac{n}{k \cdot p_{\pi(\sqrt{n})}}\right)>\log\left(\frac{n}{k}\right)$$, then we can state that $$\pi\left(\frac{n}{k}\right)=C_k \cdot p_{\pi(\sqrt{n})} \cdot \pi\left(\frac{\alpha}{k}\right)$$, where $$1 is some real number that approaches $$2$$ as $$n$$ grows to infinity. Therefore, we have that $$\sum_{k=1}^{\alpha} \mu(k) \pi\left(\frac{n}{k}\right)=C_{\alpha} \cdot p_{\pi(\sqrt{n})} \cdot \sum_{k=1}^{\alpha} \mu(k) \pi\left(\frac{\alpha}{k}\right)= C_{\alpha} \cdot p_{\pi(\sqrt{n})} \cdot K_{\alpha} \space \cdot \space \frac{\log \alpha}{\log\log \alpha}$$ where $$C_{\alpha}$$ approaches $$2$$ as $$n$$ grows to infinity.

3. Substituting in the result obtained in step 1., we have that $$\left(1-\frac{2}{\log(\sqrt{n})}\right) \cdot C_{\alpha} \cdot p_{\pi(\sqrt{n})} \cdot K_{\alpha} \space \cdot \space \frac{\log \alpha}{\log\log \alpha}

4. Looking at the limits of each element of the above expression when $$n$$ grows to infinity, we can state that, as $$n$$ grows to infinity, $$S(n)\sim 2 \cdot \sqrt{n} \cdot \frac{\log \sqrt{n}}{\log\log \sqrt{n}}$$

• Step 1 is already incorrect: because $\mu(k)$ changes sign, it's possible that the terms involving $f(n,k)$ give a contribution larger than the supposed main term. One would have to prove explicitly that this was not the case. (If the argument in step 1 were valid, one could easily establish the twin primes conjecture, for example.) Commented Jan 9 at 17:09
• @GregMartin thanks for your comment. I am not grasping how the terms involving $f(n,k)$ could give a contribution larger than $\pi\left(\frac{n}{k}\right)$. And I am very curious on your second statement, that if the argument in step 1 were valid, one could easily establish the twin primes conjecture. Could you post it a bit detailed as an answer? Commented Jan 9 at 20:21
• And if you have any comment / feedback over the next steps, or alternative ways to bound $S(n)$, happy to learn from you! Commented Jan 9 at 20:44
• $\alpha$ is not always a positive integer. Did you mean $\sum_{k=1}^{\left\lfloor\alpha\right\rfloor}$ instead of $\sum_{k=1}^{\alpha}$ ? Commented Jan 15 at 15:27
• @mathlove you are right, I will edit accordingly Commented Jan 15 at 15:41

I don't know how to get a good bound, but I think I can point out an error in your approach.

You are saying that since $$f(n,k)<\frac{2}{\log(\sqrt{n})}\cdot \pi\left(\frac{n}{k}\right)$$, the following inequality holds :

$$\left |\sum_{k=1}^{\alpha} \mu(k) f(n,k) \right |<\left |\frac{2}{\log(\sqrt{n})} \sum_{k=1}^{\alpha} \mu(k) \pi\left(\frac{n}{k}\right)\right |$$

However, for $$n=73$$, this inequality does not hold since $$\text{RHS}=\bigg|\frac{2(21-11-9-6+5-4+4)}{\log(\sqrt{73})}\bigg|=0$$

We can have $$\sum_{k=1}^{\alpha} \mu(k) f(n,k)\le \sum_{k=1}^{\alpha} f(n,k )<\frac{2}{\log(\sqrt{n})}\sum_{k=1}^{\alpha} \pi\left(\frac{n}{k}\right)$$ but I think this is not a good bound.

• thanks for your answer. I have come to think that step 1 is indeed innecessary, as the rest of the steps proposed work the same for $\pi\left(\frac{n}{k}\right)$ and for $\pi\left(\frac{n}{k}\right)+f(n,k)$, don't you think? Commented Jan 16 at 18:54
• @Juan Moreno : I am sorry but even though I've spent a lot of time considering your idea, I don't know if the steps proposed work for $\pi(\frac nk)+f(n,k)$. Commented Jan 18 at 15:44