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.
Thanks in advance for your help!
What I have tried
-
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)$.
-
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)$.
-
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)$
-
Applying the explicit bounds for $\pi(x)$, we have that $\pi(x)=C \cdot \frac{x}{\log(x)}$, where $1<C<2$ is some real number that approaches $1$ as $x$ grows to infinity.
-
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.
-
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.
-
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:
- 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 |<S(n)<\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 |$$
-
Applying the explicit bounds for $\pi(x)$, we have that $\pi(x)=C \cdot \frac{x}{\log(x)}$, where $1<C<2$ is some real number that approaches $1$ as $x$ grows to infinity.
-
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.
-
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:
-
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.
-
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<C<2$ 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<C_{k}<4$ 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.
-
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}<S(n)<\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}$$
-
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}}$
Best Answer
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.