# Approximation of partial sum over prime omega function

I haven't got any response yet. Here are the details:

The prime omega function $$\omega(n)$$ counts the number of distinct prime factors of a natural number $$n$$, and can be defined as $$\omega(n)=\sum_{p \mid n}1$$. Let $$S(N)=\sum_{n=1}^{N}n\omega(n)$$. Let $$\pi(n)$$ denote the number of primes up to $$n$$.

\eqalign{S(N) &=\dfrac{1}{2}\sum_{p{\text{ prime}} \atop p\leq N} p\left(\left\lfloor\dfrac{N}{p}\right\rfloor ^2+\left\lfloor\dfrac{N}{p}\right\rfloor\right)\cr &\approx \dfrac{N\pi(N)}{2}+\dfrac{N^2}{2}\sum_{p{\text{ prime}} \atop p\leq N} \dfrac{1}{p}\cr &\approx \dfrac{N\pi(N)}{2}+\dfrac{N^2}{2}\left[\log \log N+M+o(1)\right],\cr} where $$M$$ is the Meissel–Mertens constant.

The error term of this approximation is quite large. Is it possible to find a better approximation for this sum?

A better approximation for the sum of reciprocal primes (see https://arxiv.org/pdf/1703.08032.pdf) does not help to improve the overall sum.

The following approximation seems to work well. $$\tilde{S}(N,\epsilon)=\left[\dfrac{N\pi(N)}{2}+\dfrac{N^2}{2}\left(\log \log N+M\right)\right]\cdot \left(1+\dfrac{1}{(\log N)^{1+\epsilon}}\right)^{-1}$$, where $$\epsilon \in (0,1)$$. Define the percentage error as $$E(N,\epsilon)=\left |\dfrac{S(N)-\tilde{S}(N,\epsilon)}{S(N)}\right |\times 100$$. The following table gives an idea as to how well the approximation works for $$\epsilon=\dfrac{2}{5}$$.

$$N$$ $$S(N)$$ $$E\left(N,\frac{2}{5}\right)$$
$$10^3$$ $$1104960$$ $$0.192894816907$$
$$10^4$$ $$124547620$$ $$0.0961202670514$$
$$10^5$$ $$13558020500$$ $$0.0234415251444$$
$$10^6$$ $$1446379298344$$ $$0.00741488319826$$
$$10^7$$ $$152305298038685$$ $$0.0118235266249$$
$$10^8$$ $$15895296473923817$$ $$0.00880016331673$$
$$10^9$$ $$1648198262567978862$$ $$0.00327960320611$$
$$10^{10}$$ $$170070011690546177056$$ $$0.00270740071241$$
• Perhaps you can use the Erdős–Kac theorem. If you treat $\omega(n)$ as a random variable with mean and variance $\log \log n$, you get a sum of normal variables with mean and variance $n \log \log n$, so the total sum is a normal variable with mean and variance $\sum_{i=1}^n {i \log \log i}$, so you'd expect the number to be around $\sum_{i=1}^n {i \log \log i} \pm \sqrt{\sum_{i=1}^n {i \log \log i}}$. This is mostly heuristic, I don't know if assuming these are independent can be justified Sep 26 at 3:52
• @CommandMaster Thanks! I was not aware of this theorem. I shall try to get a better estimate using this. Sep 26 at 3:56
• My comment is inaccurate, the variance is actually $i^2 \log \log i$, but it should still give an error term of $\tilde O(n^{1.5})$ if it is correct Sep 26 at 4:02
• @Charles there is another error term, since $\lfloor \frac n p \rfloor^2 = (\frac n p + O(1))^2 = (\frac n p)^2 + O(\frac n p)$ Sep 26 at 4:04
• Assuming RH I can show this sum is $\frac12N^2\sum_{p\leq\sqrt N}\frac1p+\sum_{i\leq\sqrt N\\p\text{ prime}}{i (\text{li}(\frac{N^2}{i^2}) - \text{li}(N))}+O( N^{1.75 + \epsilon})$, but I'm not sure how to estimate the left part of the sum. Sep 26 at 5:38

By partial summation, one has $$S(N) = N\sum_{n=1}^N \omega(n) - \int_{1}^N \bigg(\sum_{n\leq t} \omega(n)\bigg) dt.$$ Using Mertens' theorem with the classical error term in the prime number theorem, one has, for some constant $$c > 0$$, \begin{aligned} \sum_{n=1}^N \omega(n) = \sum_{p\leq N} \Big\lfloor \frac{N}{p}\Big\rfloor &= N \sum_{p\leq N} \frac{1}{p} - \sum_{p\leq N} \left\{ \frac{N}{p}\right\} \\ &= N \Big(\log\log N + M + O\Big(\exp\big(-c\sqrt{\log N}\big) \Big) \Big)- \sum_{p\leq N} \left\{ \frac{N}{p}\right\} \end{aligned} where $$\{\cdot\}$$ denotes the fractional part. The sum of fractional parts can evaluated using Proposition 3 of this paper, and we have $$\sum_{p\leq N} \left\{ \frac{N}{p}\right\} = \int_{2}^N \frac{\left\{N/t \right\}}{\log t} dt + O\Big(\exp\big(-c(\log N)^{3/5-\varepsilon}\big) \Big).$$ By Proposition 2 of the above paper, the integral can be expanded asymptotically into a sum with descending powers of $$\log N$$: for any $$k\geq 1$$, $$\int_{2}^N \frac{\left\{N/t \right\}}{\log t} dt = c_0 \frac{N}{\log N} + c_1 \frac{N}{(\log N)^2} + \cdots + c_k \frac{N}{(\log N)^k} + O_k\left( \frac{N}{(\log N)^{k+1}}\right).$$ I leave the remaining details of the calculations to you, but this roughly shows that you should not hope for an error term better than $$O_k\left( \frac{N^2}{(\log N)^k}\right)$$ in your asymptotic expansion.

• Thanks for your answer. I came up with an empirical approximation that works really well for large $N$. I have no idea how to prove it though. Sep 26 at 6:39
• The Wikipedia page en.wikipedia.org/wiki/Prime_omega_function has a similar expansion for the mean value of $\omega$, which can be converted into the above sort of expansion by summation by parts. Sep 27 at 1:05
• @TerryTao, Thank you Prof. Tao for providing the solution idea. I shall look into the cited paper. Sep 27 at 2:41

As Prof. Tao suggested, we can estimate $$S(n)$$ using Summation by parts method. $$S(n)\sim nf(n) - \sum_{k=2}^{n-1}f(k),$$ where $$f(n)$$ approximates the sum $$\sum_{k=1}^{n}\omega(k)$$. $$\sum_{k=1}^{n}\omega(k) \sim f(n) = n \left[ \log \log n + M + \sum _{k\geq 1}\left(\sum _{j=0}^{k-1}\frac{\gamma_j}{j!} - 1\right)\frac{(k-1)!}{(\log n)^k}\right],$$ where $$M$$ is the Meissel-Mertens constant and $$\gamma_j$$s are Stieltjes constants.

Let $$T(n)=\sum_{m=2}^{n}f(m)$$. We can estimate $$T(n)$$ using Euler-Maclaurin formula. $$T(n)\sim \int_{2}^{n}f(x) dx + \frac{1}{2}\left(f(n)+f(2)\right) + \sum_{k=1}^{\infty}\frac{B_{2k}}{(2k)!}\left(f^{(2k-1)}(n)-f^{(2k-1)}(2)\right),$$ where $$B_k$$ is the $$k^{th}$$ Bernoulli number (with $$B_1=\frac{1}{2}$$).

Following this approach we get the following estimates (denoted by $$\hat{S}(n)$$) for $$S(n)$$ using $$5$$ terms in the summatory part of $$f(.)$$.

$$N$$ $$S(N)$$ $$\hat{S}(N)$$ Percentage error
$$10^3$$ $$1104960$$ $$1104744.867385$$ $$0.019470$$
$$10^4$$ $$124547620$$ $$124548871.265378$$ $$0.001005$$
$$10^5$$ $$13558020500$$ $$13559354294.383795$$ $$0.009838$$
$$10^6$$ $$1446379298344$$ $$1446466799145.233356$$ $$0.006050$$
$$10^7$$ $$152305298038685$$ $$152311928057871.725336$$ $$0.004353$$
$$10^8$$ $$15895296473923817$$ $$15895763172409493.954120$$ $$0.002936$$
$$10^9$$ $$1648198262567978862$$ $$1648231275071905930.713382$$ $$0.002003$$
$$10^{10}$$ $$170070011690546177056$$ $$170072396183761800450$$ $$0.001402$$
$$10^{11}$$ $$17482087123791069603605$$ $$17482264536463768138654$$ $$0.001015$$