
> 
> **Question**: Let $\omega\_k$ be the number of distinct prime divisors of k.
>  What is the asymptotic growth of $C\_n := \sum\_{k=1}^n 2^{\omega\_k}$?
> 
> 
> 


Thank you for considering this elementary question. Below I give some motivation for this problem and some of my progress.


**Motivation:**
There are a couple. The first is purely number theoretic. Note that because $2^{\omega\_k} = \sum\_{d | k} |\mu(d)|$, we have $C\_n = \sum\_{k=1}^n \sum\_{d|k} |\mu(d)|,$ and thus $C\_n$ is the asymptotic growth of absolute values of the Möbius function (in other contexts this relates to the Prime Number Theorem, see [here](https://terrytao.wordpress.com/2009/08/30/an-elementary-inequality-involving-the-mobius-function/)). 


The second motivation comes from geometric group theory. The *commensurability index* of $A, B \leq G$ (all groups) is $[A : A \cap B][B: A \cap B]$. The *full commensurability growth function* assigned to a pair $A \leq B$ is defined to be 
$$
C\_n(A,B) = \# \{ \Delta \leq B : c(\Delta, A) \leq n \}.
$$
This is a generalization of the [subgroup growth](https://en.wikipedia.org/wiki/Subgroup_growth) function to pairs and it can be infinite in natural settings. The question above is the case $G(\mathbb{Z}) = \mathbb{Z} \leq \mathbb{R} = G(\mathbb{R})$ of the following



> 
> **Problem:** Compute the full commensurability growth function for the pairs $G(\mathbb{Z}) \leq G(\mathbb{R})$ where $G$ is a unipotent linear algebraic group.
> 
> 
> 


**Some progress:**
Write $f \preceq g$ if there exists $C > 0$ such that $f(n) \leq C g(C n)$. 
In [Proposition .3](https://arxiv.org/abs/1809.10332), it is shown that $n (\log(n))^{\log(2)} \leq C\_n \preceq n(\log(n))$. 



What is the asymptotic growth of $\sum_{k=1}^n 2^{\omega_k}$?
As you observe,
$$C\_n=\sum\_{k=1}^n\sum\_{d\mid k}|\mu(d)|=\sum\_{k=1}^n\sum\_{d\mid k\text{ squarefree}}1.$$
Exchanging the order of summation,
$$C\_n=\sum\_{d\leq n\text{ squarefree}}\sum\_{d\mid k\leq n}1=\sum\_{d\leq n\text{ squarefree}}\left\lfloor\frac{n}{d}\right\rfloor=n\sum\_{d\leq n\text{ squarefree}}\frac{1}{d}+O(n).$$
Now, the squarefree numbers have density $\frac{1}{\zeta(2)}=\frac{6}{\pi^2}$, so by summation by parts it's easy to find $\sum\_{d\leq n\text{ squarefree}}\frac{1}{d}\sim\frac{1}{\zeta(2)}\log n$, hence giving $C\_n\sim\frac{1}{\zeta(2)}n\log n$. You should be able to get an $O(n)$ bound on the error this way, and using the hyperbola method you should get some more precise estimates.


