Mean value of $\Omega(n)$ is $\log\log n$

Question

This question is from my number theory assignment and I was unable to solve it. I have been following Dekonick and Luca.

Let $\Omega(n)$ be the number of prime divisors of n, counted with multiplicity ie the number of prime powers dividing n, for instance $\Omega(12) = 3$. Show that mean value of $\Omega(n)$ is $\log\log n$: $\frac{1}{N}\sum_{n\leq N} \Omega(n) = \log\log N+O(1)$.

Attempt: I thought of using Abel's Identity : $\sum_{n\leq N} f(n) = f(N)[N]- \int_{1}^x [t] f'(t)\,dt$.

Here $f(n) = f(p_1^{x_1} \cdots p_r^{x_r}) = x_1 + \dots + x_r$

So, I got $\sum_{n\leq N} f(n) = (x_1 + \dots + x_r)[N]- \int_{1}^{x} [t] (x_1+\dots+x_r) \log t\,dt$. Dividing by $N$, $((x_1 + \dots + x_r)[N])/N =O(1)$, and the other term after simplifying I got as $$(x_1+\dots+x_r)(\log N -1-(N\log N)/2+N/4+1/N(3/4))$$ which is not equal to what has to be proved.

So, please help.

Answer 1

Using a collection of useful results (left as a home exercise to polish the details) ... let's note by: $$d(n,k)=\left\{\begin{matrix} 1, & k\mid n \\ 0, & k \nmid n \end{matrix}\right.$$ Then, where $p_i$ is the $i$-th prime: $$\Omega(n)=\sum\limits_{p^\alpha \mid n}1= \sum\limits_{i=1}\sum\limits_{\alpha=1}d(n, p_i^\alpha)$$ And $$\sum\limits_{n=1}^N\Omega(n)= \sum\limits_{n=1}^N \left(\sum\limits_{i=1}\sum\limits_{\alpha=1}d(n, p_i^\alpha)\right)= \sum\limits_{i=1} \left(\sum\limits_{n=1}^N\sum\limits_{\alpha=1}d(n, p_i^\alpha)\right)=\\ \sum\limits_{i=1} \left(\sum\limits_{\alpha=1}\sum\limits_{n=1}^N d(n, p_i^\alpha)\right)= \sum\limits_{i=1} \left(\sum\limits_{\alpha=1}\left\lfloor \frac{N}{p_i^{\alpha}} \right\rfloor\right)=...$$ which is $$...=\sum\limits_{i=1} \nu_{p_i}(N!)=...$$ in fact $$...=\sum\limits_{i=1}^{\pi(N)} \nu_{p_i}(N!)$$ Given $$\frac{n}{p-1}-\log_2(n+1)<\frac{n}{p-1}-\log_p(n+1)\le\nu_p(n!)\le\frac{n}{p-1}$$ we have $$\sum\limits_{p\leq N}\frac{1}{p-1} - \frac{\pi(N)\log_2(N+1)}{N}<\frac{\sum\limits_{i=1}^{\pi(N)} \nu_{p_i}(N!)}{N}<\sum\limits_{p\leq N}\frac{1}{p-1}$$ Or $$\sum\limits_{p\leq N}\frac{1}{p} - \frac{\pi(N)\log_2(N+1)}{N}<\frac{\sum\limits_{i=1}^{\pi(N)} \nu_{p_i}(N!)}{N}<\sum\limits_{p\leq N}\frac{1}{p} + \sum\limits_{p\leq N}\frac{1}{p(p-1)}$$

The final result follows from the Prime Number Theorem and the summation of the reciprocals of the primes.

Answer 2

By definition, we know

\begin{aligned} 0\le\sum_{n\le N}[\Omega(n)-\omega(n)] &=\sum_{n\le N}\sum_{p^a\|n,a>1}a\le\sum_{a\ge2}a\sum_{p\le N}\sum_{\substack{n\le N\\p^a|n}}1 \\ &\le\sum_{a\ge2}a\sum_{p\le N}{N\over p^a}\le N\sum_{p\le N}\sum_{a\ge2}{a\over p^a} \end{aligned}

To evaluate the rightmost sum, we recall the properties of geometric series. That is, for $|z|<1$ there is

$$ {1\over1-z}=1+z+\sum_{r\ge2}z^r $$

Differentiating on both side, we have

$$ {1\over(1-z)^2}=1+\sum_{r\ge2}rz^{r-1} $$

Multiplying $z$ on both side gives

$$ \sum_{r\ge2}rz^r={z-z(z^2-2z+1)\over(1-z)^2}={z^2(2-z)\over(1-z)^2} $$

This indicates that

$$ \sum_{p\le N}\sum_{a\ge2}{a\over p^a}=\sum_{p\le N}{p^{-2}(2-p^{-1})\over(1-p^{-1})^2}\le\sum_{p\le N}{2\over(p-1)^2} $$

Since the right most sum is convergent, we conclude

$$ \sum_{n\le N}[\Omega(n)-\omega(n)]=\mathcal O(N) $$

which indicates that

$$ \sum_{n\le N}\Omega(n)=\sum_{n\le N}\omega(n)+\mathcal O(N)\tag1 $$

which converts our problem into a much more convenient one:

\begin{aligned} \sum_{n\le N}\omega(n) &=\sum_{n\le N}\sum_{p|n}1=\sum_{p\le N}\sum_{\substack{n\le N\\p|n}}1 \\ &=\sum_{p\le N}\left\lfloor\frac Np\right\rfloor=N\sum_{p\le N}\frac1p+\mathcal O(N) \end{aligned}

To continue, we summon Mertens' formula (a superior version is presented as Theorem 427 in Hardy & Wright):

$$ \sum_{p\le N}\frac1p=\log\log N+\mathcal O(1) $$

so that

$$ \sum_{n\le N}\omega(n)=N\log\log N+\mathcal O(N)\tag2 $$

Combining (1) and (2) gives the desired result.